Data Association

Data association is the problem of deciding which observation came from which object. At every time step a multi-target tracker receives an unlabeled set of measurements, such as detector boxes, radar returns, or feature points, and must decide which belongs to which target before it can update any state. In object tracking by detection, this step, more than localization, determines whether identities are kept or swapped.

Definition

Given existing tracks (targets with estimated states) and new measurements, data association chooses an association hypothesis: a labeling of every measurement either as originating from exactly one track or as clutter (a false alarm), under the constraint that each track produces at most one measurement per scan. Tracks left without a measurement are missed detections. Measurements that fit no track may start new tracks (track birth), and tracks unmatched for too long are terminated (track death).

Intuition

Picture two pedestrians walking toward each other, with a detector returning two unnamed boxes per frame. While they are far apart, the box near each predicted position obviously belongs to it. As they pass, the boxes overlap, one person may be hidden, and position alone no longer says who is who. A tracker resolves this with more evidence (appearance, velocity, history) or by waiting for later frames; association methods differ mainly in how much evidence they use and how long they wait.

Formal Definition

Let track $i \in \{1, \ldots, N\}$ have predicted state $\hat{\mathbf{x}}^{i}_{k \mid k-1}$ and covariance $P^{i}_{k \mid k-1}$ from a Kalman filter, and let $\mathbf{z}_1, \ldots, \mathbf{z}_M$ be the measurements at step $k$. For each pair, the innovation and its covariance are

$$\mathbf{y}_{ij} = \mathbf{z}_j - H \hat{\mathbf{x}}^{i}_{k \mid k-1}, \qquad S_i = H P^{i}_{k \mid k-1} H^\top + R.$$

Under the linear-Gaussian model, the likelihood that measurement $j$ came from track $i$ is

$$g_{ij} = \mathcal{N}(\mathbf{z}_j;\, H \hat{\mathbf{x}}^{i}_{k \mid k-1},\, S_i) = \frac{\exp\!\left(-\tfrac{1}{2} d_{ij}^2\right)}{\sqrt{\det(2\pi S_i)}}, \qquad d_{ij}^2 = \mathbf{y}_{ij}^\top S_i^{-1} \mathbf{y}_{ij},$$

where $d_{ij}^2$ is the squared Mahalanobis distance.

Gating. If the model is correct, $d_{ij}^2$ for the true measurement follows a chi-squared distribution with $m$ degrees of freedom, where $m$ is the measurement dimension. Pairs with $d_{ij}^2 > \gamma$, for a chi-squared quantile $\gamma$, are discarded. The gate is an ellipsoid around each prediction that grows with the track’s uncertainty.

Hypotheses and costs. An association hypothesis $\theta$ assigns each measurement to at most one track or to clutter. Assuming detection probability $P_D$, Poisson clutter of uniform spatial density $\lambda$, independent targets, and no new targets, the posterior probability of a hypothesis is, up to a constant, a product over its decisions: each matched pair contributes $P_D \, g_{ij}$, each missed track $1 - P_D$, and each clutter measurement $\lambda$. Dividing by the all-missed, all-clutter hypothesis and taking negative logarithms, the most probable single-frame hypothesis is the minimum-cost assignment with

$$c_{ij} = -\log \frac{P_D \, g_{ij}}{\lambda \, (1 - P_D)},$$

where a pair is worth accepting only if $c_{ij} < 0$, that is, only if the match is more probable than calling the track missed and the measurement clutter. The $N \times M$ matrix of $c_{ij}$ is the cost matrix. Vision trackers often use heuristic costs instead, frequently adding appearance similarity between track and detection descriptors.

Properties

• Combinatorial explosion. With $N$ tracks and $M$ measurements, the number of single-frame hypotheses is $\sum_{r=0}^{\min(N,M)} \binom{N}{r}\binom{M}{r}\, r!$. For $N = M = 10$ this is about $2.3 \times 10^8$, and multi-frame hypotheses multiply such counts. Gating splits the problem into independent clusters of tracks that share candidate measurements.
• Ambiguity under occlusion and crossing targets. When targets are close, several hypotheses are similarly probable; a wrong choice is an identity switch, and the Kalman update then corrupts both tracks.
• Uncertain tracks attract matches. A track undetected for several frames has a large $S_i$, so in Mahalanobis terms it looks closer to a detection than a confidently tracked neighbor does. Wojke et al. (2017) give this as the reason DeepSORT matches recently seen tracks first.
• Online errors are irreversible. Batch methods trade latency for the ability to revisit them.

