Image Processing Reference
In-Depth Information
3.4
Cellular Automata
Cellular automata (CA) are dynamical systems discrete in time and space. These
features make CA suitable for dealing with some problems in the analysis of digital
images, where pixels are identified with cells and the changes in a cell depends on
the current state plus the current state of its neighbours [13, 23, 37, 40].
The dynamics of CA has been extensively studied across a variety of disciplines
from different perspectives (see, e.g., [1, 8, 12]). Technically, a CA consists of two
components. The first one is a
cellular space
: a lattice of
N
identical finite-state
machines (cells) each with an identical pattern of local connections to other cells,
with boundary conditions if the lattice is finite. The second component is a set of
transition rules that gives the update state of each cell. The formal description of the
algorithm in the framework of CA requires to provide the cellular space and the set
of rules.
Given a
n
×
m
image, we will consider as
cellular space
a rectangular grid
(
n
+
2
with 8-adjacency. We will consider a cell of the cellular space for each
pixel on the image plus two extra columns and rows surrounding such cells. The
intuition behind these extra pixel lines is to consider that they are
white pixels
,which
do no affect to the skeletonizing process. The states in these extra cells never change
and we will consider that the rules are not applied on them, but they contribute to
the neighborhood of the border pixels of the original image.
With respect to the set of states, they must encode the information of each pixel
along all the steps of the algorithm. The basic information for the skeletonizing pro-
cess of a black and white image is, of course, the color of the pixel, but, depending
on the algorithm, different features can be associated to the pixel. If these features
change dynamically along the skeletonizing process, they should be encoded in the
set of states.
In order to fix ideas, we will consider the Guo and Hall algorithm. On the one
hand, the set of states should inform about the
color B
or
W
(black or white) of the
pixel at each discrete step, but, according to the algorithm, the set of pixels are split
into two subsections and only one of them is evaluated at each step. In this way, the
state of a cell at time
t
should inform if the cell corresponds to an evaluable pixel or
to a non-evaluable pixel. Putting together both pieces of information, the color and
the evaluable situation (
E
for evaluable and
N
for non evaluable), we obtain four
possible states for each cell of the cellular space:
BE
,
WE
,
BN
and
WN
.
Bearing in mind this interpretation for the states, the initial state of each cell
is determined by the color of the corresponding pixel in the input image and the
corresponding sub-section. In the initial configuration, we will take the pixels of the
first sub-section, corresponding to the pixels
a
ij
such that
i
)
×
(
m
+
2
)
j
is even, are
evaluable
and the pixels corresponding to the second sub-section, i.e., pixels
a
ij
such that
i
+
+
j
is odd, are non evaluable
4
(see Fig. 3.3).
In the description of the set of rules, it is necessary to describe the conditions
necessary for changing the state of a cell. Such conditions are taken directly from
4
If the second subsection is taken as evaluable in the initial configuration, the pixels of the
final skeleton are different.
Search WWH ::
Custom Search