Object Tracking: Mean-Shift, Correlation Filters & Re-Detection

"You showed me one box on one frame and walked away. I have followed that box across the room, behind a pillar, and out the door. We are practically family now. I would recognize it anywhere. Probably."

A Single-Object Tracker With Mild Abandonment Issues

In the previous section a static background let us label every new pixel as foreground without knowing what it was. Tracking flips the question: we are handed an initial bounding box around one object on frame zero, and we must report its box on every subsequent frame, with no detector in the loop and no assumption that the camera or background is fixed. The object's identity is implicit in its appearance, and the tracker's job is to relocate that appearance frame to frame. Because it never re-searches the whole image, a good tracker runs at hundreds of frames per second, which is precisely why trackers exist alongside detectors rather than being replaced by them.

1. Mean-Shift: Climbing an Appearance Density Intermediate

The mean-shift tracker (Comaniciu, Ramesh, and Meer, 2000) models the target by a color histogram built from the initial box, then, on each new frame, finds the nearby window whose histogram best matches the target's. The histogram and its back-projection are exactly the tools of Chapter 2: a histogram counts how often each color appears, and back-projection replaces every pixel by how strongly its color matches that histogram.

The elegant part is how mean-shift searches, and it does so in three small steps repeated to convergence. Rather than testing every candidate window, it treats the problem as climbing a density. First, for every pixel in the search region, compute a weight equal to how much that pixel's color contributes to the target histogram; that weighted image is the back-projection of the histogram, a probability map of "target-ness". Second, take the center of mass of the weighted region, which is a better estimate of the object center than the current window. Third, shift the window to that center and repeat. Each shift moves uphill on the appearance density, and the iteration converges to a local mode in a handful of steps.

Formally, mean-shift seeks the window location $\mathbf{y}$ maximizing the similarity (the Bhattacharyya coefficient) between the target histogram $\mathbf{q}$ and the candidate histogram $\mathbf{p}(\mathbf{y})$. The update is the kernel-weighted mean of pixel positions $\mathbf{x}_i$:

$$ \mathbf{y}_{\text{new}} = \frac{\sum_i \mathbf{x}_i \, w_i \, g\!\left(\left\lVert \frac{\mathbf{y} - \mathbf{x}_i}{h} \right\rVert^2\right)}{\sum_i w_i \, g\!\left(\left\lVert \frac{\mathbf{y} - \mathbf{x}_i}{h} \right\rVert^2\right)}, \qquad w_i = \sqrt{\frac{q_{b(\mathbf{x}_i)}}{p_{b(\mathbf{x}_i)}(\mathbf{y})}}, $$

where $b(\mathbf{x}_i)$ is the histogram bin of pixel $\mathbf{x}_i$ and $g$ is the derivative of the spatial kernel. The weight $w_i$ is the lever that makes the mean climb toward the target: a pixel whose color is common in the target model ($q_b$ large) but currently rare under the candidate window ($p_b$ small) gets a weight above one and pulls the window toward itself, while a pixel the model does not expect is down-weighted, so the center of mass drifts onto wherever the target's own colors are concentrated. (The square root is not cosmetic: it is exactly the gradient of the Bhattacharyya similarity, so this weighted mean is provably an ascent step on the similarity being maximized, which is why the next Key Insight can call mean-shift gradient ascent with no learning rate.) Code Fragment 1 uses OpenCV's meanShift on a hue back-projection; the plain mean-shift window is fixed in size, so an object approaching the camera eventually outgrows its box.

import cv2
import numpy as np

cap = cv2.VideoCapture("ball.mp4")
ok, frame = cap.read()
x, y, w, h = cv2.selectROI("init", frame, False)      # user draws target box
roi = frame[y:y+h, x:x+w]

# target model: hue histogram, masked to confident saturation/value
hsv_roi = cv2.cvtColor(roi, cv2.COLOR_BGR2HSV)
mask = cv2.inRange(hsv_roi, (0, 60, 32), (180, 255, 255))
hist = cv2.calcHist([hsv_roi], [0], mask, [16], [0, 180])
cv2.normalize(hist, hist, 0, 255, cv2.NORM_MINMAX)

track_window = (x, y, w, h)
term = (cv2.TERM_CRITERIA_EPS | cv2.TERM_CRITERIA_COUNT, 10, 1)  # stop rule

while True:
    ok, frame = cap.read()
    if not ok:
        break
    hsv = cv2.cvtColor(frame, cv2.COLOR_BGR2HSV)
    # back-project: probability each pixel belongs to the target color model
    prob = cv2.calcBackProject([hsv], [0], hist, [0, 180], scale=1)
    # climb the probability density to the nearest mode
    _, track_window = cv2.meanShift(prob, track_window, term)

    px, py, pw, ph = track_window
    cv2.rectangle(frame, (px, py), (px+pw, py+ph), (0, 255, 0), 2)
    cv2.imshow("mean-shift", frame)
    if cv2.waitKey(30) == 27:
        break

The fixed-window limitation is exactly what CamShift (Continuously Adaptive Mean-Shift) fixes: after each mean-shift convergence it resizes the window to match the spread of the back-projection (and reports an orientation from the second moments), so the box grows as the object nears and shrinks as it recedes. Swapping cv2.meanShift for cv2.CamShift in Code Fragment 1 yields a rotating, scaling box. Both share one structural weakness: a pure color model has no notion of shape or texture, so any same-colored distractor (a second red shirt) can capture the window. This is the appearance-ambiguity problem that the correlation filters of the next section attack with a spatially structured template.