Main Families

Nearest neighbor and global nearest neighbor. Giving each track its closest gated measurement can assign one measurement to two tracks. Global nearest neighbor instead solves the one-to-one assignment that minimizes total cost over the whole matrix, typically with the Hungarian algorithm or a related solver. It commits to one hypothesis per frame and is standard in tracking-by-detection systems such as SORT.

Probabilistic data association (PDA) and joint PDA (JPDA). PDA updates a single target in clutter with a weighted combination of all gated measurements, weighting each by the posterior probability that it is the correct one, alongside the probability that none is (Bar-Shalom & Tse, 1975). Its covariance is inflated to reflect the remaining uncertainty about origin. JPDA extends this to a known number of targets by computing association probabilities over joint events in which no measurement is shared, so targets competing for the same measurements are handled consistently; Fortmann, Bar-Shalom & Scheffe (1983) applied it to passive sonar tracking. Neither method initiates tracks or keeps alternative hypotheses beyond the current scan.

Multiple hypothesis tracking (MHT). Reid (1979) proposed keeping a branching set of association hypotheses across scans, each a full interpretation of which measurements come from known targets, new targets, or false alarms, so that a measurement can be attributed using later as well as earlier data. Track initiation is built in. To keep the count manageable, the algorithm divides targets and measurements into independent clusters, eliminates unlikely hypotheses, and combines those with similar target estimates.

Network-flow (min-cost-flow) batch association. Offline trackers associate a whole sequence at once. Zhang, Li & Nevatia (2008) mapped maximum-a-posteriori association onto a cost-flow network whose edges carry costs for linking detections across frames, for starting and ending trajectories, and for treating a detection as a false alarm. Each unit of flow is one trajectory; unit capacities keep trajectories from sharing a detection. A min-cost flow algorithm finds the optimal association without hypothesis pruning. For long occlusions the paper augments the network with an explicit occlusion model, solved iteratively on top of the basic algorithm.

Learned association. Modern trackers learn part or all of the association. DeepSORT combines the Kalman Mahalanobis distance, gated at the 95% chi-squared quantile, with the cosine distance between embeddings from a person re-identification network, keeping a gallery of each track’s recent embeddings to recover identities after occlusion; under strong camera motion, the authors rank by appearance alone and keep the Mahalanobis distance only as a gate (Wojke, Bewley & Paulus, 2017). ByteTrack uses the low-confidence detections that most trackers discard: it first matches high-score detections to all tracks, then matches the remaining tracks to low-score detections by box overlap alone, since appearance is unreliable for occluded or blurred boxes, and drops low-score detections left unmatched as background (Zhang et al., 2022). Others learn affinities with graph neural networks or, in transformer trackers, carry a query per track across frames so that association happens implicitly through attention.

Cost Functions in Vision

• Intersection over union (IoU). The cost $1 - \text{IoU}$ between predicted and detected boxes: cheap and scale-aware, but uninformative once fast or small objects no longer overlap their predictions.
• Center distance. Distance between box centers, often normalized by box size; it works without overlap but ignores shape.
• Mahalanobis distance. Principled, as above, but unmodeled camera motion breaks it.
• Appearance cosine distance. $1 - \mathbf{r}_i^\top \mathbf{r}_j$ for unit-length embeddings; it bridges long gaps where motion fails, but is unreliable for blurred, occluded, or look-alike objects.
• Combinations. Weighted sums of motion and appearance terms, where a candidate must pass each term’s gate.

Examples

Two people cross, so each now stands closer to the other’s prediction; a third track goes undetected, and a new person enters:

import numpy as np
from scipy.optimize import linear_sum_assignment

