Video Compression from Scratch — Motion Compensation and the GOP

Compressing thirty separate photographs a second gets nowhere near today's delivery bitrates. Why frame differencing breaks, what a motion vector actually carries, I/P/B frames and the GOP, and what CBR, VBR and CRF each hold constant — ending at the keyframe interval a delivery engineer has to choose.

The metaphor: "same as before, but the man on the left took a step right"

Imagine narrating a security camera feed down a phone line. Nobody describes the whole picture thirty times a second. You say "car park, three white cars" once, and after that it is "same as before, but the man on the left took a step right". Video compression is, at bottom, that idea.

Check the orders of magnitude. 1920×1080 is about 2.07 million pixels; at three bytes each that is 6.2 MB per frame and 186 MB every second at 30 fps — call it 1.5 Gbps. Encode each frame as an independent JPEG and, even at a tenth of the size, you are still near 150 Mbps. Real 1080p delivery usually fits in a pipe two orders of magnitude narrower. Stacking JPEGs does not come close.

What closes the gap is temporal redundancy. Consecutive frames are a thirtieth of a second apart and most pixels keep the value they had. Still-image compression removes redundancy inside a picture; video removes it between pictures, where there is far more of it.

The obvious idea: send the difference

The simplest move is to send the subtraction.

In words: at every pixel position, take the value it has now, subtract the value that same position had one frame ago, and send only what is left over.

$f_t$ is the frame at time $t$ and $d_t$ is the difference — a picture of "what changed since last time". With a tripod-mounted camera and one person walking, it is almost entirely black, glowing only around the person, and a long run of zeros compresses very well.

It collapses the instant the camera moves. Pan by a single pixel and every edge in the frame turns up in the difference. When a subject moves, both the place it left and the place it arrived appear. The content has not changed. It has only shifted.

Motion compensation: sending "where it came from"

If it has only shifted, shift it back before subtracting. That is motion compensation.

Split the frame into blocks (in H.264 the basic unit is a 16×16 macroblock) and, for each one, search the previous frame for the closest-looking patch. The offset you find is the motion vector $(m_x, m_y)$.

Which says, in everyday terms: look up the previous frame not at the same address, but at the one offset by $(m_x, m_y)$ — the spot this block's contents were sitting in a moment ago — and subtract that instead. What survives is only the part that the shift alone cannot account for.

The second term on the right is the prediction — the previous frame, shifted. The $r_t$ on the left is the residual. A 256-pixel block has become two numbers plus whatever little is left over.

The important part is that how you search is outside the standard. The standard fixes how a vector is transmitted and how sub-pixel positions are interpolated (most codecs predict at half- and quarter-pixel precision); finding the vector is the encoder's business. An exhaustive search over radius $S$ costs $(2S+1)^2$ comparisons per block, which becomes impossible very quickly (the complexity article calls this the quadratic wall), so real encoders use hierarchical searches and local searches seeded from neighbouring vectors. When two encoders differ in quality at the same standard and the same bitrate, this is mostly where the difference lives.

The residual is also just an image

So what is $r_t$? An image. If the prediction was good, it is a flat, empty-looking image whose pixels sit near zero.

Which means the image toolkit applies unchanged. The residual is transformed block by block (from H.264 onward with an integer-defined approximation of the DCT, so encoder and decoder never disagree about the inverse), quantized, then entropy coded — the same path as the JPEG article.

Only the input differs. Video compresses well not because its transform or its entropy coder is special, but because the picture entering the transform is already close to empty.