Tracking: Following Objects Through Time

Detection vs tracking: why following is its own problem

In the previous guides we learned to read motion from raw pixels — first watching how brightness shifts from one frame to the next, then measuring that shift precisely with optical flow. Now we ask a different, very human question: not just where is there motion, but *which thing am I looking at, and where did that same thing go?* That is the job of object tracking. Lock onto one object on the first frame and keep your eye on it, frame after frame, even as it moves, turns, shrinks, or briefly hides.

It is tempting to think tracking is just detection repeated every frame. A detector answers what objects are in THIS frame and where — it draws boxes from scratch each time, with no memory of the past. Tracking answers a harder question: *is this box the SAME object as the one I saw a moment ago?* Detection is about presence; tracking is about identity over time. Run a person-detector on a busy street and each frame gives you a fresh pile of anonymous boxes; tracking is what ties box №7 in this frame to box №7 in the last, so you can say "that is still the same pedestrian."

There are three concrete reasons tracking earns its own chapter. Identity: downstream tasks — counting cars, analysing a player's path, following a tumour across a scan sequence — all need a consistent ID glued to each object over time, which per-frame detection alone never gives you. Efficiency: if I knew where an object was last frame and roughly how it moves, I only need to search a small region around its predicted spot, instead of re-detecting the entire image — cheaper and faster. Robustness: detectors miss things and flicker; a good tracker can coast through a missed detection or a brief occlusion by leaning on what it already knows about the object's motion.

For most of this guide we focus on single-object tracking: you point at one target on frame 1 (a box drawn by you or by a detector), and the tracker follows it from then on. Once that is solid we scale up to crowds. And running underneath everything is one recurring tension worth naming now: an appearance model (what the object looks like — its colours, its texture, a learned template) versus a motion model (where the object should be — where it is heading given how it has been moving). The best trackers blend both, and the next four sections are, in effect, four answers to how to combine them.

Mean-shift: chase the appearance

Our first tracker leans entirely on the appearance side. The idea, called mean-shift tracking, is wonderfully concrete. On frame 1, summarise the target purely by its colour histogram — count how many of its pixels are reddish, how many bluish, and so on, into a few dozen colour bins. That histogram is the target's appearance fingerprint. Notice we throw away where each colour sits inside the box and keep only how much of each colour there is; this is exactly what makes the method tolerant to the target bending, rotating, or deforming.

On the next frame, we build a back-projection map: for every pixel, look up its colour in the target histogram and ask "how target-like is this colour?" Pixels whose colour the target had a lot of get a high score; pixels with colours the target never had get nearly zero. The result is a grayscale 'heat map' that glows brightly wherever the target's colours are concentrated. Tracking now reduces to a clean question: where is the brightest, densest blob in this heat map, and how do I climb to it?

Mean-shift is the climbing rule, and it is a general mode-seeking (hill-climbing) procedure — nothing tracking-specific about it. Think of a ball placed on the heat-map landscape: mean-shift rolls it uphill toward the nearest peak (the 'mode', the densest spot). One step works like this:

1. Place a search window (a small box) where the target was last frame.
2. Inside the window, compute the weighted centre of mass — average the pixel positions, weighting each pixel by how target-like it is on the back-projection map.
3. Shift the window so its centre lands on that centre of mass.
4. Repeat. When the window stops moving (the centre of mass is already at the centre), you have reached the peak — that is the new target location.

The mean-shift vector: where to step from the current window centre.

Let us read this slowly. \mathbf{x} is the current window centre (an (x,y) position). The \mathbf{x}_i are the positions of the pixels inside the window. Each w_i is that pixel's weight — its value on the back-projection map, i.e. how strongly its colour matches the target. The fraction \frac{\sum_i w_i\,\mathbf{x}_i}{\sum_i w_i} is a weighted average of pixel positions: it is the centre of mass, pulled toward wherever the target-coloured pixels are heaviest. Subtracting \mathbf{x} turns that target location into a displacement — the direction and distance to step. So m(\mathbf{x}) literally says: "move toward where the target-coloured pixels are concentrated." Iterate until m(\mathbf{x})\approx 0, meaning you are already sitting on the peak.

