Fast Fractal Image Compression by Kicking Out Similar Domain Images

Background And Main Focus

Fractal encoding is a mathematical process which is used to encode bitmaps containing a real-world image as a set of mathematical data. This mathematical data describes the fractal properties of any image. Fractal encoding utilizes the fact that all natural, and most artificial, objects contain redundant information in the form of similar, repeating patterns (Benoit Mandelbrot,1982) first observed and described the occurrence of repeating patterns in many different structures; he called these repeating patterns as fractals. The theory of iterated function systems was introduced by (Hutchinson,1981). This theory is used to model the collections of contractive transformations in a metric space as dynamical systems(M. Barnsley,1988). His idea was to use the Contractive Mapping Fixed-Point Theorem to show the existence and uniqueness of fractal sets that arise as fixed points of such systems.

M. F. Barnsley observed that many fractals that can be very compactly specified by iterated function systems have a “natural” appearance. Barnsley with S. Demko gave the idea of using iterated function systems (IFS's) to encode images in year(M. Barnsley,1988). This was the seed of the inverse problem of fractal approximation; Barnsley and Demko were the first to suggest that IFS could be used to approximate natural objects. A moderate quality picture on a pixel-by-pixel basis might require more than 500,000 bytes (or characters) of data to store and communicate. But Barnsley’s thought if we find IFS whose attractor is the picture;as fairly complicated IFS consumes only a few thousand characters to represent the image. In this way, it occupies far less space to record the IFS than the original picture. Hence representation of image in the form of IFS can also be regarded as Image Compression. A doctoral student of Barnsley’s, A.E. Jacquin gave first publication on Fractal image compression with partitioned IFS (PIFS) in 1990 .Jacquin used a block classification scheme(B. Ramamurthy and A. Gersho, 1986,Nasser M. Nasrabadi, and Robert A. King,1988) for his encoding scheme, he partitioned the input image in sub-images called as ‘Range blocks’ and PIFS are applied on sub-images, rather than the entire image. Each range image is regarded as individual image. This scheme is used worldwide in practical implementation. He purposed the first automatic algorithm in software, in 1992.