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

(v) Necessity of distance values : Distance values themselves are not always
required in some applications. If we want to know the distance value that
maximizes or minimizes a given object function, then other functions in-
creasing (or decreasing) with the distance value will be enough. For ex-
ample, if we want to find the closest point to a given point, the square
distance will be useful instead of the distance value itself.
(iv) Path and constraint : The minimal path or voxels (points) to be consid-
ered may exist only in the limited area of the space. For instance, it may
be needed to detect the closest point from a given point, or to find the
shortest path between two given points both on a specific curved surface.
In such cases, direct calculation of the distance is dicult. Such a proce-
dure is useful in execution of path generation and calculation of the path
length simultaneously. Concrete examples are derivation of the shortest
path along the surface of a 3D object and detection of the shortest route
to reach a goal avoiding obstacles.
4.9.4 Improvement in distance metric
Various research has been reported concerning the improvement of distance
functions. We will summarize some of them below.
(1) Extension of the neighborhood : Use of a neighborhood larger than the 26-
neighborhood was tried in several applications. This means that we can
move to further voxels in one step when proceeding along a path. In
other words, a direct path to a current voxel P from outside of the 26-
neighborhood of P is acceptable. In this case, real distance values from P
to voxels adjacent to P may differ among all adjacent voxels. Therefore,
adjustment of distance values to adjacent voxels may become necessary.
This point will be referred to in the next subsection.
(2) Diversifying distance values : We assume implicitly that the distance to
adjacent voxels is a unit. This simplifies some algorithms in calculat-
ing distance values. A typical example is the distance transformation
presented in the next chapter. However, in some of distance measures
this simplification causes severe bias from the Euclidean distance met-
ric. To overcome this defect, weights are multiplied to parts of distance
values to adjacent voxels in the calculation of path lengths. Several ex-
amples are shown in Fig. 4.16. If we employ weight values that are equal
to exact Euclidean distance, the computation load heavily increases be-
cause calculation of square roots of integers is required. Therefore, inte-
ger weights were developed so that ratios among them are kept closer to
those of Euclidean distance values. This type of metric was called cham-
fer distance in various literatures regarding 2D and 3D image processing
[Verwer91, Borgefors84, Borgefors86a, Borgefors86b].
(3) Distance transformation : Distance transformation gives all 1-voxels in an
input image the distance to the nearest 0-voxel. The 0-voxels of an input