Lab 9.6 — Motion Estimation & Motion-Compensated Video Processing

← Course 2 syllabus · Bonus Module 9 · Prev: « Lab 9.5

Goal

Go one layer deeper than the video pipeline of Lab 9.5: estimate the motion between frames and use it. Motion estimation is the engine inside every video codec (H.264/HEVC spend most of their compute here) and inside video denoising, frame-rate conversion, and super-resolution. You’ll implement block-matching motion estimation (the codec workhorse) and Lucas–Kanade optical flow (the gradient method), stream real video frames to the Pi 5 / Jetson host-in-the-loop, compute a motion-vector field, and then spend it two ways: motion-compensated prediction (predict the next frame from the previous one + motion, and look at the residual — the thing a codec actually transmits) and motion-compensated temporal filtering (denoise along motion trajectories instead of blurring across them). You verify against OpenCV’s own motion estimators, and measure the prediction gain the motion buys. This is the image → video mathematics of Course 1 Sections 15–17 (the Tekalp motion-estimation companion) turned into a working pipeline.

Equipment & parts

Raspberry Pi 5 (CPU/OpenCV path) and/or Jetson Orin Nano (CUDA path — block matching parallelizes beautifully on the GPU).
Host Mac with numpy opencv-python for streaming, reassembly, and the reference motion estimators.
A short test MP4 with real, structured motion — a camera pan and a moving object (so both global and local motion appear), a few hundred frames at 640×480 / 30 fps.
USB CDC or TCP over Ethernet link (the Lab 9.1 harness rides on either), with the credit-based flow control from Lab 9.1.

Wiring & bench setup

Identical link to Lab 9.5: no MCU, no instruments — wired gigabit Ethernet between the Mac and the Pi 5 / Jetson, TCP carrying the Lab 9.1 frames. Only the payloads change: consecutive frame pairs go out, motion fields come back.

flowchart LR
  MP4["media/in/pan.mp4"]
  HOST["Host: cv2 frame pairs + seq<br/>Lab 9.1 framing + credits"]
  SBC["Pi 5 / Jetson<br/>block-match SAD + LK flow"]
  MV["MV field + confidence<br/>→ quiver, residuals, G_MC"]
  REF["OpenCV reference<br/>PyrLK / Farneback cross-check"]
  MP4 --> HOST
  HOST -- "gray frame pairs" --> SBC
  SBC -- "motion vectors + residual" --> HOST
  HOST --> MV -- "compare" --> REF

flowchart LR
  MP4["media/in/pan.mp4"]
  HOST["Host: cv2 frame pairs + seq<br/>Lab 9.1 framing + credits"]
  SBC["Pi 5 / Jetson<br/>block-match SAD + LK flow"]
  MV["MV field + confidence<br/>→ quiver, residuals, G_MC"]
  REF["OpenCV reference<br/>PyrLK / Farneback cross-check"]
  MP4 --> HOST
  HOST -- "gray frame pairs" --> SBC
  SBC -- "motion vectors + residual" --> HOST
  HOST --> MV -- "compare" --> REF

Safety & don’t-break-it

Data/compute lab; the hazards are correspondence errors, bandwidth, and honest verification:

Motion estimation is ill-posed — respect it. In flat/untextured regions there is no recoverable motion (the aperture problem: only motion normal to an edge is observable). A block matcher will happily return a confident-but-wrong vector there. Gate on a confidence/texture measure (block variance, or the $2\times2$ system’s condition number for LK) rather than trusting every vector.
A video stream overruns a naive link. Same as Lab 9.5: send gray, keep the credit flow control, tag frames with seq. You need consecutive frames correctly ordered — a dropped or reordered frame produces spurious “motion.”
Search range must cover the real motion. A block-match search window of $\pm p$ pixels can only find motion up to $p$; fast motion beyond the window aliases to a wrong vector. Size $p$ to the actual displacement (or go hierarchical — Part D).
Verify on raw frames, not the re-encoded MP4. MP4’s own inter-frame coding will look like your result; score motion vectors and residuals against the OpenCV reference on raw frames, and treat any output video as the human-facing artifact only.

Project & environment setup

