寻找最优旋转角度

Question

我有一个应用程序，必须从一组15个有序且索引的3D点（X1、X2、...、X15）中找到旋转，并将其与另一组具有相同索引的15个点（1个初始点对应1个最终点）进行比较。

我已经阅读了许多关于使用欧拉角（对某些人来说很麻烦）、四元数或将向量投影在基轴上来找到旋转的内容。但是我有一个额外的限制：我的最终集合中的一些点可能是错误的（即坐标错误），因此我想区分要求远离中位旋转的点。

我的问题是：对于每组3个点（不是排列的点）及其图像，我都可以计算四元数（根据变换矩阵不是纯旋转的事实，我有一些附加计算，但这可以完成）。因此，我得到了一组四元数（最多455个），并且我想删除错误的四元数。

是否有办法找出哪些点给出了远离平均旋转的旋转？“平均值”和“标准偏差”对四元数有意义吗？还是必须计算欧拉角？一旦我有了“好”的四元数集，如何计算“平均”四元数/旋转？

谢谢，Ricola3D

- Ricola3D

Answer 1

在计算机视觉中，有一种称为RANSAC的技术可以实现您所提出的类似功能。您不必找到所有可能的四元数，而是使用最少量的点对应来找到单个四元数/变换矩阵。然后，您将评估所有点的拟合质量，并丢弃那些拟合得不够好的点。如果您没有足够的良好匹配，可能是因为在原始集合中得到了错误的匹配。因此，您将放弃该尝试并重试。如果您确实获得了足够的良好匹配，则会对所有内点进行最小二乘回归拟合，以获得新的变换矩阵，然后迭代直到满意为止。

或者，您可以获取所有已标准化的四元数并查找它们之间的点积。点积应始终为正；如果任何给定计算的点积不是正的，则应否定其中一个四元数的所有分量并重新计算。然后，您就有了四元数之间的距离度量，可以进行聚类或寻找间隙。

- JCooper

---

+1 -- 我试图回想起这个技术叫什么名字，但我记不起来了... - comingstorm

谢谢，我会尝试看看在我的数据集上哪种方法最好（即最快）。 - Ricola3D

Answer 2

这里有两个问题：

• 如何为任意数量的点计算“最佳拟合”？
• 如何决定接受哪些点，拒绝哪些点？

---

对于第一个问题的一般答案是，“做一个最小二乘拟合”。对于这个问题，四元数可能比欧拉角更好；可以尝试以下方法：

foreach point pair (a -> b), ideal rotation by unit quaternion q is:
   b = q a q*   ->   q a - b q = 0

因此，寻找q的最小二乘拟合：

minimize sum[over i] of |q a_i - b_i q|^2
under the constraint:  |q|^2 = 1

如上所述，最小二乘问题是线性的，除了约束条件外，这使得它比欧拉角公式更容易解决。

---

对于第二个问题，我可以看到两种方法：

• 如果您的点不太偏离，可以尝试使用所有点运行最小二乘求解器，然后回去，排除“异常值”（那些平方误差最大的点对），再试一次。
• 如果极不一致的点使上述过程失效，您可以尝试选择随机的、小的3或4对子集，并为每个子集找到一个最小二乘拟合。如果这些结果中有一个大的群体具有相似的旋转和低总误差，您可以使用这个来确定“好”的对（从而消除坏的对）；然后回去找到所有好的对的最小二乘拟合。

- comingstorm

---

L1范数最小化——其中你最小化绝对偏差的总和而不是平方偏差——比最小二乘法更能抵抗异常值。通常这需要更复杂的优化方法，如线性规划，但在这里可能会有用。 - japreiss

谢谢。对于最小二乘拟合，我本来想做类似的事情，但不确定“求和”和“减法”在四元数中是否有意义，因为它在旋转中没有意义。对于第二个问题，我的点不能太远，但是一点误差可能会对算法后续步骤产生悲惨的影响。但我知道我的对象必须被“民主地”放置。所以我可以用您的第一个建议分两步完成，或者也许我可以通过比较它们的相对位置来区分我的点，从而获得更好的复杂性？ - Ricola3D

是的，四元数和是有定义的（尽管如你所说，它对旋转没有意义）；同样地，平方范数 |q|^2 = q q* 也是有定义的。对于第二个问题：如果你的“坏”点对离正确的旋转不太远，你应该尝试第一个建议，看看它是否可以正常工作。这将需要两个最小二乘步骤：一个初始步骤涉及所有点，另一个在拒绝坏点后进行的最终步骤。 - comingstorm

最小二乘求解器的渐近复杂度可以非常合理：对于N个点和C个要优化的值，它是O((N+C)C^2)。由于你要解决一个四元数，C的小常数为4，因此您的复杂度与点数呈线性关系。 - comingstorm