A tiny worked example makes it click. Suppose the window holds just three pixels at positions \mathbf{x}_1=(0,0), \mathbf{x}_2=(10,0), \mathbf{x}_3=(20,0) with weights w_1=1, w_2=1, w_3=8 (the rightmost pixel is strongly target-coloured). The weighted centre of mass is \frac{1\cdot0 + 1\cdot10 + 8\cdot20}{1+1+8} = \frac{170}{10} = 17. If the current centre \mathbf{x} is at 10, the shift is 17-10=+7: the window jumps right, toward the heavy cluster of target colour, exactly as intuition demands.

Mean-shift's strengths are speed and simplicity: a handful of cheap iterations per frame, no training, and graceful behaviour when the object bends or rotates (the histogram barely changes). Its weaknesses point straight at the next sections. It struggles with scale change — a fixed-size window cannot grow as the object approaches the camera (the CAMShift variant patches this). And it can be fooled by background clutter that shares the target's colours: if a red car drives past your red-shirted target, the heat map glows in two places and the window may slide onto the wrong peak. Appearance alone is not enough — we need a sense of where the object should be. Enter motion models.

The Kalman filter: predict, then correct

Here is the conceptual centrepiece of the whole guide, so let us build the intuition before touching a single matrix. Picture the situation each frame. You have two clues about where your object is. Clue one: a measurement — say a detector's bounding box. It is roughly right but it jitters; the box wobbles a pixel here, two pixels there, frame to frame. Clue two: a motion model — a prediction of where the object should be, based on how it has been moving. If a ball moved 5 px right last frame, a 'constant velocity' model bets it will move ~5 px right again. Each clue is imperfect. The Kalman filter is the recipe for fusing them into one estimate that is better than either alone.

The filter's secret is that it tracks not just an estimate but its uncertainty — how confident it is, captured as a spread (think of a fuzzy cloud around the estimate, wide when unsure, tight when sure). The constant-velocity prediction here is exactly a motion model, the same kind of motion estimation idea you met when we modelled how pixels move; the Kalman filter is what wraps that motion model in a principled accounting of trust.

The whole filter is a loop of two steps repeated every frame. Predict: push the current state forward with the motion model — "if it was here moving this fast, next frame it should be there." Crucially, uncertainty grows during prediction, because the world is noisy and our model is only a guess. Correct (update): a new measurement arrives; nudge the prediction toward it, and uncertainty shrinks, because we just learned something. The art is in how much to nudge — and that is decided by relative trust.

The correction (update) step and the Kalman gain that controls it.

