Fractal compression

Fractal compression is a lossy image compression method using fractals to achieve high levels of compression. The method is best suited for photographs of natural scenes (trees, mountains, ferns, clouds). The fractal compression technique relies on the fact that in certain images, parts of the image resemble other parts of the same image. Fractal algorithms convert these parts, or more precisely, geometric shapes into mathematical data called "fractal codes" which are used to recreate the encoded image. Fractal compression differs from pixel-based compression schemes such as JPEG, GIF and MPEG since no pixels are saved. Once an image has been converted into fractal code its relationship to a specific resolution has been lost, it becomes resolution independent since the image can be recreated to fill any screen size.

The encoding process is extremely computationally intensive, however, the decoding process is done in near real-time.

Michael Barnsley led development of fractal compression in 1987, and holds several patents on the technology.^[1] The most widely known practical fractal compression algorithm was invented by Barnsley and Alan Sloan. Barnsley's graduate student Arnaud Jacquin implemented the first automatic algorithm in software in 1992.^[2][3]All methods are based on the fractal transform using iterated function systems. Michael Barnsley and Alan Sloan formed Iterated Systems Inc.^[4] in 1987 which was granted over 20 additional patents related to fractal compression.

A major breakthrough for Iterated Systems Inc. was the automatic fractal transform process which eliminated the need for human intervention during compression as was the case in early experimentation with fractal compression technology. In 1992 Iterated Systems Inc. received a $2.1 million government grant^[5] to develop a prototype digital image storage and decompression chip using fractal transform image compression technology.

Still fractal image compression has been used in a number of commercial applications. onOne Software developed under license from Iterated Systems Inc. Genuine Fractals 5^[6][7]which is a Photoshop plugin capable of saving files in compressed FIF (Fractal Image Format). To date the most successful use of still fractal image compression is by Microsoft in its Encarta multimedia encyclopedia^[8], also under license.

Iterated Systems Inc. supplied a shareware encoder (Fractal Imager), a stand alone decoder^[9], a Netscape plug-in decoder and a development package for use under Windows. As wavelet based methods of image compression improved and were more easily licensed by commercial software vendors the anticipated widespread adoption of the Fractal Image Format failed to evolve.

During the 1990's Iterated Systems Inc. and it partners expended considerable resources to bring fractal compression to video. While compression results were promising computer hardware of that time lacked the processing power for fractal video compression to be practical beyond a few select usages. Up to 15 hours were required to compress a single minute of video.

ClearVideo also known as RealVideo^[10] (Fractal) and SoftVideo were early fractal video compression products with limited commercial success mainly due to the excessive encoding resource requirements. In 1994 SoftVideo was licensed to Spectrum Holobyte for use in its CD-ROM games including Falcon Gold and Star Trek: The Next Generation A Final Unity^[11].

In 1996 Iterated Systems Inc. announced^[12] an alliance with the Mitsubishi Corporation to market ClearVideo to their Japanese customers. The original ClearVideo 1.2 decoder driver is still supported^[13] by Microsoft in Windows Media Player and the decoder is currently available for download^[14] although the encoder is no longer supported.

Patent restrictions have limited commercial interest in fractal video compression since the late 1990's while existing license holders made no further progress in dealing with the encoding issues. Numerous research papers have been published during the past few years discussing possible solutions to improve fractal algorithms and encoding hardware.

See also

• Fractal

Notes

1. ^ U.S. Patent 4,941,193  – Barnsley and Sloan's first iterated function system patent, filed in October 1987
2. ^ Using Fractal Coding to Index Image Content for a Digital Library Tech report
3. ^ Arnaud E. Jacquin. Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations. IEEE Transactions on Image Processing, 1(1), 1992.
4. ^ Iterated Systems Inc. changed its name to MediaBin Inc. Inc. in 2001 and in turn was bought out by Interwoven, Inc. in 2003)
5. ^ government grant
6. ^ Genuine Fractals 5
7. ^ Genuine Fractals Product Review
8. ^ Mathematics Awareness Week - April 1998 reference to Microsoft's Encarta fractal image compression
9. ^ Iterated's fractal image decoder deco_32.dll
10. ^ RealNetworks ClearVideo press release
11. ^ 1994 Manual specifying on page 11 SoftVideo under license to Spectrum Holobyte
12. ^ Mitsubishi Corporation ClearVideo press release
13. ^ Microsoft ClearVideo support
14. ^ ClearVideo codec download

External Links

• Pulcini and Verrando's Compressor
• Waterloo Fractal Coding Project Formerly the Waterloo Fractal Compression Project
• Web Archive copy of Fractal Image Encoding website
• Keith Howell's 1993 M.Sc. dissertation Fractal Image Compression for Spaceborne Transputers
• My Main Squeeze: Fractal Compression, Nov 1993, Wired.
• Fractal Basics description at FileFormat.Info

de:Fraktale Bildkompression

fr:Compression fractale it:Compressione frattale ja:フラクタル圧縮 pl:Kompresja fraktalna ru:Алгоритм фрактального сжатия