Fractal compression
Encyclopedia
Fractal compression is a lossy compression method for digital image
s, based on fractal
s. 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.
(IFS).
, where the image may be thought of as a subset of
. An IFS is a set of contraction mapping
s ƒ1,...,ƒN,
According to these mapping functions, the IFS describes a two-dimensional set S as the fixed point of the Hutchinson operator
That is, H is an operator mapping sets to sets, and S is the unique set satisfying H(S) = S. The idea is to construct the IFS such that this set S is the input binary image. The set S can be recovered from the IFS by fixed point iteration: for any nonempty compact
initial set A0, the iteration Ak+1 = H(Ak) converges to S.
The set S is self-similar because H(S) = S implies that S is a union of mapped copies of itself:
So we see the IFS is a fractal representation of S.
by considering the image's graph
as a subset of
. For a grayscale image u(x,y), consider the set
S = {(x,y,u(x,y))}. Then similar to the binary case, S is described by an IFS using a set of contraction mappings ƒ1,...,ƒN, but in
,
In the second step, it is important to find a similar block so that the IFS accurately represents the input image, so a sufficient number of candidate blocks for Di need to be considered. On the other hand, a large search considering many blocks is computationally costly.
This bottleneck of searching for similar blocks is why fractal encoding is much slower than for example DCT
and wavelet
based image representations.
At common compression ratios, 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.
Fractal interpolation maintains geometric detail very well compared to traditional interpolation methods like bilinear interpolation
and bicubic interpolation
.
led development of fractal compression in 1987, and was granted several patent
s 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 system
s. 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 $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.
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 was 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 their 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.
Numerous research papers have been published during the past few years discussing possible solutions to improve fractal algorithms and encoding hardware.
.
The Netpbm
library includes a Fiasco library.
There is a video library for fractal compression.
There is another example implementation from Femtosoft.
Digital image
A digital image is a numeric representation of a two-dimensional image. Depending on whether or not the image resolution is fixed, it may be of vector or raster type...
s, based on fractal
Fractal
A fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...
s. 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.
Iterated Function Systems
Fractal image representation can be described mathematically as an iterated function systemIterated function system
In mathematics, iterated function systems or IFSs are a method of constructing fractals; the resulting constructions are always self-similar....
(IFS).
For Binary Images
We begin with the representation of a binary imageBinary image
A binary image is a digital image that has only two possible values for each pixel. Typically the two colors used for a binary image are black and white though any two colors can be used. The color used for the object in the image is the foreground color while the rest of the image is the...
, where the image may be thought of as a subset of
. An IFS is a set of contraction mappingContraction mapping
In mathematics, a contraction mapping, or contraction, on a metric space is a function f from M to itself, with the property that there is some nonnegative real number k...
s ƒ1,...,ƒN,
According to these mapping functions, the IFS describes a two-dimensional set S as the fixed point of the Hutchinson operator
Hutchinson operator
In mathematics, in the study of fractals, a Hutchinson operator is a collection of functions on an underlying space E...
That is, H is an operator mapping sets to sets, and S is the unique set satisfying H(S) = S. The idea is to construct the IFS such that this set S is the input binary image. The set S can be recovered from the IFS by fixed point iteration: for any nonempty compact
Compact space
In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...
initial set A0, the iteration Ak+1 = H(Ak) converges to S.
The set S is self-similar because H(S) = S implies that S is a union of mapped copies of itself:
So we see the IFS is a fractal representation of S.
Extension to Grayscale
IFS representation can be extended to a grayscale imageGrayscale
In photography and computing, a grayscale or greyscale digital image is an image in which the value of each pixel is a single sample, that is, it carries only intensity information...
by considering the image's graph
Graph of a function
In mathematics, the graph of a function f is the collection of all ordered pairs . In particular, if x is a real number, graph means the graphical representation of this collection, in the form of a curve on a Cartesian plane, together with Cartesian axes, etc. Graphing on a Cartesian plane is...
as a subset of
. For a grayscale image u(x,y), consider the setS = {(x,y,u(x,y))}. Then similar to the binary case, S is described by an IFS using a set of contraction mappings ƒ1,...,ƒN, but in
,Encoding
A challenging problem of ongoing research in fractal image representation is how to choose the ƒ1,...,ƒN such that its fixed point approximates the input image, and how to do this efficiently. A simple approach for doing so is the following:- Partition the image domain into blocks Ri of size s×s.
- For each Ri, search the image to find a block Di of size 2s×2s that is very similar to Ri.
- Select the mapping functions such that H(Di) = Ri for each i.
In the second step, it is important to find a similar block so that the IFS accurately represents the input image, so a sufficient number of candidate blocks for Di need to be considered. On the other hand, a large search considering many blocks is computationally costly.
This bottleneck of searching for similar blocks is why fractal encoding is much slower than for example DCT
Discrete cosine transform
A discrete cosine transform expresses a sequence of finitely many data points in terms of a sum of cosine functions oscillating at different frequencies. DCTs are important to numerous applications in science and engineering, from lossy compression of audio and images A discrete cosine transform...
and wavelet
Wavelet
A wavelet is a wave-like oscillation with an amplitude that starts out at zero, increases, and then decreases back to zero. It can typically be visualized as a "brief oscillation" like one might see recorded by a seismograph or heart monitor. Generally, wavelets are purposefully crafted to have...
based image representations.
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 video is archived for distribution from disk storage or file downloads fractal compression becomes more competitive.At common compression ratios, up to about 50:1, Fractal compression
provides similar results to DCT-based
Discrete cosine transform
A discrete cosine transform expresses a sequence of finitely many data points in terms of a sum of cosine functions oscillating at different frequencies. DCTs are important to numerous applications in science and engineering, from lossy compression of audio and images A discrete cosine transform...
algorithms such as JPEG
JPEG
In computing, JPEG . The degree of compression can be adjusted, allowing a selectable tradeoff between storage size and image quality. JPEG typically achieves 10:1 compression with little perceptible loss in image quality....
.
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
Grayscale
In photography and computing, a grayscale or greyscale digital image is an image in which the value of each pixel is a single sample, that is, it carries only intensity information...
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 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
Bilinear interpolation
In mathematics, bilinear interpolation is an extension of linear interpolation for interpolating functions of two variables on a regular grid. The interpolated function should not use the term of x^2 or y^2, but x y, which is the bilinear form of x and y.The key idea is to perform linear...
and bicubic interpolation
Bicubic interpolation
In mathematics, bicubic interpolation is an extension of cubic interpolation for interpolating data points on a two dimensional regular grid. The interpolated surface is smoother than corresponding surfaces obtained by bilinear interpolation or nearest-neighbor interpolation...
.
History
Michael BarnsleyMichael Barnsley
Michael Fielding Barnsley is a British mathematician, researcher and an entrepreneur who has worked on fractal compression; he holds several patents on the technology. He received his Ph.D in Theoretical Chemistry from University of Wisconsin–Madison in 1972...
led development of fractal compression in 1987, and was granted several patent
Patent
A patent is a form of intellectual property. It consists of a set of exclusive rights granted by a sovereign state to an inventor or their assignee for a limited period of time in exchange for the public disclosure of an invention....
s 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
Fractal transform
The fractal transform is a technique invented by Michael Barnsley et al. to perform lossy image compression.This first practical fractal compression system for digital images resembles a vector quantization system using the image itself as the codebook....
using iterated function system
Iterated function system
In mathematics, iterated function systems or IFSs are a method of constructing fractals; the resulting constructions are always self-similar....
s. 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 $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
Genuine Fractals
Genuine Fractals is a Photoshop plug-in developed and distributed by onOne Software of Portland, Oregon. The original Windows version of Genuine Fractals was designed and developed by Altamira Group in Burbank, California under team leader Steven Bender in 1996...
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
Microsoft
Microsoft Corporation is an American public multinational corporation headquartered in Redmond, Washington, USA that develops, manufactures, licenses, and supports a wide range of products and services predominantly related to computing through its various product divisions...
in its Encarta
Encarta
Microsoft Encarta was a digital multimedia encyclopedia published by Microsoft Corporation from 1993 to 2009. , the complete English version, Encarta Premium, consisted of more than 62,000 articles, numerous photos and illustrations, music clips, videos, interactive contents, timelines, maps and...
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.
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
RealVideo
RealVideo is a suite of proprietary video compression formats developed by RealNetworks – the specific format changes with the version. It was first released in 1997 and is at version 10. RealVideo is supported on many platforms, including Windows, Mac, Linux, Solaris, and several mobile...
(Fractal) — and SoftVideo were early fractal video compression products. ClearFusion was Iterated's freely distributed streaming video plugin for web browsers. In 1994 SoftVideo was licensed to Spectrum Holobyte
Spectrum HoloByte
Spectrum HoloByte, Inc. was a video game developer and publisher originally based in Alameda, California.The company was founded in 1983 and was most famous for its simulation games, notably the Falcon series of flight simulators and Vette!, a driving simulator from 1989...
for use in its CD-ROM
CD-ROM
A CD-ROM is a pre-pressed compact disc that contains data accessible to, but not writable by, a computer for data storage and music playback. The 1985 “Yellow Book” standard developed by Sony and Philips adapted the format to hold any form of binary data....
games including Falcon Gold and Star Trek: The Next Generation A Final Unity.
In 1996 Iterated Systems Inc. announced an alliance with the Mitsubishi
Mitsubishi
The Mitsubishi Group , Mitsubishi Group of Companies, or Mitsubishi Companies is a Japanese multinational conglomerate company that consists of a range of autonomous businesses which share the Mitsubishi brand, trademark and legacy...
Corporation to market ClearVideo to their Japanese customers. The original ClearVideo 1.2 decoder driver is still supported by Microsoft in Windows Media Player
Windows Media Player
Windows Media Player is a media player and media library application developed by Microsoft that is used for playing audio, video and viewing images on personal computers running the Microsoft Windows operating system, as well as on Pocket PC and Windows Mobile-based devices...
although the encoder is no longer supported.
Numerous research papers have been published during the past few years discussing possible solutions to improve fractal algorithms and encoding hardware.
Open Source
A library called Fiasco was created by Ullrich Hafner and described in Linux JournalLinux Journal
Linux Journal is a monthly technology magazine published by Belltown Media, Inc. of Houston, Texas. The magazine focuses specifically on Linux, allowing the content to be a highly specialized source of information for open source enthusiasts.-History:...
.
The Netpbm
Netpbm
Netpbm is an open source package of graphics programs and a programming library, used mainly in the Unix world. It is a highly portable package, working under many Unix platforms, Windows, Mac OS X, VMS, Amiga OS and others and is included in all major open source Unix-like operating system...
library includes a Fiasco library.
There is a video library for fractal compression.
There is another example implementation from Femtosoft.
External links
- Pulcini and Verrando's Compressor
- Waterloo Fractal Coding Project Formerly the Waterloo Fractal Compression Project
- 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
- Superfractals website devoted to fractals by the inventor of fractal compression