I was looking for a good way to illustrate functional composition and higher order functions, and thought that something could be done with Processing, a java-based graphics tool. Among other things, Processing exposes raw pixel data for the images it renders, and you can update the pixels programatically, providing a simple kind of image filtering.

For example, here’s some code that converts a color image to grayscale. Just like with HTML, colors are represented1 as 3 channels (red, green, blue), and each channel has 255 increments. A gray pixel has equal amounts of red, green, and blue, so if you get the overall brightness of a pixel, and set its color to that much red, green, and blue, it should turn the image gray.

 1 PImage img = loadImage("tattoo.jpg");
 2 size(img.width, img.height);  // set the window size
 3 image(img, 0, 0);  // render the image at x:y = 0:0
 5 loadPixels(); // load the image's pixels into an array
 6 for (int i = 0; i < pixels.length; i++) {
 7     // get the color for this pixel
 8     color c = pixels[i];
10     // get its brightness
11     float bright = brightness(c);
13     // Change its color to its grayscale equivalent
14     pixels[i] = color(bright, bright, bright);
15 }
16 updatePixels();  // render the new pixels to the screen

Here’s the original image:

the original image

…and here’s the filtered version:

the image in grayscale

You can define a bunch of routines like this, each looping through the pixels the same way, but adjusting the colors differently. But if you can separate the pixel-changing part from the pixel-looping part, then you can swap in ANY pixel-changing routine, giving you a flexible image filtering system.

The pixel-changing code is essentially a function that turns one pixel’s color into a new color, and the pixel-looping code uses it to replace each pixel’s original color. The pixel-changing function could be described like this:

1 color transform(color c) {
2     ...
3 }

Many modern programming languages support first-class functions, which are a natural way to model this. Processing uses a form of Java, which doesn’t have first-class functions, but we can wrap the functions in a class, giving us an object called a functor. I called this one ColorTrans, for “color transformer”.

1 abstract class ColorTrans {
2     public abstract color transform(color c);
3 }

The ColorTrans class’ only method, transform, is our pixel-changing function. We can re-write the loop from before to use a ColorTrans filter, and while we’re at it, we’ll move it into a method that takes the filename as a parameter, too.

 1 void filterImage(String path, ColorTrans filter) {
 2     PImage img = loadImage(path);
 3     size(img.width, img.height);
 4     image(img, 0, 0);
 6     loadPixels();
 7     for (int i = 0; i < pixels.length; i++) {
 8         // use the filter parameter
 9         pixels[i] = filter.transform(pixels[i]);
10     }
11     updatePixels();
12 }

We can easily recreate the grayscale filter from earlier as a ColorTrans.

1 ColorTrans grayscale = new ColorTrans() {
2     color transform(color c) {
3         float bright = brightness(c);
4         return color(bright, bright, bright);
5     }
6 };
8 filterImage("tattoo.jpg", grayscale);

Another really easy filter to write is an inverter. If a pixel has R:100, G:30, B:255, an inverter will return the color R:(255-100), G:(255-30), B:(255-255), or R:155, G:225, B:0.

1 ColorTrans invert = new ColorTrans() {
2     color transform(color c) {
3         return color(255 - red(c),
4                      255 - green(c),
5                      255 - blue(c));
6     }
7 };
9 filterImage("tattoo.jpg", invert);

The image produced by an inverter is like a film negative.

inverted, like a negative

Now we begin to see the benefits of keeping the-parts-that-change separate from the-parts-that-don’t: we can easily define and swap in new filters. This is one of the big parts of higher-order programming: writing routines that are configured by passing in functions (or functors, in this case) to do part of the work.

Manufacturing a ColorTrans

A useful kind of filter is one that increases (or decreases) the color on one channel: add some red, or remove some green. This kind of filter is easy to create:

1 ColorTrans aFifthMoreRed = new ColorTrans() {
2     color transform(color c) {
3     	return color(red(c) * 1.2, green(c), blue(c));
4     }
5 };

This filter will increase the amout of red in the image by 20%. But 20% is a pretty arbitrary number; it’d be better if we could tell the filter how much to increase the red by. Generally, you’d add an “amount” parameter to the transform method, but then filterImage would have to know that this ColorTrans object takes an extra parameter. It’s kind of nice having filterImage treat all ColorTrans objects the same, just passing in the color.

Instead, we can make a method that builds ColorTrans objects: we tell it how much to increase the red by, and it builds a ColorTrans that does it for us.

 1 ColorTrans ampRed(final float amount) {
 2     return new ColorTrans() {
 3         color transform(color c) {
 4             color(red(c) * amount, green(c), blue(c));
 5         }
 6     };
 7 }
 9 ColorTrans aQuarterMoreRed = ampRed(1.25);
10 ColorTrans aThirdLessRed = ampRed(2/3);
11 ColorTrans noRedAtAll = ampRed(0);

