Iterated function systems and compression

Q11a: What is an iterated function system (IFS)?
A11a: If a fractal is self-similar, you can specify mappings that map the
whole onto the parts.  Iteration of these mappings will result in convergence
to the fractal attractor.  An IFS consists of a collection of these (usually
affine) mappings.  If a fractal can be described by a small number of
mappings, the IFS is a very compact description of the fractal.  An iterated
function system is By taking a point and repeatedly applying these mappings
you end up with a collection of points on the fractal.  In other words,
instead of a single mapping x -> F(x), there is a collection of (usually
affine) mappings, and random selection chooses which mapping is used.

For instance, the Sierpinski triangle can be decomposed into three self-
similar subtriangles.  The three contractive mappings from the full triangle
onto the subtriangles forms an IFS.  These mappings will be of the form
"shrink by half and move to the top, left, or right".

Iterated function systems can be used to make things such as fractal ferns and
trees and are also used in fractal image compression.  _Fractals Everywhere_
by Barnsley is mostly about iterated function systems.

The simplest algorithm to display an IFS is to pick a starting point, randomly
select one of the mappings, apply it to generate a new point, plot the new
point, and repeat with the new point.  The displayed points will rapidly
converge to the attractor of the IFS.

An IFS fractal fern can be viewed on the WWW at
gopher://life.anu.edu.au:70/I9/.WWW/complex_systems/fern.gif .

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,
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
[18.70.0.209].

Two books describing fractal image compression are:

1.  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.

2.  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.

The October 1993 issue of Byte discussed fractal compression.  You can ftp
sample code: ftp.uu.net:/published/byte/93oct/fractal.exe .

An introductory paper is:

1.  A. E. Jacquin, Image Coding Based on a Fractal Theory of Iterated
Contractive Image Transformation, _IEEE Transactions on Image Processing_,
January 1992.

A fractal decompression demo program is available by anonymous ftp:
lyapunov.ucsd.edu:/pub/inls-ucsd/fractal-2.0 [132.239.86.10].

Another MS-DOS compression demonstration program is available by anonymous
ftp: lyapunov.ucsd.edu:/pub/young-fractal .