Detection and tracking in the perception stack

"A detector told me there was a pedestrian. The next frame told me there was a pedestrian. It never once told me it was the same pedestrian, and that omission is where robots get people killed."

A Frame-Amnesiac AI Agent

This section assumes you know the recursive Bayes filter and the constant-velocity Kalman model from Chapter 9, and that you have met the detectors that produce the inputs here: 3D boxes from point clouds in Chapter 42 and the bird's-eye-view detectors of Chapter 43. The tracker treats the detector as a black-box measurement source; what is new is the machinery that gives those measurements memory.

The detect-then-track architecture

The dominant paradigm in robotics is tracking-by-detection. Every frame, a detector emits a list of detections \(\{z_1, \dots, z_m\}\), each a box, a class label, a confidence, and often a lidar-derived position and extent. The tracker maintains a set of tracks \(\{T_1, \dots, T_n\}\), each a Kalman-style state (position, velocity, size, heading) with a covariance. One tracking cycle is three steps. Predict: propagate every track's state forward by the elapsed time with a motion model, inflating covariance. Associate: decide which detection, if any, belongs to which track. Update: for matched pairs, correct the track with the detection; for unmatched detections, consider spawning new tracks; for unmatched tracks, coast on prediction and eventually delete.

Why separate detection from tracking at all, rather than train one network to output tracks end to end? Because the two stages have different failure modes and different time constants. A detector is a stateless pattern recognizer you can train, validate, and swap on a leakage-safe benchmark (Chapter 65) without touching the temporal logic. The tracker is a lightweight recursive estimator that runs in microseconds and encodes physics and identity constraints a single-frame network has no way to represent. Keeping them modular means a false negative in one frame is survivable: the track coasts on its motion model until the detector reacquires. That graceful degradation is exactly why safety-critical stacks keep an explicit filter in the loop rather than trusting a monolithic network.

Data association: the gating and assignment problem

Association is a matching between \(n\) tracks and \(m\) detections. Two ideas make it tractable. First, gating: a detection can only match a track if it falls within a plausibility region around the track's prediction. The natural region is the Mahalanobis distance in the measurement space, since the Kalman filter already gives us the innovation covariance \(S\):

and we admit a pair only if \(d^2\) is below a chi-square threshold for the measurement dimension. Gating throws away impossible pairings cheaply and shrinks the assignment problem. Second, global assignment: among the surviving candidate pairs, choose the one-to-one matching that minimizes total cost. Greedy nearest-neighbor is fast but makes locally-good, globally-bad choices when objects are dense; the Hungarian algorithm solves the linear assignment optimally in \(O(k^3)\), which is trivial for the few dozen objects a robot tracks at once. The cost can be Mahalanobis distance, negative 3D IoU between predicted and detected boxes, or, in modern trackers, a blend of geometric distance and a learned appearance-embedding distance so that identity survives a few frames of occlusion.

The code below runs one full associate-and-update cycle: predict a set of constant-velocity tracks, gate and solve the assignment with the Hungarian method, then Kalman-update the matches. It is the beating heart of every tracking-by-detection system, and it is under 40 lines.

import numpy as np
from scipy.optimize import linear_sum_assignment

def associate_and_update(tracks, dets, dt, R, gate=9.21):
    """tracks: list of dicts with state x=[px,py,vx,vy] and cov P.
       dets: array of measured positions [px,py]. Returns updated tracks."""
    F = np.array([[1,0,dt,0],[0,1,0,dt],[0,0,1,0],[0,0,0,1]])  # const-velocity
    H = np.array([[1,0,0,0],[0,1,0,0]])                         # observe position
    Q = 0.1 * np.eye(4)

    # 1) PREDICT every track forward.
    for t in tracks:
        t["x"] = F @ t["x"]
        t["P"] = F @ t["P"] @ F.T + Q

    # 2) Build a gated Mahalanobis cost matrix (tracks x detections).
    cost = np.full((len(tracks), len(dets)), 1e6)
    for i, t in enumerate(tracks):
        S = H @ t["P"] @ H.T + R          # innovation covariance
        Sinv = np.linalg.inv(S)
        for j, z in enumerate(dets):
            y = z - H @ t["x"]            # innovation
            d2 = float(y @ Sinv @ y)
            if d2 < gate:                 # chi-square gate, 2 dof, ~99%
                cost[i, j] = d2

    # 3) Optimal one-to-one assignment, then KF update on valid matches.
    rows, cols = linear_sum_assignment(cost)
    for i, j in zip(rows, cols):
        if cost[i, j] >= 1e6:            # gated out: not a real match
            continue
        t = tracks[i]
        S = H @ t["P"] @ H.T + R
        K = t["P"] @ H.T @ np.linalg.inv(S)      # Kalman gain
        t["x"] = t["x"] + K @ (dets[j] - H @ t["x"])
        t["P"] = (np.eye(4) - K @ H) @ t["P"]
        t["hits"] = t.get("hits", 0) + 1
    return tracks

from boxmot import ByteTrack
tracker = ByteTrack()
# dets: (N, 6) array of [x1, y1, x2, y2, conf, class]
tracks = tracker.update(dets, frame)   # (M, 8): boxes + persistent track id

Track lifecycle: birth, confirmation, coasting, and death

A world model that trusts every detection instantly is noisy; one that never lets go of a track hallucinates. The lifecycle policy manages that tradeoff with a small state machine. A new detection with no matching track opens a tentative track. It is promoted to confirmed only after it is matched in some number of consecutive frames (a hit streak), which rejects single-frame false positives such as sensor glitches or reflections. A confirmed track that misses detections coasts: it keeps predicting through the gap, its covariance growing, so it survives brief occlusions and detector dropouts. If it goes unmatched for too long (a miss streak past a threshold, roughly one second of coasting for road users), it is deleted. The ByteTrack insight worth internalizing is to associate in two passes: match high-confidence detections first, then give the leftover low-confidence detections a second chance to continue existing tracks rather than discarding them, which recovers objects that dim during occlusion without admitting them as new tracks.

Where learning enters, and the honest limits

Two components of this stage are increasingly learned rather than hand-tuned. The appearance embedding that lets association survive long occlusions is a small network producing a per-detection feature vector, so the assignment cost blends geometry with visual identity (DeepSORT, BoT-SORT, DeepOCSORT). And end-to-end tracking transformers such as MOTR and query-based 3D trackers propagate object queries across frames so association is implicit in the attention, drawing on the sequence models of Chapter 15. The tradeoff is the recurring one of this book: the learned tracker can exploit appearance cues a Kalman filter cannot, but it is a black box whose failure under distribution shift is hard to bound, whereas the explicit filter degrades predictably and its covariance is a calibrated uncertainty a planner can reason about (Chapter 18). Safety-critical robots today keep the explicit filter and treat learned components as cost terms inside it. A second honest limit: the constant-velocity model in the code assumes objects do not accelerate hard, which is fine for cars and wrong for a bouncing ball or a darting toddler; those cases need the interacting-multiple-model and nonlinear filters of Chapter 10. And every track this stage produces is only as trustworthy as the association upstream of the fusion in Chapter 49: a swapped identity poisons everything downstream.

What's Next

In Section 57.4, we fuse the exteroceptive tracks built here with the robot's own proprioceptive state from Section 57.1: the tracker estimates where the world is, but those estimates are expressed in a sensor frame that is itself moving, so knowing the robot's own motion is what lets a coasting track stay anchored while the robot drives past it.