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

(1) Topology preservation : Scan the whole of an input image in the prespec-
ified scanning mode, and test the deletability of every 1-voxel. Delete a
1-voxel (replace by a 0-voxel), if the voxel is deletable. Only one voxel is
deleted at any one time (simultaneous deletion of more than one voxel
never occurs). A deletable 1-voxel is deleted as soon as it is detected. Fur-
ther processes are applied to the image from which voxels were deleted.
That is, the algorithm is a sequential algorithm shown in Chapter 2.
The deletability test at each voxel is performed by testing whether local
features (connectivity index) satisfy the condition of Corollary 4.1 (com-
ponent index = 1 and connectivity number = 1 ) or Theorem 4.2 in the
3 3 neighborhood of the current voxel. The procedure to execute

this was presented in Section 4.8.
(2) Surface thinning : If a figure contains any of the voxel arrangements shown
in Def. 5.1 (Fig. 5.3), then a deletable voxel in such an arrangement is
eliminated (replaced by a 0-voxel). Unless a deletable voxel exists, no
deletion is required.
(3) Keeping central position : We shave a figure in the equal rate from the left
side, the right side, the up side, the down side, the front side, and the back
side. This is realized by applying the deletability test to only a 1-voxel that
has a 0-voxel in the specified side of the 6-neighborhood. For example, first
a 1-voxel that has a 0-voxel in the right is tested, second a 1-voxel having
a 0-voxel in the up side is tested, and so on. Thus, one time of scanning
the whole input image is achieved by scanning an image six times. These
six times of scanning are called a subcycle . This subcycle system has been
widely used in 2D image processing. Final results of thinning are affected
a little by the order of subcycles, although the effect is not extreme in
most cases. This effect is unavoidable in this type of algorithm.
(4) Suppression of degeneration : Subcycles are useful for suppressing degen-
eration, too.
(5) Other features : Only a local processing of the 3

× 3 ×

3 neighborhood
is employed in an algorithm. The state of voxel values in the 3

× 3 ×

3
neighborhood is classified by the calculation of local features such as the
connectivity index and the deletability test using them. Pattern matching
is used only for at most the 2

× 3 ×

× 2 × 2 neighborhood.

Remark 5.2. In 2D image processing, it is not di cult to list all possi-
ble arrangements of 0-and 1-pixels in the 3

×

3 neighborhood ( 51 patterns
exist with excluding symmetrical patterns each other). Then, we may de-
rive an algorithm by assigning a suitable output value to each of input
local patterns. Many thinning algorithms were designed by this procedure
[Toriwaki81, Stefanelli71, Tamura78, Tamura83]. On the other hand, for a 3D
image, there are 1 , 426 , 144 patterns of 0- and 1-voxels in the 3

3
neighborhood even if mutually symmetric patterns have been excluded. Then
it is almost impossible to design an ad hoc algorithm while taking into con-
sideration all of those patterns.

× 3 ×