Data Compression: Lossless (Huffman, LZW) & Lossy (JPEG, MPEG)
Idea in plain words
Need for Compression: Uncompressed 1080p RGB video at 60 fps requires approx 3 Gbps bandwidth, far exceeding standard storage and network channel limits.
Exam tip
High-yield exam topic (Very High).
Explanation
Compression removes spatial, temporal, and statistical redundancies. Lossless Huffman coding assigns variable-length prefix codes based on character frequencies (frequent characters get shortest bit strings). In JPEG, the Discrete Cosine Transform (DCT) converts 8x8 spatial pixel blocks into 64 spatial frequency coefficients: one DC component (average block brightness) and 63 AC components. The Quantization step divides high-frequency coefficients by perceptual thresholds, zeroing out subtle textures human eyes cannot perceive. In MPEG, motion estimation algorithms track moving blocks across time, encoding only motion vectors and small prediction error residuals.
Key points
- Lossless Compression: Perfect mathematical bit-for-bit reconstruction; formats: ZIP, PNG, FLAC; algorithms: Run-Length Encoding (RLE), Huffman, Lempel-Ziv-Welch (LZW).
- Lossy Compression: Irreversible psycho-perceptual omission of imperceptible data; formats: JPEG, MP3, H.264/MPEG-4.
- JPEG Image Compression Pipeline: Color space conversion (RGB -> YCbCr) -> Chroma subsampling (4:2:0) -> 8x8 Block Partitioning -> Discrete Cosine Transform (DCT) -> Quantization -> Zig-zag scanning -> Huffman Entropy Coding.
- MPEG Video Compression Frame Types: I-Frames (Intra-coded, standalone reference), P-Frames (Predicted from past frames), B-Frames (Bi-directional predicted from past and future frames).
Example
Example
Huffman Coding: If character 'E' appears with probability 0.4, it is encoded with a single bit '0', while rare character 'Z' (prob 0.001) receives an 8-bit code '11111110'.
Code examples
/*
JPEG Compression Pipeline:
[RGB Image]
|
v (Color Space Conversion)
[YCbCr (4:2:0 Subsampling)]
|
v (Partition into 8x8 blocks)
[8x8 Spatial Blocks]
|
v (Discrete Cosine Transform)
[8x8 Frequency Coefficients (1 DC + 63 AC)]
|
v (Quantization Matrix: LOSSY STEP - High frequencies zeroed out!)
[Quantized Coefficients]
|
v (Zig-Zag Reordering: clusters trailing zeros together)
[1D Vector: DC, AC1, AC2 ... 0, 0, 0]
|
v (Run-Length & Huffman Coding)
[Compressed JPEG Bitstream]
*/
Exam questions
- [10 Marks] Explain the step-by-step pipeline of JPEG image compression. Which stage is responsible for lossy degradation?
- [10 Marks] Differentiate between I-Frames, P-Frames, and B-Frames in MPEG video compression. Explain how temporal redundancy is eliminated through Motion Estimation.