The discrete cosine transform

Here are eight pixels from one row of an image, dark to light, repeated forever as the DFT sees them. Watch the jump where one copy meets the next, and watch it vanish when every other copy is mirrored.

Repeat it, or mirror it first

x: brightness along 8 pixels, 0.20 to 0.90. The DFT sees x repeated; the DCT sees x and its mirror image, repeated.

Repeated as the DFT sees it, x jumps from 0.90 back to 0.20 at every seam. A jump needs many frequencies to draw (7.3).

repeating

x, x, x, …

jump at the seam

0.70

Describe this picture

One panel: value from 0 to 1.1 against sample $n$ from $-8$ to 23, for $x$ , the brightness along 8 pixels, 0.20 to 0.90. The DFT sees $x$ repeated; the DCT sees $x$ and its mirror image, repeated. Each copy of $x$ is drawn as stems with filled-dot heads, and each mirrored copy as stems with filled-square heads. Each seam is a dotted vertical line, and a key names the dot, the square and the seam. The picture plays by itself and has no control.

At the start $x$ repeats as the DFT sees it, and jumps from 0.90 back to 0.20 at every seam. The readouts say “x, x, x, …” and a jump at the seam of 0.70, and a bracket at the seam between $n=7$ and $n=8$ is labelled “jump 0.70”. Between 4 and 6.5 seconds every other copy flips in place, reversed from left to right, and its dots turn into squares at the end of the flip, with the caption blank. At 12 seconds the readouts say “x, mirror, x, …” and 0.00, and the bracket reads “no jump”: 0.90 meets 0.90 and 0.20 meets 0.20, and this repetition, 16 samples long, has no jump.

Repeat it, or mirror it first

Sampling the spectrum (13.1) showed that the DFT treats $x$ as one period of a signal that repeats forever. For many signals that is harmless. For a signal that ends higher than it starts, it is not. Where one copy ends and the next begins there is a seam, and at the seam the repeated signal jumps.

In the picture at the top, $x$ is 0.20, 0.25, 0.35, 0.50, 0.65, 0.78, 0.86 and 0.90 for $n=0,\dots,7$ . The row is smooth. Repeated, it climbs to 0.90, drops to 0.20, climbs again, and drops again. The size of the drop is $x[0]-x[N-1]=0.20-0.90=-0.70$ , here with $N=8$ .

A jump needs many frequencies to draw. Convergence and the Gibbs phenomenon (7.3) showed it: the arrows of a wave with jumps shrink only as $1/k$ , while the arrows of a smoother wave shrink faster. So the seam fills the DFT’s high bins with arrows that belong to the repetition, not to the row of pixels.

There is a way out, and wallpaper shows it. Strips that do not match at their edges leave a visible line at every seam. Hang every second strip as a mirror image and the pattern meets itself at each edge, so no line shows. The picture at the top does this to $x$ , and the jump readout falls from 0.70 to 0.00.

The new repetition is the sequence

y=\bigl(x[0],\dots,x[N-1],\ x[N-1],\dots,x[0]\bigr),

which is $x$ followed by its reverse. It has length $2N$ , so here 16 samples. I take its $2N$ -point DFT and ask what it holds.

What the mirror does to the DFT

The sequence $y$ reads the same going forwards from one end of its first half as going backwards from the other. Its centre is half a sample past $n=N-1$ . In the language of Properties of the DFT (13.3), $y$ is circular-even about $n=N-\tfrac12$ , so its DFT is real up to a delay. The delay is half a sample, and Properties of the DTFT (12.3) gave the rule: a delay of $n_0$ samples multiplies the spectrum by $e^{-j\Omega n_0}$ . The $2N$ -point DFT of $y$ is

Y[k]=2e^{j\pi k/2N}\sum_{n=0}^{N-1}x[n]\cos\!\left(\frac{\pi k(2n+1)}{2N}\right).

Here is where it comes from. Each $x[n]$ appears in $y$ twice, at position $n$ and at position $2N-1-n$ . Those two terms of the DFT sum are $e^{-j\pi kn/N}$ and $e^{j\pi k(n+1)/N}$ , times $x[n]$ . Factor out $e^{j\pi k/2N}$ and what is left is a pair $e^{\mp j\pi k(2n+1)/2N}$ , which adds up to $2\cos$ .

Apart from the factor $e^{j\pi k/2N}$ , which is the half-sample turn, the spectrum of $y$ is real. Only cosines remain. That sum is the heart of the discrete cosine transform, in its second form, the DCT-II. In its orthonormal scaling it is

