Fractal Image Compression and the Self-Affinity Assumption: A Stochastic Signal Modelling Perspective

Abstract

Fractal image compression is a comparatively new technique which has gained considerable

attention in the popular technical press, and inore recently in the research literature.

The most significant advantages claimed are high reconstruction quality at low coding

rates, rapid decoding, and "resolution independence" in the sense that an encoded image

may be decoded at a higher resolution than the original. While many of the claims published

in the popular technical press are clearly extravagant, it appears from the rapidly

growing body of published research that fractal image compression is capable of performance

comparable with that of other techniques enjoying the benefit of a considerably

more robust theoretical foundation. .

So called because of the similarities between the form of image representation and a

mechanism widely used in generating deterministic fractal images, fractal compression

represents an image by the parameters of a set of affine transforms on image blocks

under which the image is approximately invariant. Although the conditions imposed

on these transforms may be shown to be sufficient to guarantee that an approximation

of the original image can be reconstructed, there is no obvious theoretical reason to

expect this to represent an efficient representation for image coding purposes. The usual

analogy with vector quantisation, in which each image is considered to be represented

in terms of code vectors extracted from the image itself is instructive, but transforms

the fundamental problem into one of understanding why this construction results in an

efficient codebook.

The signal property required for such a codebook to be effective, termed "self-affinity",

is poorly understood. A stochastic signal model based examination of this property is

the primary contribution of this dissertation. The most significant findings (subject

to some important restrictions} are that "self-affinity" is not a natural consequence

of common statistical assumptions but requires particular conditions which are inadequately

characterised by second order statistics, and that "natural" images are only

marginally "self-affine", to the extent that fractal image compression is effective, but

not more so than comparable standard vector quantisation techniques.