JPEG compression

JPEG is a clever image compression algorithm that exploits a human perceptual bias and the structure of natural images. It makes a change of basis before encoding so that the rewritten image representation concentrates the signal that humans are most perceptive to, and thus, the remaining details can be discarded without horribly degrading visual fidelity.

A digital image is a mapping from two-dimensional spatial coordinates to pixel values:
$I: D \subset \mathbb{Z}^2 \to \mathcal{C}.$ Here $D$ is a finite grid of pixel locations and $\mathcal{C}$ is the set of possible values. In the $RGB$ model, $\mathcal{C}=\{0,\dots,255\}^3$, representing three 8-bit color channels.

A property of human vision is that we are more sensitive to luminance (brightness) than to chrominance (color differences). Edges and fine detail in brightness are noticeable, while small variations in color are much harder to perceive. JPEG exploits this by separating brightness from color, meaning that instead of working directly in $RGB$, each pixel is converted to the $Y'CbCr$ color space:

$(R,G,B) \rightarrow (Y', C_b, C_r).$

• $Y'$ represents luminance, or perceived brightness.
• $C_b$ measures how blue a pixel is relative to its brightness.
• $C_r$ measures how red it is.

Equivalently, the chroma channels encode how color deviates from the luminance signal: $C_b$ is proportional to $B - Y'$ and $C_r$ to $R - Y'$.

The $RGB \to Y'CbCr$ conversion is linear:

$Y' = 0.299R + 0.587G + 0.114B$

$C_b = 128 + (-0.168736R - 0.331264G + 0.5B)$

$C_r = 128 + (0.5R - 0.418688G - 0.081312B)$

These weights are chosen so that $Y'$ approximates perceived brightness from the $RGB$ primaries used by the image standard, so the coefficients reflect how much each channel contributes to brightness rather than color alone. Green receives the largest weight because human vision is most sensitive in the middle of the visible spectrum, and because fine spatial detail is carried much more strongly there. The constant $128$ shifts chroma values into the standard $0$–$255$ range used by 8-bit images.

Once luminance and chroma are separated, JPEG can reduce the spatial resolution of the chroma channels before applying further compression. This step is called chroma subsampling.

In 4:4:4, every pixel keeps its own chroma values. In 4:2:2, chroma is shared horizontally across neighboring pixels. In 4:2:0, chroma is shared across small $2 \times 2$ neighborhoods. In 4:1:1, chroma is shared across groups of four horizontal pixels.

Because the human visual system is less sensitive to fine color detail, the reconstructed image still looks almost identical even though many chroma samples have been removed.

After chroma subsampling, JPEG no longer stores pixel values directly. Instead, across the $Y'$, $C_b$, and $C_r$ channels, each $8 \times 8$ block is transformed into a weighted sum of cosine waves using the discrete cosine transform (DCT). The coefficient in the top-left represents the average brightness of the block, while coefficients farther to the right or lower down correspond to progressively higher horizontal or vertical spatial frequencies. In the basis functions below, $u$ is the horizontal frequency index and $v$ is the vertical frequency index.

$$B_{u,v}(x,y) \propto \cos\left(\frac{(2x+1)u\pi}{16}\right)\times\cos\left(\frac{(2y+1)v\pi}{16}\right)$$

DCT alone does not reduce the number of stored values: an $8 \times 8$ block still produces $64$ coefficients. What changes is the representation. Because natural images are locally smooth, most of the signal lies in low spatial frequencies. After the transform, a small number of coefficients contain most of the block's energy, while many high-frequency coefficients are close to zero.

When the coefficients are quantized, many high-frequency terms are clipped to $0$. Because the human visual system is less sensitive to fine, high-frequency detail, these coefficients can be discarded with little visible change to the image.

JPEG quantization divides each coefficient by an entry in a quantization matrix and rounds:

$$\hat{C}_{u,v} = \operatorname{round}\!\left(\frac{C_{u,v}}{Q_{u,v}}\right).$$

In practice, $Q$ is usually taken from a standard JPEG luminance quantization table and then scaled by a quality factor. Larger values of $Q_{u,v}$ cause more aggressive rounding. Since the entries of the matrix get larger toward higher spatial frequencies, those coefficients are much more likely to collapse to $0$.

After quantization, JPEG still has to store the remaining coefficients efficiently. It does this by scanning the $8 \times 8$ block in a zigzag pattern so that low frequencies appear first and the long tail of high-frequency zeros gets grouped together.

The first zigzag entry is the DC coefficient, which stores the average brightness of the block and is encoded separately as a difference from the previous block's DC term. The remaining AC coefficients are encoded with symbols of the form $(\mathrm{run}, \mathrm{size})$, where run is the number of zeros before the next nonzero value and size is the bit-width category of that next value. Standard JPEG luminance Huffman tables assign Huffman codes to each symbol, and finally the amplitude bits for the coefficient itself.

After entropy coding, the image file contains a compact description of the DCT coefficients rather than the pixel values themselves. Decoding just runs the same pipeline in reverse. The coefficients are recovered from the entropy codes, rescaled by the quantization matrix, and passed through an inverse DCT to reconstruct each $8 \times 8$ block. The chroma channels are then upsampled, and the image is converted from $Y'CbCr$ back to $RGB$ for display.