Editing Fractal transform

{{Short description|Image compression technique}}
{{Unreferenced|date=September 2010}}
The '''fractal transform''' is a technique invented by [[Michael Barnsley]] ''et al.'' to perform [[lossy data compression|lossy]] [[image compression]].
This first practical [[fractal compression]] system for digital images resembles a [[vector quantization]] system using the image itself as the codebook.

== Fractal transform compression ==

Start with a digital [[image]] A<sub>1</sub>.
Downsample it by a factor of 2 to produce image A<sub>2</sub>.
Now, for each block B<sub>1</sub> of 4x4 pixels in A<sub>1</sub>, find the corresponding block B<sub>2</sub> in A<sub>2</sub> most similar to B<sub>1</sub>, and then find the [[grayscale]] or [[RGB color space|RGB]] offset and gain from A<sub>2</sub> to B<sub>2</sub>.
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<sub>1</sub>, repeat the following algorithm several times:
Downsample A<sub>1</sub> down by a factor of 2 to produce image A<sub>2</sub>. Then copy blocks from A<sub>2</sub> to A<sub>1</sub> 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 (bitmap)|resampling]] [[algorithm]]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]]

==External links==
*[http://everything2.com/?node_id=1264200 E2 writeup]

{{DEFAULTSORT:Fractal Transform}}
[[Category:Fractals]]


{{fractal-stub}}