No STM32 firmware. Reuse the Lab 9.5 environments unchanged — Pi 5 (python3-opencv + ffmpeg, or venv with opencv-python numpy scipy), Jetson (JetPack’s CUDA/TensorRT/OpenCV), host Mac venv with opencv-python. Device-side code goes in edge/lab-9-6/.

Library roles: cv2.calcOpticalFlowPyrLK / calcOpticalFlowFarneback / cv2.matchTemplate (reference estimators), scipy.ndimage.shift (building $\hat I_t$ from blocks + vectors), numpy ($G_\text{MC}$ / SNR math), matplotlib.pyplot.quiver (MV-field overlay). On the Jetson, cupyx.scipy.ndimage (CuPy, pip install cupy-cuda12x per Lab 9.5) is the drop-in GPU mirror of the scipy.ndimage calls — same API, swap the import; the Pi 5 runs the identical code on CPU SciPy.

If you take the C path on the Pi, give edge/lab-9-6/ a minimal build (you write blockmatch.cpp — the Part B SAD core; OpenCV only does frame I/O):

cmake_minimum_required(VERSION 3.16)
project(lab96 CXX)
find_package(OpenCV REQUIRED)
add_executable(blockmatch blockmatch.cpp)
target_link_libraries(blockmatch ${OpenCV_LIBS})

sudo apt install cmake libopencv-dev on the Pi, then cmake -B build && cmake --build build. The Jetson CUDA variant (blockmatch.cu, one thread per image block) builds with JetPack’s nvcc; add enable_language(CUDA) to the same CMakeLists.

Keep this lab’s reconciliation in host/lab-9-6/analysis.ipynb — the notebook convention — and export final figures next to it.

Where results go:

Artifact	Path
Bench note (G_MC, search + Pi-vs-Jetson tables)	`docs/lab-9-6.md`
Source clip (pan + moving object)	`media/in/pan.mp4`
MV quiver overlay	`host/lab-9-6/quiver.png`
Naive vs. MC residual images	`host/lab-9-6/residuals.png`
MC vs. naive temporal-denoise comparison	`host/lab-9-6/mc-vs-naive.png`
Timing / SAD-count logs	`captures/lab-9-6/timing.csv`
Device-side matcher (Python, C, or CUDA)	`edge/lab-9-6/`

Background

Block matching. Partition frame $t$ into $B\times B$ blocks. For each block, search a window of $\pm p$ pixels in frame $t{-}1$ for the displacement $(u,v)$ that minimizes a matching cost — the sum of absolute differences (SAD) is the codec standard (cheap, no multiply):

\[ \text{SAD}(u,v) = \sum_{(x,y)\in \text{block}} \big|\,I_t(x,y) - I_{t-1}(x{+}u,\,y{+}v)\,\big|, \qquad (\hat u,\hat v) = \arg\min_{|u|,|v|\le p}\text{SAD}(u,v). \]

A full search over the window costs $(2p+1)^2$ SAD evaluations per block — the expensive, exact baseline. Fast searches (three-step, diamond) cut this by orders of magnitude at a small quality cost (Part D).

Lucas–Kanade optical flow. Assume brightness constancy, $I(x,y,t)=I(x{+}u,y{+}v,t{+}1)$, and linearize to the optical-flow constraint $I_x u + I_y v + I_t = 0$. One equation, two unknowns — under-determined per pixel (the aperture problem again). LK adds the assumption that motion is constant over a small window and solves the resulting over-determined system in least squares:

\[ \begin{bmatrix}\sum I_x^2 & \sum I_x I_y\\[2pt] \sum I_x I_y & \sum I_y^2\end{bmatrix} \begin{bmatrix}u\\ v\end{bmatrix} = -\begin{bmatrix}\sum I_x I_t\\[2pt] \sum I_y I_t\end{bmatrix}, \]

the Course 1 Section 1–3 normal equations, one $2\times2$ solve per window. The matrix is exactly the structure tensor; where it is ill-conditioned (an edge or a flat patch) the motion is unobservable — the aperture problem as a rank condition, and the reason corners track and edges don’t.

