当前位置： 文江博客话题详情

找到隧道“中心线”？

发布于 2024-09-28 02:06:00 字数 328 浏览 2 评论 0原文

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

alt text

我过去使用 Delaunay triangulation 但我想避免使用该方法，因为它（通常）不允许轻松/频繁地修改我的地图数据。

关于我如何能够做到这一点有什么想法吗？

原文

I have some map files consisting of 'polylines' (each line is just a list of vertices) representing tunnels, and I want to try and find the tunnel 'center line' (shown, roughly, in red below).

alt text

I've had some success in the past using Delaunay triangulation but I'd like to avoid that method as it does not (in general) allow for easy/frequent modification of my map data.

Any ideas on how I might be able to do this?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（3）

猫七 2024-10-05 02:06:03

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

批评者的观点

The Good

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

坏处

我写了“算法”，用引号引起来，只是因为我开发了它，但肯定不够强大，无法应对病理情况。如果你的图表有很多循环，你可能会得到一些虚线。稍后将详细介绍这一点和示例。

和丑陋

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

草图

想法是：

  1. 使用图像处理来获取表示中心路径的细像素线
  2. 将图像划分为与隧道最薄通道相称的块
  3. 在每个分区处，表示所包含像素的“质心”处的一个点
  4. 使用这些像素代表图的顶点
  5. 基于“近邻”策略向图添加边
  6. 删除诱导图中的虚假小循环
  7. 结束 - 剩余的边代表您想要的路径

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

我不会提供伪代码

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

A- 从漂亮的洪水填充隧道图像开始

alt text

B- 应用距离变换

距离变换给出图像的距离变换，其中每个像素的值被其到最近背景像素的距离替换。
您可以看到我们所需的路径是隧道内的局部最大值

alt text

C- 将图像与适当的内核

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

alt text

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

以获得中心的良好视图线！

alt text

评论

也许这对你来说就足够了，因为你知道如何改变一个薄的线到近似分段段序列。由于我的情况并非如此，因此我继续这条道路以获得所需的细分。

E-图像分区

这时算法的一些优点就显现出来了：您可以开始使用并行处理或决定一次处理每个片段。您还可以将结果片段与之前的运行进行比较，并重新使用之前的结果

alt text

F- Center质量检测

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

<代码>
YCM = (Σ i∈点数 Yi)/NumPoints

白色像素很难看到（参数“a”age 渐近困难），但它们就在那里。

alt text

从顶点设置 G-图

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

alt text

H- 选择候选边

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

正如您所看到的，生成的图表有一些小循环，我们将在下一步中将其删除。

alt text

H- 删除小循环

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

alt text

I- 那是它！

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

alt text

一些镜头

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

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

alt text

HTH ！

。

更新

万一您可以访问 Mathematica 8（我今天得到了），有一个新功能细化。看看：

alt text

An "algorithm" that works well with localized data changes.

The critic's view

The Good

The nice part is that it uses a mixture of image processing and graph operations available in most libraries, may be parallelized easily, is reasonable fast, may be tuned to use a relatively small memory footprint and doesn't have to be recalculated outside the modified area if you store the intermediate results.

The Bad

I wrote "algorithm", in quotes, just because I developed it and surely is not robust enough to cope with pathological cases. If your graph has a lot of cycles you may end up with some phantom lines. More on this and examples later.

And The Ugly

The ugly part is that you need to be able to flood fill the map, which is not always possible. I posted a comment a few days ago asking if your graphs can be flood filled, but didn't receive an answer. So I decided to post it anyway.

The Sketch

The idea is:

  1. Use image processing to get a fine line of pixels representing the center path
  2. Partition the image in chunks commensurated to the tunnel thinnest passages
  3. At each partition, represent a point at the "center of mass" of the contained pixels
  4. Use those pixels to represent the Vertices of a Graph
  5. Add Edges to the Graph based on a "near neighbour" policy
  6. Remove spurious small cycles in the induced Graph
  7. End- The remaining Edges represent your desired path

The parallelization opportunity arises from the fact that the partitions may be computed in standalone processes, and the resulting graph may be partitioned to find the small cycles that need to be removed. These factors also allow to reduce the memory needed by serializing instead of doing calcs in parallel, but I didn't go trough this.

