The fractal transform is a technique invented by Michael Barnsley et al. to perform lossy image compression. This first practical fractal image compression system resembles a vector quantization system using the image itself as the codebook.
Fractal transform compression
First, start with a digital
image A. Then downsample it by a factor of 2 to produce image A2. Now, for each block B of 4x4 pixels in A, find the corresponding block B2 in A2 most similar to B, and then find the
grayscale or
RGB offset from A2 to B2. For each destination block, output the positions of the source blocks and the color offsets.
Fractal transform decompression
Starting with an empty destination image A, repeat the following several times:
Downsample A down by a factor of 2 to produce image A2. Then copy blocks from A2 to A as directed by the compressed data and add the proper color offsets.
This algorithm is guaranteed to converge to an image, and provided the compressor was well-designed, it should look 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 algorithms.
Don't try this at home.
Michael Barnsley and friends own numerous
patents in the United States and elsewhere on this system, which include U.S. Patents 4,941,193, 5,065,447, 5,384,867, 5,416,856, and 5,430,812. Implementing fractal transform compression in a product offered for sale will be illegal in the United States until at least the year 2010 because Barnsley is not willing to license the patents royalty-free.
See also image compression; image processing. If you try it on porn, you might get this.
Copyright © 2002
Damian Yerrick.
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with no Invariant, Front-Cover Texts, or Back-Cover Texts. A copy of the license is included in the writeup entitled "
GNU Free Documentation License".