Introduction to Assignment Methods in Tracking Systems

Background

In a multiple target tracking (MTT) system, one or more sensors generate multiple detections from multiple targets in a scan. To track these targets, one essential step is to assign these detections correctly to the targets or tracks maintained in the tracker so that these detections can be used to update these tracks. If the number of targets or detections is large, or there are conflicts between different assignment hypotheses, assigning detections is challenging.

Depending on the dimension of the assignment, assignment problems can be categorized into:

2-D assignment problem – assigns n targets to m observations. For example, assign 5 tracks to 6 detections generated from one sensor at one time step.
S-D assignment problem – assigns n targets to a set (m₁, m₂, m₃, …) of observations. For example, assign 5 tracks to 6 detections from one sensor, and 4 detections from another sensor at the same time. This example is a typical 3-D assignment problem.

To illustrate the basic idea of an assignment problem, consider a simple 2-D assignment example. One company tries to assign 3 jobs to 3 workers. Because of the different experience levels of the workers, not all workers are able to complete each job with the same effectiveness. The cost (in hours) of each worker to finish each job is given by the cost matrix shown in the table. An assignment rule is that each worker can only take one job, and one job can only be taken by one worker. To guarantee efficiency, the object of this assignment is to minimize the total cost.

Worker	Job
Worker	1	2	3
1	41	72	39
2	22	29	49
3	27	39	60

Since the numbers of workers and jobs are both small in this example, all the possible assignments can be obtained by enumeration, and the minimal cost solution is highlighted in the table with assignment pairs (1, 3), (2, 2) and (3, 1). In practice, as the size of the assignment becomes larger, the optimal solution is difficult to obtain for 2-D assignment. For an S-D assignment problem, the optimal solution may not be obtainable in practice.

2-D Assignment in Multiple Target Tracking

In the 2-D MTT assignment problem, a tracker tries to assign multiple tracks to multiple detections. Other than the dimensionality challenge mentioned above, a few other factors can significantly change the complexity of the assignment:

Target or detection distribution — If targets are sparsely distributed, associating a target to its corresponding detection is relatively easy. However, if targets or detections are densely distributed, assignments become ambiguous because assigning a target to a detection or another 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 may not give rise to 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 the detections from two targets. If the sensor resolution is low, then two targets in proximity may 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 complexity of the assignment task can determine which assignment methods to apply. In Sensor Fusion and Tracking Toolbox™ toolbox, three 2-D assignment approaches are employed corresponding to three different trackers:

trackerGNN — adopts a global nearest data assignment approach
trackerJPDA — adopts a joint probability data association approach
trackerTOMHT — adopts a tracker-oriented multiple hypothesis tracking approach

Note that each tracker processes the data from sensors sequentially, meaning that each tracker only deals with the assignment problem with the detections of one sensor at a time. Even with this treatment, there may still be too many assignment pairs. To reduce the number of track and detection pairs considered for assignment, the gating technique is frequently used.

Gating

Gating is a screening mechanism to determine which observations are valid candidates to update existing tracks and eliminate unlikely detection-to-track pairs using the distribution information of the predicted tracks. To establish the validation gate for a track at the current scan, the estimated track for the current step is predicted from the previous step.

For example, a tracker confirms a track at time t_k and receives several detections at time t_k+1. To form a validation gate at time t_k+1, the tracker first needs to obtain the predicted measurement as:

${\hat{y}}_{k + 1} = h ({\hat{x}}_{k + 1 | k})$

where ${\hat{x}}_{k + 1 | k}$ is the track estimate predicted from time t_k and $h ({\hat{x}}_{k + 1 | k})$ is the measurement model that outputs the expected measurement given the track state. The observation residual vector is

$\tilde{y} = y_{k + 1} - {\hat{y}}_{k + 1}$

where y_k+1 is the actual measurement. To establish the boundary of the gate, the detection residual covariance S is used to form an ellipsoidal validation gate. The ellipsoidal gate that establishes a spatial ellipsoidal region in the measurement space is defined in Mahalanobis distance as:

$d^{2} (y_{k + 1}) = {\tilde{y}}^{T} S^{- 1} \tilde{y} \leq G$

where G is the gating threshold which you can specify based on the assignment requirement. Increasing the threshold can incorporate more detections into the gate.

