Morphological image processing

Here's a cool little topic. Let's think about how to extract borders in an image. I'm sure you could think of hundreds of heuristics, but I'd like to discuss one particular heuristic that, indirectly, leads to some pretty cool results relating to cellular automata.

The technique is called "morphology", and it's one of those ideas which starts out with very simple rules, but, when the rules are composed, can yield complex behaviour.

The central components in morphology are that of a union, complement and erosion of images. We'll only be working with pure black-and-white images here, but this can all be extended (with some effort) to grayscale and color images. If we represent images $A$ and $B$ as the set of coordinate-pairs for all black pixels, then $A\cup B$ is the normal set union, the resulting image being a "combination" of both. The complement, $A^c$, just flips black pixels to white, and white pixels to black. Here are some examples

$\cup$ $=$

and

$^c$ $=$

Erosion

Erosion, however, is an operation which takes a normal image $A$, and a so called structure element, $S$, to produce a new image $B$. A structure element is a just small mini-image, typically something like a $3\times 3$ set of black pixels. The erosion, $A\ominus S$, then, is the act of placing the center of the structure element (or some arbitrarily center-replacement if the width is even) at each pixel of the input image $A$ and asking "does this local image patch look identical to the structure element?". If the answer is yes, a black pixel is placed on that position of output image.

Formally, you could express this operation as $$ A\ominus S = \Big\{ (x,y)\ |\ S_{(x,y)}\subset A \Big\} $$ where $S_{(x,y)} = \{ (x+i,y+j)\ |\ (i,j)\in S \}$ is just the translation of $S$ to postion $(x,y)$. (Here we're using the version which translates the upper-left-corner, but I'll leave it as an exercise to express how to translate from the center.)

Here's an example:

$\ominus$ $=$

Dilation

With these basic components we could start defining higher-order operations. I'll only cover dilation, which is simply $$ A\oplus S = (A^c \ominus S)^c $$ As the name implies, this operation sort of "expands" the objects in the image

$\oplus$ $=$

Borders

We don't actually need higher-order operations to solve the original problem posed. How do you use this to extract borders? The solution is natural in this algebra of images that we've developed $$ \beta(A) = A - A\ominus S $$ where $X-Y = X\cap Y^c = (X^c\cup Y)^c $. In other words, just contract the objects in the image slightly, and then look at the difference between the original image and the result.

$\beta$ $\Bigg($ $\Bigg)$ $= $

Hacking in cellular automata

Now for the cool part. While these operations were originally intended for processing images, it turns out that they have a huge expressive power when composed (in fact they're turing complete).

Recall the rules for game of life. We'll only need those rules which result in a cell-activation in the next generation. The first is "if there are two or three live neigbours, the cell lives on", and the second "any dead cell with exactly three live neighbours is born".

Notice the connection between this and erosion. Erosion activates a pixel in the output image if a perfect match with the structure element is found.

Let $S_1, \dots, S_k$ be the permutations of neighbourhoods which satisfy the first rule, i.e. $S_1 =$, $S_2 =$, $S_3 =$,$\dots$, and $S_{k+1}, \dots, S_n$ those which satisfy the second rule.

Using these patterns as structure elements, the awesome thing is that we can now express an iteration of game of life $G(A)$ in closed-form using the language of morphology! So $$ G(A) = (A\ominus S_1) \cup (A\ominus S_2) \cup \cdots \cup (A\ominus S_n). $$

Randomized cellular automata

But you've probably already seen game of life in all shapes and sizes of starting conditions. Instead, notice how this leads to a natural generalization to other kinds of cellular automata. Why use those particular $S_1, \dots, S_n$ rules specified by game of life? Why not use a different combination of rules?

Below I'm using a set of random structure elements (which are themselves randomized every once in a while to show you the full range of what can be expressed), in order to produce the following

G $\Bigg($ $\Bigg)$ $= $

If you'd like to play with this yourself, check out this small companion library. In fact, this is essentially all that's needed to do border-extraction:


        var S = morph.generateStructureElement(3);
        var eroded = morph.erode( image, S );
        var border = morph.subtract( image, eroded );

Written by Daniel Rapp. Check out the code for this on Github.