The Mathematics of Image Compression

The fundamental notions underlying fractals were known to mathematicians last century, but it was the advent of powerful computers that made exploration of fractals a practical reality. Fractals initially gained popularity as the subjects of striking and sometimes hauntingly beautiful computer-generated images. Today researchers are putting fractals to work for practical uses.

The basic idea behind fractals is that of "iteration"---repeating an operation over and over. Given a mathematical function, one can apply it repeatedly, producing what is known as an "iterated function system." Programming a computer to plot a two-dimensional picture of this iteration process is how one produces a picture of a fractal. At the initial stages, when only a few repetitions have been carried out, the picture can look like a smattering of random dots. But eventually---it may take thousands or millions of iterations---a clearly defined shape emerges. Different functions will produce different pictures.

Fractal image compression exploits the power of iterated function systems to produce highly complex, detailed images. Given a photo or other image you would like to compress, the idea is to find a mathematical function that, when you iterate it, gives you a picture that is a close approximation to the original image. Storing only information about the function takes up much less computer memory than storing information about the lightness and darkness of every pixel in the original image. The image can be "uncompressed" by iterating the function until the picture reappears.

The article "Fractal Image Compression, " by Michael F. Barnsley, in the June 1996 issue of Notices of the AMS, lays out the mathematical theory behind this important practical development.

-Allyn Jackson