Motion Compensation from Scratch — Where 90% of Video Compression Happens

What decides where a video codec's bits go isn't the transform or the quantizer — it's the prediction at the front door. What block matching actually minimizes, why motion vectors are not object motion, and how P/B reference structures and GOP boundaries turn into real streaming failures.

A metaphor: sliding a sheet of tracing paper

Picture the previous frame drawn on tracing paper. To draw the next one, the artist doesn't start over. They cut the tracing paper into small pieces, slide each one slightly, lay them down, and paint in only the parts that didn't line up.

The pieces are blocks, the sliding is the motion vector, and the painted-in part is the residual. All motion compensation decides is where to fetch each block's picture from. Whatever doesn't line up is absorbed entirely by the residual.

So motion compensation is judged not by "did it find the true motion?" but by how small it made the residual. Those two sound alike and are not the same thing, and the difference runs through the rest of this article.

What "90%" means here

The 90% in the title isn't a measured share of bits. It's about where the lever is.

A codec is a one-way pipeline: prediction → frequency transform of the residual → quantization → entropy coding. The last three are machines the standard pins down almost completely, but for prediction the standard never specifies how to choose. What it fixes is only the receiver's side of the contract: how a chosen vector is transmitted, and how sub-pixel samples are constructed.

And when the pick is bad, everything downstream collapses with it. If the residual is nearly empty, the transform coefficients are almost all zero; miss, and the residual is about as big as the original picture. Same standard, same bitrate, and yet picture quality differs by encoder. This is essentially why.

For the whole pipeline see Video Compression from Scratch, and for how the residual gets folded up afterwards see JPEG from Scratch. Here we dig into the prediction alone.

Block matching: turning "similar" into a number

To "find the most similar picture," you need similarity as a number. The workhorse, still, is SAD — the sum of absolute differences.

All this says is: take each pixel in block $B$, subtract the value in the previous frame $f_{t-1}$ at a position shifted by $(m_x, m_y)$ from the value in the current frame $f_t$, throw away the sign, and add it all up. The closer to zero, the better the match.

There's a reason for absolute values rather than squares. No multiplies are needed, so SIMD instructions chew through it, and — more importantly — you can bail out early. A sum of absolute values only ever grows, so the moment the running total passes the best score so far, that candidate can be dropped where it stands.

How wide you search is the compute cost. An exhaustive search over a radius of $S$ pixels has $(2S+1)^2$ candidates. Even $S=16$ means 1089 positions, each a 256-pixel subtraction — about 279,000 operations for a single block. A 1080p frame holds 8160 blocks of 16×16, so that's roughly 2.28 billion operations per frame. The square is why you can't be greedy about the radius.

What's actually being minimized is bits

SAD has a blind spot. The residual is about to be frequency-transformed, and SAD never looks at how tall it will stand afterwards. For the same sum of absolute values, a flat residual costs few coefficients while a finely striped one scatters its energy and costs a lot. Hence SATD, which applies a Hadamard transform before summing absolute values.

And what the encoder ultimately minimizes is neither distortion nor bits, but their sum.

$D$ is the block's distortion (how far the prediction missed, measured by SAD or SATD), $R$ is the bits needed to send it (motion vector, mode, and residual together), and $\lambda$ is the tilt of the scale between them. So the equation says: pick not the most similar place, but the cheapest one.

Which leads to the fact that trips everyone up first. Even if SAD is slightly worse, a vector identical to the neighbour's costs almost nothing to send, because vectors are coded as a difference from a predictor. As a result, blocks of flat blue sky or white wall end up with vectors that agree with their neighbours regardless of what actually moved. A motion vector field is not an estimate of object motion; it's a collection of arrows that happened to be cheap.