# Circle-based skeletonization demonstration

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:

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

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!

I just need to fine tune thresholds and such.

• Look at DistanceTransform... the examples in the help file look a lot like skeletonization. You can also pick a desired distance function. Commented Dec 2, 2020 at 21:28
• @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... Commented Dec 2, 2020 at 21:37
• 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. Commented Dec 2, 2020 at 23:33
• 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.) Commented Dec 2, 2020 at 23:38
• 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. Commented Dec 2, 2020 at 23:42

## 1 Answer

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

img = Import["https://i.sstatic.net/zV7QC.png"];
RidgeFilter[DistanceTransform[img],0.5] // ImageAdjust


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.

• 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). Commented Dec 2, 2020 at 23:55