3
$\begingroup$

Skeletonization (or the medial-axis transform) is the process of finding the "middle" axis of a region (expressed as a mask). It is performed by the SkeletonTransform, which seems to work by thinning the mask until the "frontiers" meet, where they define the medial-axis.

There is another method, based on growing circles, which is my concern.

Consider this mask of a horse head:

enter image description here

Suppose you start with the small red circle that is bi-tangent to the boundary of the mask (i.e., touches the mask boundary in at least two points, as shown below).

enter image description here

This alternate method incrementally increases the radius of the circle and automatically adjusts the position of a new center so as to retain this bi-tangency condition.

The example image above is a hack... a kludge... based on selecting some candidate circle centers and increasing the radius until two (or more) points touch the boundary of the mask.

I would like to perform this process properly and algorithmically.

My general approach was to take the current largest circle, increment its radius by a small amount (e.g., by 1 pixel), then search for the circle center that is nearest the center of the current largest that retains bi-tangency. I think there are clever region-based primitives in Mathematica that could make efficient code, but alas I simply am not familiar enough with region-based computations. Moreover, functions such as RegionMemberQ don't directly correspond to bi-tangency.

Ultimately, I'd like to color the circles and associated line linking centers, as kludged above.


@bills' suggestion about RidgeFilter (new to me) really helped!

enter image description here

I just need to fine tune thresholds and such.

$\endgroup$
5
  • $\begingroup$ Look at DistanceTransform... the examples in the help file look a lot like skeletonization. You can also pick a desired distance function. $\endgroup$ – bill s Dec 2 '20 at 21:28
  • $\begingroup$ @bills: Good idea. However, the DistanceTransform finds the distance to one boundary of the mask. So I can choose any point within the mask and draw a circle that touches one point on the boundary. I'm not quite sure how to ensure the bi-tangency condition. And yes... DistanceFunction -> EuclideanDistance is essential in this application. Hmmm... maybe hillclimbing in the DistanceTransform image is the way to go. Let me try... $\endgroup$ – David G. Stork Dec 2 '20 at 21:37
  • $\begingroup$ I think that the peaks (or maybe ridges) of the distance transform surface would be places where you are equi-distant from two (or maybe more) points on the edge. $\endgroup$ – bill s Dec 2 '20 at 23:33
  • $\begingroup$ Yes... the ridges, of course. I've been working on an elegant way to hill climb along such ridges in the DistanceTransform image. (I would have thought there is some function that automatically gave the coordinates of a path that did gradient ascent, but it seems I must write it myself.) $\endgroup$ – David G. Stork Dec 2 '20 at 23:38
  • 1
    $\begingroup$ How about using RidgeFilter? The output of that should give you the centers of the circles, and the value at those points should give you the radii. $\endgroup$ – bill s Dec 2 '20 at 23:42
2
$\begingroup$

It may not give everything you are looking for, but:

img = Import["https://i.stack.imgur.com/zV7QC.png"];
RidgeFilter[DistanceTransform[img],0.5] // ImageAdjust

enter image description here

These are the ridges, which should be the centers of your circles. The radii would be the value of the Distance Transform image at these centers.

$\endgroup$
1
  • $\begingroup$ Thanks. I was just computing precisely this... and am now extracting the locations of "peaks of ridges," and will use the coordinates to read the circle radii. More soon (I hope). $\endgroup$ – David G. Stork Dec 2 '20 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.