Image Compression & Coding: Lossy/Lossless, DCT, JPEG, Run-Length, Huffman

TAKEAWAYS:

• Image compression reduces storage/transmission time by removing redundancy (e.g., Huffman coding assigns shorter bits to frequent pixels).
• Lossless methods (RLE, Huffman) preserve data perfectly, while lossy (DCT, JPEG) sacrifice minor detail for 90%+ size reduction.
• DCT converts spatial redundancy into frequency bands, letting JPEG discard high-frequency noise (e.g., Daraz thumbnails).
• Chroma subsampling (e.g., 4:2:0 in JPEG) reduces color data by 75% with negligible visual loss.
• Entropy coding (Huffman, Arithmetic) maps symbols to variable-length codes for optimal efficiency.
• Wavelet transforms (less common) outperform DCT for textures but require more computation.

1. Why Compress Images? The Problem of Redundancy

Digital images store raw pixel values (e.g., 8 bits/pixel × 1920×1080 = 2.07 MB per RGB image). This is inefficient because:

• Many pixels share similar values (e.g., a blue sky).
• Humans perceive high-frequency noise poorly (e.g., JPEG ignores it).
• Real-world example: WhatsApp compresses photos to <500 KB before sending, saving data costs for users.

Types of Redundancy

graph TD
    A["Image Redundancy"] --> B["Spatial Redundancy"]
    A --> C["Psychological Redundancy"]
    A --> D["Statistical Redundancy"]
    B --> E["Adjacent pixels often identical (e.g., flat regions)"]
    C --> F["Human eye ignores high frequencies (e.g., JPEG artifacts)"]
    D --> G["Frequent pixel values (e.g., 255 for white) can be coded shorter"]

Visual: Below is a 10×10 grayscale image with spatial redundancy (many identical pixels). Compression exploits this.

2. Lossless Compression: Exact Reconstruction

Goal: Reduce file size without losing data. Used for medical images, legal documents, or lossless formats like PNG.

A. Run-Length Encoding (RLE)

• How it works: Replace sequences of identical pixels with (value, count) pairs.
  • Example: 1111100000111 → (1,5),(0,5),(1,3)
• Best for: Images with large uniform regions (e.g., scanned text, line drawings).
• Limitations: Fails on natural images (e.g., a photo of a forest).

Worked Example: Original: 255 255 255 255 255 0 0 0 0 0 0 0 0 0 255 255 RLE: (255,6),(0,7),(255,2)

Visual:

B. Huffman Coding

• How it works: Assigns shorter codes to frequent symbols (e.g., white pixels get 0, rare colors get 1111).
  • Steps:
    1. Count symbol frequencies (e.g., 255:50%, 128:30%, 0:20%).
    2. Build a binary tree where least frequent symbols merge last.
    3. Traverse the tree to assign codes (left=0, right=1).

Visual:

