Paul Reiners

January 7, 2009

Introduction

In this article, we examine two types of animated image convolutions that are generated from two-D cellular automata (CA). Traditional convolutions take a static image as input and, using a convolution kernel, create a static image as output. Animated convolutions, as I define them, use a sequence of related kernels and successively apply the kernels to the original image. This results in a sequence of filtered images. We can thus create an animation by showing the sequence of filtered images successively.

We will present two different ways of creating a sequence of related kernels. Both of these use two-D CA. The first technique uses CA to operate on a user-defined 3-by-3 convolution kernel. The second technique uses the states of the CA itself as 3-by-3 kernels.

We assume that the reader is familiar with image processing convolution. For brevity, we also assume the reader is familiar with the concept of two-D cellular automata and some specific two-D cellular automata, such as Conway's Game of Life, Brian's Brain, and Cyclic Space. If not, he or she can consult one of the references listed.

Overview of CA Convolution Techniques

Each of these convolution techniques operates on the RGB values of the pixels in the image (the techniques could be easily adapted to operate on HSB or other representations of pixel colors, also). The convolutions operate separately on each of the R, G, and B values and then combine the new values to compute the filtered value. Below, when we talk about applying a kernel k to a pixel p, this will be shorthand for applying k to the individual RGB values of p and then combining the resulting convolved R, G, and B values to create the new convolved pixel.

Both of the convolution techniques will use standard 3-by-3 kernels.

The CA used will have n states, which are integers from 0 to n - 1 (inclusive). For example, in Conway's Game of Life, the value of n is 2. For other CA, such as Cyclic Space, n can be arbitrarily large.

For a given image, we create a CA of the same width and height. Thus, there is a 1-1 mapping between the pixels in the image and the cells in the CA. (This CA will be seeded initially with random values.)

The code I give in this paper is in Java and uses the Processing libraries. However, the technique can be easily implemented in other languages.

Convolutions Weighted by CA

In our first technique, the filtered value of the pixel is a weighted combination of the original value and the value obtained by applying a user-defined kernel. The weight is determined by the state of the corresponding cell in the CA.

In particular, let k be the user-defined kernel. For an individual pixel, p, let k(p) be the value obtained by applying k to p. Now, let s be the state of the CA cell corresponding to the pixel p (recall that s is an integer between 0 and n - 1). The new value p' of the transformed pixel will be a weighted average of p and k(p) with k(p) weighted by s / n. Hence 

	p' = (k(p) * s + p * (n - s)) / n

CA-Weighted Convolution Code

In getKernelSum(int, int, Color), we compute a new R, G, or B value in the usual way using the user-defined kernel. 

	private float getKernelSum(int x, int y, Color rGB) {
		float sum = (float) 0.0;
		for (int ky = -1; ky <= 1; ky++) {
			for (int kx = -1; kx <= 1; kx++) {
				// img is a one-dimensional array containing the image               
                                // pixels.  Need to compute its position in this 1-D array 
                                // from its 2-D coordinates.
				int pos = (y + ky) * img.width + (x + kx);

				int pixel = img.pixels[pos];
				float val;
				if (rGB == Color.RED) {
					val = red(pixel);
				} else if (rGB == Color.GREEN) {
					val = green(pixel);
				} else {
					val = blue(pixel);
				}

				sum += kernel[ky + 1][kx + 1] * val;
			}
		}

		return sum;
	}

In getWeightedKernelSum(int, int, int, int, Color), we compute a weighted average of the original R, G, or B value with the convolved value (computed in the previous function) using the CA state as the weight. 

	private float getWeightedKernelSum(int y, int x, int state, int pixel,
			Color rGB) {
		float origRGB;
		if (rGB == Color.RED) {
			origRGB = red(pixel);
		} else if (rGB == Color.GREEN) {
			origRGB = green(pixel);
		} else {
			origRGB = blue(pixel);
		}
		float rGBSum = getKernelSum(x, y, rGB);
		int n = cellularAutomaton.getN();
		float weightedRGBSum = (state * rGBSum + (n - state) * origRGB) / n;

		return weightedRGBSum;
	}

Finally, we combine the convolved R, G, and B values. 

	public int convolve(int y, int x, int state, int pixel) {
		float weightedRSum = getWeightedKernelSum(y, x, state, pixel, Color.RED);
		float weightedGSum = getWeightedKernelSum(y, x, state, pixel,
				Color.GREEN);
		float weightedBSum = getWeightedKernelSum(y, x, state, pixel,
				Color.BLUE);
		int c = color((int) weightedRSum, (int) weightedGSum,
				(int) weightedBSum);

		return c;
	}

You can view this algorithm in action here.

Direct CA Convolutions

Our next technique is simpler, but more profound in a sense. Rather than use the cell states of a CA to weight a traditional kernel, we use the cell states themselves as kernels. Thus, instead of using a single kernel for the entire image, we use a different 3-by-3 kernel for each pixel in the image. The kernel for a given pixel consists of the state of the CA cell corresponding to the pixel and the states of the eight neighbors of this cell (giving us a 3-by-3 kernel). We then normalize this kernel so that the sum of the kernel elements is 1.

