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

Fig. 3.1 Hand-written words and their skeletonization. This skeletonization has been per-
formed with the parallel implementation on GPU of the cellular automata adaptation of the
Guo and Hall algorithm presented in [35].

using a device architecture called Compute Unified Device Architecture (CUDA TM )
has been presented [35]. CUDA TM is a general purpose parallel computing architec-
ture that allows the parallel NVIDIA 2 Graphics Processors Units (GPUs) to solve
many complex computational problems in a more efficient way than on a Central
Processing Unit (CPU). In Section 3.5, we explore how this new computer architec-
ture can be used in order to improve the efficiency of the algorithms from a practical
point of view.
Skeletonization has been found useful for data compression and pattern recogni-
tion in a wide range of applications in the industrial and scientific fields. It is usually
considered as a pre-processing step in pattern recognition algorithms, but its study is
also interesting by itself for the analysis of line-based images such as coronary arter-
ies [17], human fingerprints classification [27], cartography [29], data compression
and data storage [20], automated inspection of printed circuit boards [44] or optical
character recognition (OCR) [42] among others.
The chapter is organized as follows: Firstly, a brief overview on different skele-
tonizing algorithms is presented (Section 3.2). In Section 3.3, as an example, the
Guo and Hall skeletonizing algorithm is studied in detail. Next, some hints on a
general skeletonizing algorithm on cellular automata are shown (Section 3.4) and,
as a case study, the Guo and Hall algorithm is adapted to cellular automata. In Sec-
tion 3.5, some hints for a parallel implementation in CUDA are presented. Finally,
some examples and some conclusions are provided.

3.2 Skeletonizing Algorithms

The first definition of the skeleton of a region was provided by Blum as the medial
axis transformation (MAT) [10, 11]. According to the original definition, in order
to find the MAT region with border B from a region R , the closest neighbor in B

2 http://www.nvidia.com