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.
If you also have a question, or are not satisfied with an answer,
send an e-mail to one address listed in the
Is SPIHT just a particular implementation of Shapiro's EZW algorithm?
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).
How is the bit-allocation problem solved by SPIHT?
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.
What is the importance of the hierarchical trees in the coding process?
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?
I read about a compression method called CREW,
proposed by Ricoh, that looks much like yours. How are they related?
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 .
Why do you not use the midpoint of the interval between two successive thresholds as the quantization value?
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
WWW Image Compression Resources
These pages are still
under construction. Sorry for any inconvenience...