Wavelets: The New

Wave of Image

Compression?

Abstract

Wavelet-based compression is today one of the most widely researched areas of image analysis. A large amount of research has already been done to show that wavelet- based image compression is the method of choice for lossy image compression. The purpose of this project is to determine if wavelets can be effectively used for lossless compression as well, by comparing compressibility of wavelet-transformed files with compressibility of interlaced files.

Programs were written to compare wavelet-based compression with normal interlaced compression, such as is used in the GIF format, which is popular on the Internet today. The programs did not perform any actual compression themselves, so it was necessary to use external compression programs. PKZIP and a Huffman compressor were used for this purpose.

A total of 103 images were tested under wavelet-based and normal interlaced compression schemes, using PKZIP and Huffman for each. Thus, four file sizes were recorded for each image. The images were organized into four sets: hand-drawn images, hand-drawn images that had been reduced in size, low-contrast images, and low-contrast images that had been reduced in size. T-tests were run to ensure that the data did in fact represent different populations.

Contrary to what was hypothesized, the wavelet-based compression scheme did not work very well at all. When combined with the compression algorithm found in PKZIP, normal interlaced compression consistently did better than wavelet-based compression (with a few exceptions). However, even when using Huffman compression, wavelet-based compression only did well with hand-drawn images, and then not by a very wide margin. Thus, a lossless wavelet-based compression scheme is not very practical, except in very rare cases in which the user is limited to Huffman compression of hand-drawn images.

Table of Contents

Abstract	1

Table of Contents	2

Introduction	4

Background Information	5

How Lossy Compression Works	5

What is Wavelet Analysis?	5

How is the Haar construction used in image processing?	7

What about normal interlaced compression?	8

How the Programs Actually Work	8

How Errors Were Dealt With	9

PKZIP vs. Huffman Compression	11

Hypothesis	11

Materials	13

Procedures	13

Data	15

Means of all Data	15

Standard Deviations of all Data	16

T-Tests for Wavelet vs. Normal Compression	17

Graphs	18

Conclusion	20

Acknowledgements	22

Bibliography	22

Appendix A -- Compressed File Sizes	24

Appendix B -- Source code for the HAR format loader	34

Appendix C -- A Huffman Compressor	36

Appendix D -- A Catalog of all images used	43

Introduction

Wavelet-based compression is today one of the most widely researched areas of image analysis. Much research has already been done to show that wavelets are superior to discrete cosine transform-based (DCT) compression, used in JFIF/JPEG files. However, this research employs wavelet-based compression as a lossy compression method, meaning that the decompressed version is not the same as the original. Little research has been done to determine if wavelets can be used in lossless compression applications.

Wavelets are used for many reasons. Wavelets allow signals to be decomposed into various parts, some of which can simply be thrown away. This is called quantization, and with DCT can often result in "blockiness" in an image. With wavelet-based compression, such blockiness is minimized, thus allowing more of the image to be thrown away without suffering consequences in terms of image quality.

However, wavelets have another key characteristic important to lossless compression, that is, they have the ability to store an image at many resolutions, while minimizing overhead. Using wavelets, a smaller (lower resolution) version of the original image can be transmitted first, providing a rough sketch of what the image looks like. Next, instead of transmitting the entire version of a more detailed image, only the information necessary to derive a higher resolution image from the low resolution image is translated. As more of the image is transmitted, the decoded image increases in quality. This kind of transmission is known as progressive transmission.

There are a number of lossless methods for progressively transmitting images already existing today. One of the more common methods is used in the GIF format, a graphic file format common on the Internet. While to the user this kind of progressive transmission may seem to be very similar to wavelet-based compression, it is actually a completely different method. The purpose of this research is to determine if wavelets can be effectively used as an alternative to GIF interlacing, without losing information contained in the original image.

Background Information

History of Wavelets

In 1807, a man by the name of Joseph Fourier discovered that any 2 -periodic function f(x) is the sum

of its "Fourier series." The coefficients a0, ak, and bk are calculated by using definite integrals. Basically, Fourier took a polynomial a0 + a1x + a2x2 + ... and passed it to a different representation, of the form a0 + (a1 cos x + b1 sin x) + (a2 cos 2x + b2 sin 2x) + ... (Meyer 14).

Fourier analysis is good for describing signals in a very concise manner. Sine waves, used in Fourier analysis, have the characteristic of repeating periodically forever. It is this property of sine waves that allows Fourier analysis to represent long, regular signals very well. However, Fourier analysis does not deal very well with signals that last a short amount of time (Von Baeyer 71).

In 1909, a man by the name of Haar discovered an alternative. He began with a function h(x) which was equal to 1 on [0,1/2), -1 on [1/2,1) and 0 outside the interval [0,1). Shown in Figure 1, this was the basis function for various "atoms" hn(x) which were used to construct f(x) (Meyer 15-16).

Transforming Images with the Haar system

A 1-D signal can easily be transformed using the Haar system. The Haar "step function" can be amplified and shifted vertically to form the function shown in Figure 2. The values which represent the transformations (the amount the function is amplified/shifted) are actually equal to be the averages and differences of the two pixels. The average represents the amount to shift h(x) up, and the difference represents how much h(x) is to be amplified. For the pixels in Figure 2, h(x) would be shifted up 96 units, and amplified by -32 units (which is the difference divided by 2).

Images are often continuous functions, except near "edges," or areas of sharp contrast. Thus, in order to be able to use the Haar construction with images, it is first necessary to pass the image through a low-pass filter (Meyer 46- 47). Next, the image is also passed through a high-pass filter. The results of the two filters can actually be calculated in a single pass, as was done in Figure 3b. The results of the low-pass filter are in fact a scaled-down version of the picture, so they can be sent through the process again, as shown in Figure 3c (Gilbert).

In images, there is usually a lot more low frequency (i.e. slowly changing) information than high frequency information. Because of this, most of the values resulting from the high-pass filter are close to 0. The more of these values that are close to 0, the more efficiently the image can be compressed (Gilbert).

Generally, the difficult part of wavelet-based compression is defining the low-pass and high-pass filters. The filters should be orthogonal, meaning the output of each filter represents a different part of the signal, and they should have narrow support, meaning that they only affect a small area around the current pixel being analyzed (Meyer 59 and Gilbert). The Haar system is the only orthogonal system that meets these criteria. The complaint about the Haar system is that it produces harsh "edge effects" after the image has been quantized (Meyer 59). The generally accepted solution to this problem is a type of wavelet called a bi-orthogonal wavelet, but the Haar system should work well when the data is not quantized.

Comparison of Wavelets and Interlacing

The type of progressive transmission used today is known as interlacing and is used in the GIF format. Transforming the image this way produces four scaled- down images. The first image is derived from the first set of every fourth line, the second image from the second set of every fourth line, and so on. This results in an image similar to the one shown in Figure 4.

PKZIP vs. Huffman Compression

