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

enddo

[STEP 6] (Postprocessing)
for all ( i, j, k )'s do
if f ijk = 0

then f ijk ←

1

endif
enddo

Explanation of Algorithm 5.4. In this algorithm, we first apply the squared
Euclidean distance transformation [Saito92, Saito93, Saito94a, Saito94b] to
the whole of an input image. As a result, all 1-voxels of an input image are
given the square of the shortest distance to the background. We now calculate
the square of the distance instead of the exact distance value. Computation
load is greatly reduced by doing this because the algorithm is simplified by
avoiding the calculation of the square root and by using only the calculation
of integers throughout the procedure. We need only the order of the distance
value to the nearest 0-voxel, and need not use the absolute value of the dis-
tance.
Next we classify a voxel of the unit-squared distance into subgroups ac-
cording to the number of nonzero voxels in the 26-neighborhood represented
by m in the above description of the algorithm. For the sake of convenience,
grouping is performed at every three of the value of m . The deletability test
is applied to 1-voxels in the order of the value of m (a voxel of the smaller m
is tested earlier). A border voxel in Algorithm 5.3 corresponds to a voxel of
the unit (squared) distance value here. The deletability test and the relating
procedure here are applied to the set of 1-voxels remaining at that point.
Classification of border voxels according to the locations of 0-voxels in
their neighborhood is replaced here by the classification of voxels of the unit
distance according to the number of nonzero voxels in the 26-neighborhood.
The idea is basically the same in both algorithms. It is common to both
algorithms that a deletable voxel is replaced by a 0-voxel when it is detected
(sequential type of algorithm).
This algorithm proceeds to the processing of voxels with the (squared)
distance value 2 , after all deletable voxels with the unit distance have been
processed. The same procedure is repeated again to 1-voxels of the (squared)
distance 2 . Thus, at the point that the processing of voxels of the (squared)
distance d begins, all deletable voxels of the (squared) distance less than d
have been deleted. Therefore, voxels of the (squared) distance d have become
border voxels. Keeping a resultant figure at the center or in the vicinity and
reducing the effect of the rotation of an input figure are both realized by
executing procedures according to increasing order of the (squared) distance
values.
The above procedure is performed repeatedly for voxels of all (squared)
distance values.