Motion-compensated prediction — why codecs do this. Predict frame $t$ from frame $t{-}1$ shifted by the estimated motion, $\hat I_t(x,y)=I_{t-1}(x{+}\hat u,\,y{+}\hat v)$, and transmit only the residual $r_t = I_t - \hat I_t$. Good motion makes $r_t$ small and sparse, so it codes in far fewer bits than the frame itself. The prediction gain is measurable as the energy drop from the naive frame-difference to the motion-compensated residual:

\[ G_\text{MC} = 10\log_{10}\frac{\|I_t - I_{t-1}\|^2}{\|I_t - \hat I_t\|^2}\ \text{dB}. \]

Motion-compensated temporal filtering. Averaging consecutive frames denoises ($\sqrt{K}$ SNR gain for $K$ frames) but blurs anything that moved. Averaging along the motion trajectory — $\hat I_t$ instead of $I_{t-1}$ — denoises without the motion blur. This is the multi-frame noise reduction of the Tekalp companion, and the video analog of the coherent averaging of Lab 6.4 / Lyons Ch. 11.

Procedure

Part A — Host: stream consecutive frame pairs.

Reuse the Lab 9.5 MP4 streamer, sending grayscale frames with seq. The device needs frame $t$ and frame $t{-}1$, so either keep the previous frame on-device or send pairs; keep the Lab 9.1 credits so nothing drops.

Part B — Device: block-matching motion field.

On the device, for each $B\times B$ block compute full-search SAD over $\pm p$ and emit the best $(u,v)$. Illustrative core (Pi 5, C or NumPy; the Jetson maps blocks → CUDA threads):

int best = INT_MAX, bu = 0, bv = 0;
for (int v = -p; v <= p; v++)
  for (int u = -p; u <= p; u++) {
    int sad = 0;
    for (int y = 0; y < B; y++)
      for (int x = 0; x < B; x++)
        sad += abs(cur[by+y][bx+x] - prev[by+y+v][bx+x+u]);
    if (sad < best) { best = sad; bu = u; bv = v; }   /* argmin SAD */
  }

Return the motion-vector field (one $(u,v)$ per block) plus a per-block confidence (min-SAD, or block variance). The host overlays it as a quiver plot on the frame.

Part C — Spend the motion: prediction and temporal filtering.

Motion-compensated prediction: on the host (or device), build $\hat I_t$ by shifting each block of $I_{t-1}$ by its motion vector; compute the residual $r_t=I_t-\hat I_t$ and the prediction gain $G_\text{MC}$ against the naive $I_t-I_{t-1}$. Visualize both residuals — the MC residual should be visibly sparser.
Motion-compensated temporal denoising: add noise to the frames, then average $K$ frames along the estimated motion and compare to naive frame averaging on a moving object — quantify the SNR gain and confirm the moving edges stay sharp under MC averaging but smear under naive averaging.

Part D — Cross-check, fast search, and Pi vs. Jetson.

Verify: compare your block-match field against OpenCV template matching / calcOpticalFlowFarneback, and run calcOpticalFlowPyrLK on tracked corners as the LK cross-check. Confirm the fields agree where texture is present and both fail (or flag low confidence) in flat/aperture regions.
Replace full search with a three-step / diamond search and measure the speed-up and the small drop in prediction gain. Then run the whole pipeline on Pi 5 vs. Jetson and report FPS / latency / throughput (the Lab 9.5 methodology) — block matching is embarrassingly parallel, so the Jetson should pull far ahead of the Pi on full search.

Deliverable & expected results

Capture: the motion-vector quiver field, the naive vs. MC residual images + $G_\text{MC}$, the MC-vs-naive temporal-denoise comparison, and the full-vs-fast-search and Pi-vs-Jetson tables.

For a 640×480 gray, $B=16$, $p=16$ source (illustrative — Predicted from the formulas; fill Measured on the bench):

