Fractal transform

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.

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 algorithm 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 it should be 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.

Patents

Michael Barnsley and friends own numerous patents 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.)

If you live in United States or other country with software patents, you can do fractal compression for research purposes (patent law allows this) but for anything more than that, you should do one of:

Go to some counry that has saner law
Get permision from patent owners. That usually means paying them money
Consult your lawyer
Lobby for changing this law