Click here to Skip to main content
15,867,308 members
Articles / Desktop Programming / MFC
Article

Embedded Zerotree Image Codec with Bior97 SSE Optimized Wavelet-transform

Rate me:
Please Sign up or sign in to vote.
4.80/5 (14 votes)
20 Oct 2007GPL36 min read 56.3K   3.3K   26   6
This article demonstrates the use of Embedded zero tree still image codec with JPEG 2000 wavelet-filter.
Screenshot - ezw.jpg

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:

  • C++
    unsigned int compress(unsigned char* dest, const unsigned char* sour, 
                            unsigned int w, unsigned int h);
  • C++
    unsigned int decompress(unsigned char* dest, unsigned char* sour, 
                            unsigned int w, unsigned int h);
  • C++
    unsigned int compress(char* dest, const char* sour, unsigned int w, 
                            unsigned int h);
  • C++
    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:

  • C++
    void initgray(unsigned int width, unsigned int height);
  • C++
    unsigned char* compressgray(const unsigned char* data, unsigned int& size, 
                    unsigned int TH = 0);
  • C++
    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:

C++
unsigned int size = 0;
unsigned int quality = _wtoi(argv[3]);
if (quality > 100) quality = 100;

//put quality to log scale
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) {
        //success;
}
else
        wprintf(L"failed to compress image.\n");

Here, I provide logarithmic scale implementation for the quality.

I decompress the image this way:

C++
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.

C++
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:

C++
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.

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)


Written By
Engineer
Russian Federation Russian Federation
Highly skilled Engineer with 14 years of experience in academia, R&D and commercial product development supporting full software life-cycle from idea to implementation and further support. During my academic career I was able to succeed in MIT Computers in Cardiology 2006 international challenge, as a R&D and SW engineer gain CodeProject MVP, find algorithmic solutions to quickly resolve tough customer problems to pass product requirements in tight deadlines. My key areas of expertise involve Object-Oriented
Analysis and Design OOAD, OOP, machine learning, natural language processing, face recognition, computer vision and image processing, wavelet analysis, digital signal processing in cardiology.

Comments and Discussions

 
QuestionThank you,. Pin
Galilus3-May-12 16:59
Galilus3-May-12 16:59 
Generalezw file Pin
chal_adiera27-Oct-10 6:31
chal_adiera27-Oct-10 6:31 
GeneralRe: ezw file Pin
Chesnokov Yuriy7-Dec-10 19:50
professionalChesnokov Yuriy7-Dec-10 19:50 
GeneralGreat article Pin
Arash Partow28-Feb-08 16:43
Arash Partow28-Feb-08 16:43 
AnswerRe: Great article Pin
Chesnokov Yuriy28-Feb-08 20:31
professionalChesnokov Yuriy28-Feb-08 20:31 
GeneralRe: Great article Pin
Arash Partow29-Feb-08 17:31
Arash Partow29-Feb-08 17:31 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.