Least-Squares Block Coding by Fractal Functions

The image coding scheme described in this chapter represents an attempt to achieve image compression using, as closely as possible, the “classical” theory of strictly self-similar fractals. Image compression is achieved by establishing a partition of an image into adjoining rectangular blocks, and coding each block individually by an iterated function system together with a type of fractal function. The method differs from other fractal compression techniques in that an image is regarded as an assembly of essentially independent blocks, so that any block will have the same code regardless of the rest of the image. In this respect the method is necessarily inferior to others when encoding an entire image, but the work is of interest since it provides a nearly optimal code for a single block, which may be obtained in linear time. Moreover, this work has the theoretical interest of being the only direct solution to an inverse problem in fractal geometry yet known.