Vector quantization of image subbands: a survey <s> Crossband vector methods <s> A new subband video coding technique is introduced which utilizes several memoryless vector quantizing (VQ) schemes for encoding the various layers. A set of quadrature mirror filter banks was applied to the motion compensated frame differences (MCFDs) of the moving sequences to produce seven nonuniform bands. The upper bands displayed a significant amount of information at edge locations, these being the positions where the baseband of each layer was observed to have a similar behavior. Therefore, an edge-detecting operator, e.g., Laplacian or a Gaussian, was incorporated into the video compression model to extract the perceptually important locations of the upper bands from their correspondingly encoded baseband, thus eliminating the need for transmission of their addresses. Promising results were obtained which are suitable for low-bit-rate video applications where videophone and videoconferencing systems may be realized. > <s> BIB001 </s> Vector quantization of image subbands: a survey <s> Crossband vector methods <s> The authors discuss a vector quantization strategy which jointly optimizes distortion errors and complexity costs. A maximum entropy estimation of the vector quantization cost function yields an optimal codebook size, the reference vectors and the assignment frequencies. They compare different complexity measures for the design of image compression algorithms which quantize wavelet decomposed images. An online version of complexity optimized vector quantization is implemented by an artificial neural network with winner-take-all connectivity. Their approach establishes a unifying framework for different quantization methods like K-means clustering and its fuzzy version, entropy constrained vector quantization or self-organizing topological maps and competitive neural networks. > <s> BIB002 </s> Vector quantization of image subbands: a survey <s> Crossband vector methods <s> Vector quantization is a data compression method by which a set of data points is encoded by a reduced set of reference vectors: the codebook. A vector quantization strategy is discussed that jointly optimizes distortion errors and the codebook complexity, thereby determining the size of the codebook. A maximum entropy estimation of the cost function yields an optimal number of reference vectors, their positions, and their assignment probabilities. The dependence of the codebook density on the data density for different complexity functions is investigated in the limit of asymptotic quantization levels. How different complexity measures influence the efficiency of vector quantizers is studied for the task of image compression. The wavelet coefficients of gray-level images are quantized, and the reconstruction error is measured. The approach establishes a unifying framework for different quantization methods like K-means clustering and its fuzzy version, entropy constrained vector quantization or topological feature maps, and competitive neural networks. > <s> BIB003 </s> Vector quantization of image subbands: a survey <s> Crossband vector methods <s> A key issue in subband coding is the efficient compression of the less informative but perceptually important upper frequency bands of the decomposed image. A new approach capable of effectively encoding the upper-bands is described. An intra-band vector quantization (VQ) technique is employed for compression of the base-band while the upper frequency bands are encoded by a hierarchical inter-band VQ method. The proposed inter-band vector quantization scheme exploits the redundancies that exist between pels of significant perceptual importance across the upper frequency bands of the same resolution. Such pels are observed to be at or around the edge-locations, displaying similar discontinuity behavior across the subbands. Therefore, an edge-detector is applied on the reconstructed base-band to extract the edge locations, and as a result no overhead information is transmitted to identify the position of these pels in the upper-bands. Furthermore, a residual subband, being the difference between the original base-band of each layer and its encoded version, is incorporated in the proposed inter-band VQ model. Thus, the proposed interband VQ scheme is simply the vector quantization of pixels across the upper-bands together with their corresponding residual band. Compression results are presented for both digital images and video sequences which demonstrate high subjective visual qualities. > <s> BIB004
Vectors that are put in to the VQ can be formed of coe cients from di erent subbands. We refer to these as crossband vectors. In a uniform subband decomposition, the crossband vector typically consists of one coe cient from each subband, as shown in Figure 7 ; in the example shown, the vector dimension is 16. Sometimes the lowest band will be coded separately, and the crossband vector formed from the other bands. Sometimes, too, the highest bands will be excluded from the vector, and not coded at all. In an octave-band decomposition, a crossband vector can be formed out of X i and its descendants, as shown in Figure 8 . We refer to this as a \same orientation" crossband vector. In the example shown, the vector dimension is 21. Clearly, the dimension of the \same orientation" crossband vector can become large very fast. The octave-band decomposition can also lead to a \same level" crossband vector, as shown in Figure 9 ; here the dimension is 3. For both the \same orientation" and \same level" crossband vectors, there is not a natural vector to include the coe cients from the low band. These coe cients could be tacked on individually to any one of the crossband vectors, which would increase the dimension by one. However, recognizing that the low band has very di erent characteristics, both perceptually and statistically, from the other bands, most subband/VQ methods which employ a crossband vector-forming strategy choose to code the low band separately. With all three types of crossband vectors, the idea of a weighted distortion measure which accords di erent weights to di erent components is appealing, since the coe cients of the vector are not all of the same type. This is true both for the \same orientation" vectors, whose components come from di erent levels of the hierarchy, and for the other two types, for which the components come from the same level. In either case, the components have di erent statistics, and di erent perceptual importance. For instance, the diagonal orientation is considered to be of less perceptual importance than the horizontal or vertical. In 29], separable 32-tap QMFs were used to split the image into 16 subbands. The coe cients were encoded as 16-D crossband vectors by nite-state VQ. The master codebook had 256 codewords determined by the GLA. For each input vector x, let u and l denote the input vectors whose coe cients lie directly above and directly to the left, respectively, of the coe cients which compose x. For each x, the state codebook is composed of the 16 codewords m from the master codebook which have the smallest value of distortion(m; u) + distortion(m; l), where the distortion is MSE. Since the decoder has already decoded u and l before it receives x, it is able to determine the same state codebook as the encoder. The input vector x is encoded by nding the nearest neighbor in this state codebook. If the distortion produced by this nearest neighbor is greater than some threshold, then the nearest neighbor from the master codebook is chosen instead, and side information must be sent to the decoder to inform it of this change. This limits the maximum distortion, and can prevent the nite-state machine from becoming derailed. The method provided PSNRs of 30{34 dB for images Peppers, Airplane, and Zelda at 0.3 bpp. \Same-orientation" crossband vectors from octave-band subbands: Huh, et al., used classi ed VQ on the coe cients resulting from a 3-stage wavelet decomposition using Johnston's near-PR lters 75]. For purposes of classi cation, the 21-D vectors as shown in Figure 8 were further grouped together. Those vectors corresponding to the same spatial location but di erent orientations in the original image, including the single coe cient from the lowest band, formed a 64-D group (21 + 21 + 21 + 1 = 64). These 8 8 blocks were categorized into 4 classes depending on the directional activity: horizontally active, vertically active, diagonally active, inactive. This class information was sent separately to the decoder. Depending on the class, certain of the 64 coe cients were discarded altogether, with the remaining ones divided into between 3 and 7 smaller subvectors of dimensions ranging from 1 to 11. Only one subvector of one class actually retained coe cients that cross bands. So this method is essentially one that used the inter-band correlation for purposes of classi cation, but did not code the coe cients as crossband vectors. The algorithm produced PSNRs of 34.1, 32.3 and 30.2 for LENA at 0.5, 0.33, and 0.21 bpp respectively. The same research group tried this classi cation method with 2-channel conjugate VQ 76,  . Conjugate VQ is a structure that can save on both memory and computational complexity. Where a regular VQ might employ a single codebook with N 2 vectors, a two-channel conjugate VQ allows N 2 possible reproduction vectors using 2 codebooks, A and B, with N vectors each. Each reproduction vector is made from some combination of a codeword from A and a codeword from B. As before, coe cients from the 10 bands were grouped into 8 8 blocks for classi cation into the four classes. Based on the class, the blocks were divided into smaller subvectors for encoding with 2-channel conjugate VQ. A PSNR of 31.8 dB was obtained at 0.32 bpp for the LENA test image. Vectors of dimension 64 were also examined in 152], where the 21-D vectors as shown in Figure 8 were grouped together from di erent orientations, including the single coe cient from the lowest band. The method used non-linear interpolative VQ 66] in which a high-dimensional vector is encoded using a size-reduced feature vector, and the decoder reconstructs the high-dimensional vector using an optimal non-linear interpolation. A variable-dimension same-orientation VQ scheme was proposed in 10] for use in intra-frame coding situations of high motion and scene changes. The decomposition was into 10 bands using a biorthogonal 5/7-tap wavelet basis. Starting with a 21-D same-orientation vector as shown in 8, the coe cients were \merged" in a bottom-up quadtree fashion as described in 11], in which the decision to merge depended on whether any of the di erences between neighboring coe cients exceeded a predetermined threshold. The resulting vector could have dimension 5, 9, 13, 17, or 21, and was encoded with a weighted distortion measure using a codebook of the appropriate dimension which had been designed by the GLA. In 106], a 3-level octave-band decomposition from rectangular separable Gabor-like wavelets was used with 21-D same-orientation crossband vectors. Those vectors with all components below a speci ed threshold were designated zerotrees and not coded. The remaining coe cients were reorganized into 5-D inter-band vectors (one coe cient from the coarser level and four from the next) and 16-D intra-band vectors (4 4 blocks from the nest bands). The 5-D inter-band vectors were encoded using a weighted distortion measure, and the intra-band vectors were encoded using an unweighted full-search VQ. The method was extended to color images by separately coding luminance and chrominance coe cients, discarding lower subbands of the chrominance components, using a weighted quadratic distortion measure based on perceptual sensitivity, and by using a classi ed VQ 107] . Two classi cation strategies were adopted; one based on subbands with common frequency orientation and the other on separating edge, texture, and homogeneous regions. A PSNR on the luminance component of 28.19 dB was achieved at 0.14 bpp, but it should be kept in mind that code optimization was with respect to a weighted distortion and not the mean squared error inherent in SNR. \Same-level" crossband vectors from octave-band subbands: Vectors were formed as in Figure 9 in 109]. A 24-tap QMF was used to decompose images into seven subbands. The baseband was coded using predicted mean/residual VQ on 2 2 blocks. The previously encoded blocks were used to make a prediction of the mean value of the next block to be encoded. This predicted mean value was removed from the block to be encoded. The decoder was able to make the same prediction using its available encoded blocks. The prediction was added back to the decoded vector to form the reconstruction. A truncated Laplacian of Gaussian operator, r 2 G, was applied by both the encoder and the decoder to the reconstructed baseband image. The zero-crossings of this ltered sub-image indicated the positions of the edges. Only those coe cients from the medium and high bands which correspond to edge locations were coded. In one scheme, a 3-D vector was formed from the 3 medium bands by taking the corresponding pixels from the three di erent orientations. In another scheme, the residual baseband sub-image was formed by taking the di erence between the actual and the reconstructed baseband. Then, a 4-D vector was formed by adding the corresponding coe cient from this residual image to the 3-D vector of the previous scheme. In either case, the medium bands were dequantized and inverse transformed, to obtain a baseband at the next level. The edge detector was applied to the new baseband in order to determine the edge positions to be encoded in the high bands. The same method was applied to image sequences, where block matching was used to estimate block motion, and the subband lters were then applied to the motion compensated frame di erence image BIB004 BIB001 . Results for LENA were a PSNR of 34.1 at a bit rate between 0.69 and 0.50 bpp, depending upon whether the bit rate was calculated as the xed rate of a constant wordlength code for the codebook addresses, or as the entropy of a variable wordlength code. In a series of two articles, Buhmann and K uhnel developed the notion of VQ with complexity costs, which they referred to as entropy optimized VQ, and demonstrated its use for coding wavelet coe cients BIB002 BIB003 . The basic idea is a variation on ECVQ but the formulation is more general and the speci c algorithm di erent. The authors noted that the traditional VQ design strategy, as followed by the GLA, relies exclusively on the distortion errors for placing the reproduction vectors. The number of reproduction vectors is assumed to be chosen in advance. By incorporating into the cost function an application-dependent complexity measure, the optimization of distortion and the intrinsic constraints on the codebook can be allowed to a ect each other in some appropriate fashion. The test images were decomposed with a separable QMF lter to yield 7 subbands. The lowest band was scalar quantized. The remaining bands were formed into 3-D vectors at each level, as shown in Figure 9 . GLA clustering was compared against entropy optimized VQ, with the latter resulting in signi cantly higher PSNRs on test images. The GLA method produced considerably smaller codebooks than the entropy optimized VQ. The latter was able to place reproduction vectors in sparsely populated areas, preserving psychovisually important image features like edges more faithfully. In the experiments, the two methods were required to have the same output entropy, rather than the same output bit rate (in which case ECVQ may have been the more appropriate benchmark). A type of \same-level" crossband vector was used in 153], where the image was decomposed into even and odd symmetric size and orientation-selective band-pass lter outputs. At each level of resolution, an 8-D vector space resulted from a polar representation of local amplitude and local phase from 4 orientation-selective analytic band-pass lters. This hyper-space was partitioned in a feature-speci c way, taking into account properties of the human visual system. The small hypercube at the origin was assumed to correspond to an irrelevance zone conforming to the threshold properties of human vision. All vectors in that region could be quantized to the origin. The regions around the hypersphere coordinate axes represented intrinsically 1-D image features, as only one orientation lter was giving a strong response. Regions between two axes were di erentiated into those corresponding to 1-D image features whose orientations did not exactly coincide with the preferred axis of an orientation lter, and those which corresponded to certain intrinsically 2-D features such as discontinuities. These regions needed to be quantized relatively nely, and a saturation function in accordance with masking e ects was applied. Vectors in the residual space, arising from intrinsically 2-D image features such as curved lines and textural features that activate more than two orientation lters, could be quantized more coarsely. The quantization step thus involved only simple decisions and nonlinear transformations followed by uniform quantization, with no codebook search or distance calculations. The VQ yielded an uneven probability density function for the vectors, and an ideal entropy coder was assumed. Satisfactory subjective image quality was found at 0.78 bpp for the 256 256 LENA test image. A crossband gain/shape VQ used for a 64-band decomposition was brie y described in 30], although this paper is primarily concerned with elaborating an error-resilient technique for e ciently encoding positional information. In two papers, SQ was used on wavelet coe cients, and crossband vectors were used to design subsequent entropy coders 111, 100]. In 111], the output of a 6-band quasi-perfect reconstruction lter was quantized with SQ followed by arithmetic coding, and a crossband VQ was used to provide the arithmetic coder with a probability density function. In 100], SQ was applied to the coe cients of a 10-band pyramidal decomposition where the FIR lter banks were allowed to be di erent at each level of the decomposition. The images decomposed were motion-compensated progressive frames derived from a novel adaptive block matching algorithm. The inter-band information was used for designing a universal variable length entropy coder for vectors which were composed of the SQ output values. Wavelet hierarchical VQ (WHVQ): Vishwanath and Chou 151] realized that the subband decomposition and VQ could be accomplished together by table lookups using the HVQ structure. This provides a number of bene ts: natural scalability, ease of incorporation of perceptual considerations into the code design, and a very fast software implementation that requires only table lookups and no computation for the decomposition, quantization, and reconstruction. There is signi cant computation o line when the tables are lled since, as with ordinary HVQ, the tables simply capture the result of a complicated mapping from one discrete space into another. The system uses separable subband lters and operates alternately on rows and columns. Each stage in the hierarchical coder does one row or one column decomposition along with a vector quantization. In this way quantization is done across the subbands of the wavelet transform. The system is best suited to short lters to concentrate their e ects within the vector size used by the VQ. As with ordinary HVQ, each stage will combine pairs of indices to form individual indices, providing a 2:1 compression. Unlike ordinary HVQ, these tables do not simply implement the result of nearest neighbor searches, they also include ltering and downsampling prior to the quantization. Each stage consists of two steps. The rst is simply an HVQ on the preceding stage, which will be raw pixels in the rst stage and quantized wavelet coe cients thereafter. The rst step, providing 2:1 compression, successively maps nonoverlapping pairs of k-dimensional blocks produced by the previous stage into a single quantized block corresponding to a 2k-dimensional vector. The second step maps two of the rst-step output blocks into a stage-2 output block, but does so using overlapping blocks because the wavelet decomposition requires the larger window. This step is designed by clustering the reproduction vectors of the previous stage in a sliding-block manner, each time shifting the window by k. Following each stage, downsampling and necessary delays are easily done without computation. Each stage operates in only one dimension, so that rows and columns are handled by alternating stages. The overall e ect of a single stage is to produce wavelet coe cients and compress by 2:1. The system is inherently xed rate and no entropy constrained versions exist for optimizing for entropy coding. Using the 