Image Compression: Techniques, Methods & Applications

TAKEAWAYS:

• Compression reduces file size by exploiting redundancy (repeated data) and irrelevancy (unnecessary details) in images, using lossless (no data loss) or lossy (some data loss) methods.
• Spatial-domain methods (e.g., run-length encoding) work directly on pixel values, while frequency-domain methods (e.g., DCT, wavelet transforms) compress by transforming images into frequency components.
• JPEG uses DCT + quantization + Huffman coding for lossy compression, while PNG uses LZW + filtering for lossless compression.
• Wavelet transforms (e.g., JPEG2000) preserve image edges better than DCT by using multi-resolution analysis.
• Vector quantization groups similar pixels into codewords to reduce storage, commonly used in video compression (MPEG).
• Rate-distortion theory balances compression ratio vs. image quality, critical for real-time apps like WhatsApp image sharing or Daraz product catalogs.

1. Why Compress Images?

• Reduce storage costs (e.g., cloud storage for Daraz).
• Speed up transmission (e.g., WhatsApp image sharing).
• Lower bandwidth usage (e.g., Ncell 4G/5G data plans).

Real-world example:

• WhatsApp uses HEIF (High Efficiency Image Format), which employs wavelet-based compression to store photos in half the size of JPEG while maintaining quality.
• Daraz compresses product images using JPEG to load pages faster, even on slow 3G networks in rural Nepal.

2. Types of Image Compression

Compression methods are classified based on data loss:

Why lossy compression dominates?

• 90% of images on the web (e.g., YouTube thumbnails, Facebook photos) use JPEG because it reduces file size by 5:1 to 10:1 with minimal quality loss.
• Nepal’s NTC compresses satellite images for weather forecasting using lossy methods to save bandwidth.

3. Lossless Compression Techniques

These methods preserve all original data but achieve lower compression ratios (~2:1 to 4:1).

A. Run-Length Encoding (RLE)

• How it works: Replaces sequences of identical pixels with a count + value pair.
• Example: A row of pixels [255, 255, 255, 0, 0, 128, 128, 128, 128, 128] becomes (3,255), (2,0), (5,128).
• Limitations: Ineffective for natural images (few repeated pixels).

Worked Example: RLE on a Simple Image Consider a 1D grayscale image (8 pixels): [50, 50, 50, 75, 75, 75, 75, 75] Compressed form: (3,50), (5,75) Compression ratio: Original = 8 bytes, Compressed = 2 pairs × 2 bytes = 4 bytes → 2:1 compression.

Mermaid Diagram: RLE Process

flowchart LR
    A["Original Pixels: 50,50,50,75,75,75,75,75"] --> B["Detect Runs"]
    B --> C["(3,50)"] --> D["(5,75)"]
    D --> E["Compressed Data"]

B. Huffman Coding

• How it works: Assigns shorter binary codes to frequent symbols (e.g., common pixel values).
• Steps:
  1. Calculate frequency of each pixel value.
  2. Build a Huffman tree (greedy algorithm).
  3. Assign variable-length codes.

Worked Example: Huffman Coding for Pixel Values Suppose we have pixel values with frequencies:

Step 1: Build Huffman Tree

        Root
       /    \
     Node1   Node2
     /  \     /  \
  Leaf(0) Leaf(1) Node3
               /    \
            Leaf(2) Node4
                   /    \
               Leaf(3) Leaf(4,5)

Step 2: Assign Codes

• 0 (most frequent) → 0
• 1 → 10
• 2 → 110
• 3 → 1110
• 4 and 5 → 11110 and 11111

Step 3: Encode a Sequence Original: [0, 1, 2, 3, 4] Encoded: 0 10 110 1110 11110 → 010110111011110 (binary)

Compression Gain: Original (ASCII) = 5 bytes, Huffman = 15 bits (2 bytes) → **2.5:1 compression**.

4. Lossy Compression Techniques

These methods discard less important data for higher compression (~10:1 to 100:1).

A. Discrete Cosine Transform (DCT) – The Heart of JPEG

• How it works:
  1. Divide image into 8×8 blocks.
  2. Apply DCT to convert spatial pixels → frequency coefficients.
  3. Quantize (round) high-frequency coefficients (less visible to human eye).
  4. Encode using Huffman/RLE.

Why DCT?

• Human eyes are less sensitive to high frequencies (fine details, edges).
• Energy compaction: Most information is in low-frequency coefficients.

Worked Example: DCT on an 8×8 Block Consider a simple 8×8 grayscale block (values from 0 to 255). After DCT, the transformed matrix looks like:

Quantization Step: Apply a quantization matrix (e.g., standard JPEG table):

[16, 11, 10, 16, 24, 40, 51, 61]
[12, 12, 14, 19, 26, 58, 60, 55]
...

Divide each coefficient by the corresponding matrix value and round:

• 1200 / 16 = 75 (DC term, kept as-is)
• -50 / 11 ≈ -4.5 → -5 (AC term, quantized)
• 2 / 61 ≈ 0 → 0 (discarded)

Result: Most high-frequency terms become zero, reducing storage.

B. Wavelet Transform (JPEG2000)

• How it works:
  1. Apply multi-level wavelet decomposition (e.g., Haar, Daubechies).
  2. Separate image into approximation (low-frequency) and detail (high-frequency) coefficients.
  3. Quantize and encode.

Advantages over DCT:

• Better edge preservation (wavelets are local, unlike DCT’s blocky artifacts).
• Scalable resolution (can extract thumbnails from full-size images).

