Fractal image compression. Illustrations by Louisa F. Anson. (English) Zbl 0796.68186

Barnsley, Michael F.; Hurd, Lyman P.

Wellesley, MA: AK Peters. 255 p. (1993).

In this book the authors describe the mathematical theory of an effective image compression method called fractal transform. Furthermore, an example implementation (in C) of the compression method for gray scale images is provided.
At first, various methods of modelling so called Real World Images are given. Different models are developed for different kinds of Real World Images (black-and-white, gray scale, true color). Properties of these images are discussed and main differences between analog and digital data are outlined.
Afterwards, the mathematical theory used for the formulation of the theory of IFS-fractals (iterated function systems) and its local counterpart (local IFS theory) is presented. This includes metric and normed spaces, affine transformations, measure theory, and the key fact: The contraction mapping theorem.
Then, IFS fractals are defined and as an application of the contraction mapping theorem the existence of an attractor for each IFS is proven. For computation of the attractor the Photocopy Machine Algorithm is provided as a first method (including an implementation in C Source Code).
As a first application of IFS fractals an interactive image compression method is presented, whose success heavily relies on the user.
After discussing Markov sources and various non-lossy compression algorithms like Shannon-Fano Codes and Huffman Codes and introducing local IFS fractals, a second (automatic) image compression method is developed and a C Source Code implementation for gray scale images is given.
In an appendix, the compression method is compared with Discrete Cosine Transform (DCT) compression methods like the JPEG (Joint Photographic Experts Group) algorithm. This comparison shows, that the fractal compression method, which is covered by US Patent # 5065447, provides efficient compression almost without the typical blockiness problem observed with classical DCT methods.
The book contains essentially all necessary mathematical tools needed for understanding the IFS theory, including proofs or references to the proofs. Therefore, it is very useful for learning the background of IFS compression.

Reviewer: H. Schichl (Wien)

MSC:

68U10	Computing methodologies for image processing
94A08	Image processing (compression, reconstruction, etc.) in information and communication theory
00A69	General applied mathematics
28A80	Fractals
37N99	Applications of dynamical systems
68-02	Research exposition (monographs, survey articles) pertaining to computer science
94-02	Research exposition (monographs, survey articles) pertaining to information and communication theory

Keywords:

fractal image compression; iterated function systems; contraction mapping theorem; IFS fractals