## Introduction

Wavelet transform is the replacement of the well known DCT in JPEG 2000 standard (For a review of the subject, have a look at M. Rabanni, An overview of the JPEG 2000 still image compression standard, Signal Processing: Image Communication 17 (2002) 3-48.) The advantage of wavelets over Fourier is that you transform the whole image without subdivision to 8x8 blocks. Hence you can achieve more compression without blocking defect with superb quality. The Bior97 is one of the filters used in JPEG 2000 with floating point coefficients, allowing perfect compression quality results. I've written an SSE optimized version of this transform for faster processing extending the `BaseFWT2D`

class from my other article 2D Fast Wavelet Transform Library for Image Processing.

The compression of the wavelet-spectrum in JPEG 2000 is implemented with arithmetic codec, though there are several other schemes available for compression. One of them is embedded zero tree (EZW) algorithm. Its advantage is speed. It takes about 1 ms or so to compress about 640x480 wavelet-spectrum. In short, EZW takes advantage of the fact that every pixel in the wavelet frequency band has 4 child pixels in the previous band. It is similar to twice down sampled series of image, with every down sampled image's pixels having four corresponding child pixels in the previous image. So with 3 level wavelet-transform, there are trees of pixels with corresponding structure 1-4-16. If the root pixel of that tree is equal to zero, we set the whole tree to zero without too much loss of the details in the reconstructed image. So instead of saving 21 pixels for a tree using 168 bits, we encode it with 1 bit only as a zero tree, 1:168 compression. In my EZW implementation, I scan wavelet-spectrum in predefined scanning order inspecting those trees, if the root is zero and its four children in the next level are also zeros, I output 0 bit to the stream only, 1:168 compression of the tree. If this condition is not met I output 1 bit and the root pixel value. Then also just one 0 bit for its zero pixel children, having 1:40 compression for that part of the tree and 1 bit and the pixels values for non-zeros from the second level and its children at the third level. With EZW scheme, we actually rearrange the wavelet spectrum, encoding only non-zero pixel coefficients. This way encoded wavelet-spectrum can also be entropy coded with arithmetic codec. It provides about 1.5 additional compression only.

## Background

You should have a background with fast wavelet transform for image processing and principles behind embedded zero tree algorithm. I'm not going to introduce another tutorial on the subject. Just have a look at the various papers available on the Internet. My intent is to share my optimized code. I used the EZW paper "Embedded Zerotree Wavelet Encoding" written by C. Valens when I studied the algorithm. There you can also find a wavelet tutorial. Here I provide my own C++ implementation of the algorithm.

## Using the Code

I provided gray scale image compression console application only, with which you can compress the image to my EZW custom file. The RGB image is converted to a gray scale one and then compressed to the file. Just run the console with the following params:

>ezwconsole.exe c image_file quality

Here `image_file`

is your file to compress and `quality`

is an integer in the range 0 to 100 indicating compressed quality of the image. You can pass any image format to it as it uses GDI+ `Bitmap`

class to load it. It will output *image_file.ezw* as the compressed image file, and print compression results.

To decompress the file, just run it this way:

>ezwconsole.exe d image_file.ezw

It will decompress it to *ezw.bmp* file and open it in your image browser program for viewing with `ShellExecute()`

function.

The classes in the project are:

`BaseFWT2D`

`mBior97 : public BaseFWT2D`

`vec1D`

`EZW`

`CodecY`

`mBior97`

is just the SSE implementation of the `Bior97`

wavelet filter. I added zeros to `tG`

and `H`

filters to facilitate SSE optimized convolutions with `vec1D`

and `BaseFWT2D`

classes you might be familiar from my 2D Fast Wavelet Transform Library for Image Processing article. `EZW`

is the class for embedded zero tree algorithm for a 3 level wavelet-transform. It provides two overloads for compression and decompression of the wavelet spectrum:

unsigned int compress(unsigned char* dest, const unsigned char* sour,
unsigned int w, unsigned int h);

unsigned int decompress(unsigned char* dest, unsigned char* sour,
unsigned int w, unsigned int h);

