Next: 19 Parallel Computing in Up: 18.4.5 Three-dimensional Tracking Previous: 18.4.5 Three-dimensional Tracking

### Track Extension Associations

Given a list of existing three-dimensional tracks and a set of observations from a particular sensor, the track extension task nominally consists of three basic steps:

1. Evaluate the cost matrix for associating individual tracks with entries from the data set.
2. Find the optimal association by minimization of the global score of Equation 18.5.
3. Update each track according to its associated data item, using a full three-dimensional kinematic Kalman filter.
This nominal algorithm is hopelessly slow. If the track file and data set each have a characteristic size N, Step 1 requires operations and Step 2 requires . The reduction of the unacceptable polynomial complexities of Steps 2 and 3 to something approaching is done as follows.

A list of predicted data values for existing tracks is evaluated and is sorted using the same key as was used sorting the data set. The union of the sorted prediction and data sets is then broken into some number of gross subblocks, defined by appropriately large gaps in values of the sorting key. This reduces the single large association problem into a number of smaller subproblems.

For each subproblem, a pruned distance matrix is evaluated, subject to two primary constraints:

• Individual associations are considered only if the association score is less than some maximum allowed score value.
• The number of data value to be associated with any one track prediction is limited to some preset maximum.
The score for an individual association is the distance between prediction and datum, weighted by the prediction uncertainty:

where, for i = y,z ,

and is the predicted variance for Equation 18.15 according to the three-dimensional tracking filter. The score is essentially a for the proposed association, and the cutoff value is typically of order . The maximum allowed number of associations for any single prediction is typically -8. If more than data give acceptable association scores, the possible pairings are sorted by the association score and only the best fits (lowest scores) are kept.

The preceding scoring algorithm leads to a (generally) sparse distance matrix for the large subblocks defined through gaps in the sorting keys. The next step in the algorithm is a quick block diagonalization of the distance matrix through appropriate reorderings of the rows and columns. By this point, the original large association problem has been reduced to a large number of modest sized subproblems and Munkres algorithm for minimizing the global cost in Equation 18.5 is (finally) used to find the optimal pairings.

Next: 19 Parallel Computing in Up: 18.4.5 Three-dimensional Tracking Previous: 18.4.5 Three-dimensional Tracking

Guy Robinson
Wed Mar 1 10:19:35 EST 1995