🗜️ Why Is This Photo Only 500 KB? — JPEG, Huffman & the Art of Forgetting

Ages: 11–15  ·  Duration: 105 minutes  ·  Topics: Image representation, Information theory, Lossless & lossy compression, Human visual perception, Discrete Cosine Transform

Part 0 — Warm-Up: What IS a Picture? (10 min)

The Big Idea

"Your phone takes a photo — 12 megapixels, stunning detail. The raw data is 36 million bytes. But the file you share is 2 million bytes. Somehow, 34 million bytes vanished — and nobody can tell. Where did they go? Today, we find out — and the answer involves physics, psychology, and beautiful mathematics."

Let's start with something basic. What do you see?

You see light. Specifically, electromagnetic radiation — waves with wavelengths between about 380 nm (violet) and 700 nm (red). Your eye has three types of cone cells:

Every colour you've ever seen is your brain's interpretation of how strongly these three cone types fired. A pure yellow light (580 nm) stimulates your L and M cones — but so does a mixture of red and green light. Your brain can't tell the difference!

💡 "This is why screens only need three colours. They're not showing you real yellow — they're tricking your cones with a red–green cocktail."

Quick Practice

Key Rule

A digital image is a rectangular grid of tiny coloured squares called pixels. Each pixel stores three numbers — one for Red, one for Green, one for Blue — each between 0 and 255. That's all. Every photo you've ever taken is just millions of number triplets.

Part 1 — The Raw Truth: BMP and the Cost of Honesty (≈ 15 min)

Setting the Scene

The simplest image format is BMP (Bitmap). It stores every pixel's RGB values with a small header.

Question: A photo from your phone is 4000 × 3000 pixels. At 3 bytes per pixel, how big is it as a raw BMP?

Anatomy of a BMP

┌──────────────────────────────────────────┐
│  BMP Header (14 bytes)                   │
│  File size, offset to pixel data         │
├──────────────────────────────────────────┤
│  DIB Header (40 bytes)                   │
│  Width, height, bits per pixel, etc.     │
├──────────────────────────────────────────┤
│  Pixel Data (width × height × 3 bytes)   │
│  B₁G₁R₁ B₂G₂R₂ B₃G₃R₃ B₄G₄R₄ ...    │
│  (bottom row first, left to right)       │
└──────────────────────────────────────────┘

Fun fact: BMP stores pixels bottom-up and in BGR order (blue first). A quirk from early Windows graphics.

A Tiny Example: A 4×4 Flag

The Key Insight

BMP is perfectly faithful but catastrophically wasteful. The blue pixel (0, 70, 173) appears 12 times. We wrote those same 3 bytes twelve times. Redundancy is an invitation for compression.

Part 2 — The Format Zoo: PNG, GIF, TIFF (≈ 20 min)

The Problem

A 12-megapixel photo is 36 MB as a BMP. We want it smaller — much smaller. But there are two very different philosophies of compression, and each format picks a side.

The Two Philosophies

💡 "Lossless compression is like packing a suitcase perfectly — everything fits, and when you unpack, nothing's missing. Lossy compression is like leaving out the socks nobody will see."

🎨 GIF — The 256-Colour Veteran (1987)

Key idea: Reduce the palette to at most 256 colours, then compress with LZW.

Step 1: Colour quantization. A photo might use millions of colours. GIF picks the best 256 and maps every pixel to the nearest one — each pixel is now one byte instead of three.

Step 2: LZW Compression (Lempel-Ziv-Welch). A dictionary-based method — the encoder builds a dictionary of recurring sequences on the fly:

Input:    A B A B A B A B ...
Step 1:   A → code 0         (dictionary: {A:0, B:1})
Step 2:   B → code 1
Step 3:   AB not in dict → add AB:2, output A(0)
Step 4:   BA not in dict → add BA:3, output B(1)
Step 5:   AB found! ABA not in dict → add ABA:4, output AB(2)
...

The decoder can rebuild the exact same dictionary from the compressed data! No dictionary needs to be transmitted.

The killer feature: Animation! GIF supports multiple frames, making it the internet's favourite looping format for decades.

