Finding midlines of polygons using Voronoi diagram

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!

Answer 1

Both of these problems are 'features' of medial axis, Voronoi approach.

Point on medial axis has property that it is equally distant from two or more boundaries. That is due medial axis points are Voronoi points, or dually Delaunay triangulation centers. Which means that there is a circle with that center, whole inside the boundary, passing through three boundary points. At least that would be a case when boundary discretization goes into infinity. Since boundary doesn't have infinite number of points this approach is an approximation with problems you observed.

1) Medial axis of circle arc is a point. That result is good. If shape ends with quite clean arc than medial axis 'stops' on point that is medial axis of arc part. That can be seen in comparison of different method on Skeletonize page.

2) Medial axis of two lines passes through angle bisector. That means if there are more 'corners' on the boundary, there will be more axis 'fingers' going into these corners. Like medial axis of square is of X shape. If you are using WormAnalysis approach (you referred to), than only longest path on axis is extracted. Which is good for worms, but not in general case. In general case it would be better to clean axis by removing parts that cover small part of boundary. Like in your first image of topic 2) there is an axis part going up. That is part is medial axis for small corner on boundary top left. Left of that corner on the boundary is part that is an arc which has small medial axis. Because of taking longest path, that long 'finger' is taken which covers small part of the boundary, but smaller part of medial axis which covers larger part of the boundary is omitted.