\begin{aligned} X_\text{DCT}[k]&=w_k\sum_{n=0}^{N-1}x[n]\cos\!\left(\frac{\pi k(2n+1)}{2N}\right),\\ w_0&=\sqrt{\tfrac1N},\qquad w_k=\sqrt{\tfrac2N}\ \text{ for } k\ge1. \end{aligned}

For $k=0$ the cosine is 1, so $X_\text{DCT}[0]=\sqrt{1/N}\sum x[n]$ . For the example row that is $4.49/\sqrt8=1.5875$ . In SciPy this is scipy.fft.dct(x, type=2, norm='ortho'). SciPy’s default leaves out $w_k$ and doubles the sum, so its numbers differ from these by a factor.

The count is neat. $N$ real numbers go in and $N$ real numbers come out. With the factors $w_k$ the energy is kept as well:

\sum_{k=0}^{N-1}X_\text{DCT}[k]^2=\sum_{n=0}^{N-1}x[n]^2 .

For the example row both sides are 3.0555. The energy is the quantity from How big is a signal (1.3), and it is kept because the eight cosines are orthogonal and scaled to unit length. These DCT numbers are 1.5875, $-0.7310$ , $-0.0269$ , 0.0210, 0.0035, 0.0004, $-0.0003$ and $-0.0040$ . They fall quickly. The first two hold 99.96 % of the energy.

The maths behind it · orthonormal bases

The eight DCT cosines are an orthonormal basis of the real vectors of length 8. Keeping the first $K$ coefficients is projecting $x$ onto the first $K$ basis vectors, which is the closest a $K$ -term description can come in the mean-square sense.

Keep a few numbers, rebuild

Now I test the claim. Take a transform, keep the $K$ lowest-frequency numbers, set all the others to 0, and transform back. How close is the result to $x$ ? I keep the lowest $K$ because that is what JPEG does, and it is simple to say. For this signal it is also the choice of the largest $K$ for the DFT, and for the DCT at $K=1$ and $K=3$ . At $K=5$ the largest five would swap coefficient 4 for coefficient 7, and both are below 0.005.

The count must be fair, and the unit is a real number. A DCT coefficient is one real number. A DFT bin past bin 0 is a complex number, whose mirror partner comes free for a real $x$ (The DFT, 13.2), so a bin and its mirror cost two. So $K=1,3,5,7$ keeps the average and then 0, 1, 2 or 3 such pairs. I score each rebuild $\hat x$ by the energy of the gap $x-\hat x$ as a share of the energy of $x$ . Watch the two errors as $K$ grows: the DCT’s drops almost to nothing by $K=3$ , and the DFT’s does not.

Keep a few numbers, rebuild

Same x. Numbers kept: a DCT coefficient is 1; a DFT bin with its mirror is 2.

K = 1: both keep only the average, 0.56. Error 17.525 % of the energy for both.

numbers kept K

error, DFT

17.525 %

error, DCT

17.525 %

Describe this picture

Two stacked panels, one for the DFT and one for the DCT, each with $K$ numbers kept, for the same $x$ . A DCT coefficient counts as 1 number, and a DFT bin with its mirror as 2. Both panels have value from 0 to 1.1 against sample $n$ from 0 to 7. The original $x$ is drawn as open circles, and the rebuild as stems with filled-square heads; a key names both. The readouts are the numbers kept $K$ , in a row of their own, then the error of the DFT and the error of the DCT, each in percent to 3 decimals. The clip plays by itself and steps through $K=1,3,5,7$ , with a short morph between them during which the caption is blank, and holds at $K=7$ until 14 seconds.

At $K=1$ both keep only the average, 0.56, and both errors read 17.525 % of the energy. At $K=3$ the DCT rebuild is already within 0.015 % of $x$ , while the DFT, still fighting the seam, misses by 3.968 %, worst at the two ends. At $K=5$ the errors are 1.787 % for the DFT and 0.001 % for the DCT. At $K=7$ the DFT still misses by 0.560 %, and the DCT reads 0.001 %; the caption ends “Mirroring removed the jump, so a smooth x needs few DCT numbers. That is why JPEG uses the DCT.”

After the clip ends, the plots become a slider named “Numbers kept K”: drag across them, or use the arrow keys, and Home and End jump to the ends. It takes only $K=1,3,5,7$ and 8. At $K=8$ the caption says “K = 8: everything kept; both rebuild x exactly.” The page address stores your choice under the key keep.K, so you can share a frame.

