找到隧道'中心线'？

Question

我有一些由'折线'组成的地图文件(每条线只是一个顶点列表)代表隧道,我想尝试找到隧道的"中心线"(粗略地显示在下面的红色).

我过去在使用Delaunay三角测量方面取得了一些成功,但我想避免使用该方法,因为它(通常)不允许轻松/频繁地修改我的地图数据.

关于我如何能够做到这一点的任何想法？

Answer 1

一种适用于本地化数据更改的"算法".

评论家的观点

好的

好的部分是它使用大多数库中可用的图像处理和图形操作的混合,可以轻松并行化,合理快速,可以调整为使用相对较小的内存占用而不必在修改之外重新计算区域,如果您存储中间结果.

坏

我在引号中写了"算法",仅仅是因为我开发它并且肯定不足以应对病态案例.如果你的图表有很多周期,你可能会得到一些虚线.更多关于此和后面的例子.

和丑陋的

丑陋的部分是你需要能够填充地图,这并不总是可行的.我几天前发表了一条评论,询问你的图表是否可以填满,但没有得到答案.所以我决定发布它.

素描

这个想法是:

1. 使用图像处理来获得表示中心路径的精细像素线
2. 将图像划分为与隧道最薄的通道相称的块
3. 在每个分区处,表示包含像素的"质心"处的点
4. 使用这些像素表示图形的顶点
5. 根据"近邻"策略将边添加到图表
6. 去除诱导图中的虚假小周期
7. 结束 - 剩余的边缘代表您想要的路径

并行化机会源于以下事实:可以在独立进程中计算分区,并且可以对结果图进行分区以找到需要移除的小循环.这些因素还允许通过序列化来减少所需的内存,而不是并行地进行计算,但我并没有这样做.

剧情

我不会提供伪代码,因为困难的部分只是你的库所没有的.我将发布连续步骤产生的图像,而不是伪代码.我在Mathematica中编写了这个程序,如果有一些服务我可以发布它.

A-从充满洪水的隧道图像开始

B-应用距离变换

该距离变换给出了距离变换图像,其中每个像素的值被它的距离替换为最接近的背景像素的.
您可以看到我们所需的路径是隧道内的Local Maxima

C-用适当的内核卷积图像

选定的内核是像素半径为2 的拉普拉斯高斯核.它具有增强灰度边缘的神奇属性,如下所示.

D-截止灰度级并将图像二值化

要获得中心线的美景!

评论

也许这对你来说已经足够了,因为你知道如何将细线转换成近似的分段线段序列.对于我来说情况并非如此,我继续这条道路来获得所需的细分.

电子图像分区

以下是算法的一些优点出现时:您可以开始使用并行处理或决定一次处理每个段.您还可以将生成的段与上一次运行进行比较,然后重复使用以前的结果

F-质量检测中心

每个子图像中的所有白点仅由质心的一个点代替
XCM = (Σ i?Points Xi)/NumPoints

YCM = (Σ i?Points Yi)/NumPoints

白色像素是很难看到(与参数"一"渐近艰难时代),但它们在那里.

G-从顶点设置图形

使用选定的点作为顶点形成图形.仍然没有边缘.

H-选择候选边缘

使用点之间的欧几里德距离,选择候选边.截止值用于选择一组适当的边.这里我们使用1.5 subimagesize.

正如您所看到的,生成的Graph有一些小循环,我们将在下一步中删除它们.

H-删除小循环

使用循环检测程序,我们将小循环移除一定长度.截止长度取决于几个参数,你应该根据经验来计算图形族

我 - 就是这样!

您可以看到生成的中心线向上移动了一点点.原因是我在Mathematica中叠加了不同类型的图像......我放弃了试图说服程序做我想要的:)

一些镜头

当我进行测试时,我收集了一些图像.它们可能是世界上最不起眼的东西,但是我的隧道-101误入歧途.

无论如何,他们在这里.请记住,我向上移动了几个像素...

HTH!

.

更新

万一你可以访问Mathematica 8(我今天得到它),有一个新功能Thinning.只是看看: