Cellular Automata

Over the last fifty years cellular automata (CA) have become increasingly popular, but their application to image processing has been limited by the need to manually generate rule sets. Therefore, we have investigated the possibility of training CAs to perform several image processing tasks, using the sequential floating forward search method to select good rule sets. A range of tasks were tested: noise filtering, thinning, and convex hulls. Our approach was developed for binary images, but can also be applied to gray scale images using threshold decomposition.

For example, given examples of images corrupted with 3 X 3 salt and pepper blocks, the following rules were learnt:
rule rule rule rule
The rules are based on 3 X 3 neighbourhood patterns of eight white and/or black (displayed as gray) pixels which are matched to windows in the test corrupted image, and are shown with a black central pixel - which is flipped after the application of the rule.

Applying these rules to the first image below gives the second image. Compare this to the best results achieved using multiple iterations of either a 3 X 3 or 5 X 5 median filter (shown as 3rd and 4th images):
noisy text noisy text noisy text noisy text

More recent work has looked at learning rules for grey level images. Some examples of applying these rule to remove various types of noise are shown:
CA destriping CA denoising

A different application of CAs is to perform copy-move forgery detection. Our approach combined CAs with Local Binary Patterns (LBPs) to extract simple and low dimensional feature vectors in the form of CA rules that represent local changes in pixel luminance values. the following shows the tampered image, the ground truth, and the CMF regions detected by our method:

More details are given in:

see also

return to Paul Rosin's homepage