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

weights [Borgefors84, Borgefors86a, Borgefors86b, Danielsson80]. The dis-
tance measure weighted by them is called chamfer distance [Montanari68].
See also Chapter 4 [Jones06].
(3) Enlargement of the neighborhood : Euclidean DT is obtained with very
high accuracy by employing an enlarged neighborhood except for small
numbers of specific voxels. This was shown for a 2D image in [Danielsson80,
Ragnemalm90]. By enlarging the neighborhood, the range of paths that
can be searched is also extended, and eventually a minimal will be de-
tected. This method may be extended to a 3D image, in principle. How-
ever, the number of paths to be searched increases rapidly according to
the extension of the neighborhood ( 5 5 , for example), and both

computation time and memory requirement also increase rapidly. In fact,
extension to a 3D image has not been reported.
(4) Propagation of coordinate values : See Remark 5.11.
(5) Other variations : Most variations of DT described in [Toriwaki81] will
be extended in a straightforward manner to a 3D image. They in-
clude the directional DT [Yokoi81], the DT of a line figure [Toriwaki79,
Toriwaki81, Toriwaki82a] and the max-type DT [Suzuki83]. The DT of
the background (exoskeleton) and an application to the Voronoi divi-
sion are also extended immediately to a 3D image at least in principle
[Preston79, Mase81, Saito92]. It should be noted, however, that shapes
of resulting line figures and surface figures will become complicated such
as with a skeleton (see the next section) and a Voronoi division surface
[Edelsbrunner94, Mase81, Toriwaki88, Yashima83].

× 5 ×

5.5.7 Skeleton

One of the most useful features of DT G derived from an image F is that char-

acteristic features of an image F are carried to a limited number of voxels, or

that characteristics of an image are condensed through the DT. Intuitively

the result of condensation is represented by a set of voxels called a skeleton .
A stricter definition of the skeleton is necessary for theoretical analysis of the
skeleton and for deriving an algorithm to extract the skeleton. We will give
here four types of definitions of the skeleton. They are each a little different
from each other, and each of them has its own significance.

F

Definition 5.5 (Skeleton). Let us represent an input image by F and its

DT by .

(1) A set of voxels is called a skeleton of an image

G

, if an input
image is restored exactly from coordinates of voxels of the skeleton and
values of DT on them.
(2) A set of all local maximum points (voxels) of the DT of

F or of a DT G

F is called a

skeleton of an image F or of a DT G .

(3) Given a binary figure , let us denote by φ a processing (image operation)

to delete a 1-voxel which is at the unit distance from the background and

F