How video compression works

Sid Bala’s H.264 is Magic has been going around for the last couple of weeks, and it’s a really good introduction. It made me realize that I’d been using video codecs for fifteen years, from installing dodgy codec packs on Windows XP to arguing about encoding settings for our product’s screen recordings, without ever being able to explain how they work in more than one sentence. So I spent a few evenings with the H.264 spec’s overview sections and Iain Richardson’s book, and this is my attempt at the longer version.

Start with how big the problem is. A 1080p frame is 1920 × 1080, about two million pixels. At 3 bytes per pixel, that’s 6.2 MB a frame, and at 60 frames a second it’s 373 MB a second, almost 3 gigabits. A 1080p stream from Netflix or YouTube is usually somewhere around 5 megabits. So the codec is throwing away something like 599 out of every 600 bits, and you mostly can’t tell.

It does this with a stack of tricks, each of which is fairly simple, and each of which feeds the next one.

Trick 1: throw away color you can’t see

Your eyes are much more sensitive to brightness than to color. So the first thing nearly every video codec does is convert from RGB to a brightness channel (Y, luma) and two color-difference channels (Cb and Cr, chroma), and then store the chroma at lower resolution. The usual scheme is 4:2:0, which means one chroma sample for every 2×2 block of pixels. Brightness stays at full resolution.

That alone takes you from 3 bytes per pixel to 1.5, a 2x saving, and to most people it’s invisible on natural images. (It’s very visible on red text on a blue background, which is why screen recordings sometimes look smeary around colored text. I’ve had that bug filed against us.)

Trick 2: most of a frame is the frame before it

This is the big one. In a typical video, consecutive frames are nearly identical. The background doesn’t move, and the things that do move mostly just shift a few pixels. So instead of storing every frame, you store some frames completely and describe the rest in terms of other frames.

H.264 has three kinds:

• I-frames (intra) are stored on their own, like a still image. You can start decoding from one.
• P-frames (predicted) are described in terms of earlier frames.
• B-frames (bi-directional) can be described in terms of frames before and after them.

The way a P-frame is “described in terms of” an earlier frame is motion compensation. The frame is split into macroblocks, 16 × 16 pixels each. For each macroblock, the encoder searches the reference frame for the block of pixels that looks most like it, and records where it was found as a motion vector, an (x, y) offset.

The match is never perfect, so you also store the residual, the difference between the predicted block and the real one. For a ball moving across a static background, the residual is almost all zeros. For something like water or confetti, it isn’t, which is why those are the classic worst cases for any codec.

H.264 makes this much more flexible than older codecs did. A macroblock can be split into smaller partitions, down to 4 × 4, each with its own vector, so the edge of a moving object doesn’t have to share a vector with the background behind it. Vectors have quarter-pixel precision, interpolated, because real motion doesn’t snap to the pixel grid. And a block can be predicted from any of up to 16 reference frames, which helps with things that disappear and come back, like someone walking behind a pillar.

I-frames use a version of the same trick inside a single frame. Each block is predicted from the already-decoded pixels just above and to the left of it (“continue this edge diagonally”, “repeat the row above”), with nine modes for 4 × 4 blocks (eight directions plus a flat average), and again only the residual is stored.

Trick 3: describe the residual as frequencies

After prediction you’ve got blocks of residual numbers, which are mostly small, but still a lot of numbers. The next step is a transform: rewrite each block as a sum of patterns from smooth to busy, and keep the weights instead of the pixels.

The classic transform is the discrete cosine transform, the same one JPEG uses. H.264 uses a 4 × 4 integer approximation of it (and 8 × 8 in the High profile), chosen so that every decoder computes exactly the same result with no floating point drift. The idea is easiest to see in one dimension. Take a row of 8 pixel values that ramp smoothly from dark to light:

pixels:        100  102  104  108  112  118  124  130
DCT weights:   317.5  -28.1  5.4  -2.3  0.7  -0.6  0.1  -0.7

The first weight is the average brightness (scaled; 317.5 is the mean, 112.25, times √8). The second says “how much does it slope from one end to the other”. The rest describe finer and finer wiggles, and for a smooth row they’re tiny. Keep only the first three, rounded to integers, set the other five to zero, and invert:

kept:          318  -28  5  0  0  0  0  0
reconstructed: 101  102  104  107  113  119  125  128

Every pixel is within 2 of the original, and most are within 1, from three numbers instead of eight. Real image blocks aren’t this smooth, but natural images put most of their energy in the low frequencies, so the pattern holds: a few big numbers in the top-left corner of the block and a lot of near-zeros everywhere else.

Trick 4: quantization, the part that actually loses information

Everything so far is close to reversible. The step that actually throws data away is quantization: divide each weight by a step size and round. Small weights become zero. Big weights become small integers. In H.264 the step size comes from a quantization parameter, QP, between 0 and 51, and the step size doubles every 6 steps of QP.

This is the knob that rate control turns. Want a smaller file? Raise QP, more weights round to zero, the picture gets blockier and blurrier. Encoders typically use a bigger step for the high frequencies than the low ones, since our eyes are less sensitive to errors in fine detail, which is why compressed video loses texture (grass, skin, film grain) long before it loses shapes.

The blockiness is fixed, or at least hidden, by a deblocking filter that smooths across block edges after decoding. In H.264 it’s “in-loop”, meaning the filtered frame is what later frames are predicted from, so it actually helps compression too.

Trick 5: entropy coding

At the end you have motion vectors, mode decisions and quantized weights, mostly zeros and small numbers in fairly predictable patterns. The last stage packs those losslessly into as few bits as possible. H.264 has two options: CAVLC, a set of variable-length codes that adapt to context, and CABAC, an arithmetic coder that adapts its probability model as it goes. CABAC is slower to decode and usually around 10% smaller, and it’s one of the main reasons the Main and High profiles beat Baseline.

Putting it together

The encoder is doing a huge search: for every macroblock, which mode, which partitions, which reference frame, which motion vector, and what QP gives the best quality for the bits. That search is where encoders differ, and why x264 at a “slow” preset makes visibly better video than a hardware encoder at the same bitrate. The decoder, by comparison, is just following instructions, which is why your phone can decode in real time but encoding at quality takes so much longer.

The standard dates from 2003. HEVC, from 2013, does the same things with bigger and more flexible blocks (up to 64 × 64), more intra modes and better filters, for roughly half the bitrate at the same quality, but it’s slow to encode and has a licensing mess that’s slowed adoption. Google’s VP9 is royalty-free and YouTube uses it heavily. And the Alliance for Open Media, which includes Google, Microsoft, Mozilla, Netflix and others, is working on a royalty-free codec of their own, which I’ll believe is a thing when it’s in browsers.