Vector quantization of image subbands: a survey <s> Vector quantization on separate bands <s> This paper proposes a new method for image coding involving two steps. First we use a ''Dual Recursive Wavelet'' Transform in order to obtain a set of subclasses of images with better characteristics than the original image (lower entropy edges discrimination . . . ). Second according to Shannon''s rate distortion theory the wavelet coefficients are vector quantized using the Kohonen Self-Organizing Feature Maps. We compare this training method with the well known LBG algorithm.© (1990) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only. <s> BIB001 </s> Vector quantization of image subbands: a survey <s> Vector quantization on separate bands <s> A two-step scheme for image compression that takes into account psychovisual features in space and frequency domains is proposed. A wavelet transform is first used in order to obtain a set of orthonormal subclasses of images; the original image is decomposed at different scales using a pyramidal algorithm architecture. The decomposition is along the vertical and horizontal directions and maintains the number of pixels required to describe the image at a constant. Second, according to Shannon's rate-distortion theory, the wavelet coefficients are vector quantized using a multiresolution codebook. To encode the wavelet coefficients, a noise-shaping bit-allocation procedure which assumes that details at high resolution are less visible to the human eye is proposed. In order to allow the receiver to recognize a picture as quickly as possible at minimum cost, a progressive transmission scheme is presented. The wavelet transform is particularly well adapted to progressive transmission. > <s> BIB002 </s> Vector quantization of image subbands: a survey <s> Vector quantization on separate bands <s> A scheme for image compression that takes into account psychovisual features both in the space and frequency domains is proposed. This method involves two steps. First, a wavelet transform used in order to obtain a set of biorthogonal subclasses of images: the original image is decomposed at different scales using a pyramidal algorithm architecture. The decomposition is along the vertical and horizontal directions and maintains constant the number of pixels required to describe the image. Second, according to Shannon's rate distortion theory, the wavelet coefficients are vector quantized using a multiresolution codebook. To encode the wavelet coefficients, a noise shaping bit allocation procedure which assumes that details at high resolution are less visible to the human eye is proposed. In order to allow the receiver to recognize a picture as quickly as possible at minimum cost, a progressive transmission scheme is presented. It is shown that the wavelet transform is particularly well adapted to progressive transmission. > <s> BIB003 </s> Vector quantization of image subbands: a survey <s> Vector quantization on separate bands <s> Abstract A hierarchical image coding algorithm based on sub-band coding and adaptive block-size multistage vector quantization (VQ) is proposed, and its coding performance is examined for super high definition (SHD) image. First, the concept on SHD image is briefly described. Next, the signal power spectrum is evaluated, and the sub-band analysis pattern is determined from its characteristics. Several quadrature mirror filters are examined from the viewpoints of reconstruction accuracy, coding gain, and low-pass signal quality. Then an optimum filter is selected for the sub-band analysis. The two-stage VQ using the adaptive bit allocation is also introduced to control quantization accuracy and to achieve high-quality image reproduction. Coding performance and hierarchical image reconstruction are demonstrated using SNR and some photographs. <s> BIB004 </s> Vector quantization of image subbands: a survey <s> Vector quantization on separate bands <s> In this paper, we present a way of incorporating some important features of the human visual system in the coding of images within the framework of subband decomposition and of lattice vector quantization (VQ). As lattice VQ uses regular distribution of nodes, we use a non-linear pre-normalization of the signals in each subband, taking into account the visibility of impairments in the subbands and particularly the masking effects. Visually optimized subband lattice VQ allows us to encode complex images at bit rates between 0.4 to 0.6 bit/pixel without any visible distortion on a high-quality display.© (1993) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only. <s> BIB005 </s> Vector quantization of image subbands: a survey <s> Vector quantization on separate bands <s> A fast rate-distortion (R-D) optimal scheme for coding adaptive trees whose individual nodes spawn descendents forming a disjoint and complete basis cover for the space spanned by their parent nodes is presented. The scheme guarantees operation on the convex hull of the operational R-D curve and uses a fast dynamic programing pruning algorithm to markedly reduce computational complexity. Applications for this coding technique include R. Coefman et al.'s (Yale Univ., 1990) generalized multiresolution wavelet packet decomposition, iterative subband coders, and quadtree structures. Applications to image processing involving wavelet packets as well as discrete cosine transform (DCT) quadtrees are presented. > <s> BIB006 </s> Vector quantization of image subbands: a survey <s> Vector quantization on separate bands <s> We consider coding gain and spatial localisation properties of DWT filters for still image compression. A high coding gain, relative to a highly correlated image source model, ensures that slowly varying image areas are coded efficiently. A low spatial width ensures that anomalies such as edges can also be coded efficiently. By considering an image model we design filters that simultaneously exhibit a high coding gain and low spatial width. Several existing filters are also examined. Several filter sets are then compared for image compression using a DWT and a JPEG type quantisation method. The filters with the best spatial width and coding gain properties outperform the other filters at low bit rates, especially with regard to ringing distortion.<<ETX>> <s> BIB007 </s> Vector quantization of image subbands: a survey <s> Vector quantization on separate bands <s> We extend our previous work on space-frequency quantization (SFQ) for image coding from wavelet transforms to the more general wavelet packet transforms. The resulting wavelet packet coder offers a universal transform coding framework within the constraints of filterbank structures by allowing joint transform and quantizer design without assuming a priori statistics of the input image. In other words, the new coder adaptively chooses the representation to suit the image and the quantization to suit the representation. Experimental results show that, for some image classes, our new coder gives excellent coding performance. <s> BIB008 </s> Vector quantization of image subbands: a survey <s> Vector quantization on separate bands <s> Describes a new coding scheme based on a joint optimization of signal decomposition and of lattice vector quantizers. The adaptive signal decomposition uses wavelet packets that allow to best match the decomposition to the signal nonstationary characteristics. In order to obtain a good tradeoff between frequency and spatial localization, nonstationary wavelet packets based on filters varying at each stage of the tree structured decomposition are considered. The complete tree is pruned into the best basis subtree which minimizes a perceptually weighted distortion for a given bit rate. Each subband is then quantized using data rate constrained lattice vector quantizers. The choice of the quantizer is usually determined by the minimization of the overall mean squared error of the reconstructed signal under the constraint of a given bit rate [Ramchandran and Vetterli, 1993]. However, this procedure is not optimum in terms of visual quality. A procedure of quantization based on the minimization of perceptually weighted distortion of each frequency band is introduced. The results show a very significant improvement both in terms of SNR and of visual quality versus the JPEG algorithm. > <s> BIB009 </s> Vector quantization of image subbands: a survey <s> Vector quantization on separate bands <s> Lattice vector quantization schemes offer high coding efficiency without the burden associated with generating and searching a codebook. The distortion associated with a given lattice is often expressed in terms of the G number, which is a measure of the mean square error per dimension generated by quantization of a uniform source. Subband image coefficients, however, are best modeled by a generalized Gaussian, leading to distortion characteristics that are quite different from those encountered for uniform, Laplacian, or Gaussian sources. We present here the distortion associated with Z, E/sub 8/, and Leech lattice quantization for coding of generalized Gaussian sources, and show that for low bit rates the Z lattice offers both the best performance and the lowest implementational complexity. <s> BIB010 </s> Vector quantization of image subbands: a survey <s> Vector quantization on separate bands <s> Lattice vectorquantization( LVQ) has been recently interested to many people by its promising property.Due to the distribution of wavelet im age coefficients,pyramidal lattice vector quantization ( PLVQ) was introduce.A general coding sheme was proposed to eliminate the redundance of VQ output vectors.Furthermore,a fast algorithm of labeling lattice points and a fast inverse algorithm of finding lattice points were given.Significance m ap in VQ which determines non-zero vector position efficiently was introduce.Finally,transmission priority in case of Asynchronous Transfer Mode was suggest. <s> BIB011
When quantizing the subbands separately, the quantizer design problem involves the selection of a vector dimension (and vector shape) in each subband, as well as a bit rate for each subband. This bit allocation is often achieved in an ad hoc way. Some methods solve an optimization problem in which the overall quantization distortion is minimized subject to a constraint on the overall bit rate. The resulting quantizers can be unrealizable due to excessive complexity or memory requirements, and so the optimization methods usually invoke constraints on encoding complexity or memory as well. Additional sophistication can be added to the optimization problem by including perceptual factors in the distortion measure, or by having the optimization choose the vector dimension for each subband as well as the bit rate. With simple quantization schemes like PCM, Lagrange multiplier solutions exist to the optimal bit allocation problem. For more complex subband VQ strategies, it can be solved by conventional nonlinear smooth optimization techniques. The vector-forming strategy is usually simple in the intra-band case. Most systems employ square blocks of size 1 1, 2 2, or 4 4, together with the obvious tiling strategy. Some systems used vectors of size 2 4 or 4 2, which provide an intermediate dimension with a still-simple tiling strategy. Such rectangular blocks are usually taken to be oriented along the direction of the detail (either horizontal or vertical) of each high frequency subband, as that way there is greater inter-coe cient correlation. One study which examined codeword orientation concluded that these rectangular vectors oriented along the direction of greater inter-coe cient correlation were superior to vectors oriented in the perpendicular direction 3]. Two other studies suggested that, under particular quantization strategies, there might be advantages to scrambling the coe cients within a band when forming intra-band vectors 14, 64]. Multistage and residual vector quantizers: The earliest e ort at separately encoding the bands focused on multistage VQ 133] . Early work was with a 2-stage coder 133, 62] and a later study used a variable-rate coder with as many as 48 stages 20]. In 133], a two-band partition in horizontal and vertical frequencies yielded a total of four subbands, the lowest of which was encoded using multistage VQ. The error in the rst stage was quantized to re ne the reconstruction. The bit allocation algorithm used the fact that perceptually signi cant errors tend to occur in clusters in high-entropy parts of the input image. Application of this technique to a 512 512 monochrome image resulted in good quality at 0.5 bpp. Higher quality at the same bit rate was attained by increasing the number of subbands to 16. Multistage VQ for subband coding of super high de nition images was developed in a series of articles   BIB004 . Several QMFs were examined from the viewpoints of reconstruction accuracy, coding gain, and low pass characteristics. A two-stage encoder was introduced in which the rst stage is applied to the subband coe cients, and the second stage is applied in the spatial domain. The system employed 4 4 blocks in a 4-band decomposition. The lowest band was scalar quantized. Bit allocation was proportional to the logarithm of the subband variance. Codebooks were designed by the GLA. Variable rate multi-stage VQ was used in 20]. Variable rate multi-stage VQ examines the energy of the residual vector after each stage. If it falls below a predetermined threshold, the encoding stops. The method requires side information to inform the decoder of the number of stages to expect for each vector. The vectors were rst classi ed according to their energy level, which was scalar quantized separately with a Lloyd-Max quantizer. Each vector was then quantized with either a xed rate or variable rate multi-stage VQ, depending on the vector size. In the di erent levels, BIB007  One study used multistage VQ with a multi-path search of the direct sum codebook, which could yield almost the performance of a full-search while having only slightly more computational complexity than a sequential search 90]. An iterative descent algorithm based on a Lagrangian minimization, the entropy-constrained residual VQ (EC-RVQ) design algorithm attempted to jointly optimize each stage codebook to minimize the reconstruction error over all the training data subject to a constraint on the output entropy of the RVQ. The system could be used with large vector sizes (e.g., 8 8) . The decomposition was into 7 bands using a computationally e cient IIR allpass polyphase lter bank based on 2-D decompositions. Bit allocation was by the \equal-slope" method. For the LENA test image, PSNRs of 28.28 and 31.05 were achieved at 0.10 and 0.16 bpp respectively. Semi-orthogonal spline-wavelet-packets 33] were used with interpolative/residual VQ on the baseband and full search VQ on the other bands in 96]. Before quantization, a decision was made for each subimage of the percentage of coe cients to be retained, which depended on the desired compression ratio. Those wavelet packet coe cients with magnitude below a threshold would be set to zero. If the number of non-zero entries in a vector was below a predetermined value, the vector was set to zero. Compression results were PSNRs of 29.02 and 27.47 dB at 0.1 and 0.08 bpp, respectively, for the LENA test image. Multistage subband VQ was shown to be robust against fading channels in wireless communications 79]. The idea is that the burst error behavior typical of fading channels can cause the loss of several bits describing a single stage in a multistage VQ. Provided the lost stage is not the rst stage, the remaining stages will still provide a good overall reproduction. The rst stage bits are given the extra protection of error correcting codes. The particular implementation uses a seven band decomposition with Johnston QMF lters, a three stage VQ for the baseband, and scalar-quantized individual coe cients with entropy coded location information for the higher bands. Performance was reported on a simulated Digital European Cordless Telecommunication (DECT) system to be 35 dB at 0.69 bpp and a channel SNR of 15 dB. Lattice vector quantizers and ECVQ: For the encoding of intra-band subband coe cients, lattice VQ has been explored more than any other single type of VQ. One series of articles used a biorthogonal wavelet decomposition in the form of a quincunx pyramid, together with a lattice quantizer based on a suitably scaled and truncated version of the BIB011 lattice 5, 15, 16] . For LENA, a PSNR of 30 dB was obtained when the entropy rate was 0.064 bpp. However, the actual bit rate obtainable for this PSNR was not speci ed. Their work compared the quincunx pyramid and the BIB011 lattice against the dyadic wavelet and the E 8 and D 4 lattices, nding the former combination to be superior. The later work focused on the issues of scaling and truncating the lattices, and counting the number of points within the truncated area 16]. The basic method was to truncate the lattice as a pyramid, encoding those input vectors inside the truncation region by nding the nearest lattice point, and encoding those input vectors in the overload region (outside the truncation region) by projecting onto the pyramid's outer shell. The index for the nearest lattice point on that outer shell would then be encoded, as well as a quantized version of the projection distance, so that the decoder could reconstruct those vectors by projecting back out. Results were a PSNR of 30.3 at 0.174 bpp for the LENA test image. A related paper examined the use of lattice VQ with an elliptical truncation region 17]. The elliptical region of support was thought to be useful because neighboring wavelet coe cients retain some positive correlation; in two other studies, this perceived problem was solved by removing the correlation by forming vectors from non-neighboring coe cients BIB005 BIB010 . Another study pointed out that the entropy rate achieved in 15] was not at all representative of the actual bit rate achievable because the number of available codewords in the lattice codebook could be orders of magnitude larger than the number of codewords actually used by a given test image 120]. This work also examined a drawback to the pyramidal truncation shape of 16]. Input vectors lying outside the truncation region could be in a \columnar region" or a type of \wedge region," depending on whether they project to a lattice point with all non-zero coordinates, or to a lattice point with 1 or more zero coordinates. If the projection distance were not quantized, the distortion incurred by quantizing input vectors falling in a columnar portion of the overload region would be bounded by the shape of the Voronoi region of the lattice points in an untruncated lattice. But the distortion incurred by input vectors in a wedge region of the overload zone might not be bounded except by the bounds on the input vector range itself. This drawback was discussed and solved in 120] by using a dual density lattice composed of two concentric pyramidal volumes of lattice points both centered on the origin, with the inner pyramidal volume having a denser placement of lattice points. By allowing the density of lattice points in the outer volume to be much lower, the truncation of the outer lattice did not need to be so severe, and the volume of the overload wedge regions could be reduced as much as desired. The design algorithm then involved selecting scale factors and pyramidal heights for both lattice sections. Lattice VQ was compared against ECVQ and against unstructured full-search VQ designed by the GLA in 136]. A 4-level octaveband decomposition with 9-tap QMFs produced 13 subbands. Bit allocation used the \equal-slope" method. Initial comparisons were made for 8-D vectors from selected subbands. ECVQ performed best at low rates. The E 8 lattice did best at higher rates, possibly because ECVQ was strongly constrained by its limited number of codewords. The Z 8 lattice with centroid reproductions did almost as well as E BIB001 . Most of the lattice VQ gain over SQ was found to be due to the joint encoding and joint centroids; the denser sphere packing of E 8 seemed less important. Using E 8 for the nest scale, D BIB007 for the next scale, and A 2 for the coarsest levels resulted in a PSNR of 30.9 dB at 0.136 bpp (where that cited rate was an entropy rate and assumed an ideal entropy coder). The authors mentioned the utility of shifting the sub-image by one pixel horizontally, vertically, or diagonally prior to decomposing and downsampling it further, as a means of extending the training sequence size at the coarser levels. A method for incorporating some features of human vision within the framework of subband lattice VQ was presented in 14]. A 13-band decomposition was performed with a Daubechies wavelet lter. Vectors of 4 and 16 dimensions were formed intra-band. Vectors composed of distant coe cients were found to provide better results than vectors composed of adjacent coe cients, although details on the vector composition were not provided. Psychovisual experiments were performed to determine the maximum unit size for each lattice and for each subband such that no granular noise would be visible. This threshold, called the di erential visibility threshold, depended on the viewing distance and on masking e ects, and was used (approximated by a piece-wise linear function) to normalize each input vector prior to quantization. The Z lattices were found to be generally superior to the D, E, and lattices. Transparent quality on high-quality monitors was achieved at between 0.42 and 0.78 bpp, depending on the complexity of the input image. A comparison of the granular distortion and overload distortion for various lattices on subband coe cients was presented in 64]. For generalized Gaussian sources at low bit rates, the Z lattice was shown to provide better performance and lower computational complexity than the E 8 and Leech lattices. A small number of studies have examined the exibility of the wavelet packet decomposition 38] for image coding BIB006 BIB008 BIB009 . One study which used VQ employed non-stationary wavelet packets based on lters varying at each stage of the tree-structured decomposition 115]. The complete tree was pruned into the best basis subtree which minimized a perceptually weighted distortion   for a given bit rate. Each subband was separately quantized with lattice VQs (D n and E n ) with a dead zone. Bit allocation was by the \equal-slope" method. A trellis-coded VQ based on lattice codebooks was used in an intra-band fashion on the decomposition produced by separable biorthogonal wavelet lters of 9 and 7 taps 104]. In the di erent subbands, the VQ dimensions were 1, 4, 16, and 64, and the bit allocation was based on 7] . Results on LENA were 28.9 dB at 0.265 bpp, and 29.2 dB at 0.281 bpp. One study compared lattice VQ and kd-tree structured VQ for scalable video compression 139]. The goal was to decouple the frame rate, resolution, and bandwidth of the encoding from those of the decoding, by using successively larger codebooks that were nested subsets of the largest codebook. A hybrid SQ/ECVQ system was used in 112]. The input image was decomposed into 10 octave-band subbands by 3 stages of a 12-tap QMF. Subbands were blocked into 4-D vectors. If the standard deviation of an input vector was below a threshold, it was quantized to zero. Otherwise, the component magnitudes were individually compared against a di erent threshold. If they were all below it, the vector was quantized with an ECVQ. If not, the components were scalar quantized with a modi ed scalar quantizer that had uniformly spaced decision thresholds but output levels based on interval centroids. In either case, the output indices were Hu man coded. Use of the VQ provided an improvement in both SNR and subjective quality compared to SQ with run-length entropy coding or with block Hu man coding. Pruned tree-structured vector quantizers (PTSVQ): PTSVQ and lattice VQ used for packet-video were both examined in 113]. One scheme used an octave-band decomposition with the 16C QMF lter, resulting in 7 subbands. Separate PTSVQs were designed by the GLA for each subband. The tree structure can be exploited in a straightforward manner for layered ATM video coding. High priority packets contain the initial information from a smaller subtree, and enhancement-layer packets, subject to cell-loss, code deeper into the tree. A second scheme used time-domain aliasing cancellation parallel lterbanks to produce 64 uniform subbands. These were lattice quantized ( 16 , E 8 ). Samples of magnitude below a given threshold were excluded from VQ encoding via run-length coding. The remaining samples were grouped together for VQ coding. The method is not quite a pure intra-band method; if a vector could not be completely lled with the samples from one subband, samples from the following subband were added. The enhancement-layer coder was used for the residual error from the base-layer coder. The algorithm involving 64 uniform subbands with lattice VQ was found to be superior to the 7-band octave band decomposition with PTSVQ, and so the former algorithm was investigated with a variety of cell-loss rates and motioncompensated prediction and interpolation schemes. TSVQ was also used intra-band in 98] and 84]. In the former work, 2 2 or 4 4 blocks were coded from a 4-band decomposition of image sequence data. Motion compensation was conducted on the low band. A small subtree was used for encoding unless the MSE of the quantized block exceeded a pre-determined threshold, in which case a large tree would be used. In 84], binary trees were created for 4-D vectors for the higher 6 bands of a 10-band pyramidal decomposition using a 5/7 tap biorthogonal wavelet lter. Blocks were of size 4 1, 1 4 or 2 2 to follow the detail direction. Given the large starting size of the bands for these super-high de nition images, large super-blocks were de ned (of size 16 16) which could be zeroed out all at once for greater e ciency. Full search unstructured VQs: Full search of an unstructured codebook has been examined by many researchers. Separate VQs were designed by the GLA for each resolution level and preferential direction in  BIB001 BIB002 BIB003 . The rst of these used a recursive biorthogonal wavelet transform, and was basically a comparison of linear and modi ed linear spline lters. The second was a comparison of the GLA and the Kohonen neural network (KNN) or self organizing feature map design algorithm. The KNN method uses a neural clustering network in which the weights, or VQ codewords, between a large number of locally interconnected nodes adaptively self-organize their values in order to re ect the best feature maps, or codebook, representing the input vector patterns. For the subbands of the recursive biorthogonal wavelet transformed image, the unstructured full-search codebook produced by the KNN algorithm was found to yield approximately the same PSNR as one produced by the GLA, using about 15 times less computation during training 8]. The latter two papers used a 5-stage biorthogonal wavelet decomposition, and encoded with scalars in the lowest band, 4-D vectors in medium bands, and 16-D vectors in the high bands. In this work, noise shaping was applied across the subbands by minimizing a weighted MSE where the weights were proportional to the log of the variance of each subband, and the constants of proportionality were chosen experimentally to match human vision. The distortion expression was minimized subject to the total bit allocation constraint with a Lagrange multiplier method. The authors included a comparison of di erent wavelet lters. Another use of visual masking with subband/VQ used a uniform 16-band decomposition with a masking function associated with each coe cient 21], in a manner similar to 131]. The distortion measure was designed to ignore di erences between elements of the two vectors which are smaller than the threshold suggested by a visual masking function. The lowest band was coded with DPCM, and higher subbands were coded with full-search unstructured VQ. The bit allocation was determined by an optimization procedure that minimized a distortion expression subject to constraints on the total bit rate, on the complexity (maximum codebook size), and on the possible vector sizes. Nonseparable lter banks with hexagonal regions of support were applied to hexagonally sampled (or resampled) images in 72]. The resulting subbands had hexagonal shapes, with higher subbands having twice the bandwidth of lower ones. The subbands then had orientation properties which were not limited to vertical and horizontal directions, and the basic structure is believed to be similar to that found in the human visual system. (In section 4.4, an algorithm is described that used diamond-shaped lter banks 54].) Full search unstructured VQs were designed for each subband separately using the GLA. Performance results were not given. Another study that used hexagonal lter banks with unstructured full-search VQ was 161]. Vectors were of size 4 4 for all bands of a 10-band decomposition. Variable sized multiresolution motion estimation was performed. Bit allocation was based on the log of the variance and on the determinant of the covariance matrices, together with a weighting factor that accounted for some simple aspects of a visual model. While not precisely \image" data, the output of supercomputer ocean models, consisting of values of 6 di erent physical variables at each point of a large rectangular 3-D grid, represents an interesting application of wavelet/VQ methods 23]. Using a symmetric biorthogonal wavelet lter on 2-D data 37], four levels of octave-band decomposition resulted in 13 subbands. Full search unstructured VQs were designed for each subband using training data obtained from the rst 91 time steps in the sequence. The optimal codebook sizes and vector dimensions for each combination of total bit rate and total complexity were obtained by a nonlinear optimization procedure as in 22]. The experiment was also repeated with rst-order frame prediction (in which the prediction for the next frame was just the quantized version of the previous frame) which provided 3-5 dB gain over the non-predictive version. Classi ed VQs: An intra-band CVQ was used on the motion compensated frame di erence signal decomposed into four subbands by an 8-tap separable QMF 2]. The 4th band was discarded. The remaining bands were divided into 4 4 vectors. Blocks in subbands 1 and 2 were assigned to one of four classes based on the variance of the coe cients in the block. The lowest variance class was not encoded, and the other three used three di erent VQs. The 3rd subband used only two classes, of which the lower variance one was not coded. The VQs were all full-search unstructured VQs designed by the GLA. In 160], each image in the sequence was decomposed into 7 bands with the Daubechies 4-tap lter. Blocks of size 4 4 were used for the rst pyramid level and 2 2 blocks for the second level. The rst frame of a sequence was used to generate full-search codebooks for each sub-band. In all subsequent frames, each vector was compared to the corresponding vector in the previous frame. The di erence was classi ed by being compared to some small threshold, and side information informed the decoder of the result. If the di erence was less than the threshold, no further action was taken for that vector. Otherwise, the vector was quantized and used to update the cluster mean. If the di erence between the current codewords and the previous ones exceeded a predetermined threshold, new codewords were transmitted to the decoder. With smaller codebooks for the diagonal directions, a PSNR of of 36 dB was achieved at 0.35 bpp for the rst 20 frames of the \Claire" sequence. A combination of classi cation with PTSVQ and multistage VQ was proposed in 78] as being particularly well suited to the design of scalable compression systems. Other VQ structures: An early intra-band method used alphabet and entropy constrained VQ (AECVQ) 126] which was designed as follows. An initial large codebook was designed by the GLA for each subband. Codeword lengths were assigned to codewords based on their probabilities. Successively smaller codebooks were chosen from these same codewords by an iterative process. Each training vector was mapped to the codeword which minimized a weighted combination of MSE and codeword length. Then the centroid of each partition cell was computed, and one of the pre-existing codewords was reassigned to that cell. The reassignment alters both the overall rate and distortion of the code. In a manner similar to PTSVQ, this AECVQ allows one codebook to provide a range of distortion/rate operating points. A 3-level octave-band decomposition yielded 10 subbands. Vectors of size 2 were used in the lowest 4 bands, and 4-D vectors in the others. Bits were allocated among the bands by the \equal-slope" method. For LENA, PSNR was 34.3 dB at 2/3 bpp. One intra-band method used a \linear" VQ codebook, a structure unlike any of the ones described previously 60]. The image was split into seven subbands using separable QMFs (8th order Johnston's lter at the rst stage, and lower orders at the next stage). Lloyd-Max SQ was used on the baseband, and VQ was applied to the other bands in dimensions of 4, 8, or 16. Bits were allocated based on the variances of each subband, which had to be transmitted to the decoder in order to recompute the allocation there. For a vector of length N, the \linear" codebook consists of M concatenated symbols, where M >> N. To nd the appropriate codeword for an input vector, the input vector of length N is rst compared against the rst N symbols of the linear codebook. Then, it is shifted over by one, and compared against symbols 2; 3; : : : ; N + 1: For a given number of possible reproduction vectors, the linear codebook takes up much less space than the full-search unstructured codebook. This method was used with prediction, and with adaptive arithmetic coding applied to the output bit stream. For the LENA test image, the authors claimed transparent quality at 0.2 bpp. In 122], the pyramidal structure of the wavelet decomposition was used to advantage with a hierarchical motion compensation technique, which signi cantly reduced the computation of motion compensation. A 2nd order separable QMF was used to produce seven octave-band subbands. Motion estimation performed on the baseband was re ned using the baseband of the higher level and using the original image. The frame di erence image was encoded using a fast search algorithm known as approximation elimination search 124]. Gain/shape VQ was used with variable-sized rectangular intra-band vectors in 140]. A prediction error image from a motion-compensated image sequence was decomposed into 16 subbands by separable QMFs. Each subband was divided into regions that would get encoded, and ones that would not. For each region to be encoded, the encoder would have to describe to the decoder the location of the region, in addition to encoding the coe cients for the region. Choosing the regions to be square blocks would cost few bits for location information, but would include many irrelevant (low magnitude) coe cients. Arbitrarily shaped regions would consume almost no data rate for the encoding of irrelevant coe cients, but would cost much overhead for location information. The compromise chosen was to allow nine di erent rectangular shapes up to a maximum size of 3 3. For each candidate group of rectangles, a quality measure was based on the visual weighted sum of prediction error energy covered by the selected rectangles. The set was iteratively improved by a greedy relaxation algorithm that could add or remove rows or columns to the rectangles, within the data rate constraint. The chosen rectangles were encoded with a gain/shape VQ of the appropriate dimension designed by the GLA. The storage requirements for the nine VQs could be constrained by mapping all codebooks of smaller dimension into the codebook of the largest dimension.