Edge Detection Using Cellular Automata - Cellular Automata in Image Processing and Geometry - page 84

connects to its neighbouring pixels (cells), and the pixel values (0 or 1 in binary
images) are the state values. Basically, the process of edge detection takes several
iterations of state transition from the initial states (the input image pixel values) to
the final states (the output image with 1 representing edge pixels and 0 the others).
It is critical to find good state transition rules for the CA.
The state transition rule proposed by Wongthanavasu and Sadananda [45] is prob-
ably the simplest one, where a cell changes its state from 1 to 0 only if all its von
Neumann neighbours have state value 1, otherwise it retains its original state (either
1 or 0). Though simple, this rule can produce reasonable results. It is intuitively un-
derstandable why this simple rule works. Suppose that we have a contiguous region
of 1 as the foreground, then one iteration of CA evolution using this rule will result
in all the inner pixels (which have all 1 in their neighbourhoods) changing to 0 (non-
edge), while the boundary pixels (those have at least one 0 in their neighbourhoods)
to remain as 1 (i.e. edge). More iterations will not change the pattern. The weakness
of this rule is also obvious: if noisy pixels (value 0) exist inside a foreground region,
the neighbouring pixels of a noisy pixel will remain unchanged, and wrongly clas-
sified as edges. Thus, this approach is not able to work effectively in the presence of
noise.
To find optimal state transition rules, several researchers resorted to genetic algo-
rithms. As early as in 1994, Sahota et al. [35] used a genetic algorithm to train CA
to find optimal rules for edge detection. They used three simple original/edge image
pairs as the training samples, and the obtained rules were then used in edge detec-
tion. They did not describe the rules they obtained, and only showed the detection
results of two manually designed toy images.
Selvapeter and Hordijk [37] adopted the same method as in [35] to train CA,
where they used similar original/edge image pairs as the training samples. The con-
tribution of their work was to deal with real images with noise. They simply used a
CA-based image noise filter [38] as the first step to denoise the image, and then used
the trained CA rules for edge detection. They showed that the CA-based method can
produce comparable results to the other methods such as Canny, Prewitt, Sobel, and
Laplacian of Gaussian operators when the image is noiseless, and it can also pro-
duce reasonable results when the image is noisy, while the other methods failed
to produce meaningful edge detection results. However, their comparisons in noisy
cases are unfair because they had first denoised the image before using the CA to
detect the edges, while they used the other methods to directly detect the edges in
the noisy image.
Batouche et al. [3] also applied genetic algorithms to train CA for binary image
edge detection. Instead of training rules for all the 2 9 512 pixel patterns in a Moore

neighbourhood, they assigned those rotational symmetric patterns (that rotate 0 ⓦ ,
90 ⓦ , 180 ⓦ , 270 ⓦ , or flip horizontally or vertically) the same state transition rule. A
weak matching criterion was introduced, so that some patterns with a difference less
than a similarity threshold were further merged into a single rule. They assembled
15 state transition rules into a packet, which is represented by a chromosome, and
trained to produce optimal rules. Experiments showed that edges are successfully
detected, but are a little bit thick.

=