Also known as DCT. Expresses a sequence of samples as a weighted sum of 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 samples . The output is coefficients , 1 for each cosine pattern. Each gives the amount of the th pattern in the samples.
- sample index
- frequency index
- number of samples
- sample value at index
- coefficient for frequency
The cosine is constant. Therefore is the DC coefficient, equal to times the sample mean. Every coefficient is an AC coefficient. Its cosine completes cycles across the samples.
The inverse DCT reconstructs the samples from the coefficients:
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 . Its squared values sum to .
- Any 2 different patterns have dot product .
Each coefficient measures only its own pattern.
The transform preserves the sum of squared values:
This lets squared error be measured in either the sample domain or the coefficient domain.
Two-Dimensional DCT
For an image block , the 2D DCT applies the 1D DCT to every row, then to every column.
- column and row indices
- horizontal and vertical frequency indices
- pixel value at column and row
-
coefficient at horizontal frequency and vertical frequency
- DC coefficient, equal to times the block mean
A constant block of value has . Every other coefficient is .
For , , where and for . The forward transform becomes:
Matrix Form
Let be the DCT matrix. Row contains the th normalized cosine pattern:
The matrix form is:
is the transpose of . It swaps the rows and columns. Orthonormality gives , which is why the inverse uses the transpose.
- depends only on , so it can be computed once
Basis Functions
The inverse DCT builds a block from fixed cosine patterns:
- is constant
- completes horizontal cycles and vertical cycles across the block
- Higher and produce faster changes
The coefficients weight these patterns. A coefficient of removes its pattern from the reconstructed block.
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 multiplications per block. This is 4096 for .
- Row-column evaluation costs multiplications. This is 1024 for .
- Fast 1D factorisations cost per transform. The AAN algorithm uses 5 multiplications for 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 s with gives and every other coefficient .
idct2(dct2(f, T), T)returnsfup to floating-point error.- The sum of squares of
fequals the sum of squares ofdct2(f, T).
Worked Example
Constant Block
Find the 2-D DCT of a block where every value is .
Solution Reveal Hide
Every coefficient with or is , since its cosine terms cancel over the constant block.