Introduction to Multiple Target Tracking

Background

Tracking is essential for the guidance, navigation, and control of autonomous systems. A tracking system estimates targets (number of targets and their states) and evaluates the situational environment in an area of interest by taking detections (kinematic parameters and attributes) and tracking these targets with time. The simplest tracking system is a single target tracking (STT) system in a clutterless environment, which assumes one target only in an area of interest. An STT does not require data assignment or association, because the detection of the standalone target can be directly fed to an estimator or filter used to estimate the state of the target.

Modern tracking systems usually involve multiple target tracking (MTT) systems, in which one or more sensors generate multiple detections from multiple targets, and one or more tracks are used to estimate the states of these targets. An MTT must assign detections to tracks before the detections can be used to update the tracks. The MTT assignment problem is challenging because of several factors:

Target or detection distribution — If targets are sparsely distributed, then associating a target to its corresponding detection is relatively easy. However, if targets or detections are densely distributed, the assignment becomes ambiguous because assigning a target to a detection or a nearby detection rarely makes any differences on the cost.
Probability of detection (P_d) of the sensor — P_d describes the probability that a target is detected by the sensor if the target is within the field of view of the sensor. If the P_d of a sensor is small, then the true target might not generate any detection during a sensor scan. As a result, the track represented by the true target may steal detections from other tracks.
Sensor resolution — Sensor resolution determines the sensor’s ability to distinguish between detections from two targets. If the sensor resolution is low, then two targets in proximity might only give rise to one detection. This violates the common assumption that each detection can only be assigned to one track and results in unresolvable assignment conflicts between tracks.
Clutter or false alarm rate of the sensor — False alarms introduce additional possible assignments and therefore increase the complexity of data assignment.
The number of targets and detections — The number of possible assignments increases exponentially as the number of targets and detections increases. Therefore, obtaining an optimal assignment requires more computations.

Elements of an MTT System

The figure gives a structural representation of the functional elements of a simple recursive MTT system [1]. In real world applications, the functions of these elements can overlap considerably. However, this representation provides a convenient partitioning to introduce the typical functions in an MTT system.

To interpret this diagram, assume a tracker has maintained confirmed or tentative tracks from the previous scan. Now, the system considers whether to update tracks based on any new detections received from sensors. To assign detections to the corresponding tracks:

The internal filter (such as a Kalman filter) predicts the confirmed or tentative tracks from the previous step to the current step.
The tracker uses the predicted estimate and covariance to form a validation gate around the predicted track.
The detections falling within the gate of a track are considered as candidates for assignment to the track.
An assignment algorithm (based on the specific tracker, such as GNN or TOMHT) determines the track-to-detection association.
Based on the assignment, the tracker executes track maintenance, including initialization, confirmation, and deletion:
- Unassigned observations can initiate new tentative tracks.
- A tentative track becomes confirmed if the quality of the track satisfies the confirmation criteria.
- Low-quality tracks are deleted based on the deletion criteria.
The new track set (tentative and confirmed) is predicted to the next scan step to form validation gates.

Detections

Detection is a collective term used to refer to all the observed or measured quantities included in a report output (see objectDetection for example) from a sensor. In general, an observation may contain measured kinematic quantities (such as range, line of sight, and range-rate) and measured attributes (such as target type, identification number, and shape). A detection should also contain the time at which measurements are obtained.

For point target tracking, detections received from a single sensor scan can contain at most one observation from each target. This assumption greatly simplifies the assignment problem. One sensor can generate zero detections for a target within its field of view, because the probability of detection, P_d, of each sensor is usually less than 1. Also, each sensor can generate false alarm detections that do not correspond to true targets.

High-resolution sensors may generate multiple detections per target, which requires partitioning the detections into one representative detection before feeding to assignment-based trackers (such as trackerGNN, trackerJPDA, and trackerTOMHT). See Extended Object Tracking of Highway Vehicles with Radar and Camera for more details.

Gating and Assignment

For details about gating and assignment, see Introduction to Assignment Methods in Tracking Systems, which provides a comprehensive introduction of assignment methods. This section only covers the basics of gating and assignment used in the three assignment-based trackers, trackerGNN, trackerJPDA, and trackerTOMHT.

Gating is a screening mechanism used to determine which detections are valid candidates to update existing tracks. The purpose of gating is to reduce unnecessary computation in track-to-detection assignment. A validation gate of a predicted track is formed using the predicted state and its associated covariance, such that the detections with high probability of association fall within the validation gate of a track. Only the detections within the gate of a track are considered for assignment with the track.

After gating, the assignment function determines which track-to-detection assignments to make. Three methods of assignment are used with three trackers in the toolbox:

trackerGNN — Global nearest data association. Based on likelihood theory, the goal of the GNN method is to minimize an overall distance function that considers all track-to-detection assignments.
trackerJPDA — Joint probability data association. The JPDA method applies a soft assignment, such that detections within the validation gate of a track can all make weighted contributions to the track based on their probability of association.
trackerTOMHT — Track-oriented multiple hypothesis tracking. Unlike GNN and JPDA, MHT is a deferred decision approach, which allows difficult data association situations to be postponed until more information is received.

The decision of which tracker to use depends on the type of targets and computational resources available:

The GNN algorithm is the simplest to employ. It has low computational cost and can result in adequate performance for tracking sparsely distributed targets.
The JPDA algorithm, which requires more computational cost, is also applicable for widely spaced targets. It usually performs better in a clutter environment than GNN.
The TOMHT tracker, which requires heavily on computational resources, normally results in the best performance among all the three trackers, especially for densely distributed targets.

For more details, see the Tracking Closely Spaced Targets Under Ambiguity example for a comparison of these three trackers.

Track Maintenance

Track maintenance refers to the function of track initiation, confirmation, and deletion.

Track Initiation. When a detection is not assigned to an existing track, a new track might need to be created:

The GNN approach starts new tentative tracks on observations that are not assigned to existing tracks.
The JPDA approach starts new tentative tracks on observations with probability of assignment lower than a specified threshold.
The MHT approach starts new tentative tracks on observations whose distances to existing tracks are larger than a specified threshold. The tracker uses subsequent data to determine which of these newly initiated tracks are valid.

Track Confirmation. Once a tentative track is formed, a confirmation logic identifies the status of the track. Three track confirmation logics are used in the toolbox:

History Logic: A track is confirmed if the track has been assigned to a detection for at least M updates during the last N updates. You can set the specific values for M and N. trackerGNN and trackerJPDA use this logic.
Track Score Logic: A track is confirmed if its score is higher than a specified threshold. A higher track score means that the track is more likely to be valid. The score is the ratio of the probability that the track is from a real target to the probability that the track is false. trackerGNN and trackerTOMHT use this logic.
Integrated Logic: A track is confirmed if its integrated probability of existence is higher than a threshold. trackerJPDA uses this logic.

Track Deletion. A track is deleted if it is not updated within some reasonable time. The track deletion criteria are similar to the track confirmation criteria:

History Logic: A track is deleted if the track has not been assigned to a detection at least P times during last R updates.
Track Score Logic: A track is deleted if its score decreases from the maximum score by a specified threshold.
Integrated Logic: A track is deleted if its integrated probability of existence is lower than a specified threshold.

For more details, see the Introduction to Track Logic example.

Filtering

The main functions of a tracking filter are:

Predict tracks to the current time.
Calculate distances from the predicted tracks to detections and the associated likelihoods for gating and assignment.
Correct the predicted tracks using assigned detections.

Sensor Fusion and Tracking Toolbox™ offers multiple tracking filters that can be used with the three assignment-based trackers (trackerGNN, trackerJPDA, and trackerTOMHT). For a comprehensive introduction of these filters, see Introduction to Estimation Filters.

Tracking Metrics

Sensor Fusion and Tracking Toolbox provides tools to analyze the tracking performance if the truths are known:

You can use trackAssignmentMetrics to evaluate the performance of track assignment and maintenance. trackAssignmentMetrics provides indexes such as number of the track swaps, number of divergence steps, and number of redundant assignments.
You can use trackErrorMetrics to evaluate the accuracy of tracking. trackErrorMetrics provides multiple root mean square (RMS) error values, which numerically illustrate the accuracy performance of the tracker.
You can use trackOSPAMetric to compute the optimal subpattern assignment metric. trackErrorMetrics provides three scalar error components — localization error, labelling error, and cardinality error to evaluate tracking performance.

Non-Assignment-Based Trackers

trackerGNN, trackerJPDA, and trackerTOMHT are assignment-based trackers, meaning that the track-to-detection assignment is required. The toolbox also offers a random finite set (RFS) based tracker, trackerPHD. You can use its supporting features ggiwphd to track extended objects and gmphd to track both extended objects and point targets.

References

[1] Blackman, S., and R. Popoli. Design and Analysis of Modern Tracking Systems. Artech House Radar Library, Boston, 1999.

[2] Musicki, D., and R. Evans. "Joint Integrated Probabilistic Data Association: JIPDA." IEEE transactions on Aerospace and Electronic Systems. Vol. 40, Number 3, 2004, pp. 1093 –1099.

[3] Werthmann, J. R.. "Step-by-Step Description of a Computationally Efficient Version of Multiple Hypothesis Tracking." In International Society for Optics and Photonics, Vol. 1698, pp. 228 – 301, 1992.