我有一些由代表隧道的“折线”（每条线只是顶点列表）组成的地图文件，我想尝试找到隧道“中心线”（粗略地在下面以红色显示）。
我过去使用过一些成功的方法德劳内三角剖分但我想避免使用这种方法，因为它（通常）不允许轻松/频繁地修改我的地图数据。
关于我如何能够做到这一点有什么想法吗？
The Good
好的部分是它使用大多数库中可用的图像处理和图形操作的混合，可以轻松并行化，速度相当快，可以调整为使用相对较小的内存占用，并且不必在修改后的外部重新计算区域（如果您存储中间结果）。
The Bad
我在引号中写了“算法”，只是因为我开发了它，并且肯定不足以应对病理情况。如果你的图表有很多循环，你可能会得到一些虚线。稍后将详细介绍这一点和示例。
和丑陋者
丑陋的部分是你需要能够淹没地图，但这并不总是可能的。几天前我发表了一条评论，询问您的图表是否可以洪水填充，但没有收到答案。所以我决定无论如何都要发布它。
这个想法是：
并行化机会源于以下事实：分区可以在独立进程中计算，并且可以对结果图进行分区以找到需要删除的小循环。这些因素还可以减少序列化而不是并行计算所需的内存，但我没有这样做。
我不会提供伪代码，因为困难的部分只是您的库未涵盖的部分。我将发布连续步骤产生的图像，而不是伪代码。 我把程序写在数学，如果对您有帮助，我可以发布它。
A- 从一张漂亮的充满洪水的隧道图像开始
B- 应用距离变换
The 距离变换给出图像的距离变换，其中每个像素的值被其到最近背景像素的距离替换.
您可以看到我们想要的路径是隧道内的局部最大值
C- 使用适当的内核对图像进行卷积
所选内核是高斯拉普拉斯核像素半径为2。它具有增强灰度边缘的神奇属性，如下所示。
D- 截止灰度级并对图像进行二值化
以获得中心线的美景！
评论
也许这对您来说就足够了，因为您知道如何将细线转换为近似的分段线段序列。由于我的情况并非如此，因此我继续这条道路以获得所需的细分。
电子图像分区
这时该算法的一些优点就显现出来了：您可以开始使用并行处理或决定一次处理每个段。您还可以将结果片段与之前的运行进行比较并重新使用之前的结果
F-质心检测
All the white points in each sub-image are replaced by only one point at the center of mass
XCM = (Σ i∈Points Xi)/NumPoints
YCM = (Σ i∈Points Yi)/NumPoints
白色像素很难看到（参数“a”age 渐近困难），但它们就在那里。
从顶点设置 G-图
使用选定的点作为顶点形成图形。仍然没有边缘。
H-选择候选边
使用点之间的欧几里得距离，选择候选边。截止用于选择一组适当的边。这里我们使用 1.5 的子图像大小。
正如您所看到的，生成的图表有一些小循环，我们将在下一步中将其删除。
H- 去除小循环
使用循环检测例程，我们删除达到一定长度的小循环。截止长度取决于几个参数，您应该根据图表系列的经验来计算它
我-就是这样！
您可以看到生成的中心线稍微向上移动。原因是我在 Mathematica 中叠加了不同类型的图像......并且我放弃了试图说服程序做我想做的事情:)
当我进行测试时，我收集了一些图像。它们可能是世界上最不隧道的东西，但我的 Tunnels-101 误入了歧途。
不管怎样，他们来了。请记住，我向上移动了几个像素......
.
以防万一您可以访问数学8（今天收到了）有一个新功能Thinning。只是看看：