After the assignment gate is established for each track, the gating status of each detection y_i (i = 1,…,n) can be determined by comparing its Mahalanobis distance d² (y_i) with the gating threshold G. If d² (y_i) < G, then detection y_i is inside the gate of the track and will be considered for association. Otherwise, the possibility of the detection associated with the track is removed. In Figure 1, T₁ represents a predicted track estimate, and O₁ – O₆ are six detections. Based on the gating result, O₁, O₂, and O₃ are within the validation gate in the figure.

Global Nearest Neighbor (GNN) Method

The GNN method is a single hypothesis assignment method. For each new data set, the goal is to assign the global nearest observations to existing tracks and to create new track hypotheses for unassigned detections.

The GNN assignment problem can be easily solved if there are no conflicts of association between tracks. The tracker only needs to assign a track to its nearest neighbor. However, conflict situations (see Figure 2) occur when there is more than one observation within a track’s validation gate or an observation is in the gates of more than one track. To resolve these conflicts, the tracker must evaluate a cost matrix.

The elements of a cost matrix for the GNN method includes the distance from tracks to detections and other factors you might want to consider. For example, one approach is to define a generalized statistical distance between observation j to track i as:

$C_{i j} = d_{i j} + \ln (| S_{i j} |)$

where d_ij is the Mahalanobis distance and ln(|S_ij|), the logarithm of the determinant of the residual covariance matrix, is used to penalize tracks with greater prediction uncertainty.

For the assignment problem given in Figure 2, the following table shows a hypothetical cost matrix. The nonallowed assignments, which failed the gating test, are denoted by X. (In practice, the costs of nonallowed assignments can be denoted by large values, such as 1000.)

Tracks	Observations
Tracks	O₁	O₂	O₃	O₄
T₁	9	6	X	6
T₂	X	3	10	X
T₃	8	4	X	X

For this problem, the highlighted optimal solution can be found by enumeration. Detection O₃ is unassigned, so the tracker will use it to create a new tentative track. For more complicated GNN assignment problems, more accurate formulations and more efficient algorithms to obtain the optimal or suboptimal solution are required.

A general 2-D assignment problem can be formed as following. Given the cost matrix element C_ij, find an assignment Z = {z_ij} that minimizes

$J = \sum_{i = 0}^{n} \sum_{j = 0}^{m} C_{i j} z_{i j}$

subject to two constraints:

$\begin{array}{l} \sum_{i = 0}^{m} z_{i j} = 1, \forall j \\ \sum_{j = 0}^{n} z_{i j} = 1, \forall i \end{array}$

If track i is assigned to observation j, then z_ij = 1. Otherwise, z_ij = 0. z_i0 = 1 represents the hypothesis that track i is not assigned to any detection. Similarly, z_0j = 1 represents the hypothesis that observation j is not assigned to any track. The first constraint means each detection can be assigned to no more than one track. The second constraint means each track can be assigned to no more than one detection.

Sensor Fusion and Tracking Toolbox provides multiple functions to solve 2-D GNN assignment problems:

assignmunkres – Uses the Munkres algorithm, which guarantees an optimal solution but may require more calculation operations.
assignauction – Uses the auction algorithm, which requires fewer operations but can possibly converge on an optimal or suboptimal solution.
assignjv – Uses the Jonker-Volgenant algorithm, which also converges on an optimal or suboptimal solution but usually with a faster converging speed.

In trackerGNN, you can select the assignment algorithm by specifying the Assignment property.

K Best Solutions to the 2-D Assignment Problem

Because of the uncertainty nature of assignment problems, only obtaining a solution (optimal or suboptimal) may not be sufficient. To account for multiple hypotheses about the assignment between tracks and detections, multiple suboptimal solutions are required. These suboptimal solutions are called K best solutions to the assignment problem.

The K best solutions are usually obtained by varying the solution obtained by any of the previously mentioned assignment functions. Then, at the next step, the K best solution algorithm removes one track-to-detection pair in the original solution and finds the next best solution. For example, for this cost matrix:

$[\begin{matrix} 10 & 5 & 8 & 9 \\ 7 & \times & 20 & \times \\ \begin{array}{l} \times \\ \times \end{array} & \begin{array}{l} 21 \\ 15 \end{array} & \begin{array}{l} \times \\ 17 \end{array} & \begin{array}{l} \times \\ \times \end{array} \\ \times & \times & 16 & 22 \end{matrix}]$

