从两个集合中匹配成对的算法

Question

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

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

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

- rossb83

---

在编程中，“set1”中的一个点“对应”于“set2”中的一个点，您具体是什么意思？ - alexkelbo

@alexraasch 在特定的全局映射下低欧几里得距离。 - John Dvorak

@alexraasch，我猜它的意思是通过某个度量标准，例如欧氏距离来衡量距离的近远。 - miku

没有足够的数据来确定。或者你没有解释清楚！还有一个问题，set1中的所有点是否都有相同的转换方式才能在set2中呈现？ - mamdouh alramadan

@mamdouhalramadan 寻找一个仿射变换T：[x,y,z]=>[x,y,z]和映射M：S1=>S2，使得对于S1中的每个s1，M(s1)接近于T(s1)。 - John Dvorak

Answer 1

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

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

希望这能帮到你！

- templatetypedef

---

这些点并不是随意放置的。它们形成一个长方形，但非常明确定义的形状。 - rossb83

@rossb83- 即使您知道两个形状是相同的，ICP通常也会被使用。这对于尝试恢复点被转换的方式非常有用，因为您知道这些点定义了相同的形状，但除此之外没有其他信息。 - templatetypedef

“set-Shape相似度”和“set-Point相似度”之间存在显著差异。我不确定这些算法分别解决了哪些问题？ - RBarryYoung

Answer 2

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

一种方法：

1. 确定每组数据的质心（2D均值）。
2. 确定每组数据的最小二乘（2D）斜率。
3. 确定每组数据的2D方差。
4. 重新映射第一组数据，使用质心差异进行平移，使用斜率差异进行旋转(*)，使用方差差异进行缩放，以便两组数据现在具有相同的质心、斜率和方差。
5. 对两组数据进行排序，然后比较点的相等性/相似性。（或者，您可以通过RSM（均方根）差异来衡量它们之间的“噪声”/差异）。

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

- RBarryYoung