Discrete Cosine Transform (DCT)

What is DCT?

The Discrete Cosine Transform (DCT) is a mathematical technique used to transform a signal from the spatial domain to the frequency domain. It’s closely related to the Discrete Fourier Transform (DFT) but uses only real numbers and has better energy compaction properties, making it particularly well-suited for image and audio compression.

Key Idea: DCT expresses a finite sequence of data points as a sum of cosine functions oscillating at different frequencies.

DCT in Image Compression

DCT is a fundamental part of many image compression standards, including JPEG. Here’s how it’s used:

1. Blocking

The original image is divided into small blocks, typically 8x8 pixels.

2. Transformation

DCT is applied to each block independently. This converts the spatial information (pixel intensities) within the block into frequency information (coefficients representing the contribution of different cosine frequencies).

3. Quantization

The DCT coefficients are quantized. This involves dividing each coefficient by a corresponding value from a quantization table and rounding to the nearest integer. This step introduces lossiness but significantly reduces the amount of data needed to represent the image. Higher frequency coefficients (which are less perceptually important) are often quantized more heavily, resulting in many zeros.

4. Entropy Coding

The quantized coefficients are then further compressed using entropy coding techniques like Huffman coding or arithmetic coding. These methods exploit the statistical redundancy in the data (e.g., the prevalence of zeros) to achieve further compression.

5. Reconstruction (Inverse DCT)

To reconstruct the image, the process is reversed:

1. Entropy Decoding: The compressed data is decoded to recover the quantized coefficients.
2. Dequantization: The quantized coefficients are multiplied by the corresponding values from the quantization table.
3. Inverse DCT (IDCT): The IDCT is applied to each block to transform the frequency coefficients back into the spatial domain (pixel intensities).

DCT Equations

1-D DCT (Type-II, most common)

$$X_k=\alpha (k)\sum _{n=0}^{N-1}{x}_n\cos \left[\frac{\pi }{N}\left(n+\frac{1}{2}\right)k\right],k=0,1,\dots ,N-1$$

where:

• $x_n$ is the input signal (e.g., pixel values in a row or column of a block).
• $X_k$ is the $k^{th}$ DCT coefficient.
• $N$ is the length of the signal.
• $\alpha (k)=\{\begin{array}{ll}\sqrt{\frac{1}{N}}& \text{if }k=0\\ \sqrt{\frac{2}{N}}& \text{if }k\ne 0\end{array}$

1-D Inverse DCT (IDCT)

$$x_n=\sum _{k=0}^{N-1}\alpha (k)X_k\cos \left[\frac{\pi }{N}\left(n+\frac{1}{2}\right)k\right],n=0,1,\dots ,N-1$$

2-D DCT (for images)

$$X_{k_1,k_2}=\alpha (k_1)\alpha (k_2)\sum _{n_1=0}^{N_1-1}\sum _{n_2=0}^{N_2-1}{x}_{n_1,n_2}\cos \left[\frac{\pi }{N_1}\left(n_1+\frac{1}{2}\right)k_1\right]\cos \left[\frac{\pi }{N_2}\left(n_2+\frac{1}{2}\right)k_2\right]$$

where:

• $x_{n_1,n_2}$ is the pixel value at position $(n_1,n_2)$ in the block.
• $X_{k_1,k_2}$ is the DCT coefficient at frequency indices $(k_1,k_2)$.
• $N_1$ and $N_2$ are the dimensions of the block (e.g., 8x8).

2-D Inverse DCT (IDCT)

$$x_{n_1,n_2}=\sum _{k_1=0}^{N_1-1}\sum _{k_2=0}^{N_2-1}\alpha (k_1)\alpha (k_2)X_{k_1,k_2}\cos \left[\frac{\pi }{N_1}\left(n_1+\frac{1}{2}\right)k_1\right]\cos \left[\frac{\pi }{N_2}\left(n_2+\frac{1}{2}\right)k_2\right]$$

Basis Images

DCT basis images are the visual representations of the cosine functions used in the DCT. Each basis image corresponds to a specific frequency pair $(k_1,k_2)$.

• Low-frequency basis images: Represent gradual changes in intensity across the block.
• High-frequency basis images: Represent rapid changes in intensity (fine details and edges).

When DCT is applied to an image block, it essentially decomposes the block into a weighted sum of these basis images.

Benefits of DCT over FFT

While both DCT and FFT are used for frequency domain transformations, DCT has several advantages in the context of image compression:

1. Energy Compaction: DCT tends to concentrate the energy (information) of a typical image into a few low-frequency coefficients. This property is crucial for effective compression because it allows us to discard many high-frequency coefficients with minimal perceptual loss. FFT does not have the same level of energy compaction for real-world images.
2. Real-Valued Output: DCT uses only cosine functions and produces real-valued coefficients. FFT involves complex exponentials and results in complex-valued coefficients, which requires more storage.
3. Reduced Blocking Artifacts: Because of its energy compaction and the way it handles boundaries, DCT tends to produce fewer blocking artifacts (visible block boundaries in the reconstructed image) compared to a naive application of FFT in image compression.
4. Computational Efficiency Although there exist fast algorithms for both DCT and FFT, DCT might be slightly faster in certain implementations, especially for the common 8x8 block size.