Engineering7 min read
Lossy vs Lossless Compression: An Engineering Deep-Dive
Explore the mathematical foundations of image compression: Discrete Cosine Transform (DCT), Quantization Matrices, DEFLATE, and Huffman Coding.
Lossy vs Lossless Compression: An Engineering Deep-Dive
Image compression is one of the foundational triumphs of computer science and signal processing. Without compression, streaming media, modern websites, and smartphones would be constrained by crippling bandwidth bottlenecks.
1. Lossless Compression Engineering: Preserving Shannon Entropy
Lossless compression guarantees that the decoded output is mathematically bit-for-bit identical to the uncompressed input.
- Entropy Encoding: Claude Shannon’s Information Theory states that data can be compressed up to its theoretical entropy limit.
- LZ77 (Lempel-Ziv): Finds repeated strings of byte data and replaces them with
(distance, length)references. - Huffman Coding: Assigns variable-length binary codes where frequently occurring pixel values receive short bit representations (e.g. 2 bits), while rare colors receive longer bit representations.
2. Lossy Compression Engineering: Human Visual System (HVS) Modeling
Lossy algorithms discard data using psycho-visual models:
- Color Space Transformation ($RGB \rightarrow YCbCr$): Separates brightness from chromatic color.
- Forward Discrete Cosine Transform (FDCT): Transforms 8 × 8 pixel blocks from spatial domain into frequency amplitudes.
- Quantization: Divides frequency coefficients by a quantization matrix and rounds to nearest integers. This step is where data is intentionally discarded.
- Zig-Zag Entropy Ordering: Orders high-frequency zeros together for maximum run-length compression.