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

(6) Theoretical analysis of algorithms : DT of both a continuous image and a
digitized image have interesting properties concerning shape feature anal-
ysis and formal description of algorithms. For example, parallel algorithms
of DT are systematized in a beautiful form using image operations. Both
a sequential type and a parallel type algorithm are most clearly corre-
spondent with each other. The DT corresponds also to the morphology
operation [Toriwaki81, Yokoi81, Serra82].

5.5.3 Classification of algorithms

Before proceeding to the introduction of concrete algorithms, let us summarize
their basic principles.
The DT is a process that gives each 1 -voxel or a figure the distance to
the nearest background voxel ( 0-voxel ). Three ideas have been developed to
perform this.
(i) Calculate directly at each 1-voxel the distance to the nearest 0-voxel (direct
calculation method).
(ii) Propagate distance values to adjacent 1-voxels sequentially.
(iii) Shave a figure iteratively by one layer in one time of iteration from the
outside. A voxel shaved in the k times of iteration is regarded as being at
the distance k from the background.
(iv) Extend a path into the inside of a figure. The distance value at each voxel
that the path passes through is found by calculating the path length when
extended (path extension method).
The third and fourth methods cannot be used in the Euclidean DT. A
voxel of the distance 1 , for example, is not always m -adjacent to a voxel of
the distance 2 ( m = 6 , 18 , 26 ). Thus the Euclidean DT is calculated via the
first method or by the second method with a specific device. Other kinds of
DT with the variable neighborhood or the fixed neighborhood are calculated
mostly using the third and forth method due to ease of programming and
computation.

5.5.4 Example of an algorithm - (1) squared Euclidean DT

First, we will show a basic concept [Saito92, Saito93, Saito94a].
Given an input image F = { f ijk } ( L × M × N ), consider the following

sequence of transformations.
F = { f ijk }→ (transformation I) → G = { g ijk }→ (transformation II)

→ H s ijk }

(Transformation I) Apply the following transformation to an image

= { h ijk }→ (transformation III) → S = {

F while

referring to only in the i -direction (1D weighted minimum filter). De-

note an output image by

F

G = { g ijk } (Fig. 5.12 (a)).

x ) 2 ; f xjk = 0 , 1 g ijk =min

x {

( i − ≤ x ≤ L } . (5.2)