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

The resulting binary output images are then combined as a simple summation to
produce the edge magnitudes.
To find suitable rules a deterministic approach was used, namely sequential float-
ing forward search (SFFS) [28], which starts from the empty set and iteratively adds
the best performing rule. The objective function was such that the edge magnitudes
constructed from the CA with threshold decomposition should provide a good match
- in terms of root mean square (RMS) - to the gray level target ground truth edge
map.
The final rule set that was learnt from the training data simply consisted of a
single rule. It specified that any white pixel in a 3 3 homogeneous (i.e. all white)

neighbourhood is set to black (inverted). For each of the binary images that the
input is decomposed into, this causes all white pixels to be replaced by black ex-
cept for pixels adjacent to black pixels in the input image. Thus, a black image
is formed containing a one pixel wide white strip along the original black/white
transitions, and these images are summed at the reconstruction stage of threshold
decomposition.

×

5.4 Post-processing of Edges

In the introduction we stated how, after an initial edge detection, the results are often
thresholded, linked, and thinned. Clearly, cellular automata have been designed for
thinning - see chapter 3. They are also suitable for performing linking, although this
is less common.
Lee and Bruce [16] describe a method for edge detection that is initialised with
computing a gradient angle and edge magnitude for each pixel using an algorithm
mimicking the Prewitt edge detector. They then use CA to perform adaptive thresh-
olding based on the gradient angle and edge magnitude information. The edges are
typically overestimated after adaptive thresholding, and each edge pixel is tested,
and removed if it has the lowest edge magnitude in its neighbourhood and removal
of this pixel will not bisect the edge. Further post-processing is performed using CA
to thin wide edges, remove short edges, and delete the edges which enclose small
regions.
Chang et al. 's [5] approach to edge detection involves using an “orientation infor-
mation measure” that essentially estimates edge strength, and is used to provide an
under-thresholded sparse binary edge map (the mark matrix). CA rules are then ap-
plied to link the edge pixels. A set of 3 3 edge (line) patterns are defined based on

the assumption that the width of edges is one pixel, and the CA updates a pixel state
to edge if it matches an edge pattern when taking as edge the pixel with maximum
orientation information measure in its neighbourhood or semi-neighbourhood.
Like Chang et al. , the method of Peer et al. [22] starts with a mark matrix, which
is however undefined. Therefore, it is not possible to replicate their algorithm. The
next stage of their method is to apply Conway's Game of Life to the mark matrix to
generate a binary edge map.

×