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:** , *ex _{1}*

beginCallPREDICTION_LOOPonx_{1}^{N}Let andey_{1}^{N}be returned by this call toPREDICTION_LOOP. Initialize allS_{ij}:= 0.fori=1ton-Ndoforj=1toNdoComputeS_{ij}:=S_{i,j-1}+d(ex_{i+j-1},ey_{j})doenddoendLetkbe the largestjsuch that , and lettbe the correspondingiOutputkandtend

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 .

**Algorithm** `COMPRESS_DIFFERENTIAL_ROW`

**Input:** , *ex _{1}*

beginInitializei:= 0.Repeatthe followinguntilCallPREFIXon ,ex_{1}^{n}andy_{i+1}^{N}Letkandt, andey_{i+1}^{N}, be returned by this call toPREFIXIfkis small (say, )theney_{i+1}^{i+k}is stored explicitly,elseey_{i+1}^{i+k}is stored as a (pointer,length) pair, Compute (addition of vectors). Seti:=i+kend

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, represents the reconstructed
(``predicted'') database (and is, in fact, the image as it will be
again after decompression); *ex _{1}*

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 |

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 |

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.