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

The deletability test was applied earlier to voxels having more 0-voxels
in the 26-neighborhood among voxels of the same distance values. Using this
order, an isolated narrow protrusion tends to be shaved earlier. This tendency
is desirable in that it prevents the generation of meaningless short branches
in a thinned result from small irregularities of the surface of an input figure.
The meaning of [STEP 5] in the above algorithm may become clearer by
writing as follows:
[STEP 5] (Test of terminating rule)
if no point changed through [STEP 4]
then
if distance = maxd
then stop (finishing the whole processing)
else go to [STEP 2] (finishing a subcycle)
endif
else go to [STEP 3]
endif
Remark 5.5 (Problems in realization). Major problems that should be
considered in implementing and executing surface/axis thinning algorithms
by computer are memory requirement and processing time (or computation
load). Concerning the first problem, at least one 3D array is necessary for
storing an input image. The above algorithm uses the same 3D array for
not only storing the distance transformation, but also storing a label image
produced at the intermediate step and storing the final result. This means the
memory requirement is almost minimum, that is, only one 3D array of nearly
the same size is required as an input image.
5.4.6 Use of a 1D list for auxiliary information
Processing time is, in principle, proportional to the number of iterations in
the main cycle. This factor cannot be discussed in general because the number
of iterations strongly depends on each individual image. Another factor that
is important for practicality is the number of times each voxel is accessed
(individual element of a 3D array). One possible way to reduce the number of
times of access is the use of a 1D list that stores a 1-voxel to be processed and
attributes of each voxel such as coordinates and labels. Subsequent procedures
are executed according to the contents of this list.
It has been ascertained through experiments that this method could sig-
nificantly reduce the processing time of the above algorithm, although algo-
rithms become a little more complicated due to the list manipulation. The
total amount of memory may increase a little by preparing the space for the
list. The memory space for a list also depends on each input image. The size
of the memory space for a list is usually not very big. In most cases it is
small compared to the memory size required for an input 3D image. Roughly