3 Review of DPCM

In the following, x_i,j = x_m stands for the color value of the pixel currently in position (i,j) = m in the $N\times N$ pixels original image, and $\hat{x}_{i,j} = \hat{x}_m$ is the color value of the ``predicted'' (reconstructed) pixel of the reconstructed image. As seen in [11] and accordingly to Fig. 2, the configuration of the 2-D predictor is as following:

  

Figure 2: DPCM predictor configuration.

 

$$\hat{x}_m= 0.75A - 0.50B + 0.75C.$$ (2)

where x_m= x_i,j, $A = \hat{x}_{i,j-1}$, $B = \hat{x}_{i-1,j-1}$, and $C = \hat{x}_{i-1,j}$.

In the above, e_m stands for the error value between the original and the reconstructed pixels:

$$e_m = x_m- \hat{x}_m.$$ (3)

Finally, $e^{\star}_m$ is the quantized value of e_m, as described in [11] from which Table 1 is drawn. Then:

Algorithm PREDICTION
Input: x_i,j = x_m, $\hat{x}_{i,j-1} = A$, $\hat{x}_{i-1,j-1} = B$, and $\hat{x}_{i-1,j} = C$ (see Fig. 2).
Output: $e^{\star}_m$.
Method: We compute a first $\hat{x}_m$, then e_m and $e^{\star}_m$. Eventually, we update the value of $\hat{x}_m$.

begin
		 Compute $\hat{x}_m$ accordingly to Eq. 2
		 Clip $\hat{x}_m$ to the range [0,255]
		 Compute $e_m := x_m - \hat{x}_m$ 
		 Compute $e^{\star}_m:= Quantize (e_m)$ 
		 Upgrade $\hat{x}_m$ by computing $\hat{x}_m$ := $\hat{x}_m+ e^{\star}_m$ 
		 Clip $\hat{x}_m$ to the range [0,255] 
end

   

$$(d_i,d_{i+1}) \rightarrow r_i$$ i Probability Huffman Code

$$\rightarrow$$ 0.025 111111

$$\rightarrow$$ 1 0.047 11110

$$\rightarrow$$ 2 0.145 110

$$\rightarrow$$ 3 0.278 00

$$\rightarrow$$ 4 0.283 10

$$\rightarrow$$ 5 0.151 01

$$\rightarrow$$ 6 0.049 1110

$$\rightarrow$$ 7 0.022 111110

In fact, we add an offset of 128 to $e^{\star}_m$, making all of the error values positive (for an 8-bit original) so that they can be printed on a output device. The error image for a perfectly reconstructed image is thus uniform gray field with a code value of 128.

  

Figure 3: DPCM block diagram.

The DPCM algorithm is summarized in Figure 3. We observe that it applies to every pixel of the image. That leads to the following algorithm:

Algorithm PREDICTION_LOOP
Input: x_i,j = x_m, for all $(0\leq i\leq N-1)$ and $(0\leq j\leq N-1)$.
Output: $e^{\star}_m$, for all $(0\leq i\leq N-1)$ and $(0\leq j\leq N-1)$.
Method: We use PREDICTION to compute $e^{\star}_m$ for each pixel.

begin
		 Initialize $\hat{x}_m= x_m$ and $e^{\star}_m= x_m$ for all $(0\leq i\leq N-1)$ and j=0.
		 for j=1 to N-1 do
		 		 for i=0 to N-1 do
		 		 		 Call PREDICTION on xi,j = xm, $\hat{x}_{i,j-1} = A$, $\hat{x}_{i-1,j-1} = B$, and
		 		 		 $\hat{x}_{i-1,j} = C$ (see Fig. 2).
		 		 doend
		  doend 
end

From Figure  3 one concludes that the prediction (reconstructed pixel) $\hat{x}_m$ for the transmitter is exactly the same as the one used by the receiver. They both need, and only need, the quantized difference $e^{\star}_m$. The transmitter puts this difference in a file, whereas the receiver reads this difference from the file.

Finally, $e^{\star}_m$, which is the quantized difference for each pixel, and the whole picture (formed with these quantized differences) is compressed with Huffman code.