从两个集合匹配对的算法

Question

我有两个集合，每个集合是一对数字的列表

Set1 =[(x1, y1), (x2, y2), ..., (xN, yN)]
Set2 =[(a1, b1), (a2, b2), ..., (aN, bN)]

如果绘制在XY平面上，Set1和Set2具有相同的基本形状，但是Set2的数据点是Set1的旋转/平移/缩放/噪声/倾斜版本。每个集合中的配对顺序是随机的。有没有一种有效的方法来确定set1中的哪些点对应于set2中的对应点？

Answer 1

是的，假设只有旋转、缩放和平移可以完成（除了“噪音”和“倾斜”部分，我不确定）。

一种方法：

1. 确定每个集合的质心（2D平均值）。
2. 确定每个集合的最小二乘（2D）斜率。
3. 确定每个集合的2D方差。
4. 使用质心差转换第一个集合，斜率差旋转（*）和方差差缩放，这样两个集合现在都有相同的质心、斜率和方差。
5. 对两个集合进行排序，然后比较点是否相等/相似。（或者，您可以在它们之间进行RSM（均方根）差异，作为噪声/差异的度量）。

（*-请注意，反射和/或对称可能会导致旋转部件出现问题。）

Answer 2

你正在寻找一系列算法，试图最小化两个点云之间的差异。这是一个相当难解决的问题，可以有多种解决方案（例如，如果给你两个立方体，有许多可能的旋转是有效的）。

一种特别流行的方法是ICP（迭代最近点）算法，该算法从候选猜测开始，并不断完善它，直到达到某种正确性标准或时间到期。这可能是一个很好的出发点。

希望这有帮助！