A pattern matching approach to image compression

We propose an image compression scheme based on approximate pattern matching, that we name pattern matching image compression (PMIC). We give new, efficient algorithms for performing computations motivated by this scheme, and describe the compression ratios experimentally obtained. The main idea is a lossy extension of the Lempel-Ziv (1977) data compression scheme in which one searches for the longest prefix of an uncompressed image that approximately occurs 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. Our scheme is competitive with JPEG and wavelet compression for graphical and photographical images, and it is provably suboptimal under some probabilistic assumptions concerning an image