Fractals and IFS Page A1 of 5. Updated 17 Dec 00.

~~~~~~~~~~~~ < 0 > ~~~~~~~~~~~~

Benoit Mandelbrot, the father of fractal geometry once said (in 1983):

clouds are not spheres, mountains are not cones,
coastlines are not circles, and bark is not smooth,
nor does lightning travel in a straight line . . .

Michael Barnsley, the inventor (with Demko) of Iterated Function Systems, states near the beginning of his book Fractals Everwhere (1988):

Fractal geometry will make you see everything differently. There is danger in reading further. You risk the loss of your childhood vision of clouds, forests, galaxies, leaves, feathers, flowers, rocks, mountains, torrents of water, carpets, bricks, much else besides. Never again will your interpretation of these things be quite the same.

Niels Bohr:

"Prediction is difficult, especially the future."

~~~~~~~~~~~~ < 0 > ~~~~~~~~~~~~

Take another look at the logo leaf at top: you are looking at a fractal (built out of seven rectangles!). Soon, all will be revealed! For more detail about that image, visit the Big logo page.

~~~~~~~~~~~~ < 0 > ~~~~~~~~~~~~

Overview of this Page:

On this page I provide an introduction to Fractal Geometry and an outgrowth of it, Iterated Function Systems (IFS), and links to the following:

(a) descriptions and essays, including applications to fields such as data compression, pattern recognition, movie making, music, heart rythms, cancer diagnosis, how a cruise missle navigates, and the stock market;

(b) more detailed mathematics than you might ever wish to see (but there is no test at the end!);

(c) images produced by others using these techniques; and,

(d) links to the application of IFS theory that pertain to the development of my ConjPic computer program.

This Page consists of Pages A1 to A5, each of which consists of several pages. Sections 1 to 9 are included in Pages A1 and A2. Section Web 10 is included in Pages A3 to A5.

Go Home .

Page contents

Introduction to Fractals and Iterated Function Systems

. . . 1. Introduction

. . . 2. Generation of Complex Shapes from Simple Ones

. . . 3. Data Compression

. . . 4. Pattern Recognition

. . . 5. HDTV

. . . 6. Movies & "Live" TV

. . . 7. Music

. . . 8. Stock Market

. . . 9. Database Access via Fractal Compression

. . . 10. Web Sites in general

. . . 11. Web sites involving fractals in medical research

Introduction to Fractals and Iterated Function Systems

By Wayne Paulson C:\IFS\Intro.doc  12-May-98, updated Dec-00

1. Introduction

The complexity and beauty of information that can be generated from seemingly simple mathematical formulas, as exemplified in the mathematics of fractal geometry and iterated function systems, is a marvel to behold. That information could relate to visual images, music, the stock market, the electrical activity of the heart, the structure of our lungs and blood-vessel systems, river beds, clouds, mountains, the structure of a fern or pine tree, and colourful whorls of abstract images and sounds. In concordance with this mathematical ability, which we have only gained in our generation, there are fractals all around us, built by natural processes -- processes that at times seem to be so elegantly deterministic, and at other times, so carefree and chaotic! 