each row represents the cost associated with a track, and each column represents the cost associated with a detection. As highlighted, the optimal solution is (7,15,16, 9) with a cost of 47. In the next step, remove the first pair (corresponding to 7), and the next best solution is (10,15, 20, 22) with a cost of 67. After that, remove the second pair (corresponding to 15), and the next best solution is (7, 5,16, 9) with a cost of 51. After a few steps, the five best solutions are:

Solution	Cost
(7,15,16, 9)	47
(7,5,17, 22)	51
(7,15, 8, 22)	52
(7, 21,16, 9)	53
(7, 21,17, 9)	53

See the Find Five Best Solutions Using Assignkbest example, which uses the assignkbest function to find the K best solutions.

Joint Probability Data Association (JPDA) Method

While the GNN method makes a rigid assignment of a detection to a track, the JPDA method applies a soft assignment so that detections within the validation gate of a track can all make weighted contributions to the track based on their probability of association.

For example, for the gating results shown in Figure 1, a JPDA tracker calculates the possibility of association between track T₁ and observations O₁, O₂, and O₃. Assume the association probability of these three observations are p₁₁, p₁₂, and p₁₃, and their residuals relative to track T₁ are ${\tilde{y}}_{_{11}}$ , ${\tilde{y}}_{_{12}}$ , and ${\tilde{y}}_{_{13}}$ , respectively. Then the weighted sum of the residuals associated with track T₁ is:

${\tilde{y}}_{1} = \sum_{j = 1}^{3} p_{1 j} {\tilde{y}}_{1 j}$

In the tracker, the weighted residual is used to update track T₁ in the correction step of the tracking filter. In the filter, the probability of unassignment, p₁₀, is also required to update track T₁. For more details, see JPDA Correction Algorithm for Discrete Extended Kalman Filter.

The JPDA method requires one more step when there are conflicts between assignments in different tracks. For example, in the following figure, track T₂ conflicts with T₁ on the assignment of observation O₃. Therefore, to calculate the association probability p₁₃, the joint probability that T₂ is not assigned to O₃ (that is T₂ is assigned to O₆ or unassigned) must be accounted for.

Track-Oriented Multiple Hypothesis Tracking (TOMHT) Method

Unlike the JPDA method, which combines all detections within the validation gate using a weighted sum, the TOMHT method generates multiple hypotheses or branches of the tracks based on the detections within the gate and propagates high-likelihood branches between scan steps. After propagation, these hypotheses can be tested and pruned based on the new set of detections.

For example, for the gating scenario shown in Figure 1, a TOMHT tracker considers the following four hypotheses:

Assign no detection to T₁ resulting in hypothesis T₁₀
Assign O₁ to T₁ resulting in hypothesis T₁₁
Assign O₂ to T₁ resulting in hypothesis T₁₂
Assign O₃ to T₁ resulting in hypothesis T₁₃

Given the assignment threshold, the tracker will calculate the possibility of each hypothesis and discard hypotheses with probability lower than the threshold. Hypothetically, if only p₁₀ and p₁₁ are larger than the threshold, then only T₁₀ and T₁₁ are propagated to the next step for detection update.

S-D Assignment in Multiple Target Tracking

In an S-D assignment problem, the dimension of assignment S is larger than 2. Note that all three trackers (trackerGNN, trackerJPDA, and trackerTOMHT) process detections from each sensor sequentially, which results in a 2-D assignment problem. However, some applications require a tracker that processes simultaneous observations from multiple sensor scans all at once, which requires solving an S-D assignment problem. Meanwhile, the S-D assignment is widely used in tracking applications such as static data fusion, which preprocesses the detection data before fed to a tracker.

An S-D assignment problem for static data fusion has S scans of a surveillance region from multiple sensors simultaneously, and each scan consists of multiple detections. The detection sources can be real targets or false alarms. The object is to detect an unknown number of targets and estimate their states. For example, as shown in the Figure 4, three sensor scans produce six detections. The detections in the same color belong to the same scan. Since each scan generates two detections, there are probably two targets in the region of surveillance. To choose between different assignment or association possibilities, evaluate the cost matrix.

The calculation of the cost can depend on many factors, such as the distance between detections and the covariance distribution of each detection. To illustrate the basic concept, the assignment costs for a few hypotheses are hypothetically given in the table [1].

