## 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 (m1, m2, m3, …) 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 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 (Pd) of the sensor — Pd 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 Pd 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:

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 tk and receives several detections at time tk+1. To form a validation gate at time tk+1, the tracker first needs to obtain the predicted measurement as:

`${\stackrel{^}{y}}_{k+1}=h\left({\stackrel{^}{x}}_{k+1|k}\right)$`

where is the track estimate predicted from time tk and is the measurement model that outputs the expected measurement given the track state. The observation residual vector is

`$\stackrel{˜}{y}={y}_{k+1}-{\stackrel{^}{y}}_{k+1}$`

where yk+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}\left({y}_{k+1}\right)={\stackrel{˜}{y}}^{T}{S}^{-1}\stackrel{˜}{y}\le 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 yi (i = 1,…,n) can be determined by comparing its Mahalanobis distance d2 (yi) with the gating threshold G. If d2 (yi) < G, then detection yi 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, T1 represents a predicted track estimate, and O1O6 are six detections. Based on the gating result, O1, O2, and O3 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}_{ij}={d}_{ij}+\mathrm{ln}\left(|{S}_{ij}|\right)$`

where dij is the Mahalanobis distance and ln(|Sij|), 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 O1 O2 O3 O4 T1 9 6 X 6 T2 X 3 10 X T2 8 4 X X

For this problem, the highlighted optimal solution can be found by enumeration. Detection O3 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 Cij, find an assignment Z = {zij} that minimizes

`$J=\sum _{i=0}^{n}\sum _{j=0}^{m}{C}_{ij}{z}_{ij}$`

subject to two constraints:

`$\begin{array}{l}\sum _{i=0}^{m}{z}_{ij}=1,\forall j\\ \sum _{j=0}^{n}{z}_{ij}=1,\forall i\end{array}$`

If track i is assigned to observation j, then zij = 1. Otherwise, zij = 0. zi0 = 1 represents the hypothesis that track i is not assigned to any detection. Similarly, z0j = 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 Joker-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:

`$\left[\begin{array}{cccc}10& 5& 8& 9\\ 7& ×& 20& ×\\ \begin{array}{l}×\\ ×\end{array}& \begin{array}{l}21\\ 15\end{array}& \begin{array}{l}×\\ 17\end{array}& \begin{array}{l}×\\ ×\end{array}\\ ×& ×& 16& 22\end{array}\right]$`

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 T1 and observations O1, O2, and O3. Assume the association probability of these three observations are p11, p12, and p13, and their residuals relative to track T1 are , , and , respectively. Then the weighted sum of the residuals associated with track T1 is:

`${\stackrel{˜}{y}}_{1}=\sum _{j=1}^{3}{p}_{1j}{\stackrel{˜}{y}}_{1j}$`

In the tracker, the weighted residual is used to update track T1 in the correction step of the tracking filter. In the filter, the probability of unassignment, p10, is also required to update track T1. 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 T2 conflicts with T1 on the assignment of observation O3. Therefore, to calculate the association probability p13, the joint probability that T2 is not assigned to O3 (that is T2 is assigned to O6 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 T1 resulting in hypothesis T10

• Assign O1 to T1 resulting in hypothesis T11

• Assign O2 to T1 resulting in hypothesis T12

• Assign O3 to T1 resulting in hypothesis T13

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 p10 and p11 are larger than the threshold, then only T10 and T11 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 (O1x) Second Scan Observation (O2x) Third Scan Observation (O3x) 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 cijk 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, c011 = -10.2. Several track hypotheses conflict with other in the table. For instance, the two most likely assignments, c111 and c121 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 M1, M2, and M3 observations, respectively. Denote an observation of scan 1, 2, and 3 as i, j, and k, respectively. For example, i = 1, 2, …, M1. Use zijk to represent the track formation hypothesis of O1i, O2j, and O3k. If the hypothesis is valid, then zijk = 1; otherwise, zijk = 0. As mentioned, cijk is used to represent the cost of zijk association. cijk is 0 for false alarms and negative for possible associations. The S-D optimization problem can be formulated as:

`$J\left(z\right)=\underset{i,j,k}{\mathrm{min}}\sum _{i=0}^{{M}_{1}}\sum _{j=0}^{{M}_{2}}\sum _{k=0}^{{M}_{3}}{c}_{ijk}{z}_{ijk}$`

subject to three constraints:

`$\begin{array}{l}\sum _{i=0}^{{M}_{1}}\sum _{j=0}^{{M}_{2}}{z}_{ijk}=1,\forall k=1,2,\dots ,{M}_{3}\\ \sum _{i=0}^{{M}_{1}}\sum _{k=0}^{{M}_{3}}{z}_{ijk}=1,\forall j=1,2,\dots ,{M}_{2}\\ \sum _{j=0}^{{M}_{2}}\sum _{k=0}^{{M}_{3}}{z}_{ijk}=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\left(\lambda \right)=\sum _{k=0}^{{M}_{3}}{\lambda }_{k}\left[\sum _{i=0}^{{M}_{1}}\sum _{j=0}^{{M}_{2}}{z}_{ijk}-1\right]$`

where λk, k = 1, 2, …, M3 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.