algorithm - 找到隧道 'center line' ？

Question

我有一些由代表隧道的“折线”(每条线只是一个顶点列表)组成的 map 文件，我想尝试找到隧道“中心线”(粗略地显示为下面的红色)。



我过去使用 Delaunay triangulation 取得了一些成功。但我想避免使用这种方法，因为它(通常)不允许对我的 map 数据进行简单/频繁的修改。

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

Answer 1

一种适用于本地化数据更改的“算法”。

评论家的观点



The Good

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

The Bad

我用引号写了“算法”，只是因为我开发了它并且肯定不够强大以应对病理情况。如果您的图表有很多循环，您最终可能会出现一些幻线。稍后会详细介绍这一点和示例。

And The Ugly

丑陋的部分是你需要能够填充 map ，这并不总是可能的。几天前我发表了一条评论，询问您的图表是否可以被洪水填充，但没有收到答复。所以我还是决定发布它。

草图

这个想法是:

使用图像处理获得代表中心路径的细线像素

将图像分成与隧道最薄 channel 相称的块

在每个分区，表示包含像素的“质心”处的一个点

使用这些像素来表示图形的顶点

根据“近邻”策略将边添加到图中

去除诱导图中的虚假小循环

结束 - 剩余的边代表您想要的路径

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

剧情

我不会提供伪代码，因为困难的部分只是您的库未涵盖的部分。我将发布由连续步骤产生的图像，而不是伪代码。
我在 Mathematica 中编写了程序，如果对您有帮助，我可以发布它。

A- 从一个漂亮的充满洪水的隧道图像开始



B- 应用距离变换

Distance Transformation给出图像的距离变换，其中每个像素的值被替换为它到最近的背景像素的距离。
可以看到我们想要的路径是隧道内的Local Maxima



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

选择的内核是 Laplacian-of-Gaussian kernel像素半径为 2。它具有增强灰度边缘的神奇特性，如下所示。



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

为了获得中线的美景!



评论

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

电子图像分区

下面是算法的一些优点出现的时候:您可以开始使用并行处理或决定一次处理每个段。您还可以将结果段与之前的运行进行比较并重新使用之前的结果



F-质心检测

每个子图像中的所有白点仅被质心处的一个点替换
XCM = (Σ i∈Points Xi)/NumPoints


YCM = (Σ i∈Points Yi)/NumPoints

白色像素很难看到(参数“a”年龄渐近困难)，但它们确实存在。



来自顶点的 G- 图设置

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



H- 选择候选边

使用点之间的欧几里得距离，选择候选边。截止用于选择一组合适的边。这里我们使用 1.5 的子图像大小。

如您所见，生成的 Graph 有几个小循环，我们将在下一步中删除这些小循环。



H- 删除小循环

使用循环检测例程，我们可以删除特定长度的小循环。截止长度取决于几个参数，您应该根据经验为您的图形系列计算它



我——就是这样!

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



几个镜头

在进行测试时，我收集了一些图像。它们可能是世界上最没有隧道的东西，但我的 Tunnels-101 误入歧途。

不管怎样，他们来了。请记住，我向上移动了几个像素......



哈!

.

更新

以防万一您可以访问 Mathematica 8 (今天收到了)有一个新功能 细化 .只是看看: