Fractal compression

We begin with the representation of a binary image, where the image may be thought of as a subset of ${\displaystyle \mathbb {R} ^{2}}$. An IFS is a set of contraction mappings ƒ₁,...,ƒ_N,

${\displaystyle f_{i}:\mathbb {R} ^{2}\to \mathbb {R} ^{2}.}$

According to these mapping functions, the IFS describes a two-dimensional set S as the fixed point of the Hutchinson operator

${\displaystyle H(A)=\bigcup _{i=1}^{N}f_{i}(A),\quad A\subset \mathbb {R} ^{2}.}$

That is, H is an operator mapping sets to sets, and S is the unique set satisfying H(S) = S. The idea is to construct the IFS such that this set S is the input binary image. The set S can be recovered from the IFS by fixed point iteration: for any nonempty compact initial set A₀, the iteration A_k+1 = H(A_k) converges to S.

The set S is self-similar because H(S) = S implies that S is a union of mapped copies of itself:

${\displaystyle S=f_{1}(S)\cup f_{2}(S)\cup \cdots \cup f_{N}(S)}$

So we see the IFS is a fractal representation of S.

IFS representation can be extended to a grayscale image by considering the image's graph as a subset of ${\displaystyle \mathbb {R} ^{3}}$. For a grayscale image u(x,y), consider the set S = {(x,y,u(x,y))}. Then similar to the binary case, S is described by an IFS using a set of contraction mappings ƒ₁,...,ƒ_N, but in ${\displaystyle \mathbb {R} ^{3}}$,

${\displaystyle f_{i}:\mathbb {R} ^{3}\to \mathbb {R} ^{3}.}$

A challenging problem of ongoing research in fractal image representation is how to choose the ƒ₁,...,ƒ_N such that its fixed point approximates the input image, and how to do this efficiently.

A simple approach[2] for doing so is the following partitioned iterated function system (PIFS):

1. Partition the image domain into range blocks R_i of size s×s.
2. For each R_i, search the image to find a block D_i of size 2s×2s that is very similar to R_i.
3. Select the mapping functions such that H(D_i) = R_i for each i.

In the second step, it is important to find a similar block so that the IFS accurately represents the input image, so a sufficient number of candidate blocks for D_i need to be considered. On the other hand, a large search considering many blocks is computationally costly. This bottleneck of searching for similar blocks is why PIFS fractal encoding is much slower than for example DCT and wavelet based image representation.

The initial square partitioning and brute-force search algorithm presented by Jacquin provides a starting point for further research and extensions in many possible directions -- different ways of partitioning the image into range blocks of various sizes and shapes; fast techniques for quickly finding a close-enough matching domain block for each range block rather than brute-force searching, such as fast motion estimation algorithms; different ways of encoding the mapping from the domain block to the range block; etc.[3]

Other researchers attempt to find algorithms to automatically encode an arbitrary image as RIFS (recurrent iterated function systems) or global IFS, rather than PIFS; and algorithms for fractal video compression including motion compensation and three dimensional iterated function systems.[4][5]

Fractal image compression has many similarities to vector quantization image compression.[6]

An inherent feature of fractal compression is that images become resolution independent[12] after being converted to fractal code. This is because the iterated function systems in the compressed file scale indefinitely. This indefinite scaling property of a fractal is known as "fractal scaling".

The resolution independence of a fractal-encoded image can be used to increase the display resolution of an image. This process is also known as "fractal interpolation". In fractal interpolation, an image is encoded into fractal codes via fractal compression, and subsequently decompressed at a higher resolution. The result is an up-sampled image in which iterated function systems have been used as the interpolant.[13] Fractal interpolation maintains geometric detail very well compared to traditional interpolation methods like bilinear interpolation and bicubic interpolation.[14][15][16] Since the interpolation cannot reverse Shannon entropy however, it ends up sharpening the image by adding random instead of meaningful detail. One cannot, for example, enlarge an image of a crowd where each person's face is one or two pixels and hope to identify them.