Assignment Hypotheses	First Scan Observations (O_1x)	Second Scan Observation (O_2x)	Third Scan Observation (O_3x)	Cost
1	0	1	1	−10.2
2	1	2	0	−10.9
3	1	1	1	−18.0
4	1	1	2	−14.8
5	1	2	1	−17.0
6	2	0	1	−13.2
7	2	0	2	−10.6
8	2	2	0	−11.1
9	2	1	2	−14.1
10	2	2	2	−16.7

In the table, 0 denotes a track is associated with no detection in that scan. Assume the hypotheses not shown in the table are truncated by gating or neglected because of high costs. To concisely represent each track, use c_ijk to represent the cost for association of observation i in scan 1, j in scan 2, and k in scan 3. For example, for the assignment hypothesis 1, c₀₁₁ = -10.2. Several track hypotheses conflict with other in the table. For instance, the two most likely assignments, c₁₁₁ and c₁₂₁ are incompatible because they share the same observation in scans 1 and 3.

The goal of solving an S-D assignment problem is to find the most likely compatible assignment hypothesis accounting for all the detections. When S ≥ 3, however, the problem is known to scale with the number of tracks and detections at an exponential rate (NP-hard). The Lagrangian relaxation method is commonly used to obtain the optimal or sub-optimal solution for an S-D assignment problem efficiently.

Brief Introduce to the Lagrangian Relaxation Method for 3-D Assignment

Three scans of data have a number of M₁, M₂, and M₃ observations, respectively. Denote an observation of scan 1, 2, and 3 as i, j, and k, respectively. For example, i = 1, 2, …, M₁. Use z_ijk to represent the track formation hypothesis of O_1i, O_2j, and O_3k. If the hypothesis is valid, then z_ijk = 1; otherwise, z_ijk = 0. As mentioned, c_ijk is used to represent the cost of z_ijk association. c_ijk is 0 for false alarms and negative for possible associations. The S-D optimization problem can be formulated as:

$J (z) = \min_{i, j, k} \sum_{i = 0}^{M_{1}} \sum_{j = 0}^{M_{2}} \sum_{k = 0}^{M_{3}} c_{i j k} z_{i j k}$

subject to three constraints:

$\begin{array}{l} \sum_{i = 0}^{M_{1}} \sum_{j = 0}^{M_{2}} z_{i j k} = 1, \forall k = 1, 2, \dots, M_{3} \\ \sum_{i = 0}^{M_{1}} \sum_{k = 0}^{M_{3}} z_{i j k} = 1, \forall j = 1, 2, \dots, M_{2} \\ \sum_{j = 0}^{M_{2}} \sum_{k = 0}^{M_{3}} z_{i j k} = 1, \forall i = 1, 2, \dots, M_{1} \end{array}$

The optimization function chooses associations to minimize the total cost. The three constraints ensure that each detection is accounted for (either included in an assignment or treated as false alarm).

The Lagrangian relaxation method approaches this 3-D assignment problem by relaxing the first constraint using Lagrange multipliers. Define a new function L(λ) :

$L (λ) = \sum_{k = 0}^{M_{3}} λ_{k} [\sum_{i = 0}^{M_{1}} \sum_{j = 0}^{M_{2}} z_{i j k} - 1]$

where λ_k, k = 1, 2, …, M₃ are Lagrange multipliers. Subtract L from the original object function J(z) to get a new object function, and the first constraint in k is relaxed. Therefore, the 3-D assignment problem reduces to a 2-D assignment problem, which can be solved by any of the 2-D assignment method. For more details, see [1].

The Lagrangian relaxation method allows the first constraint to be mildly violated, and therefore can only guarantee a suboptimal solution. For most applications, however, this is sufficient. To specify the solution accuracy, the method uses the solution gap, which defines the difference between the current solution and the potentially optimistic solution. The gap is nonnegative, and a smaller solution gap corresponds to a solution closer to the optimal solution.

Sensor Fusion and Tracking Toolbox provides assignsd to solve for S-D assignment using the Lagrangian relaxation method. Similar to the K best 2-D assignment solver assignkbest, the toolbox also provides a K best S-D assignment solver, assignkbestsd, which is used to provide multiple suboptimal solutions for an S-D assignment problem.

See Tracking Using Distributed Synchronous Passive Sensors for the application of S-D assignment in static detection fusion.

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.