~~~~~~~~~~~~ < 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."
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.
Go Home .
==========================================================================
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
==========================================================================
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 19th-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
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 that 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
Go to Page contents near top
As a refinement of the process of generating the fern as discussed above, choose the transformations at random, but with probabilities proportional to the relative areas of the associated rectangles. This assures a more homogenous distribution of points and, very importantly, a tremendous reduction in computing time. One is now dealing with Random Iterated Function Systems (RIFSs). (The acronym RIFS has also been used to denote Recurrent IFSs, a different but related concept.)
The amount of data defining the IFS in this case is
the number of transforms (4)
times
[ the number of parameters (6) defining the transform of each smaller rectangle from the original
plus
the probability of choosing the transform (1 number) ],
for a total of 4 x [6 + 1] = 28 numbers.
Thus, to store the complete data needed to generate a one-million pixel image of a fern requires only 28 numbers! Not a bad compression ratio! Even this is understating the case, at least in the program that I am writing, because one can impute what those relative probabilities should be from the transforms themselves. As shown by Barnsley, those relative probabilities are proportional to the determinanats of the matrices of the transforms. To see what those matrices are, click on http://www.pha.jhu.edu/~ldb/seminar/ifs.html. Thus, only 24 not 28, input numbers are needed to generate the image. In essence, the larger the absolute value of the determinanat, the greater is the number of times that that tramsformation is chosen in our game of biased random choice. And what would it mean if the value of a determinant is negative? It means that the transformation of the starting rectangle into the transformation rectangle has not only in general distorted its shape, but has flipped it upside down!
And to think that the year-2,000 problem could have been postponed (for 1000 years) by storing just one extra byte, such as by calling the year 1998 098 instead of 98, thereby postponing the problem until the year 3,000! I dare say that each penny saved by avoiding the extra byte will cost at least $1 to fix! According to PC Dealer magazine, the Boston transport authority doesn't want people to feel anxious about riding in the subway at the last midnight of 1999. So its directors have approved a five-year (!) plan to ensure that its computers are year-2,000 compliant! Very reassuring! Long before 3000 (by 2020?), thanks to nanotechnology, one should be able to store all of the information of all libraries of the world, uncompressed, and the computer to access it, in the volume of a pocket book. By the way, such a nanocomputer would probably be mechanical, rather than electronic. It could consist of a three-dimensional array of mechanical push-rods and knobs of molecules, as detailed by K. Eric Drexler. See http://www.mitre.org/technology/nanotech/mechanical.html . Charles Babbage would have been proud! (Students at MIT have built a computer out of Tinkertoys that plays tic-tac-toe! Spare the rod? It is one of the few computers around that won't have a year-2000 problem!)
If the technology and economics of manufacturing cars had advanced as much in the last 30 years as that of computers, we should be able to by a new Cadillac for $1.00! If we were still using vacuum tubes, a cell phone would be the size of the Washington monument! (Careful: there is current research into microscopic-sized vacuum devices.) We have just begun the quest to build machines on a molecular scale -- nanotechnology. Three hundred years ago Leonardo da Vinci was asked what one of his sculptures represented. He replied that it was to be a machine that could fly. When asked why he thought that such a ridiculous thing would ever be possible, he replied that we already have machines that can fly -- they' re called birds! When a nanoscientist is asked today why he thinks that we should be able to build submarines (complete with engine and cutting devices) so small that a million of them could float on your thumbnail, the reply could be that we already have machines that small -- they're called enzymes, and we are full of them, and they are busy cutting and pasting molecular chains, at the rate of 5,000 per sec.!
In about 1995, my lawyer at work mentioned to his other client, the Canadian Nuclear Submarine Project, that I had a background in nuclear physics, computers, and contracting. They wanted me to "come aboard" and arranged to interview me, by which time the project was canceled. At about the same time, Japan announced its establishment (to the tune of $200 million) of a micro-machine laboratory, in which the first main project would be to build a submarine, of total length 1 mm. The second stage would be to build one 1,000 times smaller! Just think what a few thousand subs with shape-recognition sensors and cutters could do to fat deposits in your arteries or to the tips of the retinal rods in your eye, to give only two examples of surgery now (crudely) performed. (Shades of Fantastic Voyage!) Now let's work out the cost and the profit margin of these subs on the commercial market. Japan did not intend to lose money building this technology! Would $10.00 each (in lot quantities of 10,000) be too much? Or, eventually, would one cent each be too much? I have just heard, by radio from Germany (in 1998), that a submarine 4 mm long has been on display at the big trade show in Hannover -- that's huge, but give it time! In about 1995 I saw a picture of a working engine 4/1,000 of an inch wide, grown of silicon, with a main wheel that spins at 20,000 rpm. (No, it doen't use WD40 oil!) This is still a leap from the aim of one building molecule-by-molecule (which will happen), but it's a step!
Drexler foresees the day when, with the help of our home computer and the Net and its collection of succulent recipes, we should be able to construct in our kitchen things like a NY sirloin steak from the raw materials at hand, mainly hydrogen, oxygen, and nitrogen (free in the air) and carbon (from a pile of dirt in the corner)! As for a glass of pinot noir -- why not! "Which vintage shall I manufacture (excuse me, serve) today, sir?" (This may sound like a bit of a pipe dream in an age when we have not even accepted the use of superior Coca-Cola technology (the screw-on plastic cap) to replace cork stoppers on wine bottles! Can you imagine how little cork (and its increasing inferiority) there is left on the trees still remaining in Portugal? Our problem here is not technology, it is misperception, by both the public and many "experts". To illustrate how ludicrous this situation is, I heard an interview with an entrepreneur recently via the Australian Broadcasting Corp. in which he was explaining that, in light of the increasing shortage and price of reasonable cork (i.e., cork without holes), his new stopper had great potential because it would: (1) be made of plastic and cork such that glass would touch only plastic, not cork; (2) wine could touch only cork, not plastic; (3) the stopper would be removable (and replaceable) without using an external tool such as a corkscrew; and (4) it would look like cork. What a remarkable advance in technology, bringing us almost up to the stage that Coca-Cola had surpassed at least 20 years ago, and at twenty times the price of screw-on caps by Coke, I would guess!
Correct me if I am wrong, as I am not a wine expert, but I thought that the purpose of a cork was to keep contaminants such as air and bacteria away from the wine, especially if it is to rest on a shelf for ten years before being sipped. That technology has been in use for about 400 years, and it obviously does not work well at all. About 3% to 7% of wine is contaminated by the cork itself, not to mention the contaminants that manage to work their way from outside through the porous cork into the wine. Coca-Cola would shudder if its failure rate were even as high as 0.0001%, much less 3%, and the problem for Coca-Cola is perhaps more difficult than that facing wine bottlers, what with carbon dioxide and all. But some wine bottlers have solved the problem using the much more reliable srew-on cap, but of course, only for "cheap" wines. It is one of the great ironies of the vino world that wines least in need of quality protection utilize the most effective closures, while high-quality wines that need protection use less-effective closures. For a delightful little essay on this topic, click on Screw This!. We provide the ultimate in safety for a $1.00 bottle of pop (at a cost of $0.005 per botttle for plastic?), but fail miserably to do so for a $100 bottle of wine (at a cost of $.50 per bottle for cork?)!
For a landscape equivalent to an oil painting, one might consider an IFS consisting of 150 to 300 transforms. The difficult part is choosing which particular set of transforms would create a given image. Barnsley has solved this problem, so that his special software can now do this automatically. The procedure is too complex to describe here. Suffice it to say that it consists of an iterative mapping between grids of "domains" and "ranges" of a picture to derive the resulting IFSs. It exploits the fact that it is more probable that one grid element is similar to another than that one picture element is similar to another. Note that IFSs is plural here. Although this is somewhat of a simplification, the key idea is that, rather than even try to express the picture as the result of a single IFS, one instead aims to express several portions of the picture as arising from a single IFS, but that many IFSs will be needed to encode the total picture. For example, in the test picture of Lena, the edge of her cheek might look very similar to an edge of her arm, so why repeat all of the pixel storage for each portion of the picture? Instead, express both as arising from a single IFS. It requires a massive amount of computing. He has produced a special hardware and software system that does the job, all heavily protected by patents. He offers a special board that can be plugged into a PC, consisting of eight math co-processors operating in parallel and application-specific integrated circuits (ASICs). To reduce an 8 x 11" colour photo to an IFS requires 12 seconds (as of about 4 years ago). Having done this, one could then send the IFS parameters by phone line to a remote computer and regenerate the picture in about 2 or 3 seconds using additional regeneration software. For more of an idea as to how this works, click here: http://www.mathcs.carleton.edu/students/stewartj/networking/fbc.html.
Barnsley has contracted with a major oil pipeline system in Africa. Cameras are mounted at remote locations. They periodically snap a picture, reduce it to an IFS, and send the parameters to home base via short-wave radio where the color image is then generated. How's that for pipelining of data! We could be doing a similar thing with chest X-rays from Ninavut!
Two systems are in operation for transmitting short bursts (of perhaps a few tens or hundreds of milliseconds) of data by radio from remote sites by bouncing radio waves off meteor trails. This is underway along the west coast of BC, where data from water-level sensors is sent to a central site to help foretell tidal waves. A system is in use throughout the plains of the USA for the tramsmissit\ion of data on ground moisture, temperature, etc., for instant retrieval by the US Department of Agriculture. This is a lot cheaper than leasing land lines, and there is a sufficient supply of meteors! Auditors take note: in this business, one depends not so much on audit trails, as on meteor trails!
Barnsley has collaborated with Microsoft to produce the Encarta Encyclopedia, including 7 hours of sound, 100 animations, 800 color maps and more than 7,000 photographs in less than 600 megabytes of data on a single CD ROM. (See http://www.ippi.com/dir_akp/akp_fracim.html.) I estimate that this was done using a compression ratio of several hundred to one, perhaps 1,000 to one. (IBM is trying to increase the capacity of CD ROMs by a factor of ten, without compression, using ten layers of bits instead of one. Someday, using nanotechnology, we will be using millions or billions of layers!)
Barnsley has produced a short movie, involving a storm over an ocean, using a compression ratio of 1,000,000 to one. For high-resolution images, ratios of 20 to 100 to one are more the norm. His compression technique allows one to choose the quality of resolution desired, including (paradoxical as it may seem) a resolution higher than that of the original!
Go to Page contents near top
Barnsley has contracted with the US Air Force to solve problems such as the following. Given that we have 10,000 photos taken from spy satellites and planes, many of which, such as some over Iraq, seem to show airplanes on runways, what model of plane are they, and exactly where are they? (I came away from his company with a 3.5-inch demo disk containing very detailed zoomable aerial photos of Iraq Base 1 and Pearl Harbour 1 and 2, and 14 seconds worth of color video and sound, all compressed, of course. This is all the more impressive considering that a 600-MB CD can hold only about five minute's worth of uncompressed video!)
Another interesting application is to have a computer observe a corridor through a video camera and raise an alarm whenever an unauthorized person takes a stroll. (A bit more sophisticated than that at least one location in IBM where someone wearing a red badge could get into trouble by walking on a blue carpet instead of a red one! It gives new meaning to being brought up on the carpet! ) With cheap ($100) video-cameras-on-a-chip, Britain is leading the way in installing thousands of surveillance cameras per year in public (and not-so-public!) places to detect naughty people. (Do you think that every place inside of a "public" washroom at Heathrow or in a ATM booth is a "private place" under the law? Think about it!) This will soon escalate to tens of thousands per year. Oh brave new world! So far, the viewers are humans. Will it be more comfortable when computers do the observing instead?
Some homes are now equipped with such cameras, so that one can log onto the Net and spy upon what is happening at home. Nor quite so appealing is the thought that a hacker could arrange to peek into what is happening in someone else's home!
Cameras now stare at people punching PIN numbers into ATM machines. The problem is: how to hack into these images! It has been done, at least once! One has to make a living somehow! (Does PIN stand for Piracy Is Nifty?)
In addition to the use of fractals, several approaches are being taken in how to tell a computer what a face looks like in such a way that it can retrieve it or a close relative. One method is to use a classification system as to width of lip, angle of eyebrow, etc. If one had, say, 200 such characteristics, one could then represent the face as a single point in a 200-dimensional space. The problem of then generating a portrait of a face that appears to be half way between that of John F. Kennedy and Marilyn Monroe then becomes simple: just interpolate between the two points in that space and convert the interpolated point into a portrait. A grad student at MIT has done it. One can even extrapolate to find out who would look twice as different than JFK as Marilyn! In my ConjPic computer program, I can morph an image of a galaxy into that of a pine tree by simply varying a single parameter from frame to frame.
Go to Page contents near top
Several technologies have been vying for years to become standards for High-Definition Television (HDTV). Most of them would require four channels of TV input to produce one channel of output, a profligate use of already scarce bandwidth. Barnsley plans to bring one channel in, reduce each frame to an IFS, and regenerate each frame as an HDTV picture. To do so, the system will have to do the process 30 to 60 times per second instead of the once every twelve seconds noted above, a factor of 720, or about 72,000 times as fast as a PC. I believe that it can be done. For this reason and others, the TV set of the future will consist of a high-resolution monitor and a supercomputer, perhaps one 100 times faster than a Cray. See the chapter "The Death of Television" in the book "Microcosm: The Quantum Revolution in Economics and Technology" by George Gilder (ISBN 0-671-50969-1). Nanocomputers should be able to operate at rates such as one million million instructions per second. A partial advance is underway in that a decision appears to have been made days ago to phase out analog TV and phase in digital TV in parallel. By 2006, all present TV sets will be obsolete.
Barnsley has coined the term "fractal forgery" to denote the process of generating an image from an IFS because this process can generate a picture that has more detail than the original! Provided that the original picture has elements that are similar or identical at different scales of size, this forged detail can be believable. For example, the branch on the branch of a branch of a tree often appears to resemble the branch of a branch of that tree, possibly sheared or distorted (affine transformation). (If I incorporate a company to exploit this technology, maybe I'll call it IFFY (Iterated Forgery For You)! That way it will not only be iffy, it will sound iffy!)
So, unlike other compression techniques (such as JPEG, MPEG, Wavelets, and DCT), IFSs allow one to generate more detail than that in the original, much of it believable, some not. That is because of an important characteristic of fractal compression: that is, unlike other techniques, it is not pixel-dependent. It also allows for smooth animation by smooth variation of the underlying IFS parameters; hence the ability to morph, i.e., make movies. The reason why the associated Fractal Image Format (FIF) has not become popular is attributed to marketing and patent-law decisions by Iterated Systems, much to the dismay of some critics.
An animated zoom into a fractal image, Bluedive, is available from the following sites:
ftp://fractal.mta.ca/pub/cnam/anim/schol/
ftp://ftp.doc.ic.ac.uk/Mirrors/fractal.mta.ca/pub/cnam/anim/schol/
This was accessed from the following site:
Web 119. Bluedive, from Eric's Fractal Gallery. Fractals: Not by the Numbers, or Fractured Gary Tales by Dr. Gary Kerbaugh: http://www.cs.ecu.edu/~kerbaugh/FractalsNBTN.html Links to related pages.
Go to Page contents near top
I foresee the day, within ten years, in which a new Hollywood film premiers, starring Marilyn Monroe and Joseph Cotton, all creatures of IFSs! The screen credits will include no actors -- only computer programmers and cyber-artists. I have already seen a movie in which the credits included 30 programmers and analysts and interesting chunks of hardware, such as frame grabbers. (In the movie The Last Starfighter, an intricate 20-minute battle between spaceships was generated entirely by computer.) The number of computer analysts required will be exceeded only by the number of patent, copyright, and intellectual property lawyers needed!
When we think today of movie-production factories, we recall names such as MGM, Columbia, 20th Century Fox, and United Artists. Only a few years from now we may more immediately bring to mind names such as Industrial Light and Magic, Lucas Films, Digital Domain, and Dreamworks, fueled by cyberartists from Sheridan College (Toronto), among others.
Why is it that sports and, in particular their heroes, are so popular on TV? Why is Wayne Gretzky a millionaire for contributing what is arguably of little benefit to society? Could it be that, like the Greeks of old, we still need to manufacture heroes? Could it be that, urged on by the propaganda of Molson's, Coke, and Participaction Canada, we attach such ridiculously inflated value to being able to run faster and jump higher? (How ironical it is that Coca-Cola is a major sponsor of the Olympics in order to advertise its main product, a banned substance under the Olympic dictatorship! I can send an essay on Olympic drug testing as an unconstitutional invasion of personal privacy and national sovereignty.)
The closest most of us get to being an athletic hero is to see proxy images on TV. But we do so now with some limitations. First, the picture is not life size. Second, although the picture is in colour, it is only presented in two dimensions, in spite of the fact that technology has existed for years to give us full 3D colour images (not the old red vs green variety). But perhaps the biggest limitation we have vis-à-vis hero-association is that the hero on the screen is not I! With IFS technology it could be! Why shouldn't that athlete on the screen be me, instead of Wayne Gretzky? After all, for purposes of hero worship (and worship at some kind of shrine it appears to be!), all that is needed for me to be the hero is for my picture to be the picture of the hero! After all, to say that you have seen Wayne Gretszky "only" (for most of us) means that you have seen his picture on a screen. What would happen if, instead of his face appearing in that hockey suit on the screen, it were your face? Why would it be any less real? If his face on the screen convinces you that he exists, in spite of the fact that you have never seen him in person, why should the appearance of your face in his suit on the screen not convince you (and, even easier, everyone else) that you are not now the great hockey hero that everyone is talking about?
To appear to be, or not to be? That is the question. How do we arrange the slings and arrows (IFS vectors) for this to happen, and to make an outrageous fortune? IFS technology and smart entrepreneurs! How much would you be willing to pay so that the whole world watching the next Rosebowl game would see you as the quarterback? I can see several variants of how to do this, involving both technical and commercial considerations. Would you be willing to pay $100,000? After all, those special boxed cubicles in the stadium go for at least that much (at your expense, as corporate tax write-offs). The main technical requirement is to have a few portraits taken of you at several angles, the reduction of your portraits to IFSs, the reduction in each frame of the quarterback's face to an IFS, and the switcheroo of IFSs! That takes care of the video image. Now for the audio image. That gets a bit more complicated. We need to reduce the sonograms of the quarterback's name as spoken by several announcers and post-game interviewers, to audio IFSs, and we are ready to do audio switcheroos, being careful, of course, to use voice recognition to ensure that the audio image of your name is spoken by the appropriate announcer! If we can vote by proxy, why can't we be heroes by proxy? In other words, if an image can be picture-perfect, why can't it also be proxy-perfect? There could be two versions of this process. In one version, John Doe, would appear on all TVs as being Wayne Gretzky. In another version, John would appear as Wayne on only selected TV sets, those which, by prior arrangement, had downloaded the personalized IFSs. Would an IFS by any other name look and sound as sweet?
I dare not even mention this idea to Walt Disney studios or to the advertising agencies! Could you tolerate seeing yourself in the next 100 replays of your worst nightmare of an ad? Could you have foreseen that you did not want to be in that ad, but that someone hacked into your computer, "borrowed" a copy of your personal IFS signature, and sold it on the Net for some e-cash credits? Now he's driving the Mercedes that you saw yourself driving in an ad on TV last night! It's enough to make you want to lose face, for a change!
As a byproduct of these technologies we would no longer need or want to have football stadiums. My wife and I were given free tickets to attend several football games by the Ottawa Roughriders. Although I am not a football fan, I would enjoy watching such games on TV more than at a stadium. The problem with being at the stadium was that, at each exciting part of the game, everyone would stand up, meaning that I could not see what was happening. (Somewhat akin to watching a movie with all of the naughty bits blanked out!) Other shortcomings were: a lack of commentary, no close-up video, no instant replay, and no armchair. Without these, football in real life is not as real or as interesting as that on TV! Even in a real stadium, what does it mean to say that a game of football is real? It is no more real to me than StarTreck! I think that the logical next step is to replace the football stadium by a big TV studio. The next step is to forget the studio and replace it with comfortable computer stations and fractal computer artists. If this seems like a pipe dream, walk into a computer store and ask to see NHL hockey games being generated completely by software. It's not perfect yet, but neither were 45-rpm records a few years ago! Take a look at a recent Sony PlayStation if you want to see some fast 3D graphics. These toys are far faster than the early Cray supercomputers.
Twenty years from now, CDs will be as obsolete as record cylinders. Museum curators and librarians are already worried as to how today's recorded information will even be readable in the future! The CDs may survive, but where have all their players gone? If you had a 45-rpm record, could you play it? (In my work in Federal contracting, I had occasion to arrange for a trade-in credit of a working computer terminal from a government department to a private company so that the company could put it into its museum. In New England three years ago I saw a computer for sale in an antique store.)
Music has been compressed using IFSs. I foresee that IFSs can be invented to produce new music. Another variant would be to create a system to transform a visual image into music using IFSs and computers.
Another possibility that I might pursue is that of converting between visual and musical "images". Lest this be more than a pipe dream, I recall that there is a musical composer (Olivier Messaien, see below) who has a mental condition (synaesthesia) by which he automatically converts visual imagery, mostly triggered by color, into music. It appears to be a kind of "crosstalk" between visual and auditory modes of perception. He composed a major symphony primarily by taking a helicopter ride through a canyon (such as Bryce in Utah) in the southwest USA. This canyon has spectacularly coloured layers of rock. (We visited it a few years ago.) Perhaps not coincidentally, there is a graphics painting program called Bryce, and another one called Fractal Design Painter. Check the Net for some lovely examples. (If you are in the southwest, visit Bryce Canyon if you are moved by colour, or the Grand Canyon if you are impressed by vastness.)
Web 27. Synaesthesia: Music & Art
Synaesthesia: Music & ArtPage for the International Synaesthesia Association: http://nevis.stir.ac.uk/~ldg/ISA/ISAMusicArt.html Dr. John Harrison, Academic Unit of Neuroscience, Charing Cross and Westminster Medical School. Dr. Simon Baron-Cohen.
The composer Olivier Messaien gives a particularly florid description of his colour sound associations in his 1947 account of "the gentle cascade of blue-orange chords" in the piano part of the 2nd movement of Quator pour la fin du temps. He is later more specific about the nature of his synaesthesia when he states he sees "colours which move with the music, and I sense these colours in an extremely vivid manner".
I cannot resist a further digression in relation to crosstalk of perceptions. I have discovered only recently, by accident on the Internet (a fortuitous collision on that highway, don't you think?) that Richard P. Feynman, one of my heroes, when reading equations printed in black ink on white paper, would perceive that different aspects of the equations would appear to be in different colours, in a systematic way. One might characterize this as letter-colour synaesthesia. Curious! Here are two interesting sites.
Web ?. Richard Feynman's Synaesthesia
Richard Feynman's Synaesthesia. by Ian Watson. Richard Feynman (1918-1988), winner of the 1965 Nobel Prize in Physics, was a letter-color synesthete as . . . http://nevis.stir.ac.uk/~ldg/ISA/Feynman.html
Web ?. Quote by Richard Feynman: http://golem.physics.ucsb.edu/~mikefalk/poems/feynman.html An Intriguing Quote by Richard Feynman. It will be difficult. But the difficulty really is psychological and exists in the perpetual torment that results . . .
Go to Page contents near top
Yes, fractals are everwhere! They are buried in time series, such as electrical noise, the rise and fall of the Nile River, the growth of cities and dendrites, the sublime music of Bach, and in stock-market prices.
See the book Chaos and Order in the Capital Markets by Edgar E. Peters, for how one can apply complexity theory, fractals, genetic algorithms, and wavelets to market prices. Don't buck the trend -- make a buck from the trend!
Web ?. Wiley Finance--Frontiers in Finance Chaos and Order in the Capital Markets. Edgar E. Peters. http://www.wiley.co.uk/products/subject/finance/finance/front01.htm "The bible of market chaologists." -- BusinessWeek.
Web ?. Chaos and Order in the Capital Markets: http://www.amazon.com/exec/obidos/ISBN=0471139386/spiffynetA A New View of Cycles, Prices, and Market Volatility (Wiley Finance Editions) by Edgar E. Peters. List:.
Go to Page contents near top
9. Database Access via Fractal Compression
(This summarizes a separate document sent to Richard earlier: C:\Up\CrossZ1.doc.)
Listed below (at Web 900, Web 901, …) are some hyperlinks to sites dealing with fractal databases, that is, database-access methods that use fractal data compression as part of the access method, rather than databases of fractals as a subject, per se. They were garnered using searches for Cross&Z (120 docs), Cross&Z&International (65), "Cross/Z International" (41), and QueryObject (96).
The following article perked my interest in this subject beyond my ongoing interest in fractals as applying primarily to images: Fractal Databases – New Horizons in Database Management, by Lisa Lewinson, PC AI Magazine, March/April 1994, pages 30 to 33. The article summarizes the work of Andre Szykier, Chief Technology Officer of Cross/Z International, and his cousin, Mark Chroscielewski, Senior Marketing Executive at Chase Manhattan Bank.
Andre had been developing a proposal involving constructing a map of the last stretch of terrain that a cruise missile would fly over. Szykier proposed the use of a fractal equation (more likely, a set of affine transformations) to represent coordinates for longitude, latitude, and terrain altitude.
Mark’s problem was to build a massive customer database for the bank, involving 30 million names, with data from five credit bureaus that would have to handle up to seven levels of data. Within two weeks they had built a prototype fractal database, compressing 30 million records onto a PC. They found that they could do exact counts instantaneously, as compared to queries on a mainframe, which took several days.
The key to the technique is that, for example, one could represent 10,000 to 20,000 hourly temperature observations as a shape represented as a single fractal data point of eight bytes. This single point can be used to reproduce any or all of the original data points exactly. Thus, one can discard the original data. (I have some detailed material on this subject of fractal interpolation and construction of fractal curves.) They are exploiting 64-bit chip technology to achieve data-compression ratios of 10,000 to 1. In 1994 they were upgrading their system to display segment counts for an array of 22 by 22 variables, 7 levels deep. Their system requires about 15 minutes to create views of a 40-million record database, after which each query takes less than one second on a PC.
Go to Page contents near top
The following are some sites involving fractal geometry and iterated function systems as garnered from the World Wide Web. Some also involve L-systems (see The Algorithmic Beauty of Plants by P. Prusinkiewicz and A. Lindenmayer). They involve mostly visual imagery, although there is some fractal-generated music here and there, and some other digressions farther afield. Read the first few for a general overview and an introduction to the mathematical basis. The rest are mostly pure poetry and other applications!
Remember that my comments are in black. Plagiarized text is in maroon.
The following refernces to sites will be sorted into a better arrangement by category later.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Web 1. Fractals and Chaos in Nature - Mark Cushman. Fractals and Chaos in Nature. http://the.cushman.net/reverb/fractals/ A general introductory essay.
Web 2. See the glorious works of Ken Musgrave via the Ken Musgrave page.
Web 3. Fractal Geometry and Multifractal Formalism. Classical mathematical concepts and methods are concerned with smooth objects, ignoring irregular sets . . . Four transformations in the plane are iterated as a random iterated function system (IFS) to produce a fractal attractor of the IFS -- in this case, a fern. Ignore for now the fine point about which set of four probabilities produces the highest-fidelity image. Note that you can see a blow-up of a leaf of the fern, and it would be possible to generate a leaf of that leaf, and ., ad infinitum -- all from 28 numbers!
Here is how to grow a fern!
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. As an important refinement, choose the transformations with probabilities that are relative to the areas of their associated rectangles. This process is referred to as the random iteration algorithm, or (by Barnsley) the chaos game.
*I love the VW Beetle ad: "Reverse engineered from UFOs"! (Demand now is so high that VW can't paste them together fast enough!)
Have a look at what you could have wrought! http://ccaix3.unican.es/~gutierjm/fractals.html - size 7K - 26-Mar-98
Web 303. The Fractory: An Interactive Tool for Creating and Exploring Fractals. This page will help you learn about fractals: what they are and how to design them, but it will also let you discover more on your own. Fractals are just now emerging as a science. They show an order in seemingly random things, and give us tools with which we can predict the weather, render natural looking objects, and help understand the order in our chaotic lives. You will also play a part in our interactive fractal creation center, designing and displaying fractals you have invented. You can even post your coolest fractals on our fractal message board. How to Understand Fractals: Fractals can be understood on many different levels. We have separated the information on this page into the five levels listed in increasing order of difficulty. http://library.thinkquest.org/3288/
Web 310. Chaos in the Classroom. Robert L. Devaney, Department of Mathematics, Boston University. Technology lets teachers bring some topics of contemporary interest in research mathematics into both middle school and high school classrooms. http://math.bu.edu/DYSYS/chaos-game/chaos-game.html
Web 315. Fractals page 1 Fractals. Math Index, Index, A, B, C, . , Z. Ad Hoc Fractals. After landing on the site, start by clicking Mathematics | Fractals. Has good tutorials. A must-see site! http://www.studyweb.com/math/fractal.htm
Web 320. Here is one deep zoom. A big image from the land of Mandelbrot. It takes a while to download, but it's worth it! It is probably a Julia set, generated from z = z**2 + c (with z = x + i*y, iterated in the complex plane. http://www.rosat.mpe-garching.mpg.de/fractals/bcad.gif
Web325. Fractal Landscape Gallery http://www.spence.net/ted/fractals/. Uses KPT Bryce software. See "Jesse's Cool Seascape" for a rendition of a problem that I have been considering: how to create waves and reflectionson them.
Web 330. Oliver's images. Computer generated plants generated by our plant modelling software xfrog (http://www.greenworks.de/ ) (see also Web 335 below) demonstrate the state of the art in plant generation and imaging. These plants were generated by Marco Bubke and rendered with Maya: Computer generated ecosystems created in a project for SIGGRAPH 98 where we showed that whole ecosystems can be generated and rendered with today's workstations. The models were created using xfrog, the populations were specified by additional tools. The paper is: O. Deussen, P. Hanrahan, B. Lintermann, R. Mech, M. Pharr, P. Prusinkiewicz: Realistic Modeling and Rendering of Plant Ecosystems SIGGRAPH '98, Orlando, Florida, July 19-24, 1998, http://isgwww.cs.uni-magdeburg.de/~deussen/gallery/gallery.html Be sure to see the final image of trees in a field of sunflowers -- among the finest of natural IFS images ever generated! Uses Xfrog. See also Web 335 below.
Web 335. Greenworks Organic Software, Home of Xfrog. The organic modeler: http://www.greenworks.de/ Lintermann und Deussen Gbr and the www.greenworks.de website were launched in 1996 in Karlsruhe Germany by Bernd Lintermann and Professor Oliver Deussen, with the aim to make their development efforts in the area of organic research available to the general public, i.e., publish their technical papers, and their software, XFrog. XFrog is based on mathematical building blocks of Nature, using a linked hierarchical graph of procedural nodes to build and animate(SGI only) organic models. many technical papers have been published by lintermann and deussen regarding this work and a select group of their research is available for download. At SIGGRAPHf 2000 we were excited to release our XFrog for PC product. Xfrog 3.0 is available for almost all flavors of Windows. You can download a 30 day fully functional trial version. Be sure to visit its gallery! See also Web 330 above.
Web 340. Sierpinski Gasket: http://www.swin.edu.au/astronomy/pbourke/fractals/gasket/ The Sierpinski gasket was originally described in two dimensions but represents a family of objects in other dimensions. This family of objects will be discussed in dimensions 1, 2, 3, and an attempt will be made to visualise it in the 4th dimension. Along with a few cans of Coke! See also:
. . . 3D Sierpinski Gasket (3dsg.jpg): http://www.povray.org/preview/irtc-cd3/stills/19970630/view/3dsg.htm
. . . Sierpinski Gasket: http://www.agnesscott.edu/aca/depts_prog/info/math/riddle/ifs/siertri/siertri.htm
. . . Sierpinski Gasket Generator Applet: http://www.rose-hulman.edu/~metzleda/Gasket.html Allows plotting lines, changing no. of vertices.
. . . The Sierpinski Triangle Fractal: http://www.best.com/~ejad/java/fractals/sierpinski.shtml Interactive Applet. Go ahead and play with it! Best demo of these!
. . . Sierpinski Pyramid. http://www.bearcave.com/dxf/sier.htm Variants.
. . . The Magic Sierpinski Triangle: http://serendip.brynmawr.edu/playground/sierpinski.html Order dependent on randomness. Interactive Applet.
Web 360. Fractals and the Fractal Dimension. The Hausdorff Dimension: http://www.vanderbilt.edu/AnS/psychology/cogsci/chaos/workshop/Fractals.html The "Richardson Effect". Mandelbrot Set depicted with different colors or altitudes. See also:
. . . Felix Hausdorff: http://turnbull.dcs.st-and.ac.uk/history/Mathematicians/Hausdorff.html In 1919 he introduced the notion of Hausdorff dimension, which was a real number lying between the topological dimension of an object and 3. It is used to study objects such as Koch's curve. He also introduced the Hausdorff measure and the term 'metric space' is due to him.
. . . FRACTAL HISTORY AND BACKGROUND. http://www.digitallabyrinth.com/fractals/fractals.html The most intriguing of the nonlinear fractals thus far has been the mathematical set named after Mandelbrot by the American mathematicians John Hubbard and Adrien Douady.
. . . Making Julia Set Fractals: http://www.lifesmith.com/makjulia.html Julia sets, named for the early twentieth century French mathematician Gaston Julia, who pioneered the method by which they are produced.
. . . Abram Samoilovitch Besicovitch: http://www-groups.mcs.st-and.ac.uk/history/Mathematicians/Besicovitch.html His work on sets of non-integer dimension was an early contribution to fractal geometry. Hausdorff, in 1918, had extended Carathéodory's theory of measure to sets having finite measure of non-integral order. Besicovitch, around 1930, extended his density properties of sets to those of finite Hausdorff measure. Domb writes: . . . Hausdorff and Besicovitch [were] the two mathematical pioneers on whose work Mandelbrot's development of fractals is based.
Web 370. Fractal Geometry: http://www.math.vt.edu/people/hoggard/FracGeomReport/index.html By John Hoggard.
Web 4. The World of Chaos. Introduction. Laplace's Demon. What is Chaos? The Butterfly Effect. Strange Attractors. Logistic Difference Equation. Fractals. Iterated . . . http://www.pha.jhu.edu/~ldb/seminar/ifs.html 15-Dec-97. Includes more on how to generate the fern, etc.
Web 4000. The World of Chaos and Fractals. This paper was written in conjunction with a talk given for Intermediate Physics Seminar of the Department of Physics and Astronomy at the Johns Hopkins University. It provides an excellent overview, being neither too vague nor too detailed. It includes the following pages:
. . . Introduction: http://www.pha.jhu.edu/~ldb/seminar/index.html, including:
. . . . . . Laplace's Demon: http://www.pha.jhu.edu/~ldb/seminar/laplace.html Determinism.
. . . . . . What is Chaos? http://www.pha.jhu.edu/~ldb/seminar/chaos.html Chaos is indeterminism at its best.
. . . The Butterfly Effect: http://www.pha.jhu.edu/~ldb/seminar/butterfly.html Weather prediction is difficult!
. . . Strange Attractors: http://www.pha.jhu.edu/~ldb/seminar/attractors.html Edward Lorenz started it!
. . . Logistic Difference Equation: http://www.pha.jhu.edu/~ldb/seminar/logdiffeqn.html Variability in animal populations: a simple quadratic equation, the logistic difference equation, leads to fantastically complex and chaotic behavior. Bifurcation and Lorenz and Henon attractors.
. . . Fractals: http://www.pha.jhu.edu/~ldb/seminar/fractals.html Sierpenski triangle. Fractional dimension. Snowflake curve of Von Koch.
. . . Iterated Function Systems (IFS): http://www.pha.jhu.edu/~ldb/seminar/ifs.html Black spleenwort fern. This image is infinitely complex -- a self-similar fractal on all scales.