The Plot

I'll no provide pseudocode, as the difficult part is just that not covered by your libraries. Instead of pseudocode I'll post the images resulting from the successive steps.
I wrote the program in Mathematica, and I can post it if is of some service to you.

A- Start with a nice flood filled tunnel image

alt text

B- Apply a Distance Transformation

The Distance Transformation gives the distance transform of image, where the value of each pixel is replaced by its distance to the nearest background pixel.
You can see that our desired path is the Local Maxima within the tunnel

alt text

C- Convolve the image with an appropriate kernel

The selected kernel is a Laplacian-of-Gaussian kernel of pixel radius 2. It has the magic property of enhancing the gray level edges, as you can see below.

alt text

D- Cutoff gray levels and Binarize the image

To get a nice view of the center line!

alt text

Comment

Perhaps that is enough for you, as you ay know how to transform a thin line to an approximate piecewise segments sequence. As that is not the case for me, I continued this path to get the desired segments.

E- Image Partition

Here is when some advantages of the algorithm show up: you may start using parallel processing or decide to process each segment at a time. You may also compare the resulting segments with the previous run and re-use the previous results

alt text

F- Center of Mass detection

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

The white pixels are difficult to see (asymptotically difficult with param "a" age), but there they are.

alt text

G- Graph setup from Vertices

Form a Graph using the selected points as Vertex. Still no Edges.

alt text

H- select Candidate Edges

Using the Euclidean Distance between points, select candidate edges. A cutoff is used to select an appropriate set of Edges. Here we are using 1.5 the subimagesize.

As you can see the resulting Graph have a few small cycles that we are going to remove in the next step.

alt text

H- Remove Small Cycles

Using a Cycle detection routine we remove the small cycles up to a certain length. The cutoff length depends on a few parms and you should figure it empirically for your graphs family

alt text

I- That's it!

You can see that the resulting center line is shifted a little bit upwards. The reason is that I'm superimposing images of different type in Mathematica ... and I gave up trying to convince the program to do what I want :)

alt text

A Few Shots

As I did the testing, I collected a few images. They are probably the most un-tunnelish things in the world, but my Tunnels-101 went astray.

Anyway, here they are. Remember that I have a displacement of a few pixels upwards ...

alt text

HTH !

.

Update

Just in case you have access to Mathematica 8 (I got it today) there is a new function Thinning. Just look:

alt text

回复 原文
寄与心 2024-10-05 02:06:03

这是一个非常经典的骨架化问题；有很多可用的算法。一些算法原则上适用于轮廓轮廓，但由于几乎每个人都在图像上使用它们，我不确定这些算法的可用性如何。无论如何，如果您可以绘制并填充下水道轮廓，然后使用骨架化算法，您可以获得接近中线的东西（在像素分辨率内）。

然后，您可以沿着这些线行走，并使用圆圈进行二分搜索，直到遇到至少两个单独的线段（如果位于分支点，则为三个）。您首先击中的两个点的中点，或者接触您首先击中的三个点的圆心，是对中心的良好估计。

This is a pretty classic skeletonization problem; there are lots of algorithms available. Some algorithms work in principle on outline contours, but since almost everyone uses them on images, I'm not sure how available such things will be. Anyway, if you can just plot and fill the sewer outlines and then use a skeletonization algorithm, you could get something close to the midline (within pixel resolution).

Then you could walk along those lines and do a binary search with circles until you hit at least two separate line segments (three if you're at a branch point). The midpoint of the two spots you first hit, or the center of a circle touching the three points you first hit, is a good estimate of the center.

回复 原文
生生漫 2024-10-05 02:06:03

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

在此处输入图像描述

Well in Python using package skimage it is an easy task as follows.

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

enter image description here

回复 原文
~没有更多了~

关于作者

儭儭莪哋寶赑

暂无简介

0 文章
0 评论
22 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

留蓝

文章 0 评论 0

18790681156

文章 0 评论 0

zach7772

文章 0 评论 0

Wini

文章 0 评论 0

ayeshaaroy

文章 0 评论 0

初雪

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文