3.3.4 Transform Coding

Transform coding represents a signal not by its sample amplitudes but by coefficients of orthogonal basis functions that describe its frequency content. The original samples are multiplied by each basis function, and the resulting products are summed to produce transform coefficients indicating the contribution of each frequency component.

Figure 3.14 illustrates the process for four samples and four basis functions. If the signal closely resembles a particular basis function, the corresponding coefficient is large; if not, the coefficient is small. In many practical signals, high-frequency components contribute relatively little energy, producing coefficients that are close to zero.

Figure 3.14. A simple illustration of the transform coding procedure.

At the decoder, each basis function is multiplied by its coefficient and the results are summed to reconstruct the signal, as shown in Figure 3.15. Quantizing small high-frequency coefficients to zero provides substantial bit-rate reduction with little perceptible loss. The transform itself does not compress data; compression arises from quantization and entropy coding of the transform coefficients.

Figure 3.15. The inverse transform coding procedure.

3.3.4.1 The Discrete Cosine Transform (DCT)

The discrete cosine transform (DCT) is the most widely used transform in modern image and video compression systems. The DCT converts and N×N block of spatial-domain pixel values into an N×N block of frequency-domain coefficients.

Figure 3.16 shows the 64 basis functions of an 8×8 DCT block; each pattern corresponds to a unique combination of horizontal and vertical spatial frequencies. Light areas represent positive values and dark areas negative ones.

Figure 3.16. Basis functions for a 2-dimensional DCT.

In most natural images, most energy resides in a few low-frequency coefficients near the upper-left corner of the coefficient block. Figure 3.17(a) shows an 8×8-pixel block from a grayscale image, while Figure 3.17(b) shows an image which represents the values of the DCT coefficients for this block. Again, the lighter colored pixels in Figure 3.17(b) indicate positive coefficient values and darker colored pixels indicate negative values. The gray pixels towards the bottom right of the block have values which are close to zero. Each coefficient value shown in Figure 3.17(b) corresponds to the basis function in the same position in Figure 3.16. So, the top left coefficient corresponds to the lowest frequency basis function, and the bottom right coefficient corresponds to the basis function with the highest horizontal and vertical frequency. Notice how only a small number of the low frequency coefficients have large values and most of the high frequency coefficients have values close to zero. After the coefficients have been quantized, only a small number of non-zero low-frequency coefficients are needed to provide a good approximation of the block of pixels. These low-frequency coefficients can be coded using far fewer bits than would be required to represent the block using a binary number for each pixel.

Figure 3.17. (a) An 8×8 block of pixel values. (b) The DCT coefficients for the block of pixel values shown in (a).

Modern video encoders (such as MPEG-2, H.264/AVC, HEVC (H.265), and AV1) combine DCT-based transform coding with motion-compensated prediction, quantization, and entropy coding (typically Huffman coding or arithmetic coding). Together, these techniques routinely achieve compression ratios of 30–50:1 for high-quality visual material