DPCM Results

Table 9.2 summarizes the results obtained from applying nonadaptive and adaptive (switched quantization) DPCM techniques to the two test images using fixed 1-D and 2-D predictors. In the nonadaptive DPCM scheme, Lloyd-Max nonuniform quantizers with two, four, or eight output levels (corresponding to a bit rate of 1.00, 2.00, or 3.00 bit/pixel with fixed-length coding) were used to quantize the differential image. These quantizers were optimized for a Laplacian distortion with the same variance as the differential image global variance.

The ADPCM scheme switched among four (m=4) quantizers over a block length of 10 pixels (k=10). The overhead information required to inform the receiver of the quantizer choice was thus 2 bits/10 pixels = 0.2 bit/pixel. All quantizers were scaled versions of the same Lloyd-Max nonuniform quantizers used in the nonadaptive case. The scale factors were 0.50, 1.00, 1.75, and 2.50. With the overhead information, the resulting bit rates were 1.20, 2.20, and 3.20 bits/pixel.

Implementation Issues and Complexity of ADPCM Algorithm

In the following discussion on the ADPCM computational complexity, it is assume that the switched quantizer encoder is implemented as four independent sequential encoder units; i.e., we do not take advantage of the common components in the predictor computations or the parallel nature of the switched quantizer. A parallel implementation of the four quantizers could easily be implemented to effectively reduce the number of computations.

For each encoder unit, the third-order predictor requires 3 multiplications and 2 additions per pixel, and formation of the differential, reconstructed, and distortion signals requires 3 additions per pixel. Each scalar quantizer of rate R (R=1,2, or 3 bits) requires R comparisons per pixel if a binary tree structure, i.e., successive approximation, is used. Therefore, the four encoder units require a total of

. 12 multiplications,

. 20 additions, and

. 4R comparisons

per pixel. We disregard the additional 3 comparisons per 10 pixel block required to choose the minimum distortion quantizer. The decoder requires 3 multiplications and 2 additions per pixel for the predictor and 1 addition to form the reconstructed value.

Therefore, the decoder requires

. 3 multiplications and

. 3 additions

per pixel. The asymmetry between the encoder and decoder is obvious for this algorithm.

Memory requires are minimal for the ADPCM algorithm. At both the encoder and decoder, permanent memory is required for the predictor coefficients and the quantizer levels, and two line buffers are required to store the previous and current reconstructed lines used in the predictor computations. Four block buffers are also required at the encoder for the switched quantizer selection.

As noted in Section 9.1.1, channel errors are propagated in DPCM owing to the use of previously reconstructed values in the predictor. The errors are typically manifested as 1-D or 2-D streaks (depending on whether the predictor is 1-D or 2-D), and the extent of the streaks depends on the values of the predictor coefficients. The effects of any channel errors can be minimized by sending the actual values of pixels at prescribed locations in order to reinitialize the predictor at both the transmitter and the receiver.

Reference:

Digit Image Compression Techniques

Majid Rabbani and Paul W.Jones