Thesis: Beyond Traditional Transform Coding

["Vivek Goyal" (vivek@research.bell-labs.com)]

#12 Thesis: Beyond Traditional Transform Coding

PhD Thesis: Beyond Traditional Transform Coding
Author: Vivek Goyal
Date: December 1998
Institution: University of California, Berkeley
Advisor: Martin Vetterli

Abridged Abstract:

Transform coding is the most successful and pervasive technique
for lossy compression of audio, images, and video. In conventional
transform coding, the original signal is mapped to an intermediary
by a linear transform; the final compressed form is produced by
scalar quantization of the intermediary and entropy coding. This
thesis extends the traditional theory toward several goals: improved
compression of nonstationary and non-Gaussian signals; robust joint
source-channel coding for erasure channels; and computational
complexity reduction or optimization.

First the use of frames, overcomplete sets of vectors, is
explored. Linear transforms based on frames give representations
with robustness to random additive noise and quantization.
Nonlinear, signal-adaptive representations can be produced with
frames using matching pursuit. This algorithm exhibits good
compression performance at low rates. Optimal reconstruction is
described for both linear and nonlinear frame-based representations.

Within the conventional setting of basis representations, the
Karhunen- Loeve transform (KLT) gives optimal compression of
Gaussian sources. Its dependence on the probability density of the
source, which is generally unknown, limits its application.
Including a description of an estimated KLT in the data creates
significant overhead. In contrast, this thesis introduces a method
for on-line universal transform coding which utilizes backward
adaptation and has asymptotically negligible overhead. Also
developed are techniques inspired by adaptive FIR Wiener filtering.

Transform coding is normally used solely for source coding.
This thesis introduces two joint source-channel coding methods for
erasure channels, presented in the context of multiple description
coding. These give graceful performance degradation in the face of
random loss of transform coefficients. One technique produces
correlated transform coefficients so that lost coefficients can be
estimated. The rate allocated to channel coding is continuously
adjustable with fixed block length. The second technique--
quantized frame expansion--is similar to scalar quantization
followed by a block channel code, except that quantization and
introduction of redundancy are swapped. In certain circumstances
the end-to-end performance significantly exceeds that of a system
with separate source and channel coding.

Finally, joint optimization of computational complexity and
rate-distortion performance is considered. Sample analyses compare
unstructured and harmonic transforms, and show that JPEG encoding
complexity can be reduced with little loss in performance.

The complete abstract is available on-line at
http://cm.bell-labs.com/cm/ms/who/vivek/Thesis/
Instructions for downloading the entire thesis appear at the same address.

Your comments are always welcome. Thank you.

Vivek K Goyal
Mathematics of Communications Research, Bell Labs
Office: 600 Mountain Avenue +1 908 582 6484
Room 2C-178 fax: 582 3340
Murray Hill, NJ 07974
E-mail: v.goyal@ieee.org
URL: http://cm.bell-labs.com/who/vivek/