Fractal image decoding

The Partitioned Iterated Function System created with the above algorithm consists of a list of affine maps, each map being restricted to a specific range. Since each map is contractive in the luminance dimension (the contrast factor is less than one), we can apply the Contractive Mapping theorem to decode the image. Starting from an arbitrary image, for example a completely black image, the decoder can apply the PIFS iteratively. This process converges to the fixed point of the PIFS. If the compressor has found a good PIFS for the image, that is, if the collage of all the transformed domains is close to the original image, then the fixed point of the PIFS is also close to this image.

To perform one iteration of the PIFS, the decoder takes the list of all affine maps and applies each one in turn. This transforms a set of domains into a set of ranges. Since the ranges have been selected to be non-overlapping and to cover the whole input image, a new complete image emerges as a result. The decoder can then repeat the whole process, until convergence is achieved, that is, until there is very little difference between the input image and the output image. Convergence is generally obtained in 8 to 10 iterations.

Figure 13.3 shows the result of decoding the LISAW image with our sample program after 1, 2, 3 and 8 iterations, starting from an initially black image.

Figure 13.3  Image decoding after 1, 2, 3 and 8 iterations

Even after only one iteration, the image is recognizable. The minimum range size selected by the encoder was 4 pixels wide, and such ranges are clearly visible, giving a “blocky” aspect to the image. However since the affine maps are also contractive in the spatial dimensions (the domains are twice as large as the ranges), more detail is created at each iteration. After the second iteration, the remaining blocks are only two pixels wide. After 8 iterations, convergence has been achieved, and the resulting image is extremely close to the original image. (The compressor was set to best quality for this image.)

We can now better understand why the affine maps were chosen to be contractive in both the spatial and luminance dimensions. The contraction in luminance (reduction of contrast) was essential to ensure convergence of the decoding process. The spatial contraction is useful to create detail in the image at all scales, and thus get a much better approximation of the original image. Without spatial contraction, the decoding process would still converge, but it would converge to a a very “blocky” image, without any contrast inside each block. With spatial contraction the contrast across ranges, initially provided by the brightness offset components of the affine maps, is propagated within each range to smaller and smaller scales after each iteration.

Close inspection of the first image of Figure 13.3 reveals that sometimes detail is visible even within a range. Since the domains of the initial image are uniformly black, each range after the first iteration should have a uniform grey level, given by the brightness offset in the affine map. However to accelerate the convergence of the decoding process, our sample program uses the same buffer for both input and output images, as we will see later. Thus the detail visible within a range after the first iteration is only a side effect of our particular implementation.

Resolution independence

To reconstruct an image, the decoder starts its iterations with an arbitrary image of the same size as the original image. But what happens if the decoder starts with an initial image that is twice as large? The result of the decoding process will be also an image twice as large as the original image. However, since the affine maps used to encode the image do not depend on its resolution, the decoded image will not have the “blocky” aspect that would have been obtained if we had simply replicated the pixels of the original image. It will instead still contain detail at every scale.

Figure 13.4 shows a detail of the original LISAW image, enlarged 8 times. The 8x8 pixel blocks are clearly visible. Figure 13.5 shows the same part of the image, but decoded with scale factor 8.

Figure 13.4  Detail of original LISAW enlarged 8 times.

Figure 13.5  Detail of LISAW decompressed with scale factor 8.

The image obtained through fractal decoding is much more natural-looking. The decoding process has created artificial detail which was not present in the original image, but which looks as if we had really zoomed on the original image. This is a very useful feature, but it does have limits. If we try to zoom at an enormous scale factor, we will not end up seeing the atoms at the surface of LISAW’s skin, but rather we will be looking at detail which is completely artificial.

The fantastic compression ratios put forward by some advocates of fractal compression may have to be taken with a grain of salt in some cases. For example, assume that an image of 320x200 pixels, with an original size of 64 KB, has been compressed with a ratio of 32 to 1, resulting in a compressed image of 2 KB. Now, decode this image with a scale factor of 4. This creates an image of 1280x800 pixels, with an uncompressed size of 64x16 = 1024 KB. It would be incorrect to state that we have achieved a compression ratio of 1024 / 2 = 512 to 1. The reason is that the uncompressed image contains artificial detail which was not present in the original image. The original information is still compressed with a ratio of 32 to 1; the rest of the information has been created artificially by the decoding process.