Filigrams: A New Type of Pretty Picture

by Simon Tatham, mathematician and programmer

Synopsis

Filigrams are a type of pretty pictures generated by mathematical means. They're not technically a type of fractal, although they contain elements which people who know fractals might find hauntingly familiar. They're something I invented by accident once and decided to polish up because it looked pretty.

Genesis

I produced the first filigram completely by mistake. When I was 14 or so, my GCSE Computer Studies teacher showed me a short BASIC program on a BBC Micro that plotted a pleasant repeating pattern of interlocking circles:

I thought it was pretty enough that I should take the program home and run it on my Amiga, where I could give it the benefit of better graphics and see how much prettier it looked then.

So I memorised the important details of the program and went home to a real computer. Completely by accident, I got one character wrong when I typed the program back in, and it generated this instead:

Now that's much more interesting than interlocking circles, isn't it? It's got clear structure at the centre - black fades to white and jumps back to black again, repeatedly, in narrower and narrower stripes. Then, once the stripes become smaller than the distance between pixels, the delicate filigree (hence the name) degenerates into chaos. But beyond that, as if by magic, the chaos reforms into a new order, with little butterfly shapes embedded in the swirling black and white maelstrom. I stared at this feast of interlocking detail and was very glad I'd typed the circles formula in wrong. Then I set about enlarging it to poster size, so I could print it out and put it on my wall.

Unfortunately, the pattern proved to be elusive. The way it was generated provided an obvious way of magnifying it: the program was computing a function at every point of a square grid, so to enlarge it you just compute the same function at some new points in between the original points, right? Wrong - if you try that, a lot of the interesting detail in the butterfly shapes just disappears. Some of it remains, but more and more of the detail disappears the further you enlarge the image. It was like trying to nail fog to the wall - at 320x256 resolution, the image obediently sat there and looked pretty, but as soon as I looked any closer it vanished. Infuriating.

And there the matter rested for nearly ten years, until one day, after having done a maths degree, I remembered it and came back to see if I could finally find a way to catch that fog and nail it down.

Analysis

(Warning to non-mathematicians: this section may get a little intense. But there are pretty pictures to look at, so that's all right :-)

The formula I'd completely failed to type correctly was the obvious "circular" formula: x^2+y^2. The program I saw computed the fractional part of this function at every point on the screen and converted it to a colour value. This produces an N-colour image of interlocking circles, and the pattern ends up repeating itself after long enough. Instead of this, though, I replaced the addition with a multiplication: x^2*y^2, with its fractional part taken, generates the picture shown above.

So that explains the central section: each stripe in the centre follows a line along which x*y is constant. Based on this level of understanding, I was able to replace the function with the slightly more complex (2x+y)(2x-y)(x+2y)(x-2y), which produces a nice symmetric cross shape at the centre:

But we still haven't explained the butterflies - and I knew that I would have to understand what the butterflies were if I were to avoid them disappearing when magnified. So when I came back to the problem nearly ten years later, I looked at it with the eyes of a much more highly trained mathematician, and was finally able to see far enough into the chaos to pin down the cause of the butterflies.

The reason the central section of the image has such smooth changes of colour is that the values of f(x,y) don't vary by much over the distance between pixels. But out in the butterfly regions, f(x,y) is growing much faster than that; so why are those butterflies appearing? Answer: it must be because the difference in f(x,y) between one pixel and the next is very close to an integer - so that the difference in the fractional part of f(x,y) is very small even though the actual values of f differ by a lot. And that's why half the butterflies disappear when you enlarge the image by a factor of two: when the difference in f between two pixels is close to an odd integer, then the fractional part of f half-way between the two pixels will be about 1/2 away from what it was at the original pixels themselves - as different as it's possible to be. No wonder the butterflies disappeared so easily.

So at the centre of every butterfly, the fractional part of f(x,y) is close to the fractional part of f(x+1,y), and also close to the fractional part of f(x,y+1). In other words - and here's where the calculus begins - the partial derivatives of f with respect to x and y are both integers at the centre of each butterfly. (Well, actually they're integer multiples of the reciprocal of the inter-pixel spacing; but it obscures the essence of the mathematics to have to keep remembering about the inconvenient constants. Putting the correct constants back in is left as an exercise for the reader :-)

This also suggests that if we plot the lines along which the partial derivatives df/dx and df/dy are equal to an integer and a half, we might well find ourselves drawing a set of lines that precisely mark the divisions between the butterflies. And it's true: we get the following picture. (The partial derivatives in x and y are 16*x^3-34*x*y^2 and 16*y^3-34*y*x^2 respectively. Black lines mark contours of df/dx; red lines mark contours of df/dy.)

(Notice in the above graph that the contours of the derivatives have a three-fold symmetry. These three-way symmetric curves can clearly be seen by following the lines of butterflies in the original image; at first sight they seem a bit odd because the function being plotted is four-way symmetric, right? But it does make sense: the positions of the butterflies depend on the derivatives of the degree-4 polynomial we started with, which are degree-3 polynomials and can therefore indeed be expected to be three-way symmetric.)

Now we're getting closer. With the above piece of analysis to help us, we can isolate each butterfly and treat it separately.

For a moment, let's pretend this whole thing is only happening in one dimension, instead of two. Consider the situation at the centre: the value of f itself varies very little between pixels, so computing the halfway point between two pixels will produce a value that still fits in sensibly with the ones around it. No problem.

Now consider the situation in a butterfly region. The difference in f between two adjacent pixels is close to an integer, let's say a. So f(x+1)=f(x)+a+e, where e is the error term. Therefore, we would expect the halfway point to be f(x)+a/2+e', where e' is comparable to e. More generally, f(x+b) (where b is between 0 and 1) can be expected to be f(x)+ab+e(b). So this gives what seems like a sensible way to plot a point whose coordinates are fractional. To plot the point at x+b, compute the nearest integer g to the partial derivative at x; then compute f(x+b) as normal, but subtract b*g before taking the fractional part.

And this works! Returning to two dimensions, it still works. Every clearly defined butterfly in the original image holds together when viewed at higher resolution. Let's enlarge the image above by a factor of two to prove it:

To summarise, the algorithm for enlarging the image is as follows.

• For each pixel (X,Y) in the enlarged image, convert its coordinates to coordinates (x,y) in the original image. Save the fractional part (xf,yf) of each resulting coordinate.
• Compute the partial derivatives (fx,fy) of the function at the point (x,y), rounded to the nearest integer.
• Compute the value of the function f(x,y). Subtract the product of each partial derivative with the fractional part of the corresponding coordinate, to get f(x,y)-fx*xf-fy*yf.
• Take the fractional part of that, and convert it into a pixel colour.

Metamorphosis

After doing all of this, I made a further discovery. The original function x^2*y^2, and the replacement (2x+y)(2x-y)(x+2y)(x-2y) that I then switched to, are both products of real linear factors. What happens, I wonder, when you try using a polynomial without real factors?

So I tried it, of course. I replaced the function (2x+y)(2x-y)(x+2y)(x-2y) with the alternative function (2x+iy)(2x-iy)(x+2iy)(x-2iy) (which of course multiplies out to a real polynomial, since the factors come in conjugate pairs). The result was qualitatively different from the other images:

Suddenly we're getting circle shapes instead of butterfly shapes! In retrospect, this makes reasonable sense: you get a circle shape when the function is locally shaped like a paraboloid - curving upwards on all sides, or downwards on all sides - and a butterfly shape when the function is locally saddle-shaped, curving upwards in one direction and downwards in the perpendicular direction. By choosing polynomials with real factors, it seems I inadvertently also chose functions which were saddle-shaped everywhere.

This is very nice; what happens when we try a function with some real factors? So I tried the polynomial y(2x-iy)(2x+iy) ... and this happened.

Isn't that something? Butterflies in parts of the plot, circles in other parts - and some really fun things, like small fish shapes, happening where the two meet.

