algorithm - 将一组线拟合到多边形上的最佳拟合算法

Question

我有两组线，集合 A 和 B。这两组中所有线的起点和终点都是已知的，我想找到最适合集合 B 到集合 A 的旋转和平移。有无缩放:

• 没有一对一的映射。我相信这排除了 Kabsch 算法，尽管我可以设想一个使用它的蛮力算法。
• 集合 B 可能包含 A 中的部分线段。它可能包含相当稀疏的线数。
• B 中的线条将是错误的 - 可能观察到 A 中不存在的线条。
• 当然，可能存在不止一种可能的“匹配”

对于某些背景，这是基于原始图像的机器人定位系统的一部分。

• A 组是“ map ”- 数据是从导入的 dxf 文件导入的。
• B 组是一组观察到的线。

我环顾四周，例如这里:

How to align shapes together? (Geometrical Best-Fit Algorithm)

这是一种聪明的做法吗？快速浏览图像处理文献，形状匹配似乎更像是光栅图像的模式匹配 - 对于这个问题来说可能有点矫枉过正。

目前我能想到的最好方法是使用类似霍夫变换的方法，将 B 中的每条线沿着 A 中的每条线提取，并为这些代表的旋转/变换设置 bin。我还没有编写代码并尝试过它 - 有点想避免重新发明轮子。

非常感谢任何想法和意见。

Answer 1

一般的解决方案是从集合A中提取“特征”，并将特征与集合B进行比较。

一个例子:考虑集合 A 中的所有独特角度，并计算不同的独特角度对。在您的 A 组示例中，只有三种可能的情况:(0,0)、(0,90)、(90,0)。对集合 B 中所有线的角度进行排序，并与集合 A 中的线对进行匹配。示例:如果角度为 0,5,50,93,129，则角度为 (0,5)，(0,93)，( 5,93), (50, 129) 是匹配候选。一旦您有了候选人，您就可以进一步筛选他们。

根据集合 A 中的线条类型，您可以提取相关特征。示例:如果您的所有线都是垂直或平行的，则您可以拥有线间距等特征。