After transforming the image, the next step is to compress the transformed image. This can be done using a number of compression methods. In the research done in this paper, two methods were used for compression: deflate (the method used commonly in PKWare's PKZIP program) and Huffman compression (an old algorithm that is easy to implement). The reason for using two algorithms in testing was to show that wavelet- based compression does not work well with all compression algorithms. In general, PKZIP is considered to be the better of the two algorithms.

Huffman coding is known as a frequency coder. Proposed sometime in the early 1950's, it is based on the idea that some characters are used more than others in a file. Codes are generated for each character. Similar to Morse code, characters that are used often are represented by shorter codes than those characters that are used less frequently (Stix 54 and Apiki 310).

PKZIP, on the other hand, relies on a much more complicated algorithm. This algorithm examines characters which are adjacent in a file rather than single characters, therefore achieving higher compression. The file is finally compressed using Shannon- Fano coding, a relative of Huffman (put reference here).

Hypothesis

The result of the high-pass filter used in the Haar transform should result in bytes which are close to 0. The more bytes there are in the resulting file that are the same, the higher the compression ratio that should be obtained. When low-contrast continuous-tone images (such as digitized photographs) are looked at as a signal, they tend to change slowly over time, and so there should be many bytes in the resulting file which are close to 0. Thus, a lossless wavelet-based compression scheme should compress low-contrast images more effectively than a scheme that uses normal interlaced compression, and should also be able to somewhat more effectively compress hand-drawn images.

Materials

- Computer (486 DX2/66 running MS-DOS 6.22 was used).

- C Compiler (Turbo C++ 3.0 was used).

- Various images, all in TGA format (all of the images used in this project were downloaded from ftp://pictures@nic.funet.fi/pub/pics/misc/, and were converted to TGA format and rescaled to 320x200 resolution, if necessary).

- External compression program (PKZIP 2.04g was used, as was the Huffman compressor located in Appendix C).

Procedures

The wavelet-based technique employed here uses a high-pass and a low-pass filter. The high-pass (difference) filter is defined as:

D = a - b

where a and b are the two values to transform, and D is the difference between a and b. The low-pass (average) filter is defined as:

A = (a + b) / 2

where a and b are again the two values to transform, and A is the average between a and b. By taking values of every set of two pixels in the image and transforming them into their average and difference, the entire image can be transformed. The transform is only applied vertically, as a 1-D transform. After iterating this four times, the entire transform is completed.

However, three types of errors can occur in the image with this method, keeping the algorithm from being successfully reversed. On a computer, when the average of two values is calculated using integer arithmetic, some precision errors may occur. This is due to the decimal portion of the number being truncated. In fact, precision errors will always occur if the sum or difference of the two numbers is odd. This is a very simple problem to deal with. When the Haar transform is applied to an image, two numbers, the average and difference of the original two numbers, are stored for every pair of numbers in an image. The precision errors occur in the average. The difference can be used to determine if a precision error occurred; if this value is odd an error did in fact occur.

Another type of error also occurs, due in part to the way in which rounding errors are dealt with. The range of numbers is between -128 and 127, for a given value in the images used in this project. If the sum of the two numbers is odd, then a precision error will occur, as already discussed. However, if the sum of the two numbers is also negative, then it is important to realize how the numbers will be truncated. With computers, numbers are always truncated by simply chopping off the decimal portion of the number. In effect, all numbers are rounded toward zero using this method. This means that negative numbers are always rounded up, instead of down, like positive numbers. In order to use the fix described previously for dealing with precision errors, a statement must be added to the program to allow negative numbers to be rounded down instead of up. In effect a "floor" function (greatest integer less than or equal to) is being implemented instead of trunctation.

Finally, if the difference between two numbers is larger than the set limits of the averaging function, then the average of the two numbers will be off in the eighth bit. This was an extremely tough problem to diagnose. However, once the problem was recognized, the fix was easy. If the difference between the two numbers is less than -128 or greater than 127, then the eighth bit of the average must be set.

The completed pseudocode algorithm is in Listing 1. Two programs were derived fom this method, and are located in Appendix A. TGA2HAR.C performs a wavelet transform on the images, and TGA2INT.C, was written to store an image in interlaced format, similar to the method used in the GIF format, without the LZW compression. In Appendix B, LOADHAR.C can be found, which was written in order to test the TGA2HAR.C program, and to make sure that the lossless wavelet transform algorithm worked properly.

None of the programs written employ any sort of compression internally. Thus, an external compression program must be used in order to test the effectiveness of the algorithms. In this project, two compression programs were used -- PKZIP version 2.04g, and a Huffman compressor, the source for which is located in Appendix C.

A total of 103 images were tested. All the images were 256-color images, at a resolution of 320x200, because the programs were designed to only for images of that size and color depth, because of simplicity reasons (though the programs could be easily modified to handle other sizes and color depths). Each of the images were converted to HAR and INT format using the programs located in Appendix A. These two resulting files were compressed using both PKZIP and the Huffman compressor. The sizes of the four files from this step were recorded, and statistical analyses were run to compare the data.

Data

Sizes of the compressed images have been compiled into the following tables. The images were organized into four sets: hand-drawn images, hand-drawn images that had been reduced in size, low-contrast images, and low-contrast images that had been reduced in size. Hand-drawn images tend to have many areas of high contrast, and consist of few colors. Images that have been reduced in size tend to have antialiasing (the use of colors to create the appearance of increased resolution) and dithering (the addition of noise to an image in order to create the appearance of more colors). This tends to get in the way of the compression program. Data for individual files can be found in Appendix D, and reduced versions of all of the pictures can be found in Appendix E.

Means of all Data
Wavelet-based Comression	Normal Interlaced Compression
Image Type	Huffman	PKZIP	Huffman	PKZIP
Hand-drawn

16590	6502	18867	4776
Reduced Size Hand-drawn	34482	25719	29700	18373
Low-contrast

34799	29334	34440	21746
Reduced Size Low-contrast	40502	33927	36008	33107

Standard Deviations of all Data
Wavelet-based Comression	Normal Interlaced Compression
Image Type	Huffman	PKZIP	Huffman	PKZIP
Hand-drawn

5581	6031	7225	4334
Reduced Size Hand-drawn	12037	12279	12244	9604
Low-contrast

11599	12505	12003	11494
Reduced Size Low-contrast	13245	14289	12624	49239

T-Tests for Wavelet vs. Normal Compression
Image Type	Huffman	PKZIP
Hand-drawn

0.032721	0.001206
Reduced Size Hand-drawn	2.7 x 10-7	8.7 x 10-11
Low-contrast

0.718396	2.5 x 10-5
Reduced Size Low-contrast	1.5 x 10-5	0.909721

The type of T-test used was a two-tailed paired test. Values shown are the probabilities associated with the Student's T-Test. The groups that were compared were the wavelet compression and normal compression, under both Huffman and PKZIP compresion schemes. Based on the information shown in the table, all of the compared groups were different (i.e. represent different populations) except for the low-contrast images compressed with Huffman compression, and the reduced size low-contrast images compressed with PKZIP.

Graphs

Conclusion

Contrary to what was hypothesized, the wavelet-based compression scheme did not work very well at all. When combined with the compression algorithm found in PKZIP, normal interlaced compression consistently did better than wavelet-based compression (with a few exceptions). However, even when using Huffman compression, wavelet-based compression only did well with hand-drawn images, and then not by a very wide margin. In conclusion, a lossless wavelet-based compression scheme is not very practical, except in very rare cases in which the user is limited to huffman compression of hand-drawn images.

There are many reasons why this may have occurred. The wavelet-based compression scheme moved correlated data points further apart, making it harder for PKZIP to compress the data. In addition, the methods used to deal with errors added noise in images where the errors occurred. Such errors did not occur in hand-drawn images.

There are ways in which the wavelet-compression scheme could be improved. If the last iteration of the wavelet-based compression scheme had been delta coded, then the wavelet-based compression scheme may have done even better under Huffman, because delta coding redistributes the frequencies in some images so that they can be better compressed. Another way would be to use adaptive Huffman coding, in which the length of a repeated byte can change throughout the file, and so part of the file could have one most repeated character, and another part of the file could have another most repeated character.

Acknowledgements

The Huffman compression program located in Appendix D was written by William Demas.

PKZIP is copyrighted 1989-1992 by PKWARE, Inc., and is protected by U.S. Patent no. 5,051,745.

The code used to read the TGA files is based on the code in Steve Rimmer's book Supercharged Bitmapped Graphics.

Works Cited

Apiki, Steve. "Lossless Data Compression." Byte Mar. 1991: 309-387.

This article discusses two common methods of data compression, Huffman and LZW, as well as common variations of these methods. Both of these methods are lossless, meaning that the decompressed version of the file is the same as the original. Sample source code is also provided.

Gilbert, David Alan. "Re: Math Retard Needs Help." Usenet newsgroup comp.compression.research 5 Jun 1995.

This is an extremely well written explanation of compression algorithms using wavelets. The algorithms described in this document are the algorithms upon which the programs in this project were based.

Jakulin, Alex. "PROPOSAL for lossless image compression." Usenet newsgroup comp.compression 13 Jan 1995.

Using the delta transform on an image prior to compressing it with the deflate algorithm can decrease the quality of compression. A new method is presented which integrates RLE with the deflate algorithm, by introducing a new symbol that indicates an RLE code follows. Also recommended is sorting the palette by intensities and then delta-coding it; the palette would then be more compressible, as would an image which is delta-coded.

Meyer, Yves. Wavelets: Algorithms and Applications. Translated and revised by Robert D. Ryan. Philadelphia: Society for Industrial and Applied Mathematics, 1993.

This book is an extensive collection of chapters on various topics relating to wavelets, including background on wavelets, audio and video compression applications, and visual systems of robots. The book is easy for a novice to comprehend, provided he/she has some sort of a background in basic calculus.

Rimmer, Steve. Supercharged Bitmapped Graphics. USA: Windcrest Books, 1992.

This book explains the details of a number of graphics file formats that are commonly used. The GIF format (which uses interlacing, a method of progressive transmission) and the TGA format (a format that is easy to implement, and was used in this project) were both discussed in detail.

Stix, Gary. "Encoding the 'Neatness' of Ones and Zeroes." Scientific American Sept. 1991: 54-58.

In 1951, David Huffman developed, for a term paper, a compression methods that was the most efficient method at the time. His professor, Fano, and Claude F. Shannon had struggled with the problem for many years before Huffman's discovery. This article discusses basic coding trees, used in Huffman compression, though the main purpose of the article is to provide a brief biography of David Huffman.

Von Baeyer, Hans Christian. "Wave of the future," Discover May 1995: 69-74.

This source describes the history of Daubechies's wavelets. In addition, and explanation of wavelets that is easy to understand is also included. This source is almost a necessity in order to understand the other sources, which require high levels of mathematics in order to comprehend.

Appendix A -- Wavelet and Interlaced Format Conversion Programs

/* TGA to HAR conversion program */

#include <stdio.h>

#include <stdlib.h>

#include <dos.h>

#include <conio.h>

#define LINE_SIZE 320

#define TOT_LINES 200

#define VGA_MEM 0xa0000000

#define BIOSVID 0x10

#define VGA256 0x13

#define TEXT 0x3

#define SETMODE 0

/* avg takes the average of two values a and b */

#define avg(a,b) ((a + b) / 2)

/* diff takes the difference of two values a and b, modulo 256 */

#define diff(a,b) (a - b)

/* Declare a variable type that holds the image information */

typedef struct {

char identsize;

char colormaptype;

char imagetype;

unsigned int colormapstart;

unsigned int colormaplength;

char colormapbits;

unsigned int xstart;

unsigned int ystart;

unsigned int width, depth;

char bits;

char descriptor;

} TGAHEAD;

/* Declare variable types for various buffers */

typedef char linebuffer[LINE_SIZE];

typedef unsigned char avgbuffer[LINE_SIZE];

typedef char palbuffer[768];

/* Function declarations */

void graphics (void);

void text (void);

void convert (FILE *fp, FILE *out);

void paletteset (char *buffer);

void putline(char *buffer, unsigned int n, int width);

void getline(char *buffer, unsigned int n, int width);

void error (char *message);

void main (int argc, char *argv[]) {

FILE *fp, *out;

/* Make sure two filenames were entered */

if(argc > 2) {

/* Open the files */

if((fp = fopen (argv[1], "rb")) != NULL) {

if((out = fopen (argv[2], "wb")) != NULL) {

graphics();

/* Convert the file to Haar format */

convert(fp, out);

/* Close the files */

fclose(fp);

fclose(out);

getch();

text();

puts("Done.\n");

} else printf("Error opening %s for output\n", argv[2]);

} else printf("Error opening %s for input\n", argv[1]);

} else puts("Must specify a filename for both input and output\n");

}

/* The graphics function puts the screen in graphics mode */

void graphics (void) {

union REGS regs;

regs.h.ah = SETMODE;

regs.h.al = VGA256;

int86(BIOSVID, &regs, &regs);

}

/* The text function returns the screen to text mode */

void text (void) {

union REGS regs;

regs.h.ah = SETMODE;

regs.h.al = TEXT;

int86(BIOSVID, &regs, &regs);

}

/* The decode function reads and displays the TGA file */

void convert (FILE *fp, FILE * out) {

TGAHEAD tga;

int bytes, i, n, startline, endline, incline;

char *ptr;

char temp;

linebuffer buf1, buf2, diffbuf;

avgbuffer avgbuf, avgbuf1, avgbuf2;

palbuffer buffer;

/* Read the header for the file */

if (fread((char *)&tga, 1, sizeof(TGAHEAD), fp)==sizeof(TGAHEAD)) {

if(tga.imagetype == 0x01 ||

tga.imagetype == 0x02 ||

tga.imagetype == 0x03 ||

tga.imagetype == 0x09 ||

tga.imagetype == 0x0a ||

tga.imagetype == 0x0b) {

/* Change the image type so that the Haar reader will

know that the file it is reading is a Haar file */

tga.imagetype = 128 + tga.imagetype;

/* Make sure the image in the output file is 0 bytes away */

tga.identsize = 0;

/* Write the header to the output file */

fwrite((char *)&tga, 1, sizeof(TGAHEAD), out);

/* Make sure the dimensions of the image are all right */

if(tga.width > LINE_SIZE) error("Can only handle images of dimension 320x200\n");

if(tga.depth > TOT_LINES) error("Can only handle images of dimension 320x200\n");

/* Read until the beginning of the image is reached */

fseek(fp, (long)tga.identsize, SEEK_CUR);

/* See if the file has an valid number of colors */

if(tga.colormaptype) {

switch(tga.colormapbits) {

case 24:

for(i = tga.colormapstart; i < tga.colormaplength; i++) {

if(i >= 256) break;

buffer[i * 3 + 2] = fputc(fgetc(fp), out);

buffer[i * 3 + 1] = fputc(fgetc(fp), out);

buffer[i * 3] = fputc(fgetc(fp), out);

}

break;

case 16:

for(i = tga.colormapstart; i < tga.colormaplength; i++) {

if(i >= 256) break;

n = ((fputc(fgetc(fp), fp) & 0xff) + ((fputc(fgetc(fp), fp) & 0xff) << 8));

buffer[i * 3 + 2] = ((n >> 10) & 0x1f) << 3;

buffer[i * 3 + 1] = ((n >> 5 ) & 0x1f) << 3;

buffer[i * 3] = (n & 0x1f) << 3;

}

break;

}

paletteset(buffer);

} else {

error("Image must have a palette\n");

}

/* Set up the options for what is to be converted */

startline = 0;

endline = tga.depth;

incline = 2;

/* Convert the image */

for(i = startline; i < endline; i += incline) {

fread(&buf1, 1, tga.width, fp);

fread(&buf2, 1, tga.width, fp);

for(n = 0; n < tga.width; n++) {

avgbuf1[n] = avg(buf1[n], buf2[n]);

diffbuf[n] = diff(buf1[n], buf2[n]);

if(((buf1[n] + buf2[n]) < 0) && (diffbuf[n] & 1))

avgbuf[n]--;

if((diff(buf1[n], buf2[n]) < -127) ||

(diff(buf1[n], buf2[n]) > 128))

avgbuf[n] = avgbuf[n] + 128;

}

putline(diffbuf, i / (incline * 2) + tga.depth / 2, tga.width);

i += incline;

fread(&buf1, 1, tga.width, fp);

fread(&buf2, 1, tga.width, fp);

for(n = 0; n < tga.width; n++) {

avgbuf2[n] = avg(buf1[n], buf2[n]);

diffbuf[n] = diff(buf1[n], buf2[n]);

if(((buf1[n] + buf2[n]) < 0) && (diffbuf[n] & 1))

avgbuf[n]--;

if((diff(buf1[n], buf2[n]) < -127) ||

(diff(buf1[n], buf2[n]) > 128))

avgbuf[n] = avgbuf[n] + 128;

}

putline(diffbuf, i / (incline * 2) + 3 * tga.depth / 4, tga.width);

for(n = 0; n < tga.width; n++) {

avgbuf[n] = avg(avgbuf1[n], avgbuf2[n]);

diffbuf[n] = diff(avgbuf1[n], avgbuf2[n]);

if(((avgbuf1[n] + avgbuf2[n]) < 0) && (diffbuf[n] & 1))

avgbuf[n]--;

if((diff(avgbuf1[n], avgbuf2[n]) < -127) ||

(diff(avgbuf1[n], avgbuf2[n]) > 128))

avgbuf[n] = avgbuf[n] + 128;

}

putline(avgbuf, (i - incline) / (incline * 2), tga.width);

putline(diffbuf, (i - incline) / (incline * 2) + tga.depth / 4, tga.width);

}

/* Finally, write the converted image to disk */

for(i = startline; i < endline; i++) {

getline(buf1, i, tga.width);

fwrite(&buf1, 1, tga.width, out);

}

}

}

}

/* The paletteset function sets the color palette */

void paletteset (char *buffer) {

union REGS regs;

int i;

outp(0x3c6, 0xff);

for(i = 0; i < 255; i++) {

outp(0x3c8, i);

outp(0x3c9, (*buffer++) >> 2);

outp(0x3c9, (*buffer++) >> 2);

outp(0x3c9, (*buffer++) >> 2);

}

}

/* The putline function displays one line of the image */

void putline(char *buffer, unsigned int n, int width) {

char far *ScreenMemory = (char far *)(VGA_MEM + n * LINE_SIZE);

int j;

for(j = 0; j < width; j++) *(ScreenMemory + j) = buffer[j];

}

/* The getline function reads a line of the image from screen memory */

void getline(char *buffer, unsigned int n, int width) {

char far *ScreenMemory = (char far *)(VGA_MEM + n * LINE_SIZE);

int j;

for(j = 0; j < width; j++) *(buffer + j) = *(ScreenMemory + j);

}

/* The error function displays an error message and halts the program */

void error (char *message) {

puts(message);

exit(1);

}

/* TGA to interlaced conversion program */

#include <stdio.h>

#include <stdlib.h>

#include <dos.h>

#include <conio.h>

#define LINE_SIZE 320

#define TOT_LINES 200

#define VGA_MEM 0xa0000000

#define BIOSVID 0x10

#define VGA256 0x13

#define TEXT 0x3

#define SETMODE 0

/* avg takes the average of two values a and b */

#define avg(a,b) ((a + b) / 2)

/* diff takes the difference of two values a and b, modulo 256 */

#define diff(a,b) (a - b)

/* Declare a variable type that holds the image information */

typedef struct {

char identsize;

char colormaptype;

char imagetype;

unsigned int colormapstart;

unsigned int colormaplength;

char colormapbits;

unsigned int xstart;

unsigned int ystart;

unsigned int width, depth;

char bits;

char descriptor;

} TGAHEAD;

/* Declare variable types for various buffers */

typedef char linebuffer[LINE_SIZE];

typedef unsigned char avgbuffer[LINE_SIZE];

typedef char palbuffer[768];

/* Function declarations */

void graphics (void);

void text (void);

void convert (FILE *fp, FILE *out);

void paletteset (char *buffer);

void putline(char *buffer, unsigned int n, int width);

void getline(char *buffer, unsigned int n, int width);

void error (char *message);

void main (int argc, char *argv[]) {

FILE *fp, *out;

/* Make sure two filenames were entered */

if(argc > 2) {

/* Open the files */

if((fp = fopen (argv[1], "rb")) != NULL) {

if((out = fopen (argv[2], "wb")) != NULL) {

graphics();

/* Convert the file to Haar format */

convert(fp, out);

/* Close the files */

fclose(fp);

fclose(out);

getch();

text();

puts("Done.\n");

} else printf("Error opening %s for output\n", argv[2]);

} else printf("Error opening %s for input\n", argv[1]);

} else puts("Must specify a filename for both input and output\n");

}

/* The graphics function puts the screen in graphics mode */

void graphics (void) {

union REGS regs;

regs.h.ah = SETMODE;

regs.h.al = VGA256;

int86(BIOSVID, &regs, &regs);

}

/* The text function returns the screen to text mode */

void text (void) {

union REGS regs;

regs.h.ah = SETMODE;

regs.h.al = TEXT;

int86(BIOSVID, &regs, &regs);

}

/* The decode function reads and displays the TGA file */

void convert (FILE *fp, FILE * out) {

TGAHEAD tga;

int bytes, i, n, startline, endline, incline;

char *ptr;

char temp;

linebuffer buf1, buf2, diffbuf;

avgbuffer avgbuf, avgbuf1, avgbuf2;

palbuffer buffer;

/* Read the header for the file */

if (fread((char *)&tga, 1, sizeof(TGAHEAD), fp)==sizeof(TGAHEAD)) {

if(tga.imagetype == 0x01 ||

tga.imagetype == 0x02 ||

tga.imagetype == 0x03 ||

tga.imagetype == 0x09 ||

tga.imagetype == 0x0a ||

tga.imagetype == 0x0b) {

/* Change the image type so that the reader will

know that the file it is reading is an interlaced file */

tga.imagetype = 129 + tga.imagetype;

/* Make sure the image in the output file is 0 bytes away */

tga.identsize = 0;

/* Write the header to the output file */

fwrite((char *)&tga, 1, sizeof(TGAHEAD), out);

/* Make sure the dimensions of the image are all right */

if(tga.width > LINE_SIZE) error("Can only handle images of dimension 320x200\n");

if(tga.depth > TOT_LINES) error("Can only handle images of dimension 320x200\n");

/* Read until the beginning of the image is reached */

fseek(fp, (long)tga.identsize, SEEK_CUR);

/* See if the file has an valid number of colors */

if(tga.colormaptype) {

switch(tga.colormapbits) {

case 24:

for(i = tga.colormapstart; i < tga.colormaplength; i++) {

if(i >= 256) break;

buffer[i * 3 + 2] = fputc(fgetc(fp), out);

buffer[i * 3 + 1] = fputc(fgetc(fp), out);

buffer[i * 3] = fputc(fgetc(fp), out);

}

break;

case 16:

for(i = tga.colormapstart; i < tga.colormaplength; i++) {

if(i >= 256) break;

n = ((fputc(fgetc(fp), fp) & 0xff) + ((fputc(fgetc(fp), fp) & 0xff) << 8));

buffer[i * 3 + 2] = ((n >> 10) & 0x1f) << 3;

buffer[i * 3 + 1] = ((n >> 5 ) & 0x1f) << 3;

buffer[i * 3] = (n & 0x1f) << 3;

}

break;

}

paletteset(buffer);

} else {

error("Image must have a palette\n");

}

/* Set up the options for what is to be converted */

startline = 0;

endline = tga.depth;

incline = 1;

/* Convert the image */

for(i = startline; i < endline; i += incline) {

fread(&buf1, 1, tga.width, fp);

putline(buf1, (i % 4) * tga.depth / 4 + (i / 4), tga.width);

}

/* Finally, write the converted image to disk */

for(i = startline; i < endline; i++) {

getline(buf1, i, tga.width);

fwrite(&buf1, 1, tga.width, out);

}

}

}

}

/* The paletteset function sets the color palette */

void paletteset (char *buffer) {

union REGS regs;

int i;

outp(0x3c6, 0xff);

for(i = 0; i < 255; i++) {

outp(0x3c8, i);

outp(0x3c9, (*buffer++) >> 2);

outp(0x3c9, (*buffer++) >> 2);

outp(0x3c9, (*buffer++) >> 2);

}

}

/* The putline function displays one line of the image */

void putline(char *buffer, unsigned int n, int width) {

char far *ScreenMemory = (char far *)(VGA_MEM + n * LINE_SIZE);

int j;

for(j = 0; j < width; j++) *(ScreenMemory + j) = buffer[j];

}

/* The getline function reads a line of the image from screen memory */

void getline(char *buffer, unsigned int n, int width) {

char far *ScreenMemory = (char far *)(VGA_MEM + n * LINE_SIZE);

int j;

for(j = 0; j < width; j++) *(buffer + j) = *(ScreenMemory + j);

}

/* The error function displays an error message and halts the program */

void error (char *message) {

puts(message);

exit(1);

}

Appendix B -- Source code for the HAR format loader

/* HAR format loader */

#include <stdio.h>

#include <stdlib.h>

#include <dos.h>

#include <conio.h>

#define LINE_SIZE 320

#define TOT_LINES 200

#define VGA_MEM 0xa0000000

#define BIOSVID 0x10

#define VGA256 0x13

#define TEXT 0x3

#define SETMODE 0

/* Declare a variable type that holds the image information */

typedef struct {

char identsize;

char colormaptype;

char imagetype;

unsigned int colormapstart;

unsigned int colormaplength;

char colormapbits;

unsigned int xstart;

unsigned int ystart;

unsigned int width, depth;

char bits;

char descriptor;

} TGAHEAD;

/* Function declarations */

void graphics (void);

void text (void);

void decode (FILE *fp);

void paletteset (char *buffer);

void putline(char *p, unsigned int n, int width);

void getline(char *p, unsigned int n, int width);

void error (char *message);

void main(int argc, char *argv[]) {

FILE *fp;

/* Make sure a filename was entered */

if(argc > 1) {

/* Open the file */

if((fp = fopen (argv[argc - 1], "rb")) != NULL) {

/* Go into graphics mode */

graphics();

/* Read and display the file */

decode(fp);

/* Close the file */

fclose(fp);

/* Wait for a keypress */

while(!kbhit());

/* Return to text mode */

text();

} else printf("Error opening %s\n", argv[argc - 1]);

} else puts("Must specify a filename\n");

}

/* The graphics function puts the screen in graphics mode */

void graphics (void) {

union REGS regs;

regs.h.ah = 0;

regs.h.al = 0x13;

int86(0x10, &regs, &regs);

}

/* The text function returns the screen to text mode */

void text (void) {

union REGS regs;

regs.h.ah = 0;

regs.h.al = 3;

int86(0x10, &regs, &regs);

}

/* The decode function reads and displays the TGA file */

void decode (FILE *fp) {

TGAHEAD tga;

char *ptr;

char buffer[768], buffer2[320], buffer3[320];

char temp;

int bytes, i, n, startline, endline, incline;

/* Read the header for the file */

if (fread((char *)&tga, 1, sizeof(TGAHEAD), fp)==sizeof(TGAHEAD)) {

/* Read until the beginning of the image is reached */

fseek(fp, (long)tga.identsize, SEEK_CUR);

/* See if the file has an invalid number of colors */

if(tga.colormaptype) {

switch(tga.colormapbits) {

case 24:

for(i = tga.colormapstart; i < tga.colormaplength; i++) {

if(i >= 256) break;

buffer[i*3+2] = fgetc(fp);

buffer[i*3+1] = fgetc(fp);

buffer[i*3] = fgetc(fp);

}

break;

case 16:

for(i = tga.colormapstart; i < tga.colormaplength; i++) {

if(i >= 256) break;

n = ((fgetc(fp) & 0xff) + ((fgetc(fp) & 0xff) << 8));

buffer[i*3+2] = ((n >> 10) & 0x1f) << 3;

buffer[i*3+1] = ((n >> 5 ) & 0x1f) << 3;

buffer[i*3] = (n & 0x1f) << 3;

}

break;

}

paletteset(buffer);

}

/* Set up which parts of the file are to be displayed */

startline = 0;

endline = tga.depth;

incline = 4;

/* Read the level 1 image and display it */

for(i = startline; i < endline; i += incline) {

fread(&buffer, 1, tga.width, fp);

putline(buffer, i, tga.width);

putline(buffer, i + 1, tga.width);

putline(buffer, i + 2, tga.width);

putline(buffer, i + 3, tga.width);

}

/* Read the level 2 image and display it */

for(i = startline; i < endline; i += incline) {

fread(&buffer, 1, tga.width, fp);

getline(buffer2, i, tga.width);

getline(buffer3, i + 2, tga.width);

for(n = 0; n < tga.width; n++) {

buffer2[n] = buffer2[n] + buffer[n] / 2;

buffer3[n] = buffer3[n] - buffer[n] / 2;

if(buffer[n] & 1)

if(buffer[n] < 0) buffer3[n]++;

else buffer2[n]++;

}

putline(buffer2, i, tga.width);

putline(buffer2, i + 1, tga.width);

putline(buffer3, i + 2, tga.width);

putline(buffer3, i + 3, tga.width);

}

for(i = startline; i < endline; i += incline) {

fread(&buffer, 1, tga.width, fp);

getline(buffer2, i, tga.width);

getline(buffer3, i + 1, tga.width);

for(n = 0; n < tga.width; n++) {

buffer2[n] = buffer2[n] + buffer[n] / 2;

buffer3[n] = buffer3[n] - buffer[n] / 2;

if(buffer[n] & 1)

if(buffer[n] < 0) buffer3[n]++;

else buffer2[n]++;

}

putline(buffer2, i, tga.width);

putline(buffer3, i + 1, tga.width);

}

for(i = startline; i < endline; i += incline) {

fread(&buffer, 1, tga.width, fp);

getline(buffer2, i + 2, tga.width);

getline(buffer3, i + 3, tga.width);

for(n = 0; n < tga.width; n++) {

buffer2[n] = buffer2[n] + buffer[n] / 2;

buffer3[n] = buffer3[n] - buffer[n] / 2;

if(buffer[n] & 1)

if(buffer[n] < 0) buffer3[n]++;

else buffer2[n]++;

}

putline(buffer2, i + 2, tga.width);

putline(buffer3, i + 3, tga.width);

}

}

}

/* The paletteset function sets the color palette */

void paletteset (char *buffer) {

union REGS regs;

int i;

outp(0x3c6, 0xff);

for(i = 0; i < 255; i++) {

outp(0x3c8, i);

outp(0x3c9, (*buffer++) >> 2);

outp(0x3c9, (*buffer++) >> 2);

outp(0x3c9, (*buffer++) >> 2);

}

}

/* The putline function displays one line of the image */

void putline(char *buffer, unsigned int n, int width) {

char far *ScreenMemory = (char far *)(VGA_MEM + n * LINE_SIZE);

int j;

for(j = 0; j < width; j++) *(ScreenMemory+j) = buffer[j];

}

/* The getline function reads a line of the image from screen memory */

void getline(char *buffer, unsigned int n, int width) {

char far *ScreenMemory = (char far *)(VGA_MEM + n * LINE_SIZE);

int j;

for(j = 0; j < width; j++) *(buffer + j) = *(ScreenMemory + j);

}

/* The error function displays an error message and halts the program */

void error (char *message) {

text();

puts(message);

exit(1);

}

Appendix C -- A Huffman Compressor

/**************************************************************************

* *

* HUFF1.C: Huffman Compression Program. *

* 14-August-1990 Bill Demas Version 1.0 *

*	*

* This program compresses a file using the Huffman codes. *

* *

* USAGE: HUFF1 <input file> <output file> *

*	*

* (DISK to DISK: Input direct from disk, output direct to disk) *

**************************************************************************/

#include <stdio.h>

#include <stdlib.h>

#define VERBOSE /* If defined, prints verbose

program progress when it's

running... */

short father[512];

unsigned short code[256], heap_length;

unsigned long compress_charcount, file_size, heap[257];

unsigned char code_length[256];

long frequency_count[512];

FILE *ifile, *ofile;

/**************************************************************************

MAIN ()

This is the main program. It performs the Huffman encoding procedure in

5 separate steps.

I know that this program can be made more compact & faster, but I was more

interested in UNDERSTANDABILITY !!!

**************************************************************************/

void main (argc, argv)

int argc;

char *argv[];

{

unsigned short generate_code_table ();

void build_code_tree (), build_initial_heap ();

void compress_image (), compression_report ();

void get_frequency_count ();

if (argc == 3)

{

printf ("\nHUFF1: Huffman Code Compression Program.");

printf ("\n 14-Aug-90 Bill Demas. Version 1.0\n\n");

if ((ifile = fopen (argv[1], "rb")) != NULL)

{

fseek (ifile, 0L, 2);

file_size = (unsigned long) ftell (ifile);

#ifdef VERBOSE

printf ("(1) Getting Frequency Counts.\n");

#endif

fseek (ifile, 0L, 0);

get_frequency_count ();

#ifdef VERBOSE

printf ("(2) Building Initial Heap.\n");

#endif

build_initial_heap ();

#ifdef VERBOSE

printf ("(3) Building the Code Tree.\n");

#endif

build_code_tree ();

#ifdef VERBOSE

printf ("(4) Generating the Code Table.\n");

#endif

if (!generate_code_table ())

printf ("ERROR! Code Value Out of Range. Cannot Compress.\n");

else

{

#ifdef VERBOSE

printf ("(5) Compressing & Creating the Output File.\n");

#endif

if ((ofile = fopen (argv[2], "wb")) != NULL)

{

fwrite (&file_size, sizeof (file_size), 1, ofile);

fwrite (code, 2, 256, ofile);

fwrite (code_length, 1, 256, ofile);

fseek (ifile, 0L, 0);

compress_image ();

fclose (ofile);

}

else

printf("\nERROR: Couldn't create output file %s\n", argv[2]);

#ifdef VERBOSE

compression_report ();

#endif

}

fclose (ifile);

}

else

printf ("\nERROR: %s -- File not found!\n", argv[1]);

}

else

printf ("Usage: HUFF1 <input filename> <output filename>\n\n");

}

/**************************************************************************

COMPRESS_IMAGE ()

This function performs the actual data compression.

**************************************************************************/

void compress_image ()

{

register unsigned int thebyte = 0;

register short loop1;

register unsigned short current_code;

register unsigned long loop;

unsigned short current_length, dvalue;

unsigned long curbyte = 0;

short curbit = 7;

for (loop = 0L; loop < file_size; loop++)

{

dvalue = (unsigned short) getc (ifile);

current_code = code[dvalue];

current_length = (unsigned short) code_length[dvalue];

for (loop1 = current_length-1; loop1 >= 0; --loop1)

{

if ((current_code >> loop1) & 1)

thebyte |= (char) (1 << curbit);

if (--curbit < 0)

{

putc (thebyte, ofile);

thebyte = 0;

curbyte++;

curbit = 7;

}

}

}

putc (thebyte, ofile);

compress_charcount = ++curbyte;

}

/**************************************************************************

COMPRESSION_REPORT ()

This function displays the results of the compression sequence.

**************************************************************************/

void compression_report ()

{

float savings;

unsigned short header_charcount;

unsigned long output_characters;

header_charcount = 768 + sizeof (file_size);

output_characters = (unsigned long) header_charcount +

compress_charcount;

printf ("\nRaw characters : %ld\n", file_size);

printf ("Header characters : %d\n", header_charcount);

printf ("Compressed characters : %ld\n", compress_charcount);

printf ("Total output characters : %ld\n", output_characters);

savings = 100 - ((float) output_characters / (float) file_size) * 100;

printf ("\nPercentage savings : %3.2f%%\n", savings);

}

/**************************************************************************

GENERATE_CODE_TABLE ()

This function generates the compression code table.

**************************************************************************/

unsigned short generate_code_table ()

{

register unsigned short loop;

register unsigned short current_length;

register unsigned short current_bit;

unsigned short bitcode;

short parent;

for (loop = 0; loop < 256; loop++)

if (frequency_count[loop])

{

current_length = bitcode = 0;

current_bit = 1;

parent = father[loop];

while (parent)

{

if (parent < 0)

{

bitcode += current_bit;

parent = -parent;

}

parent = father[parent];

current_bit <<= 1;

current_length++;

}

code[loop] = bitcode;

if (current_length > 16)

return (0);

else

code_length[loop] = (unsigned char) current_length;

}

else

code[loop] = code_length[loop] = 0;

return (1);

}

/**************************************************************************

BUILD_CODE_TREE ()

This function builds the compression code tree.

**************************************************************************/

void build_code_tree ()

{

void reheap ();

register unsigned short findex;

register unsigned long heap_value;

while (heap_length != 1)

{

heap_value = heap[1];

heap[1] = heap[heap_length--];

reheap (1);

findex = heap_length + 255;

frequency_count[findex] = frequency_count[heap[1]] +

frequency_count[heap_value];

father[heap_value] = findex;

father[heap[1]] = -findex;

heap[1] = findex;

reheap (1);

}

father[256] = 0;

}

/**************************************************************************

REHEAP ()

This function creates a "legal" heap from the current heap tree structure.

**************************************************************************/

void reheap (heap_entry)

unsigned short heap_entry;

{

register unsigned short index;

register unsigned short flag = 1;

unsigned long heap_value;

heap_value = heap[heap_entry];

while ((heap_entry <= (heap_length >> 1)) && (flag))

{

index = heap_entry << 1;

if (index < heap_length)

if (frequency_count[heap[index]] >= frequency_count[heap[index+1]])

index++;

if (frequency_count[heap_value] < frequency_count[heap[index]])

flag--;

else

{

heap[heap_entry] = heap[index];

heap_entry = index;

}

}

heap[heap_entry] = heap_value;

}

/**************************************************************************

BUILD_INITIAL_HEAP ()

This function builds a heap from the initial frequency count data.

**************************************************************************/

void build_initial_heap ()

{

void reheap ();

register unsigned short loop;

heap_length = 0;

for (loop = 0; loop < 256; loop++)

if (frequency_count[loop])

heap[++heap_length] = (unsigned long) loop;

for (loop = heap_length; loop > 0; loop--)

reheap (loop);

}

/**************************************************************************

GET_FREQUENCY_COUNT ()

This function counts the number of occurrences of each byte in the data

that are to be compressed.

**************************************************************************/

void get_frequency_count ()

{

register unsigned long loop;

for (loop = 0; loop < file_size; loop++)

frequency_count[getc (ifile)]++;

}

/**************************************************************************

* *

* DHUFF.C: Huffman Decompression Program. *

* 14-August-1990 Bill Demas Version 1.0 *

*	*

* This program decompresses a file previously compressed with the *

* HUFF1 program. *

* *

* USAGE: DHUFF <input file> <output file> *

*	*

* (DISK to DISK: Input direct from disk, output direct to disk) *

**************************************************************************/

#include <stdio.h>

#include <stdlib.h>

#define VERBOSE /* If defined, prints verbose

program progress when it's

running... */

short decomp_tree[512];

unsigned short code[256];

unsigned long file_size;

unsigned char code_length[256];

FILE *ifile, *ofile;

/**************************************************************************

MAIN ()

This is the main program. It performs the Huffman decoding procedure in

2 separate steps.

I know that this program can be made more compact & faster, but I was more

interested in UNDERSTANDABILITY !!!

**************************************************************************/

void main (argc, argv)

int argc;

char *argv[];

{

void build_decomp_tree (), decompress_image ();

if (argc == 3)

{

printf ("\nDHUFF: Huffman Code Decompression Program.");

printf ("\n 14-Aug-90 Bill Demas. Version 1.0\n\n");

if ((ifile = fopen (argv[1], "rb")) != NULL)

{

fread (&file_size, sizeof (file_size), 1, ifile);

fread (code, 2, 256, ifile);

fread (code_length, 1, 256, ifile);

#ifdef VERBOSE

printf ("(1) Building the tree.\n");

#endif

build_decomp_tree ();

#ifdef VERBOSE

printf ("(2) Decompressing & Creating the Output File.\n");

#endif

if ((ofile = fopen (argv[2], "wb")) != NULL)

{

decompress_image();

fclose (ofile);

}

else

printf ("\nERROR: Couldn't create output file %s\n", argv[2]);

fclose (ifile);

}

else

printf ("\nERROR: %s -- File not found!\n", argv[1]);

}

else

printf ("Usage: DHUFF <input filename> <output filename>\n\n");

}

/**************************************************************************

BUILD_DECOMP_TREE ()

This function builds the decompression tree.

**************************************************************************/

void build_decomp_tree ()

{

register unsigned short loop1;

register unsigned short current_index;

unsigned short loop;

unsigned short current_node = 1;

decomp_tree[1] = 1;

for (loop = 0; loop < 256; loop++)

{

if (code_length[loop])

{

current_index = 1;

for (loop1 = code_length[loop] - 1; loop1 > 0; loop1--)

{

current_index = (decomp_tree[current_index] << 1) +

((code[loop] >> loop1) & 1);

if (!(decomp_tree[current_index]))

decomp_tree[current_index] = ++current_node;

}

decomp_tree[(decomp_tree[current_index] << 1) +

(code[loop] & 1)] = -loop;

}

}

}

/**************************************************************************

DECOMPRESS_IMAGE ()

This function decompresses the compressed image.

**************************************************************************/

void decompress_image ()

{

register unsigned short cindex = 1;

register char curchar;

register short bitshift;

unsigned long charcount = 0L;

while (charcount < file_size)

{

curchar = (char) getc (ifile);

for (bitshift = 7; bitshift >= 0; --bitshift)

{

cindex = (cindex << 1) + ((curchar >> bitshift) & 1);

if (decomp_tree[cindex] <= 0)

{

putc ((int) (-decomp_tree[cindex]), ofile);

if ((++charcount) == file_size)

bitshift = 0;

else

cindex = 1;

}

else

cindex = decomp_tree[cindex];

}

}

}

Appendix D -- Compressed File Sizes for Individual Files

File Sizes for Hand-drawn Images
Wavelet-based Compression	Normal Interlaced Compression
Name of Image	Huffman	PKZIP	Huffman	PKZIP
ALIEN	29407	25920	28411	18713
AMBUSH	10628	2089	10727	2231
CPUTRUTH	18296	3455	15757	2357
DPD8	16241	6881	20899	4648
EYES	9712	3355	9776	3085
FLOORPLA	28641	14356	28131	10487
GRAV	19423	14269	20788	8407
HGTTG	11960	4232	13412	3185
IRIE	14071	951	18010	810
JAH-LION	15235	3641	18317	2358
NASALOGO	11420	2782	12166	2385
NDCENT	11888	4209	13046	3720
PALM	15274	3845	18189	2577
PEPSI	16686	3247	23014	2379
PS2JOKE	13717	4707	14756	3543
QSL2	18971	8152	N/A	5266
ROGUE	19842	7870	17191	4960
SANTA	10535	2779	9438	1999
SEMINOLE	26490	5299	N/A	3438
TEST	18712	2399	33863	1691
TURNER	23528	12550	32574	11202
Mean value	16590	6502	18867	4776

File Sizes for Reduced Size Hand-drawn Images
Wavelet-based Compression	Normal Interlaced Compression
Name of Image	Huffman	PKZIP	Huffman	PKZIP
ACID	52033	45029	49586	37107
BENTSENI	19468	12271	16571	8867
BOB	24231	17414	21035	14653
BUBATH	28631	13606	24985	8642
BUNDESAD	24631	17154	19781	10864
CHAOS	42633	32959	32672	25212
CHART	47140	31966	38340	20460
EARTHV	44786	40122	40964	31003
EYE	25527	18807	24722	16213
IMPETUSL	37702	24823	29592	16473
ISLAND3	40980	34339	37434	26587
KAOS	27339	21200	22393	15766
MASON	16098	9438	13861	6495
MEM	26187	18528	24464	11280
PICTURES	49072	44434	53310	35930
RECYCLE	31406	25058	27635	17346
ROLEX	40632	29126	34373	18208
RIPLE	40038	31356	31384	22546
SKULL1	23087	12779	15093	8207
SKULL2	25248	15311	17826	11439
SKULL3	19322	9035	13367	6200
SMILE	49203	37919	47679	22375
SNEAKER	18668	7845	13982	5484
SPLASH	47078	38115	38861	24130
ULT5MAP	49855	42754	36005	29643
USMARINE	25614	17529	22676	10122
WDRAGON	54413	45494	53301	34829
Mean value	34482	25719	29700	18373

File Sizes for Low-contrast Images
Wavelet-based Compression	Normal Interlaced Compression
Name of Image	Huffman	PKZIP	Huffman	PKZIP
ALMADEN	38893	35156	39194	27150
ARMY1	29811	27147	30282	20726
CLOWN	42794	38692	41550	25593
CLOWN2	N/A	27539	36977	25486
HOWDY	20564	14647	25113	10192
HUNDREDB	30219	26205	30384	19794
JIGBALL	23610	17080	20483	11289
PIC1	31072	15036	27969	10923
PROFITS	41132	32991	43134	29703
SEAROPES	61121	59503	58879	51563
STARBASE	27536	28015	19856	13230
VEGGIES	24808	22143	27255	17575
XMAS	46026	35397	49177	23217
Mean value	34799	29334	34440	21746

File Sizes for Reduced Size Low-contrast Images
Wavelet-based Compression	Normal Interlaced Compression
Name of Image	Huffman	PKZIP	Huffman	PKZIP
$20	41235	32137	34976	23814
20BILL	50931	43669	46489	336061
500MK	56060	50867	54758	45282
BALLOONS	49729	44978	47250	35338
BARBI	35368	28326	27903	17034
BBIBLE2	41538	35388	41514	28499
BITTI	37391	31074	38412	27272
BONFIRE1	52995	35470	40614	23999
BONFIRE2	55751	40148	23895	27214
BRICKHOU	44393	38019	42426	28635
BUNDESAD	24631	17154	19781	10864
CRASH	30406	24306	27158	18551
CUTE1	47242	42169	45347	33531
EGYPTIAN	63063	62277	60159	53156
GRLENS	39769	31912	28391	20590
HOOGEE	32667	26749	31103	23222
JOOS	33841	28731	29510	23358
LIEKKI	19758	12302	19934	13254
LOR21	19537	12302	17299	9607
MANDM	50694	42654	39886	28865
MBCERIAL	50340	41394	41211	29496
MINAJA	40055	34680	37852	28630
NICKDR	61920	60972	57566	48167
PIGGY	17360	9906	16662	8554
OFFICE	43911	37416	41018	25949
POSTER_5	41952	33773	43663	24327
R136	33290	26795	26726	17346
RYSSA	25361	20018	27144	17795
SHINEON	21523	14042	19089	10503
SPORE1	61387	58749	60928	47019
TAIWAN1	51343	46242	49060	38122
TAIWAN2	59647	56178	56372	42608
TAIWAN3	48550	42129	44087	34092
TALO	46498	45936	36430	24517
TARDIS3	21898	12173	18682	8091
TARDIS6	22852	13125	19091	9250
TITO	31985	24924	33526	21016
TRSI-LOG	29889	24219	29169	20786
USROBO	57616	55059	41520	38255
VF_1S	20632	14862	14060	8724
WB1	40192	31670	41413	29781
WRESTLER	45886	40044	40253	29331
Mean value	40502	33927	36008	33107

N/A = The Huffman compressor could not properly compress these files.

Appendix E -- A Catalog of all images used