使用仅平移和旋转的方法将一组二维点对齐到另一组点。

Question

我在使用OpenCV，但我认为没有这样的函数。可以找到用于查找仿射变换的函数，但是仿射变换包括缩放操作，而我只想考虑旋转和平移。

假设我有两组二维点 - 每组都有确切的50个点。

例如，集合A = {x1，y1，x2，y2，...，x50，y50}

集合B = {x1'，y1'，x2'，y2'，...，x50'，y50'}

我想找出最接近将集合A映射到集合B的旋转和平移组合。我猜我会将“最接近”定义为最小化A中点与对应B中点之间的平均距离。即，最小化（x1，y1）和（x1'，y1'）等之间的平均距离。

我猜可以通过暴力测试所有可能的平移和旋转来实现此目的，但这将非常低效。请问是否有更简单的方法？

谢谢！

- Andrew

---

点之间是否存在一一对应关系？它们真的是同一个点，只需要找到变换吗？ - phkahler

Answer 1

这个问题有一个非常优雅的解决方案，涉及到近似矩阵的奇异值分解（点对之间的距离）。这被称为正交 Procrustes 问题，源于一个希腊传说，讲述一个人提供旅行者可以适合任何人的床。

解决方案是找到给定（不一定正交）矩阵的最近正交矩阵。

- hardmath

---

谢谢。我在你回答的时候找到了同样的解决方案：http://en.wikipedia.org/wiki/Procrustes_analysis - Andrew

@Andrew：在我看来，这是奇妙而令人惊讶的奇异值分解应用。Peter Schonemann的解决方案是受到他在心理学/社会科学测试指标中的应用的启发。如果您确信要排除镜像（而不是平移和旋转），则需要对奇异值进行微调。 - hardmath

Answer 2

我在Excel中的做法是创建几列来表示这些点。 单元格表示一组的旋转/平移（不需要旋转和平移两个）。 然后是表示那些相同点的旋转/平移的列。
接下来是另一列，用于表示旋转/平移后的点之间的距离。
然后是一个单元格，用于表示点之间距离的总和。 最后，使用Solver来优化旋转和平移单元格。

- LanceH

---

谢谢您的回答。我能够通过计算每组的平均点来计算平移，并使用这个页面来确定旋转角度http://en.wikipedia.org/wiki/Procrustes_analysis，从而完成我所需的操作。 - Andrew

Answer 3

如果你修正一些旋转，可以使用三分搜索得到答案。在x上运行搜索，并对每个测试的x在y上运行以获得最佳值。这将给出正确的答案，因为函数（相应距离的总和）是凸函数（可以通过观察函数在任何直线上的限制是一维凸函数来证明；最后一个是标准事实：几个凸函数的和是凸函数）。

我可以提出一种基于三分搜索的方法，而不是暴力枚举角度。选择一些不是很大的步长S。计算(0, S, 2S,...)中每个角度的目标函数。然后，如果S足够小，我们可以排除一些段(iS，(i + 1)S)的考虑。即具有角度iS和(i + 1)S的函数值相对较大的段。如果实现得当，这可以给出答案并比暴力枚举更快。

- Sergey Bankevich

---

感谢您的回答。我能够通过计算每个集合的平均点来计算平移，并使用此页面来确定旋转角度http://en.wikipedia.org/wiki/Procrustes_analysis - Andrew

即使在一维情况下，使用平均点也无法得到任何好的答案近似。例如：一个集合（0、2、100）的平均值为34，另一个集合是（0、50、100）的平均值为50。移动后，您将得到（16、18、116），并且16+32+16=64。但是，如果您不移动，则只会得到48。即使在平面上旋转也没有帮助。 - Sergey Bankevich

@SergeyBankevich：使用均值作为翻译可以最小化均方距离，这比平均距离更有价值。 - Eric

@Eric：你说得对。但问题是关于平均距离的。无论如何，似乎作者对距离度量并不十分明确，最终可能会采用你提出的方法。 - Sergey Bankevich