Does anyone here know much about Iterated Function Systems and how to program them ?
They are very versatile algorithms, with which it is possible to create almost any image, given a relatively few numbers to describe that image in terms of transformations. These transformations are carried out recursively to get the final image, according to the desired accuracy. Infact an image compression technique is based on this technology. These fractals were introduced by Michael Barnsley. If you have ever used FRACTINT, it supports these beautiful fractal definitions.

Could you give a little more information about how much you already know about IFS's, and fractals in general?

When you say "how to program them" do you mean that you are trying to write a computer program from scratch that can plot a picture of an IFS, given a description of the functions that make it up? This will depend a great deal on what programming languages you are using. Have you tried using a programming language such as Visual Basic before?

David

Sorry for not replying earlier !
Yes I do want to create a program that, given the transformation constants (the matrices or otherwise), probabilities, etc is able to plot the corresponding fractal. I usually use C for graphics and can easily manage such a task in C (using Turbo C graphics libraries, and some assembly language if need be).
In fact I have tried this problem for the one involving 3 triangles, each transformed independently. It gives quite a flexible and beautiful set of fractals (which I have seen at several places, such as the Millenium Math Project logo at the bottom of NRICH articles ).
But the thing is that it didn't quite work out because I just had to guess the steps and I wasn't able to get something very similar (except for the simplest case of the Sierpinski gasket).
I have done a project in Visual Basic, but I do prefer C for simple graphics (i.e., until I learn Java).
I do know quite a bit about several different fractals, such as how to plot Mandelbrot, Julia sets, plasma, and simpler ones such as Koch curves, Peano curves, etc (all in C). I have explored quite a bit using the FRACTINT software (for windows). And I am mighty interested in fractals, including fractal compression. (I do know how several compression algorithms work).
In fact I just need a place where I can look up the exact procedure for plotting IFS.
I had also thought that such a discussion might create some interest in other students (doesnt seem so now though ?)

Thanks for replying so promptly!
Ashish

Hi Ashish, I'll do what I can, although I'm no expert I'm afraid. I presume you've got a situation whereby you have some matrices P₁ to P_n and a screen of size W by H. I think what you should do is firstly invert all those matrices. Start the algorithm with the screen set to colour 1. Now at each iteration of the algorithm, copy the contents of the screen into an array S[x][y] and clear the screen to black (colour 0). Now do something like this:

For i=0 to n
For x=0 to W-1
For y=0 to H-1
Let (u,v)=P_i ^-1 (x,y)
If S[u][v]> 0 Then Putpixel x,y,S[u][v]

When I say P_i ^-1 , you probably have affine coordinates so that you can translate as well as make linear transformations, right?

Basically, the idea is that you take the screen, transform it using each of the matrices and create a new screen by stamping out a copy of the transformed screens. That's what the above algorithm does.

If it doesn't make sense, and it probably won't because it's quite late and my brain is beginning to get fuzzy, post again with a slightly more specific query and I'll see what I can do. For example, how are you storing your transformation matrices?

