algorithm - 从两组匹配对的算法

Question

我有两组，每组都是一对数字的列表

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

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

Answer 1

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

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

希望这可以帮助！

Answer 2

是的，假设只有旋转、缩放和平移可以做到这一点（除了“噪声”和“倾斜”部分，我不确定）。

一种方法：

1. 确定每组的质心（2D 平均值）。
2. 确定每组的最小二乘 (2D) 斜率。
3. 确定每组的 2D 方差。
4. 重新映射第一组，使用 Centroid Difference to Translate、Slope Difference to Rotate(*) 和 Variance Difference to Scale，这样两个集合现在具有相同的 Centroid、Slope 和 Variance。
5. 对两组进行排序，然后比较点的相等性/相似性。（或者，您可以在它们之间进行 RSM（均方根）差异作为“噪声”/差异的度量）。

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