I’m studying for a Digital Video Coding and Compression exam, and just wanted to share the coolness that is fractal coding.

Fractals are geometric objects which are said to have infinite complexity, and are often self-similar (that is, a small portion of the fractal is the same as the whole fractal). Iterated Function Systems (IFS) are one kind of fractal. An example is the Sierpinski gasket. Zoom into any of the sub-triangles, and they look just like the original.

It’s formed by making three ‘copies’ of an original image (it doesn’t matter what the image is), and placing them in the shape of a triangle; one above, one bottom-left, one bottom-right. Repeat an infinite number of times:

The same process, with an altered replication pattern, can be applied to form other shapes, such as a fern leaf (which uses 4 copies of the previous iteration’s image: One thin one for the stem, two rotated shrunk ones for the fronds coming off the sides, and one for the rest of the fern). Such patterns are often observed in nature, which makes fractals particularly interesting.

Fractal image coding applies a similar concept. Parts of the image are used to build up other parts (imagine an image of a tree; A bit of a branch is copied and shrunk, to form the image of a smaller branch coming off the first one). This process of searching for similar parts within the image, and using them to form the current part, is repeated over the whole image.

To reconstruct the image, the same process as generating the Sierpinski gasket is used: Bits of the starting pattern (which, amazingly, can be anything) are copied, scaled, coloured and rotated, as instructed by the encoding process. The whole process is repeated until the image is built:

Oh, it’s such black magic.

Unfortunately, the whole process is incredibly slow, because so much searching is required during the encoding process (Looking for that branch part that looks like the current part of the image being encoded). It also doesn’t quite give enough performance to make the extra work worthwhile. Still, it definitely performs well in some circumstances; maybe it will make a comeback when we have faster computers.

NB. Most of the images are nicked shamelessly from Dr. Tim Ferguson’s lecture notes on fractal coding, from CSE5302. Also, for further reading, Mirsad suggested this paper: A Review of the Fractal Image Coding Literature, by Brendt Wohlberg and Gehard de Jager.