Steve on Image Processing

This is the third post about using lookup tables to process binary images. The first two posts were:

The most fun I've had with binary image lookup tables is playing around with Conway's Game of Life, the most famous example of a cellular automaton. Martin Gardner popularized the Game of Life in his Mathematical Games column in Scientific American:

Of course, there are MANY web sites devoted to this game.

In Conway's Game of Life, each cell in a rectangular grid is either "alive" or "dead" at generation N. Going from one generation to the next, cells "die" or are "born" according to the following rules (as stated in Gardner's first article):

1. Survivals. Every counter [cell] with two or three neighboring counters survives for the next generation.

2. Deaths. Each counter with four or more neighbors dies (is removed) from overpopulation. Every counter with one neighbor or none dies from isolation.

3. Births. Each empty cell adjacent to exactly three neighbors - no more, no fewer - is a birth cell. A counter is placed on it at the next move.

Gardner talks about "counters" because, at the time, computer simulation was simply not available to most readers of Scientific American. In his 1970 article, Gardner explains how to play: "To play life you must have a fairly large checkerboard and a plentiful supply of flat counters of two colors. (Small checkers or poker chips do nicely.) An Oriental "go" board can be used if you can find flat counters that are small enough to fit within its cells. (Go stones are unusable because they are not flat.) It is possible to work with pencil and graph paper but it is much easier, particularly for beginners, to use counters and a board."

OK, back to the present time, when we can use a computer instead of a checkerboard and poker chips. Conway's rules are based on a 3-by-3 neighborhood and so can be implemented using a lookup table. Here's a function which applies Conway's rules to a neighborhood:

type conway

function out = conway(nhood)

live = nhood(2,2) == 1;
P = sum(nhood(:)) - nhood(2,2);  % number of live neighbors

out = (live && ((2 <= P) && (P <= 3))) || ...
   (~live && (P == 3));

Using conway and makelut we can construct a lookup table:

conway_lut = makelut(@conway, 3);

Here's a very small "blinker" pattern. The pattern repeats itself with a period of two generations.

Generation 1:

bw = zeros(5, 5);
bw(3, 2:4) = 1

bw =

     0     0     0     0     0
     0     0     0     0     0
     0     1     1     1     0
     0     0     0     0     0
     0     0     0     0     0

Generation 2:

bw = applylut(bw, conway_lut)

bw =

     0     0     0     0     0
     0     0     1     0     0
     0     0     1     0     0
     0     0     1     0     0
     0     0     0     0     0

Generation 3:

bw = applylut(bw, conway_lut)

bw =

     0     0     0     0     0
     0     0     0     0     0
     0     1     1     1     0
     0     0     0     0     0
     0     0     0     0     0

According to the Wikipedia article on Conway's Game of Life, the first pattern discovered to grow without bound was the "Gosper glider gun." A "glider" is a small configuration of cells that periodically recreates itself one step over. With sufficient imagination, you can see that it "glides." Here is the glider gun:

url = 'http://blogs.mathworks.com/images/steve/2008/gosper_glider_gun.png';
bw = imread(url);
h = imshow(bw, 'InitialMagnification', 'fit')

h =

  349.1982

This pattern will periodically produce new gliders and send them shooting across space.

This code animates the Game of Life board for the Gosper glider gun.

for k = 1:300
    bw = applylut(bw, conway_lut);
    set(h, 'CData', bw);
    pause(0.05);
end

Here's an 18-second video clip showing the glider gun in action.

My last post (I think!) in this series will be about a lookup table optimization we introduced in a recent release of the Image Processing Toolbox. Look for it soon.

Get the MATLAB code

Published with MATLAB® 7.6