Fractal encoding is a mathematical process used to encode bitmaps containing a real-world image as a set of mathematical data that describes the fractal properties of the image. Fractal encoding relies on the fact that all natural, and most artificial, objects contain redundant information in the form of similar, repeating patterns called fractals.
A fractal is a structure that is made up of similar forms and patterns that occur in many different sizes. The term fractal was first used by Benoit Mandelbrot to describe repeating patterns that he observed occurring in many different structures. These patterns appeared nearly identical in form at any size and occurred naturally in all things. Mandelbrot also discovered that these fractals could be described in mathematical terms and could be created using very small and finite algorithms and data.
Let's look at a real-world example. If you look at the surface of an object such as the floor currently beneath your feet, you will notice that there are many repeating patterns in its texture. The floor's surface may be wood, concrete, tile, carpet, or even dirt, but it still contains repeating patterns ranging in size from very small to very large.
If we make a copy of a small part of the floor's surface and compare it to every other part of the floor, we would find several areas that are nearly identical in appearance to our copy. If we change the copy slightly by scaling, rotating, or mirroring it, we can make it match even more parts of the floor. Once a match is found, we can then create a mathematical description of our copy, including any alterations we have made, and can store it, and the location of all of the parts of the floor it matches, as data.
If we repeat this process for the entire floor, we will end up with a set of mathematical equations called fractal codes that describe the entire surface of the floor in terms of its fractal properties. These mathematical equations can then be used to recreate an image of the entire floor.
The process illustrated in this example is very similar in concept to vector (2D) and 3D graphics, where mathematical descriptions of objects, rather than actual pictures of the objects themselves, are stored. The important difference between vector and fractal graphics is that fractal descriptions are derived from actual ecofactual patterns found in real-world objects, while vector and 3D objects are purely artificially generated structures that do not naturally contain fractal patterns.
Fractal encoding is largely used to convert bitmap images to fractal codes. Fractal decoding is just the reverse, in which a set of fractal codes are converted to a bitmap.
The encoding process is extremely computationally intensive. Millions or billions of iterations are required to find the fractal patterns in an image. Depending upon the resolution and contents of the input bitmap data, and output quality, compression time, and file size parameters selected, compressing a single image could take anywhere from a few seconds to a few hours (or more) on even a very fast computer.
Decoding a fractal image is a much simpler process. The hard work was performed finding all the fractals during the encoding process. All the decoding process needs to do is to interpret the fractal codes and translate them into a bitmap image.
Currently, the most popular method of fractal encoding is a process called the Fractal Transform created in 1988 by Michael F. Barnsley of Iterated Systems. Barnsley's transform was the first practical algorithm used to mathematically describe a real-world bitmap image in terms of its fractal properties.
Two tremendous benefits are immediately realized by converting conventional bitmap images to fractal data. The first is the ability to scale any fractal image up or down in size without the introduction of image artifacts or a loss in detail that occurs in bitmap images. This process of "fractal zooming" is independent of the resolution of the original bitmap image, and the zooming is limited only by the amount of available memory in the computer.
The second benefit is the fact that the size of the physical data used to store fractal codes is much smaller than the size of the original bitmap data. If fact, it is not uncommon for fractal images to be more than 100 times smaller than their bitmap sources. It is this aspect of fractal technology, called fractal compression, that has promoted the greatest interest within the computer imaging industry.
Fractal compression is lossy. The process of matching fractals does not involve looking for exact matches, but instead looking for "best fit" matches based on the compression parameters (encoding time, image quality, and size of output). But the encoding process can be controlled to the point where the image is "visually lossless." That is, you shouldn't be able to notice where the data was lost.
Fractal compression differs from other lossy compression methods, such as JPEG, in a number of ways. JPEG achieves compression by discarding image data that is not required for the human eye to perceive the image. The resulting data is then further compressed using a lossless method of compression. To achieve greater compression ratios, more image data must be discarded, resulting in a poorer quality image with a pixelized (blocky) appearance.
Fractal images are not based on a map of pixels, nor is the encoding weighted to the visual characteristics of the human eye. Instead, bitmap data is discarded when it is required to create a best-fit fractal pattern. Greater compression ratios are achieved using greater computationally intensive transforms that may degrade the image, but the distortion appears much more natural due to the fractal components.
Most other lossy methods are also symmetrical in nature. That is, a particular sequence of steps is used to compress an image, and the reverse of those steps is used to decompress it. Compression and decompression will take about the same amount of time as well. Fractal compression is an asymmetrical process, taking much longer to compress an image than to decompress it. This characteristic limits the usefulness of fractally compressed data to applications where image data is constantly decompressed but never recompressed. Fractal compression is therefore highly suited for use in image databases and CD-ROM applications.
The content and resolution of the source bitmap can greatly affect fractal compression. Images with a high fractal content (e.g., faces, landscapes, and intricate textures) result in much higher compression ratios than images with a low fractal content (e.g., charts, diagrams, text, and flat textures). High-resolution images may be compressed to achieve higher compression ratios and will still retain a high image quality. To retain a high quality for lower resolution images, the resulting compression ratio will be much lower. Images with a greater bit depth (such as 24-bit truecolor images) will also compress more efficiently than images with fewer bits per pixel (such as 8-bit gray-scale images).
The process of fractal compression is by no means in the public domain. There are many patents claiming a method of image data compression based on fractal transforms. Also, the exact process used by some fractal packages--including Barnsley's Fractal Transform--is considered proprietary.
A wealth of information on fractal compression is available both on the World Wide Web and in your local technical bookstore. On the Web the following sites will provide you with quite a bit of reading material and with links to other sites containing fractal information:
Waterloo fractal compression page
Yuval Fisher's fractal image compression page
Groupe Fractales
The Spanky Fractal Database
Dietmar Supe's FTP site for fractal papers
Fractal software packages on the Internet include:
RGB fractal compression tools
Yuval Fisher's fractal decompression code
Information on fractal encoding can also be found on the USENET newsgroups sci.fractals, comp.compression and sci.math.
Yuval Fisher's paper "Fractal Image Compression," SIGGRAPH '92 Course Notes, is a very good introduction to fractal compression and is available as a PostScript document at:
ftp://nic.funet.fi/pub/graphics/packages/fractal-image-compression/
There are many books on fractals and fractal compression. Probably the best for getting a programmer up to speed with fractal technology is:
Yuval Fisher, ed., Fractal Image Compression: Theory and Application to Digital Images, Springer Verlag, New York, 1995.
This book is a collection of article about fractal encoding that includes a non-mathematical introduction to fractal compression, description of modems for the encoding and decoding process, and C source code for a fractal encoder and decoder.
The following books also contain very good overviews of fractal technology:
Barnsley, Michael F., Fractals Everywhere, second edition, Academic Press, San Diego, 1993.
Barnsley, Michael F., The Desktop Fractal Design System Versions 1 and 2, second edition, Academic Press, San Diego, 1992.
Barnsley, Michael F., and Lyman P. Hurd, Fractal Image Compression, AK Peters Limited, 1993.
You might also want to look at the original Mandelbrot text:
Mandelbrot, Benoit B., The Fractal Geometry of Nature, WH Freeman & Co., New York, 1983.
The following journal articles are also recommended:
Anson, L.A., "Fractal Image Compression," Byte Magazine, October 1993.
Sloane, M.F and A.D., "A Better Way to Compress Images," Byte Magazine, January 1988.
McGregor, D.R., R.J. Fryer, P. Cockshott, and P. Murray, "Fast Fractal Compression," Dr. Dobb's Journal, vol. 21, no. 243, January 1996.
Iterated Systems produces the Images Incorporated fractal imaging application. This application supports the encoding and decoding of fractal image from over 20 different bitmap file formats. Iterated also sells a library of fractal routines you can incorporate directly into your own programs. You can contact Iterated Systems at:
Iterated Systems, Inc.
3525 Piedmont Road
Seven Piedmont Center, Suite 600
Atlanta GA 30305-1530
Voice: 800-437-2285
Fax: 404-264-8300 (sales)
Email: support@iterated.com (technical support)
WWW: http://www.iterated.com/
Two documents to read are the Iterated System's Fractal FAQ at:
http://www.iterated.com/nfaq.htm
and the Welcome to Fractals and Imaging document at:
http://www.iterated.com/nwelbook.htm
The Iterated Systems' Web site also provides much useful information, including Iterated's patent claims on fractal technology and its Fractal Image File (FIF) format.
Copyright © 1996, 1994 O'Reilly & Associates, Inc. All Rights Reserved.