Fast Fractal Image Compression by Kicking Out Similar Domain Images

Fast Fractal Image Compression by Kicking Out Similar Domain Images

Shilpi Sharma (Birla Institute of Technology and Science, India), Arvind Kumar Kourav (Birla Institute of Technology and Science, India) and Vimal Tiwari (Birla Institute of Technology and Science, India)
DOI: 10.4018/978-1-5225-3870-7.ch019


Fractal algorithms are used to represent similar parts of images into mathematical transforms that can recreate the original image. This chapter presents a fast fractal image compression technique via domain kick-out method, based on averaging of domain images to discard redundant domain images. It accelerates the encoding process by reducing the size of the domain pool. Results of a simulation on the proposed speedup technique on three standard test images shows that performance of the proposed technique is far superior to the present kick out methods of fractal image compression. It has reported a speedup ratio of 31.07 in average while resulting into compression ratio and retrieved image quality comparable to Jacquin's full search method.
Chapter Preview

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.

Key Terms in this Chapter

Iterated Function System (IFS): Iterated function systems are a method of constructing fractals; the resulting fractals are often self-similar. IFS fractals are more related to set theory than fractal geometry.

Multi-Resolution Analysis (MRA): A multiresolution analysis (MRA) or multiscale approximation (MSA) is the design method of most of the practically relevant discrete wavelet transforms (DWT) and the justification for the algorithm of the fast wavelet transform (FWT).

Wavelet-Based Fractal Transform (WBFT): Wavelet - based fractal transform (WBFT) links the theory of multiresolution analysis (MBA) with iterated function systems (IFS).

Discrete Cosine Transform (DCT): The discrete cosine transform (DCT) helps separate the image into parts (or spectral sub-bands) of differing importance (with respect to the image's visual quality). The DCT is similar to the discrete Fourier transform: it transforms a signal or image from the spatial domain to the frequency domain.

Complete Chapter List

Search this Book: