control//state estimation//multi-target tracking//data association
Data association is the decision of which measurement belongs to which tracked object, taken before any filter is updated, and it is the core of multi-target tracking and of matching observations to landmarks in SLAM. A filter given the wrong measurement corrects confidently towards the wrong place, so the method chosen for association decides more of a tracker's behaviour than its filters do.
Data association is the decision of which measurement belongs to which tracked object, taken before any filter is updated, and it is the core of multi-target tracking and of matching observations to landmarks in SLAM. A filter given the wrong measurement corrects confidently towards the wrong place, so the method chosen for association decides more of a tracker's behaviour than its filters do.
It works in two steps. The first discards impossible pairs: for each track and echo the filter's innovation ν\nuν is compared with its expected covariance SSS through the Mahalanobis distance, and a pair with d2=νTS−1νd^2=\nu^{\mathsf T}S^{-1}\nud2=νTS−1ν above a chi-square threshold (9.21 for a two-dimensional measurement at 99 %) is never considered (innovation gating). The second pairs what is left. The global version solves it over all tracks and echoes at once:
minaij∈{0,1} ∑i,jaij dij2,each echo to at most one track, each track to at most one echo.\min_{a_{ij}\in\{0,1\}}\;\sum_{i,j}a_{ij}\,d_{ij}^2,\qquad \text{each echo to at most one track, each track to at most one echo.}aij∈{0,1}mini,j∑aijdij2,each echo to at most one track, each track to at most one echo.
That is an assignment problem, solved by the Hungarian algorithm in O(n3)O(n^3)O(n3) (in Python, scipy.optimize.linear_sum_assignment), the same algorithm that shares orders among warehouse robots.
The gate is a nightclub bouncer.
It decides who gets in, never who dances with whom; the pairing is the next step, inside.
Nearest-neighbour association lets each track take its closest echo. It costs almost nothing and is enough when targets are separated by more than a few measurement deviations; it fails when targets come close or cross, because two tracks fight over one echo.
Global nearest neighbour (GNN in the tracking literature, which shares the acronym with graph neural networks), the optimal one-to-one assignment above, is the industrial workhorse and holds through crossings far better. Its weakness is that a wrong hard decision under heavy clutter is never undone.
Joint probabilistic data association (JPDA) does not choose: it corrects each track with the average of the echoes in its gate, each weighted by the probability of that pairing. It copes with clutter, and the tracks of targets that move together tend to merge.
Multiple hypothesis tracking (MHT) keeps several association hypotheses alive and decides scans later, pruning the unlikely ones. It is the most robust and the most expensive, and it fails when the computing budget cannot hold the hypotheses it needs. JPDA and MHT appear in demanding surveillance systems; GNN with a gate is what most products ship.