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