I've found that, if the number of possible states n is large, the resulting animation tends to be "smoother". This should be fairly obvious. However, it's also the case with small n that it's possible to change the values of the states to obtain more smooth results.

For example, with Conway's Game of Life (in which n is 2), I first tried giving 'dead' cells a state value of 0 and 'live' cells a state value of 1. Because there tend to be more dead cells than live cells in a typical Life universe, in the resulting animation, the CA tended to dominate the original image. In effect, you basically saw a Life animation where the color of the live cells was the color of the 'underlying' image pixels. This can be fun to watch, but by simply switching the state values and giving live cells a value of 0 and dead cells a value of 1, I obtained much more subtle and aesthetically pleasing results. The image was subtly animated and not dominated by the mechanics, as it were, of the Life CA.

Also, although I've assumed that the CA states are integers from 0 to n - 1, there's no reason why they need be this. Interesting results I'm sure could be obtained using different integer (or floating-point values), including negative values. There is a lot of room for exploration in this area.

Direct CA Convolution Code

In getKernelSum(int, int, Color), we use the states of the CA cells as the kernel elements in computing a new R, G, or B value. 

	private float getKernelSum(int x, int y, Color rGB) {
		float sum = (float) 0.0;
		int stateTotal = 0;
		for (int ky = -1; ky <= 1; ky++) {
			for (int kx = -1; kx <= 1; kx++) {
				int pos = (y + ky) * img.width + (x + kx);

				int pixel = img.pixels[pos];
				float val;
				if (rGB == Color.RED) {
					val = red(pixel);
				} else if (rGB == Color.GREEN) {
					val = green(pixel);
				} else {
					val = blue(pixel);
				}

				// Use the corresponding CA state as the kernel element.
				int state = cellularAutomaton.getState(ky + y, kx + x);
				sum += state * val;
				stateTotal += state;
			}
		}

		// Normalize
		float kernelSum = sum / stateTotal;

		return kernelSum;
	}

Combine the individual R, G, and B values as before. 

	public int convolve(int y, int x, int state, int pixel) {
		float rSum = getKernelSum(x, y, Color.RED);
		float gSum = getKernelSum(x, y, Color.GREEN);
		float bSum = getKernelSum(x, y, Color.BLUE);
		int c = color((int) rSum, (int) gSum,
				(int) bSum);

		return c;
	}

You can view this algorithm in action here.

Display Code

The display code is quite straightforward and is the same for both types of convolutions. We simply iterate over the pixels and convolve each. draw() is called repeatedly by the Processing framework, causing animation. During each call to draw(), we update the CA by one step. 

	public void draw() {
		for (int y = 1; y < img.height - 1; y++) {
			for (int x = 1; x < img.width - 1; x++) {
				int state = cellularAutomaton.getState(y, x);
	
				int pos = y * img.width + x;
				int pixel = img.pixels[pos];
	
				int c = cAConvolution.convolve(y, x, state, pixel);
				edgeImg.pixels[pos] = c;
			}
		}
		edgeImg.updatePixels();
		image(edgeImg, 0, 0);
	
		cellularAutomaton.update();
	}

Conclusion

I've obtained aesthetically interesting results with both of these techniques. With CA-weighted animated convolutions, I've tried both Cyclic Space and Brian's Brain. With Cyclic Space, the CA tended to dominate the resulting animation at the expense of the image as filtered by the user-defined kernel. This can be okay, if that's what you're aiming for. However, I obtained more subtle and interesting results using Brian's Brain. With Brian's Brain, it looked like the image as transformed by the user-defined kernel was being subtly animated and it was hard to see the actual mechanics of Brian's Brain, in the animation (this isn't entirely true---you could see gliders in patches of solid color). I think that using CA-weighted animated convolutions is an interesting way to give life to a traditional convolution.

However, I think direct CA animated convolutions are more interesting both philosophically and aesthetically. There's no a priori reason why using the states of CA cells as convolution kernels should give aesthetically pleasing results. Obviously, if you were to apply randomly changing, random-valued kernels to individual pixels in an image, the resulting animation would probably be a horrible-looking mishmash. However, the coherence and aesthetic beauty of a CA can produce the same coherence and aesthetic beauty in an image animated by the CA. By using different CA and different integer values for the states, you make the animation as varied and as subtle or garish as you wish.

For example, a direct CA animated convolution, using Life or Brian's Brain, of van Gogh's Sunflower paintings adds a subtle, scintillating effect to the original paintings. If you were to look at a single still image from the animation, you probably couldn't easily distinguish it from the original painting (this is why I haven't included screenshots in the article---please try out the applets (here and here) or watch a QuickTime movie of the applet, instead). In the animation as generated by the Life or Brian's Brain, the original painting dominates, but it's like viewing a real sunflower as the subtly changing sunlight and perhaps a slight breeze give it animation.

References

Creative Commons License
Animated Convolutions Using Two-D Cellular Automata by Paul Reiners is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.