.TH QCCTARPENCODE 3 "QCCPACK" "".SH NAMEQccWAVTarpEncode, QccWAVTarpDecode \-encode/decode an image using the tarp algorithm.SH SYNOPSIS.B #include "libQccPack.h".sp.BI "int QccWAVTarpEncode(const QccIMGImageComponent *" image ", const QccIMGImageComponent *" mask ", double " alpha ", int " num_levels ", int " target_bit_cnt ", const QccWAVWavelet *" wavelet ", QccBitBuffer *" output_buffer );.br.BI "int QccWAVTarpDecodeHeader(QccBitBuffer *" input_buffer ", double *" alpha ", int *" num_levels ", int *" num_rows ", int *" num_cols ", double *" image_mean ", int *" max_coefficient_bits );.br.BI "int QccWAVTarpDecode(QccBitBuffer *" input_buffer ", QccIMGImageComponent *" image ", const QccIMGImageComponent *" mask ", double " alpha ", int " num_levels ", const QccWAVWavelet *" wavelet ", double " image_mean ", int " max_coefficient_bits ", int " target_bit_cnt );.SH DESCRIPTION.SS Encoding.LP.B QccWAVTarpEncode()encodes an image component,.IR image ,using the tarp algorithm by Simard.IR "et al" .The tarp algorithm involves a 2D DWT followed by a progressive "bitplane" coding of the wavelet coefficients using aParzen-window technique to estimate probability of significance andnonadaptive arithmetic coding to code significance-map andrefinement information. See "ALGORITHM" below for more detail..LP.I imageis the image component to be coded and.I bufferis the output bitstream..I buffermust be of.B QCCBITBUFFER_OUTPUTtype and opened via a prior call to.BR QccBitBufferStart (3)..LP.I num_levelsgives the number of levels of dyadic wavelet decomposition to perform,and.I waveletis the wavelet to use for decomposition..LPThe tarp algorithm performance is determined primarily throughthe parameter.IR alpha ,a value that gives the learning rate of the density-estimationprocess implemented by the tarp filter.Simard.IR "et al" .originally used a value of.I alpha= 0.6..LPThe bitstream output from the tarp encoder is embedded, meaning thatany prefix of the bitstream can be decoded to give a valid representation of the image.  The tarp encoder essentially producesoutput bits until the number of bits output reaches.IR target_bit_cnt ,the desired (target) total length of the output bitstream in bits,and then it stops.Note that this is the bitstream length in bits, not the rate of the bitstream(which would be expressed in bits per pixel)..LP.BR QccTarpEncode()optionally supports the use of a shape-adaptive DWT (SA-DWT) rather thanthe usual DWT. That is, .BR QccTarpEncode()can call.BR QccWAVSubbandPyramidShapeAdaptiveDWT (3)as the wavelet transform rather than the usual.BR QccWAVSubbandPyramidDWT (3).The use of a SA-DWT is indicated by a.RB non- NULL.IR mask ;if .I maskis.BR NULL ,then the usual DWT is used.In the case of a SA-DWT,.I mask gives the transparency mask which indicates which pixels of the imageare non-transparent and thus have data that is to be transformed.Refer to .BR QccWAVSubbandPyramidShapeAdaptiveDWT (3)for more details on the calculation of this SA-DWT, andsee "ALGORITHM" below for how the shape-adaptive maskis employed in the tarp algorithm..SS Decoding.LP.B QccWAVTarpDecodeHeader()decodes the header information in the bitstream in the input.I buffer(which must be of.B QCCBITBUFFER_INPUTtype and opened via a prior call to.BR QccBitBufferStart (3)).The header information is returned in.I alpha(the learning-rate parameter of the density-estimation process),.I num_levels(number of levels of wavelet decomposition),.I num_rows(vertical size of image),.I num_cols(horizontal size of image),.I image_mean(the mean value of the original image), and.I max_coefficient_bits(the number of bits used to represent the magnitude of the coefficient with largest absolute value)..LP.B QccWAVTarpDecode()decodes the bitstream.IR buffer ,producing the reconstructed image component,.IR image .The bitstream must already have had its header read by a prior callto.B QccWAVTarpDecodeHeader()(i.e., you call.B QccWAVTarpDecodeHeader() first and then.BR QccWAVTarpDecode() ).If.I target_bit_cntis.BR QCCENT_ANYNUMBITS ,then decoding stops when the end of the input bitstream is reached;otherwise, decoding stops when.I target_num_bitsfrom the input bitstream have been decoded..LPIf a SA-DWT was used in tarp encoding, then the original transparencymask should be passed to .BR QccWAVTarpDecode()as.IR mask .That is,.I maskshould be the same transparency mask (in the spatial domain)that was passed to.BR QccWAVTarpEncode() .Note that.BR QccWAVTarpDecode()will transform this.I maskvia a Lazy wavelet transform, and then pass the transformed maskto .BR QccWAVSubbandPyramidInverseShapeAdaptiveDWT (3).If the usual DWT was used in encoding, then.I maskshould be a.B NULLpointer..SH "ALGORITHM"There are several variants of the tarp algorithm for image coding.The coder originally described by Simard.IR "et al" .applied a scalar quantizer to the coefficients of a 2D DWT andthen used the tarp-filter procedure described below toindependentlycode each of the bitplanes of the coefficients. The quantizer stepsizewas adjusted to optimze performance for a specified target rate.Although this approach results in a progressive coding of the image,strictly speaking, the bitstream is not embedded.On the other hand,the QccPack implementation of tarp coding is an embeddedcoder based on the significance-refinement approachto bitplane coding common to wavelet-based embedded coders.We note that this embedded approach was suggested as analternative implementation by Simard.IR "et al" .in their original paper, but results given there focused on the quantizer-based non-embedded approach just described..LPThe embedded tarp coder asimplemented in QccPackinvolves a 2D DWT followed by a progressive encodingof the bitplanes of wavelet coefficients.As is common with bitplane-based embedded coders,the encoder of the tarp algorithmcodes significance information in a significance passfollowed by refinement-bit information in a refinement pass.The significance pass determines the significance of a wavelet coefficientagainst a given threshold, while the refinement pass codes the bits ofthose coefficients previously determined to be significant..LPThe unique aspect of the tarp algorithm is in the significancepass. The tarp algorithm employs a density-estimation processbased upon Parzen windows to determine the probability that eachcurrently insignificant coefficient becomes significant in the currentsignificance pass. This probability is passed to a two-symbol,nonadaptive arithmeticcoder to code the actual significance value of the current coefficient.The.I alphaparameter to the algorithm determines the shape of the Parzen windowsemployed, effectively determining the learning rate of thedensity-estimation process. The actual density estimation isimplemented as an efficient set of filtering operations that createa causal 2D filter that looks like a canvas propped up by a poleat the current coefficient, hence the name "tarp" filter.That's it - no runlength coding, no zerotrees - just a simpledensity estimation..LPThe refinement pass codes refinement bits using the samenonadaptive arithmetic coder used in the significance pass except thatthe refinement bits are assumed equally likely, and thus a uniformdensity is used by the nonadaptive arithmetic coder..LPThere are several ways to handle the overlapping of the 2D causal tarp filter beyond the image boundaries.Simard.IR "et al" .proposed boundary initial conditions that attempt to spread priorknowledge accumulated during the filtering along the boundary.In contrast, the implementation here takes the simpler route ofmerely assuming all values beyond the image boundaries are insignificant.It is unlikely that either approach differs much from the otherin terms of rate-distortion performance..LPAs proposed by Fowler,to handle shape-adaptive coding (not originally considered by Simard.IR "et al" .),the implementation here merely skips over the transparent regions, maintaining the currentprobability estimate unchanged..LPFinally, we note that Tian and Hemami proposed a variant of tarpcoding somewhat similar to what is implemented here in thatthey use the tarp filter to code significance information.However, their approach is somewhat more sophisticated in thatfraction bitplanes are used in the significance pass toachieve a higher degree of embeddedness..SH "PERFORMANCE"The tarp algorithm offers rate-distortion performanceamazing close to the SPIHT algorithm (see.BR QccSPIHTEncode (3)in the optional QccPackSPIHT module).The following table compares the tarp coder (alpha = 0.6) with theSPIHT coder (arithmetic-coding version)..RS.nf               Lenna ------------------------------------ | Rate  |          PSNR (db)       | | (bpp) |    Tarp          SPIHT   | ------------------------------------ |  0.2  |    32.83    |    32.94   | |  0.5  |    36.74    |    37.11   | |  1.0  |    39.85    |    40.28   | ------------------------------------    Average difference = 0.22 dB              Barbara ------------------------------------ | Rate  |          PSNR (db)       | | (bpp) |     Tarp         SPIHT   | ------------------------------------ |  0.2  |    26.48    |    26.48   | |  0.5  |    31.07    |    31.33   | |  1.0  |    35.90    |    36.43   | ------------------------------------    Average difference = 0.11 dB              Goldhill ------------------------------------ | Rate  |          PSNR (db)       | | (bpp) |    Tarp          SPIHT   | ------------------------------------ |  0.2  |    29.62    |    29.68   | |  0.5  |    32.97    |    32.96   | |  1.0  |    36.16    |    36.37   | ------------------------------------    Average difference = 0.12 dB.fi.RE.SH "NOTES"The tarp-filer algorithm as described originally by Simard.I "et al" .does not employ shape-adaptive coding..SH "SEE ALSO".BR tarpencode (1),.BR tarpdecode (1),.BR imgdwt (1),.BR imgdist (1),.BR QccBitBuffer (3),.BR QccENTArithmeticEncode (3),.BR QccENTArithmeticDecode (3),.BR QccWAVSubbandPyramid (3),.BR QccPackWAV (3),.BR QccPackIMG (3),.BR QccPack (3)P. Simard, D. Steinkraus, and H. Malvar, "On-Line Adaptation in Image Codingwith a 2-D Tarp Filter", in.IR "Proceedings of the IEEE Data Compression Conference" ,J. A. Storer and M. Cohn, Eds.,  Snowbird, UT, April 2002, pp. 422-431..LPJ. E. Fowler, "Shape-Adaptive Tarp Coding," in.IR "Proceedings of the International Conference on Image Processing" ,Barcelona, Spain, September 2003, vol. 1, pp. 621-624..LPC. Tian and S. S. Hemami, "An Embedded Image Coding SystemBased on Tarp Filter with Classification," in.IR "Proceedings of the International Conference on Acoustics, Speech, and Signal Processing" ,Montreal, Canada, May 2004, to appear..SH AUTHORCopyright (C) 1997-2005  James E. Fowler.\"  The programs herein are free software; you can redistribute them and/or.\"  modify them under the terms of the GNU General Public License.\"  as published by the Free Software Foundation; either version 2.\"  of the License, or (at your option) any later version..\"  .\"  These programs are distributed in the hope that they will be useful,.\"  but WITHOUT ANY WARRANTY; without even the implied warranty of.\"  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the.\"  GNU General Public License for more details..\"  .\"  You should have received a copy of the GNU General Public License.\"  along with these programs; if not, write to the Free Software.\"  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.