Fractal Image Compression

by Henk Nieland

---

The explosive increase in possibilities of electronic data processing has induced a corresponding need for fast transmission of images. Without compression the transmission is far too slow and even current compression techniques should be improved where possible, because this can lead to further savings in communication time (and thus in money) and reduce the load on a network (WWW is an obvious example). Fractal image compression is a promising, relatively new technique, in which CWI started research in 1996.

Decompressing an image encoded by fractals.

Whereas a standard method like JPEG can compress images with a factor up to 20, with fractal techniques a compression factor of 100 may be reached, depending on the features of the original image. (On the average a factor of 35 seems feasible.) The method, proposed in the eighties by Michael Barnsley, is based on the observation that fractals can generate deceptively realistic images. Then, conversely, it should be possible to store any natural image in the form of just a few basic fractal patterns, together with the prescription how to restore the image. Starting from a group of pixels of the original image one searches the image for similar groups of pixels which can be mapped more or less on the first group. The compressed image consists of the 'code book' of all these mappings. Fractal image compression is a lossy method, ie, information is lost during the process, which is no problem for applications like moving images. Images can be restored to any desired resolution, but compression is time-consuming. Hence, the method is well-suited for, eg, presenting images on Internet. CWI addresses several unsolved mathematical questions, including a precise definition of 'more or less similar' images (mathematical modelling of human criteria) and statistical aspects of the method.

More information at http://www.cwi.nl/cwi/projects/fractals/index.html

Please contact:
Mike Keane or Ben Schouten - CWI
Tel: +31 20 592 4050/4170
E-mail: {keane,bens}@cwi.nl