IFS - Theory

Fractal image compression: Did you already hear somebody talking about this compression technique? Are you interested in it? If yes, then read on.

Fractal image compression can achieve incredible packing rates: For certain images (mostly natural objects, which seem to be quite self similar, for example a tree) it should be possible to describe whole images by only a small set of numbers. The basic idea for this packing algorithm is an iterated function system, short: IFS.

Well, Julia- and Mandelbrotsets are also iterated function systems: A function is used, it is iterated, and thus it’s an iterated function system. But here I will explain another type, which deals with more formulas (i.e. a formula system), applied according to a probability assigned to each formula, where each formula is an affine transformation (i.e. matrix multiplication plus vector addition). These functions are applied many times (thus iterative function system).

Yet again, one is interested in the 'attractor'. You have already seen (at least I hope so), that this attractor can be very complicated. Just remember a few pictures of the Mandelbrot set. The special thing about the (linear) IFS is, that one is not only able to calculate the attractor from a given IFS. One is also able to reconstruct an IFS from an attractor. That means, if you have an attractor (as a normal pixel image) you can calculate in some way an IFS (i.e. several functions). And the attractor of your ”reconstructed” IFS is quite similar to the attractor, which you already have.

For example, Julia sets don’t allow this: If you have a nice picture showing a Julia set, you are not able to calculate the formula or parameters, which have lead to that image. Well, perhaps you can do that, perhaps by hand, using trial and error, for some images, but for sure not in general.

So lets assume, you have a picture, assume that it is an attractor of an unknown IFS, reconstruct the IFS, save the IFS (which normally needs only a small set of numbers) and if you want to look at the picture, you just must calculate the attractor of the previously saved IFS: You will get a picture, which is similar to your original picture. This is the basic idea behind fractal image compression. Basically it is not a compression technique, it is rather some kind of reverse engineering. As you can imagine, the quality is better, the better the attractor of your reconstructed IFS matches the attractor given (i.e. your image). And the better the attractor, the more functions in the IFS you will need, thus more numbers to store.

So one only has to choose the right functions, so that the attractor is similar to the picture which one wants to compress. Sounds quite easy, doesn't it? Well, now, how exactly does it all work? How does one find the correct functions? Is it possible to find functions for *all* possible images?

An IFS consists of several functions, every single function is an affine transformation, that means, a function, which just rotates, moves around or streches a given object. Every such affine transformation has a value assigned, which is interpreted as the execution probability, that means, this value determines, how often this function is applied to a point compared to the other functions in the system. Such affine transformations can be represented simply by a matrix (responsible for rotating and stretching) and a vector (responsible for moving the object around).

To be more mathematical, an IFS is a system of affine transformations:

Mi x + bi , with probability Pi ; i element of {1...n} , n >=1, Mi a 3x3 Matrix, bi vector from R3

Sum of Pi, i=1...n, is equal to 1.

Now, how is a picture, the attractor of an IFS, calculated?

1. One starts with a point, which surely lies onto the attractor. For example, one can take the fixed point of the first transformation.

2. Choose a function of the IFS, such that the given probabilities are fulfilled. For example, P1=0.2, P2=0.5, P3=0.3: Generate a random number p between 0 and 1. If p <=0.2, then choose function 1, if 0.2<p<=0.7, the choose function 2, if p>0.7, choose function 3.

3. Apply the chosen transformation to the previous point. The result is a new point of the attractor. Go to step 2...

Well, after some time the attractor will appear.

Now lets come to the question, why and especially how it is possible, to (re)construct an IFS from/to a given picture. There exists a mathematical proposition, called the 'Collage Theorem', which essentially says, that this construction is possible:

Given an IFS with the transformations w1 to wn, additionally a set T. Let s be the greatest Lipschitz-constant of all the transformations w1 to wn, which must be smaller than 1. The Hausdorff-distance between T and the union of w1(T) to wn(T) should be smaller than a given epsilon. Then the Hausdorff-distance between the attractor of the IFS and T is smaller than epsilon/(1-s).

Well, so s should be the biggest stretching factor of all transformations, and s must be smaller than 1, i.e. all transformations must be contracting transformations.

The Hausdorff-distance of two sets is, to be quite inexact (and mathematically wrong, but who cares), the 'normal' distance between 2 sets.

Well, now let me explain, what this theorem essentially says:

Given a set T, this could be perhaps a picture (should be a black-white-picture ...)

Then choose the transformations w1 to wn of the IFS, so that the union of the sets w1(T) to wn(T) covers quite exactly the whole set T. That means, the union of the sets, which you obtain, if you separately apply w1, w2, ..., wn to the set T, covers the picture. Remember, the transformations are functions, which just rotate, stretch and move an object around. So this previous sentence means, that the functions w1 to wn should be chosen, such that the whole picture T is built of small copies of itself, just like a collage...w1(T) is a rotated, stretched (with a factor smaller than 1!) and displaced copy of the original set/picture T, and so is w2(T), w3(T),...wn(T).

Well, then the condition of the theorem is approximately fulfilled, i.e. the Hausdorff-distance between T and the union of w1(T) to wn(T) is smaller than epsilon. This epsilon of course is determined by the quality of the collage. Now the theorem says:The attractor of the IFS, which one can calculate from the transformations, is similar to the original set/picture T. To be more exact, the Hausdorff-distance between this attractor and T is smaller than epsilon/(1-s). Now you can see, why the Lipschitz-constant must be smaller than 1. And you can see even more: If you have a very small Lipschitz-constant, then (1-s) is near 1, but then of course you need many transformations to cover your picture, because the Lipschitz-constant is the stretch-factor, so you have to build the picture T out of many very small copies of it. So if you want to make a very good collage, then the compression ratio isn't that good. Also notice, that the calculation time goes up, if 's' is small. It makes sense, to choose 's'=0.25, so to build the whole picture of quarters of itself.

As you can see, too, the number of differences between the attractor and the original picture depend on epsilon. So if you make a bad collage, then this epsilon is big...

Well, this is the idea for fractal image compression. One simply has to find out the transformations. One could implement the following algorithm: Given a picture, this picture is then cut out and used as a brush, just as in any paint program. The user then has to rotate, move around and stretch this brush, so it covers a part of the original picture. Then the user has to fix it. the first transformation is completed (one simply has to write down all actions done like moving, rotating and stretching). Then one fetches another copy of the original picture, again moves, rotates and stretches it, so it covers another part of the original picture. It then should be fixed, too, and so the second transformation is ready. The user continues like this, until the original picture has been covered by some smaller copies of itself, just like a collage.

Let me note one thing: The parts of the copies may of course overlap, but this just increases the calculation time, so it should be avoided.





Last update on Nov 26 2002.