P7-T2 — Object Association and Identity

Learning objectives

After this lesson, you should be able to:

• Build a cost matrix between predicted tracks and detections and apply a gate.
• Show with an example why greedy nearest-first assignment can be suboptimal and what optimal assignment optimises.
• Compute a squared statistical (Mahalanobis) distance and gate it with a chi-square limit.
• Define identity switches and fragmentation and compute MOTA from its counts.

The idea: a global decision about who is who

Suppose three tracks and three detections. Each track could claim any detection, so there are six ways to pair them (three factorial). Choosing track 1’s nearest detection is a local decision; if track 2’s only reasonable detection is the same one, track 2 is left with a bad choice. The pairing has to be decided for all tracks together.

Three ingredients

1. A cost. A number for each (track, detection) pair that is small when they likely belong together: the distance between the predicted position and the detection, possibly plus differences in size, class or appearance.
2. A gate. A limit on the cost above which a pair is not allowed. It removes the absurd pairs, keeps the search small and lets the tracker say “none of these” and start a new track (Lab P7-L2, stage 1).
3. An assignment rule. A procedure that picks pairs so that each track and each detection is used at most once. The rule can be greedy, or optimal in the sense of the lowest total cost.

Greedy and optimal

The greedy rule sorts all allowed pairs by cost and takes them from the cheapest, skipping a pair if its track or its detection is already used. It is simple and fast, and it is what Lab P7-L1 uses. It can be wrong, as the figure shows, because a locally cheap pair may use up a detection that another track needs much more. The optimal rule chooses the set of pairs with the lowest total cost, after first maximising the number of pairs, so that a track is not left unmatched when a full matching exists. It is computed with the Hungarian algorithm (also called Munkres, or Kuhn–Munkres), which solves the problem in polynomial time, about the cube of the number of objects. For the handful of objects in the labs a recursive search gives the same answer.

Identity

The tracker gives each track an identifier. Two kinds of errors concern identity. An identity switch occurs when an object that carried identifier A is next given identifier B: the identities of two objects may be exchanged when they come close, or one object is given a new identifier after a gap. Fragmentation is when one object’s trajectory is split into several tracks. Both matter to a planner: an exchanged identity can send a robot to avoid the wrong person’s predicted path, and a fragmented one loses velocity history.

The mathematics: costs, uncertainty and metrics

Let the tracks be i = 1 … m with predicted positions p_i, and the detections j = 1 … n with positions z_j. The simplest cost is the Euclidean distance c_ij = ‖z_j − p_i‖, with the gate c_ij ≤ g. The assignment problem chooses a set of pairs A, each track and detection in at most one pair, to

A fixed distance gate ignores that some tracks are better known than others. The squared Mahalanobis distance measures the offset in units of the track’s own uncertainty:

z_j − p_i

the difference between the detection and the track’s predicted position (the innovation).

S_i

the covariance of that difference: the track’s prediction uncertainty plus the detector’s measurement noise. For independent x and y with standard deviations σx and σy, it is diagonal and d² = (Δx/σx)² + (Δy/σy)².

d²

a dimensionless number. If the detection is the true match and the noise is Gaussian, d² follows a chi-square distribution with 2 degrees of freedom (for a 2D position).

The gate becomes a probability statement: d² ≤ 5.99 keeps 95% of true matches, d² ≤ 9.21 keeps 99% (two degrees of freedom). A track that has been coasting has a large S and therefore a wide gate; a track updated one frame ago has a narrow one.

Counting errors. Over a sequence, let FN be the number of true objects not tracked (misses), FP the number of tracker outputs that match no object (false positives), IDSW the identity switches, and GT the total number of true object appearances (object-frames). The MOTA (multiple object tracking accuracy) score is

It counts each error type equally, can be negative, and is dominated by FN and FP when the sequence is long; it says little about how well identity is kept. IDF1 is built to measure identity directly: the F1 score of the identities, found by matching each true trajectory to a predicted one over the whole sequence. More recent measures such as HOTA balance detection and association explicitly.

Worked examples: cost matrix, Mahalanobis gate, MOTA

Greedy against optimal. The cost matrix is C = [[1, 3], [4, 10]] (rows: T1, T2; columns: D1, D2), with a gate of 12. Greedy: the cheapest pair is (T1, D1) at 1; T2 can then use only D2, at 10. Total 11. Optimal: compare the two complete matchings. {(T1, D1), (T2, D2)} costs 1 + 10 = 11; {(T1, D2), (T2, D1)} costs 3 + 4 = 7. The optimal total is 7, which is 36% lower.

