Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 37 ยท Compression in Practice

Lossy Compression and Rate-Distortion Theory

Learn what lossy compression trades away: distortion measures, the rate-distortion function, scalar quantization and DCT transform coding, with runnable NumPy and SciPy examples.

Everything so far was lossless: decode and you get the original back, bit for bit. Photos, music and video would be far too large that way. JPEG, MP3 and H.264 are lossy: they throw away information that people are unlikely to notice. The theory that says how much you can save for a given quality is rate-distortion theory, also due to Shannon (1948 and 1959).

This lesson introduces distortion, the rate-distortion function R(D), quantization and transform coding with the discrete cosine transform (DCT).

Distortion and rate

A distortion measure d(x, xฬ‚) says how bad it is to reconstruct xฬ‚ when the source produced x. The most common is the squared error, (x - xฬ‚)ยฒ; its average is the mean squared error (MSE). Image quality is often quoted as PSNR in decibels: 10 log10(MAXยฒ / MSE), with higher values better.

The rate-distortion function R(D) is the smallest number of bits per source symbol that allows reconstruction with average distortion at most D. For a Gaussian source with variance ฯƒยฒ and squared error it is beautifully simple:

TEXT
R(D) = 1/2 log2(ฯƒยฒ / D)      for 0 < D <= ฯƒยฒ,   and 0 for D >= ฯƒยฒ

Each extra bit of rate cuts the distortion by a factor of 4 (6.02 dB). At D = ฯƒยฒ the rate is zero: just output the mean. At small D the rate grows without bound, because exact reproduction of a continuous value needs infinitely many bits.

Scalar quantization

The simplest practical lossy coder is a uniform scalar quantizer: round each value to the nearest multiple of a step size ฮ”. The rate is the entropy of the quantizer output (when you code it with an entropy coder), and the distortion is about ฮ”ยฒ/12, the variance of a uniform error on an interval of width ฮ”.

Python Quantizing a Gaussian source

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last column is the gap to the theoretical bound. It approaches about 1.53 dB (a quarter of a bit per sample, (1/2) log2(ฯ€e/6)) at high rates: a plain uniform quantizer with ideal entropy coding is only 0.25 bit worse than the best possible scheme. Better quantizers that work on blocks of values (vector quantization) can close part of this gap.

Why transforms help

Real signals are correlated: neighbouring pixels or audio samples are similar. Quantizing each sample separately wastes rate. Transform coding first applies an orthogonal transform that packs most of the energy into a few coefficients, then quantizes those coefficients coarsely and discards the many small ones. JPEG uses an 8ร—8 DCT; MP3 and AAC use the modified DCT on audio.

Python Energy compaction with the DCT

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Keeping only 8 of 64 coefficients (one eighth of the data) already reproduces the signal with a tiny error, because almost all the energy sits in a few low-frequency coefficients. The rest is mostly the noise. That is why JPEG files are small: smooth image areas have almost empty high-frequency coefficients.

A tiny transform coder

Combine both ideas: DCT, then a uniform quantizer with a coarse step, then estimate the rate as the entropy of the quantized coefficients.

Python Transform + quantization versus quantizing directly

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For every step size the DCT version needs far fewer bits per sample and even has lower distortion, because the many tiny coefficients are quantized to zero (a small error each) and their entropy is tiny. That is the gain of transform coding.

Perceptual codecs go further: they spend distortion where the senses are least sensitive. MP3 hides quantization noise under loud sounds (masking); JPEG quantizes high spatial frequencies more coarsely than low ones, and works in a colour space that separates brightness from colour.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the rate-distortion function R(D) give?

    R(D) is the lower bound on rate for a given allowed distortion; no code can do better, and good codes approach it.
  2. 2. For a Gaussian source with variance sigma^2, what does one extra bit of rate do to the squared-error distortion?

    D = sigma^2 * 2^(-2R), so each added bit reduces D by a factor of 4, which is about 6 dB.
  3. 3. Why is the DCT useful in lossy compression?

    The transform is invertible and energy-preserving; compression comes from quantizing and entropy-coding the sparse coefficients.
  4. 4. The approximate distortion of a uniform quantizer with step size D is:

    The error is roughly uniform on an interval of width step, whose variance is step^2 / 12.

Summary

  • Lossy coding trades distortion for rate; R(D) is the theoretical limit.
  • For a Gaussian source R(D) = 1/2 log2(ฯƒยฒ/D): 6 dB per bit.
  • A uniform quantizer has MSE about ฮ”ยฒ/12 and is about 1.53 dB from the bound at high rates.
  • Transform coding (DCT) makes most coefficients near zero, so rate falls at equal distortion.
  • Real codecs add perceptual models, prediction and entropy coding.

Next: Cross-Entropy and KL Divergence in Machine Learning