How 2D DCT Works in JPEG Compression

This article explains how the Two-Dimensional Discrete Cosine Transform (2D DCT) mathematically maps spatial pixel blocks into the frequency domain within the JPEG compression standard. It details the preprocessing of pixel values, the core algebraic formulation of the transform, the role of orthogonal cosine basis functions, and how the resulting coefficients separate average brightness from detailed edge variations.

Spatial Block Preprocessing

JPEG compression processes an image in non-overlapping blocks of \(8 \times 8\) pixels. For an 8-bit image, spatial pixel values \(P(x, y)\) initially range from \(0\) to \(255\). Before applying the DCT, these values undergo level shifting by subtracting \(128\):

\[f(x, y) = P(x, y) - 128\]

This centers the dynamic range around zero (\(-128\) to \(127\)), reducing dynamic range requirements in subsequent calculations and removing direct-current (DC) offset bias.

The 2D DCT-II Formula

The JPEG standard uses the type-II Discrete Cosine Transform. The mathematical transform from the shifted spatial domain block \(f(x, y)\) to the frequency coefficient matrix \(F(u, v)\) is defined as:

\[F(u, v) = \frac{1}{4} C(u) C(v) \sum_{x=0}^{7} \sum_{y=0}^{7} f(x, y) \cos\left( \frac{(2x + 1)u\pi}{16} \right) \cos\left( \frac{(2y + 1)v\pi}{16} \right)\]

In this equation:

• \(x\) and \(y\) represent the spatial row and column coordinates within the \(8 \times 8\) block (\(x, y \in \{0, 1, \dots, 7\}\)).
• \(u\) and \(v\) represent the horizontal and vertical spatial frequency indices (\(u, v \in \{0, 1, \dots, 7\}\)).
• \(C(u)\) and \(C(v)\) are normalization factors ensuring orthogonality:

\[C(\xi) = \begin{cases} \frac{1}{\sqrt{2}}, & \text{if } \xi = 0 \\ 1, & \text{if } \xi > 0 \end{cases}\]

Projection onto Orthogonal Basis Functions

The double summation computes the inner product between the input block \(f(x, y)\) and 64 predefined, orthogonal 2D cosine basis functions:

\[B_{u,v}(x, y) = \cos\left( \frac{(2x + 1)u\pi}{16} \right) \cos\left( \frac{(2y + 1)v\pi}{16} \right)\]

Each coefficient \(F(u, v)\) measures the degree of cross-correlation between the input pixel block and a specific spatial frequency pattern:

• Horizontal Variation: Controlled by frequency index \(u\).
• Vertical Variation: Controlled by frequency index \(v\).

Because the basis functions are mutually orthogonal, any \(8 \times 8\) block can be reconstructed without redundancy through the inverse process (2D IDCT).

Coefficient Distribution: DC vs. AC

The result of the transform is an \(8 \times 8\) matrix of frequency coefficients:

1. DC Coefficient (\(F(0, 0)\)): When \(u = 0\) and \(v = 0\), the cosine terms evaluate to \(\cos(0) = 1\). The formula simplifies to: \[F(0, 0) = \frac{1}{8} \sum_{x=0}^{7} \sum_{y=0}^{7} f(x, y)\] \(F(0, 0)\) represents eight times the average intensity of the entire \(8 \times 8\) block.

2. AC Coefficients (\(F(u, v)\) where \(u \neq 0\) or \(v \neq 0\)): These 63 coefficients represent alternating current components. Coefficients near the top-left corner represent low-frequency components (gradual gradients), while coefficients toward the bottom-right correspond to high-frequency components (rapid transitions, fine textures, and sharp edges).

Transform Separability

The 2D DCT kernel is mathematically separable because the bivariate basis function factors into two independent single-variable functions:

\[\cos\left( \frac{(2x + 1)u\pi}{16} \right) \cos\left( \frac{(2y + 1)v\pi}{16} \right)\]

This allows the 2D DCT to be computed as a sequence of two 1D DCTs:

1. Apply a 1D DCT horizontally across each of the 8 rows.
2. Apply a 1D DCT vertically down each of the 8 columns of the intermediate result.

Separability reduces the computational complexity from \(\mathcal{O}(N^4)\) operations to \(\mathcal{O}(N^3)\) operations for an \(N \times N\) block, concentrating the spatial energy into a small subset of low-frequency coefficients ready for perceptual quantization.