Image Processing Reference
In-Depth Information
information
, but it should also keep the basic structure. The concept of skeleton
was introduced by Blum in [10, 11], under the name of medial axis transformation,
but other previous approaches can be found in the literature (see, e.g., [16, 28]).
The skeleton of an image is useful to characterize objects by compact represen-
tation while preserving the connectivity and topological properties of any image.
The most important features concerning a shape are its
topology
(represented by
connected components, holes, etc.) and its
geometry
(elongated parts, ramifications,
etc.), thus they must be preserved.
Currently, there are many different definitions of the skeleton of a black and white
image and, according to Saeed
et al.
[39], more than one thousand algorithms have
been published on image skeletonization. Nevertheless, roughly speaking, we can
say that the image
B
is a skeleton of the black and white image
A
, if the former has
fewer black pixels than the latter, preserves its topological properties and, in some
sense, keeps its
meaning
. Figure 3.1 illustrates this idea. The skeletonized image
keeps the
meaning
of the original one and it uses fewer black pixels. It keeps the
basic geometry of the original image and also its topology. Let us remark that the
white regions inside the hand-made words are also white regions in the skeletonized
one and the connectedness is preserved.
As pointed out by Rosenfeld [36], the concept of skeletonizing
1
isnoteasytobe
defined mathematically; however it seems reasonable to require that any skeletoniz-
ing algorithm should preserve the connectedness for both objects and their comple-
ment; leave unchanged 1-pixel wide and isolated points; and change objects whose
length and width are both greater than 1.
From the computational side, a digital image can be roughly defined as a function
from a two dimensional surface which maps each point from the surface onto a set
of attributes as brightness or color. Technically, a digital image can be considered as
a bi-dimensional array of
n
×
m
pixels. Each pixel can be characterized by a triplet
(
represents its position in the array and
a
encodes brightness, color or any other feature associated to the position
i
,
j
,
a
)
(usually written as
a
ij
)where
(
i
,
j
)
.Asin
many other image processing algorithms, the basic procedure for skeletonizing an
image involve a discrete transformation of the features associated with the position
(
(
i
,
j
)
according to the current values of such features (i.e., the current value of
a
)
together with the values of the features of the neighbour positions. From this point
of view, a cellular automaton can be considered as a natural computer device for
such transformations [23, 40]. As usual, pixels are identified with cells of the cellular
automaton and the encoding
a
represent the current
state
of the pixel. In many cases,
the transformation of all the pixels can be done in parallel, since the
state
of a pixel
at the step
i
only depends on the
states
of a set of pixels at the step
i
i
,
j
)
1.
Such parallelism in skeletonizing algorithms has been broadly studied (see, e.g.,
[21, 32, 43, 45]). The development of new hardware architectures has also con-
tributed to new parallel implementations of these algorithms [19, 24, 26]. Recently, a
parallel implementation of a cellular automata skeletonizing algorithm developed by
−
1
Rosenfeld used the word
thinning
instead of
skeletonizing
. In this paper, both terms are
considered synonymous. Nevertheless, in the literature many different definitions of
skele-
tonizing
and
thinning
can be found, not all of them equivalent.
Search WWH ::
Custom Search