Skeletonizing Digital Images with Cellular Automata - Cellular Automata in Image Processing and Geometry - page 45

Chapter 3
Skeletonizing Digital Images with Cellular
Automata

Daniel Díaz-Pernil, Francisco Peña-Cantillana, and Miguel A. Gutiérrez-Naranjo

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 me-
dial 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 chap-
ter, 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.

3.1 Introduction

Skeletonization is one of the approaches for representing a shape with a small
amount of information by converting an image into a more compact representa-
tion and keeping the meaningful features. The conversion should remove redundant

Daniel Díaz-Pernil
Research Group on Computational Topology and Applied Mathematics,
Department of Applied Mathematics, University of Seville, Spain
e-mail: [e-mail]
Francisco Peña-Cantillana · Miguel A. Gutiérrez-Naranjo
Research Group on Natural Computing,
Department of Computer Science and Artificial Intelligence, University of Seville, Spain
e-mail: [e-mail], [e-mail]