Hi Dan,
Thanks for your reply here. But I doubt it that the algorithm you've outlined above would work the way I need. In fact I don't entirely understand what it will do. :( But it seems to me that what we are doing in that is finding the set of points that would transform into the set we already have, right? (Why do we take the condition S[u][v]> 0 - it would take the intersection of the 2 sets - one being calculated and other's the screen, if I am correct). But this means that the number of points on the screen would reduce after each iteration, because in IFS the transformations (mappings) are contractive, so their inverses will be expansive giving points outside our buffer. But it did give me an idea that I hadn't thought of before - trying to transform the whole plane instead of just the points - which is what I had been trying. .For example to get the Sierpinski gasket - we take a (right angled or equilateral) triangle (or three points !), scale it to half and create 3 copies translated appropriately, and then repeat for the 3 triangles and so on for the desired number of iterations or until we are limited by resolution. This is relatively easy, and I've been able to do it recursively. And I had been trying to similarly do it for other IFSes based on 3 triangles, by recursing with the points already generated - when I ran into difficulty. Because the whole plane was transformed, the transformation constants (or matrices) will also have to be changed to give an equivalent result in the smaller transformed plane. This I don't understand how to do.
Besides, the general IFS definition consists of a set of transformations (defined by giving 6 constants which make up an affine transformation) along with a probability. The total probability is equal to one. It is also very difficult to understand how these probabilities are used. For example in the IFS using 3 triangles (including Sierpinski triangle) the probabilities are equal (1/3 each). But in case of the Fern fractal (which you might have seen) I don't at all understand how the probabilities are used. Here's how it is given (in FRACTINT - a software that generates a large variety of fractals)

I'm afraid I'm going to have to get back to you in a couple of days, as my knowledge about this is very small. I can tell you what the transformations are for though. The idea, as far as I know, is to find a minimal set of transformations which the final image is invariant under. So, in this case, the first one transforms the entire image into the stem at the bottom, the last two transform it into the first and second leaves, and the second one scales it down a bit and moves it up a bit, i.e. the rest of the fern except for the stem and two leaves at the bottom. If you look at the picture, you can see that if you take the entire image and transform it in these ways you do indeed get the original image back again. The clever thing about IFS's is that whatever image you start with (as long as it's not blank), after enough iterations you'll eventually end up with the same picture, in this case the fern. I hope that makes some sense and I'll try and get back to you as soon as possible (a couple of days, since I'm going to be moving from home to university tomorrow and it'll take me a while to sort my stuff out).

Hi Dan,
Thanks for your insight into this. I do get it now, why the transformations are the way they are. But I still have the problem of how to go about plotting it ? Also how to use the probablilities, and in fact why are they there in the first place ? One new thing I tried is to choose the image space as [0,1]² instead of the screen coordinates I was using before (something like [0,200]² ). I tried to transform every point in this space a number of times (using each of the transformations, and taking a union of all the points obtained) and they do tend to settle down on the final image although very slowly and the image looks kind of crude - with holes and points that haven't still converged. Although I think that I now understand better what is happening here, but it's still unclear what would be a good way to generate the image.
Thanks for your response above. Please share any thoughts you have on this, whenever you get the time to. I am not in a hurry, but very inquisitive and interested in getting this done right! So take your time. I appreciate your help.
Ashish

The fern is slightly fatter than you normally see, but there is a reason. If you use the non probabilistic approach, the set of points in the set shrinks each time, so the more you run the program the closer it will get to the fern, but it will always be "fatter" than the true fern. The probabilistic approach (which I'll describe in a minute) does it the opposite way round, after each iteration it gets fatter but it will always be thinner than the true fern. Here is what I got using the probabilistic method:

The idea of the probabilistic method is that you take the point x=1,y=1. Then you repeatedly apply a random transformation to (x,y) (using the probabilities given) and plot that point. The one above has 100,000 points plotted.

I found this web page which showed me what I was doing wrong (it's Barnsley's original program). There's a better version here . I found some stuff on fractal compression here which is quite readable. Unfortunately, most web pages I found on fractal compression seem to not be very accessible for anyone without an understanding of at least university level maths, with talk of Hausdorff metrics and the like.

I hope that answers your questions, but feel free to post any other questions if they arise, I've included the source code for my programs.

By the way, the above programs are C++ programs and use the graphics library Allegro for the free DJGPP compiler. However, you should be able to easily modify them to work with whatever graphics library you are using.

Wow!! That's really great Dan! That's a lot of information you have given here, I'm trying to absorb as much of it now, as I can. I had tried to find some web references through a search engine, but come up with nothing very useful (except a lot of image galleries). Thanks for your references and your program. I'll study them and get back to you if I have a problem (which shouldn't be so, since I have the code now). Well, I can't thank you enough for your ample effort. I'll tell you where I get with all this.

Ashish