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

of the 26-neighborhood DT at the voxel P. On the other hand, this idea can-
not be applied to the Euclidean DT. Thus a DT algorithm is classified into
two groups: the Euclidean DT and the variable (or fixed) neighborhood DT.
The latter group is classified further into an ordinary type and apathexten-
sion type . From the viewpoint of execution, they include the sequential type
and the parallel type. Examples of algorithms in each class will be presented
subsequently. Basic parts of algorithms of DT do not depend on the dimen-
sionality (dimensionality-independent), and can be immediately extended to
an n -dimensional DT.

5.5.2 Significance of DT and skeleton

Significance of the DT and the skeleton in image processing is summarized
in (1) (4) below [Toriwaki81]. (The skeleton will be explained later in

Section 5.5.3. Although many reports referred to in this section treat 2D
image processing, almost all of the contents presented there are immediately
extendable to a 3D image.)

∼

(1) Distance value : Values of the DT are used to discover the distance between
two voxels, the distance from a voxel to a figure, and the distance between
two figures. The Euclidean DT is the best for this.
(2) Concentration of information : Information that is stored, being scattered
over subarea in the 3D space, is put together onto the lower dimensional
subspace. For example, information distributed over a spherical region
is collected on the center, which is extracted as a skeleton. Information
distributed along a line figure is put together in specific points by the DT
on a line pattern [Toriwaki82a]. This property of information propagation
is made use of by applying the DT based upon the shortest path and the
DT of a line pattern.
(3) Shape feature : Values of the DT and their distribution on a figure, the
shape of equidistance surfaces, and skeletons are useful as shape features
themselves and as tools of feature extraction. The DT is particularly effec-
tive in finding the distance from an arbitrary point to some 3D volumetric
object. The DT is also effectively used in an ordinary image processing
procedure as a tool of segmentation and as a similarity measure between
3D figures [Kitasaka02a, Kitasaka02b, Mori94a]. Detection of a narrow
part in a figure is a good example and was applied to detecte a polyp in
virtual colonoscopy.
(4) Preprocessing : DT is used as a preprocessing of other image process-
ing such as in surface/axis thinning and calculation of Voronoi division
[Saito92]. The Euclidean DT is best here, too.
(5) Control information : The process of performing the DT based upon the
path length is available for controlling other kinds of processing and in-
formation propagation [Toriwaki79, Toriwaki81].