Pattern Matching Image Compression

We investigate image compression schemes based on approximate pattern matching. The research involves efficient algorithms for performing the computations motivated by such schemes, and experimental determination of the compression ratios achieved. The main idea is a lossy extension of the Lempel-Ziv data compression scheme in which one searches for the portions of an uncompressed image that approximately occur in the already processed image. It 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, and so forth. Provable performance bounds are established, under some probabilistic assumptions concerning an image.