Looking for algorithm: skeleton generation for raster images

Question

I am doing some work (too complicated to explain), and one of the tasks I have is I need to convert raster image of a smoothed polygon into a skeleton. So I need to do something like this:

I have raster image (on the left), and I want to have a graph consisting of points and edges (on the right) that represents the image.

I've read about algorithms, especially a book by Steven Skiena, where he tells to use "Brush fire" algorithm, which he explains as "each cycle, go through every point that is on the edge, for edges that collide add a point to the skeleton and remove the remaining points, move on to next cycle until only skeleton is left" but all info I could find on this algorithm online is about some pathfinding algorithms for robots, I don't understand how to apply it here (basically how do I know "edges" if all I have is coordinates of filled/vacant pixels).

I've looked up CGAL library and it's skeleton demonstration, but it doesn't do well when polygon has many vertixes, so just converting each vertex on the border into a vertex of a polygon and then feeding it to the algorithm won't produce good results.

I expect this must be a common algorithm as the task seems to be quite basic, but I don't want to invent the wheel and I couldn't find anything on the topic (perhaps because I don't know the correct keywords)

Answer 1

The better term for your search is digital thinning, the digital version of the medial axis. For example, this paper cites 15 such algorithms:

"Note on fifteen 2D parallel thinning algorithms." M. Couprie (PDF download link)

Here is a little piece of Figure 16, showing the results of two such algorithms: