Iterated Function Systems

I became, like many, interested in fractals and computer image generation
after reading Chaos, James Gleick's 1987 popular science classic.
One part of that book that really caught my attention was connected with the
picture shown at right. This image of a fern leaf was generated using Michael
Barnsley's method of **iterated function systems**. What was so amazing
about this was that despite the manifest complexity and detail of the image, a
natural shape, it took only a few parameters to specify it -- just 4 sets of
six real numbers, 24 all together, to 2 digits of precision. 48 decimal
digits: 160 bits.

Here, I thought, was something quite amazing. Perhaps equally remarkable was
the way that the numbers were used to generate the image, which seemed almost
like magic. Each set of 6 numbers specifies a function known as an affine
transformation from the plane to the plane. Such a function takes points in
the plane (or shapes, which are sets of points) and maps them to rotated,
skewed, translated versions of themselves. (Technically, it consists of a
linear transformation plus an added translation.) To generate the image, one
picks any point close to the origin and randomly applies one of the six
transformations to it. The result is plotted, and then another randomly
chosen transformation is applied to this point, that result is plotted, and so
on. (This is the origin of the name iterated function system.) Somehow, from
this sequence of random choices, the image-pattern emerges, independent of
which point is started from, or what sequence of choices is made.

Before I learned anything further about how (and why) this actually works, I
wondered what would happen if instead of using Barnsley's fern leaf
parameters, you substituted in ones that had been generated randomly. My
(faulty) reasoning was that the IFS technique mapped a small space of
parameters onto a much larger space of images, and since the result in one
case was known to be aesthetically interesting, there was reason to suspect
that the subspace mapped onto consisted *entirely* of interesting
images. With breathless anticipation I watched as my old 8086 IBM clone
ground out the points of my first experiments in this area -- which turned out
to be utterly disapppointing random collections of dots and lines.

Undeterred (and spurred on by my younger brother's derisive reaction to my
attempts), I went back and learned a little more about how iterated function
systems worked and used this insight to constrain the random parameter
generation a little bit. The results (see examples below), were quite
rewarding. It *is* possible to generate pleasing abstract shapes via
random parameter generation, the characteristics of which depend on the
constraints employed. Also, by slightly modifying the parameters for a given
shape, one can obtain interesting variations of it (the two images in second
row are distortions of Barnsley's fern).

What are these images? Plants? Clouds? Snowflakes? They seem to define an entire realm of quasi-natural shapes. Almost every new image is a pleasant surprise.

The images were generated by a program I've written
called *randim*, which affords interactive
control over the parameter selection process. (Some more recent images, with
color: one two and three. Screenshots of the
program itself in action here.) You can download
this program if you want (HTTP). It is written in C using X
Windows and should work on most workstations with minor adjustments at most.
All I ask is that you don't sell the program or one based on it for money, and
you send me the code for any cool modifications you do (email: *arobert at
interstitiality ddot net*). Thanks!

A technical explanation of how iterated function systems work (along with a brief description of my randomization constraint methods) can be found here.

A clearer and more rigorous explanation can be found in Barnsley's excellent book, Fractals Everywhere, cited below.

Practically, iterated function systems have been applied to image compression and font generation, and theoretically they have relations to dynamical systems and neural networks. Personally, I think there is much more that remains to be said about them. I continue to be amazed at the sheer variety of patterns that can be generated via random parameter selection. Somehow the mathematical structure of the IFS technique opens the connection between randomness and regularity, chaos and order, the absence of symmetry and its presence - that appears to be a central aspect of natural beauty.

- Barnsley, M.F. (1988); Fractals Everywhere.
- Barnsley, M.F., Hurd, L. P. (1993); Fractal Image Compression.
- Ip, H.S., Wong, H.T.F., Mong, F.Y. (1994); "Fractal Coding of Chinese Scalable Calligraphic Fonts" in Computers and Graphics 18:343-51.
- Stark, Jaroslav (1991); "Iterated Function Systems as Neural Networks" in Neural Networks 4:679-90.

- The web site of Scott Draves, another practitioner of the mathematical arts.
- Information on Fractint, a good freeware fractal generation program for PC or Xwindows.
- For a more practical bent on things, check out this site, with links relating to using Fractal properties to compress images and other data.

Back to Adrian's home page.