Multi-object tracking

Deep dive

How it works

Parts:

• motion model — Kalman filter per track (state x, covariance P)
• gate — Mahalanobis distance against a chi-square threshold
• associator — Hungarian, greedy, JPDA or MHT on the gated pairs
• track manager — tentative, confirmed, coasting and deleted states

Per frame, with tracks T and detections D:

1. Predict each track: x' = F x, P' = F P Fᵀ + Q (constant velocity).
2. Gate: y = z − H x', S = H P' Hᵀ + R, d² = yᵀ S⁻¹ y; keep pairs with d² < γ (chi-square quantile, dof = measurement dimension; 9.21 is 99 % for dof 2).
3. Associate: one-to-one assignment minimizing total cost over gated pairs: Hungarian/Jonker-Volgenant (optimal) or greedy cheapest-first (fast, not optimal). Solve each connected component of the gating graph alone (cluster splitting).
4. Update matched tracks; unmatched tracks coast on the prediction.
5. Lifecycle: an unmatched detection starts a tentative track; M hits in N frames confirm it; a confirmed track with misses coasts and is deleted after max_age misses; a tentative track that can no longer reach M-of-N dies.

Vision. SORT: Kalman on box centre, scale, aspect ratio; IoU cost; Hungarian. DeepSORT adds a CNN appearance embedding (cosine distance) and a Mahalanobis gate. ByteTrack matches high-score boxes first, then leftover tracks to low-score boxes (occluded objects score low). OC-SORT re-updates the filter along a virtual path after a gap; BoT-SORT adds camera-motion compensation.

Radar/defense. GNN is steps 1-4 with a log-likelihood cost (include ln|S|). JPDA updates each track with all gated measurements, weighted by joint association probability; it needs a known track set and enumerates hypotheses per cluster. MHT keeps several hypotheses across scans, pruned (N-scan); exponential without pruning. IMM mixes motion models (constant velocity, coordinated turn) by Markov mode probabilities for manoeuvring targets. Polar plots need an extended Kalman filter or conversion; several sensors mean sensor fusion.

Metrics. MOTA = 1 − (FN + FP + IDSwitches)/GT (detection-dominated). IDF1 scores identity over whole trajectories. HOTA = √(DetA · AssA), averaged over localization thresholds.

Code

Two decoupled axes (valid for isotropic noise), position-only, Mahalanobis gate, greedy assignment, M-of-N confirmation, max-age deletion. Test: two crossing targets, noisy plots, a missed frame, a one-frame false alarm.

/// One axis of a constant-velocity Kalman filter; covariance [p00, p01, p11].
#[derive(Clone, Copy)]
struct Axis { x: f64, v: f64, p: [f64; 3] }

impl Axis {
    fn predict(&mut self, q: f64) { // dt = 1, Q = q*[[1/3,1/2],[1/2,1]]
        let [p00, p01, p11] = self.p;
        self.x += self.v;
        self.p = [p00 + 2.0 * p01 + p11 + q / 3.0, p01 + p11 + q / 2.0, p11 + q];
    }
    fn update(&mut self, z: f64, r: f64) { // H = [1 0]
        let [p00, p01, p11] = self.p;
        let (s, y) = (p00 + r, z - self.x);
        let (k0, k1) = (p00 / s, p01 / s);
        self.x += k0 * y;
        self.v += k1 * y;
        self.p = [(1.0 - k0) * p00, (1.0 - k0) * p01, p11 - k1 * p01];
    }
}

pub struct Track { pub id: u32, ax: [Axis; 2], hist: u8, age: u32, misses: u32, pub confirmed: bool }
impl Track { pub fn pos(&self) -> [f64; 2] { [self.ax[0].x, self.ax[1].x] } }

pub struct Tracker {
    pub tracks: Vec<Track>, next_id: u32,
    q: f64, r: f64, gate: f64,       // gate: chi-square threshold on d^2 (2 dof)
    m: u32, n: u32, max_age: u32,    // M hits in the last N frames confirm; coast <= max_age
}

impl Tracker {
    pub fn new(q: f64, r: f64, gate: f64, m: u32, n: u32, max_age: u32) -> Self {
        Tracker { tracks: vec![], next_id: 0, q, r, gate, m, n, max_age }
    }

