我有一些由代表隧道的“折线”(每条线只是一个顶点列表)组成的 map 文件，我想尝试找到隧道“中心线”(粗略地显示为下面的红色)。
我过去使用 Delaunay triangulation 取得了一些成功。但我想避免使用这种方法，因为它(通常)不允许对我的 map 数据进行简单/频繁的修改。
关于我如何能够做到这一点的任何想法？
最佳答案
一种适用于本地化数据更改的“算法”。
评论家的观点
The Good
好的部分是它使用了大多数库中可用的图像处理和图形操作的混合，可以轻松并行化，速度合理，可以调整为使用相对较小的内存占用，并且不必在修改后重新计算如果您存储中间结果，则区域。
The Bad
我用引号写了“算法”，只是因为我开发了它并且肯定不够强大以应对病理情况。如果您的图表有很多循环，您最终可能会出现一些幻线。稍后会详细介绍这一点和示例。
And The Ugly
丑陋的部分是你需要能够填充 map ，这并不总是可能的。几天前我发表了一条评论，询问您的图表是否可以被洪水填充，但没有收到答复。所以我还是决定发布它。
草图
这个想法是:
并行化的机会来自于分区可以在独立进程中计算的事实，并且可以对结果图进行分区以找到需要移除的小循环。这些因素还允许通过序列化而不是并行进行计算来减少所需的内存，但我没有这样做。
剧情
我不会提供伪代码，因为困难的部分只是您的库未涵盖的部分。我将发布由连续步骤产生的图像，而不是伪代码。
我在 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 (今天收到了)有一个新功能细化 .只是看看:
关于algorithm - 找到隧道 'center line' ？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3983613/