Fractal Compression

Q11b: What is the state of fractal compression?

A11b: Fractal compression is quite controversial, with some people claiming it doesn't work well, and others claiming it works wonderfully. The basic idea behind fractal image compression is to express the image as an iterated function system (IFS). The image can then be displayed quickly and zooming will generate infinite levels of (synthetic) fractal detail. The problem is how to efficiently generate the IFS from the image. Barnsley, who invented fractal image compression, has a patent on fractal compression techniques (4,941,193). Barnsley's company, Iterated Systems Inc (http://www.iterated.com/), has a line of products including a Windows viewer, compressor, magnifier program, and hardware assist board.

Fractal compression is covered in detail in the comp.compression FAQ file (See "compression-FAQ"). ftp://rtfm.mit.edu/pub/usenet/comp.compression .

One of the best online references for Fractal Compress is Yuval Fisher's Fractal Image Encoding page (http://inls.ucsd.edu/y/Fractals/) at the Institute for Nonlinear Science, University for California, San Diego. It includes references to papers, other WWW sites, software, and books about Fractal Compression.

Three major research projects include:

Waterloo Montreal Verona Fractal Research Initiative: http://links.uwaterloo.ca/
Groupe FRACTALES: http://www-syntim.inria.fr/fractales/
Bath Scalable Video Software Mk 2: http://dmsun4.bath.ac.uk/bsv-mk2/

Several books describing fractal image compression are:

M. Barnsley, Fractals Everywhere, Academic Press Inc., 1988. ISBN 0-12-079062-9. This is an excellent text book on fractals. This is probably the best book for learning about the math underpinning fractals. It is also a good source for new fractal types.
M. Barnsley and L. Anson, The Fractal Transform, Jones and Bartlett, April, 1993. ISBN 0-86720-218-1. Without assuming a great deal of technical knowledge, the authors explain the workings of the Fractal Transform(TM).
M. Barnsley and L. Hurd, Fractal Image Compression, Jones and Bartlett. ISBN 0-86720-457-5. This book explores the science of the fractal transform in depth. The authors begin with a foundation in information theory and present the technical background for fractal image compression. In so doing, they explain the detailed workings of the fractal transform. Algorithms are illustrated using source code in C.
Y. Fisher (Ed), Fractal Image Compression: Theory and Application. Springer Verlag, 1995.
Y. Fisher (Ed), Fractal Image Encoding and Analysis: A NATO ASI Series Book, Springer Verlag, New York, 1996 contains the proceedings of the Fractal Image Encoding and Analysis Advanced Study Institute held in Trondheim, Norway July 8-17, 1995. The book is currently being produced.

Some introductary articles about fractal compression:

The October 1993 issue of Byte discussed fractal compression. You can ftp sample code: ftp://ftp.uu.net/published/byte/93oct/fractal.exe .
A Better Way to Compress Images," M.F. Barnsley and A.D. Sloan, BYTE, pp. 215-223, January 1988.
"Fractal Image Compression," M.F. Barnsley, Notices of the American Mathematical Society, pp. 657-662, June 1996. (http://www.ams.org/publications/notices/199606/barnsley.html)
A. E. Jacquin, Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformation, IEEE Transactions on Image Processing, January 1992.
A "Hitchhiker's Guide to Fractal Compression" For Beginners by E.R. Vrscay
ftp://links.uwaterloo.ca/pub/Fractals/Papers/Waterloo/vr95.ps.gz

Andreas Kassler wrote a Fractal Image Compression with WINDOWS package for a Fractal Compression thesis. It is available at http://www-vs.informatik.uni-ulm.de/Mitarbeiter/Kassler/papers.htm

Other references:

Fractal Compression Bibliography: http://www.dip.ee.uct.ac.za/imageproc/compression/fractal/fractal.bib.html
Fractal Video Compression: http://inls.ucsd.edu/y/Fractals/Video/fracvideo.html
Many fractal image compression papers are available from: ftp://ftp.informatik.uni-freiburg.de/documents/papers/fractal
A review of the literature is in Guide.ps.gz.: ftp://ftp.informatik.uni-freiburg.de/documents/papers/fractal/README