Quantizer optimization

A substantial portion of the compression achieved by a lossy DPCM scheme is due to the quantization of the differential image. Quantizer design may be based on either statistical or visual criteria. Several approaches to designing quantizers based on visual criteria have been suggested , but a debate continues on the best criterion to use, and justifiably so, considering the complexities of the HVS. In the discussion that follows, we restrict ourselves to the design of quantizers that are optimized on a statistical basis.

A quantizer is essentially a staircase function that maps many input values (or even a continuum) into a smaller, finite number of output levels. Let e be a real scalar random variable with a probability density function p_e(e); e.g., e could represent the differential image and p_e(e) could represent its histogram. A quantizer maps the variable e into a discrete variable that belongs to a finite set {r_i, i = 0,...,N-1}of real numbers referred to as reconstruction levels. The range of values of e that map to a particular are defined by a set of points {d_i, i = 0,...,N}, referred to as decision levels. The quantization rule states that if e lies in the interval (d_i,d_i+1), it is mapped (quantized) to r_i, which also lies in the same interval. The quantizer design problem is to determine the optimum decision and reconstruction levels for a given p_e(e) and a given optimization criterion.

Depending on whether the quantizer output levels are encoded using variable-length or fixed-length codewords, two different types of quantizers are typically used in a DPCM system. For fixed-length codewords, the DPCM bit rate is proportional to log₂ N, where N is the number of quantizer levels. In this case, it is desirable to design a quantizer that minimizes the quantization error for a given N. If the MSE criterion is used, this approach leads to a quantizer known as the Lloyd-Max quantizer. This types of quantizer has nonuniform decision regions. For variable-length codewords, the bit rate is lower bounded by the entropy of the quantizer output (instead of log₂ N), which leads to the approach of minimizing the quantization error subject to an entropy constraint. Since the qunatizer output distribution is usually highly skewed, the use of variable-length coding seems appropriate. For a Laplacian density and MSE distortion, the optimum quantizer in this case is uniform; i.e., the decision regions all have the same width. For the same MSE distortion, a uniform quantizer has more levels than a Lloyd-Max quantizer, but it also has a lower output entropy. It has been shown that for Laplacian density and a large number of quantizer levels, optimum variable-length coding improves the SNR by about 5.6 dB over fixed-length coding at the same bit rate

It is worthwhile to discuss the Lloyd-Max quantizer in more detail since it finds use in other techniques DPCM. Its derivation is based on minimizing the expression

                             (9.16)

with respect to{d_i, i = 0,1,..,N}and {r_i, r = 0,...,N-1}. The solution results in decision levels that are halfway between the neighboring reconstruction levels and reconstruction levels that lie at the center of the mass of the probability density enclosed by the two adjacent decision levels, i.e., at the mean of the differential image in that interval. Mathematically, the decision and reconstruction levels are solutions to the following set of nonlinear equations:

                                                                  (9.17)

                   (9.18)

In general, Eqs. (9.17) and (9.18) do not yield closed-form solutions, and they need to be solved by numerical techniques. In certain cases, such as the Laplacian pdf, a closed-form solution exists. When a numerical solution is necessary, the following iterative algorithm can be used. First, an arbitrary initial set of values for {d_i} is chosen, and the optimum {r_i} for that set are found by using Eq. (9.18). For the calculated {r_i}, the optimum {d_i} are then determined using Eq. (9.17). This process is iterated until the difference between two successive approximations is below a threshold. In most cases, rapid convergence is achieved for a wide range of initial values.

Fig 9.2 shows the optimum Lloyd-Max decision and reconstruction levels for a unit-variance Laplacian density with N=8 (3-bit quantizer). As expected, the quantization is fine near zero where the signal pdf is large, and becomes coarse for large differences. To illustrate typical performance, the 3-bit quantizer (scaled according to the prediction error variance) was applied to the LENA image. The results are summarized in Table9.1. The first column denotes the index i of the quantizer output. The second column denotes the decision and reconstruction levels for a given quantizer level. Note that the magnitude of the largest reproducible difference value in this system is only 20. Due to the required symmetry, a quantizer with an even number of levels cannot reconstruct a difference of zero. This type of quantizer is referred to as mid-riser quantizer. It is also possible to design a mid-tread quantizer that has an odd number of levels and can pass zero. If the levels are fixed-length coded, the mid-tread quantizer is less efficient because of unused codewords. The third column shows the probabilities of occurrence of the quantizer outputs, The entropy of the quantizer output levels is 2.52 bits/pixel while the local Huffman code in the last column of Table 9.1 achieves a bit rate of 2.57bits/pixel, which is fairly close to the entropy. As noted previously, the use of an optimum uniform quantizer with variable-length coding would allow for a higher quantity reconstruction at this same bit rate, or conversely, a lower bit rate for the same quality.

In designing a quantizer for a given application, it is important to understand the types of visual distortion introduced by the quantization process in DPCM, namely, granular noise, slope overload, and edge busyness. There are illustrated in Fig 9.3, Granular noise is apparent in uniform regions and results from the quantizer output fluctuating randomly between the inner levels as it attempts to track small differential signal magnitudes. The use of small inner levels or a mid-tread quantizer with zero as an output level may help to reduce granular noise. Slope overload noise occurs at high contrast edges when the outer levels of the quantizer are not large enough to respond quickly to large differential signals. A lag of several pixels is required for the quantizer to tract the differential signal, resulting in a smoothing of the edge. Edge busyness occurs when a reconstructed edge varies slightly in its position from one scan line to another due to quantizer fluctuations. Unfortunately, attempts to reduce one type of degradation usually enhance other types of noise.

Reference:

Digit Image Compression Techniques

Majid Rabbani and Paul W.Jones