Vector quantization of image subbands: a survey <s> Vector quantizers with constrained structures <s> In this paper, we present a multiple stage vector quantization technique which allows easy expansion of the original vector quantizer design to operate at higher bit rates for lower distortion. The computation and storage reduction is achieved by the fact that the overall requirements are the sum of the requirements of each stage instead of an exponentially increasing function of the bit rate as in the original one stage design. In the case of Euclidean distance measures such as the log area ratio measure, experimental results show that the quantizer performance is very close to a theoretically predicted asymptotically optimal rate distortion relationship. <s> BIB001 </s> Vector quantization of image subbands: a survey <s> Vector quantizers with constrained structures <s> A hierarchical approach to encoding of images using vector quantization (VQ) is described which allows VQ of large blocks with a tolerable computational complexity and permits progressive image reconstruction at bit rates as low as 0.3 bit/pixel. The technique used, multi-stage hierarchical VQ (MSHVQ), is a successive approximation approach for quantization that is based on recursive decomposition of larger image blocks into smaller subblocks. The encoder of MSHVQ consists of several stages, each of which encodes the quantization error generated from the previous stage. Digital decimation and interpolation techniques are used to convert between different vector dimensions in the higher level stages and to reduce the otherwise highly noticeable blocking effect in the reconstructed image. Variable-rate encoding increases the compression efficiency by allocating greater resolution to high-detail regions and provides a perceptually more consistent image quality throughout all areas of the decoded image. Experimental results show that MSHVQ yields a significantly improved image quality over conventional VQ of equivalent complexity. > <s> BIB002 </s> Vector quantization of image subbands: a survey <s> Vector quantizers with constrained structures <s> 1 Introduction.- 1.1 Signals, Coding, and Compression.- 1.2 Optimality.- 1.3 How to Use this Book.- 1.4 Related Reading.- I Basic Tools.- 2 Random Processes and Linear Systems.- 2.1 Introduction.- 2.2 Probability.- 2.3 Random Variables and Vectors.- 2.4 Random Processes.- 2.5 Expectation.- 2.6 Linear Systems.- 2.7 Stationary and Ergodic Properties.- 2.8 Useful Processes.- 2.9 Problems.- 3 Sampling.- 3.1 Introduction.- 3.2 Periodic Sampling.- 3.3 Noise in Sampling.- 3.4 Practical Sampling Schemes.- 3.5 Sampling Jitter.- 3.6 Multidimensional Sampling.- 3.7 Problems.- 4 Linear Prediction.- 4.1 Introduction.- 4.2 Elementary Estimation Theory.- 4.3 Finite-Memory Linear Prediction.- 4.4 Forward and Backward Prediction.- 4.5 The Levinson-Durbin Algorithm.- 4.6 Linear Predictor Design from Empirical Data.- 4.7 Minimum Delay Property.- 4.8 Predictability and Determinism.- 4.9 Infinite Memory Linear Prediction.- 4.10 Simulation of Random Processes.- 4.11 Problems.- II Scalar Coding.- 5 Scalar Quantization I.- 5.1 Introduction.- 5.2 Structure of a Quantizer.- 5.3 Measuring Quantizer Performance.- 5.4 The Uniform Quantizer.- 5.5 Nonuniform Quantization and Companding.- 5.6 High Resolution: General Case.- 5.7 Problems.- 6 Scalar Quantization II.- 6.1 Introduction.- 6.2 Conditions for Optimality.- 6.3 High Resolution Optimal Companding.- 6.4 Quantizer Design Algorithms.- 6.5 Implementation.- 6.6 Problems.- 7 Predictive Quantization.- 7.1 Introduction.- 7.2 Difference Quantization.- 7.3 Closed-Loop Predictive Quantization.- 7.4 Delta Modulation.- 7.5 Problems.- 8 Bit Allocation and Transform Coding.- 8.1 Introduction.- 8.2 The Problem of Bit Allocation.- 8.3 Optimal Bit Allocation Results.- 8.4 Integer Constrained Allocation Techniques.- 8.5 Transform Coding.- 8.6 Karhunen-Loeve Transform.- 8.7 Performance Gain of Transform Coding.- 8.8 Other Transforms.- 8.9 Sub-band Coding.- 8.10 Problems.- 9 Entropy Coding.- 9.1 Introduction.- 9.2 Variable-Length Scalar Noiseless Coding.- 9.3 Prefix Codes.- 9.4 Huffman Coding.- 9.5 Vector Entropy Coding.- 9.6 Arithmetic Coding.- 9.7 Universal and Adaptive Entropy Coding.- 9.8 Ziv-Lempel Coding.- 9.9 Quantization and Entropy Coding.- 9.10 Problems.- III Vector Coding.- 10 Vector Quantization I.- 10.1 Introduction.- 10.2 Structural Properties and Characterization.- 10.3 Measuring Vector Quantizer Performance.- 10.4 Nearest Neighbor Quantizers.- 10.5 Lattice Vector Quantizers.- 10.6 High Resolution Distortion Approximations.- 10.7 Problems.- 11 Vector Quantization II.- 11.1 Introduction.- 11.2 Optimality Conditions for VQ.- 11.3 Vector Quantizer Design.- 11.4 Design Examples.- 11.5 Problems.- 12 Constrained Vector Quantization.- 12.1 Introduction.- 12.2 Complexity and Storage Limitations.- 12.3 Structurally Constrained VQ.- 12.4 Tree-Structured VQ.- 12.5 Classified VQ.- 12.6 Transform VQ.- 12.7 Product Code Techniques.- 12.8 Partitioned VQ.- 12.9 Mean-Removed VQ.- 12.10 Shape-Gain VQ.- 12.11 Multistage VQ.- 12.12 Constrained Storage VQ.- 12.13 Hierarchical and Multiresolution VQ.- 12.14 Nonlinear Interpolative VQ.- 12.15 Lattice Codebook VQ.- 12.16 Fast Nearest Neighbor Encoding.- 12.17 Problems.- 13 Predictive Vector Quantization.- 13.1 Introduction.- 13.2 Predictive Vector Quantization.- 13.3 Vector Linear Prediction.- 13.4 Predictor Design from Empirical Data.- 13.5 Nonlinear Vector Prediction.- 13.6 Design Examples.- 13.7 Problems.- 14 Finite-State Vector Quantization.- 14.1 Recursive Vector Quantizers.- 14.2 Finite-State Vector Quantizers.- 14.3 Labeled-States and Labeled-Transitions.- 14.4 Encoder/Decoder Design.- 14.5 Next-State Function Design.- 14.6 Design Examples.- 14.7 Problems.- 15 Tree and Trellis Encoding.- 15.1 Delayed Decision Encoder.- 15.2 Tree and Trellis Coding.- 15.3 Decoder Design.- 15.4 Predictive Trellis Encoders.- 15.5 Other Design Techniques.- 15.6 Problems.- 16 Adaptive Vector Quantization.- 16.1 Introduction.- 16.2 Mean Adaptation.- 16.3 Gain-Adaptive Vector Quantization.- 16.4 Switched Codebook Adaptation.- 16.5 Adaptive Bit Allocation.- 16.6 Address VQ.- 16.7 Progressive Code Vector Updating.- 16.8 Adaptive Codebook Generation.- 16.9 Vector Excitation Coding.- 16.10 Problems.- 17 Variable Rate Vector Quantization.- 17.1 Variable Rate Coding.- 17.2 Variable Dimension VQ.- 17.3 Alternative Approaches to Variable Rate VQ.- 17.4 Pruned Tree-Structured VQ.- 17.5 The Generalized BFOS Algorithm.- 17.6 Pruned Tree-Structured VQ.- 17.7 Entropy Coded VQ.- 17.8 Greedy Tree Growing.- 17.9 Design Examples.- 17.10 Bit Allocation Revisited.- 17.11 Design Algorithms.- 17.12 Problems. <s> BIB003 </s> Vector quantization of image subbands: a survey <s> Vector quantizers with constrained structures <s> This paper shows that tree search encoders are ineffective when used to determine the closest code vector in residual quantizer (RQ) alphabets. In particular, the equivalent cell boundaries are poorly chosen and the labelling of equivalent code vectors produced by the decoder and by a tree-structured encoder are inconsistent. This problem does not arise when two-level RQ alphabets are used in trellis coded vector quantizers. Trellis-coded RQs are designed for the memoryless Gaussian, Laplacian, and Gauss-Markov sources at a rate of R=1 bit per sample with encouraging results; a SQNR of 5.92 dB has been achieved on the Gaussian source. > <s> BIB004 </s> Vector quantization of image subbands: a survey <s> Vector quantizers with constrained structures <s> Trellis-coded quantization is generalized to allow a vector reproduction alphabet. Three encoding structures are described, several encoder design rules are presented, and two design algorithms are developed. It is shown that for a stationary ergodic vector source, if the optimized trellis-coded vector quantization reproduction process is jointly stationary and ergodic with the source, then the quantization noise is zero-mean and of a variance equal to the difference between the source variance and the variance of the reproduction sequence. Several examples illustrate the encoder design procedure and performance. > <s> BIB005 </s> Vector quantization of image subbands: a survey <s> Vector quantizers with constrained structures <s> Multistage vector quantization (MSVQ) can achieve very low encoding and storage complexity in comparison to unstructured vector quantization. However, the conventional stage-by-stage design of the codebooks in MSVQ is suboptimal with respect to the overall performance measure. The authors introduce an algorithm for the joint design of the stage codebooks to optimize the overall performance. The performance improvement, although modest, is achieved with no effect on encoding or storage complexity and only a slight increase in design effort. > <s> BIB006 </s> Vector quantization of image subbands: a survey <s> Vector quantizers with constrained structures <s> The use of direct sum codebooks to minimize the memory requirements of vector quantizers is investigated. Assuming arbitrary fixed partitions, necessary conditions for minimum distortion codebooks are derived, first for scalar codebooks, assuming mean-squared error distortion, and then for vector codebooks and a broader class of distortion measures. An iterative procedure is described for designing locally optimal direct sum codebooks. Both optimal and computationally efficient suboptimal encoding schemes are considered. It is shown that although an optimal encoding can be implemented by a sequential encoder, the complexity of implementing optimal stagewise partitions generally exceeds the complexity of an exhaustive search of the direct sum codebook. It is also shown that sequential nearest-neighbor encoders can be extremely inefficient. The M-search method is explored as one method of improving the effectiveness of suboptimal sequential encoders. Representative results for simulated direct sum quantizers are presented. > <s> BIB007 </s> Vector quantization of image subbands: a survey <s> Vector quantizers with constrained structures <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> BIB008
Shannon theory states that VQ can perform arbitrarily close to the theoretical optimal performance for a given rate if the vectors have su ciently large dimension. Unfortunately, unconstrained VQ is limited to fairly small vector dimensions and codebook sizes because of the search complexity. One approach to reduce this complexity is to impose constraints on the codebook. This means that the codewords cannot have arbitrary locations as points in k-dimensional space, but are distributed in a restricted manner that either allows an easier search for the nearest neighbor, or else allows for a search that does not necessarily produce the nearest neighbor. In this section, seven di erent constrained structures are described, all of which have been used as part of subband/VQ schemes. The imposed structural constraints return computation savings, or memory savings, or sometimes both. Due to space constraints, we limit ourselves to describing the functioning of each structure, but references are provided for design algorithms. Lattice vector quantization: A lattice n in R n is composed of all integral combinations of a set of linearly independent vectors which span the space. In one dimension, a lattice quantizer is a uniform quantizer with a (theoretically) in nite number of levels where the entire real line is partitioned into a countable set of equal size intervals of length . In 2-D, a lattice is a set of points with a regular arrangement in the plane: L = ft 2 R 2 : t = Am for all integer pairs m = (m 1 ; m 2 )g where A is a nonsingular (2 2) matrix called the generator matrix of the lattice, and m is an integer vector. This concept generalizes to N dimensions. Conway and Sloane 39, 40] have determined the best known lattices for several dimensions, as well as fast quantizing and decoding algorithms. Some important n-dimensional lattices are the root lattices A n (n 1), D n (n 2), and E n (n = 6; 7; 8), the Barnes-Wall lattice BIB008 in dimension 16, and the Leech lattice 24 in 24 dimensions. These latter give the best sphere packings and coverings in their respective dimensions. Two critically important issues in lattice VQ concern the truncation and scaling of the lattice. The truncation region, also called the region of support, is the subset of the lattice that will actually be coded. For those input points in the \overload region," that is, the region of possible input space which extends beyond the chosen lattice subset, the output distortion (\overload distortion") is not bounded in the same way as it is in the interior of the lattice (\granular distortion"). For each cell in the region of support of a lattice VQ, the reproduction vector is taken to be either the midpoint of the cell or else the centroid of the training vectors lying in that cell. It is desirable to scale the lattice (or equivalently, the source) so as to minimize the total distortion. The choice of support region can also have an important e ect on the encoding speed. Gain/shape VQ: When the distortion measure is squared error, gain/shape VQ provides a simple means of increasing vector size and sequentially coding the vector shape and its gain without requiring any normalization of the input vector. Input vectors are rst encoded into a unit energy shape vector by a maximum correlation search, and then the optimum gain for the given shape is found by a simple scalar quantization. The sequential encoding is optimal in the sense of minimizing mean squared error and the suboptimal product codebook can improve performance by allowing larger dimensions for the shape codebook 130]. Tree-structured VQ (TSVQ): In TSVQ the codeword is selected by a sequence of binary minimum distortion decisions comparing the input vector to stored vector reproductions at each available node. The encoder produces binary symbols to represent its sequence of decisions from the root node of the tree through the terminal node. This binary sequence or pathmap is the nal codeword. Code trees can be balanced with all indices have the same length R, yielding a xed rate code, or unbalanced with indices of di ering length, yielding a variable rate code. Compared with a fullsearch unstructured VQ, the search complexity of a balanced tree is linear in the bit rate instead of exponential but at the cost of a roughly doubled memory size. For unbalanced trees the search complexity remains linear in the average bit rate, but the memory can be considerably larger unless constrained 129]. Multistage vector quantization: Multistage VQ divides the encoding task into several stages BIB001 BIB002 BIB003 BIB006 . The rst stage performs a relatively crude encoding of the input vector using a small codebook. Then a second stage quantizer operates on the error vector between the original vector and the quantized rst stage output. The quantized error vector provides a re nement to the rst approximation. At the decoder, the reproduction vectors produced by the rst and second stages will be added together. Additional stages of quantizers can provide further re nements. Unlike full-search VQ, whose encoding complexity and memory requirements increase exponentially with the dimension-rate product, in multistage VQ the increase is only linear. This has particular utility in subband coding, since either the rate or the dimension can be made large, which allows it to respond to the occasional need for a locally high bit rate in subband coding. Multistage VQ is sometimes referred to as residual VQ, but those words better apply to a variation on multistage VQ which e ectively uses the same codebook, but allows a nongreedy search such as a full search or an M-algorithm. The codebook corresponding to a multistage VQ can be viewed as the collection of all possible reproductions that can be constructed by adding one codeword from each of the stages. This codebook can be viewed as a direct sum codebook because it corresponds to all possible sums of one reproduction codeword per layer, or as a product codebook because the Cartesian product of the indices provide a composite index which can be used to produce the nal reproduction. If this codebook is searched in a greedy fashion one stage at a time, the resulting code is naturally progressive, but it need not nd the best of all possible reproduction words in the direct sum codebook. Allowing the encoder to look at the entire reproduction will lead to better performance, but the search complexity grows accordingly. Design algorithms speci c to this encoder structure can then be used  BIB004 BIB007 . Predictive vector quantization (PVQ): PVQ is a straightforward vector extension of tradi-tional scalar predictive quantization (DPCM). The encoder makes a prediction of the incoming vector based on previously encoded vectors. The di erence between the actual input vector and its prediction is called the residual vector. This residual is vector quantized. Because the encoder only uses the previous outputs in making its prediction, the decoder is able to make the same prediction. After dequantizing the residual vector, the decoder adds the prediction to it to form the reproduction vector. The prediction is often a simple linear predictor that takes a weighted average of nearby previously encoded coe cients. Classi ed vector quantization (CVQ): The input x n is subjected to a classi er which generates an index i n , an integer from 1 to m, which identi es which sub-codebook C i to search for the nearest neighbor 123]. The codeword corresponding to x n thus consists of two parts: an index i n specifying the codebook, and an index u n specifying the selected word in that codebook. The rst part of the codeword is typically referred to as side information, although it can be longer or shorter than the second part. The classi er can be based on texture properties, edge directions, features of diagnostic or scienti c importance or irrelevance, perceptual masking, or a variety of other criteria. Finite-state vector quantization (FSVQ): Like a classi ed VQ, a nite-state VQ has multiple codebooks, and the next vector to be encoded is referred to the appropriate codebook. Unlike CVQ, however, no side information is sent to the decoder to inform it of which codebook to use. That information is inferred using the next-state rule. The next-state rule uses various information available to the decoder in order to decide which codebook to use. For instance, reconstructed vectors from nearby locations, which codebook was used the last time (corresponding to the previous state of the system) and which codeword was chosen from that last codebook, are all pieces of information available to both the decoder and the encoder that can be used to decide which codebook to use for the current vector (corresponding to the current state of the system). The decoder and encoder both know the next-state function. Assuming that the decoder and encoder start with the same codebook and that there is no channel noise, the decoder will always be able to track which codebook the encoder is using next, since the next-state function employs only information available to both parties 9, 88]. Trellis coded vector quantization (TCVQ): Trellis coded quantization (TCQ) and TCVQ can be viewed as an extension of the FSVQ approach with a lookahead search. They are source coding analogs to the Ungerboeck coded modulation approach 144] to channel coding (error control coding) on narrowband channels. The TCVQ encoder can be thought of as having a supercodebook which is partitioned into a collection of subcodebooks. At any time the encoder may have only a few of the subcodebooks available. A popular choice is to have the supercodebook be a lattice and the subcodebooks be sublattices. The encoder has a collection of possible states and allowed transitions between those states. Each of the transitions between states corresponds to one of the subcodebooks. As a form of FSVQ, this system's encoder in a given state could view a single source vector, look at all of the available subcodebooks, and nd the nearest neighbor. The encoder could communicate this word to the decoder with a two-part binary vector. The rst part tells the encoder's next state by sending an index of which allowable transition is being taken. The second part indexes which of the possible codewords in that particular codebook was chosen. This implementation, however, su ers the shortcoming of allowing a good short term choice to lead to a bad state which could in turn lead to bad long term behavior. Hence the TCVQ is allowed to look ahead to nd the best available sequence of paths for a sequence of input vectors. This ensures better long run behavior at the expense of added coding delay. A variety of design algorithms for the supercodebook and subcodebooks based on lattices and on clustering have been considered BIB005 BIB008 possible input pairs provides a nearest neighbor mapping from all possible inputs to all possible reproductions. Furthermore, this stage achieves a compression of 2:1 since the total of 16 bits for the original vector (2-D vector with 8 bits for each coordinate) is now reduced to 8. The next stage takes the reproduction pairs and combines them two at a time to form two 4-D vectors. These are each quantized with a (possibly distinct) 8-bit codebook, where a table lookup again replaces the pre-computed nearest neighbor mapping. The process can be repeated once more. The overall operation results in a compressed vector at 1 bit per symbol with no computation. The HVQ has the nice property of being easily scalable, as one can put out indexes at rates of 8, 4, 2, or 1 bit per symbol. Further stages will yield further compression. The overall operation is depicted in Figure 6 . The obvious cost of this method is memory, but this can be an acceptable price to avoid numerical computation. The method can be applied to an image by sequentially compressing rows and then columns. Hierarchical VQ did not have much impact in its original form because it was essentially a means of implementing simple VQ on raw data, e.g., speech samples or image pixels, and such simple VQ, even if full-search, does not usually perform well in comparison with transform or subband codes. However, HVQ can perform both subband coding and VQ together by table lookup, resulting in a fast software-only implementation of subband/VQ image coding systems 151].