🖼️ PNG — The Lossless Champion (1996)

Key idea: Keep all colours, predict each pixel, compress the residuals.

PNG applies a prediction filter to each row. Instead of storing raw values, it stores the difference between each pixel and a prediction:

💡 "The filter doesn't compress anything itself. It transforms the data so the actual compressor (DEFLATE) can work more efficiently. Like pre-chewing food for a baby."

The Format Comparison

*GIF's palette reduction is technically lossy, but the compression step itself is lossless.

Dead-End: Why Lossless Isn't Enough

To reach 10:1 or 50:1, we must lose something. JPEG's genius: it throws away precisely what your brain won't miss.

☕ Break (5 min)

Part 3 — The Science of Not Noticing: Human Visual Perception (≈ 10 min)

Weber's Law & Contrast Sensitivity

JPEG is built on psychophysics — the science of how physical stimuli create perceptual experiences.

Weber's Law (1834): The just-noticeable difference (JND) in a stimulus is proportional to the stimulus magnitude. $$\frac{\Delta I}{I} \approx \text{constant} \approx 0.02 \text{ (for brightness)}$$

• In a dark room, you notice a candle.
• In a bright room, you need a spotlight for the same perceived change.
• A ±2 brightness change on a dark pixel (value 10) is very visible.
• A ±2 change on a bright pixel (value 200) is invisible.

Spatial Frequency: Your Eye Has a Resolution Limit

Your eye is not equally sensitive to all detail. Spatial frequency measures how rapidly brightness changes:

At high spatial frequencies (fine detail), your sensitivity drops dramatically. JPEG exploits this ruthlessly.

Colour vs. Brightness: The Chroma Trick

Your eye is far more sensitive to brightness (luminance) than to colour (chrominance). JPEG converts from RGB to YCbCr:

Notice green contributes the most (0.587) — because your M cones (green-sensitive) are the most numerous!

After conversion, JPEG downsamples the Cb and Cr channels — keeping only one colour sample for every four pixels (4:2:0). This cuts the data by a third, and you can barely tell.

💡 "Imagine telling a painter: 'Use detailed brushwork for light and shadow, but slap the colour on roughly.' That's chroma subsampling."

Solution 1 — Run-Length Encoding: The Simplest Trick 🥉

Setup

The simplest compression: if a value repeats, store the value and the count.

Computation

Compress our flag's first row:

Original:  BLUE  BLUE  YELLOW  BLUE
RLE:       2×BLUE  1×YELLOW  1×BLUE

No savings! But the all-yellow row: 4×(254,204,0) = 4 bytes instead of 12 — 3:1 ratio.

Result

Solution 2 — Huffman Coding: Nature's ZIP 🥈

Key Observation

In Morse code, the most common letter (E) gets the shortest code (a single dot). Huffman coding does this optimally: short codes for common symbols, long codes for rare ones.

Shannon's Entropy — The Theoretical Floor

Claude Shannon (1948) defined the minimum average bits per symbol:

Building a Huffman Tree

The algorithm (greedy, bottom-up):

1. Create a leaf node for each symbol with its frequency.
2. Repeat: merge the two lowest-frequency nodes into a parent.
3. When one node remains, that's the root. Left = 0, right = 1.

The Prefix Property

✋ "If black is '0' and grey is '10', how does the decoder know whether '0' is complete or the start of '10'?"

Huffman codes are prefix-free: no code is a prefix of any other. The decoder reads bits left-to-right and decodes unambiguously — no separators needed!

Result

Solution 3 — The Discrete Cosine Transform: Hearing the Image 🥇

Setup

The DCT looks at an image the way a musician looks at a chord — breaking it into component frequencies.

The Fourier Idea

Joseph Fourier (1807) discovered:

Any periodic function can be written as a sum of sines and cosines.

This works for sound (audio frequencies) and images (spatial frequencies).

The 8×8 Block: JPEG's Canvas

JPEG divides the image into 8×8 blocks (64 pixels each) and transforms each independently. Why 8×8? Small enough to be fast, large enough for meaningful frequency content, and $8 = 2^3$ is friendly for fast algorithms.

