IFS: Iterated Function Systems and Fractal Attractors
The Barnsley fern looks indistinguishable from a real fern frond, yet
it is generated by just four simple affine transformations applied
randomly in sequence. Iterated Function Systems are one of
mathematics' most beautiful surprises: an infinitely detailed
self-similar structure encoded in a handful of numbers. Apply the same
contractions over and over — to a point, to a set of points, to an
entire image — and the same fractal attractor always emerges,
regardless of where you started.
1. Contraction Mappings and the Fixed-Point Theorem
The mathematical engine behind IFS is the
Banach Fixed-Point Theorem (also called the
Contraction Mapping Theorem). It guarantees that any contractive
transformation has a unique fixed point — and that repeatedly applying
the transformation converges to that fixed point from any starting
position.
// Contraction mapping definition A function f : X → X is a
contraction mapping if: d(f(x), f(y)) ≤ c · d(x, y) for all x, y ∈ X,
and some c ∈ [0, 1) Where: d(·,·) = distance metric c = contraction
ratio (smaller = faster convergence) Banach Fixed-Point Theorem: If X
is a complete metric space and f is a contraction: → f has a UNIQUE
fixed point x* such that f(x*) = x* → for any starting point x₀, the
sequence x₀, f(x₀), f²(x₀),... converges to x* at rate cⁿ Example:
f(x) = 0.5x on ℝ Fixed point: x* = 0 Starting from x₀ = 100: 100, 50,
25, 12.5, ... → 0
For IFS, the relevant metric space is not ℝ but the
space of compact subsets of ℝ², equipped with the
Hausdorff metric — the maximum distance you'd need to
"drag" one set to cover the other. In this space, applying a set of
contractions simultaneously is itself a contraction, and its fixed
point is the fractal attractor.
2. IFS Definition and the Attractor
An Iterated Function System consists of a finite set
of contraction mappings on ℝⁿ, usually affine transformations:
// An IFS is: {f₁, f₂, ..., fₙ} where each fᵢ is a contraction // Each
fᵢ is typically an affine map: fᵢ(x) = Aᵢ · x + bᵢ Where: Aᵢ = 2×2
matrix (scaling, rotation, shear) bᵢ = 2D translation vector
Constraint: all eigenvalues of Aᵢ have magnitude < 1 (contraction)
// The IFS attractor A is the unique compact set satisfying: A = f₁(A)
∪ f₂(A) ∪ ... ∪ fₙ(A) Intuition: A is the set that maps to itself
under all transformations simultaneously. It is the "union of n scaled
copies of itself" — self-similarity by definition. // Convergence:
starting from ANY compact set S₀: S_{k+1} = f₁(Sₖ) ∪ f₂(Sₖ) ∪ ... ∪
fₙ(Sₖ) S_k → A (in Hausdorff metric, exponentially fast)
The attractor is unique and independent of starting point.
Whether you start from a single point, a filled square, or a random
scribble — after enough iterations, the orbit converges to the same
fractal attractor A. The IFS acts as a "recipe" that specifies the
attractor implicitly through the self-similarity equation A = ∪ fᵢ(A).
3. The Chaos Game Algorithm
The deterministic approach (applying all fᵢ to every point each
iteration) requires tracking exponentially growing sets. The
chaos game is a probabilistic algorithm that plots
the attractor efficiently by tracing a single random orbit:
// The Chaos Game (Barnsley 1988) 1. Start with any point x₀ ∈ ℝ² 2.
Repeat N times: - Choose transformation fᵢ at random with probability
pᵢ - x_{n+1} = fᵢ(x_n) - Plot x_{n+1} (skip first ~20 iterations for
warm-up) Properties: - Probabilities pᵢ are arbitrary (any pᵢ > 0
works for convergence) - Natural choice: pᵢ ∝ |det(Aᵢ)| (proportional
to the area it covers) → uniform density on the attractor - After
N=100 000 iterations, the attractor is visible to the eye - After N=1
000 000 iterations: high-quality rendering Time complexity: O(N) —
renders any IFS fractal in milliseconds // JavaScript skeleton: let x
= 0, y = 0; for (let i = 0; i < 1e6; i++) { const f =
chooseTransform(); // random, weighted by probability [x, y] =
applyAffine(f, x, y); if (i > 20) plotPixel(x, y); }
4. The Barnsley Fern in Detail
Michael Barnsley's fern (1988) is the iconic example — four affine
transformations that produce a structure visually identical to a
Blechnum spicant fern frond, down to fine vein detail:
// Barnsley Fern — 4 affine transformations (x' = ax + by + e, y' = cx
+ dy + f) // a b c d e f prob meaning //
──────────────────────────────────────────────────────────────────────────
f1: [ 0.00, 0.00, 0.00, 0.16, 0.00, 0.00 ] p=0.01 // stem f2: [ 0.85,
0.04, -0.04, 0.85, 0.00, 1.60 ] p=0.85 // main frond (scaled copy) f3:
[ 0.20, -0.26, 0.23, 0.22, 0.00, 1.60 ] p=0.07 // left leaflet f4:
[-0.15, 0.28, 0.26, 0.24, 0.00, 0.44 ] p=0.07 // right leaflet
Interpretation: f1: contracts entire fern to a tiny stem segment at
the base f2: copies the entire fern at 85% scale, slightly rotated →
main frond body f3: takes the fern, rotates 83° CCW, scales to 30% →
small left leaflets f4: takes the fern, rotates 37° CW, scales to 37%
→ small right leaflets Self-similarity equation: Fern = f1(Fern) ∪
f2(Fern) ∪ f3(Fern) ∪ f4(Fern) // Rendering window: x ∈ [-2.5, 2.5], y
∈ [0, 10] // Map to canvas pixels: px = (x+2.5)/5 * width, py =
(1-y/10) * height
The probabilities encode the relative "weight" of each transformation
in the attractor. f₂ has probability 0.85 because the main frond body
takes up ~85% of the attractor's area. If you set all probabilities
equal to 0.25, the chaos game still converges to the same fern, but
the stem and small leaflets are rendered with too many points while
the main body is under-sampled.
5. Classic IFS Fractals
Sierpiński Triangle (3 contractions)
// Three contractions, each scaling by 0.5 toward a different corner
// Triangle vertices: A=(0,0), B=(1,0), C=(0.5, √3/2) f1(x) = 0.5·x //
toward A=(0,0) f2(x) = 0.5·x + (0.5, 0) // toward B=(1,0) f3(x) =
0.5·x + (0.25, √3/4) // toward C // Chaos game equivalent: // Pick a
random corner; move halfway toward it; plot; repeat // After ~50
iterations: Sierpiński triangle emerges Hausdorff dimension:
log(3)/log(2) ≈ 1.585
Koch Snowflake IFS (4 contractions)
// IFS for the Koch curve (one side of the snowflake) // Scale each
copy by 1/3, place 4 copies: f1: scale 1/3, translate to [0, 1/3] //
left segment f2: scale 1/3, rotate +60°, translate to [1/3] // left
tent f3: scale 1/3, rotate -60°, translate to ... // right tent f4:
scale 1/3, translate to [2/3, 1] // right segment Hausdorff dimension:
log(4)/log(3) ≈ 1.262
IFS attractors in general have non-integer Hausdorff dimensions — they
are too rough and detailed to be one-dimensional curves but not filled
enough to be two-dimensional regions. The dimension quantifies their
"in-between-ness".
For a self-similar IFS that satisfies the
open set condition (the transformed copies do not overlap,
except possibly at boundaries), the Hausdorff dimension d satisfies
the Moran equation:
// Moran equation for self-similar IFS (open set condition) Σᵢ rᵢᵈ = 1
Where: rᵢ = contraction ratio of the i-th transformation
(|det(Aᵢ)|^{1/n}) d = Hausdorff (= Minkowski = similarity) dimension
Examples: Sierpiński triangle: 3 maps, each rᵢ = 1/2 3 · (1/2)^d = 1 →
d = log(3)/log(2) ≈ 1.585 Cantor set (2 maps, each r=1/3): 2 · (1/3)^d
= 1 → d = log(2)/log(3) ≈ 0.631 Koch curve (4 maps, each r=1/3): 4 ·
(1/3)^d = 1 → d = log(4)/log(3) ≈ 1.262 Dense IFS (many maps with
large r): d → 2 (approaches plane-filling)
When the open set condition fails (overlapping
copies), the Moran equation gives an upper bound, and the actual
Hausdorff dimension may be less. Computing the exact dimension for
overlapping IFS (like random IFS) is an open problem in mathematics —
the exact overlaps conjecture is still not fully resolved.
7. The Collage Theorem and Fractal Compression
The Collage Theorem is the inverse problem: given a
target image T, find an IFS whose attractor approximates T. It states
that if you can cover T with transformed copies of itself (a
"collage"), then the IFS attractor will be close to T, with error
bounded by the coverage error.
// Collage Theorem (Barnsley) If you can find transformations
f₁,...,fₙ such that: d_H(T, f₁(T) ∪ ... ∪ fₙ(T)) ≤ ε Then the IFS
attractor A satisfies: d_H(A, T) ≤ ε / (1 − c) Where c = max
contraction ratio across all transformations (For c=0.5 and ε=0.1:
guaranteed d_H(A,T) ≤ 0.2) This is the basis of FRACTAL IMAGE
COMPRESSION: 1. Partition target image into range blocks (8×8 or 16×16
pixel tiles) 2. For each range block: search for a domain block
(larger tile anywhere in the image) that, when transformed (scaled +
affine colour map), best approximates the range block 3. Store:
(domain position, rotation, scale, brightness) per range block →
typically 10:1 to 100:1 compression ratio 4. Decode: start from any
image, apply all affine mappings repeatedly → converges to the
original after ~8 iterations
Fractal image compression (developed by Barnsley and Jacquin in the
1990s) was commercially used in CD-ROM encyclopedias (Encarta used
it). It lost favour against JPEG and later JPEG2000 and WebP because
practical compression ratios were similar but encoding was much slower
(finding the best domain block for each range block is computationally
expensive). As a mathematical technique it remains elegant — you are
essentially finding the IFS whose attractor is the image.
8. Implementation: Rendering IFS in JavaScript
// Full IFS chaos game renderer (Canvas 2D) function renderIFS(canvas,
transforms, iterations = 500_000) { const ctx =
canvas.getContext('2d'); const W = canvas.width, H = canvas.height; //
Build cumulative probability array for weighted random selection const
cumProb = []; let total = 0; for (const t of transforms) { total +=
t.prob; cumProb.push(total); } // Map fractal coords to canvas pixels
// bounds: auto-detect or pass {xmin, xmax, ymin, ymax} const xmin=-3,
xmax=3, ymin=0, ymax=10; const toX = x => (x - xmin) / (xmax - xmin) *
W; const toY = y => (1 - (y - ymin) / (ymax - ymin)) * H; // Histogram
buffer for density-based colouring const buf = new Uint32Array(W * H);
let x = 0, y = 0; for (let i = 0; i < iterations; i++) { // Pick
transformation by probability const r = Math.random() * total; const t
= transforms[cumProb.findIndex(p => r <= p)]; // Apply affine
transform: [a b; c d] * [x; y] + [e; f] const nx = t.a*x + t.b*y +
t.e; const ny = t.c*x + t.d*y + t.f; x = nx; y = ny; if (i < 20)
continue; // warm-up: skip first points const px = Math.floor(toX(x));
const py = Math.floor(toY(y)); if (px >= 0 && px < W
&& py >= 0 && py < H) buf[py * W + px]++; } //
Render: use log-density colouring for better detail const imgData =
ctx.createImageData(W, H); const maxDensity = Math.max(...buf); const
logMax = Math.log1p(maxDensity); for (let i = 0; i < buf.length;
i++) { if (buf[i] === 0) continue; const t = Math.log1p(buf[i]) /
logMax; const idx = i * 4; imgData.data[idx] = Math.floor(50 + 150 *
t); // R imgData.data[idx+1] = Math.floor(150 + 100 * t); // G
imgData.data[idx+2] = Math.floor(50 + 50 * t); // B
imgData.data[idx+3] = 255; } ctx.putImageData(imgData, 0, 0); } //
Barnsley fern transforms: const barnsleyFern = [ { a:0, b:0, c:0,
d:0.16, e:0, f:0, prob:0.01 }, { a:0.85, b:0.04, c:-0.04,d:0.85, e:0,
f:1.60, prob:0.85 }, { a:0.20, b:-0.26,c:0.23, d:0.22, e:0, f:1.60,
prob:0.07 }, { a:-0.15,b:0.28, c:0.26, d:0.24, e:0, f:0.44, prob:0.07
}, ]; renderIFS(myCanvas, barnsleyFern);
Log-density colouring assigns brightness proportional to log(1 + hits)
rather than hits directly, revealing fine detail in low-density
regions that would be invisible with linear colouring. This is the
same technique used by the flame fractal algorithm for its
characteristic glowing, high-dynamic-range appearance.
Exploring IFS: Changing a single coefficient by 0.01
can dramatically alter the attractor's shape while keeping it
recognisably related. The space of IFS fractals is a rich parameter
space — IFS parameter space explorations have been used as generative
art tools, and the Electric Sheep distributed screensaver
project evolved fractal flame parameters using genetic algorithms
driven by user votes.