def iou(a, b):
    """IoU between every box in a and every box in b; boxes are [x1, y1, x2, y2]."""
    x1 = np.maximum(a[:, None, 0], b[None, :, 0])
    y1 = np.maximum(a[:, None, 1], b[None, :, 1])
    x2 = np.minimum(a[:, None, 2], b[None, :, 2])
    y2 = np.minimum(a[:, None, 3], b[None, :, 3])
    inter = np.clip(x2 - x1, 0, None) * np.clip(y2 - y1, 0, None)
    area = lambda r: (r[:, 2] - r[:, 0]) * (r[:, 3] - r[:, 1])
    return inter / (area(a)[:, None] + area(b)[None, :] - inter)

def normalize(v):
    return v / np.linalg.norm(v, axis=1, keepdims=True)

def solve(cost, gate):
    """Minimum-cost assignment that never accepts a pair outside the gate."""
    LARGE = 1e6
    rows, cols = linear_sum_assignment(np.where(gate, cost, LARGE))
    keep = gate[rows, cols]
    return list(zip(rows[keep].tolist(), cols[keep].tolist()))

# Predicted boxes of three tracks; tracks 0 (person A) and 1 (person B) are crossing.
tracks = np.array([[100, 100, 140, 200],
                   [110, 100, 150, 200],
                   [400, 120, 440, 220]], dtype=float)
# Detections: A has moved past B's prediction and B past A's;
# track 2 is missed, and a new person appears far away.
dets = np.array([[112, 102, 152, 202],
                 [ 98,  98, 138, 198],
                 [700, 300, 740, 400]], dtype=float)

# Unit appearance embeddings (in practice from a re-identification network).
rng = np.random.default_rng(0)
person_a, person_b, person_c, person_d = normalize(rng.normal(size=(4, 8)))
track_emb = np.stack([person_a, person_b, person_c])
det_emb = normalize(np.stack([person_a, person_b, person_d])
                    + 0.1 * rng.normal(size=(3, 8)))

motion_cost = 1.0 - iou(tracks, dets)          # 0 = perfect overlap
app_cost = 1.0 - track_emb @ det_emb.T         # cosine distance
motion_gate = motion_cost < 0.7                # require IoU > 0.3

print("IoU only:            ", solve(motion_cost, motion_gate))

lam = 0.3
combined = lam * motion_cost + (1 - lam) * app_cost
gate = motion_gate & (app_cost < 0.4)
matched = solve(combined, gate)
print("IoU + appearance:    ", matched)
print("unmatched tracks:    ", sorted(set(range(3)) - {i for i, _ in matched}))
print("unmatched detections:", sorted(set(range(3)) - {j for _, j in matched}))

Output:

IoU only:             [(0, 1), (1, 0)]
IoU + appearance:     [(0, 0), (1, 1)]
unmatched tracks:     [2]
unmatched detections: [2]

Overlap alone swaps the two identities. The combined cost keeps them correct and leaves track 2 unmatched, to coast on its prediction or be deleted after enough misses, and detection 2 as a candidate new track, usually confirmed only after a few consecutive matches.

Common Misconceptions

• “Association is just the Hungarian algorithm.” Results depend far more on the cost function, the gates, and the rules for track birth and death than on the solver.
• “The optimal assignment is the correct one.” It is optimal only for the given costs in one frame; when targets are genuinely ambiguous, any single-frame decision can be wrong, which is why MHT and batch methods defer or revisit it.
• “Unmatched means lost.” An unmatched track may be occluded, and an unmatched detection may be a false alarm. Treating either as definitive causes fragmented tracks or spurious new ones.

Where It Is Used

• Multi-object tracking. Every tracking-by-detection system, from SORT to ByteTrack, centers on a per-frame association step; offline trackers use network-flow or graph formulations.
• Radar, sonar, and air traffic control. PDA, JPDA, and MHT were developed for these settings, where clutter is dense and targets are points without appearance.
• SLAM and feature correspondence. Matching observed landmarks to the map, or keypoints between frames as in feature tracking, is the same problem, with gating and robust estimation rejecting wrong correspondences.
• Sensor fusion. Camera, lidar, and radar detections must be associated before they can be fused.
• Evaluation. Multi-object tracking metrics first match predictions to ground truth, so scores depend on that matching.