Image Compression

CSS Optional — Paper-II, Section-B · P-II.V.XII · Syllabus: Image Compression. Numericals are predictable: compression ratio, redundancy, entropy, Huffman coding, run-length coding, PSNR. Theory questions: lossless vs lossy, types of redundancy, JPEG steps.

1. Why Compress?

• A 1-minute uncompressed Full-HD video is ≈ 11.2 GB (see Image Sampling and Quantization, N4). Storage, bandwidth and transmission time all demand compression.
• Compression ratio C = b / b' (original bits ÷ compressed bits).
• Relative data redundancy R = 1 − 1/C (fraction of the original data that was redundant).

2. The Three Types of Redundancy

3. Measuring Information and Quality

• Entropy H = −Σ pk·log₂(pk) bits/symbol — the lower bound on average code length for lossless coding (Shannon's first theorem).
• Average code length Lavg = Σ lk·pk; coding efficiency = H / Lavg.
• Objective fidelity (for lossy): MSE, RMSE, and PSNR = 10·log₁₀(255² / MSE) dB (higher = better; ~30–40 dB is typical good quality).
• Subjective fidelity: human viewers rate quality (excellent / fine / passable / marginal / inferior / unusable).

4. Compression System Model

graph LR
    A["Input image"] --> B["Mapper (transform / prediction / run-length)"]
    B --> C["Quantizer (lossy only)"]
    C --> D["Symbol coder (Huffman / arithmetic)"]
    D --> E["Compressed bit-stream"]
    E --> F["Symbol decoder"]
    F --> G["Inverse mapper"]
    G --> H["Reconstructed image"]

• Mapper reduces inter-pixel redundancy (reversible).
• Quantizer removes irrelevant information — the only irreversible block; omitted in lossless systems. (The decoder has no "inverse quantizer" that recovers lost data.)
• Symbol coder removes coding redundancy (reversible).

5. Lossless vs Lossy

6. Lossless Techniques

• Huffman coding: repeatedly merge the two least probable symbols; assign shorter codes to more probable symbols. Optimal prefix code (no code is a prefix of another → instant decoding).
• Arithmetic coding: encodes a whole message as one number in [0, 1); can beat Huffman when probabilities are not powers of ½.
• LZW (Lempel-Ziv-Welch): builds a dictionary of repeated patterns on the fly; no probabilities needed. Used in GIF, TIFF, PDF.
• Run-length encoding (RLE): store (value, run length) pairs; ideal for binary images and flat regions — fax (CCITT Group 3/4), BMP.
• Bit-plane coding: split into 8 binary planes and run-length/JBIG-code each (high planes compress well).
• Lossless predictive coding: code the difference e = f − f̂ between each pixel and its prediction (e.g. the left neighbour); differences cluster near 0 → low entropy.
• DEFLATE (LZ77 + Huffman): used in PNG and ZIP.

7. Lossy Techniques

• Transform coding: transform blocks (DCT / wavelet) → most energy packs into a few low-frequency coefficients → quantize/discard the rest.
• Lossy predictive coding (DPCM): quantize the prediction error; delta modulation uses a 1-bit quantizer (slope overload and granular noise are its artefacts).
• Wavelet coding: whole-image multiresolution transform → JPEG 2000; no blocking artefacts, supports progressive and region-of-interest decoding.
• Vector quantization and fractal coding (less common).

8. JPEG (Baseline) — Step by Step

1. Convert RGB → YCbCr (luminance + two chroma channels).
2. Chroma subsampling (usually 4:2:0) — the eye is less sensitive to colour detail.
3. Split into 8 × 8 blocks; shift values by −128.
4. Apply the 2-D DCT to each block.
5. Quantize each coefficient: round(DCT / Q-table value) — high frequencies get large steps → many zeros. (The lossy step; the "quality" slider scales the Q-table.)
6. Zig-zag scan to put zeros together.
7. DC coefficients coded by DPCM (difference from previous block); AC coefficients by run-length.
8. Huffman (entropy) coding of the result.

Artefacts at high compression: blocking (visible 8 × 8 squares) and ringing around edges.

9. Standards at a Glance

---

📐 Worked Numericals

N1 — Ratio and redundancy: a 1024 × 1024 8-bit image (1,048,576 bytes) compressed to 131,072 bytes.

• C = 1,048,576 / 131,072 = 8 → 8:1
• R = 1 − 1/8 = 0.875 → 87.5% of the original data was redundant

N2 — Huffman coding (Gonzalez's classic): six symbols with p = 0.4, 0.3, 0.1, 0.1, 0.06, 0.04.

Source reduction (merge the two smallest each time):

1. 0.06 + 0.04 = 0.1 → {0.4, 0.3, 0.1, 0.1, 0.1}
2. 0.1 + 0.1 = 0.2 → {0.4, 0.3, 0.2, 0.1}
3. 0.2 + 0.1 = 0.3 → {0.4, 0.3, 0.3}
4. 0.3 + 0.3 = 0.6 → {0.6, 0.4}

Assign bits back up the tree:

• Lavg = 0.4(1) + 0.3(2) + 0.1(3) + 0.1(4) + 0.06(5) + 0.04(5) = 2.2 bits/symbol
• Entropy H = 0.529 + 0.521 + 0.332 + 0.332 + 0.244 + 0.186 ≈ 2.14 bits/symbol
• Efficiency = 2.14 / 2.2 ≈ 97.4%; vs a 3-bit fixed code, C = 3 / 2.2 ≈ 1.36
• (Ties can be broken differently — other code sets are equally valid if Lavg is the same.)

N3 — Run-length encoding: binary row 0000011100000000 (16 pixels).

• Runs: five 0s, three 1s, eight 0s → 5, 3, 8 (convention: first run is 0s)
• With 4-bit run lengths: 3 × 4 = 12 bits vs 16 raw → C = 16/12 ≈ 1.33

N4 — Predictive (difference) coding: row 100, 102, 103, 103, 105.

• Send first value, then differences: 100, 2, 1, 0, 2
• Differences need only ~2–3 bits instead of 8 → lossless, because the decoder adds them back.

N5 — PSNR: 8-bit image, MSE = 25.

• PSNR = 10·log₁₀(65,025 / 25) = 10·log₁₀(2601) = 10 × 3.415 ≈ 34.2 dB (RMSE = 5)

N6 — Chroma subsampling saving: each 2 × 2 block at 4:2:0 stores 4 Y + 1 Cb + 1 Cr = 6 samples instead of 12 → 50% saving before DCT even starts.

N7 — JPEG quantization: DC coefficient 236 with step 16 → round(14.75) = 15; decoded 15 × 16 = 240 (error 4). A high-frequency coefficient −5 with step 99 → round(−0.05) = 0 → discarded. This rounding is where JPEG loses data.

N8 — Entropy lower bound: four equally likely gray levels → H = log₂4 = 2 bits → no lossless code can average fewer than 2 bits per pixel.

---

🎯 CSS Exam Angle

• "Lossless vs lossy": table + one format and one application for each + the line "the quantizer is the only irreversible step".
• "Types of redundancy": the three-row table with a concrete example of each (a fax page, neighbouring sky pixels, fine colour detail).
• Numericals: Huffman source-reduction table + Lavg + entropy + efficiency is a complete 10-mark answer. Always finish with compression ratio.
• JPEG steps as a numbered list with a small block diagram earns full marks on "explain JPEG compression".

📌 Past CSS Paper Frequency

⚠️ MCQ Traps

• JPEG = lossy; PNG and GIF = lossless (GIF limited to 256 colours).
• Quantization is the lossy step; Huffman and RLE are lossless.
• Entropy is a lower bound on average code length for lossless coding — you cannot beat it.
• Huffman codes are prefix-free; Huffman is optimal only among codes that assign whole bits per symbol.
• LZW is used in GIF/TIFF; DEFLATE in PNG; DCT in JPEG; wavelets in JPEG 2000.
• JPEG converts to YCbCr, not HSI.
• Higher PSNR = better quality; higher compression ratio usually means lower PSNR.
• I-frames are self-contained; B-frames reference both past and future frames.

Self-Check

1. Name the three redundancies and the block of the compression model that removes each.
2. Compute the entropy of p = 0.5, 0.25, 0.125, 0.125. Can Huffman reach it? (Answer: 1.75 bits, yes.)
3. Why is RLE good for fax but poor for photographs?

---

✅ Self-Check (with Answers)

Q1. Define compression ratio and relative redundancy. Compute both for 2 MB compressed to 250 KB.

Ans: C = original / compressed; R = 1 − 1/C. C = 2048/250 ≈ 8.19; R = 1 − 1/8.19 ≈ 0.878 (87.8% redundant).

Q2. Which block of the compression model makes compression lossy?

Ans: The quantizer — it discards information irreversibly. The mapper and symbol coder are reversible, and lossless systems omit the quantizer entirely.

Q3. Why can't Huffman coding go below the entropy?

Ans: Shannon's source-coding theorem: the entropy H is the minimum average number of bits per symbol for any lossless code. Huffman approaches H and equals it only when all probabilities are powers of ½.

Q4. Why does GIF suit a logo but not a photograph?

Ans: GIF is lossless (LZW) but limited to 256 colours. A logo has few flat colours and compresses well; a photo has thousands of colours, so reducing to 256 causes banding/dithering — JPEG suits photos.

Q5. Name the JPEG steps in order.

Ans: RGB → YCbCr and chroma subsampling → 8 × 8 blocks and level shift (−128) → DCT → quantization → zig-zag scan → run-length + Huffman coding.

Q6. How is temporal redundancy removed in video?

Ans: By motion estimation and compensation: only I-frames are coded independently; P-frames store differences from previous frames and B-frames from both previous and next frames, plus motion vectors.

Q7. Compute entropy for four symbols each with probability 0.25.

Ans: H = −4 × 0.25 × log₂0.25 = 2 bits/symbol — a fixed 2-bit code is already optimal.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2018 · Paper-II · Q7(C) and 2025 · Paper-II · Q7(a) · 6 marks each

Q. In the context of compression, differentiate between coding, spatial (inter-pixel) and temporal redundancies.

Ans.

• Compression removes redundant data. There are three main kinds of redundancy.
• Coding redundancy: the code used to represent grey levels is not the shortest possible. A fixed 8 bits for every pixel wastes bits, since frequent levels deserve short codes. Remedy: Huffman or arithmetic coding (variable-length codes).
• Spatial (inter-pixel) redundancy: neighbouring pixels in one image are strongly correlated (large smooth areas), so each pixel can be predicted from its neighbours. Remedy: run-length coding, predictive coding, transform coding (DCT), quadtrees.
• Temporal redundancy: in a video, successive frames are almost identical. Remedy: send only the differences using motion estimation and compensation (MPEG, H.264).
• Psychovisual redundancy (also): details the eye cannot see are discarded (quantisation in JPEG).

2019 · Paper-II · Q6(c) · 6 marks

Q. Describe the step-by-step process of applying a compression-based technique for image segmentation.

Ans.

• Idea: a good segmentation describes the image with the fewest bits (minimum description length). Each region is homogeneous, so it is cheap to encode, and region boundaries are where encoding cost rises.
• Steps:
  • Step 1: Divide the image into small blocks or windows and extract features (colour, texture) for each.
  • Step 2: Model each candidate group of blocks with a simple compressor (a cluster mean, a Gaussian or a texture model) and compute the coding length (bits) of the group.
  • Step 3: Group (cluster) blocks so that the total coding length of the image plus the cost of the region description is minimised. Merge two groups only if the merged code is shorter.
  • Step 4: Repeat merging and splitting until the total cost stops decreasing.
  • Step 5: Label each pixel with its region and clean boundaries (smoothing, morphology).
• Advantage: it needs no preset number of regions, and handles texture. Limit: it is computationally costly.