| The method of Iterated
Function Systems generated great excitement in the computer graphics community,
and also in the image compression community. After all, this tree image can be
generated with only 36 four-digit numbers. Moreover, the fractal nature of the
image makes it scale-independent: the image can be rendered on a larger scale,
without additional information, and without pixellation. |
 |
|
| The problem, of course, is we don't necessarily want this tree,
but some other tree, or a cat, or maybe a person. Also, we would like to have
an automated process for finding the IFS rules to produce a given picture. |
| Michael Barnsley, one of the first popularizers of
IFS, developed a method to approach this problem. The Fractal
Transform is based on the notion that the whole picture is not made of
smaller copies of itself, but that some parts are made of smaller copies of
other parts. The standard example used in these tests is "Lena," on the left. |
|
| Note on the right, the small square is similar to the larger
square. The Fractal Transform has two steps. |
| Partition the image into (non-overlapping) small squares, called range blocks. |
| For each range block, find the domain block (usually of twice the linear
dimension of the range blocks) that best fits the range block after it has been
rescaled and perhaps reoriented by one of the eight symmetries of the square. |
| Here are the maximum quality JPG (left, 5.75:1 compression) and
maximum quality FIF (Fractal Image Format) (right, 6.07:1 compression). |
|
| Here are JPG 22.35:1 (left) and FIF 25.11:1. |
|
| JPG won the image compression contest, yet Barnsley and others
remain optimistic the fractal encoding eventually will be seen as superior. The
test cases contained many scenes without natural components, so it is little
surprise an algorithm designed around fractals would not succeed. In the
space of all pictures, those with natural fractal aspects may form a large
subset. |
| Second, the main advantage of FIF is that it is easy to automate.
It is not particularly sensitive to fractals, but rather is inspired by the
mathematical mechanism of IFS. A better method may be discovered. |
| Third, wavelets have been very successfully used in image
compression (if the FBI has your fingerprints on file, they are stored as
a table of wavelet coefficients). Wavelets exhibit the same scaling properties as
fractals, but the relation between wavelets and fractals has not yet been unpacked. |
| Fourth, fractal compression is scale-independent. Magnifying
an image reveals additional detail. On the left is a magnification of the
original image of Lena's eye. On the right is the same part of the fractal
image rendered at the same scale. To the extent that natural images exhibit
some degree of self-similarity, this is an advantage. |
|
