04-06-2012, 04:24 PM
Fractal Image Compression
Fractal Image Compression.DOC (Size: 236.5 KB / Downloads: 5)
Introduction
1.1 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.
1.2 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.
This presented an intriguing possibility; since fractal mathematics is good for generating natural looking images, could it not, in the reverse direction, be used to compress images? The possibility of using fractals for image encoding rests on two suppositions:
1. many natural scenes possess this detail within detail structure (e.g. clouds);
2. an IFS can be found that generates a close approximation of a scene using only a few transformations.
The first point is true, but excludes many real world images, while the second leads to the so called "inverse problem", which is explained later.
1.3 A Brief History of Fractal Image Compression
1977 Benoit Mandelbrot finishes the first edition of "The Fractal Geometry of Nature"
1981 John E. Hutchinson publishes "Fractals and Self Similarity"
1983 Revised edition of "The Fractal Geometry of Nature" is published
1985 Michael F. Barnsley and Stephen Demko introduce Iterated Function Theory in their paper "Iterated Function Systems and the Global Construction of Fractals"
1987 Iterated Systems Incorporated is founded in Georgia, US
1988 Michael Barnsley and Alan D. Sloan wrote the article "A Better Way to Compress Images" published in Byte, claiming fractal compression ratios of 10 000 to 1
Barnsley publishes the book "Fractals Everywhere", which presents the mathematics of Iterated Function Systems, and proves a result known as the Collage Theorem
1990 Barnsley's first patent is granted (US Patent # 4 941 193)
1991 M. Barnsley and A. Sloan are granted US Patent # 5 065 447 "Method and Apparatus for Processing Digital Data"
J.M. Beaumont publishes a paper "Image Data Compression Using Fractal Techniques"
1992 Arnaud E. Jacquin publishes an article that describes the first practical fractal image compression method
Iterated Systems Inc finally break even and begin to make money
Microsoft Corporation publish the multimedia encyclopedia "Microsoft Encarta" which uses fractal image compression to great effect
1993 The book "Fractal Image Compression" by Michael Barnsley and Lyman P. Hurd is published
The Iterated Systems' product line matures
The Multiple Reduction Photocopy Machine
The Multiple Reduction Photocopy Machine is an imaginary image duplicator, which may be used to find successive approximations for the attractor of an IFS. It functions like a normal photocopy machine with the following exceptions:
1. The machine has several lenses, to create multiple copies of the original.
2. Each lens reduces the size of the original.
3. The copier operates in a feedback loop; the output of one stage becomes the input to the next.
The lenses can be set for different reduction factors, and the reduced (output) images can be positioned at any desired location. Thus, the image may undergo any contractive affine transformation. The initial input can be anything. When the machine is run, the output tends towards a limiting image, which is independent of the initial image. The limiting image is the fixed point, or the attractor.
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. If the corresponding contractive affine transformations are written in the form:
Fractal Image Compression.DOC (Size: 236.5 KB / Downloads: 5)
Introduction
1.1 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.
1.2 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.
This presented an intriguing possibility; since fractal mathematics is good for generating natural looking images, could it not, in the reverse direction, be used to compress images? The possibility of using fractals for image encoding rests on two suppositions:
1. many natural scenes possess this detail within detail structure (e.g. clouds);
2. an IFS can be found that generates a close approximation of a scene using only a few transformations.
The first point is true, but excludes many real world images, while the second leads to the so called "inverse problem", which is explained later.
1.3 A Brief History of Fractal Image Compression
1977 Benoit Mandelbrot finishes the first edition of "The Fractal Geometry of Nature"
1981 John E. Hutchinson publishes "Fractals and Self Similarity"
1983 Revised edition of "The Fractal Geometry of Nature" is published
1985 Michael F. Barnsley and Stephen Demko introduce Iterated Function Theory in their paper "Iterated Function Systems and the Global Construction of Fractals"
1987 Iterated Systems Incorporated is founded in Georgia, US
1988 Michael Barnsley and Alan D. Sloan wrote the article "A Better Way to Compress Images" published in Byte, claiming fractal compression ratios of 10 000 to 1
Barnsley publishes the book "Fractals Everywhere", which presents the mathematics of Iterated Function Systems, and proves a result known as the Collage Theorem
1990 Barnsley's first patent is granted (US Patent # 4 941 193)
1991 M. Barnsley and A. Sloan are granted US Patent # 5 065 447 "Method and Apparatus for Processing Digital Data"
J.M. Beaumont publishes a paper "Image Data Compression Using Fractal Techniques"
1992 Arnaud E. Jacquin publishes an article that describes the first practical fractal image compression method
Iterated Systems Inc finally break even and begin to make money
Microsoft Corporation publish the multimedia encyclopedia "Microsoft Encarta" which uses fractal image compression to great effect
1993 The book "Fractal Image Compression" by Michael Barnsley and Lyman P. Hurd is published
The Iterated Systems' product line matures
The Multiple Reduction Photocopy Machine
The Multiple Reduction Photocopy Machine is an imaginary image duplicator, which may be used to find successive approximations for the attractor of an IFS. It functions like a normal photocopy machine with the following exceptions:
1. The machine has several lenses, to create multiple copies of the original.
2. Each lens reduces the size of the original.
3. The copier operates in a feedback loop; the output of one stage becomes the input to the next.
The lenses can be set for different reduction factors, and the reduced (output) images can be positioned at any desired location. Thus, the image may undergo any contractive affine transformation. The initial input can be anything. When the machine is run, the output tends towards a limiting image, which is independent of the initial image. The limiting image is the fixed point, or the attractor.
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. If the corresponding contractive affine transformations are written in the form:
