Image Compression

Firstly, I cannot even go into this without referring you to the excellent Hypertext Compression FAQ. This document lists many many compression schemes and a wealth of information about conversion tools such as PBMPLUS.

This document will discuss a few image compression schemes that I have experimented with.

Video hardware

Video hardware comes in many resolutions and capabilities. Some have acceleration hardware to handle moving pictures or perhaps 3-dimensional images. Dedicated video games frequently have hardware support for something called "Sprites" which are pieces of the image that can be moved across a background very quickly.

Typical PCs have progressed from black and white text, black and white graphics, 4 color graphics, 16 color graphics, 256 colors from a pallette of 16 million, and finally there are some that can now actually do as many of the 16 million colors as you desire. There are other organizations as well with some of them not so straight-forward.

Today's computers are predominantly 256 colors from a pallete of 16 million and about 1024 by 768 pixels (this would be called Super VGA or SVGA). But, for the remainder of this discussion, it is important to note that the 24-bit adapter (16 million color) is becoming more common and resolution of 1280 by 1024 are becoming quite popular.

Within this file, any time I'm trying to show an uncompressed image I am going to use JPEG so the transfer time will be fast and the distortion will be low. I will use this sample image.

Basic Concepts

What should be called "uncompressed images" are actually 24-bit images consisting of an 8-bit red, 8-bit green, and 8-bit blue channel.

Some compression programs operate on the actual 24-bit image which can have some 16 million colors in it, others cannot. Some compression programs yield an identical file after compressing and decompressing it and others do not. Some have strengths when using natural images such as photographs and others are better suited for crude graphics. Almost any compression program will have one sort of image that it performs outstanding on and others that it will not do very well. The lena image that I'm using here is very popular as a test image for real-life pictures. Admittedly, GIF won't do very well on it.

The breaking point for modern compression algorithms (at least on this image) seems to be at about 35 times compression. They all show distortions but in different ways.

GIF

In particular, it should be pointed out that the popular GIF format yields identical data after any number of compression/decompression cycles but that the input data must first be restricted to only 256 colors. Therein lies the fault of the GIF format in that before you even start you've degraded the image from freely using 16 million colors down to only 256. In fact, GIF is really best suited to the few-color blocky images now referred to as "graphics". GIF usually results in compression factors of about 2 to about 10.

I used the GIF format to dramatically reduce the filesize of my homepage picture.

Here is lena as a 35x GIF compressed image.

JPEG

JPEG is a recently developed image compression format which loses information each time it is compressed (called lossy) but operates on the 24-bit image directly. It operates the best on full color photographs and sacrifices details that have been deemed unimportant. It yields compressions factors of about 10 to 100 although obtaining 100 times compression is usually accomplished by asking the compressor to reduce the quality of the image.

Here is lena as a 35x JPEG compressed image.

Sometimes JPEG is given a bad name either by the fact that it is a lossy compression and sometimes because it is being viewed on an 8-bit adapter. When using an 8-bit adapter, not only is it hard to appreciate the 24-bit nature of JPEG, but the perception of the quality of the results is greatly affected by the method used to map the resulting 24-bit image to the 8-bit display.

For instance, xv Version 3, currently installed for Palo Alto and pointed to by Austin, does a pretty bad job of displaying JPEGs on an 8-bit adapter by default (because it uses a quick but crude dithering when running in 24-bit mode) but has outstanding results by adding the following lines to your .Xdefaults: 

xv.force8:                      true
xv.ownCmap:                     true

Fractal

Another method of compression, which was perhaps blown out of proportion when it was first investigated, is "fractal compression". Ultimately, fractal compression would be done by developing formulas which describe the picture in seemingly infinite detail and storing them. This is a long and painful process that is not truly feasible. However a simplification of this method which takes small pieces of the image and looks for mathematical representations of it's details is worth looking at. The default encoder that I have gave a compression factor of about 35 but for decent image quality I have been able to achieve compression of about 5 to 20.

Here is lena as a 35x fractal compressed image.

Perhaps more importantly, once you compress an image with this method, the decompression can be done at a larger resolution where the mathematical representation of the image is used to do much better than any sort of interpolation could do. Hard edges remain hard. Curves remain curves. The stair-case effect that becomes evident when zooming a normal image or the blurriness of trying to fix it are not necessary.

Since my fractal compressor doesn't handle full color I based it on a gray version of the sample image. Here is (a JPEG of) a 4x piece of the gray image. Note the stair-case effect. To get rid of this effect, you would usually use a smoothed version of this. However, after being compressed with the fractal method, the image can be decompressed with 4x magnification. It could be argued that the zoom of the 60K compressed image is better than the zoom of the original 260K image.

Wavelet

Epic is one of several wavelet encoders. It is intended as a research tool. It's documentation claims to have compromised image quality and compression a bit for speed. It is definitely fast and very respectable.

Here is lena as a 35x wavelet compressed image.

Paul Chamberlain