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

clidean distance is rather large in the 26-neighborhood and the 6-neighborhood
distance and also that the directional inhomogeneity is more remarkable in
3D space than in 2D space.
Remark 5.8. For surface/axis thinning presented here the words skeletoniza-
tion and medial surface/axis thinning ( extraction ) are also used, but an exact
distinction among them has not been shown clearly. Skeleton extraction based
upon the distance transformation stated in the following section is quite differ-
ent from any others [Borgefors99]. Many papers concerning 3D thinning have
seen published since around 2000. Examples are shown in Supplementary list
in the reference list.
Remark 5.9. The surface/axis thinning stated here imposes the general and
theoretically very strict requirement of preserving the topology of an input
figure for an arbitrary binary image. In many practical applications, however,
an input image or a resulting image may be restricted a little more. A thinning
algorithm will be useful, even if it does not satisfy such a condition strictly.
Many other algorithms have been developed for a wide range of practical
problems. Following are examples of more moderate requirements and easier
situations concerning thinning.
(a) Input figures are slender tubular figures extending in almost the same
direction. The axis thinning will be achieved by connecting center points
of their cross sections which are almost 2D circular figures.
(b) To connect center points of balls, inscribing an input 3D figure might
give acceptable results. This is nearly equivalent to using skeleton vox-
els determined by the distance transformation presented in the following
section.
(c) To extract a sequence of points (voxels) inside an input figure, which are as
distant from a border of a figure as possible, and connect one and the other
end of an input figure is discussed in [Bitter01]. A tree search algorithm
and the minimization of weights of a tree are available for obtaining such
a sequence of voxels.
(d) An input figure has no holes and cavities or they may be neglected even if
they exist. One example of such cases is automated generation of paths for
flying through colon and bronchus branches in virtual endoscopy [Saito00,
Hayashi00, Hayashi03].
5.5 Distance transformation and skeleton
5.5.1 Definition
The distance transformation (DT) of a 3D figure is defined as follows.