Discrete Cosine Transform

Also known as DCT. Expresses a sequence of NN samples as a weighted sum of NN cosines of increasing frequency.

Each coefficient measures how strongly 1 cosine pattern appears in the samples. Low-frequency patterns change slowly. High-frequency patterns change quickly.

One-Dimensional DCT

The input is NN samples x(n)x(n). The output is NN coefficients X(k)X(k), 1 for each cosine pattern. Each X(k)X(k) gives the amount of the kkth pattern in the samples.

X(k)=α(k)∑n=0N−1x(n)cos⁡(2n+1)kπ2NX(k) = \alpha(k) \sum_{n=0}^{N-1} x(n) \cos\frac{(2n+1)k\pi}{2N}
Here:
nn
sample index
kk
frequency index
NN
number of samples
x(n)x(n)
sample value at index nn
X(k)X(k)
coefficient for frequency kk
α(0)\alpha(0)
1/N\sqrt{1 / N}
α(k) for k≥1\alpha(k) \ \text{for} \ k \geq 1
2/N\sqrt{2 / N}

The k=0k=0 cosine is constant. Therefore X(0)X(0) is the DC coefficient, equal to N\sqrt{N} times the sample mean. Every k≥1k \geq 1 coefficient is an AC coefficient. Its cosine completes k/2k/2 cycles across the samples.

The inverse DCT reconstructs the samples from the coefficients:

x(n)=∑k=0N−1α(k)X(k)cos⁡(2n+1)kπ2Nx(n) = \sum_{k=0}^{N-1} \alpha(k) X(k) \cos\frac{(2n+1)k\pi}{2N}

The forward and inverse DCT retain all information. Reconstruction is exact apart from floating-point rounding.

Orthonormality

The transformation is orthonormal. Its cosine patterns form an orthonormal basis.

  • Every pattern has length 11. Its squared values sum to 11.
  • Any 2 different patterns have dot product 00.

Each coefficient measures only its own pattern.

The transform preserves the sum of squared values:

∑n=0N−1x(n)2=∑k=0N−1X(k)2\sum_{n=0}^{N-1} x(n)^2 = \sum_{k=0}^{N-1} X(k)^2

This lets squared error be measured in either the sample domain or the coefficient domain.

Two-Dimensional DCT

For an N×NN \times N image block f(x,y)f(x, y), the 2D DCT applies the 1D DCT to every row, then to every column.

F(u,v)=α(u) α(v)∑x=0N−1∑y=0N−1f(x,y)cos⁡(2x+1)uπ2Ncos⁡(2y+1)vπ2NF(u, v) = \alpha(u)\,\alpha(v) \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} f(x, y) \cos\frac{(2x+1)u\pi}{2N} \cos\frac{(2y+1)v\pi}{2N}
f(x,y)=∑u=0N−1∑v=0N−1α(u) α(v) F(u,v)cos⁡(2x+1)uπ2Ncos⁡(2y+1)vπ2Nf(x, y) = \sum_{u=0}^{N-1} \sum_{v=0}^{N-1} \alpha(u)\,\alpha(v)\, F(u, v) \cos\frac{(2x+1)u\pi}{2N} \cos\frac{(2y+1)v\pi}{2N}
Here:
x,yx, y
column and row indices
u,vu, v
horizontal and vertical frequency indices
f(x,y)f(x, y)
pixel value at column xx and row yy
F(u,v)F(u, v)

coefficient at horizontal frequency uu and vertical frequency vv

F(0,0)F(0, 0)
DC coefficient, equal to NN times the block mean

A constant block of value cc has F(0,0)=NcF(0, 0) = Nc. Every other coefficient is 00.

For N=8N = 8, α(k)=C(k)2\alpha(k) = \frac{C(k)}{2}, where C(0)=12C(0) = \frac{1}{\sqrt{2}} and C(k)=1C(k) = 1 for k≥1k \geq 1. The forward transform becomes:

F(u,v)=14C(u)C(v)∑x=07∑y=07f(x,y)cos⁡(2x+1)uπ16cos⁡(2y+1)vπ16F(u, v) = \frac{1}{4} C(u) C(v) \sum_{x=0}^{7} \sum_{y=0}^{7} f(x, y) \cos\frac{(2x+1)u\pi}{16} \cos\frac{(2y+1)v\pi}{16}

Matrix Form

Let T\mathbf{T} be the N×NN \times N DCT matrix. Row kk contains the kkth normalized cosine pattern:

T(k,n)=α(k)cos⁡(2n+1)kπ2NT(k, n) = \alpha(k) \cos\frac{(2n+1)k\pi}{2N}

