GEOMETRICAL PROPERTIES OF 3D DIGITIZED IMAGES - Fundamentals of Three-Dimensional Digital Image Processing - page 106

Remark 4.19. Distance measures on a digitized space have been studied in
many papers including [Borgefors84, Borgefors86a, Borgefors86b, Coquin95,
Klette98, Kuwabara82, Okabe83a, Okabe83b, Ragnemalm90, Saito94a, Tori-
waki01, Verwer91, Yamashita84, Yamashita86]. Furthermore, if a domain in
which a path exists is limited, the distance between two pixels and the distance
transformation from a subset of pixels should be significantly modified.

4.9.3 Distance function in applications

The distance function can be discussed from at least two different viewpoints.

(1) Digital space viewpoint : If we consider that a digitized image is defined
only by voxels (or sample points), then it is enough that the distance
between arbitrary two voxels is defined.
(2) Approximation viewpoint : We may consider that a digitized image is an
approximation of a continuous image. From this viewpoint, it is desirable
that a distance value on a digitized image is as close as possible to that
on a continuous image.

The relative weight of two viewpoints varies in different applications. Thus,
various research has been performed theoretically and experimentally. Exam-
ples of requirements in applications are as follows:

(i) Difference from the Euclidean metric : For the measurement of quantities
such as the distance, area, and volume, the distance function nearer to
the Euclidean distance is better (approximation view point).
(ii) Computation cost ( computational complexity ): An explicit form of expres-
sion for a distance value is more convenient than an algorithmic procedure
to calculate the distance between two points of given coordinates. For ex-
ample, the formula to calculate the Euclidean distance between two given
points is well known. Only an algorithm to find the minimum distance be-
tween two points is known for a variable neighbor distance on a digitized
image (Theorem 4.5).
(iii) Distance measure : Is a distance measure required in the strict sense? In
some applications the axiom of the distance metric is not always necessary.
(iv) Distance from a point set : To calculate the distance between a point and
a point set (= figure), the definition and the algorithm are needed. For
example, given a set of voxels

S and a voxel S ,

x 1

existing outside of

S and a voxel S )) may be given as the distance between a set x 1 ( d ( x 1 ,

S ) ∈ S } d ( x 1 , ≡ min { d ( x 1 , y ); y . (4.68)

In this case, the algorithm to calculate effectively the distance between
x

S is more important than a formula to obtain
the distance between two given voxels. See distance transformation in
Section 5.4 (digital space viewpoint).

and y for all y sin