Skeletonizing Digital Images with Cellular Automata

Abstract

The skeletonization of an image consists of converting the initial image into a more compact representation. In general, the skeleton preserves the basic struc-ture and, in some sense, keeps the meaning. The most important features concerning a shape are its topology (represented by connected components, holes, etc.) and its geometry (elongated parts, ramifications, etc.), thus they must be preserved. Skele-tonization is usually considered as a pre-processing step in pattern recognition algo-rithms, but its study is also interesting by itself for the analysis of line-based images such as texts, line drawings, human fingerprints classification or cartography. Since the introduction of the concept by Blum in 1962 under the name of medial axis transform, many algorithms have been published in this topic and there are many different approaches to the problem, among them the ones based on distance transform of the shape and skeleton pruning based on branch analysis. In this chapter, we focus on how the skeletonization of an image can be studied in the Cellular Automata framework and, as a case study, we consider in detail the Guo and Hall skeletonizing algorithm.