## Image Compression

I've implemented a number of image compression algorithms in the past few years. Discreet Cosine Transform based, wavelet based, vector quantization, fractal based, various lossless algorithms, the works. I've always been more interested in trying out off-beat methods like fractal compression rather than trying to squeeze and extra 0.1bpp out of existing DCT and wavelet methods, which seems to be what most of the research in image compression is about these days.

Below is a simple, completely non-scientific comparison of a couple image compression algorithms I've implemented. Namely vector quantization and fractal compression. I don't think that the word fractal is really correct when describing fractal compression, but the name stuck.

Vector quantization builds a codebook of "representative" vectors from an image and then rebuilds the image out of them. It takes surprisingly few vectors to reconstruct an image with a high degree of accuracy. On average, a pretty good reconstruction can be achieved with a only few thousand. This is where the compression comes from.

Fractal compression is actually quite closely related to vector quantization. The big difference is that the codebook in fractal compression is generated from scaled down, possibly rotated and flipped sections of the image itself, rather than being constructed out of representative vectors prepared beforehand. Whereas vector quantization exploits coherence in some higher dimensional representation of the image, fractal compression exploits coherence across different scales, rotations, and brightness.

##### Uncompressed reference image:

The uncompressed image.

##### Vector Quantization:

Vector quantized at ~2 bits per pixel. I should note that the vector quantization code I wrote was originally designed for colour images, so it's definitely not working as efficiently as possible here. Compression took ~15 seconds on an Athlon64 3800+.

##### Fractal Compression:

Fractal compression at ~1 bit per pixel. Quality's about the same as vector quantization at half the bit rate. An interesting artifact is the very slight change in luminance from the others. This is due to the luminance scaling coefficients being quantized. Compression took **TEN MINUTES**.

##### Good ol' Jpeg:

Jpeg at ~1 bit per pixel. It does so much better than VQ and Fractal compression that it's almost funny. Compression took a few hundredths of a second.

##### Conclusion:

My conclusion? Stick with Jpeg, unless you really like bad image quality and long waits.