Notice where the DFT’s rebuild fails: at the two ends of the row, the sides of the seam. At $K=3$ it reads 0.426 and 0.672 there, against 0.20 and 0.90, so it is off by about 0.23 at each, while the DCT’s rebuild is 0.190, 0.252, 0.363, 0.502, 0.645, 0.769, 0.860, 0.907. A jump that the signal does not contain, built by the repetition, is the part it cannot give up.

After the clip ends, drag across the plots, or use the arrow keys, to keep 1, 3, 5, 7 or all 8 numbers.

Why does the DCT win here? The mirrored repetition is smooth, so, as in 7.3, its arrows fall quickly. In numbers, the DFT’s highest bin is still 29 % of its first non-zero bin, and the DCT’s last coefficient is 0.6 % of its second. This is energy compaction: a smooth signal puts nearly all its energy in the first few coefficients. Describing a hillside’s slope takes two numbers, and describing a cliff at its edge takes many.

The maths behind it · principal components

For data whose neighbouring values are strongly correlated, as image pixels are, the DCT’s basis is close to the principal components of that data (the Karhunen–Loève transform). That is part of why it compacts so well.

Worked example

Every number below was recomputed with NumPy and SciPy for the example row.

The seam. The jump of the plain repetition is $x[0]-x[7]=-0.70$ . In the mirrored repetition the seams run 0.90 to 0.90 and 0.20 to 0.20.
The coefficients. The orthonormal DCT-II is 1.5875, $-0.7310$ , $-0.0269$ , 0.0210, 0.0035, 0.0004, $-0.0003$ , $-0.0040$ . The DFT magnitudes are 4.49, 1.287, 0.516, 0.387, 0.370, 0.387, 0.516, 1.287. The energy is $\sum x^2=3.0555$ and the mean is 0.56125.
The errors. As a share of the energy, for $K=1,3,5,7$ : the DCT gives 17.525 %, 0.015 %, 0.001 %, 0.001 %, and the DFT gives 17.525 %, 3.968 %, 1.787 %, 0.560 %.
A ramp. For $x=0,1,\dots,7$ the DCT is 9.8995, $-6.4423$ , 0, $-0.6735$ , 0, $-0.2009$ , 0, $-0.0507$ , so the even-numbered coefficients past 0 vanish. At $K=3$ the DCT misses by 0.355 % and the DFT by 10.490 %.
The link. For the ramp, the 16-point DFT of $x$ followed by its reverse equals $2e^{j\pi k/16}\sum_n x[n]\cos(\pi k(2n+1)/16)$ for $k=0$ to 7, and SciPy’s default dct(x, type=2) is twice that sum. I checked this in NumPy; it holds for the example row too.

Where you’ll meet this

JPEG cuts an image into blocks of 8 by 8 pixels, takes a two-dimensional DCT of each, and stores the low coefficients finely and the high ones coarsely. That is the subject of Image compression (28.4). MP3 and AAC use the MDCT, a DCT on overlapping blocks, which Perceptual audio coding (29.3) takes up. Video codecs such as H.264 and HEVC use integer approximations of the DCT. Filter banks (23.1) come back to the same idea of splitting a signal into bands.

Left out here: the overlap of the MDCT, the two-dimensional DCT, quantisation tables, and the DCT types I, III and IV.

Reference card

Quantity	Formula	Notes
Seam jump (DFT)	$x[0]-x[N-1]$	the repetition of 13.1
Mirrored extension	$y=(x[0..N-1],\ x[N-1..0])$ , length $2N$	no jump at any seam
DCT-II, orthonormal	$X_\text{DCT}[k]=w_k\sum_{n=0}^{N-1}x[n]\cos\frac{\pi k(2n+1)}{2N}$	$w_0=\sqrt{1/N}$ , $w_k=\sqrt{2/N}$
Link to the DFT	$Y[k]=2e^{j\pi k/2N}\sum_n x[n]\cos\frac{\pi k(2n+1)}{2N}$	$2N$ -point DFT of $y$
Energy	$\sum_k X_\text{DCT}[k]^2=\sum_n x[n]^2$	orthonormal scaling only
SciPy	`dct(x, type=2, norm='ortho')`; inverse `idct(…, norm='ortho')`	default: no $w_k$ , sum doubled
Compaction	smooth $x$ : energy in the first few $X_\text{DCT}[k]$	JPEG, MP3 and AAC (MDCT), video

The discrete cosine transform

First, the picture

Repeat it, or mirror it first

What the mirror does to the DFT

Keep a few numbers, rebuild

Worked example

Where you’ll meet this

Reference card