一种能很好地处理局部数据变化的“算法”。

The Good

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

The Bad

我引用了“算法”一词,仅仅是因为我开发了它,而且肯定不足以应付病理病例。如果你的图形有很多循环,你可能会得到一些虚线。更多关于这个和后面的例子。

And The Ugly

最难看的是,你需要能够淹没地图,这并不总是可能的。几天前,我发表了一条评论,问你的图表是否能被洪水淹没,但没有得到答复。所以我决定把它贴出来。

素描

想法是:

1. 使用图像处理获得表示中心路径的像素细线
2. 将图像分割成小块,并与隧道最薄的通道相连
4. 使用这些像素来表示图的顶点
5. 基于“近邻”策略向图中添加边
7. 结束-剩余的边表示所需的路径

并行化的机会来自于这样一个事实:分区可以在独立的进程中计算,结果图可以被分区以找到需要删除的小循环。这些因素还允许通过串行化而不是并行执行calcs来减少所需的内存,但我没有经历这些。

情节

我不提供伪代码,因为困难的部分只是你的库没有涵盖。我将发布连续步骤产生的图像,而不是伪代码。 Mathematica 如果对你有帮助的话,我可以寄出去。

从一幅充满洪水的隧道图片开始

这个 Distance Transformation 给出图像的距离变换,其中每个像素的值被其到最近背景像素的距离替换。

用适当的核卷积图像

Laplacian-of-Gaussian kernel 像素半径2。它具有增强灰度边缘的神奇特性,如下所示。

D-截断灰度并对图像进行二值化

看一眼中心线的美景!

评论

也许这对您来说已经足够了,因为您可能知道如何将细线转换为近似的分段序列。因为对我来说不是这样的,所以我继续这条路以获得所需的片段。

E-图像分割

下面是该算法的一些优点:您可以开始使用并行处理,也可以决定一次处理每个段。您还可以将结果段与上一次运行进行比较,并重新使用上一次运行的结果

F-质心检测

每个子图像中的所有白点都只替换为质心处的一个点
X CM = (Σ i∈ Points X i )/NumPoints

Y CM = (Σ i∈ Points Y i )/NumPoints

白色像素很难看到(参数“a”的渐近困难 年龄

从顶点建立G-图

H-选择候选边

正如您所看到的,结果图有几个小循环,我们将在下一步中删除。

H-去除小循环

我-就是这样!

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

几枪

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

啊!

.

更新

以防万一 Mathematica 8 变薄 . 你看:

这是一个非常经典的骨架化问题;有很多算法可用。一些算法原则上适用于轮廓线,但由于几乎每个人都在图像上使用它们,我不确定这些东西将如何可用。不管怎样,如果你可以绘制并填充下水道轮廓,然后使用骨架化算法,你可以得到一些接近中线的东西(像素分辨率内)。

然后你可以沿着这些线走,用圆圈做一个二元搜索,直到你碰到至少两个独立的线段(如果你在一个分支点上,则为三个)。你第一次击中的两个点的中点,或者一个圆的中心与你第一次击中的三个点接触,是对中心的一个很好的估计。

很好地 Python 使用包 skimage 这是一个简单的任务如下。

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()