Image Processing Reference
In-Depth Information
Rosenfeld [36] was the first to evaluate the necessary and sufficient conditions
for preserving topology while deleting border points in parallel process. Only a
few years later, Pavlidis [34] proposed a combination of parallel and sequential
operations.
In 1980s, many other algorithms were proposed (see, e.g., [3, 18, 45]). Among
them, it is Baruch's remarkable algorithm [7]. It is a non iterative, non pixel-based
algorithm. The skeleton is produced in one pass, by line following. Another impor-
tant contribution is the Guo and Hall algorithm, which will be showed in detail in
Section 3.3. In this algorithm, the contour pixels are examined for deletion in an iter-
ative process and it has been the basis for further refinements (see, e.g., [46]). There
are many different approaches to the problem of skeletonizing and a detailed survey
of the different methods is out of the scope of this chapter 3 . Among the different
research areas around the skeletonization problem, we can cite the studies based on
distance transform of the shape and skeleton pruning based on branch analysis (see,
for example, [4-6, 9, 41]). The research of skeletonizing algorithms also includes
different computational models, as the algorithm presented by Altuwaijri and Bay-
oumi [2] where self-organizing neural networks are used or the use of skeletonizing
in color images [33].
As pointed out above, there exists an enormous amount of skeletonizing algo-
rithms. Generally, each of the presented algorithms has its own advantages and
disadvantages, and each has its applications where it performs better than others.
Therefore, it is often difficult to directly compare the results.
3.3
Guo and Hall Algorithm
As an example of skeletonizing algorithm, we will see the implementation of a
classical algorithm, the Guo and Hall algorithm [21, 22]. It is a so-called 1-subcycle
parallel algorithm or fully parallel algorithm. It is an iterative edge-point erosion
algorithm where a 3
3 window is considered around each pixel of the image with
a set of rules applied to the contents of the window. In a sequential simulation of
the algorithm, a unique window is moved along the image, whereas in the parallel
one, all the windows are considered simultaneously. The skeleton is obtained by an
iterative procedure of skeletonizing: the border points are removed as long as they
are not considered significant. The remaining set of points is called the skeleton .
In this algorithm, the contour pixels are examined for deletion in an iterative
process. The decision is based on a 3
×
3 neighbourhood. The image is divided into
two disjoint areas (sub-sections), similarly to a chess board. One of the sections
is composed by the pixels a ij such that i
×
j is even. Alternatively, the second sub-
section corresponds to the pixels a ij such that i
+
j is odd. The algorithm consists on
two sub-iterations where the removal of redundant pixels from both sub-sections are
alternated, i.e., in each step only the pixels of one of the subsections are evaluated
for its deletion. This is repeated until there are no redundant pixels left.
+
3
A good introduction can be found in [39].
 
Search WWH ::




Custom Search