iterated function system

Sometimes written as IFS. Pretty much what each word means. Either a function or set of functions which may be applied iteratively to produce output which seems far more complex or intricate than the functions or input themselves. Examples include the rules for making a Sierpinski triangle, a Koch snowflake, and many L-systems. In a very odd way, you may consider the game of life to be an IFS where the rules map an infinite plane of cells to an infinite plane of cells, but this is a bit of a stretch. Iterated function systems are very much tied to ideas of fractals.

A type of fractal that can be used for fractal image compression. IFS stands for Iterated Function System. Often generates objects which look like natural objects. e.g. ferns, trees, snow flakes

An IFS has a few functions, each of which transform a point to another location. Each of these functions have a probability of occuring. Starting with one point the transformations are performed at random (keeping with the probabilities) and the IFS attractor (picture/object) emerges.

An iterated function system (IFS) is a function or set of functions which operate on data repeatedly. Often, the input and/or functions are kept simple so as to be more easily analyzed. Some examples of IFS include the dragon fractal, Sierpinski triangle, Koch curve, L-systems and the Mandelbrot set. By way of example, below is the Sierpinski triangle followed by another similar fractal shown step by step (for three steps each):

________________
|              |
| |_           |
|              |
|              |
|              |
|              |
|              |
|              |
----------------
________________________________
|              ||              |
| |_           || |_           |
|              ||              |
|              ||              |
|              ||              |
|              ||              |
|              ||              |
|              ||              |
--------------------------------


________
|      |
|      |
|      |
|      |
--------
________________
|      ||      |
|      ||      |
|      ||      |
|      ||      |
----------------
________        ________
|      |        |      |
|      |        |      |
|      |        |      |
|      |        |      |
--------        --------
________________________________
|      ||      ||      ||      |
|      ||      ||      ||      |
|      ||      ||      ||      |
|      ||      ||      ||      |
--------------------------------


____
|  |
|  |
----
________
|  ||  |
|  ||  |
--------
____    ____
|  |    |  |
|  |    |  |
----    ----
________________
|  ||  ||  ||  |
|  ||  ||  ||  |
----------------
____            ____
|  |            |  |
|  |            |  |
----            ----
________        ________
|  ||  |        |  ||  |
|  ||  |        |  ||  |
--------        --------
____    ____    ____    ____
|  |    |  |    |  |    |  |
|  |    |  |    |  |    |  |
----    ----    ----    ----
________________________________
|  ||  ||  ||  ||  ||  ||  ||  |
|  ||  ||  ||  ||  ||  ||  ||  |
--------------------------------

---

________________
|            _ |
|           |  |
|              |
|              |
|              |
|              |
|              |
|              |
----------------
________________________________
|              ||              |
| |_           ||              |
|              ||              |
|              ||              |
|              ||              |
|              ||              |
|              || _|           |
|              ||              |
--------------------------------


________________
|      ||      |
|      ||      |
|      ||      |
|      ||      |
----------------
________
|      |
|      |
|      |
|      |
--------
________                ________
|      |                |      |
|      |                |      |
|      |                |      |
|      |                |      |
--------                --------
________________________________
|      ||      ||      ||      |
|      ||      ||      ||      |
|      ||      ||      ||      |
|      ||      ||      ||      |
--------------------------------


________________
|  ||  ||  ||  |
|  ||  ||  ||  |
----------------
____        ____
|  |        |  |
|  |        |  |
----        ----
____
|  |
|  |
----
________
|  ||  |
|  ||  |
--------
________                ________
|  ||  |                |  ||  |
|  ||  |                |  ||  |
--------                --------
____                        ____
|  |                        |  |
|  |                        |  |
----                        ----
____        ________        ____
|  |        |  ||  |        |  |
|  |        |  ||  |        |  |
----        --------        ----
________________________________
|  ||  ||  ||  ||  ||  ||  ||  |
|  ||  ||  ||  ||  ||  ||  ||  |
--------------------------------

---

With the three-way IFS above, many of the fractals that are produced are simple reflections or restatements of each other. Out of 512 possible fractals, only 200 or less are unique for this particular IFS form.
I worked in the extra spaces above to make sure that the overall idea is clear.

Random iterated function system algorithm

The random iterated function system (IFS) is a very simple algorithm that can easily produce a large variety of fractals including but not exclusively cantor's set, serpinskis, dragon curves, koches and many others.

The algorithm is based around the use of transformations, namely axis rotation, translation and scaling. These transformations are used to draw the attractor pointwise (one point at a time). The generalisation resulting from using transformations means that these fractals can be drawn in an arbitrary number of dimensions.

The transformations are usually expressed as matrices, either as a single homogeneous matrix or a matrix for scaling and rotation and one for translation.

The algorithm also uses a weight for each of the transformations. The weight for each is either proportional to the determinant of the matrix or a small value for cases where the determinant is zero. The total of all the weights should add up to one. These weights can then be used a probabilities for picking a particular transformation. This weight is not strictly necessary but it does improve the performance of the algorithm a great deal.

Each IFS fractal is described as a weighted list of transformations. Amazingly only two transformations are necessary to produce a wealth of nice fractals but the more complex ones will require more. The ubiquitous fern requires four: the stem, left leaflet, right leaflet and the overall shape.

The probability of a given transformation being picked is found using the determinate of the transformation. The determinates are totalled up and each of the individual determinates are divided by this total. This results in a probability out of one for each of the transformations and a total probability of one for all the transformations. If a transformation has a determinate of zero (a pure rotation for example) it should be given a low but non-zero probability e.g. 0.01.

As previously stated the algorithm is very simple:

Start with a point at the origin P = (0,0)
FOR however many points you want DO

Pick a transformation, T, from the list with probability p(T)

Apply it to the point P = T*P

Draw the point p
END

Some of the literature suggests that you discard the first hundred or so points to give the algorithm a chance to converge to the attractor. I, personally, have never found this necessary as often the origin lies on the attractor anyway and if it doesn't who's going to notice a few stray points in the maelstrom this algorithm produces. I've never been able to spot more than three but I guess it depends on the application.