(If you’re curious why amount is final, the short answer is “because the compiler says so,” but there’s a better answer2.)

This is pretty nice, because we can use this inside an animation loop, animating the amount of color amplification.

 1 float theta = 0.0;
 3 void setup() {
 4     filterImage("tattoo.jpg", noChange);
 5 }
 7 void draw() {
 8     float ampRedAmount = sin(theta) * 1.2;
 9     filterImage("tattoo.jpg", ampRed(ampRedAmount));
10     theta += 0.1;
11 }

[Here’s where I’d link to the applet, nicely hosted somewhere, if I had a hosting service that allowed applets. I’ll try to find a place to put all the code, so you can try it yourself.]

Processing calls setup to initialize the animation, and calls draw once per “tick”, to advance the animation. Here, in each frame of the animation, a new ColorTrans is constructed by ampRed, with the amount tied to the sine wave function, oscillating between 0 and 1.2. When viewed, the amount of red in the image swells and falls, and back again3.

This is another big part of higher-order programming: writing functions that build other functions, based on some arguments. Combined with routines that take functions as arguments, it’s a handy way to break down some problems. If done well, the routines that take functions as arguments, and the functions that build those functions, can become a sort of mini-language, a fluent interface, or almost an embedded DSL.

Plugging filters together - filter composition

This is where it gets fun. Suppose you’ve created an ampBlue that works just like ampRed, and now you want to filter an image with both of them. One approach might be something like this:

1 void draw() {
2     filterImage("tattoo.jpg", ampRed(sin(theta) * 1.2));
3     filterImage("tattoo.jpg", ampBlue(cos(theta) * 1.2));
4 }

Using the sine and cosine functions, the image should pulse nicely through reds and blues. The only problem is that it doesn’t really work, because filterImage loads the image fresh from the filesystem each time, so you only get the effect of the ampBlue filter. So how can we apply multiple filters?

We plug them together. We want a filter that does the work of two other filters, and we want it to look like any other filter, so filterImage won’t know the difference. To get this, we can add a method to ColorTrans that returns a new ColorTrans, which calls first the one, and then the other.

 1 class ColorTrans {
 2     ...
 3     public ColorTrans then(final ColorTrans applySecond) {
 4         final ColorTrans applyFirst = this;
 5         return new ColorTrans() {
 6 	    color transform(color c) {
 7 	        return applySecond(applyFirst(c));
 8 	    }
 9 	};
10     }
11 }
13 filterImage("tattoo.jpg", grayscale.then(invert));

first grayscaled, then inverted

Combining filters becomes a matter of chaining them together through then. The red-and-blue example becomes:

1 void draw() {
2    filterImage("tattoo.jpg",
3         ampRed(sin(theta) * 1.2).then(
4             ampBlue(cos(theta) * 1.2)));
5 }

Processing does it kind of this way, too

If you look at the source for Processing, in PImage.java on line 619, you’ll find code that looks kind of like this:

 1 public void filter(int kind) {
 2     loadPixels();
 4     switch (kind) {
 5       case BLUR: ...
 6       case GRAY: ...
 7       case INVERT: ...
 8       case POSTERIZE: ...
 9       case RGB: ...
10       case THRESHOLD: ...
11       case ERODE: ...
12       case DILATE: ...
13     }
14     updatePixels();  // mark as modified
15   }

It basically does just what I’ve been doing, except the operations are hard-coded into the source, rather than being separated behind a class interface. The filters aren’t composable directly, though you can call a number of them in a row:

1 filter(INVERT);
2 filter(THRESHOLD);
3 filter(DILATE);

One benefit of this approach is that it’s easy to see, line-by-line, exactly what’s happening. I’d bet it beats the pants off of the ColorTrans version in benchmarks, too. But filters aren’t composeable, and it’s certainly not extendable. When you’re doing computation-intensive graphics, every bit of speed is important; when you’re illustrating a programming idea, it’s not. Decide for yourself which is more important for your needs.

1. It may seem weird, if you know Java, that the parameter’s type is color – it’s not a java primitive, but it doesn’t follow the normal classname conventions. It’s just the way Processing does it. You can read more about the color constructor in the Processing reference. [back]

2. Taken from the AnonymousInnerClasses page on the Portland Patterns Repository, 2009-04-30:

AnonymousInnerClasses can also be used to create something like closures in the JavaLanguage. However they do not "close over" the lexical environment so they aren't TrueClosures. (They can capture the value of local variables, but they do not have access to the variable binding so they can't change the original variable. Which Java makes quite clear by only allowing InnerClasses to refer to local variables that have been declared final (so no-one can change them)).


3. The noChange filter returns the same color it was given – an identity function. filterImage is called inside setup only so the window size is set correctly, since setting the size inside draw has no effect. And theta is just a Greek letter often used for angles and trigonometry.[back]