Vector quantization of image subbands: a survey <s> Bit allocation <s> An optimal bit allocation algorithm is presented that is suitable for all practical situations. Each source to be coded is assumed to have its own set of admissible quantizers (which can be either scalar or vector quantizers) which do not need to have integer bit rates. The distortion versus rate characteristic of each quantizer set may have an arbitrary shape. The algorithm is very simple in structure and can be applied to any practical coding scheme (such as a subband coder) that needs dynamic bit allocation. > <s> BIB001 </s> Vector quantization of image subbands: a survey <s> Bit allocation <s> An algorithm introduced by L. Breiman et al. (1984) in the context of classification and regression trees is reinterpreted and extended to cover a variety of applications in source coding and modeling in which trees are involved. These include variable-rate and minimum-entropy tree-structured vector quantization, minimum expected cost decision trees, variable-order Markov modeling, optimum bit allocation, and computer graphics and image processing using quadtrees. A concentration on the first of these and a detailed analysis of variable-rate tree-structured vector quantization are provided. It is found that variable-rate tree-structured vector quantization outperforms not only the fixed-rate variety but also full-search vector quantization. The successive approximation character of variable-rate tree-structured vector quantization permits it to degrade gracefully if the rate is reduced at the encoder. This has applications to the problem of buffer overflow. > <s> BIB002 </s> Vector quantization of image subbands: a survey <s> Bit allocation <s> A low bit rate adaptive video coding technique is proposed. The redundancy within adjacent video frames is exploited by motion-compensated interframe prediction, and the motion-compensated frame difference (MCFD) signal is decomposed by using a quadrature mirror filter (QMF) structure. The subband signals are vector quantized adaptively. The MCFD signals are low correlated, hence transform coding techniques are not very suitable for this kind of signal source. At 0.25-0.3 bits/pixel range, 38-40-dB peak-to-peak signal-to-noise ratio is achieved with the proposed scheme for four monochrome test sequences used: cindy, mono, duo, and quartet. The visual quality of the encoded test sequences is good, almost indistinguishable from the originals. The proposed technique outperforms the adaptive transform coding and adaptive vector quantization techniques for the tested sequences. > <s> BIB003 </s> Vector quantization of image subbands: a survey <s> Bit allocation <s> A technique for directly designing a variable-rate tree-structured vector quantizer by growing the tree one node at a time rather than one layer at time is presented. The technique is a natural extension of a tree growing method for decision trees. When the tree is pruned with a generalized algorithm for optimally pruning trees, improvement is measured in the signal-to-noise ratio at high rates over pruning a fixed-rate tree-structured vector quantizer of the same initial rate. The growing algorithm can be interpreted as a constrained inverse of the pruning algorithm. > <s> BIB004 </s> Vector quantization of image subbands: a survey <s> Bit allocation <s> P.H. Westerink et al. (1988) developed an optimal bit allocation algorithm that is simplified when all operational distortion-rate functions (which are referred to as quantizer functions) are convex. This algorithm is restated using the generalized Breiman, Friedman, Olshen, and Stone (BFOS) algorithm (a recently developed technique for variable rate vector quantizer design) for both cases of convex and nonconvex quantizer functions (QFs), and its complexity is analyzed. The use of the generalized BFOS algorithm for optimal bit allocation is analysed. It is shown that if each source has a convex quantizer function then the complexity of the algorithm is low. > <s> BIB005 </s> Vector quantization of image subbands: a survey <s> Bit allocation <s> Vector quantization for entropy coding of image subbands is investigated. Rate distortion curves are computed with mean square error as a distortion criterion. The authors show that full-search entropy-constrained vector quantization of image subbands results in the best performance, but is computationally expensive. Lattice quantizers yield a coding efficiency almost indistinguishable from optimum full-search entropy-constrained vector quantization. Orthogonal lattice quantizers were found to perform almost as well as lattice quantizers derived from dense sphere packings. An optimum bit allocation rule based on a Lagrange multiplier formulation is applied to subband coding. Coding results are shown for a still image. <s> BIB006
Bit allocation is the problem of assigning bit rates to a number of sources that are to be encoded. In the case of subband coding systems, the di erent sources may be the di erent subbands, but they are not necessarily. The goal of the allocation is typically to minimize the overall distortion of the coder subject to constraints such as a maximum overall bit rate, where the overall distortion can be de ned in di erent ways. If the quantization is to be scalar without subsequent entropy coding, then there is the constraint that the assignment must be integer. There are a variety of other possible constraints that will be discussed later. It is well known from experience that the low frequency subbands have higher variance than the high frequency subbands, and this higher variance means that they have \more information" and ought to be allocated more bits. How many more bits? A small number of researchers decided upon arbitrary numbers. For example, a low frequency band might get 2 bits per pixel (bpp), and a higher frequency band only 1 bpp, with perhaps some highest frequency bands being discarded altogether (0 bpp). Other researchers allocated bits to be proportional to the logarithm of the variance of each subband. In such a case, typically the variances would need to be transmitted to the decoder in order to recompute the allocation there. The most common bit allocation method is one we will refer to as the \equal-slope" method. It is applicable to both scalar and vector quantizers. The idea is based on what is known in economics as \Pareto Optimality." We assume that a variety of quantizers have been designed for each subband. For each subband, we can in turn apply each of the quantizers which were designed for it, and compute the resulting distortion and bit rate. These distortion/rate points can be plotted in the (D; R) plane, and the lower convex hull of the set can be extracted for each band. We call these the distortion/rate curves. The \equal-slope" method, which was invented and re-invented in di erent contexts and from di erent viewpoints BIB001  BIB002 BIB004 BIB005 BIB006 indicates that the overall system should operate by nding a point of equal slope along the D(R) curve for each band. For the given D(R) curves related to those xed VQs, this bit allocation strategy was shown to be optimal for an orthogonal decomposition, in the sense of minimizing the mean-squared error (MSE) of the reconstructed image. The intuitive explanation for this \equal-slope" method is as follows: Suppose you are operating an encoder with a variety of quantizers available to encode two sources. The variety of quantizers, which operate at di erent rates, yield a spread of possible distortions and rates for each source. If the channel allows you to increase your overall rate slightly, which source should you choose to increase? One source may be encoded at a at part of its D(R) curve, so an increase in the rate will cause only a trivial decrease in the distortion. But another source may be encoded on a steep part of its D(R) curve, so that an increase causes the distortion to drop sharply. One would choose to add bits to that source until it too reaches an equally at part of its D(R) curve, at which point adding an additional bit to either source would produce the same drop in distortion. A variety of further re nements to this \equal-slope" bit allocation scheme have been tried, mostly involving attempts to weight the distortion so as to re ect human visual sensitivity. The equal-slope intuition for determining bit allocation indeed re ects asymptotic results from quantization theory, as does the older method of allocating bits proportional to log variances. It is worthwhile to describe these results brie y to provide an appreciation for their relevance and limitations. BIB003 ] is the average distortion of the kth quantizer, then the goal is to minimize the total average distortion P k D k subject to an overall rate constraint P k R k R. This problem can be easily solved by converting this constrained minimization to an unconstrained minimization, using a Lagrange multiplier. The unconstrained problem is to minimize P k D k (R k ) + P k R k for some 0. This can be shown directly, or by using variational principles. In the latter case, we take derivatives with respect to R k and equate to zero: D 0 k (R k ) + = 0 for each k. This is precisely the \equal slope" method. Each R k is chosen to satisfy D 0 k (R k ) = ? . In the case where D k (R k ) = ce ?2R k , we have ?2ce ?2R = ? , or R k = (1=2) log(2c= ). This is the \rule of thumb" that the bit allocation is an a ne function of the log of the variance, c. If all of the random variables are independent and if they are such that the standardized random variables (Y k ? E(Y k ))= Y k are identically distributed, then the optimal bit allocation allocates bits to Q k proportional to log 2 Y k plus some constant in the case where no entropy coding is used. The same conclusion follows for the case with entropy coding if the random variables are also assumed to be Gaussian. If the random variables do not share the same standardized distribution, then additional terms must be included. Lastly, if one has correlated Y k , then these results do not hold. If, however, the variables are jointly Gaussian and one rst applies a Karhunen-Loeve transform, then one produces uncorrelated variables which are also independent and to which one can apply these asymptotic approximations and draw similar conclusions to the e ect that the optimal rate allocations for both approaches are proportional to the log variance. The key points of the preceding discussion for our case of decomposing signals by a transform (such as the wavelet transform) can now be summarized: To have a rigorous basis for the common rule of thumb that bit allocation should be made proportional to the logarithms of the coe cient variances, the following assumptions are required: The rate is asymptotically large (or the distortion is asymptotically small). The original data being transformed are jointly Gaussian. The transform is the Karhunen-Loeve transform. These assumptions are often not valid in practice. The most interesting bit rates for many applications are not asymptotically large, image intensities are not well modeled by Gaussian, and wavelet transforms can at best only approximate the Karhunen-Loeve transform. In particular, wavelet transforms can render data approximately uncorrelated, but not independent. Nonetheless, this approach remains common.