Let us decode it symbol by symbol. \mathbf{x}_{\text{pred}} is the predicted state (where the motion model thinks the object is). \mathbf{z} is the new measurement (the detector's box). H is a matrix that maps a state into measurement space — if the state holds position and velocity but the detector only sees position, H simply picks out the position part. So H\,\mathbf{x}_{\text{pred}} is "what we predicted the measurement should look like," and (\mathbf{z} - H\,\mathbf{x}_{\text{pred}}) is the innovation — the surprise, i.e. how wrong the prediction turned out to be. We then add a fraction K of that surprise back to the prediction.

That fraction K is the Kalman gain — think of it as a trust knob between roughly 0 and 1. Look at how it is built. R is the measurement noise (how unreliable the sensor is) and P_{\text{pred}} is the prediction uncertainty (how unsure we are of our own forecast). When the sensor is noisy (large R), the denominator grows, K shrinks toward 0, and the update barely moves off the prediction — trust the model. When our prediction is shaky (large P_{\text{pred}}), the numerator grows, K rises toward 1, and the update jumps almost all the way to the measurement — trust the sensor. The gain is the automatic referee deciding which friend to believe.

A one-number feel for it (a 1-D position, dropping matrices): suppose the prediction says the object is at x_{\text{pred}}=100 and the measurement says z=110, so the innovation is +10. If we trust both equally, the gain works out to K=0.5 and x_{\text{new}} = 100 + 0.5\times 10 = 105 — dead between them. If the sensor is very noisy so K=0.1, then x_{\text{new}} = 100 + 0.1\times 10 = 101 — we barely budge from the prediction. If the sensor is trusted so K=0.9, then x_{\text{new}} = 109 — we nearly accept the measurement. Same equation, three personalities, all set by one knob.

# One Kalman cycle per frame, sketched for a 'constant velocity' box tracker.
# State x = [cx, cy, vx, vy]: centre position and its velocity.
# F = motion model (advance position by velocity). H = picks out [cx, cy].

def kalman_step(x, P, z, F, H, Q, R):
    # --- PREDICT: coast forward with the motion model ---
    x_pred = F @ x                      # where it SHOULD be next frame
    P_pred = F @ P @ F.T + Q            # uncertainty GROWS (Q = process noise)

    # --- CORRECT: fold in the new measurement z (detector box centre) ---
    innovation = z - H @ x_pred         # the 'surprise': how wrong we were
    S = H @ P_pred @ H.T + R            # innovation covariance
    K = P_pred @ H.T @ inv(S)           # Kalman gain = the trust knob
    x_new = x_pred + K @ innovation     # nudge prediction toward measurement
    P_new = (I - K @ H) @ P_pred        # uncertainty SHRINKS after measuring
    return x_new, P_new

# If z is missing this frame (occlusion / missed detection), skip CORRECT
# and just return x_pred, P_pred: the tracker 'coasts' on its motion model.

Two payoffs to carry forward. First, the 'coast on prediction when the measurement is missing' trick (the last lines above) is precisely how a tracker survives a brief occlusion — we will return to it in the final section. Second, the Kalman filter is the natural per-object engine for crowds: in object tracking at scale, you simply give each track its own Kalman filter, predicting where every object will be so you can match incoming detections to the right one. That is exactly where Section 5 picks up.

Correlation filters: tracking at hundreds of frames per second

Mean-shift describes the target with a histogram; the Kalman filter reasons about motion. The third family — correlation filter tracking, whose famous members are MOSSE and KCF — takes a third route: it learns a small template discriminatively. The intuition is delightful. We want a little filter such that, when you slide it across the search region (correlate it everywhere) and read off the response, you get a single sharp peak exactly at the target and near-zero everywhere else. The filter is a template that 'lights up' on the target and stays dark on everything that is not the target.

Recall convolution from the CNN guides — sliding a small kernel over an image and recording a weighted sum at every position. Correlation is the same sliding-and-summing operation (convolution with the kernel un-flipped); a correlation filter is just a learned kernel whose job is to produce that one bright spike on the target. So far this sounds expensive: sliding a filter over every position of every frame is a lot of multiply-adds.

Here is the magic trick that makes these trackers blisteringly fast — often hundreds of frames per second on a single CPU. The convolution theorem says that sliding correlation in the image domain equals a simple element-wise multiply in the Fourier (frequency) domain. So instead of dragging the filter across thousands of positions, you take one FFT of the patch, one element-wise multiply, and one inverse FFT — and you have the entire response map at once. Expensive sliding becomes cheap pointwise multiplication.

Applying the filter (left) and learning it in closed form (right) — both in the Fourier domain.

Decoding the symbols: a hat means 'the Fourier transform of', \odot is element-wise multiplication, and the overline (conj) is the complex conjugate (a harmless bookkeeping detail of correlation in the frequency domain). On the left, \hat{X} is the Fourier transform of the image patch; multiply it by \overline{\hat{H}}, the conjugated filter, then take the inverse transform \mathcal{F}^{-1} to land back in image space — and you read off the response map, whose brightest pixel is the new target location. That one line replaces an entire sliding-window scan.

The right equation is how the filter is learned, and it is the real elegance. \hat{X} is again the image patch and \hat{Y} is the desired output — the ideal response we want, a clean Gaussian bump centred on the target. We are solving "what filter \hat{H}, correlated with this patch, yields that perfect spike?" In the image domain that is a least-squares problem; in the Fourier domain it collapses to a per-element division — solved in one shot, no iterations. The \lambda is regularization: a small number added to the denominator so we never divide by near-zero, keeping the filter stable. Intuitively: "find the filter whose correlation with the target is a single clean peak," computed almost for free by FFTs.

Two refinements and one caveat. Online updating: the target's look drifts (it turns, the light changes), so the filter is re-learned a little each frame, blending the new patch into the old filter — it adapts as it goes. The kernel trick (KCF): rather than raw pixels, KCF feeds richer features (like HOG gradients) and uses a kernelised version that stays just as fast, sharply improving accuracy. The caveat is the familiar one: a fixed-size filter handles scale change and heavy deformation poorly — when the object grows or contorts, the learned template no longer fits, and the tracker can lag or slip.

Multi-object tracking: identities in a crowd

So far one target, one tracker. Real scenes have dozens of people, cars, or cells at once, and we need a consistent ID on each. This is multi-object tracking (MOT), and the dominant paradigm is tracking-by-detection: every frame, run an object detector to get a fresh set of boxes, then solve the real puzzle — data association — deciding which of this frame's detections belongs to which existing track. Detection gives you anonymous boxes; association is what stamps the right ID back onto each.

Here is where the previous section pays off: each existing track carries its own Kalman filter, so before we look at the new detections we already have a prediction of where every tracked object should be this frame. Association then becomes a matching problem between two lists — the predicted boxes (tracks) and the detected boxes (observations). We score every possible pairing in a cost matrix: row i = track i, column j = detection j, entry = how bad it would be to match them. A natural cost is geometric overlap, and often an appearance-embedding similarity (a learned feature vector per box) is folded in too, so identity survives even when boxes momentarily overlap.

Intersection-over-Union as a similarity, turned into an association cost.

Reading it: A is a track's Kalman-predicted box and B is a new detection box. \mathrm{area}(A \cap B) is the area where the two rectangles overlap (intersection); \mathrm{area}(A \cup B) is the total area they cover together (union). Their ratio, \mathrm{IoU}, is 1 for two boxes that sit perfectly on top of each other and 0 for two that do not touch — a clean similarity score from 0 to 1. Because the matcher wants to minimise cost, we flip it: \text{cost} = 1 - \mathrm{IoU}, so a great overlap (IoU near 1) becomes a tiny cost (near 0), and no overlap becomes the maximum cost of 1.

Concretely: say a track predicts a box of area 100, a detection has area 100, and they overlap over an area of 80. The union is 100 + 100 - 80 = 120, so \mathrm{IoU} = 80/120 \approx 0.67 and the cost is 1 - 0.67 = 0.33 — a fairly cheap, fairly confident match. A detection that overlaps the prediction by only area 10 gives \mathrm{IoU} = 10/190 \approx 0.05, cost 0.95 — almost certainly a different object. Fill the whole matrix with such costs and you have posed the assignment cleanly.

With the cost matrix in hand, we want the optimal one-to-one matching — assign every track to at most one detection (and vice versa) so the total cost is lowest. Naively trying all pairings is factorial and hopeless, but the classic Hungarian algorithm solves this assignment problem exactly in polynomial time. This trio is the canonical pipeline SORT = Kalman prediction + IoU cost + Hungarian matching: small, fast, and surprisingly strong.

# SORT-style frame loop (pseudocode). Each track owns a Kalman filter.
for frame in video:
    detections = detector(frame)                 # fresh, anonymous boxes
    predictions = [t.kalman.predict() for t in tracks]  # where each track expects to be

    # Build cost matrix: 1 - IoU between every (track, detection) pair
    cost = [[1 - iou(p, d) for d in detections] for p in predictions]

    matches, unmatched_tracks, unmatched_dets = hungarian(cost, thresh=0.7)

    for (t_idx, d_idx) in matches:
        tracks[t_idx].kalman.update(detections[d_idx])   # correct with measurement
        tracks[t_idx].keep_id()                           # identity preserved

    for d_idx in unmatched_dets:
        tracks.append(new_track(detections[d_idx]))       # a new object appeared

    for t_idx in unmatched_tracks:
        tracks[t_idx].mark_missed()                       # coast on prediction;
        # delete the track if it stays unmatched for too many frames

SORT's Achilles' heel is the ID switch: when two paths cross or one object hides another, IoU alone cannot tell who is who once the boxes pile up, and the IDs may swap. DeepSORT fixes much of this by adding an appearance descriptor — a learned embedding per box — so association uses what the object looks like (re-identification), not just where it sits. Cross paths, and the embeddings still recognise "this is the same person in the red coat," stitching the identity back together. To judge any of this honestly, the field reports MOTA (overall accuracy — penalising misses, false boxes, and ID switches together) and IDF1 (how consistently identities are preserved over time). We will lean on these metrics in the closing section.

Occlusion, drift, and honest evaluation

Every tracker, however clever, meets the same hard realities, and a practitioner is someone who knows them by name. The first is occlusion: the target slips behind a pillar, another person, or the edge of the frame, and for a stretch of frames there is simply no measurement. This is where the predict/correct loop earns its keep — with no detection to correct on, the Kalman filter keeps predicting, coasting the box along its last known velocity through the blind spell. Its uncertainty cloud swells the whole time (no new evidence), and when the object re-emerges, a good IoU or appearance match snaps the track back on. For longer disappearances, re-identification — matching the re-appeared object's appearance embedding to the lost track — recovers the original ID rather than minting a new one.

The second reality is drift. Each frame's tiny localisation error is small on its own, but errors accumulate; left unchecked, the box gradually slides off the target until it is tracking the background. Drift is worst for trackers that update their appearance model aggressively: every frame they absorb whatever is inside the box as 'the target', so if the box is even slightly off, they start learning the background — and once they learn the background, they chase it. This is the famous stability-plasticity dilemma.

A structural distinction shapes which tricks you may use. Online (causal) tracking processes frames as they arrive, using only the past — this is what live robotics, AR, and surveillance demand, and everything in this guide so far is online. Offline (batch) tracking has the whole video in hand and may peek at future frames; for after-the-fact analytics (sports breakdowns, traffic studies) this is a gift, because seeing how a path continues lets you fix a momentary ambiguity in hindsight and resolve ID switches that an online tracker had to guess at. Same problem, looser constraints, better accuracy.

So which tracker do you reach for? A rule of thumb that ties the whole guide together: mean-shift / correlation filters (appearance-driven) shine for a single target that you must follow fast with no detector handy — KCF when you want hundreds of fps on a CPU. The Kalman filter (motion-driven) is your backbone whenever you have noisy measurements and predictable motion, and it is the per-track engine for crowds. Tracking-by-detection (SORT / DeepSORT) is the default for multi-object tracking when a good detector exists — add DeepSORT's appearance embeddings the moment ID switches start hurting. The honest meta-lesson: appearance excels at recognising, motion excels at predicting, and the strongest object tracking systems fuse the two.

Finally, judge trackers honestly with the metrics from the last section. MOTA rolls misses, false positives, and ID switches into one accuracy number — but it can flatter a tracker that localises well yet swaps identities, so always read IDF1 alongside it, which directly rewards keeping each identity consistent over its whole life. With these in hand you can not only build a tracker but defend the choice with numbers. Next in this track we move from following a known object to recognising what is happening — teaching networks to watch video and name the action — and then to dense, per-pixel video understanding.