On this is a page I describe the development of my computer program ConjurePicture (ConjPic for short) for the creation of images using Iterated Function Systems (a branch of Fractal Geometry). As well as showing some of the resulting images, I will show some of the itermediate template images that are used to generate those images.
Big Logo is an example of an image generated. using ConjPic. For a summary of how that was done, visit the Big Logo page.
Go Home .
C:\ConjArt\Art.rtf 20-Mar-00
The Art of Fractal Imagery Using Iterated Function Systems and ConjPic® By Wayne R. Paulson
(Partial draft.)
Contents
This draft version is incomplete, for the following reasons:
(a) Much of the text of the initial part of the document has been incoporated into the page
Fractals and Iterated Function Systems (IFS), which you are advised to read before reading this page.
(b) I have more to write yet!
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Directory of fractal images produced by ConjPic for this document only . See below.
. . . 1.1 Preamble
. . . . . . 1.1.1 The varieties of language misunderstanding
. . . . . . 1.1.2 American English vs British English punctuation
. . . . . . 1.1.3 English-to-English translation
. . . 1.2 Introduction to the concepts of fractals and IFS
Chapter 2: Mathematics of fractals and IFS
. . . 2.1 Fractals and the Mandelbrot Set
. . . 2.2 Generating the Mandelbrot Set by iteration
. . . 2.3 Iterated Function Systems (IFS)
. . . 2.4 Chaos is not randomnes
. . . 2.5 Interpretations of the image-generation process
. . . 2.5.1 How to generate the image
. . . . . . 2.5.1.1 Contractivity
. . . . . . 2.5.1.2 Affine transformations
. . . . . . 2.5.1.3 Specifying the IFS and its transformations
. . . . . . 2.5.2 Choosing the transforms that will generate a given image
Chapter 3: Building a maple leaf (Page ConPic32.)
. . . 3.1 Why build a maple leaf?
. . . . . . 3.1.1 Building a twig
. . . . . . 3.1.2 Building our first tree
. . . . . . 3.1.3 Building a maple leaf
. . . 3.2 A botanical garden grown from IFSs!
Chapter 4: The ConjPic® program (Not yet written.)
. . . 4.1 Overview of ConjPic®
. . . 4.2 General capabilities of ConjPic®
. . . 4.3 Detailed features of ConjPic®
. . . 4.3 Log of fixes to and additions to ConjPic®
Chapter 5: Building a spiral galaxy (Not yet written.)
. . . 5.1 Why build a spiral galaxy?
. . . 5.2 At the galaxy at last
. . . 5.3 Spin faster, galaxy!
. . . 5.4 Now, for a warped view!
. . . 5.5 Supernova!
. . . 5.6 Around the horn of plenty
Chapter 6: Building a mountain (Page ConPic40.)
. . . 6.1 Why build a mountain?
. . . 6.2 How to build a mountain
To be continued . . .
Directory of fractal images produced by ConjPic for only the document The Art of Fractal Imagery Using Iterated Function Systems and ConjPic®
For fractal images additional to these, see Directory of all fractal images.
Images for each of the following were each generated from one or more iterated function systems (ifs). Each ifs, in turn, is represented by a fractal template. Although these templates are not listed separately in the following, they are presented adjacent to (usually following) the corresponding image or picture.
Figure T1Twig1I.gif. Image of twig
Figure T1Twig2I.gif. Image of twig, rendering 2 stems
Figure T1Tree1I.gif. Image of tree1
Figure T1Tree2I.gif. Image of tree2, rendering 2 stems
Figure Mount1.jpg. Snow on green mountain
Picture MtSand1.jpg. Sand and mountains at dawn
Picture MtCld1.jpg: Mountain with low cloud
Picture MtCld2.jpg: Mountain with low cloud again
Picture MtSnow2.jpg: Snowy mountain with basic water shimmer
Go to Table of contents near top.
The Art of Fractal Imagery Using Iterated Function Systems and ConjPic
1.1 Preamble
My aim in this book is to introduce you to the art of using Iterated Function Systems (IFS) as a new means of artistic expression. As a means of illustrating this book and as a an artist’s tool should one wish to pursue that craft, I wish to illustrate the basic capability of a computer program that I am writing for the generation of images, pictures, stereograms, and movies. The program is called "ConjurePicture®", or "ConjPic®" for short.
The program makes use of a branch of Fractal Geometry called Iterated Function Systems (IFS).
This is the first in a series of chapters that are to form two guides for the use of the ConjPic® program. The other book might be entitled "User Guide to ConjPic® Program for Generating Fractal Images".
1.2 Introduction to the concepts of fractals and IFS
This first chapter involves both a general description of the mathematical basis for being able to generate such images, interspersed with practical illustrations of our initial progress toward building a leaf from the ground up. This should form a firm basis for exploring additional techniques and types of images in future chapters. To obtain a sufficient understanding of the procedures, it will be necessary to delve into the major mathematical ideas; however, this will be kept to a minimum. Links will be provided to sites on the Web where one can feast on the mathematical details if one wishes and to sites where one can wander through galleries of fractal art.
A cautionary note: the many sites on the Web that deal with what is termed fractal art deal mostly with elaborations of the Mandelbrot set and its close cousins, Julia sets and Fatou dusts, and with Newton-basin and Lorenz attractors, and others. Many of these images are generated by the famous program Fractint, written by the collective, the Stone Soup Group. As sketched briefly below in relation to the Mandelbrot set, these efforts are primarily iterations of a primary equation, a quite simple one in the case of the Mandelbrot set. As such, they do not usually try to produce images of natural forms. In contrast, my primary interest is to employ IFSs to create natural forms that can be rendered to appear as either photographs or paintings. This rendering can be achieved with the ConjPic® program on its own. That is not to restrict the possibility that such images could be subject to further rendering and manipulation by such programs as, for example, Adobe Photoshop in the Windows world or the GIMP in the realm of Linux and the Open Software Foundation. Notwithstanding this interest in natural forms, the program can also be used to create abstract images and, in general, any kind of image.
I hope that, with this program, you will develop the ability to create your own paintings, not by using electronic brushes and virtual canvas, as in most paint programs, but rather by manipulating transformations of basic shapes—building blocks, so to speak. In this way you become an artist using the techniques not of brushstrokes, but in the manipulation of forms themselves—a kind of meta-artist! In the process of conjuring up an image with ConjPic®, you will literally see basic forms such as simple rectangles metamorphose into swirls of images of many kinds. These are images that will arise from what, in slow motion, would appear to be a fog of randomly painted pixels, a procedure for which the apt term "fractal forgery" was coined by the founder of IFS, Michael Barnsley, about whom more below.
Chapter 2: Mathematics of fractals and IFS
2.1 Fractals and the Mandelbrot Set
2.2 Generating the Mandelbrot Set by iteration
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. See http://www.unity.force9.co.uk/fractals/.
The Mandelbrot Set Explorer. Discover the wonderful world of color that surrounds the famous Mandelbrot Set. http://www.mja.org.mx/Prometeo/ejemplos/mndlbrt.html.
2.3 Iterated Function Systems (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. 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/ .
As an introduction to IFSs, we consider the Sierpinski Gasket. 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? For the answer and additional explanation, click on the following site: http://cs.heritage.edu/cpsc/302/gasket.htm.
There are various ways of generating the Sierpinski Gasket. What follows is the method of IFSs that I shall be pursuing. Let us start with another approach to generating the Sierpinski Gasket—one that appears to be different, but which is equivalent in its results. It will be almost as simple as the above case because, after all, we are going to use building blocks, just like kids again! Consider the figure that I have generated using ConjPic®, as shown in the following figure T1Sier1T.jpg.
Because of limited space on the server, I will summarize this figure instead of using up to 33.3 KB of a gif file to display it.
Figure T1Sier1T.jpg. Template for inverted Sierpinski Gasket. It consists of a (a) seed square, a square just slightly smaller than the picture box itself, (b) two squares, reduced copies of the seed, each one half the width of the picture box, cenetred side by side in the top half of the box, and (c) centered underneath them, a third copy of the seed.
[C:\Program Files\hjpro\bin\T1Sier1T.jpg (18 KB)]
As promised, it consists of three building blocks or, as I shall call them, tiles—two in the top half of the picture box and one centered in the bottom half. They are in the colors of magenta (pink), yellow, and green, respectively. What could be simpler? Each tile is a transformed copy of what I shall call the seed tile.
The seed tile is shown in green and is just slightly smaller than the picture box. Note that I am denoting the above figure a "picture box", and not a "picture". We will define below what is meant by a picture. The contents of the "picture box" is, again, not a "picture", and not an "image", but a "template". (You can barely see the seed at the edges of the picture box, with small quarter-circles denoting the seed corners.) Each of the three tiles is about one quarter the size of the seed tile in area, or one half the size in linear dimensions. That the size of each tile is smaller than the seed is of crucial importance, as is discussed later.
Now let’s play the same game as above, except that instead of A, B, and C representing the positions of vertex points, they are to represent the transformations of the seed tile into the smaller tiles. Let’s label the tiles A, B, and C, proceeding from the one at top left , clockwise. The ConjPic® program now chooses at random either A, B, or C (with equal probability in this case), and starts plotting points after iterating (and not plotting) the first 200 points. At each stage, it picks the appropriate transformation at random, applies it to the present point, and plots the next (iterated) point, in the color assigned to that tile or transformation. For the result, see the following figure T1Sier1I.jpg.
Figure T1Sier1I.jpg. Image of inverted Sierpinski Gasket. The resulting image would be the same as the Sierpinski Gasket in the following, but upside down: http://serendip.brynmawr.edu/playground/sierpinski.html
[C:\Program Files\hjpro\bin\T1Sier1I.jpg (59 KB)]
All plotted points converge onto the resulting image, the so-called attractor of the IFS. One could 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 three rectangles or three profiles of the Volkswagen Beetle, one would end up with the same image. Why? Because the equations describing the transformations are invariant in relation to the particular shape of the seed image (rectangle) used as illustration. Iteration of the IFS converges to its unique attractor. In other words, the resulting image is the attractor of the IFS. 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. In the present case of the Sierpinski Gasket, the probabilities are all equal. In general, they are not.
It might seem that the next few paragraphs are a digression; however, they will help to lead to an understanding of how and why certain IFSs lead to certain final images. It will also help in gaining an insight into an even more difficult problem: namely, how does one construct an IFS that will produce a given image. (That problem has been solved (and patented) by Michael Barnsley and is incorporated into the proprietary software and hardware (including fast add-on boards) of Iterated Systems, Inc.)
2.4 Chaos is not randomness
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.
2.5 Interpretations of the image-generation process
It may take some time and some lateral thinking to appreciate the two major processes involved in IFS image generation. On the one hand, we want to know how to choose the transformations that would produce a given image. In particular, how would we know, or just guess, that the three blocks in the above figure would produce the Sierpinski Gasket? As with some mathematical concepts, that might be either immediately obvious to you, or it may be totally incomprehensible, even after some explanation. Do not despair. It may take some time for an understanding to develop, until it suddenly clicks. It did with me. That time could be a few minutes or a few weeks!
The second major concept that we need to understand is that, given a particular IFS, how is the image generated from it? Although it may seem backward, let us deal with this case first, as I think that it is the easier and more immediate of the two.
The mathematical basis establishing that these two processes are possible in theory was derived and proven rigorously by Barnsley and others, including Demko, within the past twenty years. It involves metric space theory, affine transformations, Haussdorf-Besicovitch dimension, Haussdorf distance, measures on Borel sets, Cauchy limits, the important Collage Theorem, and some other mathematical niceties. Barnsley sets them out rigidly in about 380 pages of his book "Fractals Everywhere". For our purposes, we do not need to understand much of that theory, nor invoke much of its jargon, but we do need to gain an insight into the practical ideas that are needed to implement it. So here goes.
2.5.1 How to generate the image
2.5.1.1 Contractivity
The primary requirement for all of this work is that each transformation of the seed shape into its associated tile involves a contraction in size. In our case of the Sierpinski Gasket, each tile is one half the size of the seed in both horizontal and vertical directions. So, in the dice-tossing game, we kept generating a new point, say Pnew, by choosing its position as being half way from its present position, say Pold, to one of the vertices, A, B, or C that was determined at random by the roll of the die. Consider what would happen in the extremely unlikely event that the die always came up A? We would then keep plotting points in a straight line proceeding toward A, with steps that became half as long each time. If you have ever heard of Zeno’s paradox, you will be aware that part of the paradox is equivalent to asking the question "Will we ever arrive at the point A?". The answer is that we will approach A to within an ever-decreasing distance that approaches zero as the number of steps increases without limit, i.e., approaches infinity. But, we never actually reach A exactly, Very importantly, we never get beyond A! If we did get beyond A, it means that we would never achieve an image. Instead, we would get an explosion that could fill the entire universe! Talk about the Big Bang! A more subtle concept, involving Cauchy sequences, arises when we deal with the rate at which such decreases in step size occur, or the degree of convergence toward a limit.
2.5.1.2 Affine transformations
A second fundamental requirement for both processes is that the transformations be affine. That means that each tile generated from a seed must be either similar to or identical to the seed in its shape, and the boundary of the tile must be continuous, i.e., have no gap. In our case of the Gasket, the tiles are identical to the seed, but reduced in size by half. So, we have the special case that the tiles are not only similar in shape to the seed but are identical to it. In general, the tiles need not be identical; however, they must still obey the following general rules. First, the tile must be smaller than the seed. The tile can then be translated in any direction, while retaining its shape. The tile could be rotated about its corner or center, while retaining its shape. Or the tile could be sheared. That is, the tile could be distorted in such a way that opposite sides remain parallel if they were parallel to begin with. This could be denoted as an affine shear transformation. One can apply any or all of these transformations of the seed shape to obtain the resulting tile shape, size, and orientation. One can specify any such overall affine transformation of the seed shape into a tile shape using two equations involving two unknowns and six parameters, as set out below.
2.5.1.3 Specifying the IFS and its tranformations
To summarize:from the above two sections, 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 the single "images" that we have been producing in this chapter.
For our purposes, a "picture" would consist of a set of separate "images", usually overlayed partly on top of or beside each other, and all of which, in turn, are overlayed on top of background fields of variable color, usually representing sky, water, sky reflected in water, or ground. Each "image" is a separate IFS, independent of the other "images". Even after a "picture" is composed and portrayed in this way, we will still have control over each "image" of which it is comprised, that is, the ability to further modify each "image" independently of the others.]
See Fractals for the mathematics of setting up an IFS.
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 Fractals and then on http://www.astro.virginia.edu/~eww6n/math/Barnsley'sFern.html.
2.5.2 Choosing the transforms that will generate a given image
It may seem like one step backward; however, let us generate the simplest IFS and its generated image, both in the following figure T2LineTI.
Figure T2LineTI.jpg. Template for, and image of, straight line (diagonal).
The picture contains (a) a seed square, just slightly smaller than the picture box, (b) two squares, each generated from the seed and half its size in lnear dimension -- one near the lower left corner, the other near the top right corner of the box, and (c) the resulting image generated from those squares -- a straight line from near the lower left corner of the box to near its top right corner.
[C:\Program Files\hjpro\bin\T2LineTI.jpg (24KB)]
Here, the two transforms, in black and white, generate a single straight line at about a 45-degree angle. Unlike the previous cases, we have here used an IFS of only two transforms, consisting of four linear equations, to generate a straight line. We must admit that this is overkill, in that we could have generated the straight line with only a single linear equation of the form y = a * x + b, where a represents the slope of the line and b its intercept on the y axis. As a feature additional to those of the preceding figures, note that in the bottom right corner of the caption is a value, 492.5, of CR. CR is the data-compression ratio of the number of points plotted from the IFS to the amount of input data in bytes. The figure preceding it indicates that we have plotted 29,552 points, as generated directly from the IFS. Note that this number of points is not the same as the number of points shown in the above figure, because of an additional stage of data compression (JPEG) that is involved, as detailed in the next paragraph. To emphasize this distinction, let us refer to the CR as being the Fractal Compression Ratio (FCR), i.e., FCR = CR. It is notable that we have achieved a Fractal Compression Ratio of 492.5. Most image-compression techniques, including JPEG, achieve figures of between 10 and 40.
The subject of data compression will be dealt with in more detail later, as it deserves more than a paragraph. For now, note that the figures as shown in this document have undergone two stages of data compression. The first stage is what we shall term Fractal Data Compression (FDC). Its effects were as stated in the preceding paragraph, where we stated that the CR, alias FCR, value was 492.5. The second stage of compression comes into play when we display a representation of that plotted image as a figure in this document. That is why I have been careful not to refer to the figures as seen in this document as the plotted images. Instead, the figures shown here are only a representation of the images as originally plotted on my computer. The difference is that the image as originally plotted is stored as a bitmap (of 1,000 by 1,000 pixels = 1,000 KB) in a bitmap (BMP) file before it is then compressed by another program (HiJaak Pro®) into a Joint Photographic Experts Group (JPEG) image file. JPEG is a particular form of compression that exploits the fact that there are redundancies in most original images (such as, for example, a straight line of pixels, all of the same color). Let us refer to the compression ratio produced by this JPEG stage of compression as the JPEG Compression Ratio (JCR). By definition, the value of JCR is the ratio of the size of the BMP file to that of the JPEG file.
We define the combined effects of these two stages to be the Total Compression Ratio (TCR), where TCR = FCR * JCR. At the risk of some repetition, let us summarize these effects by expanding on the case of the T2LineTI.jpg figure referred to two paragraphs above. In this case, JCR = (1,000 KB BMP file size )/ (24 KB JPEG file size) = 41.6667 . Thus, TCR = FCR(= 492.5) * JCR(=41.6667) = 20,520.83. In the field of computer graphics this is a huge compression ratio! It is notable, too, that although we may not have much, if any, control over the degree of JPEG compression, we can easily choose the degree of fractal compression, by simply increasing the number of plots to be generated. More precisely, we would increase the density of points to be plotted. The ConjPic® program then calculates the actual number of points to plot. That is why some of the figures for number of points plotted, as shown in the caption bars for most figures, are not nice round numbers.)
. . . Contiued at Chapter 3: Building a maple leaf. (ConPic32)
Go Home. Go up to Table of contents near top.
You can e-mail me at waynerp@sympatico.ca
