PATTERN MATCHING IMAGE AND VIDEO COMPRESSION:
                Theory, Algorithms, and Experiments

                        Wojciech Szpankowski
                     Department of Computer Science
                           Purdue University
                         W. Lafayette, IN 47907



We propose a lossy data compression framework based on an
approximate two dimensional pattern matching (2D-PMC) extension of the
well known Lempel-Ziv lossless scheme. This framework forms the basis upon which
higher level schemes relying on differential coding, frequency domain
techniques, prediction, and other methods can be built. We apply the
pattern matching framework to image and video compression and report on
theoretical and experimental results. Theoretically, we show that the
fixed database model used for video compression leads to suboptimal
but computationally efficient performance.
The compression ratio of this model is shown to tend to
the generalized entropy defined in this paper. For image compression
we use a growing database model for which we provide an approximate analysis.
The implementation of 2D-PMC is a challenging problem from the
algorithmic point of view. We use a range of techniques and data
structures such as k-d trees, generalized run length coding, adaptive
arithmetic coding, and variable and adaptive maximum distortion level
to achieve good compression ratios at high compression speeds. We
demonstrate bit rates in the range of 0.25-0.5 bpp for high quality
images and data rates in the range of 0.15-0.5 Mbps for
a baseline video compression scheme that does not use any prediction or
interpolation. We also show that this asymmetric compression scheme
is capable of extremely fast decompression making it particularly
suitable for networked multimedia applications. If time allows,
we present a demo of real-time decompression for streaming video using
mobile code.