2. Correlation Filters: Tracking in the Fourier Domain Advanced

The correlation-filter family is the great speed story of classical tracking. The idea: learn a small filter $\mathbf{h}$ such that correlating it with the target patch produces a sharp peak at the object's center, and correlating it with off-center patches produces near-zero response. Then on each new frame, correlate the filter with a search window; the location of the peak is the new object position. Correlation in the spatial domain is expensive, but the convolution theorem from Chapter 4 turns it into a single elementwise multiply in the frequency domain. A full search over every shift of the window costs one forward FFT, one multiply, and one inverse FFT, which is why MOSSE (Bolme et al., 2010) tracks at over 600 frames per second on a CPU.

The filter is learned to map the target patch $\mathbf{f}$ to a desired Gaussian-shaped response $\mathbf{g}$ peaked at the center. In the Fourier domain (capital letters denote transforms, $\odot$ elementwise product, $^*$ complex conjugate) the optimal filter that minimizes squared output error is

$$ H^* = \frac{G \odot F^*}{F \odot F^* + \lambda}, $$

a closed-form ratio regularized by $\lambda$. The intuition is direct: in the spatial domain we want a filter that, correlated with the patch $\mathbf{f}$, yields the target response $\mathbf{g}$; the convolution theorem turns that correlation into the elementwise product $F \odot H = G$, so solving for $H$ is just elementwise division, and the $+\lambda$ in the denominator keeps the division stable where $F$ is near zero (the same regularization trick used for deconvolution in Chapter 7). MOSSE updates the numerator and denominator with a running average each frame, so the filter adapts as the object's appearance changes. The Kernelized Correlation Filter (KCF, Henriques et al., 2015) extends this with a kernel trick and multi-channel features (such as histogram-of-oriented-gradients descriptors from Chapter 10) while keeping the closed-form Fourier solution, giving a large accuracy jump for a small cost. CSRT (Lukezic et al., 2017) adds a spatial reliability map and channel weights for the best accuracy in the OpenCV family, at lower frame rates. Figure 15.5.1 shows the per-frame correlation-tracking loop.

OpenCV's tracking module exposes these as drop-in trackers behind a uniform interface. Code Fragment 2 initializes a CSRT tracker from a single box and runs it across a video, including the critical check on the boolean returned by update, which signals that the tracker has lost confidence.

import cv2

cap = cv2.VideoCapture("walk.mp4")
ok, frame = cap.read()
box = cv2.selectROI("init", frame, False)   # (x, y, w, h) of the target

# CSRT: most accurate OpenCV tracker; KCF is faster, MOSSE fastest of all
tracker = cv2.TrackerCSRT_create()
tracker.init(frame, box)

while True:
    ok, frame = cap.read()
    if not ok:
        break
    found, box = tracker.update(frame)       # one FFT-based localization
    if found:
        x, y, w, h = [int(v) for v in box]
        cv2.rectangle(frame, (x, y), (x+w, y+h), (0, 255, 0), 2)
    else:
        cv2.putText(frame, "LOST", (20, 40),
                    cv2.FONT_HERSHEY_SIMPLEX, 1, (0, 0, 255), 2)
        # a real system would now trigger re-detection (Section 4 below)
    cv2.imshow("CSRT", frame)
    if cv2.waitKey(1) == 27:
        break

3. Drift, Occlusion, and Scale: Why Trackers Fail Intermediate

Every appearance tracker shares a fatal tendency called drift. Because the model updates itself from its own predictions, any small localization error contaminates the next template: the filter learns a bit of background, which pulls the next prediction slightly off, which puts more background in the template, and the tracker slides off the object over tens of frames. Three situations turn slow drift into outright loss. Occlusion: the object disappears behind a pillar, the tracker latches onto the occluder, and when the object reappears it is gone. Scale change: a fixed-size template (plain MOSSE, plain KCF) loses an object that approaches or recedes; CSRT and KCF-with-scale-pyramid mitigate this but do not cure it. Fast motion or blur: the object leaves the search window between frames and the peak lands on whatever was nearby.

The classical defenses are pragmatic. Monitor the peak response strength (a confident track has a sharp, tall peak; the Peak-to-Sidelobe Ratio quantifies this) and freeze or shrink the learning rate when confidence drops, so the model does not learn the occluder. Search a slightly larger window after a low-confidence frame. And, crucially, do not trust a tracker indefinitely: pair it with a detector that periodically re-anchors the target.

4. Tracking-by-Detection and Re-Detection Advanced

The robust pattern that dominates production is tracking-by-detection: run a detector (a background-subtraction blob detector from Section 15.4, or a learned object detector from Chapter 23) periodically or every frame, and use a fast tracker to bridge the gaps and to associate detections across frames. The historically influential TLD framework (Kalal et al., 2012, "Tracking-Learning-Detection") made the loop explicit: a tracker follows the object frame to frame, a detector scans for the object independently, and a learning component reconciles the two, correcting the tracker when the detector finds the object elsewhere and expanding the detector's model from the tracker's confident frames. The detector provides the long-term memory the tracker lacks; the tracker provides the speed and inter-frame continuity the detector lacks.

This division of labor is the conceptual bridge to multi-object tracking. Once a detector emits a fresh set of boxes every frame, the tracking problem becomes data association: which of this frame's detections continue which of last frame's tracks? Answering that with a motion model and an assignment algorithm is precisely the subject of Section 15.6, and the Kalman filter there supplies the motion prediction that tells the associator where each tracked object should appear before any detection is even examined.