.TH QCCBISKENCODE 3 "QCCPACK" "".SH NAMEQccWAVbiskEncode, QccWAVbiskDecode \-encode/decode an image using the BISK algorithm.SH SYNOPSIS.B #include "libQccPack.h".sp.BI "int QccWAVbiskEncode(const QccIMGImageComponent *" image ", const QccIMGImageComponent *" mask ", int " num_levels ", int " target_bit_cnt ", const QccWAVWavelet *" wavelet ", QccBitBuffer *" output_buffer ", FILE *" rate_distortion_file );.br.sp.BI "int QccWAVbiskEncode2(QccWAVSubbandPyramid *" image_subband_pyramid ", QccWAVSubbandPyramid *" mask_subband_pyramid ", double " image_mean ", int " target_bit_cnt ", QccBitBuffer *" output_buffer ", FILE *" rate_distortion_file );.br.sp.BI "int QccWAVbiskDecodeHeader(QccBitBuffer *" input_buffer ", int *" num_levels ", int *" num_rows ", int *" num_cols ", double *" image_mean ", int *" max_coefficient_bits );.br.sp.BI "int QccWAVbiskDecode(QccBitBuffer *" input_buffer ", QccIMGImageComponent *" image ", const QccIMGImageComponent *" mask ", int " num_levels ", const QccWAVWavelet *" wavelet ", double " image_mean ", int " max_coefficient_bits ", int " target_bit_cnt );.br.sp.BI "int QccWAVbiskDecode2(QccBitBuffer *" input_buffer ", QccWAVSubbandPyramid *" image_subband_pyramid ", QccWAVSubbandPyramid *" mask_subband_pyramid ", int " max_coefficient_bits ", int " target_bit_cnt );.SH DESCRIPTION.SS Encoding.LP.B QccWAVbiskEncode()encodes an image component,.IR image ,using the BISK algorithm by Fowler.An embedded wavelet-based image coder based on the popularbitplane-coding paradigm, BISK is designed specifically for the codingof image objects with arbitrary shape. While other similar algorithms(e.g., SPECK) employ quadtree-based set partitioning to codesignificance-map information, BISK uses a simpler, and moreflexible, binary decomposition via.IR k -dtrees. Additionally, aggressivediscarding of transparent regions is implemented by shrinking sets tothe bounding box of their constituent opaque coefficients beforefurther partitioning.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 bitstream output from the BISK encoder is embedded, meaning thatany prefix of the bitstream can be decoded to give a valid representation of the image.  The BISK 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 QccbiskEncode()optionally supports the use of a shape-adaptive DWT (SA-DWT) rather thanthe usual DWT. That is, .BR QccbiskEncode()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 BISK algorithm..LP.I rate_distortion_fileis a pointer to an output file.If this pointer is not.BR NULL ,then a rate-distortion profile is written to the file whilethe image is being compressed. Essentially, this rate-distortionprofile gives numerous points on the operational rate-distortioncurve of the compressed bitstream produced by.BR QccWAVbiskEncode() ;see "RATE-DISTORTION PROFILE" below for more details.The file pointed to by.I rate_distortion_filemust be opened for writing prior to calling.BR QccWAVbiskEncode() ,and must be closed after.BR QccWAVbiskEncode() returns.If.I rate_distortion_fileis .BR NULL ,no rate-distortion profile is written..LPThe routine.BR QccWAVbiskEncode2()provides an alternative interface to BISK encoding.Specifically,.BR QccWAVbiskEncode2()functions indentically to.BR QccWAVbiskEncode()described above, except that both the image and optional mask areassumed to have had a DWT applied to them prior to calling.BR QccWAVbiskEncode2() .As a consequence, the image and mask are passed to.BR QccWAVbiskEncode2()in the wavelet domain as.IR image_subband_pyramidand.IR mask_subband_pyramid .We note that most applications should opt for.BR QccWAVbiskEncode()rather than.BR QccWAVbiskEncode2() ;however,.BR QccWAVbiskEncode()is implemented essentially as a call to an appropriate DWTfollowed by a call to.BR QccWAVbiskEncode2() .If .BR QccWAVbiskEncode2()is used, it is the responsibility of the calling routineto perform the appropriate DWT prior to calling.BR QccWAVbiskEncode2() ..SS Decoding.LP.B QccWAVbiskDecodeHeader()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 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 QccWAVbiskDecode()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 QccWAVbiskDecodeHeader()(i.e., you call.B QccWAVbiskDecodeHeader() first and then.BR QccWAVbiskDecode() ).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 BISK encoding, then the original transparencymask should be passed to .BR QccWAVbiskDecode()as.IR mask .That is,.I maskshould be the same transparency mask (in the spatial domain)that was passed to.BR QccWAVbiskEncode() .Note that.BR QccWAVbiskDecode()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..LP.BR QccWAVbiskDecode2()provides the appropriate alternative interface to BISK decodingrequired if encoding was done via.BR QccWAVbiskEncode2() .Essentially, .BR QccWAVbiskDecode()is implemented by a call to.BR QccWAVbiskDecode2()followed by an appropriate inverse DWT.If.BR QccWAVbiskDecode2()is used, it is the responsibility of the calling to routineto perform the appropriate inverse DWT subsequent to the callto.BR QccWAVbiskDecode2() .As noted above, most applications should use.BR QccWAVbiskDecode()rather than.BR QccWAVbiskDecode2() ..SH "ALGORITHM"The BISK algorithm involves 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 BISK 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 BISK algorithm is in the significancepass. In many ways, the BISK algorithm can be considered to bea variant of SPECK (Pearlman.IR "et al" .2003)designed specifically for improved shape-adaptive coding.The BISK coder employs two tacticsto this end---aggressivediscarding of transparent regions from sets after partitioning,and a spatial-partitioning structure more flexible than thequadtrees used by SPECK.In quadtree partitioning, the significance state of an entireblock of coefficients is tested and coded, the block is subdivided intofour subblocks of approximately equal size, and the significance-codingprocess is repeated recursively on each of the subblocks.On the other hand, when processing a given set, the BISK coderemploys a different partitioning scheme,.IR k -dtrees (Bentley 1975)rather than quadtrees, to recursively code the significancemap.Like quadtrees,.IR k -dtrees are a recursivespatial partitioning data structure. Unlike quadtrees, which subdividea block into four equally sized subblocks,.IR k -dtrees effectuatea binary partitioning; that is, blocks are divided in two, rather thanquarters. Although there are several approaches for selectingthe location and orientation of the split, we use a simple approach inwhich blocks are divided into approximately equally sized halves, andwe alternate between splitting horizontally and vertically..LPAdditionally, to improve shape-adaptive coding, the BISKcoder "shrinks" each set to the bounding box surrounding theopaque coefficients before subdividing the set into smaller blocks..LPThe BISK coder uses only one type of set, rather than having S and I setsas in SPECK. Consequently, each subband in the DWT decomposition isadded to an LIS at the start of the BISK algorithm, whereas the SPECKalgorithm initializes with only the baseband subband in an LIS..SH "RATE-DISTORTION PROFILE"For an embedded coding, such as that produced by the BISK algorithm,any prefix of the final compressed bitstream may be decoded to producea reconstruction of the original image. This prefix will have anassociated distortion which is necessarily greater than or equal to thedistortion of the full-length bitstream, and a rate that is necessarilyless than or equal to the rate of the full-length bitstream.These rate and distortion values give a single point on the so-calledoperational rate-distortion curve of the embedded coding; evaluatingrate and distortion for a variety of prefixes allows one totrace out an approximation to the entire operational rate-distortion curve..LPIt is computationally expensive to perform multipletruncatations and reconstructions of a bitstream to generate thisopertional rate-distortion curve as the full decoding algorithm(including inverse transform)must be run numerous times. Instead, it is fairly straightforwardto calculate rate and distortion values while encoding istaking place. To do so, the encoder keeps a running estimate of thecurrent mean squared error (MSE)as calculated in the wavelet domain. Each time awavelet coefficient is modified while encoding, the encoder adjuststhe running MSE estimate using the value of the wavelet coefficientas it would be reconstructed in the decoder..LPIn theory, the MSE as calculated by this procedure would be exactly thesame 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 theapproach outlined above will differ somewhat from the spatial-domainMSE, which is really what is of interest.The first discrepancy is due to the fact that, in practice, usuallybiorthogonal, rather than orthonormal, transforms are used forimage compression. Using "near orthogonal" transforms, such as thepopular Cohen-Daubechies-Feauveau biorthogonal family, helpmitigate this effect, however.Additionally, the wavelet-domain MSE calculation ignores the fact thatspatial-domain pixels are "rounded" to integer valuesafter the inverse wavelet transform in the decoder.This, too, should produced only a small deviation, so that the wavelet-domainMSE should usually be quite close to the desired spatial-domainMSE. However, by calculating MSE in the wavelet-domain, one avoidsnumerous and costly inverse-transform calculations..LPIn.BR QccWAVbiskEncode() ,each time a coefficient is modified (in the refinement pass, or when thecoefficient initially becomes significant in the significance pass),the current wavelet-domain MSE estimate, along with the current rateas 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-distortioncurve, typically producing several thousands, or tens of thousands, ofpoints on the curve, depending on the final rate of the compressed bitstream..SH "SEE ALSO".BR biskencode (1),.BR biskdecode (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)J. E. Fowler,"Shape-Adaptive Coding Using Binary Set Splitting with.IR k -dTrees,"in.IR "Proceedings of the International Conference on Image Processing" ,Singapore, October 2004, to appear.W. A. Pearlman, A. Islam, N. Nagaraj, and A. Said,"Efficient, Low-Complexity Image Coding With a Set-Partitioning EmbeddedBlock Coder,".IR "IEEE Transactions on Circuits and Systems for Video Technology" ,to appear, 2003.J. L. Bentley, "Multidimensional Binary Search Trees Used forAssociative Searching,".IR "Communications of the ACM" ,vol. 18, no. 9, pp. 509-517, September 1975..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.