Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 46 ยท Detection, Segmentation and Video

Motion, Optical Flow and Tracking

Detect motion with frame differencing and background subtraction, estimate optical flow with Lucas-Kanade, then track objects with a centroid tracker and a Kalman filter.

A video is a stack of images over time, and time adds new questions. What moved? How fast and in which direction? Is the blob in this frame the same car as the blob in the previous one? Everything so far in this course treated one image at a time; here you will use several frames to answer these questions. A video frame is just a NumPy array like any other (see Images as Arrays), so the first techniques need nothing more than subtraction.

This lesson covers four steps, from cheap to smart: frame differencing and background subtraction to find where something changed, optical flow to measure how pixels move, a centroid tracker to give each object a persistent identity, and the Kalman filter idea to smooth noisy tracks and bridge gaps when the detector misses an object. All demos use small synthetic frames so that you can see every number.

flowchart LR
    A["video frames"] --> B["find motion<br/>differencing,<br/>background model"]
    A --> C["measure motion<br/>optical flow"]
    B --> D["detections<br/>blobs, boxes"]
    D --> E["tracker<br/>associate over time"]
    E --> F["filter<br/>smooth and predict"]

A typical motion pipeline. Detection finds things in each frame, tracking links them across frames.

Frame differencing

The simplest motion detector subtracts one frame from the next. If the camera is still and nothing moves, the difference is only sensor noise. If something moves, the pixels it uncovers and the pixels it covers change a lot. Taking abs(f1 - f0) and applying a threshold (see Thresholding) gives a binary motion mask.

The demo makes a 12 by 30 frame with noise and a bright 4 by 4 square that moves 3 pixels to the right between frames.

Python Motion mask from two frames

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The mask shows two blocks of 12 pixels each: columns 4 to 6 where the square left and columns 8 to 10 where it arrived, with a gap at column 7 where the old and new squares overlap and both are bright. That is the weakness of differencing: a moving object appears as a ghost pair, uniform interiors cancel out, and an object that stops moving vanishes. The strength is that it needs no setup and is very fast, and with the static scene (noise only) it reports zero changed pixels. A sensible threshold sits well above the noise level (here the noise has standard deviation 0.02, the threshold is 0.25).

Background subtraction

A better approach for a fixed camera is to keep a background model of what the scene looks like when nothing is moving, and mark every pixel that differs from it as foreground. The simplest model is a running average: after each frame, move the background a small step toward the new frame,

TEXT
background = (1 - alpha) * background + alpha * frame

The learning rate alpha controls the memory. A small alpha is stable and rarely absorbs real objects, but adapts slowly to changes such as sunrise. A large alpha adapts quickly, but an object that stops moving melts into the background and is lost. The demo starts with an empty scene, moves a square for 20 frames, and then lets it stand still from frame 28.

Python Running-average background: learning rate matters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Before the object arrives (frame 5) both settings report 0 foreground pixels, so the model handles noise well. While it moves, both find the full 16-pixel square. After the object stops, the two settings diverge. With alpha = 0.02 the square is still reported as foreground in frame 60 (16 pixels), because the model absorbs it too slowly. With alpha = 0.1 the count falls to 7 pixels at frame 35 and 0 at frame 45: the parked object has become part of the background and would no longer be detected. Neither value is "right". Real systems use per-pixel Gaussian mixtures (the MOG2 family in OpenCV) to cope with swaying trees and flickering light, shadow handling, and tricks like not updating the model where foreground was found.

Note: Background subtraction needs a fixed camera. If the camera moves, every pixel changes. In that case you first estimate and cancel the camera motion (for example with feature matching, as in Keypoint Descriptors and Matching), or use optical flow and detection instead.

Optical flow

Differencing tells you that something changed. Optical flow estimates how each pixel moved between two frames, as a vector field (u, v) of horizontal and vertical displacement. It is the basis of video stabilization, motion-based segmentation and action recognition.

The classic Lucas-Kanade method starts from the brightness constancy assumption: a point keeps its brightness as it moves. For small motion, a first-order Taylor expansion turns this into one equation per pixel:

TEXT
Ix * u + Iy * v + It = 0

