Release 4.0 | |||

| |||

## 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 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:
M
Sum of P 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, P 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:
Well, so 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 w
Well, then the condition of the theorem is approximately fulfilled, i.e. the Hausdorff-distance between T and the union of w 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. |