Fractal Compression
Background
We model a grayscale image as a vector \(x \in [0,1]^n\) with \(n = H \times W\) and write \(\mathcal{I} = [0,1]^n\) for the image space. A transform \(f : \mathcal{I} \to \mathcal{I}\) is a contraction when \(|f(x) - f(y)| \leq k |x - y|\) for some \(k < 1\). The Banach fixed-point theorem then tells us that every contraction admits a unique fixed point \(x^* \in \mathcal{I}\) with \(f(x^*) = x^*\).
Moreover, for any starting image \(x \in \mathcal{I}\), the sequence \(x, f(x), f(f(x)), \ldots\) converges to \(x^*\). Fractal compression searches for a contraction \(f\) whose fixed point closely approximates the target image. Once such an \(f\) is found, we store its parameters instead of the pixels, because iteratively applying \(f\) to any seed image converges back to the fixed point. When the description of \(f\) is shorter than the original data, the image is effectively compressed.
To make this concrete, we subdivide the image into a grid of blocks and assemble a family of contractions \(f_i\) whose combined action covers the entire image. We refer to the smaller target patches as range blocks, and to the larger source patches from which we reuse detail as domain blocks.
The illustration highlights the core idea: a domain block (one cell in the coarse grid) is contracted onto a range block in the finer grid. For each range block we therefore search for a domain block and a contraction that brings the transformed pixels as close as possible to the target block, ensuring the overall image stays close to the fixed point.
Implementation
This demo instantiates the blockwise contractions described above on 512×512 grayscale images. For every 4×4 range block we examine each candidate 8×8 domain block in the image, downsample it to the range resolution, and enumerate the eight spatial symmetries so every rotated or reflected variant is considered. For each candidate we solve for a simple intensity contraction—contrast \(c\) and offset \(d\)—that minimizes the mean-squared difference between the transformed domain block and the current range block. The parameters with the lowest error define one of the contractions \(f_i\); collecting these local winners yields a global mapping whose fixed point aims to reproduce the source image.
We record these choices in a mapping table: each entry remembers the domain index, symmetry, and contrast/offset pair. During decompression the table is iterated repeatedly, with each pass replacing every range block by its contracted domain partner so the noisy seed image converges to the fixed point.