where Ix and Iy are the spatial gradients of the image (the same gradients you computed in Gradients and Edge Detection) and It is the difference between the two frames. One pixel gives one equation but two unknowns. Lucas and Kanade add a second assumption: all pixels in a small window move together. A 9 by 9 window then gives 81 equations, which you solve by least squares: with the stacked gradients as the matrix A and the temporal differences as b = -It, the answer is (A^T A)^(-1) A^T b.

The matrix A^T A is exactly the structure tensor from Corner Detection. It also tells you whether the answer is reliable. Both eigenvalues large: a corner or texture, the motion is well determined. One large and one tiny: a straight edge, and you only get the motion perpendicular to the edge. This is the aperture problem.

Python Lucas-Kanade on a shifted image

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The image moved by exactly (1.0, 0.5) pixels (the whole pattern is shifted, including sub-pixel amounts). Lucas-Kanade recovers about (1.04, 0.52) at three different points, an error of a few hundredths of a pixel: the small remaining bias comes from the first-order approximation. The eigenvalues are all clearly positive because the Gaussian blobs have gradients in many directions. For the straight edge the smaller eigenvalue is essentially zero (it prints as 0.), which signals that the window has no information about motion along the edge, and the least-squares solve would be unstable. Real implementations check the smaller eigenvalue and refuse to track points that fall below a threshold, which is why trackers pick good features to track (corners) first.

Plain Lucas-Kanade assumes motion smaller than about a pixel. For larger motion you work on an image pyramid (see Image Pyramids and Scale Space): estimate the flow on the coarsest level, where big motions are small, and refine it level by level. That is the pyramidal Lucas-Kanade in OpenCV. In OpenCV (read-only here):

Python
import cv2
import numpy as np

cap = cv2.VideoCapture("video.mp4")
ok, prev = cap.read()
prev_gray = cv2.cvtColor(prev, cv2.COLOR_BGR2GRAY)
points = cv2.goodFeaturesToTrack(prev_gray, maxCorners=100, qualityLevel=0.3, minDistance=7)

while True:
    ok, frame = cap.read()
    if not ok:
        break
    gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
    new_points, status, err = cv2.calcOpticalFlowPyrLK(prev_gray, gray, points, None)
    points = new_points[status.ravel() == 1].reshape(-1, 1, 2)   # keep tracked points
    prev_gray = gray

# dense flow for every pixel: cv2.calcOpticalFlowFarneback(prev_gray, gray, None, 0.5, 3, 15, 3, 5, 1.2, 0)

Learning-based flow networks (RAFT and its successors) now beat these classical methods on difficult footage, but the constraint equation above is still the idea they build on.

Tracking by centroid

Detection finds blobs in each frame. Tracking links them over time so that each object keeps one ID. The simplest tracker is the centroid tracker: for every new frame, match each existing track to the nearest new detection, update matched tracks, start new tracks for unmatched detections, and retire tracks that have been missing for too long.

Greedy "closest first" matching can swap IDs when two objects pass near each other. The standard fix is to solve the assignment as a whole: build the matrix of distances between tracks and detections and find the one-to-one pairing with the smallest total distance, using the Hungarian algorithm (scipy.optimize.linear_sum_assignment). Pairs that are farther apart than a max_distance are rejected, since a car cannot teleport.

Python A centroid tracker with the Hungarian algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Follow the output. Tracks 1 and 2 are created in frame 0 and follow their objects. In frame 2 a third object appears at (60, 5), starting track 3. In frame 3 the second object is not detected: track 2 stays put at its last position, marked as missed once. In frame 4 the object returns at (31, 34), about 5.4 pixels from where track 2 waited, which is inside max_distance, so it keeps ID 2 instead of getting a new one. That is the point of the max_missed allowance. Had it stayed away for three frames, track 2 would have been deleted and the object would return as a new ID.

Weaknesses are easy to predict: it uses position only, so when two objects cross, their IDs may swap; and a track that waits at its last position cannot bridge a gap when the object keeps moving quickly. Production trackers (SORT, DeepSORT, ByteTrack) fix this by predicting where each object should be, with a Kalman filter, and by adding appearance features and IoU matching of boxes (see Object Detection Basics).

