Mikhail Atallah,Yann Genin,Wojciech Szpankowski

COAST TR 97-21

article

We propose a non-transform image compression technique based on approximate pattern matching, that we name Pattern Matching Image Compression (PMIC). The main idea behind it is a lossy extension of the Lempel-Ziv data compression scheme in which one searches for the longest prefix of an uncompressed image that approximately (e.g., D of mismatches are allowed) occurs in the already processed image. This main algorithm is enhanced with several new features 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 D, and so forth. These enhancements are crucial to the overall quality of our scheme. In this paper we present algorithmic as well as experimental results of the Pattern Matching Image Compression. Our scheme turns out to be competitive with JPEG and wavelet compression for graphical and photographical images. A unique feature of the purposed algorithm is that an asymptotic performance of the scheme can be theroretically established. More precisely, under stationary mixing probablilistic model of an image and fixed maximum distortion level D, the compression ratio is asymptotically equal to the so called generalized Renyientropy r0(D). This entropy is in general smaller than the optimal rate distortion function R(D), but there is numerical evidence that these two quantities do not differ too much for small values of D.

PDF

1997 – November

COAST Lab

IEEE Transactions on Pattern Analysis and Machine Intelligence

Atallah

2001-01-01