Fractal compression?

tulip jpeg

tulip fractal: 2.0%

There will be a review of image compression first, as presented in this site so far:

mandrill jpeg

mandrill fractal: 6.5%

Most of the time, the 'fit' will, of course, be lamentable, but if a large number of domains is used, then a few may provide an acceptable match. If the contrast value cannot be obtained from the formulae above, it is zero. Convergence is guaranteed if the contrast values are between -1 and +1. Actually, this condition is stricter than necessary; in practice, a fair proportion of contrast values was closer to 2, and has been retained, but the results in the decoder were constrained between the minimun and maximum brightness values in the original image. In the implementation, it is seen that the difference of the average brightess in a range block from the respective value in the previous block can be recorded, with advantage.

monarch jpeg

monarch fractal: 6.0%

Fractal compression is a highly asymmetric process, meaning that encoding takes far longer than image restoration. Domain blocks which do not stand a chance of providing a good match really must be excluded from further processing soonest. There are several ways to speed up compression. Some techniques are suitable for all block based lossy methods, while the last two points are only valid for fractal coders in particular:

• Noisy blocks need not attract a lot of care: They cannot be well encoded- if they could, it would not be obvious, anyway.
• Set a reasonable error margin. The maximum acceptable error was set to 10%, rather than searching for the optimal domain, in one image (the black and white tiger), which only worsened the actual average error from 7.7 to 8.9, but provided a threefold improvement in speed. Even better, you could increase the error margin especially for noisy blocks.
• The domain search could be limited to those blocks which are close to the range block in question only. However, for best quality, the distance between every range block and the corresponding optimal domain, is random. Lu suggests only considering far domains when the difference in quality is significant (he is using Huffman coding for the domain number.)
• Ranges and domains can be classified to 24 groups according to the ordering of partial brightness levels in quadrants. Fisher advises to seek a suitable domain only in the same class as the range. (If both positive and negative contrast adjustments are allowed, two classes are appropriate.) Further classification can be attempted by taking local variance levels into account, as well.

Lenna gif

Lenna fractal: 3.5%

When you are not happy with compression quality, it may be better to try another compression method: There are a couple of options to take, actually, but they will almost certainly do little to improve image quality and everything to render the compression time completely unacceptable. There are several ways to increase the number of hopeful domain blocks:

• Add a fixed codebook to the domain pool.
• Domain blocks may overlap- the domain separation is reduced from eight pixels to 4, 2 or 1- in both directions.
• In addition, all domain classes can yield prospective matches- if the quadrants are rearranged so that the ordering of local brightness levels matches that of the range quadrants. This will be discussed in more detail.

Thus a range is approximated by a brightness and contrast value, plus a domain location and, possibly, an isometry descriptor. The contents of the domains themselves are not needed in the compression file. Some quantisation of values and bit manipulation is in order so that data is packed efficiently in the fractal file.

The site has tried using domain and range blocks of the same size, in the hope that self- similarity might be more apparent at the same scale. The results, predictably, were plagued with convergence problems. Restraining contrast values between -1 and +1 and shifting domain and range blocks as shown in the following sketch improved matters- but only so much. This direction has been abandonded.

The decompression process has not been given as much attention- it is much faster on any reasonable hardware. If subsampling has been used for encoding, there is a technique called pixel chasing (or is it pixel chaining?), which exploits the fact that pixels are classified in a small number of families, every family having a limited number of cycles. Usually, though, decompression is recursive. It is faster to choose a uniform image of the average brightness in the original for a start (but much more impressive to start with a completely different photograph.)

Strictly speaking, there is a difference between the fractal approximation (the so called collage) and the final decompressed image (the attractor), but it is small if the photograph was suitable for fractal encoding. The following table gives the residual error for every iteration of the Lenna image. Ten iterations are usually adequate, though given the collage error, even three iterations would be acceptable in many cases. Normally, convergence seems to take place more or less at a geometric rate:

Iteration	Error (%)
1	23.0
2	9.8
3	4.7
4	3.8
5	3.7
10	3.7
collage	3.5

Only the ratio, not the actual sizes of range and domain blocks have been fixed during compression. The decompressed image may therefore be of any size. (This seems to be the source of some unfortunate claims of compression ratios in the past.) The images below show a part of Lenna magnified twice. For comparison, a jpeg blow up is displayed, too. The fractal zoom is said to have the edge at much higher zoom factors, though. Both images are badly in need of postprocessing, but here you get the chance to compare the raw results.

Jpg error: 2.5%

Collage error: 2.6%