qccspihtencode.3

SPIHT的寫法~~請大家參考看看~~比較一下

.I arithmetic_coded
= 0, the QccPack code is similar to RPI's
.BR fastcode / fastdecd
programs).
However, the difference has been observed to be rather small, with
the QccPack implementation achieving PSNR typically 0.15 dB  below
that achieved with the RPI binary executables (although look at the
Barbara arithmetic-coded results below for an unusually strong QccPack
performance!)
.LP
A quantitative comparison follows using the three "standard" images
(Lenna, Barbara, and Goldhill)
provided with QccPack.  In all of the results, the wavelet transform employed
is a 5-level dyadic decomposition using
the 9/7 Cohen-Daubechies-Feauveau biorthogonal wavelet with
symmetric extension at the image boundaries (this is the same transform
used in Said and Pearlman's paper and in their executable code).
The RPI results refer to the results obtained using the
SPIHT executable code available from RPI.
The "average difference" is the average of the RPI PSNR minus the
QccPack PSNR over the range 0.05 dB to 1 dB calculated at every 0.025 dB.

.RS
.nf
      Lenna - Arithmetic Coding
 ------------------------------------
 | Rate  |          PSNR (db)       |
 | (bpp) |     RPI         QccPack  |
 ------------------------------------
 |  0.2  |    33.15    |    32.94   |
 |  0.5  |    37.21    |    37.11   |
 |  1.0  |    40.41    |    40.29   |
 ------------------------------------
    Average difference = 0.16 dB


     Lenna - No Arithmetic Coding
 ------------------------------------
 | Rate  |          PSNR (db)       |
 | (bpp) |     RPI         QccPack  |
 ------------------------------------
 |  0.2  |    32.73    |    32.60   |
 |  0.5  |    36.84    |    36.72   |
 |  1.0  |    39.98    |    39.89   |
 ------------------------------------
    Average difference = 0.13 dB


     Barbara - Arithmetic Coding
 ------------------------------------
 | Rate  |          PSNR (db)       |
 | (bpp) |     RPI         QccPack  |
 ------------------------------------
 |  0.2  |    26.66    |    26.47   |
 |  0.5  |    31.40    |    31.33   |
 |  1.0  |    36.41    |    36.43   |
 ------------------------------------
    Average difference = 0.05 dB


    Barbara - No Arithmetic Coding
 ------------------------------------
 | Rate  |          PSNR (db)       |
 | (bpp) |     RPI         QccPack  |
 ------------------------------------
 |  0.2  |    26.29    |    26.11   |
 |  0.5  |    30.94    |    30.80   |
 |  1.0  |    35.94    |    35.79   |
 ------------------------------------
    Average difference = 0.16 dB


     Goldhill - Arithmetic Coding
 ------------------------------------
 | Rate  |          PSNR (db)       |
 | (bpp) |     RPI         QccPack  |
 ------------------------------------
 |  0.2  |    29.85    |    29.68   |
 |  0.5  |    33.13    |    32.96   |
 |  1.0  |    36.55    |    36.37   |
 ------------------------------------
    Average difference = 0.15 dB


   Goldhill - No Arithmetic Coding
 ------------------------------------
 | Rate  |          PSNR (db)       |
 | (bpp) |     RPI         QccPack  |
 ------------------------------------
 |  0.2  |    29.53    |    29.33   |
 |  0.5  |    32.71    |    32.54   |
 |  1.0  |    36.00    |    35.84   |
 ------------------------------------
    Average difference = 0.14 dB
.fi
.RE

.SH "SHAPE-ADAPTIVE CODING"
The usual way to handle arbitrarily shaped objects within SPIHT is to
permanently set transparent regions in the image 
to "insignificant" during the SA-DWT so that the SPIHT algorithm
processes these transparent regions in a manner identical to that of other
insignificant coefficients. This approach has been taken for
a number of zerotree-based coding algorithms; see Li and Li for
an example of such.
Minami
.IR "et al" .
go one step further on this basic approach by discarding all
sets of coefficients that lie entirely within a transparent region
from the lists maintained by SPIHT. Although this refinement typically
offers a small gain in performance, the size of the gain is dependent
on how much of the overall image is transparent.
The QccPack implementation of SPIHT follows the approach by
Minami
.IR "et al" .
for shape-adaptive coding.
.LP
Finally, note that the concept of
shape-adaptive coding arose in the work surrounding
the MPEG-4 standard and was
not considered in the original work by Said and Pearlman.
.SH "NUMBER OF DECOMPOSITION LEVELS AND IMAGES OF ARBITRARY SIZE"
The QccPack implementation of SPIHT has the constraint
that the dimensions of the image must be an integer
multiple of two raised to the power
.RI ( num_levels " + 1)."
The reason for this limitation is that the zerotree structure in 
SPIHT, as originally described by Said and Pearlman, is built upon 
blocks of coefficients of size 2x2, and these blocks are coded together. 
Consequently, each subband at each decomposition scale is required to
divide into an integer number of these 2x2 blocks, a requirement that
translates into the power-of-two constraint on the size of the image.
.LP 
There are a number of ways to circumvent this limitation of SPIHT. Although
it would possible to make slight modifications 
to the zerotree structure to accommodate blocks of sizes different from 
2x2 near the borders of subbands as needed to accommodate arbitrary 
sized images, the easiest way around the limitation is to 
maintain the original 2x2 block size and let these blocks overlap the 
subband boundary as needed. One would then treat all portions of the 
block beyond the subband boundary as permanently insignificant and 
proceed with the original SPIHT algorithm. This solution is actually a 
special case of shape-adaptive coding as discussed above.
That is, one could easily "pad" an
.IR M1 x M2
image to size
.IR N1 x N2 ,
where
.I N1
and
.I N2
are the closest integer multiples of
.RI 2^( num_levels " + 1)"
greater than or equal to
.I M1
and
.IR M2 , 
respectively. The padded pixels are then considered to be 
"transparent," and the SPIHT coder is passed a transparency mask of size 
.IR N1 x N2
consisting of simply a single rectangular opaque region of size 
.IR M1 x M2 .
It would be possible to have
.BR QccSPIHTEncode()
automatically pad the image 
in this manner when needed, but this has not
been implemented (yet).
.SH "RATE-DISTORTION PROFILE"
For an embedded coding, such as that produced by the SPIHT algorithm,
any prefix of the final compressed bitstream may be decoded to produce
a reconstruction of the original image. This prefix will have an
associated distortion which is necessarily greater than or equal to the
distortion of the full-length bitstream, and a rate that is necessarily
less than or equal to the rate of the full-length bitstream.
These rate and distortion values give a single point on the so-called
operational rate-distortion curve of the embedded coding; evaluating
rate and distortion for a variety of prefixes allows one to
trace out an approximation to the entire operational rate-distortion curve.
.LP
It is computationally expensive to perform multiple
truncatations and reconstructions of a bitstream to generate this
opertional rate-distortion curve as the full decoding algorithm
(including inverse transform)
must be run numerous times. Instead, it is fairly straightforward
to calculate rate and distortion values while encoding is
taking place. To do so, the encoder keeps a running estimate of the
current mean squared error (MSE)
as calculated in the wavelet domain. Each time a
wavelet coefficient is modified while encoding, the encoder adjusts
the running MSE estimate using the value of the wavelet coefficient
as it would be reconstructed in the decoder.
.LP
In theory, the MSE as calculated by this procedure would be exactly the
same as the MSE calculated in the original spatial domain,
providing that an orthonormal wavelet transform is used
(a direct consequence of Parseval's theorem).
However, in practice, the MSE as calculated in the wavelet domain using the
approach outlined above will differ somewhat from the spatial-domain
MSE, which is really what is of interest.
The first discrepancy is due to the fact that, in practice, usually
biorthogonal, rather than orthonormal, transforms are used for
image compression. Using "near orthogonal" transforms, such as the
popular Cohen-Daubechies-Feauveau biorthogonal family, help
mitigate this effect, however.
Additionally, the wavelet-domain MSE calculation ignores the fact that
spatial-domain pixels are "rounded" to integer values
after the inverse wavelet transform in the decoder.
This, too, should produced only a small deviation, so that the wavelet-domain
MSE should usually be quite close to the desired spatial-domain
MSE. However, by calculating MSE in the wavelet-domain, one avoids
numerous and costly inverse-transform calculations.
.LP
In
.BR QccSPIHTEncode() ,
each time a coefficient is modified (in the refinement pass, or when the
coefficient initially becomes significant in the significance pass),
the current wavelet-domain MSE estimate, along with the current rate
as calculated from the number of bits written to the output bitstream thus far,
is written to the output rate-distortion file, in ASCII.
This is a fairly fine sampling of the operational rate-distortion
curve, typically producing several thousands, or tens of thousands, of
points on the curve, depending on the final rate of the compressed bitstream.
.SH "SEE ALSO"
.BR spihtencode (1),
.BR spihtdecode (1),
.BR QccBitBuffer (3),
.BR QccWAVPerceptualWeights (3),
.BR QccWAVSubbandPyramid (3),
.BR QccWAVSubbandPyramidDWT (3),
.BR QccWAVSubbandPyramidShapeAdaptiveDWT (3),
.BR QccPackWAV (3),
.BR QccPackIMG (3),
.BR QccPack (3)

A. Said and W. A. Pearlman,
"A New, Fast, and Efficient Image Codec Based
on Set Partitioning in Hierarchical Trees,"
.IR "IEEE Transactions on Circuits and Systems for Video Technology" ,
vol. 6, no. 3, pp. 243-250, June 1996.
.LP
S. Li and W. Li, "Shape-Adaptive Discrete Wavelet Transforms for
Arbitrarily Shaped Visual Object Coding,"
.IR "IEEE Transactions on Circuits and Systems for Video Coding" ,
vol. 10, pp. 725-743, August 2000.
.LP
G. Minami, Z. Xiong, A. Wang, and S. Mehrota,
"3-D Wavelet Coding of Video With Arbitrary Regions of Support,"
.IR "IEEE Transactions on Circuits and Systems for Video Technology" ,
vol. 11, no. 9, pp. 1063-1068, September 2001.

.SH AUTHOR
Copyright (C) 1997-2006  James E. Fowler

.SH LICENSE
The Set Partitioning In Hierarchical Trees (SPIHT) algorithm is protected
by US Patent #5,764,807 (issued June 9, 1998), US Patent #6,674,911 (issued
January 6, 2004), and other international patents and patents pending. An
implementation of the SPIHT algorithm is included herein (utility programs
spihtencode and spihtdecode, and spiht.c in the QccPackSPIHT module of the
QccPack library) with the permission of PrimaComp, Inc., exclusive holder
of patent rights. PrimaComp has graciously granted a license with certain
restrictions governing the terms and conditions for use, copying,
distribution, and modification of the SPIHT algorithm implementation
contained herein. Specifically, only use in academic and non-commercial
research is permitted, while all commercial use is prohibited.  Refer to
the file LICENSE-SPIHT for more details.