Image Processing Reference
In-Depth Information
of each pixel in
R
should be found. If the pixel has more than one such neighbor,
it is said to belong to the medial axis (skeleton) of
R
. The definition of
closest
depends, of course, on the definition of distance. Obviously, the implementation of
such definition is typically prohibitive computationally. Many algorithms have been
proposed for improving computational efficiency while at the same time attempting
to produce a medial axis representation. Such skeletonizing algorithms iteratively
delete edge points of a region subject to the constraints that deletion of these points
(1) does not remove end points, (2) does not break connectedness and (3) does not
cause excessive erosion of the region.
Due to the enormous amount of algorithms, it is not easy to classify them. Differ-
ent criteria can be used in a a preliminary approach. A first classification can be done
according to the method used to obtain the skeleton. Following this criterion, the al-
gorithms are split into iterative and non-iterative. A second classification method
focuses on the properties which a black pixel must satisfy in order to be marked as
erasable. In this way, the properties can be
local
or
global
.
According to the first criterion, the skeletonizing algorithms can be classified
as either iterative or non-iterative. In iterative methods, skeletonizing algorithms
produce a skeleton by examining and deleting contour pixels through an iterative
process in either sequential or parallel way. Parallel algorithms may also be fur-
ther classified according to their performance, i.e., in 4-, 2-, or 1-subcycle manners.
The latter (1-subcycle parallel algorithms) have always received more considerable
attention in the research area of parallel skeletonizing as they have reduced the com-
putation time in the number of iterations, and that is why they are sometimes called
one-pass or fully parallel algorithms [14, 15, 22]. In sequential skeletonizing al-
gorithms, contour points are examined for deletion in a predetermined order. In
parallel skeletonizing algorithms, pixels are examined for deletion on the basis of
results obtained only from the previous iteration. That is why parallel skeletoniz-
ing algorithms are suitable for implementation in parallel processors. Non-iterative
(non-pixel based) skeletonizing algorithms produce a certain median or centre line
of the pattern to be thinned directly in one pass, without examining all the individual
pixels.
According to the second criterion, (see [19]), two different methods of pattern
analysis can be applied to determine the skeleton of an image or scene: Global
Pattern Analysis, where pixels are labeled depending on their distance from the
contours and Local Pattern Analysis, based on the repetition of the simultaneous
deletion of border points verifying certain conditions. This classification is not strict,
and some
hybrid
methods can be found in the literature, as Liu's method [30, 31],
based on the notion of
cell complex
. This method combines an iterative process
where
outer
cells are removed with two difference measures which provide some
ideas of the size of the maximum disk inscribed in the object.
Since Dinneenn [16] found in the 1950s that an averaging operation over a square
window with a high threshold resulted in a skeletonizing of the input image and later
Blum presented his definition of medial axis transformation [10, 11], many different
authors have contributed to the skeletonizing theory. After some attempts of defin-
ing the skeleton of an image and different skeletonizing algorithms, (e.g. [25, 38]),
Search WWH ::
Custom Search