python - Finding midlines of polygons using Voronoi diagrams

Question

I am using the Voronoi diagram-based approach outlined here to find midlines of binary masks of root images. I am using the Python code more or less exactly as described:

import skimage.morphology as morphology

WHITE = 255

image_bool = binary_mask == WHITE
d = morphology.disk(2)
img = morphology.binary_closing(image_bool, selem=d)
skeleton = morphology.medial_axis(img)

Then comes the graphing: I feed the skeletonized image into buildTree, as described in user Gabriel's iPython notebook: https://github.com/gabyx/WormAnalysis/blob/master/SkeletonTest/Skeletonize.ipynb

In general, this produces great results. However, the method occasionally fails in two distinct ways:

1) The graphs do not always extend the full length of the root:

2) The graphs sometimes connect "prematurely" to a point along the root contour that may appear to be the longest path, but clearly does not conform to what I would call the "midline". This happens for a diverse range of polygon shapes:

This final case is an artificial mask -- none of my actual roots have perfectly flat tips -- but I think it represents the problem quite well.

Does anyone with a more refined understanding of Voronoi diagrams have any tips for how to address either of these problems, while still retaining this general approach.

Thanks!

标签： pythonpolygoncomputational-geometrycurve-fittingvoronoi

Answer 1

这两个问题都是中轴的“特征”，Voronoi 方法。

中轴上的点具有与两个或多个边界等距的特性。这是由于中轴点是 Voronoi 点，或双重 Delaunay 三角测量中心。这意味着有一个以该中心为中心的圆，整个在边界内，通过三个边界点。至少当边界离散化进入无穷大时会出现这种情况。由于边界没有无限数量的点，这种方法是您观察到的问题的近似值。

1）圆弧的中轴是一个点。这个结果很好。如果形状以非常干净的弧线结束，则中间轴“停止”在弧形部分的中间轴点上。这可以从Skeletonize 页面上不同方法的比较中看出。

2）两条线的中轴通过角平分线。这意味着如果边界上有更多的“角”，就会有更多的轴“指”进入这些角。就像正方形的中轴是X形的。如果您使用 WormAnalysis 方法（您提到过），则仅提取轴上最长的路径。这对蠕虫有好处，但不是在一般情况下。在一般情况下，最好通过移除覆盖一小部分边界的部分来清洁轴。就像您在主题 2 的第一张图片中一样，有一个轴部分在上升。即部分是边界左上角小角的中轴。边界上那个角的左侧是具有小中轴的弧形部分。因为走最长的路，所以走的那个长“手指”覆盖了边界的一小部分，