The matrix form is:

F=T f T⊤f=T⊤F T\mathbf{F} = \mathbf{T}\, \mathbf{f}\, \mathbf{T}^\top \qquad \mathbf{f} = \mathbf{T}^\top \mathbf{F}\, \mathbf{T}

T⊤\mathbf{T}^\top is the transpose of T\mathbf{T}. It swaps the rows and columns. Orthonormality gives T−1=T⊤\mathbf{T}^{-1} = \mathbf{T}^\top, which is why the inverse uses the transpose.

  • f[y][x]=f(x,y)\mathbf{f}[y][x] = f(x, y)
  • F[v][u]=F(u,v)\mathbf{F}[v][u] = F(u, v)
  • T\mathbf{T} depends only on NN, so it can be computed once

Basis Functions

The inverse DCT builds a block from N2N^2 fixed cosine patterns:

f(x,y)=∑u=0N−1∑v=0N−1F(u,v) bu,v(x,y)bu,v(x,y)=α(u) α(v)cos⁡(2x+1)uπ2Ncos⁡(2y+1)vπ2Nf(x, y) = \sum_{u=0}^{N-1} \sum_{v=0}^{N-1} F(u, v)\, b_{u,v}(x, y) \qquad b_{u,v}(x, y) = \alpha(u)\,\alpha(v) \cos\frac{(2x+1)u\pi}{2N} \cos\frac{(2y+1)v\pi}{2N}
  • b0,0b_{0,0} is constant
  • bu,vb_{u,v} completes u/2u/2 horizontal cycles and v/2v/2 vertical cycles across the block
  • Higher uu and vv produce faster changes

The coefficients weight these patterns. A coefficient of 00 removes its pattern from the reconstructed block.

∑x,yf(x,y)2=∑u,vF(u,v)2\sum_{x,y} f(x, y)^2 = \sum_{u,v} F(u, v)^2

The 2D transform also preserves the sum of squared values.

Why the DCT Is Useful

  • Neighbouring pixels in natural images usually have similar values. Most energy then concentrates in low-frequency coefficients.
  • Quantization can preserve low-frequency coefficients more accurately than high-frequency coefficients.
  • All DCT coefficients are real. A DFT of a real block is generally complex.
  • The DCT is equivalent to a DFT of an even-symmetric extension. The extension avoids a jump at the block boundary.

Fast Computation

  • Direct evaluation of the 2D sum costs N4N^4 multiplications per block. This is 4096 for N=8N = 8.
  • Row-column evaluation costs 2N32N^3 multiplications. This is 1024 for N=8N = 8.
  • Fast 1D factorisations cost O(Nlog⁡N)O(N \log N) per transform. The AAN algorithm uses 5 multiplications for N=8N = 8 when scale factors are folded into later quantization.

Implementation

Row-column evaluation with a precomputed matrix:

from math import cos, pi, sqrt

def dct_matrix(N):
    T = [[0.0] * N for _ in range(N)]
    for k in range(N):
        a = sqrt(1 / N) if k == 0 else sqrt(2 / N)
        for n in range(N):
            T[k][n] = a * cos((2 * n + 1) * k * pi / (2 * N))
    return T

def matmul(A, B):
    return [[sum(A[i][k] * B[k][j] for k in range(len(B))) for j in range(len(B[0]))]
            for i in range(len(A))]

def transpose(A):
    return [list(row) for row in zip(*A)]

def dct2(f, T):    # F = T f T^t, f[y][x] -> F[v][u]
    return matmul(matmul(T, f), transpose(T))

def idct2(F, T):   # f = T^t F T
    return matmul(matmul(transpose(T), F), T)

Implementation checks:

  • A block of all 55s with N=8N = 8 gives F[0][0]=40F[0][0] = 40 and every other coefficient 00.
  • idct2(dct2(f, T), T) returns f up to floating-point error.
  • The sum of squares of f equals the sum of squares of dct2(f, T).

Worked Example

Constant Block

Find the 2-D DCT of a 2×22 \times 2 block where every value is 55.

Solution Reveal Hide
F(0,0)=12∑x=01∑y=015=10F(0,0) = \frac{1}{2}\sum_{x=0}^{1}\sum_{y=0}^{1} 5 = 10

Every coefficient with u>0u > 0 or v>0v > 0 is 00, since its cosine terms cancel over the constant block.

F=[10000]F = \begin{bmatrix} 10 & 0 \\ 0 & 0 \end{bmatrix}
Written by November 3, 2026 4 min read
Was this helpful?