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

images were artificial figures (a sphere, a cube, connection of them), a hand,
and a bronchus extracted from a CT image.
Figures 5.6 and 5.7 show thinned results of artificial figures. Input figures
were put in parallel with coordinate axis in Fig. 5.6 and rotated in Fig. 5.7.
Results from different thinning algorithms differ significantly from each other.
The thinning algorithm accompanied by Euclidean distance transformation is
affected less by the orientation and the rotation of an input figure and gives
natural results. Results of Algorithms 5.4 and 5.5 applied to the same input
image are shown in Fig. 5.8. By observing this carefully, the difference between
the surface and axis thinning is clearly apparent. Finally, Fig. 5.9 is a result
of axis thinning by Algorithm 5.6.
The generation of undesired branches (spurious branches) is controlled to
some extent by two kinds of parameters as presented in [Saito01, Toriwaki01].
A result is shown in Fig. 5.10. An input figure here is a Y-shaped connection
of three cylinders contaminated by random noise. A kind of trade-off between
generation of spurious branches and degeneration of a figure will be confirmed
in this example. Details of the method are presented in [Saito01, Toriwaki01].

5.4.9 Points in algorithm construction

Let us summarize in this section the important points in constructing thinning
algorithms. They show a method to discover the requirements for thinning
algorithms described in Section 5.4.2. How to integrate factors referred to
in these points in individual algorithms also strongly depends on computer
technologies available at the time. In fact, memory cost is much lower and
speed is much faster now than in the 1980s.
(i) Definition of functions : What are the contents of “thinning” that we con-
sider at the design of an algorithm. All of the following also relate to this,
such as definitions of a line figure and a surface figure, intuitive under-
standing of them, and constraints of an input figure. Most input figures
may be elongated figures in some applications. Topology preservation may
not be so important in other applications. Algorithms will become much
simplerinsuchcases.
(ii) Topology preservation : Did the topology of an input figure have to be
preserved precisely or not? The shape of an input figure may be restricted
in some applications.
(iii) Deletability test : The deletability test can be performed by either calcu-
lation of mathematical equations or local pattern matching. The former
method was first reported in [Yonekura80b] for all four types of connectiv-
ity and the outline was explained in this topic. Most other reports employ
the latter method with template matching on the 3

3 neighborhood
except for completely parallel algorithms employing the 5

× 3 ×

× 5 × 5 neigh-

borhood. Assuming the use of the 3 3 neighborhood, at least six

template patterns will be necessary which are symmetric to one particu-
lar template pattern, corresponding to six surfaces of a cubic voxel. When

× 3 ×