08-08-2012, 03:29 PM
Fractal Image Compression
Fractal Image.doc (Size: 314.5 KB / Downloads: 106)
Abstract
This paper seeks to explain the emerging technology known as fractal image compression. It presents both the mathematical ideas and the practical techniques involved in compressing images by means of fractals. With claims of compression ratios in excess of 10 000 to 1, fractal compression is certainly a promising new technology. However, the method is in fact quite controversial, with some people claiming it doesn't work well, while others claim it works wonderfully; as the technology is fast developing, but as yet unproven. At the moment, very little is known about fractal compression and what is known is difficult to ascertain. The main aspects of the technology are patented by M. F. Barnsley, who pioneered fractal image compression. This paper attempts to clarify the key ideas behind the methodology; and includes an overview of the competition, which includes the JPEG standard and vector quantization. Included as an appendix is the source code for a model digital implementation of fractal image compression of binary black-and-white images, written in C. Examples of decompressed images are also included, as is an evaluation of the program.
Fractal image compression relies on the fact that all real-world images are rich in affine redundancy; that is, under suitable affine transformations, large bits of real-world images look like smaller bits of the same real-world image. The basic idea behind the method is to express the image as a set of local iterated function systems (IFSs). An IFS is just a set of contractive affine transformations. The IFS coefficients are then stored in place of the original. No information regarding the pixels is actually stored. When the original is required, the IFSs are iterated on an arbitrary starting image of the desired resolution. The image can then be displayed quickly and zooming will create infinite levels of (synthetic) fractal detail. The problem is how to efficiently generate the IFSs from the original image.
The hypothetical Multiple Reduction Photocopy Machine is used to illustrate the implementation of IFSs. Also, the classical Sierpinski triangle is used as an example of a self-similar shape to illustrate how IFSs work. One important result that is central to fractal image compression is known as the Collage Theorem, which was proved by M. Barnsley in his book Fractals Everywhere. The Collage Theorem states what an IFS must be like in order to represent an image. Also covered is what is known as the inverse problem, which involves going from a given image to an IFS that can generate a good approximation of the original. This remains unsolved.
Introduction
Compression
With the advent of multimedia, the necessity for the storage of large numbers of high quality images is increasing. One obstacle that has to be overcome is the large size of image files. For example, a single 800- by 600-pixel true-colour image requires three bytes per pixel, plus a header, which amounts to over 1.37 Mb of disk space, thus almost filling a 1.4Mb high-density diskette. Clearly, some form of compression is necessary. As well as saving storage space, compressed files take less time to transmit via modem, so money can be saved on both counts.
The choice of compression algorithm involves several conflicting considerations. These include degree of compression required, and the speed of operation. Obviously if one is attempting to run programs direct from their compressed state, decompression speed is paramount. The other consideration is size of compressed file versus quality of decompressed image.
There are essentially two sorts of data compression. 'Lossless' compression works by reducing the redundancy in the data. The decompressed data is an exact copy of the original, with no loss of data. Huffman Encoding and LZW are two examples of lossless compression algorithms. There are times when such methods of compression are unnecessarily exact. 'Lossy' compression sacrifices exact reproduction of data for better compression. It both removes redundancy and creates an approximation of the original. The JPEG standard is currently the most popular method of lossy compression. Obviously, a lossless compression method must be used with programs or text files, while lossy compression is really only suitable for graphics or sound data, where an exact reproduction is not necessary. Fractal image compression is a lossy compression method.
Fractals
The French mathematician Benoit B. Mandelbrot first coined the term fractal in 1975. He derived the word from the Latin fractus, which means "broken", or "irregular and fragmented". In fact, the birth of fractal geometry is usually traced to Mandelbrot and the 1977 publication of his seminal book The Fractal Geometry of Nature. Mandelbrot claimed that classical Euclidean geometry was inadequate at describing many natural objects, such as clouds, mountains, coastlines and trees. So he conceived and developed fractal geometry.
There are two main groups of fractals: linear and nonlinear. The latter are typified by the popular Mandelbrot set and Julia sets, which are fractals of the complex plane. However, the fractals used in image compression are linear, and of the real plane. So, the fractals used are not chaotic; in other words, they are not sensitive to initial conditions. They are the fractals from Iterated Function Theory. An Iterated Function System (IFS) is simply a set of contractive affine transformations. IFSs may efficiently produce shapes such as ferns, leaves and trees.
The Sierpinski Triangle
A classical example of a self-similar shape is the Sierpinski triangle, or gasket. It was named after the Polish mathematician Waclaw Sierpinski, who first described it in 1916. The Sierpinski triangle may be created using a Multiple Reduction Photocopy Machine in the following manner. An image is placed on the machine, reduced by one half and copied three times, once onto each vertex of a triangle.
Automatic Fractal Image Compression and the Fractal Transform
Local Iterated Function Systems
The Advantages of Representing Images Using Iterated Function Schemes
By utilizing the self-similarity and repetition in nature, a relatively small number of transformations (and probabilities if used) lead to very high compression ratios. Also, given a set of affine transformations, reproduction of the image is computationally straightforward, is well suited to parallel computation, and is stable – small changes in the transformations lead to small changes in the invariant set. The ability of the transformations to define the image at arbitrarily small scales, and the ease at which small regions may be zoomed in on are also points in favour of IFSs.
The Problem With Using Iterated Function Systems to Compress Images
The main disadvantage of the method is the difficulty of obtaining a set of transformations to represent a given image. None of the algorithms proposed for the "inverse problem" have been successfully used in practical image compression. In order to fully automate fractal image compression, an algorithm must be used which requires no 'user interference', such as adjusting the coefficients in an IFS. Standard IFSs are not, in fact, good for general and practical image compression. A high correlation between different parts of a picture are required. The method may be excellent for giving an overall picture of a tree, but is no use if the exact arrangement of the leaves on different branches is important.
Even if the inverse problem were solved, it may be to no avail. Real world scenes are very diverse in subject matter, there may be totally different looking objects in the same scene. They do not, on the whole, obey fractal geometry. Real ferns do not branch down to infinity, and they may be distorted, discoloured, perforated and torn; while other objects are even further from fractal geometry. One theoretical reason why IFSs may never be successfully used in compression is the fact that given the IFS for object A, and the IFS for object B, they cannot be combined to give the IFS for object A * B, or object A * B. In practical fractal compression, to capture the diversity of real images, what is used instead is the "fractal transform", which uses local (or partitioned) IFSs, in which, the (contractive) transformations do not map the whole image onto part of itself, but map one part of the image onto another (smaller) part of the image. They allow the compression process to be fully automated.
Fractal Image.doc (Size: 314.5 KB / Downloads: 106)
Abstract
This paper seeks to explain the emerging technology known as fractal image compression. It presents both the mathematical ideas and the practical techniques involved in compressing images by means of fractals. With claims of compression ratios in excess of 10 000 to 1, fractal compression is certainly a promising new technology. However, the method is in fact quite controversial, with some people claiming it doesn't work well, while others claim it works wonderfully; as the technology is fast developing, but as yet unproven. At the moment, very little is known about fractal compression and what is known is difficult to ascertain. The main aspects of the technology are patented by M. F. Barnsley, who pioneered fractal image compression. This paper attempts to clarify the key ideas behind the methodology; and includes an overview of the competition, which includes the JPEG standard and vector quantization. Included as an appendix is the source code for a model digital implementation of fractal image compression of binary black-and-white images, written in C. Examples of decompressed images are also included, as is an evaluation of the program.
Fractal image compression relies on the fact that all real-world images are rich in affine redundancy; that is, under suitable affine transformations, large bits of real-world images look like smaller bits of the same real-world image. The basic idea behind the method is to express the image as a set of local iterated function systems (IFSs). An IFS is just a set of contractive affine transformations. The IFS coefficients are then stored in place of the original. No information regarding the pixels is actually stored. When the original is required, the IFSs are iterated on an arbitrary starting image of the desired resolution. The image can then be displayed quickly and zooming will create infinite levels of (synthetic) fractal detail. The problem is how to efficiently generate the IFSs from the original image.
The hypothetical Multiple Reduction Photocopy Machine is used to illustrate the implementation of IFSs. Also, the classical Sierpinski triangle is used as an example of a self-similar shape to illustrate how IFSs work. One important result that is central to fractal image compression is known as the Collage Theorem, which was proved by M. Barnsley in his book Fractals Everywhere. The Collage Theorem states what an IFS must be like in order to represent an image. Also covered is what is known as the inverse problem, which involves going from a given image to an IFS that can generate a good approximation of the original. This remains unsolved.
Introduction
Compression
With the advent of multimedia, the necessity for the storage of large numbers of high quality images is increasing. One obstacle that has to be overcome is the large size of image files. For example, a single 800- by 600-pixel true-colour image requires three bytes per pixel, plus a header, which amounts to over 1.37 Mb of disk space, thus almost filling a 1.4Mb high-density diskette. Clearly, some form of compression is necessary. As well as saving storage space, compressed files take less time to transmit via modem, so money can be saved on both counts.
The choice of compression algorithm involves several conflicting considerations. These include degree of compression required, and the speed of operation. Obviously if one is attempting to run programs direct from their compressed state, decompression speed is paramount. The other consideration is size of compressed file versus quality of decompressed image.
There are essentially two sorts of data compression. 'Lossless' compression works by reducing the redundancy in the data. The decompressed data is an exact copy of the original, with no loss of data. Huffman Encoding and LZW are two examples of lossless compression algorithms. There are times when such methods of compression are unnecessarily exact. 'Lossy' compression sacrifices exact reproduction of data for better compression. It both removes redundancy and creates an approximation of the original. The JPEG standard is currently the most popular method of lossy compression. Obviously, a lossless compression method must be used with programs or text files, while lossy compression is really only suitable for graphics or sound data, where an exact reproduction is not necessary. Fractal image compression is a lossy compression method.
Fractals
The French mathematician Benoit B. Mandelbrot first coined the term fractal in 1975. He derived the word from the Latin fractus, which means "broken", or "irregular and fragmented". In fact, the birth of fractal geometry is usually traced to Mandelbrot and the 1977 publication of his seminal book The Fractal Geometry of Nature. Mandelbrot claimed that classical Euclidean geometry was inadequate at describing many natural objects, such as clouds, mountains, coastlines and trees. So he conceived and developed fractal geometry.
There are two main groups of fractals: linear and nonlinear. The latter are typified by the popular Mandelbrot set and Julia sets, which are fractals of the complex plane. However, the fractals used in image compression are linear, and of the real plane. So, the fractals used are not chaotic; in other words, they are not sensitive to initial conditions. They are the fractals from Iterated Function Theory. An Iterated Function System (IFS) is simply a set of contractive affine transformations. IFSs may efficiently produce shapes such as ferns, leaves and trees.
The Sierpinski Triangle
A classical example of a self-similar shape is the Sierpinski triangle, or gasket. It was named after the Polish mathematician Waclaw Sierpinski, who first described it in 1916. The Sierpinski triangle may be created using a Multiple Reduction Photocopy Machine in the following manner. An image is placed on the machine, reduced by one half and copied three times, once onto each vertex of a triangle.
Automatic Fractal Image Compression and the Fractal Transform
Local Iterated Function Systems
The Advantages of Representing Images Using Iterated Function Schemes
By utilizing the self-similarity and repetition in nature, a relatively small number of transformations (and probabilities if used) lead to very high compression ratios. Also, given a set of affine transformations, reproduction of the image is computationally straightforward, is well suited to parallel computation, and is stable – small changes in the transformations lead to small changes in the invariant set. The ability of the transformations to define the image at arbitrarily small scales, and the ease at which small regions may be zoomed in on are also points in favour of IFSs.
The Problem With Using Iterated Function Systems to Compress Images
The main disadvantage of the method is the difficulty of obtaining a set of transformations to represent a given image. None of the algorithms proposed for the "inverse problem" have been successfully used in practical image compression. In order to fully automate fractal image compression, an algorithm must be used which requires no 'user interference', such as adjusting the coefficients in an IFS. Standard IFSs are not, in fact, good for general and practical image compression. A high correlation between different parts of a picture are required. The method may be excellent for giving an overall picture of a tree, but is no use if the exact arrangement of the leaves on different branches is important.
Even if the inverse problem were solved, it may be to no avail. Real world scenes are very diverse in subject matter, there may be totally different looking objects in the same scene. They do not, on the whole, obey fractal geometry. Real ferns do not branch down to infinity, and they may be distorted, discoloured, perforated and torn; while other objects are even further from fractal geometry. One theoretical reason why IFSs may never be successfully used in compression is the fact that given the IFS for object A, and the IFS for object B, they cannot be combined to give the IFS for object A * B, or object A * B. In practical fractal compression, to capture the diversity of real images, what is used instead is the "fractal transform", which uses local (or partitioned) IFSs, in which, the (contractive) transformations do not map the whole image onto part of itself, but map one part of the image onto another (smaller) part of the image. They allow the compression process to be fully automated.