Skeletonizing Digital Images with Cellular Automata - Cellular Automata in Image Processing and Geometry - page 52

WN WE WN WE WN

WE BN BE BN WE

WN WE BN WE WN

WE WN WE WN WE

WN WE WN WE WN

(a) (b)

Fig. 3.3 A toy example of black and white image and the initial configuration of the associ-
ated CA for skeletonizing it according to the Guo and Hall algorithm

the Guo and Hall algorithm. A cell will change its state if the corresponding pixel in
the image satisfies the Guo and Hall conditions. Since each cell can be in one of four
different states, a full description of the rules needs to consider all the possibilities
of the 3 2 18 rules. Obviously, they are too much from a

practical point of view. Nevertheless, we can provide an intensive description.

3 neighborhood, i.e., 4 9

× =

• If the central pixel is in the state WN , the next state is WE , regardless the states

of the surrounding pixels.

• If the central pixel is in the state WE , the next state is WN , regardless the states

of the surrounding pixels.

The intuition is clear. If the cell corresponds to a white pixel, it remains white to
the end of the process. The unique change is that the pixel alternates the condition
of evaluable and non evaluable in each step.

• If the central pixel is in the state BN , the next state is BE , regardless the remaining

cells of the neighborhood.

If a cell correspond to a black pixel and the pixel belongs to the non evaluable
section, it remains black, but in the next step it will be evaluable.
With these descriptions, it only remains to describe the rules in case of the central
pixel is BE . In this case, it should be evaluated according to the Guo and Hall condi-
tions in order to decide if the next state will be BN or WN . Nevertheless, the number
of possibilities is enormous. By fixing the state of the central pixel, four possibilities
for the remaining eight cells, i.e., 4 8 2 16 possibilities, should be considered.

In order to reduce the number of different CA rules, we observe than the decision
of change the current state BE (to the state BN or WN ) only depends on the color
of the surrounding pixels and not on the evaluable or non evaluable condition. This
consideration reduces drastically the number of possibilities, since only 2 8

=

= 256

cases should be considered.
In order to encode each of these cases, we can use the enumeration of the pixels
used in the Section 3.3 to represent the neighborhood of the pixel P 0in ( i , j ) .Given