寻找隧道的“中心线”？

Question

我有一些地图文件，其中包含表示隧道的“折线”（每条线都是一个顶点列表），我想尝试找到隧道的“中心线”（大致以下图红色所示）。

过去使用 Delaunay 三角剖分取得了一些成功，但我想避免使用该方法，因为它通常不允许轻松/频繁修改我的地图数据。

您有任何想法吗？

- sje397

---

在GIS.se上的问题：http://gis.stackexchange.com/questions/2775/find-tunnel-center-line - sje397

@belisarius：我想得到一条线（在数学意义上）- 即墙壁是无限薄的线（向量），我希望得到一个无限细的中心线作为输出。 - sje397

@belisarius 我还没有选择解决方案。我会研究一下你提到的“去除小循环”的评论，因为这是我现有的Delauny隧道/岩石分类器存在的问题。我的问题实际上是关于如何高效地计算和集成地图的小区域变化，因为我已经能够生成初始的“全局”图表，并且预计算的效率并不是一个问题。不幸的是，没有人详细讨论过这个特定的问题 - 这完全是我的问题，因为我在问题中没有表述清楚。当我有时间时，我会重新表述一下。 - sje397

@sje 谢谢你的回答。请在你有时间更新问题时给我留言。祝你好运！ - Dr. belisarius

@belisarius 谢谢。我被推到了其他事情上，但是你的答案和这个也非常有帮助。 - sje397

Answer 1

一种适用于本地化数据变化的“算法”

---

评论家的看法

好处

它的好处在于它使用了大多数库中可用的图像处理和图形操作的混合，可以轻松并行化，速度相对较快，可以调整为使用相对较小的内存占用，并且如果存储中间结果，则不必在修改区域外重新计算。

坏处

我打了引号的“算法”，只是因为它是我开发的，肯定不能应对病态情况。如果你的图有很多环，可能会出现一些幻影线。稍后会有更多关于此的说明和例子。

丑陋的部分

丑陋的部分是您需要能够填充地图，这并不总是可能的。几天前，我发布了一条评论，问您的图是否可以被填充，但没有得到答案。所以我决定发帖。

---

概述

思路如下：

1. 使用图像处理获取表示中心路径的像素细线
2. 将图像分割成与隧道最窄通道相对应的块
3. 在每个分区中，使用包含像素的“质心”表示一个点
4. 使用这些像素来表示图形的顶点
5. 根据“近邻”策略向图形添加边缘
6. 在引入的图形中去除不必要的小循环
7. 结束- 剩余的边缘代表您想要的路径

这种并行化机会是由于每个分区可以在独立的进程中计算，并且结果图可以进行分区以找到需要删除的小循环。这些因素也允许通过串行化来减少所需的内存，而不是并行计算，但我没有深入研究。

---

情景

我不会提供伪代码，因为难点仅限于您的库未涵盖的部分。 我将发布从连续步骤中获得的图像，而不是伪代码。 我使用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。看看：

- Dr. belisarius

---

非常棒的回答。关于洪水填充问题没有回答，我很抱歉 - 事实上，我不确定这是否可能。我会仔细考虑一下。这里有很多需要思考的地方。非常感谢您付出了如此多的努力。 - sje397

令人印象深刻！我想，经过对每个顶点的隧道宽度进行初步注释后，本地重新填充不会太困难。在第一次填充后计算出隧道宽度。在更改周围切出一个区域，然后应用类似于这样的东西来进行切割应该不会太难。 - Rex Kerr

@Rex Kerr，删除边缘和合并图形的算法并不难。实际上，我已经在逐个合并点了。如果修改后的区域具有简单的几何表达式（矩形、圆形等），整个过程都很容易。如果泛洪填充可行，我想我会发布一个示例。 - Dr. belisarius

@Rex Kerr 更具体地说：重新合并修改后的区域需要两个几何对象..1) 修改后的区域和2) 原始地图中的边界。从边界中获取图形顶点，以创建与新区域相邻的候选接近性边缘。 - Dr. belisarius

@belisarius - 同意。我认为这不是一个微不足道的变化，但如果可以对顶点间距等进行某些假设，我不认为会有任何巨大的概念问题。无论如何，再次表示印象深刻！ - Rex Kerr

赞一个，对有趣的解决方案和回答中所付出的努力表示赞赏！ - Simon

Answer 2

这是一个相当经典的骨架化问题，有很多算法可供选择。一些算法原则上适用于轮廓线，但由于几乎每个人都在图像上使用它们，所以我不确定这些东西会有多少可用性。无论如何，如果您可以绘制并填充污水管轮廓，然后使用骨架化算法，您就可以得到接近中线的东西（在像素分辨率内）。

然后，您可以沿着这些线行走，并使用圆进行二分搜索，直到至少命中两条不同的线段（如果您在分支点处，则需要三条）。最初命中的两个点的中点或触及最初三个点的圆的中心是中心的良好估计。

- Rex Kerr

---

一个骨架本身就足够准确了。问题在于我找到的实现方式没有很好地处理经常变化的地图数据（即非常大的地图中的局部变化）。 - sje397

大多数算法本身无法将局部更改传播得太远 - 为什么不直接剪切地图的局部部分，重新进行骨架化，在最后修复任何差异（例如，在一些距离上两个答案之间进行线性插值）呢？ - Rex Kerr

Answer 3

使用skimage包，配合Python编程语言，这个任务变得非常简单。

import pylab as pl
from skimage import morphology as mp

tun = 1-pl.imread('tunnel.png')[...,0]        #your tunnel image
skl = mp.medial_axis(tun)                     #skeleton

pl.subplot(121)
pl.imshow(tun,cmap=pl.cm.gray)
pl.subplot(122)
pl.imshow(skl,cmap=pl.cm.gray)
pl.show()

- Developer