我有一些地图文件,其中包含表示隧道的“折线”(每条线都是一个顶点列表),我想尝试找到隧道的“中心线”(大致以下图红色所示)。
过去使用 Delaunay 三角剖分取得了一些成功,但我想避免使用该方法,因为它通常不允许轻松/频繁修改我的地图数据。
您有任何想法吗?
我有一些地图文件,其中包含表示隧道的“折线”(每条线都是一个顶点列表),我想尝试找到隧道的“中心线”(大致以下图红色所示)。
过去使用 Delaunay 三角剖分取得了一些成功,但我想避免使用该方法,因为它通常不允许轻松/频繁修改我的地图数据。
您有任何想法吗?
它的好处在于它使用了大多数库中可用的图像处理和图形操作的混合,可以轻松并行化,速度相对较快,可以调整为使用相对较小的内存占用,并且如果存储中间结果,则不必在修改区域外重新计算。
我打了引号的“算法”,只是因为它是我开发的,肯定不能应对病态情况。如果你的图有很多环,可能会出现一些幻影线。稍后会有更多关于此的说明和例子。
丑陋的部分是您需要能够填充地图,这并不总是可能的。几天前,我发布了一条评论,问您的图是否可以被填充,但没有得到答案。所以我决定发帖。
思路如下:
这种并行化机会是由于每个分区可以在独立的进程中计算,并且结果图可以进行分区以找到需要删除的小循环。这些因素也允许通过串行化来减少所需的内存,而不是并行计算,但我没有深入研究。
我不会提供伪代码,因为难点仅限于您的库未涵盖的部分。 我将发布从连续步骤中获得的图像,而不是伪代码。 我使用Mathematica编写程序,如果对您有帮助,我可以发布它。
A- 从漂亮的洪水填充隧道图像开始
B- 应用距离变换
距离变换提供图像的距离变换,每个像素的值被替换为其到最近背景像素的距离。
您可以看到我们所需路径是隧道中的局部极大值
C- 使用适当的核对图像进行卷积
选择的内核是像素半径为2的拉普拉斯高斯核。它具有增强灰度边缘的神奇属性,如下所示。
D- 截断灰度级并将图像二值化
以获得中心线的清晰视图!
评论
也许对你来说已经足够了,因为你知道如何将一条细线转换为近似的分段序列。但是对我而言,这不是情况,所以我继续这个路径以获得所需的线段。
E-图像分割
这里是算法的一些优势:您可以开始使用并行处理或决定逐个处理每个线段。您还可以将结果线段与之前的运行进行比较并重复使用先前的结果。
F-质心检测
子图像中的所有白点都被替换为仅位于质心的一个点
XCM = (Σ i∈Points Xi)/NumPoints
YCM = (Σ i∈Points Yi)/NumPoints
白色像素很难看到(随着参数“a”age的增加呈指数级地难以看到),但它们确实存在。
G-从顶点设置图
使用选定的点作为顶点形成图形,但没有边缘。
H-选择候选边缘
使用点之间的欧几里得距离选择候选边缘。使用一个截止值来选择适当的边缘集。这里我们使用子图像大小的1.5倍。
如您所见,结果图表中有一些小环,我们将在下一步中移除它们。
H- 移除小循环
使用循环检测例程,我们会删除长度小于某个值的小循环。截止长度取决于一些参数,您应该根据自己的图表集合进行经验性的确定。
I- 就这样!
您可以看到,结果中心线向上移了一点。原因是我在Mathematica中叠加不同类型的图像……而我放弃了试图说服程序按照我的意愿操作 :)
在测试过程中,我收集了一些图片。它们可能是世界上最不像隧道的东西,但我的“隧道101”走失了。
无论如何,这里它们是。请记住,我上移了几个像素…
.
如果您能访问Mathematica 8(我今天得到了它),那么有一个新函数Thinning。看看: