What is an Iterated Function System?

Mandelbrot had observed that complex images could be obtained from simple formulas. Given a formula, it is relatively easy to derive the corresponding image. Barnsley had the idea of going in the other direction, from the image to the formula. When this is possible, it can result in fantastic compression ratios. Instead of representing the image as a long sequence of pixel values, the image can be reconstructed from a formula, which can be encoded in a much smaller number of bytes. Let’s take an example which is not one of fractal compression but which can convey the right idea.

Assume that you want to represent a black and white image consisting of a black circular disk on a white background. For an image of a given resolution (a given number of pixels in the horizontal and vertical dimensions), you can enumerate all the pixels which are inside the disk. Alternatively, you can give an equation for the disk, specifying it as the set of points (x, y) which satisfy:

(x-a)2+ (y-b)2 < r2

where r is the radius of the disk and (a, b) its center. This equation is sufficient to reconstruct the image of the disk. Moreover, the image can be reconstructed at any resolution—this would not be true for an explicit list of pixels. A similar difference exists between scalable character fonts (TrueType fonts in Microsoft Windows) and fonts that are made of a fixed number of pixels. Each character in a scalable font is described by a formula for drawing the character; a character in a fixed font is just a set of pixels.

Unfortunately, real-world images almost never let themselves be represented as such simple equations. Given an image, it is generally impossible to find a simple formula representing the image exactly. Barnsley’s idea was to take advantage of the self-similarity present in an image to find an approximate representation of the image as a fractal, like Mandelbrot’s fractals which exhibit self-similarity at different scales. Also, instead of giving an explicit equation satisfied by all points of the image, the fractal is implicitly defined as the fixed-point solution of an Iterated Function System. The theory of IFS is outside the scope of this book, so we will only mention very briefly some of the mathematics involved without giving precise definitions.

Basic IFS mathematics

A mapping from a set to itself is said to be contractive if it reduces the distances: the distance between f(x) and f(y) is smaller than the distance between x and y. For example, the function f(x) = x/2 defined on the set of real numbers is contractive. The Contractive Mapping theorem states, in short, that a contractive mapping has a unique fixed point, that is, a value x such as f(x) = x. Moreover, the fixed point can be obtained by starting from any point x₀ and computing the sequence:

x1= f(x0)
x2= f(x1) = f(f(x0))
etc...

The sequence converges to the unique fixed point. For example, starting with the value x₀= 1 and applying the function f(x) = x/2 iteratively, we get the sequence 1, 1/2, 1/4, 1/8, etc... which converges to the value 0. The example was given in the set |R of the reals, but the Contractive Mapping theorem also applies to higher dimensions, in particular for two dimensional images.

An Iterated Function System consists of a finite set of contractive mappings w₁... w_N on the plane |R². The IFS can be applied to a black and white image as follows. Each (black) point x of the image is mapped to N points w₁(x) ... w_N(x). The union of all the resulting points forms itself another black and white image. So the IFS transforms an image into another image. Hutchinson proved that in some well defined sense, the IFS is itself a contractive mapping, and thus it has a unique fixed point within the set of all black and white images. So by starting from an arbitrary image and applying the IFS iteratively, the process converges to a unique image which depends only on the IFS and not on the initial image.

This is in essence how fractal decompression works. The decompressor need only know the description of the IFS, and can reconstruct an image from this. The method works regardless of the exact form of the IFS, as long as it is contractive. The IFS can be viewed as a special copy machine which creates N reduced copies of the input image, and pastes them together. The copies are reduced since each w_i is contractive. By feeding the output of this copying machine into itself in a feedback loop, the images generated at each step get closer and closer to each other and the process converges to the unique fixed-point image, also called the attractor of the IFS.

The resulting image is a fractal, since it contains reduced copies of itself at every scale. More detail can be seen if we zoom on a portion of the image. Because of this self-similarity property, image compression using IFS deserves the name of fractal image compression.

We have only mentioned black and white images so far, but the theory can be extended to grayscale images. Color images can themselves be encoded as three grayscale images, one for each of the red, green, and blue components (just like the JPEG algorithm does).

Up to now, we have only considered the decompression process. The compression process is to find a good IFS for a given image. This is known in the fractal compression literature as “the inverse problem.” This problem is vastly more complicated than the decompression process.