从简单的2D图像中提取线段的简单有效方法是什么？

Question

具体来说,我试图从游戏'小行星'的截图中提取所有相关的线段.我已经查看了各种边缘检测方法,但似乎没有一个方法适合我的问题有两个原因:

1. 它们检测平滑的轮廓,而我只需要检测直线段,而只检测一定长度范围内的直线段.现在,这些约束应该使我的任务比一般情况更容易,但我不想只使用一个完整的边缘检测器,然后清除曲线的结果,因为这将是非常昂贵的.速度对我的目的至关重要.

2. 它们输出修改后的图像,其中边缘是高光,而我想要一组像素坐标来描绘检测到的线段的端点.或者,每个段中包括的所有像素的列表也将起作用.

我有一个暗示,一个可能的解决方案将涉及霍夫变换,但我不知道如何使用它来获得线段的实际位置(即像素空间中的端点).虽然我做了,但我不知道这是否是最简单或最有效的做事方式,因此问题标题的一般措辞.

最后,这是一个示例图像:

请注意,所有主线的长度和密度都相似,并且整体图像对比度非常高.我希望我的问题的解决方案将利用这些功能,因为再次,效率是至关重要的.

需要注意的是:虽然这个上下文中的大多数线段都是多边形的一部分,但我不想要一个依赖于这个事实的解决方案.

Answer 1

看看线段检测器算法。

这是他们所做的：

您可以在页面底部找到令人印象深刻的视频。

有一个开箱即用的 C 实现（适用于 C++ 编译器）。只有一两个文件，没有额外的依赖

但是，请注意，该算法受 GNU Allegro GPL 许可。