Search the FAQ Archives

3 - A - B - C - D - E - F - G - H - I - J - K - L - M
N - O - P - Q - R - S - T - U - V - W - X - Y - Z
faqs.org - Internet FAQ Archives

Fractal Frequently Asked Questions and Answers
Section - Iterated function systems and compression

( Single Page )
[ Usenet FAQs | Web FAQs | Documents | RFC Index | Restaurant inspections ]


Top Document: Fractal Frequently Asked Questions and Answers
Previous Document: Feigenbaum's constant
Next Document: Chaotic demonstrations
See reader questions & answers on this topic! - Help others by sharing your knowledge
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 .  
  
Frank Rousells hyperindex of clickable/retrievable IFS images:  
ftp://ftp.cnam.fr/pub/Fractals/ifs/Index.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: ftp://rtfm.mit.edu/pub/usenet/  
[18.181.0.24].  
  
Three 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.  
.  
3. Y. Fisher (Ed), _Fractal Image Compression: Theory and Application_.  
Springer Verlag, 1995.  
  
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: ftp://lyapunov.ucsd.edu/pub/ .  
  
A site with information on fractal compression is  
ftp://legendre.ucsd.edu/pub/Research/ . On the WWW you can access  
file://legendre.ucsd.edu/pub/Research/Fisher/fractal.html .  
  
Many fractal image compression papers are available from  
ftp.informatik.uni-freiburg.de:/documents/papers/fractal [132.230.150.1].  
A review of the literature is in Guide.ps.gz. See the README 
file for an overview of the available documents.  
  
Other references:  
  
http://dip1.ee.uct.ac.za/fractal.bib.html "Fractal Compression  
Bibliography"   
  
http://inls.ucsd.edu/y/Fractals/ Fractal Compression (Yuval Fisher )   
  

User Contributions:

Comment about this article, ask questions, or add new information about this topic:

CAPTCHA




Top Document: Fractal Frequently Asked Questions and Answers
Previous Document: Feigenbaum's constant
Next Document: Chaotic demonstrations

Single Page

[ Usenet FAQs | Web FAQs | Documents | RFC Index ]

Send corrections/additions to the FAQ Maintainer:
stepp@marshall.edu





Last Update March 27 2014 @ 02:11 PM