FRACTAL, page 13 of 36, hit 002'170

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.

Interactive IFS Playground (Otmar Lendl)

http://www.cosy.sbg.ac.at/rec/ifs/

Frank Rousell's hyperindex of IFS images

http://www.cnam.fr/fractals/ifs.html

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:

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

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

4. Y. Fisher (Ed), Fractal Image Compression: Theory and Application.

Springer Verlag, 1995.

5. 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:

1. The October 1993 issue of Byte discussed fractal compression. You can

ftp sample code: ftp://ftp.uu.net/published/byte/93oct/fractal.exe .

2. A Better Way to Compress Images," M.F. Barnsley and A.D. Sloan, BYTE,

pp. 215-223, January 1988.

3. "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)

4. A. E. Jacquin, Image Coding Based on a Fractal Theory of Iterated

Contractive Image Transformation, IEEE Transactions on Image Processing,

January 1992.

5. 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.html

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