Real-world use:

• Google Earth uses wavelet compression to serve high-res satellite images at different zoom levels.
• Nepal’s NTC compresses weather radar images with JPEG2000 to save bandwidth.

Mermaid Diagram: Wavelet Decomposition

flowchart TD
    A["Original Image"] --> B["Wavelet Transform"]
    B --> C["LL: Approximation"]
    B --> D["HL: Horizontal Details"]
    B --> E["LH: Vertical Details"]
    B --> F["HH: Diagonal Details"]
    C --> G["Recursive Decomposition"]
    G --> H["LL1"]
    G --> I["HL1"]
    G --> J["LH1"]
    G --> K["HH1"]

5. JPEG vs. JPEG2000 vs. PNG

Real-world tie-in:

• Daraz uses JPEG for product images (fast loading, acceptable quality).
• Nepal’s NEPSE uses PNG for stock market charts (lossless, sharp lines).
• Pathao uses JPEG2000 for high-res driver ID photos (better quality at small sizes).

6. Vector Quantization (VQ)

• How it works:
  1. Divide image into small blocks (e.g., 4×4).
  2. Find the closest "codeword" from a codebook (predefined set of blocks).
  3. Replace each block with its index in the codebook.

Example:

• Codebook (4 codewords for simplicity):

  Codeword 0: [[255,255,255],[255,255,255]]
  Codeword 1: [[0,0,0],[0,0,0]]
  Codeword 2: [[128,128,128],[128,128,128]]
  Codeword 3: [[255,0,0],[0,255,0]]
  

• Image block: [[254,254,254],[254,254,254]] → Closest to Codeword 0 → Stored as 0.

Applications:

• MPEG video compression (uses VQ for motion compensation).
• Facial recognition systems (e.g., NIDA’s e-Governance uses VQ for template matching).

7. Rate-Distortion Theory

• Goal: Find the optimal compression that balances:
  • Rate (R): Bit rate (lower = better compression).
  • Distortion (D): Difference between original and compressed image (lower = better quality).
• Trade-off: Higher compression → More distortion.
• Mathematical Form: $$D(R)=\text{Minimum distortion achievable at rate }R$$
• Real-world example:
  • WhatsApp uses HEVC (H.265) to minimize distortion at low bit rates for smooth video calls.
  • Ncell’s 4G data plans limit bit rate to reduce distortion for users on slow networks.

Graph: Rate-Distortion Curve Interpretation:

• At low bit rates (R), distortion (D) is high (blurry images).
• At high bit rates, distortion is low (near-lossless quality).

8. Real-World Applications in Nepal

9. Worked Example: Compressing a Real Image (JPEG Pipeline)

Let’s compress a small 8×8 grayscale image (simplified) using JPEG steps:

Original Image (8×8):

[128, 128, 128, 128, 128, 128, 128, 128]
[128, 128, 128, 128, 128, 128, 128, 128]
...
[128, 128, 128, 128, 128, 128, 128, 128]

(Uniform gray → All pixels = 128)

Step 1: DCT Transform

• Since all pixels are identical, DCT produces:
  • DC coefficient (0,0): High (e.g., 1024)
  • All AC coefficients: 0 (no variation)

Step 2: Quantization

• Apply quantization matrix (e.g., all values = 1 for simplicity):
  • DC term: 1024 / 1 = 1024
  • AC terms: 0 / 1 = 0

Step 3: Zigzag Scan + Huffman Encoding

• Only the DC term (1024) is stored (AC terms are zero).
• Huffman encodes 1024 as a short code (e.g., 10000000000).

Final Compressed Data:

• Size: ~1 byte (vs. original 64 bytes) → 64:1 compression (theoretical max for this image).

Real-world tie-in:

• This explains why uniform images (e.g., plain white backgrounds) compress extremely well in JPEG.
• Daraz’s white product backgrounds are optimized for JPEG compression to save storage.

10. Exam Tip: How to Score Full Marks

1. Define clearly:

   • Differentiate lossless vs. lossy with examples (e.g., "PNG is lossless; JPEG is lossy").
   • Explain DCT vs. wavelet in one sentence: "DCT uses fixed 8×8 blocks; wavelets use multi-resolution analysis."

2. Diagrams are mandatory:

   • Draw a Huffman tree or wavelet decomposition in the exam.
   • Sketch a DCT block with quantization matrix.

3. Numerical examples:

   • Solve RLE or Huffman coding for a given pixel sequence.
   • Calculate compression ratio (e.g., "Original: 1000 bytes, Compressed: 200 bytes → 5:1").

4. Compare methods:

   • JPEG vs. PNG: "JPEG is lossy but smaller; PNG is lossless but larger."
   • DCT vs. Wavelet: "Wavelets preserve edges better for medical images."

5. Real-world applications:

   • Link to Nepali companies (e.g., "NTC uses JPEG2000 for satellite images").
   • Mention trade-offs (e.g., "WhatsApp uses HEIF for smaller files but slower encoding").

6. Rate-Distortion Curve:

   • Always plot R (x-axis) vs. D (y-axis) and label axes.
   • Explain: "Lower R → Higher D (more distortion)."

Common Mistakes to Avoid:

• Confusing DCT (JPEG) with wavelet (JPEG2000).
• Forgetting zigzag scan in JPEG encoding.
• Not showing quantization step in DCT compression.
• Ignoring real-world examples (examiners love Nepali apps!).