The DCT Formula

where $C(0) = 1/\sqrt{2}$ and $C(k) = 1$ for $k > 0$.

🗣️ "Don't panic! What matters is what it DOES."

The 64 Basis Patterns

Each coefficient $(u,v)$ corresponds to a cosine "wave pattern." Position $(0,0)$ is the DC coefficient (average brightness). Higher positions = finer detail.

The Key Insight

The DCT doesn't compress anything. It reorganises information so that important parts (low frequencies) separate from unimportant parts (high frequencies). This sets the stage for: throw the unimportant parts away.

💡 "For natural photographs, most high-frequency DCT coefficients are nearly zero. The energy is concentrated in a few low-frequency terms."

Solution 4 — The Full JPEG Pipeline 🎓

The Pipeline

Stage 4: Quantization — The Art of Forgetting

Each DCT coefficient is divided by a value from a quantization matrix and rounded:

The standard JPEG luminance quantization matrix:

Q = │ 16  11  10  16  24  40  51  61 │
    │ 12  12  14  19  26  58  60  55 │
    │ 14  13  16  24  40  57  69  56 │
    │ 14  17  22  29  51  87  80  62 │
    │ 18  22  37  56  68 109 103  77 │
    │ 24  35  55  64  81 104 113  92 │
    │ 49  64  78  87 103 121 120 101 │
    │ 72  92  95  98 112 100 103  99 │

✋ "Top-left values are small (preserve low frequencies). Bottom-right values are large (destroy high frequencies). This IS the psychovisual model."

Stage 5: Entropy Coding

After quantization, the block is full of zeros. JPEG reads coefficients in zigzag order to group zeros together:

 → 1  2  6  7  15 16 28 29
   3  5  8  14 17 27 30 43
   4  9  13 18 26 31 42 44
   10 12 19 25 32 41 45 54
   11 20 24 33 40 46 53 55
   21 23 34 39 47 52 56 61
   22 35 38 48 51 57 60 62
   36 37 49 50 58 59 63 64

Then it applies RLE on zeros + Huffman coding on the remaining values. The DC coefficient stores only the difference from the previous block.

The Full Pipeline on a Smooth Gradient Block

When JPEG Fails

Result

Summary — The Complete Picture

The Compression Spectrum

Key Numbers

Why Multiple Approaches?

The Deeper Message

"JPEG compression is a mathematical theory of what humans don't notice. It's one of the most elegant examples in all of science: understanding perception well enough to exploit it."

Extensions & Challenge Problems 🧩

🥉 Bronze

1. Byte count. A 1920×1080 image has how many pixels? How many bytes as raw BMP? Express in MB.
2. Huffman drill. Build a Huffman tree for ABRACADABRA. What are the codes? Average bits/char?
3. RLE practice. Run-length encode AAABBBCCDDDDDDEE. How many bytes RLE vs. original?

🥈 Silver

4. Shannon entropy. The letters in MISSISSIPPI have frequencies: M=1, I=4, S=4, P=2. Compute $H$. How close does Huffman get?
5. YCbCr conversion. Convert RGB = (255, 128, 0) to YCbCr. What does the large Y tell you?
6. Quantization. Given $F(3,5)=45$ and $Q(3,5)=87$: quantized value? Dequantized? What was lost?

🥇 Gold

7. Huffman optimality. Prove that in an optimal prefix-free code, the two least-probable symbols have equal length and differ only in the last bit.
8. DCT energy. For [100, 102, 101, 103, 100, 101, 102, 100], compute $F(0)$ and the fraction of total energy in the DC term.
9. Why 8×8? What would happen with 4×4 or 16×16 blocks? Discuss frequency resolution, artifacts, and cost.

🎓 Diamond

10. Gibbs phenomenon. Research why truncating a Fourier series causes overshoot near discontinuities. Can you estimate the percentage?
11. Arithmetic coding. Explain why it beats Huffman and why JPEG 2000 switched to it.
12. JPEG vs. wavelets. Why does JPEG 2000's DWT eliminate blocking artifacts?

Answer Key (for instructors)

This lecture was generated for a Math Circle session.