Pattern Matching Image Compression with Predication Loop
D. Arnaud, Wojciech Szpankowski · Data Compression Conference · 1997
Recently, Atallah, Genin and Szpankowski [2] (cf. also [3]) introduced a novel image compression technique based on pattern matching, namely Pattern Matching Image Compression (PMIC). Basically, it is a lossy extension of the well known Lempel-Ziv scheme in which one searches for the longest prefix of an uncompressed image that approsimately occurs in the already processed image. It was proved that such an extension leads to a suboptimal compression. Success of PMIC crucially depends on several enhancements such as searching for reverse approximate matching, recognizing substrings in images that are additively shifted versions of each other, introducing a variable and adaptive maximum distortion level, and so forth. Here, we introduce another enhancement, namely, predictive coding. More importantly, we implement Differential Predictive Code Modulation (DPCM) within PMIC. More precisely, the PMIC compression algorithm with prediction loop should be performed on the quantized differential image on a pixel-by-pixel basis. Unfortunately, the PMIC algorithm, proceeds several pixels at a t ime (i.e., the longest prefix found in the database). But, we can consider a prediction loop algorithm that works on a cell where the cell in PMIC becomes naturally the longest prefix found in the database. The table below presents a comparison between JPEG, PMIC with constant and variable distortion level D, and PMIC-PL (with prediction loop). We conclude that prediction gives