    pub fn step(&mut self, dets: &[[f64; 2]]) {
        for t in &mut self.tracks { t.ax.iter_mut().for_each(|a| a.predict(self.q)); }
        let mut pairs = vec![];
        for (ti, t) in self.tracks.iter().enumerate() {
            for (di, d) in dets.iter().enumerate() {
                let d2: f64 = (0..2).map(|k| (d[k] - t.ax[k].x).powi(2) / (t.ax[k].p[0] + self.r)).sum();
                if d2 < self.gate { pairs.push((d2, ti, di)); }
            }
        }
        pairs.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
        // greedy: cheapest pair first, each track/detection once (not optimal)
        let (mut t_hit, mut d_used) = (vec![None; self.tracks.len()], vec![false; dets.len()]);
        for &(_, ti, di) in &pairs {
            if t_hit[ti].is_none() && !d_used[di] { t_hit[ti] = Some(di); d_used[di] = true; }
        }
        let win = (1u8 << self.n) - 1;
        for (t, hit) in self.tracks.iter_mut().zip(&t_hit) {
            t.age += 1;
            t.hist <<= 1;
            if let Some(di) = *hit {
                (0..2).for_each(|k| t.ax[k].update(dets[di][k], self.r));
                t.hist |= 1;
                t.misses = 0;
            } else { t.misses += 1; }
            if (t.hist & win).count_ones() >= self.m { t.confirmed = true; }
        }
        let (n, m, max_age) = (self.n, self.m, self.max_age);
        self.tracks.retain(|t| if t.confirmed { t.misses <= max_age }
            else { t.age.min(n) - (t.hist & win).count_ones() <= n - m }); // M-of-N no longer reachable
        for d in dets.iter().zip(&d_used).filter(|(_, u)| !**u).map(|(d, _)| d) {
            // birth: velocity unknown (large variance)
            let ax = |z| Axis { x: z, v: 0.0, p: [self.r, 0.0, 25.0] };
            self.tracks.push(Track { id: self.next_id, ax: [ax(d[0]), ax(d[1])], hist: 1, age: 1, misses: 0, confirmed: false });
            self.next_id += 1;
        }
    }
}

fn main() {
    let mut seed = 12345u64; // LCG noise in [-0.5, 0.5)
    let mut noise = move || { seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407); (seed >> 33) as f64 / (1u64 << 31) as f64 - 0.5 };
    let mut tr = Tracker::new(0.01, 0.1, 9.21, 3, 5, 3);
    let mut at6 = vec![];
    for t in 0..25 {
        let f = t as f64;
        let mut dets = vec![[f + noise(), 21.0 - 2.0 * f + noise()]];    // B descends, crosses A at t = 5.25
        if t != 10 { dets.push([f + noise(), 2.0 * f + noise()]); }      // A ascends; missed in frame 10
        if t == 12 { dets.push([40.0, -30.0]); }                         // one-frame false alarm
        tr.step(&dets);
        assert!(tr.tracks.iter().all(|x| !x.confirmed || x.pos()[0] < 30.0), "false alarm confirmed");
        if t == 6 { at6 = tr.tracks.iter().filter(|x| x.confirmed).map(|x| (x.id, x.pos()[1])).collect(); }
    }
    assert_eq!(at6.len(), 2);
    assert_eq!(tr.tracks.len(), 2); // false-alarm track gone
    for (id, y6) in at6 { // the track above the other at t=6 must still be the high one at t=24
        let fin = tr.tracks.iter().find(|x| x.id == id).expect("id lost").pos()[1];
        assert_eq!(y6 > 10.5, fin > 10.5, "identity swap");
    }
}

Compiled and run: IDs survive the crossing and the gap; the false alarm never confirms.

Complexity and constants

• Gating tests all T·D pairs. Hungarian is O(n³) on the largest cluster; greedy is O(P log P) for P gated pairs.
• A track here is about 100 bytes; cost matrices are T×D doubles unless sparse.
• Measured (this code, Apple M4 Pro, release, one thread, one detection per track, targets over 1000×1000 so gates are nearly empty): 10 tracks 0.4 µs/frame, 100 tracks 16 µs, 500 tracks 325 µs, 1000 tracks 1.27 ms. Quadratic: the pair loop dominates, about 1.2 ns per pair.

