Szpankowski
Le Jeudi 8 Mars 2001 à 16h00
W. Szpankowski
(Purdue University, W. Lafayette)
Pattern matching image and video compression
Theory, algorithms, and experiments
Résumé/Abstract :
We propose a lossy data compression framework based on an approximate
two dimensional pattern matching (2D-PMC) extension of the 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 discuss
the associated mobile decompressor called MobilVideo.
This is a joint work with M. Alzina (ENST, France), A. Grama (Purdue) and
D. Meyer (Purdue/VisualGold Inc.).