The fractal transform is a technique invented by
Michael Barnsley
Michael Fielding Barnsley (born 1946) 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 Wi ...
''et al.'' to perform
lossy
In information technology, lossy compression or irreversible compression is the class of data compression methods that uses inexact approximations and partial data discarding to represent the content. These techniques are used to reduce data size ...
image compression
Image compression is a type of data compression applied to digital images, to reduce their cost for storage or transmission. Algorithms may take advantage of visual perception and the statistical properties of image data to provide superior r ...
.
This first practical
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. Fractal a ...
system for digital images resembles a
vector quantization
Vector quantization (VQ) is a classical quantization technique from signal processing that allows the modeling of probability density functions by the distribution of prototype vectors. It was originally used for data compression. It works by di ...
system using the image itself as the codebook.
Fractal transform compression
Start with a digital
image
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
A
1.
Downsample it by a factor of 2 to produce image A
2.
Now, for each block B
1 of 4x4 pixels in A
1, find the corresponding block B
2 in A
2 most similar to B
1, and then find the
grayscale
In digital photography, computer-generated imagery, and colorimetry, a grayscale image is one in which the value of each pixel is a single sample representing only an ''amount'' of light; that is, it carries only intensity information. Graysca ...
or
RGB
The RGB color model is an additive color model in which the red, green and blue primary colors of light are added together in various ways to reproduce a broad array of colors. The name of the model comes from the initials of the three addi ...
offset and gain from A
2 to B
2.
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 A
1, repeat the following algorithm several times:
Downsample A
1 down by a factor of 2 to produce image A
2. Then copy blocks from A
2 to A
1 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
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
resampling algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s.
Patents
The basic patents covering Fractal Image Compression, U.S. Patents 4,941,193, 5,065,447, 5,384,867, 5,416,856, and 5,430,812 appear to be expired.
See also
*
Image compression
Image compression is a type of data compression applied to digital images, to reduce their cost for storage or transmission. Algorithms may take advantage of visual perception and the statistical properties of image data to provide superior r ...
External links
E2 writeup
Fractals
{{fractal-stub