The study of fractals arising as attractors of IFS's became an area of possibly extreme practical importance thanks to Mandelbrot's fundamental insight that the prevailing shapes of nature resemble self-similar fractals and Barnsley's insight that it is possible to begin with the shape and determine a dynamical system whose attractor looks like the shape. This is called Inverse Problem of fractal geometry: to begin with the fractal and find the iterated function system or other dynamical system that converges onto that fractal. A typical picture might require on a pixel-by-pixel basis more than 500,000 bytes (or characters) of data to store. Imagine though that we might find an IFS whose attractor is the picture. Even a fairly complicated IFS consumes only a few thousand characters to write down. Thus, it consumes far less space to record the IFS than the original picture; this is called Image Compression. To decompress the picture, we apply the Random Iteration Method to the stored IFS to rapidly generate the picture.
How do we find the IFS associated to an image? The key ingredient in
Barnsley's approach is the Collage Theorem (see
[Bar93] Theorem III.10.1). Suppose we have a particular
fractal-ly compact set L that we wish to encode as the attractor of
an IFS. Then we examine the set and try to discover parts of it that
might resemble the whole set. That is, we find contractions
such that each 
is approximately a small piece
of L. The union of all these pieces should be approximately L.
The key question here is what exactly do we mean by approximately? To answer that we turn to the notion of Hausdorff distance that we labored upon earlier. We ask that
be small. Let s<1 be a contractivity factor for the IFS
. We have seen there is certainly an attractor A
associated to this IFS. Barnsley's theorem says
The Collage Theorem:If s<.5, for instance, then.
. Then the
attractor is almost as good an approximation of L as the original
``collage'' (choice of w's). The best possible situation is when s
is as small as possible. To arrange that s is very small may require
using many linear maps 
each representing a small piece of L.
Thus, there is a trade-off between accuracy of the attractor and size
of the IFS used to represent L.
All this smacks of engineering, and indeed Barnsley and associates founded a company, Iterated Systems, Inc., to develop the application of IFS theory to image and video compression. Some results of their compression and decompression algorithms are shown in Plates 42-45 in [Bar93]. Even before that, it was recognized that variations of the IFS method of generating fractals could produce far more realistic images of natural landscapes than any human hand. Artificial fractal landscapes first appeared in Star Trek II: The Wrath of Khan (the Genesis project video) and have since become a standard aspect of science fiction and fantasy film-making. Some Web resources on all of this are listed below.
To end this chapter, we will carry out only a few exercises in finding the IFS associated to an image. Suppose we have the picture of the fern to begin with. There is a clear pattern of fronds on either side of the main stem marching off to the tip. Thus, if we omit the first fronds on the left and right of the main stem, we see a smaller version of the whole fern. On the other hand, the first side fronds themselves are even smaller versions of the whole fern. In this figure, we mark triangles on these parts which are similar to the whole. The only remaining part we must account for is the piece of the main stem not contained in these three parts. That is also marked in blue in the figure.
Figure 51: Dissection of the fern into similar parts.
An affine map w depends on six real parameters a,b,c,d,e,f.
Suppose we have six points 
, 
,
, 
, 
, 
.
Then the equations
amount to six linear equations in the six unknowns a,b,c,d,e,f.
If the three points 
do not lie on a single line, these
equations always have a unique solution. Thus, affine maps are
determined by how they map a single triangle. This allows us to
convert out dissection of the fern into four affine maps. In
this figure, we show the
original four parts in red together with a triangle corresponding to
the whole fern in blue.
Figure 52: Mapping triangles for the fern
After carefully measuring the coordinates of the vertices of these
triangles, we may solve for the four affine maps , j=1,2,3,4.
To help with these calculations, we wrote some programs for computing affine maps in MAPLE. You can retrieve worksheets containing these programs at
For our next example, we will try to codify a famous
piece of Japanese art, The Great Wave Off Kanagawa
from the ``Thirty-six Views of Mount Fuji'' (1823-29) by
Katsushika Hokusai.
This color woodcut of a great
tsunami with Mount Fuji in the background shows an
amazing feel for the self-similarity of natural
phenomena. The whole picture is shown here.
Figure 53: The Great Wave Off Kanagawa
We want to concentrate on the wave crest shown in this figure. The wave overall has a crescent shape that is similar to the smaller crescents appearing throughout. We have superimposed a large blue triangle and three smaller red triangles as a first guess at designing an IFS associated with the image.
Figure 54: The crest of the Great Wave and self-similar pieces
We next measure the coordinates of the vertices of these triangles as closely as possible, and compute the affine maps that send the blue triangle onto each of the three red triangles. Then all that remains is to compute the attractor of this IFS. Using the MAPLE routines in the worksheet mentioned above, we arrive at this picture. The results are a bit laughable at this point. Clearly, we made visually based choices of the linear maps. Perhaps, we should tinker with these choices to more accurately reproduce the crest. By hand, this requires a bit of artistry; Barnsley's company Iterated Systems is founded on replacing this artistry with detailed algorithms. We hope this example gives the reader a taste of the possibilities of encoding images by means of an IFS.
Figure 55: The attractor of our Great Wave IFS
One interesting question that we shall only mention is what happens when the parameters of the IFS are continuously varied. Barnsley proves that the fractal attractor also varies continuously with respect to the Hausdorff metric. With the right changing of parameters, we can simulate a fern ``blowing in the wind,'' to use Barnsley's colorful terminology ([Bar93], Chapter III, Section 11). Some beautiful animations of the changing attractors of varying IFS's may be found in Devaney's pages on ``Chaos in the Classroom.'' Procure a QuickTime movie viewer, and don't miss these animations.
Animations of changing IFS's: Click to the ``Rotations and Animations'' section. The actual movies are:
- Rotating crosses: How many affine maps do these IFS's have?
- Rotating crosses 2: Another version.
- One rotating cross ad infinitum
- One rotating cross 2: Another version.
- Discombobulating Sierpiński triangle