Iterated Function Systems (IFS)
The aim of the assignment is to give one an appreciation of (a) the difference in difficulty of a forward problem and the corresponding inverse problem and (b) how complex self-similar shapes that are seen commonly in many biological systems can arise as a result of repeated application and scaling of a few motifs.
For this we look at a mathematical idea called: Iterated Function Systems (IFS)
Formally, these define a set of linear affine transformations.
If that sounds intimidating, don't be!
It just means that they are defined by a set of rules (which are
linear functions) that tell you how to map a collection of points
in some region of space to another region of space and to do this
repetitively. The question is if one does this again and again, then
does it result in some robust pattern arising asymptotically (i.e.,
after long times, following many rounds of iteration of the process).
To see concrete examples let's look at IFS defined on 2-dimensional
space where every point is defined by its horizontal and vertical
coordinates, say x and y. Then given the initial coordinates of
some set of points x(0), y(0) one can define where they will map
in any future time by specifying a set of linear transformations
between x(n), y(n) (i.e., the position of the points at the n-th
iteration) and x(n+1), y(n+1) (i.e., the position of the points
at the (n+1)-th iteration) as follows:
x(n+1) = a x(n) + b y(n) + e
y(n+1) = c x(n) + d y(n) + f
You can of course define multiple linear transformations for the
same set of points, all of which will be applied simultaneously to
create multiple images of the set of points.
Alternatively you can define N different linear transformations
and give also the probability p_i (i= 1, ..., N such that
p_1 + p_2 + .... + p_N = 1) such that only one of them is chosen
to be applied at any given iteration - with a particular
transformation i being chosen randomly based on its probability p_i.
Now all you need to see the result of applying the IFS is to program a computer to map all points in some given interval in 2-D space to another interval based on your specification of the parameter set {a, b, c, d, e, f}. It turns out that by judicious choice of values for {a, b, c, d, e, f} you can create spectacular images - such as a object resembling a fern leaf or a snowflake - which happen to be self-similar fractals - i.e., if you magnify any part of the object to whatever scale you want, the resulting magnified detail looks similar to the whole. To generate the fern leaf you need to use 4 transformations whose parameters are:
| a | b | c | d | e | f | p | |
| Function 1 | 0.00 | 0.00 | 0.00 | 0.16 | 0.00 | 0.00 | 0.01 |
| Function 2 | 0.85 | 0.04 | -0.04 | 0.85 | 0.00 | 1.60 | 0.85 |
| Function 3 | 0.20 | -0.26 | 0.23 | 0.22 | 0.00 | 1.60 | 0.07 |
| Function 4 | -0.15 | 0.28 | 0.26 | 0.24 | 0.00 | 0.44 | 0.07 |
If you are unsure how to program the computer to do this, you can take a look at any of a number of web-pages which show how. There is a web-based program for creating the images on giving the parameter sets available at Ray Toal's IFS Renderer page, http://cs.lmu.edu/~ray/notes/ifs/
A. Write a code that computes the asymptotic pattern generated by IFS in 2-D space and use it to generate the fern leaf whose parameters are given above. This is the forward problem - i.e., given a IFS, what is the asymptotic pattern it generates ? Can you figure out what is the principle of operation by which the IFS can create such complex fractal images ?
B. Now, try to solve the inverse problem. If you are given any arbitrary image (in black and white - corresponding to presence or absence of a point in that part of 2-D space) can you figure out an IFS for generating the image ? This is obviously a much more difficult problem - and essentially corresponds to solving a problem of data compression. An image requires a lot of information to be stored if you want it completely specified pixel by pixel. If we can instead just store a number of IFS parameters and then generate the image as and when required by solving the forward problem, we will need to use a lot less computer memory. But the important question is can we have a general recipe that will work for any picture ?
Think about it. And you are free to research the web...