The Kalman filter idea

Detections are noisy: the box jitters from frame to frame, and sometimes the detector misses the object. A Kalman filter keeps a running estimate of an object's state (for a moving point: position and velocity) and its uncertainty. It repeats two steps:

  1. Predict: move the state forward using a motion model ("position += velocity"). Uncertainty grows.
  2. Update: if a measurement arrived, blend it with the prediction. The blend weight, the Kalman gain, is high when the measurement is trustworthy and low when the prediction is. Uncertainty shrinks.

If there is no measurement in a frame, you simply skip the update and the filter coasts on its prediction. The code below tracks a point moving 1.5 pixels per frame whose measured position has 3 pixels of noise, with four frames where the detector found nothing. The matrices are the standard constant-velocity model for one coordinate: F advances the state, H extracts the position, Q is how much we distrust the motion model, and R is the measurement noise variance.

Python A constant-velocity Kalman filter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Over frames 10 to 39 the raw measurements are off by 2.82 pixels (RMSE), while the filter's estimates are off by 1.21: less than half the error. During the gap at frames 15 to 17, the filter keeps moving forward (23.1, 24.5, 25.9) and trails the truth (24.5, 26.0, 27.5) by about 1.5 pixels, the price of a velocity estimate that is a little too low. It snaps back when frame 18 returns a measurement (29.2 against a true 29.0). Its final velocity estimate, 1.19, is below the true 1.5: with this much noise the velocity cannot be pinned down quickly, and it improves with more frames. Tuning Q and R trades smoothness against responsiveness: a small Q trusts the motion model and gives smooth tracks that react slowly to real changes; a large Q follows the measurements closely, noise included.

In a real tracker there is one filter per track (often with state [x, y, w, h] and their velocities), the predicted position is used for the matching step instead of the last seen position, and an unmatched track simply coasts for a few frames. Objects that change direction abruptly, such as a bouncing ball or a person turning, break the constant-velocity assumption; then other motion models or an Extended Kalman filter are used.

Tip: Build motion systems in layers and test each one: first check that your detections are good, then add tracking, then add the Kalman filter. Most "tracking bugs" turn out to be detection problems, such as boxes that flicker or merge.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A square moves a few pixels between two frames. What does the thresholded absolute frame difference show?

    Pixels that change from background to object and from object to background are both large differences. Where old and new positions overlap, both frames are bright, so the difference is small.
  2. 2. In a running-average background model, what happens when alpha is large and an object stops moving?

    A large learning rate pulls the background quickly toward the current frame, so a stationary object soon becomes part of the background.
  3. 3. What does the aperture problem mean for Lucas-Kanade optical flow?

    An edge looks identical after sliding along itself, so the structure tensor has one near-zero eigenvalue and the motion along the edge is undetermined.
  4. 4. Why is the Hungarian algorithm used for matching tracks to detections?

    Greedy nearest-first matching can pick a locally good pair that makes the overall assignment worse. The Hungarian algorithm optimizes the whole assignment at once.
  5. 5. What does a Kalman filter do when the detector misses the object in a frame?

    Without a measurement there is nothing to blend with, so the filter keeps the predicted state (and its growing uncertainty) until the next detection arrives.

Summary

  • Frame differencing marks pixels that changed between frames; it is cheap, but it ghosts moving objects and loses objects that stop.
  • Background subtraction compares each frame to a model of the empty scene; the running-average learning rate trades stability against absorbing stopped objects. It needs a fixed camera.
  • Optical flow estimates per-pixel motion. Lucas-Kanade solves Ix*u + Iy*v + It = 0 by least squares in a window; small eigenvalues of A^T A signal the aperture problem, and pyramids handle large motions.
  • A centroid tracker assigns detections to tracks by solving a one-to-one assignment (Hungarian algorithm) with a distance limit, creating and retiring tracks as needed.
  • A Kalman filter alternates predict and update, smooths noisy detections and bridges short gaps; tune its process and measurement noise to balance smoothness and responsiveness.

Next up: put numbers on all of these systems in Evaluating Vision Models.