The
Sierpinski TriangleData on the computer is stored on the hard drive. Unfortunately, hard drives only have a certain capacity. In order to store more in less space, data needs to be compressed, or made smaller.
Another reason that you might want to compress data is to send it. For example, if there is a sattelite in space that takes a high resolution picture of earth taking up 100 megabytes, then it would be much easier to send a compressed picture taking only 10 megabytes, sent to the sattellite's control center, and then decompressed.
Several ideas have been proposed to compressed images. The most commonly used method, currently the standard, is JPEG. On a PC, files with the extension .jpg are generally JPEG pictures. Compare the size of .jpg and .bmp (BitMaps are not compressed) files. Two other promising methods are currently under development: Fractal and wavelet. We will concentrate on fractal image compression.
Fractal image compression only works with photos. With icons and cartoons, the quality of the decompressed picture is generally awful.
Lets say we want to make a picture with the top-left, top-right, and bottom-left quarters are the exact same as the entire picture. The only picture that fits these requirements is:
The
Sierpinski Triangle
Let's look carefully at this picture. In order for these three quarters of the picture to be the same as the whole picture, nine of the sixteenths have to be the same as the whole picture as well. This could go infinitely. This gives the attribute of infinite resolution to the picture. Of course, on the screen it can't be shown at infinite resolution, so I have generated it at 128 X 128 pixels. This means that the picture can be generated at any size at any resolution and still be seen with perfect quality (the best attainable for that resolution).
This type of picture, with self-similarity covering the whole picture is called an Integrated Function System, of IFS for short. This particular IFS was first generated by someone named Sierpinski, and it is a triangle, so it is called the Sierpinski Triangle.
We know that this is the only picture that has these special qualities of self-similarity in three of the four quarters, but how could it be generated? The first thing to do is to start of with any picture you want. You can have anything from a big black box to a beautiful picture of Hawaii with the surrounding Pacific. It doesn't matter. Since there is only one picture that it can end up with, all original pictures will get to the same thing. For simplicity, we will use a big black box (takes up less room than a great photo). Here is our pho..., er, that is, box:
Step
1: A black block
Now lets make three copies of our picture (whatever you may be using) and shrink them half the size. One will put in the top-left corner, one in the top-right, and one in the bottom-left. The bottom-right corner we will leave white.
Step
2
Lets do step two again, this time to our new image:
Step
3
Let's do this several more times:
Step
4
Step
5
Step
6
Step
7
We do it just one more time, and we get our Sierpinski Triangle again:
Step
8: The final Sierpinski Triangle
Notice that you can find several, shrunken copies of all the above steps in the final Sierpinski Triangle. The Sierpinski Triangle isn't the only IFS. In fact, there are an infinite number of IFS!
So, let's get back to the original topic: fractal image compression. We just described the Sierpinski Triangle with a few instructions: shrink, duplicate three, position. If there were a program (and there is) that can generated IFS from a few, simple instructions, then it would be silly to store the actual pictures. Instead, you can just store a few simple instructions. Then, when you want to see the picture, you simply feed the IFS into the program.
If you could do the same with normal looking pictures, then it would be a great compression method! Instead of saving a few pictures, save just the instructions to generate the picture! The trick is, finding an IFS that looks somewhat like the picture you would like to compress.
Does the Sierpinski Triangle look anything at all like a normal photo? In my opinion, and I'm sure yours, no! So how is one supposed to find an IFS that looks at all like a photo? The answer is, unfortunately, that you can't. So, we will have to develop a better way of doing IFS that can generate pictures more photo-like. The result is Partitioned Integrated Function Systems - PIFS! I won't touch on the topic of color; that's to complicated.
With IFS, you can take several copies of the whole picture, then shrink and move it. With PIFS, you have much more power. You can take several copies of several parts of the picture, and then shrink and move it. This gives much more flexibility to the possibilities of the resulting images. Though, for a given picture, you probably won't find a PIFS that is the same as the picture, however it is very easy to find a similar looking PIFS.
That makes it sound so easy! The only problem is finding the PIFS that looks like the picture. However, I will put that away until later. Lets first think about some terminology to refer to when talking about PIFS. Just two words:
range - a block in the picture that is the
same as a bigger block in the picture
domain - a block in the picture that, during
decompression, is copied by a smaller range block
In otherwords, range blocks cover the whole picture, and each range block must find a bigger domain block to map to.
Now that we know what a PIFS is, we still have a problem to solve: how to find the smallest PIFS possible that looks most like the picture that we want to compress. This problem is, of course, a contradiction in itself, you can sacrifice quality for size and vise versa. However, we will not divulge into that.
First we must divide the picture into lots of small blocks. You can divide it up any way you want; the blocks don't even have to be square (i. e. they could be triangle). However, there are systematic ways of doing it. For example, the most commonly used method is called QuadTree decomposition (QD). However, I read about a proposition for a similar method, called QaudTree recomposition (QR) which is faster. However, to keep this brief (which it already isn't), I will show the simplist method.
Let's pretend we have a 512X512 picture. In our simple method, we will divide the picture into lots of 4X4 blocks that cover the whole image, non-overlapping. We get 103X103=10609 range blocks. Let's say we divide the picture into a similar amount of 8X8 overlapping domains, to get 10609 ranges and about (I don't think it's exact; I don't feel like figuring it our) 10609 domains.We have to compare each domain with each range, totalling 112550881 comparising. Each domain can be rotated and reflected 8 ways (rotate 4, and reflect each), in order to match with a range, totalling 900407048 comparisons. Even with our speedy 450MHz computers now-a-days, it can take several days just to compress just one, small, 512X512 picture. A faster way must be found.
You can cut down on several things. Each one, however, makes such a small difference in speed that you would have to use all of them to cut the compression time down to less than a minute (note that we are talking about compression; decompression for fractal image compression is very quick for normal sized pictures). Each method reduces the quality of the decompressed picture drastically. So, at the end, we will discuss a method by the use of classification that solves the problems of both quality and speed. However, even with classification, it takes a while, and most of the research for fractal image compression is put into the compression speed. Of course, other areas are also in research such as fractal video compression, color compression, etc.
One way of doing faster compression is only searching the nearest area. For example, for a given range block, it would only search the nearest sixty potential domains for a matching domain. This doesn't do too much to quality because, if you look at a picture (especially ones with only natural objects in it, i.e. a tree), you will notice that similar features tend to be in the same area.
One could also cut it down by not rotating the domains all eight ways for each range. However, this has a bigger affect on quality, because similar features are often rotated different ways.
This is kind of getting ridiculous. You might as well drop searching. Now, the time has come for me to introduce classification.
Take a block. Divide it into it's four quarters. There are exactly 24 combinations of arranging the quarters. You can order the quarters according to the color. Some of the 24 combinations are (using numbers instead of colours):
1 |
2 |
3 |
4 |
2 |
3 |
1 |
4 |
4 |
3 |
2 |
1 |
Now, we can classify every block into one of the twenty-four classifications. Classify every range and domain. When we are comparing, we can look only at the domains in the same class as that range!
More research is being put into fractal image comrpession. It is still under development and it has great potential. Who knows? Maybe one day it will take over JPEG.
I hope this as been a good guide to the basics of fractal image compression. I tried to keep it as brief as possible, but it kind of came out long.
Last updated: January 17, 1999