3.8 Fractal Coding

A fractal is a structure possessing similar looking forms of many different sizes and orientations. It can be magnified infinitely with structure at every scale and can be generated by small, finite sets of data and instructions. Fractal compression is based on three concepts: affine maps, iterated system functions, and the collage theorem. The affine map is a combination of rotations, scalings, and translations that act on a part of a source image to create a part of a target image. An iterated function system is a collection of contractive, affine maps. The iterated function system acts on a part of the source image to create a part of the target image out of repeated parts of the source image. These repeated parts are of various rotations, scales, and translations. The collage theorem says that if an image can be described by a set of affine maps then that set of maps provides an iterated system function that can be used to reproduce as good an approximation of the image as you desire.

The challenge is then to find a fractal model for a given image. This is done through the fractal transform, which is a systematic method that breaks up an image into smaller regions, called domain regions, and finds the best affine maps for those regions. The domain regions are nonoverlapping and completely cover the image. Range regions are also defined. They can overlap and do not need to cover the entire image. An affine...