Cardinality matters too. With C = [[1, 5], [6, 20]] and a gate of 12, greedy takes (T1, D1) at 1 and cannot match T2 (its only remaining cost, 20, exceeds the gate): one pair. The matching {(T1, D2), (T2, D1)} gives two pairs at 5 + 6 = 11. Optimal assignment maximises the number of pairs first, so it picks the second.

Mahalanobis gate. A track was updated in the last frame and has σ = (1, 1) in x and y. Another has been coasting for five frames with σ = (2, 2). Each has a detection offset of (4, 3) from its prediction, a Euclidean distance of 5.

The same offset is a clear mismatch for the track that is known well and an acceptable match for the one that is not. A fixed gate of 5 units would treat them alike.

MOTA. Over a sequence with GT = 200 object appearances, a tracker has 16 misses, 10 false positives and 4 identity switches. MOTA = 1 − (16 + 10 + 4) / 200 = 1 − 0.15 = 0.85. The four switches count the same as four misses, though a swap between two pedestrians may be far more dangerous than a missed frame; for that reason identity measures such as IDF1 are reported beside it.

Engineering implications and limitations

Gate on uncertainty, not on pixels. A statistical gate adapts to coasting tracks, fast objects and noisy detections. A fixed gate must be tuned for the worst case and then admits too many candidates for the best.

Use more than distance. Combine position with the object’s class, size and, where available, an appearance descriptor. Two pedestrians in similar clothes are hard to separate by appearance and easy by position; two parked cars are the reverse. A matching class is a cheap and strong cue: never assign a person’s track to a car’s detection.

Do the assignment in stages. Many trackers match high-confidence detections first, then try low-confidence ones against the remaining tracks, then handle new tracks. This keeps weak detections from stealing a good track.

Prefer optimal assignment when objects are close. Greedy is fine when objects are far apart. In crowds, use the Hungarian algorithm or a library implementation; it is a standard routine and costs little for tens of objects.

Decide what to do when association is ambiguous. If two assignments have nearly the same cost, the tracker can keep both hypotheses (multiple hypothesis tracking) or mark the tracks as uncertain so that the planner does not rely on their identity. A confident wrong identity is worse than an honest “not sure”.

Report identity metrics, not only MOTA. A system with a good MOTA can still swap identities every time two objects cross.

Common misconceptions

Engineering takeaways

1. Association needs a cost, a gate and an assignment rule; the decision is global, not per track.
2. Greedy nearest-first can be suboptimal: for C = [[1, 3], [4, 10]] it costs 11 against an optimum of 7, and it can leave a track unmatched.
3. The squared Mahalanobis distance divides offsets by the track’s own uncertainty; gate on chi-square limits (5.99 for 95%, 9.21 for 99% at two degrees of freedom).
4. Identity switches and fragmentation are the identity errors; MOTA = 1 − (FN + FP + IDSW)/GT combines all errors, IDF1 and HOTA measure identity better.
5. Use class, size and appearance beside position, and report ambiguity instead of guessing silently.

References and further reading

Papers for the algorithms and metrics named. The cost matrices, uncertainties and counts in the examples are constructed for teaching.

• Kuhn, H. W. (1955). The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly; Munkres, J. (1957). Algorithms for the Assignment and Transportation Problems. Journal of the SIAM.
• Bernardin, K. and Stiefelhagen, R. (2008). Evaluating Multiple Object Tracking Performance: The CLEAR MOT Metrics. EURASIP Journal on Image and Video Processing.
• Ristani, E., Solera, F., Zou, R., Cucchiara, R. and Tomasi, C. (2016). Performance Measures and a Data Set for Multi-Target, Multi-Camera Tracking. ECCV Workshops: IDF1.
• Luiten, J. et al. (2021). HOTA: A Higher Order Metric for Evaluating Multi-Object Tracking. International Journal of Computer Vision.
• Wojke, N., Bewley, A. and Paulus, D. (2017). Simple Online and Realtime Tracking with a Deep Association Metric. ICIP: Mahalanobis gating plus appearance.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: what a track carries and how it moves: state, motion models and the first filter.

Related content

Nothing below is required to finish this lesson.

• Before
  P7-T1: Detection Across Consecutive Frames

  Explain what detections give frame by frame and why this is not yet tracking.

• Lab
  P7-L1: Track Moving Objects Across Simulated Frames

  Link detections over time with nearest-neighbour association and see where it fails.

• Lab
  P7-L2: Repair an Object-Association Algorithm

  Fix a greedy association with gating and an optimal assignment.