Vector quantization of image subbands: a survey <s> Scalar quantization <s> This paper discusses the problem of the minimization of the distortion of a signal by a quantizer when the number of output levels of the quantizer is fixed. The distortion is defined as the expected value of some function of the error between the input and the output of the quantizer. Equations are derived for the parameters of a quantizer with minimum distortion. The equations are not soluble without recourse to numerical methods, so an algorithm is developed to simplify their numerical solution. The case of an input signal with normally distributed amplitude and an expected squared error distortion measure is explicitly computed and values of the optimum quantizer parameters are tabulated. The optimization of a quantizer subject to the restriction that both input and output levels be equally spaced is also treated, and appropriate parameters are tabulated for the same case as above. <s> BIB001 </s> Vector quantization of image subbands: a survey <s> Scalar quantization <s> The authors present a 16-band subband coder arranged as four equal-width subbands in each dimension, It uses an empirically derived perceptual masking model, to set noise-level targets not only for each subband but also for each pixel in a given subband. The noise-level target is used to set the quantization levels in a DPCM (differential pulse code modulation) quantizer. The output from the DPCM quantizer is then encoded, using an entropy-based coding scheme, in either 1*1, 1*2, or 2*2 pixel blocks. The type of encoding depends on the statistics in each 4*4 subblock of a particular subband. One set of codebooks, consisting of less than 100000 entries, is used for all images, and the codebook subset used for any given image is dependent on the distribution of the quantizer outputs for that image. A block elimination algorithm takes advantage of the peaky spatial energy distribution of subbands to avoid using bits for quiescent parts of a given subband. Using this system, high-quality output is obtainable at bit rates from 0.1 to 0.9 bits/pixel, and nearly transparent quality requires 0.3 to 1.5 bits/pixel. > <s> BIB002 </s> Vector quantization of image subbands: a survey <s> Scalar quantization <s> Subband Coding of images which can be seen as an extension of orthogonal transformations has been introduced by Woods and O''Neil [8]. In [8] the subbands are further encoded by DPCM. In this study it is proposed to use subband coding as a stand alone coding technique. The emphasis is put on the question of subband quantization. A methology is proposed where the quantization step of the subbands is taken so as to minimize a quantization noise power weighted by a sensitivity function of the eye.© (1990) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only. <s> BIB003 </s> Vector quantization of image subbands: a survey <s> Scalar quantization <s> A novel theory is introduced for analyzing image compression methods that are based on compression of wavelet decompositions. This theory precisely relates (a) the rate of decay in the error between the original image and the compressed image as the size of the compressed image representation increases (i.e., as the amount of compression decreases) to (b) the smoothness of the image in certain smoothness classes called Besov spaces. Within this theory, the error incurred by the quantization of wavelet transform coefficients is explained. Several compression algorithms based on piecewise constant approximations are analyzed in some detail. It is shown that, if pictures can be characterized by their membership in the smoothness classes considered, then wavelet-based methods are near-optimal within a larger class of stable transform-based, nonlinear methods of image compression. Based on previous experimental research it is argued that in most instances the error incurred in image compression should be measured in the integral sense instead of the mean-square sense. > <s> BIB004 </s> Vector quantization of image subbands: a survey <s> Scalar quantization <s> Abstract An orthogonal basis of L2 which is also an unconditional basis of a functional space F is an optimal basis for compressing, estimating, and recovering functions in F . Simple thresholding operations, applied in the unconditional basis, work essentially better for compressing, estimating, and recovering than they do in any other orthogonal basis. In fact, simple thresholding in an unconditional basis works essentially better for recovery and estimation than other methods, period. (Performance is measured in an asymptotic minimax sense.) As an application, we formalize and prove Mallat′s Heuristic, which says that wavelet bases are optimal for representing functions containing singularities, when there may be an arbitrary number of singularities, arbitrarily distributed. <s> BIB005
Quantization is the mapping of a large set of possible inputs into a smaller set of possible outputs. In scalar quantization (SQ), the inputs are individual numbers. Scalar quantization includes such operations as \rounding to the nearest integer." The possible outputs, in this case the integers, are called quantization levels or reproduction levels or reconstruction levels. Integers are evenly spaced, so this is an example of uniform quantization. In general, the quantization levels do not have to be integers, nor evenly spaced. The spacing between the reproduction levels is often called the bin width. To specify a scalar quantizer, one needs the set of possible reproduction levels and a rule for mapping input scalars to reproduction levels. In the simplest application of SQ to subband coe cients, one simply applies a uniform quantizer with bin width to all coe cients, i.e., the real line is carved up into disjoint intervals of length  BIB004 . A coe cient lying in a particular interval is represented by the midpoint (centroid with respect to Lebesgue measure) of the interval. The intervals are numbered. The coe cient is mapped into an index labeling the interval in which it lies, and these indices are then coded using an entropy code. As gets bigger the interval size grows, the distortion increases, and the entropy decreases so that the compression is greater. As gets smaller, distortion goes down but compression is less. The resulting quantization indices can then be entropy coded. A typical approach is to use a Peano or zigzag scan through the coe cients to form a 1-D data stream and then apply either a simple scalar Hu man or an arithmetic code to the result. Both Hu man and arithmetic codes can be combined with run-length coding to take advantage of the many zero coe cients remaining after quantization. An alternative is to exploit both the spatial and frequency localization of wavelets. Lewis and Knowles 92] proposed to model edges across scales by gathering non-zero coe cients corresponding to a given spatial location in bands oriented in the same direction. A further development taking dependencies across scales into account is Shapiro's landmark SQ method based on embedded zerotrees 137]. This successful variation on uniform SQ attempts to take advantage of the many zeros that appear in the quantized coe cients (increasing as does) and of the location correspondence between those zeros. An extension to this SQ algorithm attempted to jointly optimize the scalar quantizers and the zerotree structures by examining distortion/rate trade-o s 158]. These methods are described further in Section 4.2, together with the VQ algorithms based on them. One way to improve on simple uniform SQ of all subbands is to adjust the quantizers to the di erent bands. One could use an analog of the JPEG quantization table. Non-uniform SQs can also be used. For example, a Lloyd-Max quantizer could be designed for each subband based either on a training sequence of typical data or on a model of the data  BIB001 . With a Lloyd-Max quantizer, the quantization law is tailored to the probability density function of each subband. In the discrete case, the value of the probability mass function associated with a coe cient value x is estimated by the frequency of occurrence of x in the training sequence for that subband. Each subband can itself have a variety of SQs available for coding di erent coe cients within that subband. For example, the encoder can classify the activity level of blocks of coe cients within the band, and transmit that class information to the decoder so it knows which SQ to use for coding those coe cients 156]. Or, the classi cation can be made on the baseband, which is assumed to be transmitted rst, and that way the decoder can perform the same classi cation and use the correct quantizer for each later coe cient, without the encoder having to explicitly send the class information as overhead  . Another popular design is to employ quantizers with a center \dead zone" which zeros out large numbers of coe cients, and makes subsequent entropy coding very e cient (see, e.g., 68]). Such a method requires a \signi cance map" which indicates where the coe cients of large magnitude are located. A variety of methods, such as run-length coding, could be used for e ciently coding this sparse positional information 30]. Some works on wavelet compression place little emphasis on the quantization operation and focus almost entirely on the signal decomposition. Donoho et al. 51] essentially use the dead zone idea without explicitly quantizing the nonzero coe cients. Their \hard thresholding" method sets to zero all coe cients having energy less than a pre-determined threshold, forming a \dead zone." The remaining coe cients are not explicitly quantized. If operating on real numbers, this method mathematically amounts to no compression at all since there is no compression in going from any number of real numbers to a much smaller collection of real numbers. On a computer, real numbers are of course approximated by oating point numbers. Thus there will be some compression, but it is not immediately quanti able since the location of the non-thresholded coe cients has to be sent as well. Thus, the scheme presented in BIB005 is not yet a compression scheme. A simple approach would be to explicitly quantize the non-thresholded coe cients, for example with a uniform quantizer having a stepsize of the order of the threshold. The error would of course increase, but proportionally to the number of remaining coe cients, which we assume is small. However, the locations of these coe cients must be sent as side information, with an overhead of the order of log 2 N bits for a signal of size N, unless some prior information is known. Donoho et al. also consider a \soft thresholding" approach which corresponds to attenuating all of the coe cient values according to some weighting function instead of making the \hard" comparison and zeroing. Again, quantization is not considered in their scheme, but the same discussion as above can be used to arrive at a realistic compression scheme. Note that the classes of signals considered by Donoho et al. contain many discontinuities (e.g. like images) and thus the wavelet basis is indeed an interesting choice because of its ability to focus on edges. For other classes of signals (e.g. containing sinusoidal components like musical sounds) that advantage is not clear. Some subband/SQ methods attempt to compute the quantization steps of the di erent subbands so as to minimize a noise power weighted by the sensitivity function of the human visual system BIB002 BIB003 . This is a very important line of investigation, since perceptually based quantization will outperform quantization based on mean squared error by a large margin, especially at low bit rates.