```mermaid
graph TD
    A["Root"] --> B["0 (255)"]
    A --> C["1"]
    C --> D["0 (128)"]
    C --> E["1"]
    E --> F["0 (64)"]
    E --> G["1 (0)"]

Huffman tree for symbols: 255 (50%), 128 (30%), 64 (15%), 0 (15%).

Worked Example:

Original: 255 128 64 0 255 128 → Compressed: 0 10 110 111 0 10 (6 bits vs. 24 bits raw).

Advantages:

• Optimal for symbol frequencies (proven by information theory).
• Used in PNG, TIFF, and ZIP.

Disadvantages:

• Requires frequency analysis (slow for dynamic images).
• Poor for high-entropy images (e.g., a cloudy sky).

3. Lossy Compression: Trading Quality for Size

Goal: Reduce file size by accepting minor quality loss. Used in JPEG, MP3, and video (H.264).

A. Discrete Cosine Transform (DCT)

• How it works:
  1. Divide image into 8×8 blocks.
  2. Apply DCT to convert spatial data into frequency components (like Fourier transform but faster).
  3. Quantize high-frequency coefficients (discard them).
  4. Encode remaining coefficients with Huffman.

Visual: DCT converts this block into coefficients where top-left (DC) is brightness, and top-right (AC) are edges/textures.

Key Insight:

• Humans ignore high frequencies (e.g., fine details in a photo).
• Quantization matrix (e.g., JPEG’s default) weights high frequencies more heavily:

B. Chroma Subsampling

• Why? Human eye is less sensitive to color than luminance.
• Methods:
  • 4:4:4: Full RGB (uncompressed, e.g., PNG).
  • 4:2:0: Store 1/4 chroma data (e.g., YouTube thumbnails).
    • Example: In a 2×2 block, store 1 luminance + 1 chroma instead of 4.
  • 4:2:2: Used in MP4 videos (better quality than 4:2:0).

Visual:

Worked Example:

• Original: 4×4 RGB block = 48 bits (3 channels × 16 pixels).
• 4:2:0: 12 bits (1 Y + 1 Cb + 1 Cr for 4 pixels).
• Loss: Color edges blur slightly (e.g., a red apple’s outline softens).

4. JPEG Standard: Putting It All Together

Steps in JPEG Compression:

flowchart TD
    A["Original Image"] --> B["Divide into 8x8 blocks"]
    B --> C["Apply DCT"]
    C --> D["Quantize (discard high frequencies)"]
    D --> E["Zig-zag scan"]
    E --> F["Run-Length + Huffman Encoding"]
    F --> G["Entropy Coding"]
    G --> H["Store in JPEG file"]

Real-World Tie:

• Daraz product images: Compressed to <200 KB using JPEG 80% quality (lossy) for fast loading.
• WhatsApp photos: Use JPEG + WebP (lossless option) to balance size and quality.

Comparison Table:

5. Advanced Topics

A. Wavelet Transform

• Advantage over DCT: Better for textures (e.g., clouds, fur).
• Disadvantage: Slower to compute.
• Example: Used in JPEG 2000 for medical imaging.

Visual:

B. Entropy Coding

• Huffman vs. Arithmetic Coding:
  • Huffman: Fixed-length codes (e.g., 0, 10, 110).
  • Arithmetic: Variable-length interval mapping (more efficient for long sequences).
    • Example: 0.500000 0.500000 0.500000 0.750000 → 0.500000 0.750000 (compressed).

Worked Example: Original: A A B C C C (frequencies: A=2, B=1, C=3) Arithmetic code: 0.500000 0.750000 (instead of Huffman’s 0 0 1 100 100 100).

In the Real World

1. Daraz Product Images:

   • Idea: JPEG + Chroma Subsampling (4:2:0).
   • How: Daraz’s backend compresses product photos to <200 KB using 80% JPEG quality, balancing loading speed and visual fidelity. Customers see slightly blurred edges (e.g., a shirt’s weave) but fast page loads.

2. WhatsApp Photo Sharing:

   • Idea: Lossless WebP + Lossy JPEG fallback.
   • How: WhatsApp first tries WebP (lossless), then falls back to JPEG 85% quality if the image is complex (e.g., a landscape). This reduces data usage by ~50% for users on slow networks.

3. Ncell’s Mobile Wallpapers:

   • Idea: DCT + Run-Length Encoding.
   • How: Ncell’s app stores wallpapers in JPEG format (lossy) for <100 KB size. Users download them quickly, but high-frequency details (e.g., fine textures in a mountain wallpaper) are slightly lost.

Exam Tip

1. Know the difference between lossless and lossy:

   • Lossless: RLE, Huffman, PNG (exact reconstruction).
   • Lossy: DCT, JPEG, MP3 (quality trade-off).

2. DCT is the backbone of JPEG:

   • Always mention 8×8 blocks, quantization, and chroma subsampling in answers.
   • Example: "JPEG compresses an image by dividing it into 8×8 blocks, applying DCT, quantizing high frequencies, and encoding with Huffman."

3. Worked examples are worth marks:

   • For RLE, show the before/after byte count.
   • For Huffman, draw the tree and assign codes.
   • For JPEG, explain one quantization step (e.g., "Discard 90% of high-frequency coefficients").

4. Compare compression methods:

   • Use a table (like above) to show when to use each method.
   • Example: "Use RLE for scanned documents, but JPEG for photos."

5. Real-world applications:

   • Link Daraz/Daraz, WhatsApp, or Ncell to JPEG/DCT in answers.
   • Example: "Ncell’s mobile app uses JPEG compression to reduce wallpaper sizes, improving download speeds for users with limited data."

6. Avoid vague answers:

   • ❌ "Compression reduces file size."
   • ✅ "JPEG reduces file size by 90% using DCT + quantization, sacrificing high-frequency details that humans perceive poorly."

Final Visual: