Skeletonization

I was recently curious about how to find the endpoint of a line in an image.¹ I couldn’t quite think of a good way to do it. The methods I conjured seemed to be really fragile and kinda hacky. Graph-based algorithms seemed inefficient, and just didn’t feel right.

In my search for a better solution, I came across a Stack Overflow thread where someone mentioned a method for creating single-pixel-thick lines. I was intrigued, so I looked into it some more.

The process is called skeletonization. It’s a way of producing a “skeleton” of an image, where the “bones” are equidistant from its nearest boundaries. Wikipedia has a good example for a letter B:

It’s a simple process, really. First you take a binary image and use a “hit-and-miss” transform. This transform looks at each pixel and its neighborhood. If the neighborhood matches any of a set of patterns², you clear the center pixel. Otherwise the center pixel is left unchanged. You do this to every pixel for several defined patterns, then repeat the process until further iterations don’t produce any changes.

When you’re done, you’re left with a skeleton that retains the same connectivity as the original image, except every line is only a single pixel thick. As an added bonus, the patterns used in the hit-and-miss transform ensure that the lines don’t shorten in this process.

Finding the endpoint of such a single-pixel-thick line is easy to do. Simply look for pixels that have only one neighbor. If a pixel has two neighbors, you know it’s not an endpoint.

Fingerprint

I immediately thought that applying the algorithm to an image of a fingerprint would be a fun application of this technique. I grabbed the following image from Google because it is clean and neat:

With a few lines of Python code, I was able to produce the skeletons of the image and its inverted image:

Finding the endpoints was a cinch using a different hit-and-miss transform that only looks for pixels with one neighbor:

As you can see, it did a pretty good job of finding the endpoints of both the ridges and the valleys. There were a few hiccups, like those at the center of the whorl. There is a red dot indicating the end of a valley that shouldn’t be there, and there are two closely-spaced green dots at the top of the ridge above it.

I would imagine that this could provide a very useful input to fingerprint recognition algorithms, but I wasn’t able to find any information about whether this was used in the real world. If you happen to know anything about this, leave a comment or email me@bryanredd.com.

Stick Figure

Just for fun, I wanted to find the skeleton of a stick figure, so I took a picture of a simple stick figure that I drew.

Then I applied the same algorithm to find its skeleton:

It looks like bro has some scoliosis. That was too spooky for me, so I added some meat back onto his bones using a dilation technique:

Happy Halloween! 👻🎃