JPEG Encoding

Since the eye is less sensitive to chroma variations, we can reduce the resolution of the chroma channels.

Optionally, take each $8 \times 8$ chroma block (i.e. the Cb or Cr channel) and replace it with a $4 \times 4$ block. Each of the "pixels" in a coarser block replaces a $2 \times 2$ set of pixels in the original block, and its value is the average of that set of pixels. This can also be done with a $4 \times 8$ block or an $8 \times 4$ block.

The Discrete Cosine Transform (DCT) is like the Discrete Fourier Transform (DFT), but uses a basis of cosine functions only.

There are several variants of the DCT; JPEGs use the Type-II DCT.

Applying the DCT to an $8 \times 8$ block of pixels results in an $8 \times 8$ block containing the real coefficients of the cosine basis functions, which we can then compress in Step 5.

The cosine basis functions are, for wavenumbers $u$ and $v$, $$S_{uv}(x,y) = \alpha(u)\ \alpha(v)\ \cos{ (2x+1) u \pi \over 2 \times 8 }\ \cos{ (2y+1) v \pi \over 2 \times 8 }$$

where the two 8s above come from the dimensions of the $8 \times 8$ block and $\alpha(u) = {1 \over \sqrt{2}}$ if $u =0$ and $\alpha(u) = 1$ otherwise.

Below are the 64 DCT basis functions, where white is +1, black is -1, and a mid-level grey is 0. You can see sinusoidal patterns in the top row and left column. Note that only half a period is used in these basis functions.

The 64 DCT basis functions are discrete functions that can be precomputed and stored.

To find the DCT coefficients we project the $8 \times 8$ pixel block, $f(x,y)$, onto each of the 64 basis functions, $S_{uv}(x,y)$, in turn. The coefficient for wavenumbers $u$ and $v$ is $$F(u,v) = \sum_{x=0}^7 \sum_{y=0}^7 f(x,y)\ S_{uv}(x,y)$$

The resulting coefficients can be manipulated much like we manipulated Fourier coefficients. In particular, we can suppress high frequency components by setting their coefficients to zero. More on this in Step 6.

Why are we using the DCT instead of the DFT? First, with the DCT, the coefficients are real numbers. Second, with the DCT, there is no discontinuity at period boudaries. The figure below shows, in the top row, how the DFT considers its input to be periodic and, in the bottom row, how the DCT does this. The DCT has no implicit discontinuities, which means that fewer terms in the series are needed to achieve the same accuracy than would be needed if a discontinuity did exist. See the Wikipedia article for more details.

[ Gonzales & Woods figure 8.25 ]

The result from Step 4 is a matrix of coefficients, $F(u,v)$, for each of the Y, Cr, and Cb channels. The low-frequency coefficients are in the upper-left corner of the matrix, and with frequency increasing with distance from that corner (just as with the Fourier Transform).

The $F_\textrm{Y}(x,y)$ matrix is $8 \times 8$, while the $F_\textrm{Cr}(x,y)$ and $F_\textrm{Cb}(x,y)$ matrices might be $8 \times 8$ or $4 \times 4$.

The goal in this step is to make many coefficients zero, so that we can use run-length encoding (RLE) on the zeros.

Since the eye is more sensitive to low frequencies, we can lose more resolution in the high frequencies.

In the context of JPEGs, quantization is the act of removing some of the least-significant bits of a DCT coefficient.

Here are two examples of quantization: $$\begin{array}{rcl} 01100011 & { \div \; 4 \atop \longrightarrow } & 011000 \\ \\ 01100011 & { \div \; 16 \atop \longrightarrow } & 0110 \\ \end{array}$$

We don't have to quantize by powers of two, as long as we round the answer: $$\begin{array}{rcl} 01100011 & { \div \; 19 \atop \longrightarrow } & 0101 \end{array}$$

Above, $99 \; \div \; 19 = 5.21$ which, rounded, is $5$.

Quantization Tables

Quantization

Given the $8 \times 8$ table of quantized coefficients, $\widehat{F}(u,v)$, we now linearize the 64 elements by enumerating them in a zig-zag pattern, as shown below:

[ Alex Khristov on Wikipedia ]

Recall that the low-ferquency components are in the upper-left. This zig-zag pattern collects the component in approximate order of increasing frequency.

Since we expect that many of the high-frequency component will be zero after quantization, there should be a lot of zeroes at the end of this sequence of 64 linearized coefficients. For example, the "Result" matrix shown above is linearized as $$20, 5, -3, -1, -2, -3, 1, 1, -1, -1 0, 0, 1, 2, 3, -2, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\ldots$$

The result of linearization is

• the first integer, which is the DC component
• the remaining 63 integers, which are the AC components.

The DC and AC components from Step 6 are treated differently.

For the DC components:

For the AC components: