Iterated Function Systems
Published:
A fern can be generated from a handful of equations.
Not by drawing every leaf.
Not by storing every pixel.
By repeatedly applying a small set of transformations.
This is the idea behind an iterated function system, or IFS.
IFS fractals reveal one of the deepest themes in complexity:
a short rule can generate a vast structure.
Transformation
A geometric transformation takes points and moves them.
Examples include:
- translation,
- rotation,
- scaling,
- reflection,
- shear.
An IFS uses several transformations repeatedly.
The final shape emerges from iteration.
Contractive Maps
Classic IFS theory often uses contractive transformations.
A contraction brings points closer together.
For example, a transformation may shrink a shape to half size and move it somewhere else.
Repeated contractions can converge toward a stable set.
That set is the fractal attractor.
A Simple Example
Imagine three transformations.
Each:
- shrinks the plane by one-half,
- moves the result to one corner of a triangle.
Apply them repeatedly.
The limiting set becomes the Sierpiński triangle.
The whole fractal is encoded in three small rules.
The Hutchinson Operator
Mathematically, an IFS can be viewed as a set of maps:
[ f_1,f_2,\ldots,f_n ]
Instead of applying one transformation, we apply all of them to a set:
[ F(S)=f_1(S)\cup f_2(S)\cup\cdots\cup f_n(S) ]
Repeated application can converge to a unique invariant set under suitable contraction conditions.
The Attractor
The fractal is an attractor in a geometric sense.
Start with many different initial sets.
Apply the IFS repeatedly.
The images converge toward the same limiting structure.
Initial detail is forgotten.
The rules determine the attractor.
Sierpiński Triangle
The Sierpiński triangle can be generated by three affine contractions.
Each transformation maps the whole triangle into one smaller corner triangle.
Repeat infinitely.
The empty center pattern reproduces at every scale.
This is exact self-similarity.
The Barnsley Fern
The Barnsley fern is a famous IFS fractal.
A few affine transformations generate an image resembling a natural fern.
Different transformations create:
- stem,
- successive leaflets,
- larger branches.
The realism is surprising because the rule set is so short.
Affine Transformations
A two-dimensional affine transformation can be written:
[ egin{pmatrix} x’
y’ \end{pmatrix} = egin{pmatrix} a & b
c & d \end{pmatrix} egin{pmatrix} x
y \end{pmatrix} + egin{pmatrix} e
f \end{pmatrix} ]
The matrix controls:
- scaling,
- rotation,
- shear.
The vector controls translation.
A few such maps can create elaborate images.
Deterministic Construction
One way to generate an IFS is deterministic.
Start with a set.
Apply every transformation.
Then apply every transformation to every resulting piece.
Repeat.
The number of pieces grows rapidly.
The fractal structure becomes visible.
The Chaos Game
There is another remarkable method called the chaos game.
Start with one point.
At each step:
- choose one transformation,
- apply it,
- plot the result,
- repeat.
If choices follow suitable probabilities, the points accumulate on the fractal attractor.
Random choices generate a deterministic geometric set.
Randomness Producing Order
The chaos game is conceptually beautiful.
Each individual step may be randomly chosen.
Yet the long-term point cloud forms a precise structured image.
Randomness and deterministic constraints cooperate.
The allowed transformations define the geometry.
Probability Weights
IFS transformations can have different selection probabilities.
In the Barnsley fern, some transformations are chosen more often.
This changes how densely different regions are sampled.
The geometry comes from the maps.
The visual density also depends on probabilities.
Fractal Compression
IFS ideas inspired fractal image compression.
If parts of an image resemble transformed versions of other parts, one can store transformations instead of every pixel.
The hope is compression through self-similarity.
Fractal compression became historically important, though other methods dominate many modern applications.
Compression and Generative Rules
The deeper idea remains powerful.
A complex image can be represented not by listing all details but by storing a generative rule.
This is a form of algorithmic compression.
The same theme will return in recursion and computation.
Local Rules, Global Form
An IFS has no picture of the final fern stored inside it as a bitmap.
It stores transformations.
Iteration produces the picture.
This resembles:
- development,
- recursive growth,
- dynamical systems.
Structure is generated, not merely copied.
IFS and Natural Forms
IFS can imitate:
- ferns,
- branches,
- leaves,
- landscapes.
But resemblance does not prove that real plants literally grow by affine transformations.
The model captures geometric regularity.
Biological mechanisms are more complex.
Model vs Mechanism
This distinction matters.
A model can reproduce form without reproducing the causal process that created it.
IFS may be an excellent descriptive generator.
It is not automatically a biological theory.
Similarity of output does not imply identity of mechanism.
Exact and Approximate Fractals
IFS usually produces exact mathematical self-similarity.
Natural forms are noisy and approximate.
To mimic nature more realistically, one can add:
- randomness,
- parameter variation,
- nonlinear transformations.
The mathematical framework can be extended.
Random IFS
A random IFS allows transformations or parameters to vary stochastically.
This creates statistical self-similarity.
It can produce more natural-looking textures and branching forms.
Again, order can arise from constrained randomness.
Fractal Interpolation
IFS methods can also generate curves passing through prescribed points while retaining fractal roughness.
These are fractal interpolation functions.
They show that interpolation need not always mean smoothness.
A curve can match data and remain irregular.
Invariant Set
The central concept is the invariant set.
A fractal attractor (A) satisfies:
[ A=f_1(A)\cup f_2(A)\cup\cdots\cup f_n(A) ]
The whole is made from transformed copies of itself.
This equation expresses self-similarity formally.
Recursive Structure
An IFS definition is naturally recursive.
The whole is defined in terms of smaller versions of the whole.
This is the same conceptual structure found in:
- recursive functions,
- branching grammars,
- self-similar sets.
Geometry and recursion meet.
Why IFS Matters
Iterated function systems show how complexity can arise from:
- repetition,
- transformation,
- contraction,
- recursion.
They replace the intuition:
complex shape requires complex description
with:
complex shape may require only a compact generative rule.
From Geometry to Growth Rules
IFS generates self-similar sets through transformations.
But another family of systems models growth more explicitly.
Instead of transforming points, it rewrites symbols.
Those symbols can then be interpreted as drawing instructions.
This leads to:
L-systems.