DIP+CV · Programming Exercise

EP05_03 — 🟠 DCT Quantization: The True Source of Compression

5.13.3 EP05_03 🟠 DCT Quantization: The True Source of Compression

A photo gallery application needs to reduce the size of thousands of images before uploading them to the cloud, without recoding everything from scratch. The engineer in charge already has the DCT coefficients for each \(4\times4\) block calculated (the computationally expensive step has already been done) — only the quantization table needs to be applied, the step that actually discards information and generates compression. High-frequency coefficients, which are less perceptible to the human eye, receive large divisors and tend to become zero; low-frequency coefficients, which are more perceptible, receive small divisors and survive almost intact.

You will implement exactly this step: quantize and dequantize (divide, round, multiply back) — the heart of JPEG lossy compression.

5.13.3.1 📋 Implementation Guidelines

  1. Block size: Read the integer \(N\) (\(N \times N\) block).
  2. Coefficients: Read the matrix \(C\) of DCT coefficients, \(N\) rows with \(N\) integers each (they may be negative).
  3. Quantization table: Read the matrix \(Q\), \(N\) rows with \(N\) positive integers each.
  4. Quantization: For each position \((u,v)\), compute the quantized index \[ \tilde{C}(u,v) = \text{round}\!\left(\frac{C(u,v)}{Q(u,v)}\right) \] using standard rounding to the nearest integer (intermediate .5 values never occur in the test cases).
  5. Dequantization (reconstruction): Compute \[ C'(u,v) = \tilde{C}(u,v) \times Q(u,v) \]
  6. Output: Display the reconstructed matrix \(C'\), \(N \times N\), integers.

5.13.3.2 📌 Computational Constraints

  • Complete round-trip: The output is the reconstructed coefficient (\(\tilde{C} \times Q\)), not the isolated quantized index.
  • Floating-point division: The division \(C(u,v)/Q(u,v)\) must be performed in floating point before rounding — truncated integer division will produce an incorrect result.
  • Preserved sign: Negative coefficients retain their sign after quantization and reconstruction.
  • \(Q(u,v) > 0\) always: There is no need to handle division by zero.

5.13.3.3 🧠 Theoretical Background

Coefficient Frequency Typical value of \(Q\) Effect of quantization
\(C(0,0)\) DC (block average) Small Almost always survives — dominates energy
\(C(u,v)\) low \(u+v\) Low frequency Small/medium Partially preserved
\(C(u,v)\) high \(u+v\) High frequency Large Often becomes zero — source of compression

5.13.3.4 📦 Input and Output Specification (VPL)

Input:

  • Line 1: Integer \(N\).
  • The next \(N\) lines: matrix \(C\) (DCT coefficients, integers, may be negative).
  • The next \(N\) lines: matrix \(Q\) (quantization table, positive integers).

Output:

  • Reconstructed matrix \(C'\), \(N \times N\), integers separated by spaces.

5.13.3.5 📌 Examples

Input Output Observation
4
50 10 -5 0
8 -3 2 1
0 1 0 0
2 0 0 -1
2 5 7 8
4 7 8 11
6 8 11 12
9 11 12 14		 50 10 -7 0
8 0 0 0
0 0 0 0
0 0 0 0		 \(C(0,0)=50/2=25 \to 25\times2=50\) (preserved). \(C(0,2)=-5/7\approx-0.71\to-1\to-1\times7=-7\). Meanwhile, \(C(1,1)=-3/7\approx-0.43\to0\): zeroed by quantization — most of the block becomes zero, illustrating the energy compaction in the upper-left corner.
🎮 Simulator EP05_03: DCT Quantization round(C / Q) × Q
Adjust the Q scale and see how many coefficients survive (non-zero) after the round-trip.
DCT Coefficients (C)
Reconstructed (round(C / Q) · Q)
–
Figure 5.34: EP05_03 Simulator: DCT Quantization (round-trip) 
%%writefile EP05_03.cpp
// your solution
Overwriting EP05_03.cpp
TestSuite("EP05_03.cpp").run()
✔️ EP05_03.cases already exists in casos/
📋 5 case(s) loaded from casos/EP05_03.cases

🔍 Testing C++: EP05_03.cpp
⚠️ EP05_03.cpp: Empty file (fewer than 3 lines). Tests skipped.