Abstract
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.