We can work out which type of feature we expect to see in which parts of the plane, by applying a bit more calculus: given a twice partially differentiable function f(x,y), a few hours of intense thought will tell you that the double partial derivatives can be combined into the formula (d2f/dxdy)^2 - (d2f/dx2)(d2f/dy2), and that this is greater than zero in saddle-shaped regions and less than zero in circle-shaped regions. (Also, this formula only varies by a positive constant factor when you change the axes on the diagram, so it's a genuine reliable way to tell.) But this doesn't seem to help with the pretty pictures - it just gives us a useful tool to analyse them with.

Synthesis

So that's the heavy-duty maths over with. We're now able to take the original simple fractionalpart(f(x,y)) plots, and enhance them into high-resolution images that can be fed to a seriously high quality printer to generate eye-twisting posters. But that isn't the end of it: some of the by-products of the algorithm above can be used to produce some more fun effects.

In particular, when the partial derivatives above are rounded to the nearest integer, it's instructive to note the amount by which each derivative had to change when rounded. This will be close to zero (in both directions) at the centre of each butterfly, close to one-half (in both directions) at the corner between four butterflies, and close to one-half (in only one direction) on the edge between two butterflies. So we could take the maximum of the fractional part of each partial derivative and use it to fade the butterflies out at the edges:

Also, keeping the integer parts of the partial derivatives provides a good way to differentiate one butterfly from the next by changing the colour. Here's what happens if we colour each butterfly purple or green depending on whether the sum of the integer parts of the partial derivatives is even or odd (this looks a bit strange unless the fading effect is used at the same time):

Catalysis

In case you want to try doing some of these for yourself, a program to generate filigrams is available for download here. The program is provided as C source code - you'll need a C compiler in order to use it. For Windows users, Borland provide a C compiler for free-of-charge download, on their web site at www.borland.com.

The program produces its output as Windows 24-bit .BMP files. Most image processing software should be able to convert these to other formats for you.

Here's a selection of sample command lines you might like to try:

• filigram -o cross.bmp -s 640x512 -I 0.03125 -p 4x4-17x2y2+4y4 -x 10 -O 0.015625
  This one is the "standard" image that I've been using as an example in the above discussion.
• filigram -o accident.bmp -s 640x512 -I 0.025 -p x2y2 -x 8
  This one is the original image that I generated by accident.
• filigram -o circles.bmp -s 640x512 -I 0.025 -p x2+y2 -x 8 -O 4
  This is the pattern of interlocking circles that I was trying to generate when I created the above accident. The formula is so similar that the same program will generate it!
• filigram -o complex.bmp -s 640x512 -I 0.03125 -p 4x4+17x2y2+4y4 -x 10 -O 0.015625
  This is the image with circle shapes instead of butterflies, created using a polynomial with no real linear factors. The parameters are exactly the same as the ones for cross.bmp above, except for one crucial plus sign replacing a minus sign in the polynomial.
• filigram -o fish.bmp -s 640x512 -I 0.03125 -p 4x2y+y3 -x 10 -O 0.5
  This is the image with some circle shapes, some butterflies, and strange fish shapes where the two meet. This one behaves interestingly when separate regions are coloured differently: it turns out that the "head" and the "tail" of each fish shape are not separate regions as far as the partial derivatives are concerned, but are actually one combined feature.

To add colour effects to any of the above pictures, try putting these extra options on the end of the command line:

• -f -c 0.7,0,1:0,0.63,0
  This gives a purple-and-green checkerboard effect.
• -f -c 2+0.61,0.0,0.0:0.48,0.0,0.56:0.82,0.64,0.0:0.0,0.7,0.0
  This gives coloured stripes across the images, in jewel colours.
• -f -c 1,0,0:1,1,0:0,1,0:0,1,1:0,0,1:1,0,1
  This gives a diagonal rainbow stripe effect.
• -f -c 1,1,1:0,0,0
  This causes half the features in the picture to turn black and disappear completely! Perhaps it might help spice up an otherwise boring picture...
• -f -c 0,0.4,1:0,0.7,0.5
  This gives a combination of sea-blue and sea-green which might go will with the shapes in fish.bmp :-)

To generate a bigger version of any of those images, change the image size specification after the "-s" option.

Here are a few bigger (800x600) images I generated myself. All these are in JPEG format, and each is about 100Kb.
[checkers] [rainbow] [jewels] [wormhole] [deepsea]