Fractal transform
Encyclopedia
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.
A1.
Downsample it by a factor of 2 to produce image A2.
Now, for each block B1 of 4x4 pixels in A1, find the corresponding block B2 in A2 most similar to B1, and then find the grayscale
or RGB
offset and gain from A2 to B2.
For each destination block, output the positions of the source blocks and the color offsets and gains.
Downsample A1 down by a factor of 2 to produce image A2. Then copy blocks from A2 to A1 as directed by the compressed data, multiplying by the respective gains and adding the respective color offsets.
This algorithm is guaranteed to converge to an image, and it should appear similar to the original image.
In fact, a slight modification of the decompressor to run at block sizes larger than 4x4 pixels produces a method of stretching images without causing the blockiness or blurriness of traditional linear
resampling
algorithm
s.
and friends own numerous patent
s in the United States and elsewhere on what this article describes. (These include U.S. Patents 4,941,193, 5,065,447, 5,384,867, 5,416,856, and 5,430,812.) These patents have hindered widespread adoption of the fractal transform in image coding.
If you live in United States
or other country with software patent
s, you can do fractal compression for research purposes (patent law allows this) but for anything more than that, you would need to get permission from the patent owners. That usually means paying them a license fee to use the technology.
Michael 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...
et al. to perform lossy
Lossy data compression
In information technology, "lossy" compression is a data encoding method that compresses data by discarding some of it. The procedure aims to minimize the amount of data that need to be held, handled, and/or transmitted by a computer...
image compression
Image compression
The objective of image compression is to reduce irrelevance and redundancy of the image data in order to be able to store or transmit data in an efficient form.- Lossy and lossless compression :...
.
This first practical fractal compression
Fractal compression
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...
system for digital images resembles a vector quantization
Vector quantization
Vector quantization is a classical quantization technique from signal processing which allows the modeling of probability density functions by the distribution of prototype vectors. It was originally used for data compression. It works by dividing a large set of points into groups having...
system using the image itself as the codebook.
Fractal transform compression
Start with a digital imageImage
An image is an artifact, for example a two-dimensional picture, that has a similar appearance to some subject—usually a physical object or a person.-Characteristics:...
A1.
Downsample it by a factor of 2 to produce image A2.
Now, for each block B1 of 4x4 pixels in A1, find the corresponding block B2 in A2 most similar to B1, and then find the 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...
or RGB
RGB color space
An RGB color space is any additive color space based on the RGB color model. A particular RGB color space is defined by the three chromaticities of the red, green, and blue additive primaries, and can produce any chromaticity that is the triangle defined by those primary colors...
offset and gain from A2 to B2.
For each destination block, output the positions of the source blocks and the color offsets and gains.
Fractal transform decompression
Starting with an empty destination image A1, repeat the following algorithm several times:Downsample A1 down by a factor of 2 to produce image A2. Then copy blocks from A2 to A1 as directed by the compressed data, multiplying by the respective gains and adding the respective color offsets.
This algorithm is guaranteed to converge to an image, and it should appear similar to the original image.
In fact, a slight modification of the decompressor to run at block sizes larger than 4x4 pixels produces a method of stretching images without causing the blockiness or blurriness of traditional linear
Linear
In mathematics, a linear map or function f is a function which satisfies the following two properties:* Additivity : f = f + f...
resampling
Resampling
Resampling may refer to:* Resampling , several related audio processes* Resampling , resampling methods in statistics* Resampling , scaling of bitmap images* Sample rate conversion-See also:* Downsampling* Upsampling...
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s.
Patents
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...
and friends own numerous 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 in the United States and elsewhere on what this article describes. (These include U.S. Patents 4,941,193, 5,065,447, 5,384,867, 5,416,856, and 5,430,812.) These patents have hindered widespread adoption of the fractal transform in image coding.
If you live in United States
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
or other country with software patent
Software patent
Software patent does not have a universally accepted definition. One definition suggested by the Foundation for a Free Information Infrastructure is that a software patent is a "patent on any performance of a computer realised by means of a computer program".In 2005, the European Patent Office...
s, you can do fractal compression for research purposes (patent law allows this) but for anything more than that, you would need to get permission from the patent owners. That usually means paying them a license fee to use the technology.