Quantity	Predicted	Measured
Blocks per frame ($40\times30$)	1200	…
Full-search cost / block	$(2p{+}1)^2 = 1089$ SADs	…
Motion-comp prediction gain $G_\text{MC}$	several dB over frame-diff (content-dependent)	…
Aperture regions (flat/edge)	low confidence, unreliable MV	…
MC temporal denoise, $K=4$	$\approx 6$ dB SNR, moving edges sharp	…
Naive $K=4$ averaging	same SNR but motion blur	…
Three-step vs. full search	$$25–50× fewer SADs, small $G_\text{MC}$ loss	…
Jetson vs. Pi 5 (full search)	Jetson ≫ Pi (parallel)	…

Analysis & reconciliation

Confirm the on-device motion field agrees with the OpenCV reference where there is texture, and that both mark the flat/edge regions as unreliable — if your matcher returns confident vectors in a blank sky, your confidence gate is missing, not your search. Reconcile the prediction gain: $G_\text{MC}$ should beat the naive frame difference by several dB on the moving object and by little on the static background (which needs no motion) — a negative gain means the search window is too small for the real displacement (vectors pinned at $\pm p$) or the motion is sub-pixel and needs interpolation. The LK failures should line up with the structure tensor being ill-conditioned — check that the corners track and the long edges slide (the aperture problem, measured, not just described). For temporal filtering, the whole point is visible side-by-side: naive averaging and MC averaging give the same SNR on the static background, but only MC keeps the moving edge sharp — if MC also blurs, the motion estimate is wrong there (verify against the flow field). Finally, the three-step search should give most of the prediction gain at a fraction of the SADs; the residual quality gap is the price of the sub-optimal search, and the Jetson’s lead over the Pi on full search is the parallel-throughput lesson of the whole edge module.

Cross-platform ports & language variants

See the syllabus Implementation tracks. Motion estimation is the module’s clearest block / batched / throughput-bound + learned-adjacent case — and, unlike most of Module 6, it does not map to the STM32 at all (no camera, no frame buffer, and full-search block matching is far past the M4F’s budget). The comparison here is Pi 5 CPU vs. Jetson GPU.

Raspberry Pi 5 (CPU / OpenCV, and Rust). Full-search block matching is $O(\text{blocks}\cdot p^2 \cdot B^2)$ — heavy on a CPU; OpenCV’s optimized matchers or a fast search keep it real-time-ish. The value on the Pi is the classical, explainable pipeline. A Rust port (ndarray + rayon to parallelize across blocks) is a clean way to see the data-parallelism the GPU exploits.

Jetson Orin Nano (CUDA). Block matching is embarrassingly parallel — one CUDA thread (or block) per image block, each doing its own SAD search — so the Jetson’s advantage over the Pi is large and grows with $p$. This is the concrete counterexample to Module 6’s “sequential ⇒ MCU wins” rule: a genuinely parallel vision kernel is exactly what the GPU is for. Batch multiple frame pairs to hide launch overhead (the Lab 8.5 discipline).

No RTOS variant. This lab has no MCU build, so the bare-metal-vs-RTOS axis doesn’t apply; the runtime comparison is Linux-userspace throughput on the two SBCs.

Going further

Hierarchical / pyramidal ME. Estimate coarse motion on a downsampled pyramid and refine — the standard way to capture large motion without a huge search window (the Tekalp Ch. 4 hierarchical method), and how LK handles fast motion.
Sub-pixel accuracy. Interpolate the SAD surface (or the frame) to get half-/quarter-pel vectors — the accuracy H.264/HEVC actually use, and worth a measurable $G_\text{MC}$ bump.
Overlapped / variable block size. Compare fixed $16\times16$ against variable block sizes (the codec’s quadtree) on prediction gain vs. motion-vector overhead — the rate side of the trade.
Frame-rate up-conversion. Use the motion field to interpolate a frame halfway between $t{-}1$ and $t$ (motion-compensated temporal interpolation) and compare against naive frame blending — motion estimation spent on synthesis instead of prediction.
Segmentation from motion. Cluster the motion-vector field to separate the moving object from the panning background (the Tekalp Ch. 5 motion-segmentation idea), a bridge from this lab to tracking.

This is the final lab of Course 2. From Module 0’s power supply to motion estimation on an edge GPU, every result was predicted by hand, built, measured, and reconciled against a reference — the working habit of a DSP embedded / firmware engineer.