30.2 Video compression and motion compensation⧉
The still-image part of this book taught one compression idea over and over: don't store what the viewer won't miss, and don't store what you can predict. JPEG (Chapter 8.11, File formats and compression) commonly subsamples chroma and quantizes transform coefficients, often more coarsely at high frequencies where errors can be less visible. Video adds a second, far larger redundancy that stills cannot touch: the next frame looks almost exactly like this one. At 30–60 frames per second the camera and the world barely move between frames; most of the picture is already on screen. Coding each frame independently (so-called Motion-JPEG, literally JPEG per frame) ignores this entirely and is wildly wasteful. Inter-frame codecs exploit prediction from decoded references and code residuals along with the information needed to construct that prediction. That is the whole subject.
Correspondence on a budget: motion compensation is optical flow you can afford. A codec needs, for every block, the same thing Chapter 12.8, Optical flow asks (where did this come from in a frame we already have?), but it does not need a physically correct, dense, sub-pixel flow field. It needs a coarse, block-constant correspondence field that is cheap to estimate and, above all, cheap to transmit, and it chooses that field to minimize total bits, not endpoint error. So decades before learned optical flow, video codecs were already estimating dense-ish correspondence at massive scale, optimized for rate, not accuracy. The recurring move: reuse what the decoder already has, and code only the difference. It returns inverted in Chapter 38.3, Motion and video magnification, which keeps the temporal difference instead of discarding it, and it is the rate-aware cousin of the correspondence story in Chapter 12.8, Optical flow.
30.2.1 Why video compresses far better than still × N: temporal redundancy⧉
Here is the single observation the chapter stands on. Take two consecutive frames of a camera on a tripod and subtract one from the other. The difference image $I_t - I_{t-1}$ is near-zero almost everywhere, black except at moving edges, occlusions, and lighting changes. That near-black difference image is the only new information the second frame carries; everything else was already on screen and need not be sent again (Figure 30.2.2). Measured on real clips, coding a tripod clip losslessly takes 3.1 bits per pixel frame by frame and 0.8 as frame differences. When the camera moves, the plain difference stops working: on a clip with real camera motion it takes 4.5 bits per pixel against 4.9 for the frame alone, and with a pan of 1.5 pixels a frame added it costs more than the frame alone on every clip. Compensating for the motion first brings it back down, to 4.05 bits per pixel on the moving clip, for about 0.01 bit per pixel spent on the motion vectors. That is the rest of this chapter.
The naive baseline ignores this. Motion-JPEG codes every frame as an independent JPEG: simple, edit-friendly, randomly accessible at any frame, but it pays the full still-image cost $N$ times and exploits none of the temporal redundancy. It is the "still $\times\,N$" strawman, and inter-frame coding can be much more efficient, with the gain depending strongly on content, quality, and codec settings.
The lever is to stop coding the frame and start coding the surprise. Instead of coding $I_t$, code the residual between $I_t$ and a prediction $\hat I_t$ assembled from already-decoded frames. If the prediction is good the residual is mostly zero, so after the DCT and quantization almost all coefficients vanish, and entropy coding then crushes a block that is nearly all zeros into almost nothing. The slogan is good prediction $=$ small residual $=$ few bits.
Two redundancies are now stacked. Video keeps JPEG's spatial and perceptual redundancy removal (the DCT, chroma subsampling, perceptual quantization, adapted from the same ideas as Chapter 8.11, File formats and compression, with codec-specific transforms and coding tools) and adds temporal redundancy removal on top. The temporal one is the large win.
The only question left is how to build $\hat I_t$. The crude answer, predict $I_t$ by the previous frame $I_{t-1}$ and code $I_t - I_{t-1}$, works when nothing moves but fails the moment anything does: a moving sharp edge sits in a different place in the two frames, so the difference lights up as a bright residual band exactly along every edge, precisely where coding is expensive. The fix is to predict with motion: line each block up with where it actually went, so the residual stays small even as the scene moves. That is motion compensation.
30.2.2 Motion-compensated prediction: the core trick⧉
The idea is geometric and simple. A moving object's block in frame $t$ is, to first order, the same pixels as some block in a reference frame, merely displaced. So for each block we find that displacement, copy the matched patch from the reference as our prediction, and code only what is left over.
The crude delta encoding above (code $I_t - I_{t-1}$, the difference at each fixed pixel) is Eulerian: it watches a stationary grid and asks what changed here. That is exactly why it collapses under motion: a moving edge changes the value at every pixel it sweeps past, so the Eulerian difference lights up everywhere there is movement, precisely where coding is expensive. Motion compensation is the Lagrangian fix: instead of differencing at a fixed location, it follows the content: find where each block went, displace the reference to meet it, and code only the small residual. The whole MPEG / H.264 family is Lagrangian video coding, and it beats Eulerian delta coding for the same reason warping beats per-pixel editing when things move: when the world moves, move with it. (Callback to L29, the Eulerian/Lagrangian split introduced in warping part.)
Macroblocks. Partition the frame into blocks, classically $16\times 16$ luma "macroblocks," though modern codecs use variable sizes down to $4\times 4$. Each block is predicted independently, with its own motion.
Block matching is the correspondence step, and it is exactly the cost-volume search of Chapter 12.8, Optical flow run per block. For a block $B$ in frame $t$, search a window in the reference frame for the best-matching patch and record the offset $(u,v)$, the motion vector:
This cost is the sum of absolute differences (SAD); the sum of squared differences (SSD) is its smooth cousin; the same matching primitive as Chapter 12.8, Optical flow, just summed over a whole block instead of a single pixel's neighborhood. Per block, it is a search over the displacement window for the cheapest match:
for each block B in frame I_t: best = ∞ for (u, v) in search window: sad = ∑_{(x,y) in B} |I_t[x, y] - I_ref[x-u, y-v]| if sad < best: best = sad mv[B] = (u, v) residual[B] = B - I_ref shifted by mv[B]
The search is sped up with hierarchical, coarse-to-fine search and with predicted starting points from neighboring blocks, and sub-pixel motion vectors (half- or quarter-pel, found by interpolating the reference) sharpen the match further. Figure 30.2.3 runs this search on real video.
The prediction is then just the reference frame shifted by that vector,
and the residual, the thing we actually code, is what the prediction missed,
small wherever the match was good.
Transform-code the residual. Apply a codec-defined transform, quantize its coefficients under the chosen quality or quantization-parameter setting, and entropy-code them. This follows the transform/quantize/code pattern of Chapter 8.11, File formats and compression, but modern codecs need not use JPEG’s transform sizes, tables, or entropy coder. The codec transmits, per block, prediction-mode and reference information, motion information, and a coded residual where needed. Skip and merge modes can infer some of these rather than sending them explicitly. (The motion vectors are themselves predictively coded from their neighbors, since they too are spatially correlated; adjacent blocks tend to move together.)
The decoder mirrors the encoder. It decodes the residual, fetches the same reference patch via the transmitted motion vector, and adds them: $\tilde I_t = \hat I_t + \tilde r$. Here tildes denote decoded quantities, including quantization error. One subtlety keeps the two sides in lock-step: the encoder predicts from the reconstructed (lossy) reference the decoder will actually have, not from the pristine original. If it predicted from the original, the small quantization errors would compound frame after frame and the two sides would slowly drift apart; predicting from the reconstruction makes encoder and decoder see the same reference and eliminates drift.
Figure 30.2.1 runs this loop on real video.
I P P P …, a GOP of 16). Each 16 × 16 macroblock of a P frame is predicted from the previous decoded frame by a half-pel motion vector $(u,v)$ found by block matching, and the encoder picks per macroblock whichever of skip (the predicted vector, no residual, one bit), a coded residual $r = I_t - \hat I_t$, or intra coding minimizes $D + \lambda R$. The lower panels show the prediction $\hat I_t$ and the residual (gray is zero, contrast doubled); the mode map colors each macroblock by its choice and draws its vector four times longer. On the subway clip, shaken by the train, a P frame costs about a fifth of an I frame; on the guitar and the sleeping baby nearly every macroblock is skipped and a P frame costs under 1 kbit against 53 to 81 kbit for an I frame. On the zipline, where the camera pans through foliage, a P frame still costs about 60% of an I frame (36 against 59 kbit) and a sixth of its macroblocks are coded intra, a third on the bear in rapids. An intra macroblock's prediction is flat gray, so its residual is the picture itself. Click a column to inspect a frame. Clips from Eulerian Video Magnification Wu et al. 2012, and the zipline and the bear in rapids, the author's.Rate–distortion is the real objective. The encoder does not pick the most accurate motion vector. It picks the one that minimizes
the reconstruction distortion $D$ plus $\lambda$ times the bits $R$ needed to send the vector and its residual. A slightly worse match that codes far cheaper wins outright. This $\min D + \lambda R$ trade-off is the same Lagrangian balance that sets a quantization table's aggressiveness in Chapter 8.11, File formats and compression. It is why the motion field is on a budget: it is optimized for bits, not for physical correctness (Figure 30.2.4).
30.2.3 I, P, and B frames; GOP structure⧉
Not every frame can be predicted from another. You need an entry point with no dependency, and you would like to predict from both directions when you can. Codecs therefore define three frame types, and a frame's type is exactly its place in the prediction graph (Figure 30.2.1).
- I-frame (Intra). Uses intra coding without temporal prediction. Modern intra coding can predict blocks from spatial neighbors before transforming residuals. An intra picture alone does not necessarily reset later reference dependencies; formats distinguish random-access refresh pictures such as H.264 IDR pictures.
- P-frame (Predicted). Allows prediction from a reference list of decoded pictures, plus intra-coded blocks where useful. In a simple chronological GOP these references are earlier frames. Its size depends on content and encoder choices.
- B-frame (Bidirectional). Allows two prediction lists and combinations of predictions. A common case uses a past and a future frame, but modern reference structures are more flexible and a B picture need not use both temporal directions. Bidirectional prediction can reduce residuals, without guaranteeing the smallest frame size. The price is out-of-order decoding: the future reference must already be decoded, so a codec's coding order differs from its display order.
I B B P B B P …). A B frame predicts each macroblock from the anchor before it, the anchor after it, or the average of the two, and no frame is predicted from it. Arrows above the timeline are P-frame references, arrows below are B-frame references, heavy for the selected frame. Because a B frame needs its future anchor, the decode-order row sends each P frame before the B frames that precede it on screen. On the subway clip a B frame costs about half a P frame, the P frames, now three frames from their reference, cost more than with I P P P, and the sequence comes out about 10% smaller overall. On the nearly static clips at high quality the trade reverses: P frames were almost free already, and spacing them three apart costs more than the B frames save. On the zipline and the bear in rapids B frames do not pay either: I B B P comes out 3 to 7% larger than I P P P.GOP (Group of Pictures). The repeating arrangement of these types (for example I B B P B B P …, restarting at the next I-frame) is the GOP, and its length is a direct trade-off:
- short GOP (frequent I-frames) → easy random access and seeking, robust to errors, but bigger files;
- long GOP (rare I-frames) → best compression, but slow seeking and error propagation that lasts until a suitable refresh or recovery point clears the affected dependencies.
In practice streaming and editing favor shorter GOPs (you seek and splice constantly); archival and broadcast push longer GOPs for size. All-intra (I-only) modes also exist, for editing-friendly, frame-accurate video at the cost of size, which is essentially Motion-JPEG with a better intra coder.
30.2.4 Why this is "optical flow on a budget"⧉
State the equivalence plainly, because it is the whole reason this chapter lives next to Chapter 12.8, Optical flow. The field of motion vectors over all the blocks of a frame is a correspondence field: a piecewise-constant, one-vector-per-block approximation to the optical flow between the frame and its reference. Block motion compensation supplies a prediction correspondence field, computed at scale in inter-frame codecs (Figure 30.2.5).
But it is the budget version, and the differences are the point.
- Block-constant, not per-pixel. One vector covers a whole block, even though the true flow varies within it. The residual absorbs the within-block error. The codec does not need the flow to be right, only cheap, because whatever it gets wrong is paid for once, in residual bits.
- Rate-optimal, not accuracy-optimal. The vector is chosen to minimize bits ($D + \lambda R$), so the encoder will happily pick a physically wrong vector when it codes cheaper. A codec's motion field is not a measurement of scene motion; do not read it as ground-truth flow.
- Block-matching, not variational. A simple encoder uses SAD/SSD search, related to Chapter 12.8, Optical flow, without a global smoothness solve. Actual encoders use varied search and mode-decision strategies; the bitstream standard specifies decoding rather than one required search algorithm. What smoothness there is comes implicitly, from predictively coding the vectors and from the rate cost of disagreeing with neighbors.
- Graceful fallback. When prediction is hopeless, as in a scene cut, fast new content, or a large occlusion, the encoder simply codes the block, or the whole frame, intra, degrading gracefully back to the still-image path.
The conceptual bridge runs both ways. The same aperture problem, search window, and sub-pixel interpolation appear in the codec and in flow estimation. Learned optical flow (RAFT and its kin, Teed & Deng 2020; see Chapter 12.8, Optical flow) and learned video codecs both build on this cost-volume correspondence skeleton; the codec just got there first, optimized for a different loss.
The flip side of "graceful fallback" is a failure mode you have certainly seen: when the motion is genuinely unpredictable, as in falling snow, confetti, churning water, or a field of static, there is no good block match anywhere, the residual balloons, and at a fixed bitrate the whole frame smears into mush. It is the most vivid everyday demonstration that video compression depends strongly on predictability, and Tom Scott's popular explainer makes exactly this point (Figure 30.2.6).
30.2.5 Modern codecs in one breath⧉
The lineage is long and the skeleton never changes: Moving Picture Experts Group (MPEG)-1/2 Le Gall 1991 (MPEG) → H.264 / Advanced Video Coding (AVC) (Wiegand, Sullivan, Bjøntegaard and Luthra 2003) → H.265 / High Efficiency Video Coding (HEVC) (Sullivan, Ohm, Han and Wiegand 2012) → AV1 (AOMedia Video 1; AOMedia, 2018) Chen et al. 2018 (AV1) → H.266 / Versatile Video Coding (VVC). Every one of them keeps the same three pieces: motion-compensated block prediction $+$ transform-coded residual $+$ entropy coding. What changes generation to generation is how each piece is implemented, not the architecture.
What they add, on the same bones:
- Variable / recursive block sizes: big blocks for flat, uniform motion, tiny blocks for fine detail, chosen per region.
- Multiple reference frames and better sub-pixel interpolation, so a block can be predicted from whichever past (or future) frame matches best.
- Intra prediction within a frame: predict a block from its already-decoded spatial neighbors using directional modes, so that even I-frames now beat a plain JPEG.
- Richer entropy coders such as CABAC (context-adaptive binary arithmetic coding).
- In-loop deblocking and sample-adaptive filters to hide the block edges that motion compensation and block-transform coding would otherwise leave.
- AV1 additionally brings warped / affine motion (a deliberate step toward true flow), overlapped-block motion compensation, and the practical advantage of being royalty-free.
Decades of codec progress is better prediction plus smarter residual coding inside an unchanged motion-compensation framework, and that framework is correspondence chosen under a bitrate constraint, applied to the temporal axis. Many learned codecs also exploit temporal prediction, but some code conditional latent representations rather than an explicit pixel residual. Predictive block coding explains the major conventional codec families; it is not a definition that covers every possible video representation.
Recap: big lessons of this chapter
Correspondence on a budget: motion compensation is optical flow you can afford. A codec needs, for every block, the same thing Chapter 12.8, Optical flow asks (where did this come from in a frame we already have?), but it does not need a physically correct, dense, sub-pixel flow field. It needs a coarse, block-constant correspondence field that is cheap to estimate and, above all, cheap to transmit, and it chooses that field to minimize total bits, not endpoint error. So decades before learned optical flow, video codecs were already estimating dense-ish correspondence at massive scale, optimized for rate, not accuracy. The recurring move: reuse what the decoder already has, and code only the difference. It returns inverted in Chapter 38.3, Motion and video magnification, which keeps the temporal difference instead of discarding it, and it is the rate-aware cousin of the correspondence story in Chapter 12.8, Optical flow.
The crude delta encoding above (code $I_t - I_{t-1}$, the difference at each fixed pixel) is Eulerian: it watches a stationary grid and asks what changed here. That is exactly why it collapses under motion: a moving edge changes the value at every pixel it sweeps past, so the Eulerian difference lights up everywhere there is movement, precisely where coding is expensive. Motion compensation is the Lagrangian fix: instead of differencing at a fixed location, it follows the content: find where each block went, displace the reference to meet it, and code only the small residual. The whole MPEG / H.264 family is Lagrangian video coding, and it beats Eulerian delta coding for the same reason warping beats per-pixel editing when things move: when the world moves, move with it. (Callback to L29, the Eulerian/Lagrangian split introduced in warping part.)