ALGORITHM OF BINARY IMAGE PROCESSING - Fundamentals of Three-Dimensional Digital Image Processing - page 113

thinning, border surface following, and distance transformation are explained
as examples of algorithms realizing such information concentration.
Algorithms used to execute those processes are also given. Through the ex-
planation of algorithms, we intend to provide algorithms that can be used for
practical applications, and at the same time we expect readers to understand
various characteristics of algorithms and methods to design algorithms by
themselves. As examples, detailed sequential and parallel algorithms, concen-
tration and restoration of figures, serial composition, and 1D decomposition
are presented.
Although most algorithms in this chapter are described by program-like
expressions, they are neither programs themselves nor definitions of algorithms
in their strict meanings. Our aim is to give readers the most essential parts of
algorithms while avoiding ambiguity. We omit some parts of procedures that
might be necessary for correct behavior of a program, but are less important
in the definition of such algorithms as detection of the overflow in numerical
calculation and exceptional processing for the frame of an input image. The
descriptions of some algorithms may vary. This is to avoid errors in rewriting
descriptions from original papers.
All algorithms presented in this chapter have been coded and executed at
least once in the authors' laboratory and their expected performance has been
confirmed.

5.2 Labeling of a connected component

A connected component was defined already in Def. 4.3. Roughly speaking,
each connected component corresponds to an individual 3D figure. Hence ex-
traction of a connected component is useful as a tool to find the topological
properties of a figure, such as the Euler number. Connected component ex-
traction is very useful also for practical applications of image processing.
Procedures to extract a connected component (= labeling) are basically
the same as those of a 2D image [Rosenfeld82, Watt98]. Here we will present
concrete algorithms for all of four types of connectivity [Yonekura82a]. The
18 -connectivity case is neglected because it is the same as the 6-connectivity
case. We will use positive integers as labels as was stated in Section 4.2.

Algorithm 5.1 (Labeling of connected components).
F = { f ijk } : input image (binary image).

: label image: l ijk is a positive integer representing a label of each
connected component, (The value 0 is reserved for the background and
so the value of a 0-voxel is not changed.)
λ : variable representing the number of a connected component.
T ( i ): label table (1D array).
(1) Initialization: λ

L = { l ijk }

← 0 . Start the raster scan from a voxel ( 2 , 2 , 2 ).