Iterated Function Systems


Technical Description

The description given here is based on the extended mathematical development given in Barnsley's 1988 work, Fractals Everywhere, which is highly recommended to anyone with an interest in fractals and a modest mathematical background.

The AFFINE TRANSFORMATIONS referred to above consist of a linear part and a translation, thus:

T(x,y) =	[a b] (x) + (e) = (ax + by) + (e) = (ax + by + e)
		[c d] (y)   (f)   (cx + dy)   (f)   (cx + dy + f)

where (x,y) is the point transformed by transformation T, which consists of matrix abcd and vector (e,f).

As described, such a transformation maps points to points, but it may also be thought of as mapping SETS of points to SETS of points. The result of applying a transformation to a set is simply the set of all the points that result from applying the transformation to each of its points. In fact it is possible to define a METRIC (distance function) on sets and consider a space of sets analogous to the plane as a set of points (a space is a set of elements together with a distance function telling you how far apart any two elements are). Just as one calculates the distance between two points in the plane using the formula [(x1-x2)^2 + (y1-y2)^2]^1/2, there is a method for telling how far apart two sets of points are -- which in fact roughly agrees with their similarity in shape. Thus, we can imagine an affine transformation as a mapping from elements of a space of sets to other elements which may lie in different parts of the space (separated by a various distances).

Furthermore, given several transformations, one may consider the result of applying all of them to each point in a given set. This result will in fact simply be another set (consisting of the union of all the possible resulting points), and so the entire system of transformations (henceforth iterated function system, or IFS) may be thought of as a single function mapping points (i.e. sets) in a space of sets to other points.

If one specifies the parameters of the IFS in a certain way, it will have the property that it is a CONTRACTION. This means that given any two points, say p and q, the results of applying the IFS to the two points will be closer together by a certain factor c - that is, d(f(p),f(q)) < cd(p,q), where c is a constant less than 1. In terms of the space of sets, a contraction will map any pair of sets to another pair that is more similar.

Forgetting about sets for a moment, there is a very interesting property that contractions have which is that if you start from any point and iteratively apply a given contraction to it, the results will always converge to the same point, called the ATTRACTOR of the contraction. To see why this is, consider a sequence of points x1,x2,x3,... obtained by applying a contraction f to an initial point x0 -- that is, x1 = f(x0), x2 = f(x1), and so on. Since x2 = f(x1) and x1 = f(x0), the contraction property implies that d(x2,x1) < cd(x1,x0). This relation is true for any points in the sequence, so d(xn+1,xn) < cd(xn,xn-1) -- the successive points in the sequence must keep getting closer together. In fact, the distance between successive points must eventually drop to zero. That is, we reach a point x (= xN for some N) for which f(x) = x. This point is the attractor. It is easy to see that it doesn't depend on where you start from -- if there were two points, x and y such that f(x) = x and f(y) = y, then the contraction property would imply that d(x,y) < cd(x,y), which can only happen if d(x,y) = 0, that is x = y.

Now it is possible to define an IFS such that it is a contraction on the space of sets discussed above. This IFS will have an attractor, which in this case will be a set, and it is this set which, plotted as a set of points in the two-dimensional plane, is the IMAGE generated by the IFS.

One way to actually generate and plot this image is suggested by the argument given above to prove there is an attractor. Simply start from any point in the space of sets and apply the IFS to that point. Store this new set and apply the IFS to it, store that, and so on. After some number of repetitions the distance between successive sets will be small, and so the result is an approximation to the attractor as described above.

This method is somewhat impractical, since it involves a large amount of storage and computation. At each iteration, the entire set must be stored, at some finite resolution. And each affine transformation making up the IFS must be applied to every single point to generate the next set. But suppose we choose a single point that happens to lie in the attractor set. Then any of the transformations we apply to it will give another point in the attractor (remember that the result of applying ALL the transformations to every point in the attractor will give the set of points in the attractor and nothing else), and any of the transformations we apply to this point will give another point in the attractor, and so on. In fact, if we choose a sequence of transformations randomly, we will obtain a corresponding sequence of points in the attractor, and if we choose a long enough sequence, we will end up visiting every point in the attractor (at a given resolution). Why? Because in fact the single point we started with is a set, and so a sequence of applications of the entire IFS to that set will converge to the attractor. The sequences of single transformations we choose simply "fill in" the possible paths that points take within that sequence of sets.

This explains the mystery of how a pattern can emerge from random choices of transformations -- the pattern is the attractor which must be reached in any iterative process. However, the question remains as to why and how it is that these attractors -- random mathematical objects as they are -- possess structure that the human eye finds beautiful. This highly interesting question will be discussed in a future work.




Method of Parameter Generation

Several different types of constraints are employed in generating transformation parameters, based on the properties of linear transformations. They are described below.

TransType	  Description
---------	  ----------- 

Fully random	  All numbers chosen randomly in range -0.5 to 0.5.

Fully symmetric	  Odd-numbered transformations are chosen randomly as
		  above, even-numbered ones are determined by simply
		  reversing the signs of the preceding odd ones.  This
		  infuses some symmetrical structure into the image.

Rand. symmetric	  Every fourth transformation is chosen randomly, and
		  the other three have the same entries as this one but
		  with a random sign.  This infuses a degree of partial
		  symmetry into the image.

Rotational,	  The linear part of the transformation is constrained
const. radius	  to be a pure rotation about the origin, with no
		  scaling.

Rotational,	  The linear part of the transformation is constrained
rand. radius	  to be a rotation about the origin coupled with a
		  scaling uniform in each dimension.

Hybrid		  This generates a set of transformations consisting
		  of some fully random and some randomized rotational
		  ones.

Fern		  This selects the set of parameters used by Barnsley
		  to generate the fern leaf.




Back to Randim page.
Back to Adrian's home page.