Efficiency

Cost: one frame costs T·D gate tests (about 1.2 ns each, measured on an M4 Pro) plus assignment on the gated block; 1000 tracks and 1000 detections take about 1.3 ms single-threaded. Bound: the pair loop, then the upstream detector. ByteTrack reports about 30 FPS for the whole pipeline including the detector on one V100 (ByteTrack README): association is not the bottleneck.

Levers:

• Spatial index (grid, k-d tree) for gating — T·D tests drop to about T·k (not measured here) — thousands of tracks.
• Cluster splitting — Σ nᵢ³ instead of n³ (arithmetic) — sparse scenes.
• Greedy instead of optimal assignment — no cubic term, wrong in dense ambiguity — mostly 1×1 gated blocks.
• Embed only detections that pass the cheap motion/IoU stage — fewer network calls (not measured here) — DeepSORT-style trackers.
• Structure-of-arrays tracks, so predict/update vectorizes (not measured here) — thousands of tracks.

Naive → standard → state of the art:

• Naive: full T×D matrix, optimal assignment on everything · O(T·D + n³).
• Standard: Mahalanobis or IoU gate, per-cluster Hungarian or Jonker-Volgenant, M-of-N lifecycle · O(T·D) plus small cubic blocks.
• State of the art: indexed gating, two-pass association (ByteTrack); IMM with JPDA or pruned MHT for radar · cost grows with hypotheses kept, bounded by pruning.

Implementation notes

• F(dt) and Q(dt) must follow real time, not frame count (radar scans, dropped frames).
• Initial velocity variance must cover the fastest plausible target (here σ = 5 per frame); too small and the gate rejects the next plot.
• Mistuned q (manoeuvre rate) is the usual cause of ID switches; a moving camera needs motion compensation.
• Hungarian needs a finite matrix: give non-gated entries a large cost and drop assignments that hit it.

Pitfalls

• Greedy swaps IDs when two targets pass within one gate.
• Confirming on the first hit floods the picture with clutter; too strict an M-of-N loses fast targets.
• Coasting too long keeps ghosts that steal detections; IoU of predicted boxes is zero for fast small objects.
• MOTA hides identity errors; also report IDF1 and HOTA.

Variants and alternatives

In production

Camera analytics use SORT-family trackers behind a detector and NMS; surveillance and air-defence radars use GNN, JPDA or MHT with IMM; driving stacks track in BEV space; biologists track cells through time-lapse images with TrackMate (Fiji).

Implementations

Sources

• Ershov et al., TrackMate 7: integrating state-of-the-art segmentation algorithms into tracking pipelines, Nature Methods 2022. paper
• Alex Bewley et al., Simple Online and Realtime Tracking, ICIP 2016. paper · code
• Nicolai Wojke et al., Simple Online and Realtime Tracking with a Deep Association Metric, ICIP 2017. paper · code
• Yifu Zhang et al., ByteTrack: Multi-Object Tracking by Associating Every Detection Box, ECCV 2022. paper · code
• Jinkun Cao et al., Observation-Centric SORT, CVPR 2023. paper
• Nir Aharon et al., BoT-SORT: Robust Associations Multi-Pedestrian Tracking, 2022. paper
• Jonathon Luiten et al., HOTA: A Higher Order Metric for Evaluating Multi-Object Tracking, IJCV 2021. paper
• Ergys Ristani et al., Performance Measures and a Data Set for Multi-Target, Multi-Camera Tracking (IDF1), 2016. paper
• Blackman, Multiple-Target Tracking with Radar Applications, Artech House 1986; Bar-Shalom, Li, Estimation and Tracking, Artech House 1993.
• Fortmann, Bar-Shalom, Scheffe, JPDA, IEEE J. Oceanic Eng. 1983; Reid, MHT, IEEE TAC 1979; Blom, Bar-Shalom, IMM, IEEE TAC 1988.