Wojciech Szpankowski

Pattern Matching Image Compression: Theory, Algorithms and Experiments

We describe a non-transform image compression technique based on approximate pattern matching, called Pattern Matching Image Compression (PMIC). The main idea is a lossy extension of the Lempel-Ziv data compression scheme in which one searches for the longest prefix of an uncompressed image. This scheme turns out to be competitive with JPEG and wavelet compression for graphical and photographical images. Unlike other algorithms, its asymptotic performance can be theoretically established. Under a stationary mixing probabilistic model of an image and fixed maximum distortion level the compression ratio is asymptotically equal to the generalized R\'enyi entropy. In this talk, we discuss theoretical, algorithmic and experimental results of this new compression scheme.