Math Detours · Grade 12 · Connections · 7

How a photo gets ten times smaller

Blocks of pixels, the cosine transform, and throwing away the high frequencies nobody sees. Fourier in your phone.

Name ____________________Date ____________

Tonight's idea

A grey photo is a grid of brightness numbers from 0 to 255. JPEG shrinks it about tenfold by asking not "what is each pixel?" but "which patterns is this patch made of?".

It cuts the image into 8×8 blocks and writes each as a weighted sum of 64 cosine patterns, flat grey to fine checkerboard. The weights are the discrete cosine transform (DCT), a Fourier series for a finite list \(x_0, \ldots, x_{N-1}\). The \(k\)-th pattern is

\[c_k(n) = s_k \cos\frac{\pi(2n+1)k}{2N}, \qquad k = 0, \ldots, N-1,\]

where \(s_0 = \sqrt{1/N}\) and \(s_k = \sqrt{2/N}\) make each pattern a unit vector. The patterns are perpendicular, so each weight is a dot product and the list comes back by summing:

\(X_k = x \cdot c_k\) and \(x = X_0 c_0 + X_1 c_1 + \cdots + X_{N-1} c_{N-1}\).

k = 0: flat 1.00 1.00 1.00 1.00 k = 1: half a wave 0.92 0.38 -0.38 -0.92 k = 2: one wave 0.71 -0.71 -0.71 0.71 k = 3: one and a half 0.38 -0.92 0.92 -0.38
The four patterns for \(N = 4\), sampled at the four pixel centres (orange); the numbers are the cosines before scaling by \(s_k\). Every list of four numbers is a unique mix of them.

Nothing is lost yet. For a block, transform each row, then each column.

Now the saving. Photos are mostly smooth, so high-\(k\) weights are small, and the eye barely registers fine light–dark alternation at pixel scale but notices average brightness. So JPEG quantises: divide each weight by a step size, larger for higher \(k\), and round. Most high-\(k\) weights become 0, and zeros are nearly free.

Watch one: \(N = 4\), \(x = (100, 90, 80, 70)\)

For \(N = 4\) the patterns are \(c_0 = (\tfrac12, \tfrac12, \tfrac12, \tfrac12)\), \(c_1 = (0.653, 0.271, -0.271, -0.653)\), \(c_2 = (\tfrac12, -\tfrac12, -\tfrac12, \tfrac12)\) and \(c_3 = (0.271, -0.653, 0.653, -0.271)\). Pair the end terms to save work:

\[X_0 = 170,\quad X_1 = 0.653(30) + 0.271(10) = 22.30,\quad X_2 = \tfrac12(100 - 90 - 80 + 70) = 0,\quad X_3 = 0.271(30) - 0.653(10) = 1.59.\]

A smooth ramp is almost all \(c_0\) and \(c_1\). Throw \(X_3\) away and rebuild: \(170c_0 + 22.30c_1 = (99.6, 91.0, 79.0, 70.4)\). The largest error is 1 on a scale of 255. Nobody can see it.

Hear and see the same idea for sound at mathdetours.com/demos/fourier.html.

Your turn

  1. (a) Find the four weights of the flat list \((50, 50, 50, 50)\). (b) Check with the decimals that \(c_1 \cdot c_2 = 0\) and \(c_1 \cdot c_3 = 0\).
  2. Transform the sharp edge \(x = (40, 40, 120, 120)\). Which weights are large? Drop \(X_3\), rebuild, and find the four errors. What does this predict about JPEG applied to text or line drawings?
  3. Quantise the ramp's weights \((170, 22.30, 0, 1.59)\) with step sizes \((10, 10, 20, 40)\): divide, round to the nearest whole number, and write down what gets stored. Then multiply back, rebuild, and find the largest error.
  4. (a) An 8×8 block of clear sky has every pixel equal to 200. Which of its 64 weights are nonzero? (b) A block whose eight rows are all the same left-to-right ramp: where in the 8×8 table of weights can nonzero entries appear, and why? (c) For \(N = 4\), show that any symmetric list \((a, b, b, a)\) has \(X_1 = X_3 = 0\) exactly.

Stretch: nothing is lost in the rotation

Show exactly that \(c_1\) is a unit vector (use \(\cos\tfrac{3\pi}{8} = \sin\tfrac{\pi}{8}\)). Then explain why \(\sum x_n^2 = \sum X_k^2\) for every list, and find what fraction of the ramp's total \(\sum x_n^2\) was thrown away with \(X_3\).

Answers

  1. (a) \(X_0 = 4 \times 50 \times \tfrac12 = 100\), and \(X_1 = X_2 = X_3 = 0\): each other pattern has entries summing to zero. (b) \(c_1 \cdot c_2 = \tfrac12(0.653 - 0.271 + 0.271 - 0.653) = 0\); \(c_1 \cdot c_3 = 0.653(0.271) - 0.271(0.653) - 0.271(0.653) + 0.653(0.271) = 0\).
  2. \(X_0 = 160\), \(X_1 = -80(0.653) - 80(0.271) = -73.9\), \(X_2 = 0\), \(X_3 = -80(0.271) + 80(0.653) = 30.6\). The edge puts a large weight on the finest pattern. Rebuilding from \(160c_0 - 73.9c_1\) gives \((31.7, 60.0, 100.0, 128.3)\): errors \(-8, +20, -20, +8\). Dropping high frequencies smears a sharp edge and adds a faint halo either side of it. That is the fuzz around letters in a heavily compressed screenshot.
  3. \(170/10 = 17\), \(22.30/10 = 2.23 \to 2\), \(0\), \(1.59/40 = 0.04 \to 0\). Stored: \((17, 2, 0, 0)\), four small whole numbers, two of them zero. Multiply back to \((170, 20, 0, 0)\) and rebuild: \(170c_0 + 20c_1 = (98.1, 90.4, 79.6, 71.9)\). Largest error 1.9.
  4. (a) Only the top-left weight, the flat pattern: \(8 \times 8 \times 200 \times \tfrac18 = 1600\). All 63 others are zero. (b) Every column is constant, so transforming down the columns leaves only the vertical-frequency-0 entry: nonzero weights can appear only in the top row of the table (and since a ramp is smooth, mostly in its first few entries). (c) \(c_1\) and \(c_3\) are antisymmetric, \(c_k(3 - n) = -c_k(n)\), so against a symmetric list the dot product pairs each term with its negative: \(X_1 = 0.653a + 0.271b - 0.271b - 0.653a = 0\), and the same for \(X_3\). Symmetric content lives entirely in the even patterns: \(X_0 = a + b\), \(X_2 = a - b\).

Stretch. \(|c_1|^2 = \tfrac{2}{4}\left(2\cos^2\tfrac{\pi}{8} + 2\cos^2\tfrac{3\pi}{8}\right) = \cos^2\tfrac{\pi}{8} + \sin^2\tfrac{\pi}{8} = 1\). Writing \(x = \sum X_k c_k\) with the \(c_k\) perpendicular unit vectors, \(x \cdot x = \sum X_k^2\): Pythagoras in four dimensions, or, a rotation does not change length. For the ramp, \(\sum x_n^2 = 29{,}400 = 170^2 + 22.30^2 + 0 + 1.59^2\), and \(1.59^2/29{,}400 \approx 0.00009\): dropping \(X_3\) discards about one part in twelve thousand.

← PreviousNext: Radiocarbon dating →