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

Remark 5.3. In shrinking and thinning algorithms, only deletable voxels are
permitted to be deleted to preserve the topology of an input image. In a
shrinking algorithm all deletable voxels are deleted as was explained in Sec-
tion 5.3. In a thinning algorithm only parts of deletable voxels are really
deleted because additional requirements stated in Section 5.4.2 have to be
satisfied.

In order that the results of thinning are located at the center of an input
figure, thinning algorithms shave deletable voxels by one layer from a border
of a figure. This shaving must be executed at an equal rate in an upside border,
downside border, left and right side border, and back and front side border,
respectively. Intuitively, such shaving of all deletable voxels on the surface of
afigure ( one-layer thinning ) is repeated around the number of times equal
to half of the figure width. One main cycle is executed usually after being
divided into six times of the partial thinning ( subcycle ) as follows, in order to
keep a thinned result near the center of an original figure.
For example, all upside border voxels are tested for deletability first and
replaced by a 0-voxel if deletable. Second, downside border voxels are tested
and deleted if deletable. The same procedure is applied to left border voxels,
right border voxels, front border voxels, and back border voxels in this order.
Thus, one main cycle consists of six subcycles of shaving. Each subcycle
scans the whole of an input image one time and tests deletability of border
voxels. The total number of subcycles is the number of times of iteration of
an algorithm and is the most important factor to determine the computation
time of the algorithm. Some of algorithms employ 12 subcycles and some
others avoid subcycles by using larger neighborhoods and different types of
the deletability test [Saito96, Saito01, Palagyi99, Ragnemalm90].

5.4.4 Examples of surface/axis thinning algorithms (sequential
type)

Let us show an example of a surface-thinning algorithm basing upon the
principle described above.

Algorithm 5.3 (Surface thinning).

F { f ijk }

Input: = input binary image.

f ijk =densityvalueofavoxel( i, j, k )whichtakes 0 or 1 .Asetof1-voxels
is considered to be a figure.
m = type of the connectivity ( m = 6 , 18 , 18 , 26 ).
Output:

=

= result of surface thinning is stored when the algorithm
finishes. Physically the same array as the one storing an input image is
assigned.
Conditions for a finally preserved voxel ( FPV ): A border voxel ( i, j, k )satis-
fying at least one of the following C 1and C 2 is called FPV and is never
deleted in the subsequent procedure.

F = { f ijk }