The discrete cosine transform

The problem the transform solves

A natural image is smooth over most of its area. Neighbouring picture elements carry almost the same value, and the differences between them are small. A compression stage that stores each element independently ignores this structure and pays for it. The discrete cosine transform, or DCT, is a way of rewriting a block of picture elements as a weighted sum of a fixed set of wave patterns, arranged so that the smooth content of the block collects in a few large weights and the fine detail collects in many small ones.

The transform itself is reversible. No information is lost when a block is transformed; the same number of values comes out as went in. The saving appears in the next step, when the small weights are quantised more coarsely than the large ones. Because so much of a typical block now sits in a handful of large weights, most of the small ones can be set to zero with little visible effect. This is the whole reason the transform is used.

Basis functions

The DCT expresses a block as a sum of cosine waves of increasing frequency. Each pattern is a product of a horizontal wave and a vertical wave, and the pair of frequencies names the coefficient it multiplies. The pattern with zero variation in both directions is the average, or DC, coefficient. The patterns with variation in one direction describe horizontal or vertical detail. The patterns with variation in both describe diagonal detail. The diagrams below show a few of these patterns for an eight-point axis.

The 8×8 block

The transform is applied to a small block rather than to a whole picture, for two reasons. First, the assumption of smoothness holds better over a short distance than over a long one, so a small block concentrates its energy more sharply. Second, a small block can be processed in parallel, which suits the hardware that does the work. The classic choice is an 8 by 8 block of 64 values, producing 64 coefficients. Later standards extend or reshape this block, but the principle is unchanged: transform a local patch, and arrange the result from low frequency to high frequency.

For an N-point one-dimensional transform, the coefficient of index u is the sum over positions x of the sample value multiplied by the cosine of π·u·(2x+1)/2N, scaled by a normalising factor. The two-dimensional form applies the same operation along rows and then along columns, and the separability is what makes the arithmetic cheap. A block of 64 values therefore costs 64 operations along one axis and 64 along the other, rather than the far larger count a general two-dimensional transform would require.

Quantisation and the zig-zag order

After the transform, the coefficients are divided by a quantisation step and rounded to integers. A large step discards detail and saves bits; a small step preserves detail and costs bits. Because the eye is less sensitive to fine detail than to broad tonal shifts, the step is usually larger for high-frequency coefficients than for low-frequency ones. This is the single most important control in a lossy encoder, and every quality setting is ultimately a choice of how coarse these steps should be.

The resulting integers are then read out in a zig-zag order that runs from the low-frequency corner to the high-frequency corner. Because the small high-frequency coefficients are often zero, the zig-zag order groups the zeros together at the end of the row, where a simple run-length stage can describe them as a single short statement. The combination of transform, quantisation and ordered readout is the core of every block-based compression standard, from the earliest MPEG specifications to the present day.