Fractal compression

A lossy compression method for digital images, based on fractals.

Fractal compression is a lossy compression method for digital images, based on fractals. The method is best suited for textures and natural images, relying on the fact that parts of an image often resemble other parts of the same image. Fractal algorithms convert these parts into mathematical data called "fractal codes" which are used to recreate the encoded image.

Features

With fractal compression, encoding is extremely computationally expensive because of the search used to find the self-similarities. Decoding, however, is quite fast. While this asymmetry has so far made it impractical for real-time applications when a video is archived for distribution from disk storage or file downloads fractal compression becomes more competitive.

A common compression ratio, up to about 50:1, Fractal compression provides similar results to DCT-based algorithms such as JPEG. At high compression ratios, fractal compression may offer superior quality. For satellite imagery, ratios of over 170:1 have been achieved with acceptable results. Fractal video compression ratios of 25:1–244:1 have been achieved in reasonable compression times (2.4 to 66 sec/frame).

Compression efficiency increases with higher image complexity and color depth, compared to simple grayscale images.

Resolution independence and fractal scaling

An inherent feature of fractal compression is that images become resolution independent after being converted to fractal code. This is because of the iterated function systems in the compressed file scale indefinitely. This indefinite scaling property of a fractal is known as "fractal scaling".

Fractal interpolation

The resolution independence of a fractal-encoded image can be used to increase the display resolution of an image. This process is also known as "fractal interpolation". In fractal interpolation, an image is encoded into fractal codes via fractal compression and subsequently decompressed at a higher resolution. The result is an up-sampled image in which iterated function systems have been used as the interpolant. Fractal interpolation maintains geometric detail very well compared to traditional interpolation methods like bilinear interpolation and bicubic interpolation. Since the interpolation cannot reverse Shannon entropy however, it ends up sharpening the image by adding random instead of meaningful detail. One cannot, for example, enlarge an image of a crowd where each person's face is one or two pixels and hope to identify them.

History

Michael Barnsley led the development of fractal compression in 1987 and was granted several patents on the technology. 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. All methods are based on the fractal transform using iterated function systems. Michael Barnsley and Alan Sloan formed Iterated Systems Inc. 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 US$2.1 million government grant to develop a prototype digital image storage and decompression chip using fractal transform image compression technology.

Fractal image compression has been used in a number of commercial applications: onOne Software, developed under license from Iterated Systems Inc., Genuine Fractals 5 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, also under license.

Iterated Systems Inc. supplied a shareware encoder (Fractal Imager), a stand-alone decoder, 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 adoption of the Fractal Image Format failed to evolve. The redistribution of the "decompressor DLL" provided by the ColorBox III SDK was governed by restrictive per-disk or year-by-year licensing regimes for proprietary software vendors and by a discretionary scheme that entailed the promotion of the Iterated Systems products for certain classes of other users.

During the 1990s Iterated Systems Inc. and its 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 (Fractal) – and SoftVideo were early fractal video compression products. ClearFusion was Iterated's freely distributed streaming video plugin for web browsers. In 1994 SoftVideo has licensed to Spectrum Holobyte for use in its CD-ROM games including Falcon Gold and Star Trek: The Next Generation A Final Unity.

In 1996, Iterated Systems Inc. announced an alliance with the mitsubishi Corporation to market ClearVideo to its Japanese customers. The original ClearVideo 1.2 decoder driver is still supported by microsoft in Windows Media Player although the encoder is no longer supported.

Two firms, Total Multimedia Inc. and Dimension, both claim to own or have the exclusive license to Iterated's video technology, but neither has yet released a working product. The technology basis appears to be Dimension's U.S. patents 8639053 and 8351509, which have been considerably analyzed. In summary, it is a simple quadtree block-copying system with neither the bandwidth efficiency nor PSNR quality of traditional DCT-based codecs. In January 2016, TMMI announced that it was abandoning fractal-based technology altogether.

Numerous research papers have been published during the past few years discussing possible solutions to improve fractal algorithms and encoding hardware.

source
This entry was adapted from content published on wikipedia.org
Modified
The content of this entry was last modified on February 20, 2020, 5:06 pm (5 Months ago)
Videocide.com is service provided by Codecide, a company located in Chicago, IL USA.