next up previous
Next: References Up: PATTERN MATCHING IMAGE COMPRESSION Previous: 3 Review of DPCM

4 New Algorithm: PMIC with DPCM

Like in Huffman compression (the compression part of DPCM), the PMIC compression algorithm should be performed on the quantized differential image. However, the algorithms seen above are well adapted to Huffman coding, because they deal on a pixel-by-pixel basis. Unfortunately, the PMIC algorithm, proceeds several pixels at a time (i.e., the longest prefix found in the database). Besides, we do not know in advance what the length of this prefix will be. But, there is a way around all of those problems. In fact, if we consider the PREDICTION algorithm to be performed, not on a pixel basis, but on a cell (which is, in the case of DPCM, one single pixel) basis, then this algorithm needs just a few adaptations in order to be suited for PMIC: in this latter, the cell becomes naturally the longest prefix found in the database.

These considerations lead to the algorithms given below, which should replace the PREFIX and COMPRESS_ROW algorithms for more detail) respectively:

Algorithm DIFFERENTIAL_PREFIX
Input: $\hat{x}_1^n$, ex1n (where n=fN), and y1N
Output: Largest integer k such that, for some index t ($1
\leq t \leq n-N$), $d ( ex_t^{t+k-1} , ey_1^k ) \leq D$. The algorithm outputs both k and t, as well as $\hat{y}_1^N$ and ey1N, both returned by the call to the PREDICTION_LOOP algorithm.
Method: We first use PREDICTION_LOOP to form a differential row, then we compute, for all i,j, Sij = total distortion measure between exii+j-1 and ey1j.


begin
		 Call PREDICTION_LOOP on x1N
		 Let $\hat{y}_1^N$ and ey1N be returned by this call to PREDICTION_LOOP.
		 Initialize all Sij := 0.
		 for i=1 to n-N do
		 		 for j=1 to N do
		 		 		 Compute Sij := Si,j-1 + d(exi+j-1, eyj)
		 		 doend
		  doend
		  Let k be the largest j such that $S_{ij} \leq j D$, and let t be the corresponding i
		  Output k and t
end

One should note that the PREDICTION_LOOP algorithm is here used on generally more pixels than needed, since it is used on N pixels, and that the longest prefix will have a size $\leq N$.

Algorithm COMPRESS_DIFFERENTIAL_ROW
Input: $\hat{x}_1^n$, ex1n (where n=fN), y1N.
Output: A compressed version of ey1N, in the form of (pointer,length) pairs, and the new reconstructed portion, $\hat{y}_1^N$, of the database.
Method: We use PREFIX to ``peel off'' a prefix of the row being compressed, and repeat on the remaining portion of that row until we use it all up.


begin
		 Initialize i := 0.
		 Repeat the following until $i \geq N$ 
		 		 Call PREFIX on $\hat{x}_1^n$, ex1n and yi+1N 
		 		 Let k and t, $\hat{y}_{i+1}^N$ and eyi+1N, be returned by this call to PREFIX
		 		 If k is small (say, $\leq 4$)		 		 then eyi+1i+k is stored explicitly,
		 		 else eyi+1i+k is stored as a (pointer,length) pair,
		 		 Compute $\hat{y}_{i+1}^{i+k} := \hat{y}_{i+1}^{i+k} +
 ey_{i+1}^{i+k}$ (addition of vectors).
		 		 Set i := i+k
end

We have used here the notation ex and ey for x and y, as they are understood in the COMPRESS_ROW algorithm of [2] and discussed briefly above, except that what is now compressed is the quantized differential image, whence the e before x and y. Therefore, $\hat{x}_1^n$ represents the reconstructed (``predicted'') database (and is, in fact, the image as it will be again after decompression); ex1n means the database of the differential image (image actually being compressed); y1N is the currently processed row of the original image; ey1N is the ``differential'' row currently being compressed, that is, the differential pendant of y1N; and $\hat{y}_1^N$ is the new portion of the reconstructed (``predicted'') database. Thus, $\hat{y}$ leads to $\hat{x}$, and ey gives ex.


 
Table 2: ``Lena'' image compressed by JPEG (quality=57), PMIC with constant D (D = 155, DD = 20), PMIC with variable D (D1 = 500, D2 = 55, DD = 22), and PMIC-PL (D1 = 600, D2 = 50, DD = 16).
  JPEG Const D Var D PMIC-PL
Compression ratio 10.03 9.99 10.01 10.04
Bit rate (bits/pixel) 0.8 0.8 0.8 0.8
RMSE (0-255) 4.65 8.90 8.44 15.97
PSNR (dB) 34.78 29.14 29.61 24.06


 
Table 3: ``Basselope'' image compressed by JPEG (quality=57), PMIC with constant D (D = 800, DD = 38), PMIC with variable D (D1 = 800, D2 = 100, DD = 39), and PMIC-PL (D1 = 1000, D2 = 45, DD = 15).
  JPEG Const D Var D PMIC-PL
Compression ratio 9.96 10.04 10.04 9.96
Bit rate (bits/pixel) 0.8 0.8 0.8 0.8
RMSE (0-255) 9.07 12.22 8.44 78.89
PSNR (dB) 28.97 26.39 29.61 10.19


 
Table 4: ``Lena'' image compressed by JPEG (quality=21), PMIC with constant D (D = 400, DD = 38), PMIC with variable D ( D1 = 500, D2 = 55, DD = 22), and PMIC-PL (D1 = 600, D2 = 50, DD = 16).
  JPEG Const D Var D PMIC-PL
Compression ratio 10.03 10.00 9.95 10.02
Bit rate (bits/pixel) 0.8 0.8 0.8 0.8
RMSE (0-255) 7.96 13.92 12.87 20.41
PSNR (dB) 30.11 25.26 25.94 21.94

Finally, we present some experimental results. We summarize them in Tables 2--4 where JPEG, PMIC with constant and variable D, and PMIC-PL (PMIC with Prediction Loop) are compared for three images, namely: ``Lena'' image, ``Basselope'' image (a graphic image) and ``San Francisco'' image (a photographic image). We conclude that prediction, as discussed in Section 2, can lead to substantial speed up of compression time, butter compression time without significant deterioration of image quality. More sophisticated PMIC-PL cna lead to further improvements, as our preliminary results suggest. However, results in Tables 2-4 are, in fact, worse than expected. We believe they originate from the fact that we use variable-D scheme which seems to be unsuited for the predictive loop (the derivative is actually done on the original image, and not on the differential image, as it should be). This might be an interesting point further research (i.e., to implement a good derivative scheme on the differential image). Then, we believe we can achieve much more substantial improvements. This will be reported in our journal version of this paper.


next up previous
Next: References Up: PATTERN MATCHING IMAGE COMPRESSION Previous: 3 Review of DPCM
Denis Arnaud
11/19/1997