unsigned int compress(char* dest, const char* sour, unsigned int w,
unsigned int h);

unsigned int decompress(char* dest, char* sour, unsigned int w, unsigned int h);

You can use it with `char`

or `unsigned char `

wavelet spectrum. For the latter, the zero assumed pixel is equal to 128. The `dest`

is the buffer where the EZW coded data will be placed and `sour`

is the wavelet spectrum. `w`

and `h`

are the width and height of the image. They return 0 in case of error and non-zero result indicating the size of the compressed/decompressed spectrum.

The implementation of the codec is done in the `CodecY`

class. It provides three functions:

void initgray(unsigned int width, unsigned int height);

unsigned char* compressgray(const unsigned char* data, unsigned int& size,
unsigned int TH = 0);

int decompressgray(unsigned char* dest, unsigned char* sour);

You need to initialize it to specific image width and height before compression and decompression with `initgray()`

function. For compression, call `compressgray()`

providing with `data`

your image. Upon success it will output compressed image size to variable `size`

and return the pointer to the compressed data. `TH`

is the threshold below which all pixels in the wavelet-spectrum will be zeroed.

I use it this way in my console application:

unsigned int size = 0;
unsigned int quality = _wtoi(argv[3]);
if (quality > 100) quality = 100;
quality = (unsigned int)(100.0f/log(100.0f) * log(float(quality)));
gCodec.initgray(width, height);
unsigned char* frame = gCodec.compressgray(gray, size, 100 - quality);
if (frame != 0) {
}
else
wprintf(L"failed to compress image.\n");

Here, I provide logarithmic scale implementation for the quality.

I decompress the image this way:

struct CODECHDR* phdr = (CODECHDR *)spec;
unsigned char* gray = new unsigned char[phdr->width * phdr->height];
gCodec.initgray(phdr->width, phdr->height);
int res = gCodec.decompressgray(gray, spec);
if (res < 0) {
wprintf(L"failed to decompress: %d\n", res);
return;
}

After compression, the codec puts the CRC of the frame to its header, calculated in the IP checksum manner. The checksum error is `res`

= -3, and the rest of the error codes are put to the *codecy.h* file.

## Points of Interest

I've provided only gray image codec for a start. You can easily extend it to color image compression just arranging three `mBior97`

classes for Y, U and V channels and compress them separately as I do with just the Y channel. I hope I'll have time in future to extend it myself.

## History

#### Update 1.0 - 21 Oct, 2007

Without plunging into writing `CodecYUV`

class supporting compression of color images, I modified a little console application to enable it to compress RGB images with existing `CodecY`

class. I just added RGB to `YCbCr`

conversion and provided three `CodecY`

objects for `Y`

, `Cb `

and `Cr `

channels. Then I just save compressed frames to the file in that order.

yCodec.initgray(width, height);
uCodec.initgray(width, height);
vCodec.initgray(width, height);
unsigned char* yframe = yCodec.compressgray(gray, ysize, 100 - quality);
unsigned char* uframe = uCodec.compressgray(Cb, usize, (100 - quality) + 10);
unsigned char* vframe = vCodec.compressgray(Cr, vsize, (100 - quality) + 10);
unsigned int size = fwrite(yframe, 1, ysize, fp);
size += fwrite(uframe, 1, usize, fp);
size += fwrite(vframe, 1, vsize, fp);

And decompress them in that order too:

gCodec.initgray(phdr->width, phdr->height);
int res = gCodec.decompressgray(gray, pspec);
if (res < 0) {
return;
}
size = res;
pspec += phdr->size + sizeof(CODECHDR);
phdr = (CODECHDR *)pspec;
res = gCodec.decompressgray(Cb, pspec);
if (res < 0) {
return;
}
size += res;
pspec += phdr->size + sizeof(CODECHDR);
phdr = (CODECHDR *)pspec;
res = gCodec.decompressgray(Cr, pspec);
if (res < 0) {
return;
}
size += res;

You may compare the quality of EZW compression with Windows JPEG compressors or others. Additional lossless compression of the EZW file provides about 1.7 compression ratio, however you cannot do the same with JPEG files.