The term "fractal" was coined by the mathematician Benoit B. Mandelbrot (born 1924), as detailed in his marvelous book The Fractal Geometry of Nature (1977), based on the Latin adjective fractus. (For a biography, click on http://pconf.terminal.cz/participants/mandelbrot.html [Web site Web 1070 below]). The corresponding Latin verb frangere means "to break": to create irregular fragments. Fractal designates the property of self-similarity at different scales of size. Consider, for example, as a fragment, the branch of a tree. Consider now, as a fragment of that fragment, a branch of the branch. Does it not look like the branch itself? Now, for the branch on the branch on the branch . . .

Such forms as are provided in nature with such abundance, and seemingly so effortlessly, have been difficult to treat using classical mathematics. Mathematicians including, Georg Cantor (1872), Giuseppe Peano (1890), David Hilbert (1891), Helge von Koch (1904), Waclaw Sierpinski (1916), Gaston Julia (1918), and Felix Hausdorff (1919), and Abram Samoilovitch Besicovitch, Pierre Fatou glimpsed the possibilities and difficulties inherent in such shapes, which were deemed to be pathological by most mathematicians. Benoit Mandelbrot, at IBM, resurrected these ideas and extended them to many fields of study. A crucial advantage that he exploited was the use of modern computers to enable one to visualize these shapes, which are very intensely computational to generate. (That is, it takes thousands of calculations to generate each single point in an image.) His name will remain immortal in the Mandelbrot set, a very complex fractal shape generated from a very simple equation, z = z**2 + c, iterated in the complex plane, where z = x + i * y, and i * i = - 1.

To see what this little equation can generate, click here: http://www.unity.force9.co.uk/fractals/ (Web 46). This will show some blow-ups of the edges of the Mandelbrot set without getting too mathematical yet! The central black cardioid shape is often called the Mandelbrot set (M-set), or Mandelbrot lake; however, it is important to note that it is connected by fine (black) tendrils to other M-sets, an infinitude of them. All of these M-sets are similar, but not identical. (The shoreline of the Mandelbrot lake can serve as a map of pointers to Julia sets and Fatou dusts.)

You could keep zooming in on the lakeshore of the Mandelbrot set until it is wider than the known universe and you would still see interesting detail in the small fraction of it that is on your screen! Care to calculate a zoom ratio? Don't even try if a factor of 10**1600 : 1 intimidates you! You can do your own zooms into the land of Mandelbrot, if you have a Java-enabled browser, at http://www.mindspring.com/~chroma/mandelbrot.html. (Ref. Web 410 below.)

Here is one deep zoom: a big image from the land of Mandelbrot. It takes a while to download, but it's worth it! http://www.rosat.mpe-garching.mpg.de/fractals/bcad.gif

Computer-assisted drawing programs (CAD/CAM) allow one to generate complex images, especially man-made ones that conform to the classical geometry of lines, pipes, cones, and so on. However, such methods are fundamentally lacking when it comes to drawing a cloud, a fern, or a mountain. Such programs are also not capable of answering such a simple question as the following, that is the title of one section of the book The Fractal Geometry of Nature by Benoit Mandelbrot, the modern founder of fractal geometry: How Long is the Coast of Britain? Possible answers are: 1,000 km, 10,000 km, 100,000 km, or 1,000,000 km. Which answer is "right"? Answer: each of them is "right", depending on the length of the measuring stick. As the length of the stick approaches zero, the measured length of the coastline increases without limit, even though the enclosed area converges to a finite value. For more, see http://complex.csu.edu.au/complex/tutorials/tutorial3.html.

Lewis Richardson was one of the first to quantify this phenomenon in an attempt to correlate the occurrence of wars with the shape of the boundaries between nations. (See "Arms and insecurity: a mathematical study of the causes and origins of war", Ed. N. Rashevsky & E. Trucco. Pacific Grove, CA: Boxwood Press.) Richardson's search in encyclopedias reveals notable differences in the lengths of common land frontiers claimed by Spain and Portugal (987 vs 1214 km), and by the Netherlands and Belgium (380 vs 449 km). See http://www.vanderbilt.edu/AnS/psychology/cogsci/chaos/workshop/Fractals.html and Web 360. If one thinks that boundary-value problems are in the domain of only mathematicians and their fractals and differential equations, consider what is happening near the boundary of Eritrea and Ethiopia. Bombs are being dropped! The problem? 400 square km of land in dispute, partly because of a map drawn by an Italian. Maybe the border wasn't sketched in clearly enough? About how many times bigger than a soccer field is this? By the way, at least one war was started based on the results of a soccer game. A player who accidently kicked a ball into his own goal was shot to death in the parking lot after the game! Talk about the positive influence of sports on our "culture"! Participaction Canada propagandizes about it -- at your tax expense, by the way!

Mandelbrot built extensively upon Richardson's work and suggested that the relationship between the length of the measuring stick and the length of the coastline could be expressed by a parameter D called the fractal dimension. This dimension has some correspondence to the traditional Euclidean dimension by which a line is considered to be one-dimensional and a figure in a plane is two-dimensional. D is a measure of the roughness of a line or of the extent to which it tends to fill space. An ideal circle would have D = 1. Mandelbrot gives D = 1.26 for the coastline of Britain. Jens Feder, in his book Fractals, presents maps of the west coast of his native Norway, a very corrugated coast indeed! He used a box-counting method to obtain a coastline length of about 2,500 km using boxes of side 80 km and a length of about 30,000 km with 0.6-km boxes. Fractal dimension: 1.52, about halfway between the Euclidean dimension of a smooth curve and that of a smooth surface.

For more insight into this question of scaling, if you have not already done so a few paragraphs above,see: http://parallel.acsu.unsw.edu.au/complex/tutorials/tutorial3.html.

The US Department of Agriculture is investigating the use of fractal dimension in the analysis of aerial photographs to impute the types and stages of growth of vegetation. It seems that the fractal dimension of a maple tree in the ides of March might differ from that in the hazy days of August! Barnsley was one of the earliest proponents of the application of fractal geometry to the analysis of satellite imagery, one source of interest being the (fractal) structure of riverbeds and basins.

Fractal geometry deals readily with questions such as this (although the mathematical basis can be very abstract); classical geometry cannot. Classical geometry and calculus deal well with curves or functions that have a definable slope (tangent or first derivative) at each point. In other words, they deal well with functions that are continuous and have a first derivative (slope) at each point. They are out of their league when they confront curves which are continuous but which have no definable slopes. Fractal geometry thrives on such curves! Mathematicians used to call them monster curves! As stated by Freeman Dyson in "Characterizing Irregularity", Science, May 12, 1978, pp 677-678, "The same pathological structures that the mathematicians invented to break loose from 19^th-century naturalism turn out to be inherent in familiar objects all around us". And yet it is such shapes and other phenomena that appear everywhere in nature. The mathematics of fractals is built on metric space theory, that is, a mathematical space that has a measure of distance, but not necessarily one's usual idea of distance in a Euclidean space. For example, in a metric space the distance from a set A to a set B of points is, in general, not the same as the distance from B to A. This is just to whet your appetite! (As an over-simplified example, in a so-called "taxi-cab" metric space, the shortest distance from one corner of a city block to its diagonal opposite is two blocks, not the square root of 2 blocks.)

My interest lies primarily in the creation and manipulation of pictures. Consider that a picture consists of a collage of images and that, in turn, an image consists of a collage of sub-images. The distances of concern are those between sub-images in a metric picture space of images, and, in particular, how to minimize these distances.

As an introduction to this subject, I have searched the Internet to arrive at the following list of interesting sources out of the thousands available. See section 10. Web sites below. Of those many links, the ones listed under Web 4000 below provide a useful overview and links to detailed supporting material.

After you have reviewed some of these sources and gained some insight into the concepts of iterated function systems (IFS), you will be in a better position to understand some of the following implications of IFSs, the main basis and applications of which are being developed by Michael Barnsley. (By the way, I visited his company, Iterated Systems, Inc., in Norcross, Ga. (northeast of Atlanta) in about 1996.)

Go to Page contents near top of this Page A1.

2. Generation of Complex Shapes from Simple Ones

2.1 Generating the Mandelbrot Set by iteration

It was here that Mandelbrot worked his mathematical genius in developing the idea of the iteration of a simple mathematical formula in the complex plane to produce the incredibly complex image known as the Mandelbrot set. It is probably the most complex object that can ever be envisioned. (Actually, he built on the work in the early 1900s of Fatou and Julia in France and of von Koch, and Cantor.) The Mandelbrot set is an example of an infinitely complex mathematical object called a fractal. What "Infinitely complex" means is that, no matter how much you magnify one section, it will continue to show finer and finer details as the level of magnification is increased. You have probably seen pictures of this blue or black cardioid-shaped "lake" surrounded by intricate filaments of colored swirls, each of which contain smaller , slightly distorted, copies of the "lake". In turn, each of those "lakes" contains surrounding swirls and lakes, ad infinitum.

The Mandelbrot Set is defined as the set of all points in the complex plane for which the value of the iterated equation z = z^2 + c stays bounded (in the complex plane). Here, z^2 = z * z (z times z), z = x + i * y, and i * i = - 1 (i.e., i is the square root of -1). The following are some sites at which you can zoom into the Mandelbrot set to ??? discover a whole new kind of geography. In fact an atlas has been prepared for navigating some of its frontier territories! When it is said that the iterative generation of fractal images can proceed ad infintum, it means that the approach to infinite detail is limited only by the ability of the computer to deal with very large and small numbers. One could expand the following images with your computer to such an extent that your starting screen image would be one hundred million miles wide, and you would still be looking at detailed imagery. (Try asking for that kind of enlargement at your photo store!)

In order to plot such an image, however, intensive computing is involved. In general, to plot a single point of the Mandelbrot set or its environs, one might have to start with a given value of its parameters, evaluate the expression z^2 + c, determine whether that value exceeded a specified distance (square root of 2) from the origin, and determine whether the number of specified iterations had been reached. If the value was remaining within that distance from the origin and the iteration limit had been reached, then the point is considered to be bounded in the sense that, no matter how many iterations one might perform, it would never stray further from the origin. In that case, it is plotted in the "lake" color, usually black or blue. However, if the iteration limit had been reached and the point was fleeing outward beyond the specified distance from the origin, then one calculates its speed of flight, converts that to an associated color, and plots a pixel of that color. One then moves on to the next initial set of values for the initial expression, changing one of its parameters by a small amount. To get reasonable detail in the resulting image, one might have to repeat 500 or more iterations of the above process for each point to be plotted. The picture box used in this chapter is calculated based on a resolution of 1,000 by 1,000 pixels. So, to calculate the full Mandelbrot picture in this case would require 500 * 1,000 * 1,000 = 500 million iterations of the expression and its associated decision-making. Some of the detailed pictures produced a few years ago took three full days of computer time per picture.

The Mandelbrot Set Discovered by Dr. Benoit Mandelbrot, after whom it is named, is an example of an infinitely complex mathematical object called a fractal: http://www.cs.odu.edu/~carr/fractals/mandelbr.html

The Mandelbrot Set Explorer: http://www.mja.org.mx/Prometeo/ejemplos/mndlbrt.html Discover the wonderful world of color that surrounds the famous Mandelbrot Set. Use it online.

2.2 Iterated Function Systems (IFS)

2.2.1 What is an IFS?

The Mandelbrot set illustrates the concept of a fractal as being a very complex object that can be generated through a recursive (iterative) process based on a simple generating rule -- in this case, the simple equation z = z * z + c. Now we proceed with a particular branch of Fractal Geometry called Iterated Function Systems, invented (and patented, for many practical purposes) by Michael Barnsley, formerly Prof. of Math at Georgia Tech, lately founder of Iterated Systems, Inc., Norcross, Ga. He is the author of the wonderful book "Fractals Everywhere".His corporate site is at http://www.iterated.com/.

An IFS is a set of transformations of an arbitrary starting shape -- hereby defined as a seed shape - into at least one additional shape. To produce an image from this IFS one chooses an arbitrary point in the plane, makes a biased random choice of which transfromation to use, then applies that transformation to that point to create a new point. One again makes a biased random choice of transformation, and applies it to the new point to create a newer point. Repeat this iterative process about 200 to 500 times, then start plotting each newest point. Keep on plotting for perhaps 25,000 more points to fill a screen with a reasonable image, or go for 300,000 if you wish. As one plots additional points one obtains additional detail.

It is crucial that each transformation of the seed shape be both contractive and affine. By contractive it is meant that the transformation converts the seed shape into a shape that is smaller. By affine it is meant,that the transformation either shears the seed shape along some axis, reduces its size, translates it without change in shape, or rotates it about any axis, or any combination of these. For example, such an affine transformation could be one in which the seed shape, a square, is reduced in size by half, sheared along the horizontal to become a parallelogram, then rotated about its centroid through thirty degrees, and shifted vertically.

2.2.2 Sierpinski Gasket

As an introduction to IFSs, we consider the Sierpinski Gasket, first studied by the Polish mathematician Waclaw Sierpinski cieca the First World War. First, consider a thought experiment. Draw three points on a paper. Label them A, B, and C. Draw a point P anywhere on the paper. Roll a three-sided die with sides labeled A, B, and C. If the die shows A, draw another point half way between P and A. and let the new point be called P. Repeat this process. Can you imagine what kind of shape, if any, results after you have plotted 30,000 points? Would you expect to see a set of dots placed at random, given that your die has been generating a sequence of random numbers for you? Can you guess what figure begins to emerge from this fog of seemingly randomly plotted points? Click on http://www.swin.edu.au/astronomy/pbourke/fractals/gasket/. This is the Sierpinski Gasket, a triangular fractal. It is the attractor of a 3-transform random IFS dataset of 21 numbers. If that Coca-Cola version of the Sierpinski Gasket was not enough to quench your mathematical thirst, try out some of the other links at Web 340, including some interactive ones in which you can design your own. For an additional explanation, click on http://cs.heritage.edu/cpsc/302/gasket.htm

2.2.3 How can one create a given image?

Let us proceed to build a more complex image, and using a technique which appears to be different, but which can be shown to be mathematically equivalent half-distance method used above. Start with a single rectangle. Transform it into four smaller rectangles, suitably placed, and all lying within (or mostly within) the original rectangle. Denote these as transformations 1 to 4. Pick an arbitrary point on the plane. Choose at random a digit from one to four. Apply that numbered transformation to the point and plot the resulting point. To that resulting point, apply the next randomly chosen transformation. Repeat (iterate) this process several thousand times. What you may see emerging from a supposedly random fog of dots could be a pine tree or the famous Black Spleenwort Fern of Barnsley, depending on the placement and sizes of the four transformed rectangles. Ignore the first 500 or so points. All subsequent points will converge onto the resulting image, the so-called attractor of the IFS. Choose any portion of that image and plot an additional million points to obtain as much additional detail of the attractor as you wish. Whether one started with four rectangles or four profiles of the Volkswagen Beetle, one will end up with the same image. Why? Because the equations describing the transformations are invariant in relation to the particular starting image (rectangle) used as illustration. Iteration of the IFS converges to its unique attractor. This process is referred to as the random iteration algorithm, or (by Barnsley, with his delightful sense of humor, as manifested in his book) the chaos game. Here is an image of the resulting Black Spleenwort Fern of Barnsley: http://www.pha.jhu.edu/~ldb/seminar/ifs.html. (Part of Web 4000 below.)

2.2.4 Collage Theorem

Another way of visualizing these transformations is to consider that the four transformations of the original rectangle are to be laid down beside each other, or partially on top of each other, in such a way as to form a collage that has the appearance of the desired target attractor image. The fundamental basis of IFS image generation lies in the Collage Theorem derived by Barnsley and Demko (Barnsley, M.F., and Demko, S., Iterated function systems and the global construction of fractals, Proc. Roy. Soc. London Ser. A, Vol. 399, pp 243-275, 1985). It quantifies the nearness of a set of points generated by an an IFS to any given structure, the mappings of the IFS being chosen to roughly define a self-tiling of the structure. See http://www.cut-the-knot.com/ctk/ifs.html. (I could have used "approximately" instead of "roughly"; however, contrary to popular usage, "approximately" means "very precisely", not "roughly". Also of some annoyance to me is the increasing trend (even by the CBC) to mistakenly use the word "plus" as meaning "and"; they are not synonyms. To whit: 1 plus 1 may be equal to 2; however, 1 and 1 would make 11, no? )

To see another version of the fern image and variations on it, click on http://cogsci.ucsd.edu/~arobert/ifs.html. (Note to the lawyers: the use (and possibly even the generation of it, as we are doing here) is protected under the proprietary rights of Iterated Systems, Inc.! See http://www.iterated.com/ . Otherwise, downloading explicit images of ferns is not illegal -- yet!

To see some of the mathematics of how to conjure rectangles into ferns, proceed to Web 3 (below) and its link. http://www.pha.jhu.edu/~ldb/seminar/ifs.html at Web 4000 also gives a good description.

2.2.5 Why use random numbers?

Another way to see how simplicity can lead to complexity is to play the chaos game in a somewhat different way. It is emphasized here that chaos does not mean randomness, although a deterministic algorithm can generate so-called random (pseudo-random) numbers, such as the digits of pi (3.1415926535 …). The chaos game shows how randomness in a dynamical system can produce a well-defined geometrical object called an attractor. This object is usually a fractal.

We have used the terms "random" and "chaos" above. In popular parlance, they are synonymous. Here, they have a distinct and important difference in meaning. A random process is one in which there is no discernible pattern. For example, one can examine the digits of pi (3.14159265358979323846264338327 … (that’s as far as I have memorized it (about 45 years ago)). Mathematicians have examined the first billion digits of pi and have found no regularity or repetition. Each digit occurs with equal probability. In contrast, when we say that a process is chaotic, it is common sense to say that there is no apparent pattern—that the process is random. Not so. In science and mathematics, common sense is often wrong. (In fact, much of the progress of science has been made by those who assumed that common sense was either wrong, or at least questionable.)

Consider, for example, a process that Leonardo da Vinci portrayed in one of his drawings, the turbulent flow of water in a stream. In a remarkable stroke of genius and careful observation, he portrayed the water as consisting of turbulent swirls, with smaller eddies occurring within bigger ones. By definition, this represents a fractal process, the occurrence of self-similarity at different scales of size. If one were to throw a small drop of ink into the water, could one predict where the ink would end up "downstream", or whether it would even retain its identity as a drop? (In this context, one might well question what the term "downstream" means. Here we go, getting picky with meanings again!) In the days of Leonardo, one certainly could not. One would be tempted to say that the destination of the ink is a random location. Even with our present knowledge and fancy mathematics dealing with turbulent and laminar flow, including the differential equations of Bernoulli and Navier-Stokes, it is still a difficult process, even with the aid of powerful computers. Witness weather forecasting. Now we would say that the process has some structure, although complex, and is therefore, not random. We denote a process as being chaotic if a small change in initial conditions can lead to a large change in outcome, not just a small change. Another way to state this is to realize that what appears to be a random process has an inherent regularity, except that it is too complex to easily discern. A third categorization of chaotic systems is to say that they are non-linear, in the sense that at each stage of iteration, the resulting effect is proportional to a power of the input change instead of being linearly proportional to it; hence the term "chaotic dynamical systems". We are back to the distinction between smooth, classical functions in contrast to the broken, fractal processes that bothered the classical mathematicians so much.

We are now ready to appreciate Barnsley’s categorization of generating images from IFSs using random numbers as being the "chaos game". Another way to designate this procedure is to call it a Random IFS (RIFS). In the above Sierpinski Gasket that we have generated, note where the pink, yellow, and green pixels appear. They seem to be randomly distributed, and yet the image that is generated has a regularity in its shape apart from color. We could have generated the image without using random numbers, by using a so-called Deterministic IFS (DIFS). In that procedure we could have chosen a starting point P, and then applied transformations A, B, and C in an ordered fashion so as to exhaust the number of possible combinations of A, B, and C, down to a prescribed level of detail, or, in other words, through a given number of branching levels. (This concept of branching levels will be pursued later, as it will form an important tool in the rendering process, even when using RIFS (as we shall do) instead of DIFS.)

The problem is that, in using DIFS, we would have spent an inordinate amount of time plotting detail at the expense of other areas of the developing image because the number of such possible combinations quickly becomes enormous as we increase the number of levels of combinations (i.e., the number of branching levels) to apply. In other words, we might be expending computer time plotting 1,000,000 points in a portion of the image the size of the letter A, whereas 10,000 points would have been sufficient for good detail in appearance. In other words, we might have spent 2 hours plotting the above image (at 7,000 plots per second) instead of 20 seconds, without achieving any advantage in the apparent quality of the image. In fact, for some purposes, plotting too many points can degrade an image. For example, one might like to plot an image that includes fog that is partially transparent, not solid white, if one wishes to see another image underneath the fog.

For an introductory essay and for the distinction between chaos and randomness, click on http://www.pha.jhu.edu/~ldb/seminar/laplace.html and prroceed on through at least the next two pages at that site (at Web 4000).

The following is an excerpt from Tom Stoppard's "Arcadia". See http://www.honors.unr.edu/~fenimore/wt202/vandeman/#math for Vandeman on interated algorithms, and some images, and http://www.honors.unr.edu/~fenimore/wt202/arcadia.html for mathematical aspects of the play, including those in a course at the University of Nevada, Reno! After all, the folks in Nevada do know a bit about randomness and how sure its odds are!

"The ordinary-sized stuff which is our lives, the things people write poetry about - clouds - daffodils - waterfalls - and what happens in a cup of coffee when the cream goes in - these things are full of mystery, as mysterious to us as the heavens were to the Greeks. We're better at predicting events at the edge of the galaxy or inside the nucleus of an atom than whether it'll rain on auntie's garden party three Sundays from now. Because the problem turns out to be different. We can't even predict the next drip from a dripping tap when it gets irregular. Each drip sets up the conditions for the next, the smallest variation blows prediction apart, and weather is unpredictable the same way, will always be unpredictable. When you push the numbers through the computer you can see it on the screen. The future is disorder. A door like this has cracked open five or six times since we got up on our hind legs. It's the best possible time to be alive, when almost everything you thought you knew is wrong."

2.2.6 Image vs picture

For our purposes, I define an image as being the set of points generated in this way by one single IFS. I define a picture as being either of the following:

(a) A single image imposed upon a background.

(b) A single image along with a transformation or repetiton of it -- for example, its reflection (e.g., in water) -- with, or without an added background.

(c) Two or more images, with or without backgrounds and transformations or repetitions of images.

(d) A picture, to which has been added (or superimposed) either an image, another picture, or any additional backgrounds or transformsations of images.

Therefore, for our purposes, the word picture does not mean the same, in general, as the word image. I define an image as being the graphic generated from a single IFS.

My aim is to create a program for the design and storage of images and for building pictures from them. What I call a picture would be a collage of images. In turn, each image could be a collage of sub-images. Consider that one wishes to build a picture such as a classical landscape consisting of images of sky, mountains, trees, and water, in which the images are applied in layers one on top of another. In general, each image would be partly transparent, so that, for example, the rectangular boundary of an image of a pine tree would enclose an area in which only a relatively small percentage of the image area would consist of green pixels, even though it would appear as if the tree occupies almost the entire extent of the rectangle. This area as seen in the final picture could contain green pixels from the tree image, brown and white pixels from an underlying mountain image, and blue and white pixels from a sky image underlying the mountain image. Thus, the term collage here includes, but is not restricted to, the special case of cutting out pieces of paper images and pasting them side by side.

2.2.7 Specifying the IFS and its tranformations

To summarize:from the above, we have learned that each transformation of the seed into a tile must be both contractive and affine, and that each transform can involve any or all of translation, rotation, and shear. Secondly, a given IFS consists of a set of such transforms, all of which must apply to the same seed. The fact that all of the transforms of a given IFS must all apply to the same seed is very important, especially as we shall be dealing, in later chapters, with multiple IFSs to generate what we shall call "pictures" rather than just single "images".

An affine transformation A (in two dimensions) is a function that performs some combination of scaling, rotation, and translation on points in a plane and takes the general form

x’ = a * x + b * y + e

y' = c * x + d * y + f

Given a particular transform of the seed shape into a tile shape, one can set up six equations in the six unknowns a, b, c, d, e, and f using matched pairs of the known points (x, y) and (x’, y’) to solve for the values of the parameters a to f. Now, given any arbitrary point (x, y) in the plane, one can apply the above transform to obtain the transformed point (x’, y’).

Another way of expressing the two equations above is to use matrix notation (alias vector notation), here in the form

(x', y') = [A] * (x, y) + (e, f),

where terms in the format (symbol, symbol) are vectors, and the term [A] is a matrix (in this case a 2 by 2 matrix). This is more elegantly expressed using more sophisticated formatting, in the following, which is well worth a second look: http://www.pha.jhu.edu/~ldb/seminar/ifs.html.

[To mathematicians who are reading this, please excuse the fact that I may be stating this too simply. There is hope for you yet, in that there will be places where I will be saying decidedly too little (albeit of less importance for our immediate purposes)! Besides, the details are in Barnsley’s book and on the Web, including to some extent, in the link shown immediately above. There, you can revel in the technical specifics of what is meant by a measure of distance in metric space. (The answer is not obvious. For example, the distance from a set P1 of points to a set P2 in metric space is not necessarily the same as the distance from P2 to P1 in our ordinary (Euclidian) space. That should give pause for thought!)]

You will not need to know or apply these details in your creation of the ideas for images nor for using ConjPic for generating them; however, I think it helps to aid in the overall understanding of these processes, as do the following notes on interpretation. The parameters e and f represent a linear translation of the tile, by the distance e along the x direction and f along y, without any change in orientation or size of the tile. The parameters a, b, c, and d represent either a size scaling or a rotation of the tile about its center, or both.

[An alternative to the above representation is possible and, for some cases, is more convenient. That is a representation in which, instead of having x and y as variables (in a Cartesian coordinate system), we have a polar distance variable, r, and an angular variable, theta (in a polar coordinate system). It is possible to translate between these two modes of representation.]

By now, you have probably realized that we have been proceeding under a hidden assumption. We have implicitly assumed that we are using two-dimensional affine transforms for the creation of a two-dimensional IFS which, in turn, will be used to build a two-dimensional image. That is the case with the present version of ConjPic and its documentation. It is possible, however, to carry out these procedures in three-dimensional space, in which case, we would be dealing with affine transforms, IFSs, and images, all of which would be three-dimensional. Representing the final three-dimensional object on a two-dimensional computer screen or a piece of paper would then require the projection of that object onto the two-dimensional plane taking into account the viewing angle (viewport in some parlance). The latter procedure is now a standard part of the mathematics of computer graphics. Instead of dealing with a 2 by 2 matrix operating on a vector (x, y), we would be using a 3 by 3 matrix operating a three-vector (x, y, z). You may find it to be enough of a challenge to master the present craft in two dimensions, rather than worrying about how it could be done in three!

The three-dimensional case should not be ruled out totally, however. There are at least two methods now by which a computer can operate machines to produce three-dimensional sculptures. Recently, a three-dimensional photocopy machine has been demonstrated!

To see some of the mathematics of how to conjure rectangles into ferns, and the presentation of the above in typographically more elegant form, click on http://www.astro.virginia.edu/~eww6n/math/Barnsley'sFern.html. If that site is still unavailable, owing to a copyright battle, click on http://codenet.al.ru/progr/fract/intro7.htm for an excellent discussion (some of it in Russian). It is well worth navigating the other related subjects in this series of links. Start at An Introduction to Fractals at http://codenet.al.ru/progr/fract/intro.htm.

Although the length of the perimeter of an image is not readily definable (in general, it increases without limit), there is a means of determining a limit to the spatial extent of the attractor. (See "Estimating the Spatial Extent of Attractors of Iterated Function Systems", D. Canright, Comput. & Graphics, Vol. 18, No. 2, pp 231-238, 1994.)

I have written programs in Basic and C that allow me to build images. I am now proceeding in the environment of Visual Basic (VB) to build the overall program. (I have chosen VB because it has hooks into menuing and other capabilities already present in Windows, thereby saving me from writing thousands of lines of tricky housekeeping and interface code.) I can envision processes additional to those of collage, about which more later.

To ponder the question of software design, consider the following:

"There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies." -- C. A. R. Hoare

End of section 2. Generation of Complex Shapes from Simple Ones. _______ Continued at 3. Data Compression

Go Home. Go to Page contents near top of this Page A1.

You can e-mail me at waynerp@sympatico.ca