Information about 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.
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 (U.S. Patent 5,065,447). Barnsley's graduate student Arnaud Jacquin purposed the first automatic algorithm in software in 1992.[2][3]All methods are based on the fractal transform using iterated function systems.
Fractal compression appeared to be a promising technology in the late 1980s, when in some circumstances it appeared to compress much better than JPEG, its main competitor at that time. However, fractal compression never achieved widespread use. Fractal compression is much slower to compress and decompress than JPEG. Its patents were not widely licensed. Fractal compression only has a large advantage over JPEG at low image quality levels, which is usually undesirable. The claim that fractal compressed images, when enlarged beyond their original size, looked better than similarly enlarged JPEG images seems also to have been an irrelevant distinction.
It has also turned out that the most impressive examples of fractal compression require considerable human intervention: the process of generating an image from its fractal representation is easy to automate, but reversing the procedure to generate an optimal fractal representation of an image is very difficult. Most real-world images have heterogeneous mathematical properties; for instance a photograph in which mountains and clouds and trees might be represented by several classes of fractal representation; automated recognition of which class works best for which part of the image is a difficult problem in AI. Although Barnsley's collage theorem proves that for a large class of real-world images, compact fractal representations must exist; it does not provide a general-purpose algorithm for the construction of such representations. According to the compression FAQ, fractal image compression is sardonically known as the "graduate student algorithm": lock a graduate student in a room with a computer until they solve your problem. In practice, to achieve high image quality with compression ratios that significantly exceed those of JPEG requires significant amounts of human effort.
(See for formats and for codecs)
..... Click the link for more information.
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 (U.S. Patent 5,065,447). Barnsley's graduate student Arnaud Jacquin purposed the first automatic algorithm in software in 1992.[2][3]All methods are based on the fractal transform using iterated function systems.
Fractal compression appeared to be a promising technology in the late 1980s, when in some circumstances it appeared to compress much better than JPEG, its main competitor at that time. However, fractal compression never achieved widespread use. Fractal compression is much slower to compress and decompress than JPEG. Its patents were not widely licensed. Fractal compression only has a large advantage over JPEG at low image quality levels, which is usually undesirable. The claim that fractal compressed images, when enlarged beyond their original size, looked better than similarly enlarged JPEG images seems also to have been an irrelevant distinction.
It has also turned out that the most impressive examples of fractal compression require considerable human intervention: the process of generating an image from its fractal representation is easy to automate, but reversing the procedure to generate an optimal fractal representation of an image is very difficult. Most real-world images have heterogeneous mathematical properties; for instance a photograph in which mountains and clouds and trees might be represented by several classes of fractal representation; automated recognition of which class works best for which part of the image is a difficult problem in AI. Although Barnsley's collage theorem proves that for a large class of real-world images, compact fractal representations must exist; it does not provide a general-purpose algorithm for the construction of such representations. According to the compression FAQ, fractal image compression is sardonically known as the "graduate student algorithm": lock a graduate student in a room with a computer until they solve your problem. In practice, to achieve high image quality with compression ratios that significantly exceed those of JPEG requires significant amounts of human effort.
See also
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.
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.
External links
- Fractal Image Compression for Spaceborne Transputers
- Pulcini and Verrando's Compressor
- Waterloo Fractal Coding Project Formerly the Waterloo Fractal Compression Project
- Web Archive copy of Fractal Image Encoding website
- onOne software Genuine Fractals 5
- Keith Howell's 1993 M.Sc. dissertation Fractal Image Compression for Spaceborne Transputers
- Giovambattista Pulcini's Fractal Image Compression description and windows binary
| Lossless compression methods | ||||
|---|---|---|---|---|
| Audio compression methods |
| |||
| Image compression methods |
| |||
| Video compression |
| |||
| Timeline of information theory, data compression, and error-correcting codes | ||||
lossy compression method is one where compressing data and then decompressing it retrieves data that may well be different from the original, but is close enough to be useful in some way.
..... Click the link for more information.
..... Click the link for more information.
fractal.]]
A fractal is generally "a rough or fragmented geometric shape that can be subdivided in parts, each of which is (at least approximately) a reduced-size copy of the whole,"[1] a property called self-similarity.
..... Click the link for more information.
A fractal is generally "a rough or fragmented geometric shape that can be subdivided in parts, each of which is (at least approximately) a reduced-size copy of the whole,"[1] a property called self-similarity.
..... Click the link for more information.
tree is a perennial woody plant. It is sometimes defined as a woody plant that attains diameter of 10 cm (30 cm girth) or more at breast height (130 cm above ground).
..... Click the link for more information.
..... Click the link for more information.
mountain is a landform that extends above the surrounding terrain in a limited area. A mountain is generally steeper than a hill, but there is no universally accepted standard definition for the height of a mountain or a hill although a mountain usually has an identifiable
..... Click the link for more information.
..... Click the link for more information.
FERN
Charity
Founded 1995, The Netherlands
Headquarters Brussels, Belgium and Moreton-in-Marsh, UK
Key people Jutta Kill
Leontien Krul
Iola Leal Riesco
Judith Neyer
Saskia Ozinga
Industry Environmentalism
..... Click the link for more information.
Charity
Founded 1995, The Netherlands
Headquarters Brussels, Belgium and Moreton-in-Marsh, UK
Key people Jutta Kill
Leontien Krul
Iola Leal Riesco
Judith Neyer
Saskia Ozinga
Industry Environmentalism
..... Click the link for more information.
cloud is a visible mass of condensed droplets, frozen crystals suspended in the atmosphere above the surface of the Earth or another planetary body, such as a moon. (Clouds can also occur as masses of material in interstellar space, where they are called interstellar clouds and
..... Click the link for more information.
..... Click the link for more information.
Michael F. Barnsley is a researcher and an entrepreneur who has worked on fractal compression; he holds several patents on the technology. In 1987 he founded Iterated Systems Incorporated, and in 1988 he published a book entitled Fractals Everywhere.
..... Click the link for more information.
..... Click the link for more information.
patent is a set of exclusive rights granted by a state to a patentee for a fixed period of time in exchange for a disclosure of an invention.
The procedure for granting patents, the requirements placed on the patentee and the extent of the exclusive rights vary widely
..... Click the link for more information.
The procedure for granting patents, the requirements placed on the patentee and the extent of the exclusive rights vary widely
..... Click the link for more information.
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.
..... Click the link for more information.
..... Click the link for more information.
iterated function systems or IFSs are a method of constructing fractals; the resulting constructions are always self-similar.
IFS fractals as they are normally called can be of any number of dimensions, but are commonly computed and drawn in 2D.
..... Click the link for more information.
IFS fractals as they are normally called can be of any number of dimensions, but are commonly computed and drawn in 2D.
..... Click the link for more information.
JPEG
A photo of a flower compressed with successively more lossy compression ratios from left to right.
File extension:
..... Click the link for more information.
A photo of a flower compressed with successively more lossy compression ratios from left to right.
File extension:
.jpeg, .jpg, .jpe
.jfif, .jfi, ...... Click the link for more information.
fractal.]]
A fractal is generally "a rough or fragmented geometric shape that can be subdivided in parts, each of which is (at least approximately) a reduced-size copy of the whole,"[1] a property called self-similarity.
..... Click the link for more information.
A fractal is generally "a rough or fragmented geometric shape that can be subdivided in parts, each of which is (at least approximately) a reduced-size copy of the whole,"[1] a property called self-similarity.
..... Click the link for more information.
iterated function systems or IFSs are a method of constructing fractals; the resulting constructions are always self-similar.
IFS fractals as they are normally called can be of any number of dimensions, but are commonly computed and drawn in 2D.
..... Click the link for more information.
IFS fractals as they are normally called can be of any number of dimensions, but are commonly computed and drawn in 2D.
..... Click the link for more information.
data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an un-encoded representation would use through use of specific encoding schemes.
..... Click the link for more information.
..... Click the link for more information.
Lossless data compression is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. This can be contrasted to lossy data compression, which does not allow the exact original data to be reconstructed from the
..... Click the link for more information.
..... Click the link for more information.
Information theory is a branch of applied mathematics and engineering involving the quantification of information to find fundamental limits on compressing and reliably communicating data.
..... Click the link for more information.
..... Click the link for more information.
Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable.
Shannon entropy quantifies the information contained in a piece of data: it is the minimum average message length, in bits (if using base-2 logarithms), that must
..... Click the link for more information.
Shannon entropy quantifies the information contained in a piece of data: it is the minimum average message length, in bits (if using base-2 logarithms), that must
..... Click the link for more information.
In computer science, the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity
..... Click the link for more information.
..... Click the link for more information.
Redundancy in information theory is the number of bits used to transmit a message minus the number of bits of actual information in the message. Informally, it is the amount of wasted "space" used to transmit certain data.
..... Click the link for more information.
..... Click the link for more information.
In information theory an entropy encoding is a lossless data compression scheme that is independent of the media’s specific characteristics.
One of the main types of entropy coding assigns codes to symbols so as to match code lengths with the probabilities of the
..... Click the link for more information.
One of the main types of entropy coding assigns codes to symbols so as to match code lengths with the probabilities of the
..... Click the link for more information.
Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way
..... Click the link for more information.
..... Click the link for more information.
Adaptive Huffman coding (also called Dynamic Huffman coding) is an adaptive coding technique based on Huffman coding, building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows one-pass encoding and adaptation to
..... Click the link for more information.
..... Click the link for more information.
Arithmetic coding is a method for lossless data compression. Normally, a string of characters such as the words "hello there" is represented using a fixed number of bits per character, as in the ASCII code.
..... Click the link for more information.
..... Click the link for more information.
Range encoding is a form of arithmetic coding, a data compression method, that is believed to be free from arithmetic coding related patents. It is on this basis that interest in range encoding has arisen, particularly in the open source community.
..... Click the link for more information.
..... Click the link for more information.
..... Click the link for more information.
An Exponential-Golomb code (or just Exp-Golomb code) of order is a type of universal code, parameterized by a whole number . To encode a nonnegative integer in an order- exp-Golomb code, one can use the following method:
..... Click the link for more information.
..... Click the link for more information.
universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic (i.e.
..... Click the link for more information.
..... Click the link for more information.
Elias gamma code is a universal code encoding positive integers. It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.
To code a number:
..... Click the link for more information.
To code a number:
- Write it in binary.
..... Click the link for more information.
Fibonacci coding is a universal code which encodes positive integers into binary code words. All tokens end with "11" and have no "11" before the end.
The formula used to generate Fibonacci codes is:
where F(i) is the i-th Fibonacci number.
..... Click the link for more information.
The formula used to generate Fibonacci codes is:
where F(i) is the i-th Fibonacci number.
..... Click the link for more information.
A dictionary coder, also sometimes known as a substitution coder, is any of a number of lossless data compression algorithms which operate by searching for matches between the text to be compressed and a set of strings contained in a data structure (called the 'dictionary')
..... Click the link for more information.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
