SPIHT IMAGE COMPRESSION

Technical Discussion

Below is what can be called "graduate-level FAQ:" frequently asked questions about how SPIHT deals with the general problems of image compression, and about the material covered in the papers. Familiarity with the papers and their terminology may be required to understand the answers.

Questions about the demo programs are answered in the FAQ page.

Coding algorithm.
Quantization.

If you also have a question, or are not satisfied with an answer, send an e-mail to one address listed in the home page.

Coding algorithm

Q. Is SPIHT just a particular implementation of Shapiro's EZW algorithm?
A. No. The two methods share some properties and are based on similar principles. Our predecessor to SPIHT was more like EZW. We never failed to recognize EZW's precedence, but now it would be misleading to insist on the similarities, because EZW and our last version have significant differences (some obvious and some quite subtle, but equally important).
Q. How is the bit-allocation problem solved by SPIHT?
A. Well, definitely not in any explicit form, i.e., it is not decided in advance how many bits are going to be used in different parts of the transformed image. And no a priori decision would useful for embedded coding anyway.

With SPIHT the allocation problem is replaced by a scheduling problem. When the encoder tells the decoder that a subset is insignificant, it means that at that moment zero bits are going to be used to quantize the pixels in that set. This is equivalent to say that it (the encoder) wants to know if the bits are not more "profitable" if used in other sets. The same set is visited again later, and eventually it should decide to use some bits for the quantization of its members.

There are some other implicit decisions: when a pixel becomes significant only one more bit (the sign) is used for it. Similarly, pixels gets only one bit in each refinement pass.

Q. What is the importance of the hierarchical trees in the coding process?
A. Theoretically you don't really need those trees. After all, what can't be done with infinite complexity? However, in practice they proved to be very useful in reducing the complexity of the entropy coding process. The fact that good results were obtained with SPIHT even without arithmetic coding proves it. Furthermore, what you think is more efficient: using one bit to inform the decoder to disregard, say, 32x32 pixels, or use a state-of-the-art, very effective, super-fast, quickly-adaptive, context-based, phenomenal entropy-encoder to code 000000.... 1024 times?
Q. I read about a compression method called CREW, proposed by Ricoh, that looks much like yours. How are they related?

A. In our paper "Reversible Image compression via multiresolution representation and predictive coding", presented at the SPIE VCIP Symposium, Cambridge, MA, Nov. 1993, we proposed a transformation for lossless compression called S+P transform (Sequential + Prediction), and presented some embedded coding results with an earlier version of SPIHT.

In March of 1995 Ricoh researchers presented at the IEEE DCC, Snowbird, UT, a paper called "CREW: Compression with reversible embedded wavelets", proposing "reversible wavelets" which are equal to a special case of our S+P transform (predictor "A" in the SPIE paper), and propose a version of EZW for progressive transmission. So, the two works are indeed very similar, but the least we can say is that our work was published more than a year earlier.

We have written a case report on the precedence of our lossy-to-lossless compression method over CREW. We include here a link to this report for those who are interested. CREW Report .

Quantization

Q. Why do you not use the midpoint of the interval between two successive thresholds as the quantization value?
A. A midpoint quantization value is the best choice only for a uniform probability distrution between thresholds. Most images have wavelet coefficients where smaller values are more probable than larger ones. Using some analysis, we chose the 0.38 fraction of the interval rather than the 0.5 midpoint. For the technical details of the derivation, please read the memorandum by Amir Said .

Links to other pages.

SPIHT Home Page;
Properties of the Method
Licensing Information
Demo Programs
Papers
Demo Images
FAQ
WWW Image Compression Resources
Guest Book

These pages are still under construction. Sorry for any inconvenience...