Compression and Formats

Compression exploits two kinds of redundancy. Statistical redundancy is structure the data contains and the representation repeats, and removing it is lossless. Perceptual redundancy is detail the viewer will not miss, and removing it is not.

Lossless Compression

Lossless coders guarantee an exact reconstruction. They work by making common patterns short and rare patterns long, which is only possible because natural images are far from random.

Prediction and entropy coding

PNG does not compress pixels directly. It first predicts each pixel from its neighbours and stores the residual, which clusters tightly around zero, and only then hands the result to DEFLATE. The filter choice is made per row, and getting it wrong can double the file size.

Lossy Compression

The DCT and JPEG

JPEG splits the image into eight by eight blocks and transforms each into a set of cosine basis coefficients. Energy concentrates in the low-frequency corner. The coefficients are then divided by a quantisation table, and this single division is where the loss happens. Everything after it is lossless bookkeeping.

1. 01

   Convert to YCbCr and subsample chroma

   Colour resolution is halved, usually in both axes. This alone removes half the data before any transform runs.

2. 02

   Split into blocks and apply the DCT

   Each eight by eight block becomes 64 coefficients ordered from flat to fine detail.

3. 03

   Quantise

   Divide by a table tuned to human sensitivity and round. High-frequency coefficients mostly become zero. The quality slider scales this table.

4. 04

   Zig-zag, run-length and Huffman code

   The zig-zag order groups the zeros together so run-length coding can collapse them into almost nothing.

Figure 7.1

Image prompt

Three panels on a transparent background. Panel one: a single 8 by 8 grid of grey squares with smoothly varying tones. Panel two: the classic 8 by 8 array of DCT basis patterns, each cell containing a distinct grey cosine pattern, increasing in frequency toward the bottom right. Panel three: an 8 by 8 grid where only the top-left corner cells are filled cyan with decreasing intensity and the remaining cells are empty outlines, showing coefficients driven to zero. Thin 1px cell borders, no text, flat vector, 16:7.

Copy

Quality 25Quality 25

Quality 90Quality 90

Image prompt

Two versions of the same photograph for a before and after slider. Subject: a close crop of a red painted door with a brass handle and a soft out-of-focus green background, containing both a hard colour boundary and a smooth gradient. Version A: clean, no visible compression artefacts. Version B: identical framing showing heavy JPEG damage, visible 8 by 8 blocking in the gradient, ringing along the door edge, and red colour bleeding past the boundary. Photographic, identical composition and colour grade between the two, no text, 16:9.

Copy

WebP and AVIF

Newer formats borrow from video coding. They predict blocks from already decoded neighbours before transforming the residual, support variable block sizes rather than a fixed eight by eight, and use arithmetic coding in place of Huffman. The result is smaller files and slower encoding.

Colour Quantisation

Palette formats store an index per pixel and a table of colours. Choosing that table well is the whole problem, because the eye notices a badly placed palette immediately in smooth gradients and skin tones.

Median cut splits the colour cloud along its longest axis, repeatedly, until the required number of boxes exists. It is simple, deterministic, and slightly worse than the alternatives. NeuQuant trains a small self-organising map on a sample of the pixels and generally handles gradients better.

Module 08 turns to execution: where all of this runs, and how to make it run fast enough to feel immediate.