codebook iris 7.5%
fractal iris 7.9%
codebook iris 7.5% | fractal iris 7.9% |
There are some clear similarities between this technique and fractal compresssion:
 codebook monarch 7.9% |  fractal monarch 6.0% |
A codebook has been formed by considering the most oft used blocks in three images, tulip from last month's page, as well as the portraits of Foti and Helen. The image of Helen is not shown for reasons of copyright- she is a famous actress. (Must it have been Julia?) The picture of Foti may be included in the fractal automata section, later. None of the images shown on this page have been used to form (or optimise) the codebook. Rainy iris has replaced the tulip image.
It must also be said that the error figures shown are quite misleading: For fractal compression, collage error is shown, while attractor error can be expected to be slightly higher. And although the fractal compression figure was not constant, the fractal codebook was 4 times larger than the fixed codebook, for some images. Again, there was no postprocessing of images whatsoever.
 codebook Monalisa 2.0% |  fractal Monalisa 1.8% |
A codebook is trained on a set of images by using Lloyd's algorithm (sometimes called the LBG algorithm after the names of the people proposing it). Two steps are involved:
Fractal compression and codebook compression are similar enough in their mechanism, so that the same program can provide both with marginal modifications only: This time, domain blocks are derived from a ficticious image, which is simply the composite of codebook blocks. Domains are of the same size as ranges, since there is no averaging operation. Clearly, there is no point in decreasing the domain 'separation' in this case.
The size is still 4x4, yielding a compression ratio of about 5, which is not impressive. I am not after portraits which look as though they have been bitten by rats! I am after excellent rendition quality at moderate compression factors.
 codebook baboon 7.1% |  fractal baboon 6.5% |
Of course, there is some self-similarity in many images, mainly in the form of symmetry. The algorithm which is widely known for fractal compression cannot exploit it, because there are convergence problems when the domain and block range sizes are almost equal. More self similarity is present, at several scales and orientations. Fractal compression can hardly take advantage of that, either, as it only investigates principal isometries at a fixed scale of probably 2:1. In principle, additional scales and angles can be explored. In practice, fractal compression takes long enough as it is, for the higher quality settings. Extra scales and orientations need extra bytes in the compressed file.
The red, green and blue colour planes are still considered individually for the images on this page. One can do better than that: The luminance, red and blue components are more hopeful for image compression. Most of the image information is then in the luminance plane, and the red and blue constituents do not need to be treated equally thoroughly. The relevant formulae, for 8 bit values:
Y = 0.30R + 0.59G + 0.11B
Cb = - 0.17R - 0.33G + 0.5B + 128
Cr = 0.5R - 0.42G - 0.08B + 128
 codebook Lenna 3.9% |  fractal Lenna 3.5% |
The images on this page are still transmitted as 24-bit bitmaps, in the interests of a fair comparison. This is slow, and some browsers may not show them. On the other hand, the 256 gray tone Lenna image is sent losslessly as a Gif file.
The fractal compresssion program has been placed at the end of the fractal compression page. There is a one second delay between iterations of the decompressor, purely for the comfort of the viewer- it is most certainly not needed by the decoder. All error figures assume brightness conditioning.
The code for this page is given; later, the source will follow, too. The image files supplied carry width and height information (one byte each) followed by raw data. On the net, you can find some bin images. They are usually 256x256 or 512x512 and size information is not prefixed. There are also some pgm files, which are fairly similar, but there is a header detailing size, plus the magic identifier P5 and an optional comment field. However, you may wish to use your own test files with this, past and future programs. I will supply a suitable converter quite soon.
The following picture shows the codebook: At the top can be found the most commonly used blocks, which thus are examined first.
Some sites of free photographs.