Fractal image compression, also known as fractal encoded image information,
consists of contractive transforms (Barnsley, 1988; and Fisher, 1994) and
mathematical functions required for reconstruction of the original image, instead of any data
in pixel form. These transforms are composed of the union of a number of
affine mappings on the entire image, known as Iterated Function System (IFS). It is
based on fractals, rather than pixels. Barnsley introduced the fundamental principle of
fractal image compression in 1988, and derived a special form of Contractive
Mapping Transform (CMT) applied to IFSs, called the College Theorem (Barnsley, 1988;
Fisher, 1994; and Wohlberg and Jager, 1999), which gives the distance between the
image to be encoded and the fixed point of a transform, in terms of the distance
between the transformed image and the image itself. This distance is known as college
error and it should be as small as possible. Jacquin's first publication on fractal
image compression with Partitioned IFS (PIFS) was in 1990 (Jacquin, 1990, 1992 and
1993; and Fisher, 1994). In Jacquin's method, the image is partitioned into sub-images,
called `range blocks', and PIFS are applied on sub-images, rather than the entire image.
The process of fractal image encoding is shown in Figure 1. First, the image
is partitioned to form range blocks. Then, a set of domain blocks is selected in
domain pool selection. This choice depends on the type of partition scheme used
(Weistead, 2005; and Distasi et al., 2006). Then, transformations to be applied on domain
blocks to form range blocks are determined, which assures the convergence properties
of decoding (Barnsley, 1988; and Fisher, 1994). The partition scheme and the type
of domain pool used affect the choice of transforms. In suitable domain search, the
most compatible domain block for every range block is searched. The computational
cost of this step makes the whole process very much time consuming. Hence, the
design of effective and efficient domain search technique is one of the most active
areas of research in fractal coding. A wide variety of solutions has been suggested
(Polvere and Nappi, 2000; Weistead, 2005; and Chaurasia and Somkuwar, 2009). |
