寻找点集子集的良好算法

Question

我正在尝试寻找适用于在较大数据集中搜索2D点子集的算法。 一张图片胜过千言万语:

任何想法如何实现这一点？请注意，转换仅为旋转和缩放。

似乎最相关的问题是点集配准[1]。我正在尝试使用CPD和其他刚性和非刚性算法的实现，但它们似乎在查找较大点集中的小子集方面表现不佳。

另一种方法可能是使用星跟踪算法，如[2]中提到的“角度方法”，或者像[3]这样更健壮的方法。但是，它们似乎都是针对大型输入集和目标集而设计的。我正在寻找更少可靠但更简约的东西...

感谢任何想法！

[1]: http://en.wikipedia.org/wiki/Point_set_registration [2]: http://www.acsu.buffalo.edu/~johnc/star_gnc04.pdf [3]: http://arxiv.org/abs/0910.2233

- RobSis

---

你能提供更多的上下文细节吗？例如，您是否仅假定2D点，还是算法也应适用于更高的维度？您要搜索匹配的点集的典型大小是多少？您只有一个模板要查找，还是会一个接一个地搜索许多模板？ - BConic

输入集大约会有5到15个点。目标集大约有1000个点，但可以分成更小的区域...最终，我想找到最相似的匹配，因此输入集可能不完美。 - RobSis

@RobSis 我很好奇你是如何解决你的问题的。我需要解决类似的问题，如果你能告诉我你的经验中哪种算法最适合这种类型问题，我会非常感激。我已经研究了RPM、ICP和CPD方法，但无法为我的3D数据产生令人满意的结果。 - Arash_D_B

@RobSis，抱歉让这个旧帖子重见天日。但我正在寻找做同样的事情，只不过是进行翻译和旋转。你是否找到了准确的方法来匹配子集与集合？谢谢！ - anti

Answer 1

以下是与您的问题可能相关的一些论文:

• 欧几里得运动下的几何模式匹配 (1993) L. Paul Chew，Michael T. Goodrich，Daniel P. Huttenlocher，Klara Kedem，Jon M. Kleinberg，Dina Kravets。
• 二维点模式的快速期望时间算法 (2004) Wamelena, Iyengarb。
• 刚性运动下部分点集模式匹配的简单算法 (2006) Bishnua, Dasb, Nandyb, Bhattacharyab。
• 相似变换下平面点集的精确和近似几何模式匹配 (2007) Aiger和Kedem。

顺便提一下，您最后的参考文献让我想起了:

• 点模式匹配在航天学中的应用 (1994) G. Weber、L. Knipping和H. Alt。

- mrtubis

Answer 2

我认为你应该从输入点的子集开始，并确定所需的转换以匹配大集合的子集。例如：

• 选择输入的任意两个点，比如A和B。
• 将A和B映射到大集合的一对中，这将确定比例和两个旋转角度（顺时针或逆时针）。
• 将相同的缩放和变换应用于第三个输入点C，并检查大集合是否存在一个点。您将需要检查两个位置，一个用于每个旋转角度。如果点C存在于大集合中应该在的位置，则可以检查其余的点。
• 对于大集合中的每对点重复此过程。

我认为您还可以尝试匹配3个输入点的子集，因为知道三角形的角度在缩放和旋转下是不变的。

这些是我的想法，我希望它们能帮助解决您的问题。

- RonL

Answer 3

我会尝试使用迭代最近点算法。像你所需要的这种简单版本应该很容易实现。

- McMa

---

不确定ICP是否适合，因为它必须在靠近解的情况下初始化才能收敛。 - BConic

你说得完全正确！当ICP用于匹配数百万个3D点时，它对初始猜测非常敏感，但我认为在这种简单的情况下，它应该能够通过所有点的“暴力”匹配。如果最坏的情况发生，他可以尝试1000个随机的初始位置:D - McMa

Answer 4

看一下几何哈希。它允许在不同的变换下找到几何模式。如果只使用旋转和缩放，那么它将非常简单。

主要思想是将模式编码为“本地”坐标，这在变换下是不变的。

- Andrey Rubshtein

Answer 5

你可以尝试使用Geohash。将点转换为二进制并交错排列。测量距离并与原始值进行比较。你也可以尝试旋转Geohash，例如z-curve或morton curve。

- Micromega