Data Compression
Open in the Padhaiko app5.1 Need for Data Compression
Uncompressed multimedia data—especially digital audio, high-resolution images, and digital video—generates enormous bit volumes that overwhelm storage capacities, disk I/O throughput, and network bandwidth.
For example, of uncompressed Full-HD (, RGB, ) video requires over of storage and a sustained link of , making real-time streaming over standard broadband () impossible without compression. Data compression reduces the number of bits needed to represent information so that multimedia can be stored economically, transmitted quickly within network QoS limits, and played back smoothly in real time.
5.2 Compression Basics
Data Compression & Redundancy
Data compression is the process of encoding information using fewer bits than the original representation by removing redundancy (predictable or repetitive patterns) and/or irrelevancy (details imperceptible to human eyes or ears).
Four Types of Redundancy in Multimedia
- Coding (Statistical) Redundancy: Assigning equal-length codes to symbols that appear with unequal probabilities (e.g.,
eoccurs far more often thanzin English text). - Spatial Redundancy: Strong correlation among neighboring pixels in an image (smooth walls, clear sky) or adjacent samples in audio.
- Temporal Redundancy: High similarity between consecutive frames in a video sequence where only a small foreground object moves against a static background.
- Psycho-Visual / Psycho-Acoustic Redundancy: Visual high-frequency textures or audio frequencies masked by louder neighboring tones that human sensory organs cannot perceive.
Key Compression Metrics
Compression systems can also be symmetric (equal encoding and decoding time, required for live video conferencing) or asymmetric (slow, intensive encoding once; ultra-fast decoding millions of times, ideal for Video-on-Demand and streaming).
5.3 Storage Space
Quantitative comparison of uncompressed vs. compressed storage illustrates why compression is essential across every multimedia building block:
| Media Asset | Uncompressed Parameters | Uncompressed Size | Typical Compressed Size |
|---|---|---|---|
| Plain Text () | , ASCII | (ZIP/DEFLATE) | |
| Raster Image () | True Color RGB | (JPEG ) | |
| CD Stereo Audio () | , , | (MP3 at ) | |
| SD Video (, ) | RGB, | (MPEG-2 / H.264) | |
| HD Video (, ) | RGB, | (H.264 / HEVC) |
5.4 Coding Requirements
Following Steinmetz and Nahrstedt, multimedia compression algorithms must satisfy distinct technical requirements depending on the operating mode:
- General Requirements: High compression ratio with minimal perceptible quality loss, hardware/software independence (standardized bitstreams), low codec complexity, and resilience to bit/packet errors on noisy networks.
- Dialogue Mode (Interactive Communication — e.g., Video Conferencing):
- End-to-end delay must stay below (coding + decoding delay typically ).
- Must be symmetric (real-time encoding and decoding simultaneously).
- Retrieval Mode (Stored Playback — e.g., Video-on-Demand, E-Learning):
- Asymmetric coding is acceptable (encoding can take hours offline, while decoding must run in real time).
- Must support random access, fast-forward, and rewind (requiring periodic intra-coded anchor frames), plus smooth audio–video synchronization.
5.5 Lossless and Lossy Compression techniques
| Aspect | Lossless Compression | Lossy Compression |
|---|---|---|
| Reconstruction | Exact bit-for-bit recovery of original data () | Approximate recovery (); discarded information is permanently lost |
| Typical Compression Ratio | Modest ( to for natural media) | Very high ( to for images, audio, video) |
| Techniques Used | RLE, Huffman, Shannon–Fano, Arithmetic, LZ77 / LZW, DEFLATE | Quantization, DCT, DWT (Wavelets), DPCM, Perceptual Audio/Video coding |
| Target Media | Executable code, text, medical imaging, archival audio (FLAC), PNG, GIF | Photographs (JPEG), streaming audio (MP3/AAC), video (MPEG/H.264) |
Core Lossless Algorithms
- Run-Length Encoding (RLE): Replaces consecutive repetitions of the same symbol with
(symbol, count)pairs (e.g.,AAAAABBBCCA5B3C2). Highly effective on fax scans, solid graphic fills, and trailing zeros in quantized DCT blocks. - Huffman Coding: Builds a binary tree bottom-up by repeatedly merging the two lowest-probability symbols, yielding an optimal instantaneous prefix-free variable-length code where frequent symbols get shorter bit strings.
- Arithmetic Coding: Encodes an entire message as a single fractional sub-interval inside , achieving coding rates arbitrarily close to Shannon entropy without requiring integer bit lengths per symbol.
- Dictionary Coding (LZ77, LZ78, LZW): Replaces repeated substrings with pointers/indices into a dynamically built dictionary (used in ZIP, PNG, GIF, and TIFF).
5.6 Source, Entropy and Hybrid Coding
Steinmetz and Nahrstedt classify multimedia compression algorithms into three fundamental coding families:
| Coding Family | Core Principle | Lossless / Lossy | Typical Methods |
|---|---|---|---|
| Entropy Coding | Treats data purely as a sequence of digital symbols ignoring media semantics; exploits symbol frequencies | Lossless | Run-Length Coding (RLE), Huffman Coding, Arithmetic Coding |
| Source Coding | Exploits semantic properties of the specific medium (spatial/temporal/perceptual characteristics) | Usually Lossy (can be lossless for DPCM) | Prediction (DPCM, DM), Transformation (FFT, DCT), Vector Quantization |
| Hybrid Coding | Combines source coding (transform + quantization) followed by entropy coding (RLE + Huffman/Arithmetic) | Lossy | JPEG, MPEG-1/2/4, H.264, MP3 |
Shannon Entropy and Coding Efficiency
For a discrete memoryless source emitting symbols with probabilities ():
- Source Entropy (Theoretical Lower Bound on Average Bits/Symbol):
- Average Codeword Length () and Coding Efficiency ():
where is the bit length assigned to symbol (by Shannon's source coding theorem, for any uniquely decodable code).
5.7 Lossy Sequential DCT- based Mode
The Baseline Sequential DCT-based Mode is the foundational JPEG image compression pipeline, processing an image in a single left-to-right, top-to-bottom scan through four stages:
Four Stages of Baseline Sequential DCT Compression
- Image Preparation:
- Convert RGB to YCbCr and optionally downsample ().
- Partition each plane into pixel blocks and level-shift unsigned samples by into signed .
- 2D Forward Discrete Cosine Transform (FDCT): Transforms each spatial block into frequency coefficients :
where if , and for .
- (DC coefficient): Proportional to the average brightness of all pixels ().
- for (63 AC coefficients): Represent progressively higher horizontal and vertical spatial frequencies; natural images pack almost all energy near the top-left corner.
- Quantization (The Primary Lossy Step): Each DCT coefficient is divided by its corresponding entry from an Quantization Matrix (with smaller step sizes for low frequencies and larger step sizes for high frequencies) and rounded to the nearest integer:
High-frequency AC coefficients drop to , achieving dramatic data reduction.
- Entropy Encoding:
- DC coefficients are encoded differentially (DPCM) relative to the previous block's DC value.
- AC coefficients are read in a zigzag scan order (from low to high frequency) to collect long runs of trailing zeros, compressed via Zero Run-Length Encoding (RLE), and finalized with Huffman coding.
5.8 Expanded Lossy DCT-based Mode
While baseline sequential JPEG transmits all quantized coefficients of one block before moving to the next, the Expanded (Extended) Lossy DCT-based Mode adds progressive delivery, multi-resolution coding, sample precision, and optional arithmetic coding:
- Progressive DCT Mode: Encodes the image in multiple scans so the entire frame appears quickly as a rough preview and sharpens over successive passes:
- Spectral Selection: The first scan sends only low-frequency DCT bands (e.g., DC + AC indices ); later scans transmit higher-frequency bands () to sharpen edges.
- Successive Approximation: The first scan transmits only the most significant bits (MSBs) of each quantized DCT coefficient; subsequent scans deliver lower-order refinement bits.
- Hierarchical (Pyramidal) Mode: Stores the image at multiple spatial resolutions (e.g., , , and resolution). Low-resolution thumbnail layers are decoded directly, then upsampled to predict the next resolution layer, encoding only the residual difference.
5.9 JPEG and MPEG Compression
JPEG (Joint Photographic Experts Group)
JPEG is the international standard for continuous-tone still images, offering four operational modes:
- Sequential DCT-based (Baseline): samples, Huffman coding, single scan.
- Progressive DCT-based: Multi-scan refinement (spectral selection / successive approximation).
- Hierarchical: Multi-resolution pyramid encoding.
- Lossless Predictive Mode: Uses spatial pixel prediction + Huffman/Arithmetic coding without DCT (rarely used compared to PNG).
MPEG (Moving Picture Experts Group)
MPEG extends JPEG's intra-frame spatial compression with inter-frame temporal compression (Motion Estimation and Motion Compensation) across video frames:
| Frame Type | Coding Method | Reference Frames | Compression & Role |
|---|---|---|---|
| I-Frame (Intra) | Standalone DCT coding (like a JPEG image) | None | Lowest compression; provides random-access seek points and stops error propagation |
| P-Frame (Predicted) | Forward motion vectors ( macroblocks) + residual DCT | Preceding I or P frame | Moderate compression ( smaller than I-frame) |
| B-Frame (Bidirectional) | Motion-compensated interpolation from both past and future references | Preceding and following I or P frames | Highest compression ( smaller than I-frame); cannot be a reference for other frames in MPEG-1/2 |
- Group of Pictures (GOP): A repeating pattern between I-frames (e.g.,
I B B P B B P B Bin display order). Because B-frames depend on a future P-frame, frames are transmitted/decoded in coding order (I P B B P B B ...) rather than display order. - MPEG Standards Overview: MPEG-1 (CD-ROM video at , includes MP3 audio), MPEG-2 (DVD/Digital TV broadcast, interlaced support, ), MPEG-4 (object-based multimedia, H.264/AVC and AAC audio).
Worked Examples
1
A multimedia source emits five symbols with probabilities:
- Construct a Huffman code for the symbols.
- Calculate the source entropy , average codeword length , and coding efficiency .
Build the Huffman tree bottom-up by merging the two smallest probabilities:
- Merge and . Remaining: .
- Merge and . Remaining: .
- Merge and . Remaining: .
- Merge and .
Assign 0 to the left/upper branch and 1 to the right/lower branch at each internal node:
-
0() -
10() -
110() -
1110() -
1111()
Compute source entropy :
Compute average codeword length and efficiency :
- Huffman codes: , , , , .
- , , and coding efficiency .
2
Consider a flat image block whose raw pixel values are all .
- After JPEG level-shifting by , compute the DC DCT coefficient and state all AC coefficients .
- If the quantization table entry at is , compute the quantized DC value and write the resulting RLE-encoded AC stream (End-of-Block
EOB).
Level shift and compute 2D Forward DCT: Subtracting from every pixel gives for all . For , and :
Because the block is completely uniform (zero spatial variation), all higher-frequency AC coefficients are .
Quantize and perform zigzag + RLE encoding:
Every quantized AC coefficient is . After encoding the DC difference separately, the zigzag scan of the AC coefficients encounters only zeros, which JPEG collapses into the single two-symbol End-of-Block marker (0, 0) = EOB.
- , and all AC coefficients .
- Quantized DC value ; AC stream collapses to
EOB(0, 0).
3
An MPEG video stream runs at (, raw RGB) using a Group of Pictures (GOP) in display order:
Suppose average compressed frame sizes are , , and ().
- Write the transmission (coding) order of this GOP.
- Compute the compressed average bit rate in () and the overall compression ratio.
Determine transmission (coding) order: Label frames in display order as (followed by next GOP's ). Each frame needs its future (or next ) frame decoded before it, so the anchor frame is transmitted first:
Calculate GOP size, compressed bit rate, and compression ratio: The -frame GOP contains I-frame, P-frames, and B-frames, spanning :
- Coding order: .
- Compressed bit rate ; compression ratio .
Exercises
Practice Exercises — Data Compression
Distinguish between Source Coding, Entropy Coding, and Hybrid Coding with concrete examples. Explain how multimedia coding requirements differ between dialogue mode and retrieval mode.
Source, Entropy, and Hybrid Coding:
- Entropy Coding (lossless) ignores media semantics and removes statistical/coding redundancy using symbol probabilities (Huffman, Arithmetic, RLE).
- Source Coding (typically lossy) exploits media structure and human perceptual limitations (DPCM, DCT, Wavelets, Vector Quantization).
- Hybrid Coding applies source coding first (transform + quantization) followed by entropy coding (RLE + Huffman), forming the basis of JPEG, MPEG, and MP3.
Dialogue Mode vs. Retrieval Mode Requirements:
- Dialogue Mode (e.g., live video conferencing) demands symmetric real-time encoding/decoding and strict end-to-end latency below (codec delay ).
- Retrieval Mode (e.g., VoD) permits asymmetric codecs (heavy offline encoding, fast real-time playback) and prioritizes fast random access, seek/trick play, and tight stream synchronization.
Entropy coding is lossless statistical coding (Huffman, RLE, Arithmetic), source coding exploits media semantics/perception (DCT, DPCM), and hybrid coding combines both (JPEG, MPEG). Dialogue mode requires symmetric codecs with end-to-end latency, whereas retrieval mode allows asymmetric coding and prioritizes random seek and synchronization.
Trace all stages of Baseline Lossy Sequential DCT-based JPEG compression, explaining the specific purpose of level shifting, 2D DCT, quantization, zigzag scanning, and DPCM on DC coefficients. Also explain how Expanded (Progressive and Hierarchical) DCT modes differ from Sequential mode.
Baseline Sequential DCT Pipeline:
- Preparation & Level Shift: Convert RGB to YCbCr (), divide into blocks, and subtract so pixel values center symmetrically around ().
- 2D FDCT: Concentrates block energy into the single DC average and a few low-frequency AC coefficients.
- Quantization: Divides each coefficient by and rounds—discarding imperceptible high-frequency detail (the primary lossy step).
- DPCM + Zigzag + RLE + Huffman: Neighboring DC coefficients vary smoothly, so DPCM encodes only DC differences; zigzag scanning orders the AC coefficients from low to high frequency so trailing zeros group together for RLE and Huffman coding.
Expanded DCT Modes:
- Progressive Mode transmits multiple scans across the full image using spectral selection (low frequencies first, high frequencies later) or successive approximation (MSBs first, LSB refinement later).
- Hierarchical Mode encodes a multi-resolution image pyramid where lower-resolution layers predict higher-resolution residual layers.
Baseline JPEG performs YCbCr + level shifting 2D DCT (energy compaction) Quantization (lossy high-frequency pruning) DC DPCM + AC Zigzag/RLE + Huffman. Expanded Progressive mode refines the full image across multiple frequency/bit-plane scans, while Hierarchical mode builds a multi-resolution pyramid.
Explain how MPEG achieves high video compression ratios by combining spatial and temporal compression. Define I-frames, P-frames, and B-frames, and explain why MPEG frames are transmitted in a different order than they are displayed.
Spatial + Temporal Compression & Frame Types: MPEG removes spatial redundancy within frames via DCT + quantization (like JPEG) and temporal redundancy between frames via macroblock motion estimation/compensation.
- I-Frame (Intra): Coded independently without temporal references; supports random seeking.
- P-Frame (Predicted): Forward motion-compensated from the prior I or P frame plus DCT of prediction error.
- B-Frame (Bidirectional): Interpolated from both a past and a future I/P reference frame, achieving the highest compression.
Why Coding Order Differs from Display Order: Because a B-frame depends on a future P-frame (or I-frame) in display time, the encoder must transmit and the decoder must reconstruct that future anchor I/P frame before decoding the intervening B-frames (e.g., display I B B P is transmitted as I P B B).
MPEG combines intra-frame DCT (spatial) with inter-frame motion compensation (temporal) using I-frames (independent anchors), P-frames (forward-predicted), and B-frames (bidirectionally predicted). Frames are transmitted in coding order (sending future I/P anchors before B-frames) so the decoder has both reference frames available.
A source emits five symbols with probabilities .
- Construct an optimal Huffman code and list the codeword for each symbol.
- Compute the source entropy , average codeword length , and coding efficiency .
Construct the Huffman tree:
- Merge and . Remaining: .
- Merge and . Remaining: .
- Merge and . Remaining: .
- Merge and .
Assigning 0/1 along each split yields codewords:
Calculate entropy , average length , and efficiency :
- Huffman codes: , , , , .
- , , .
- An uncompressed , RGB image is compressed into a JPEG file (). Compute its uncompressed size in , compression ratio, and percentage space savings.
- Suppose a video at uses an MPEG GOP of length (
I B B P B B P B B P B B). How many I-frames, P-frames, and B-frames appear in the video?
Image compression ratio and space savings:
MPEG GOP frame counts over : Total frames . Number of -frame GOPs . Each GOP has I-frame, P-frames, and B-frames:
- Uncompressed size ; Compression ratio ; Space savings .
- Over ( GOPs): , , and .