Fractal transform

related topics
{system, computer, user}
{math, number, function}
{law, state, case}
{work, book, publish}
{car, race, vehicle}

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.

Contents

Fractal transform compression

Start with a digital image 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.

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 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.) These patents have hindered widespread adoption of the fractal transform in image coding.

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 would need to get permission from the patent owners. That usually means paying them a license fee to use the technology.

See also

External links

Full article ▸

related documents
Inter-process communication
Session Description Protocol
Interior Gateway Routing Protocol
Fsck
Intel 8008
Presentation Layer
Handshaking
Microphone array
Information technology
Freescale DragonBall
Wikipedia:Federal Standard 1037C terms/computer hardware terms
Risc PC
Vertical interval timecode
Low-power communication device
Round-trip delay time
Delay encoding
Intel 80186
Java Data Objects
Back Orifice 2000
Transatlantic telephone cable
Star coupler
EDVAC
Reduced-carrier transmission
Electronic Delay Storage Automatic Calculator
GEGL
IBM System p
Undernet
16-bit
XPilot
BOS/360