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

algorithm is simple and clear. However, since conventional computers with
single processors can manipulate one voxel at one time, this algorithm had to
scan the whole of an input image as many times as the maximum distance
value in an input DT image. Concerning the memory requirement, two 3D
arrays are needed for storing an input image and an output image, separately.
When the algorithm is terminated, the result of the DT is restored exactly
in an output image . An original binary image is obtained at once by replac-

ing all positive values in

G

G by 1 . These are the same as in Algorithm 5.10.

Remark 5.15. This idea is applicable to the variable neighborhood RDT,
except that the neighborhood varies in every iteration and that the propaga-
tion is performed only inside that neighborhood. The neighborhoods in the
given neighborhood sequence is used in the reverse order. The starting neigh-
borhood of the neighborhood sequence is determined by the distance value. If
the distance value on a skeleton voxel is k , for example, the entry of a given
neighborhood sequence employed in the k -times of iteration is employed first.
Details of the concrete algorithm are neglected here (an algorithm for a 2D
image was given in [Toriwaki81, Yokoi81]). The same form of an algorithm
will be possible for a 3D image. This way of analysis cannot be applied to
the Euclidean DT, because the distance to an adjacent voxel is not always a
unit. In other words, the length of a path defined by a sequence of voxels does
not always correspond to the distance. By devising a neighborhood sequence
in the variable neighborhood DT such as , values of the DT will

become closer to the Euclidean distance than those of the fixed neighborhood
DT.

{ 6 , 18 , 26 }

Remark 5.16. Algorithms of the fixed neighborhood DT using the 6-, 18-,
and 26-neighborhood distances are obtained immediately from those of the
2D DT. Algorithms of the RDT were given here because they are useful for
understanding restoration from a skeleton. The 26- and the 6-neighborhood
DT (fixed neighborhood DT) are not so significant as the (squared) Euclidean
DT in problems relating directly to the distance metric such as invariability
to the rotation, utilization in thinning, and evaluation of the distance from a
figure, because in such applications the squared Euclidean DT is much more
advantageous. On the other hand, in the compression and deformation of a
figure, the fixed neighborhood DT becomesmoreusefulduetoitsmerits,as
follows:
(1) Both the DT and the RDT can be performed easily by simple algorithms.
(2) Relation between the DT and the RDT is very clear.

Remark 5.17. Image operator expressions similar to those presented in Re-
mark 5.12 are derived as follows, corresponding to parallel algorithms of the
fixed neighborhood DT. They are the same as those in a 2D image.

N ( k ) ] maximum fil- Definition 5.7. We call the following image operator M [

N ( k ) . ter with the neighborhood