An Investigation of Image Size Reduction Algorithms

Full-size images require large amounts of disk space to store and bandwidth or time to transmit and display. In many applications, a smaller version of an image is sufficient. For example, a catalog of images could include many "thumbnail" images, each of which could be transmitted and displayed quickly. These thumbnails would give the user a good enough idea of the full image that they could choose the appropriate full-sized image to retrieve.

There are many ways in which a large image can be reduced in size.

The simplest way in which to reduce an image's size is by cropping, i.e. choosing only a certain portion of the image to view. This works well if one region of an image contains all of the interesting information. Even then, it requires a determination of what part of the image is important. This may be an easy task for a human, but is very difficult for a computer.
Pixel Skipping
To eliminate the above problem, we can reduce the size of an image by throwing out pixels evenly throughout an image. For example, if we wanted to reduce the size of an image by half in each dimension, we could throw out every other pixel. This method is fairly fast, but may produce artifacts, especially in color images. If an image is dithered, for example, it may have a regular pattern of two or more colors adjacent to each other in order to produce the illusion of a different color (which wasn't available in the color palette.) If we happen to throw out all of one of those colors, the perceived color, and thus the overall look, of the image will change drastically.
Pixel Averaging
In order to eliminate the problem of color artifacts as described above, we can average adjacent pixels together instead of simply throwing them out as in Pixel Skipping. However, this will take more time and may tend to blur the image.
Frequency Domain Processing
A different approach to image size reduction involves looking at an image in the frequency domain in the hopes that the useful information will be more easily selected. For example, if an image was composed entirely of low frequency components, the high frequency components would all be very small in the frequency domain and we could truncate them. When the image was transformed back to the spatial domain, it would be reduced in size by the same factor as in the frequency domain. Note that for this example, the net effect would be the same as Pixel Averaging. The advantage of Frequency Domain Sampling is that it could also reduce the size of images with only high-frequency content. In addition, if the frequency domain image was sampled as in Pixel Skipping, then the image in the spatial domain would also be reduced in size. The exact effects of this on the image are not obvious.
Wavelet Decomposition
The 2-D Discrete Wavelet Transform (DWT) offers another possible approach to image size reduction. The DWT is a decimating transform which produces a segmented image with different segments containing coefficients corresponding to different levels of detail in the image. Each level of the DWT produces four segments, one of which is a "smoothed" version of the image. The next level of the DWT operates on that smoothed version. Thus successive levels of the DWT produce a smaller and smaller (by a factor of 2 in each dimension) version of the original image.
Note: A color image can be thought of as three grey-scale images (Red, Green, and Blue). Any of the above algorithms must be applied to each of these images separately, after which the images can be re-combined to form the complete image.

In order to investigate the above algorithms, I used several platforms. For Cropping, Pixel Skipping, and Pixel Averaging, I used XV, an image display and manipulation package. XV includes hooks for programmers to add their own code. This allowed me to write the appropriate routines without having to worry about writing code to load and display images. XV already implemented Cropping, and I added Pixel Skipping and Pixel Averaging.

For the DWT, I used S-Plus with the Wavelets toolkit. I had to split the color images up into their R, G, and B components in order to run the DWT on them. I added a routine to XV to save images to separate files which S-Plus could read (1 file for each of the three color components R, G, and B). I also added a routine to load images which had been saved by S-Plus.

Note: All of the images shown below must be displayed by the software you are using to view this document. Due to the large number of colors needed by these images, unless you are using a true 24-bit color display (TrueColor or DirectColor), the images will be dithered, so direct comparisons will be difficult. To overcome this, each image is also a link to its file. If your viewing software is set up to send GIF images to an external viewer (such as XV), selecting each image will send it to a separate window. By setting each separate window to use its own colormap, each image will be displayed correctly. You will only be able to view one image at a time, because the colors of the other images will be stolen by the image being viewed. However, by switching from one image to the next you can compare them as best is possible.

I used three images to compare the effects of Pixel Skipping, Pixel Averaging, and the 2-D decimating DWT.


Somehow this part of my report got sent to the great bit-bucket in the sky. I'll rewrite it as soon as I get time...