## 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*_{1},*m*_{2},*m*_{3}, …) 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.

| 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 (

*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:

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

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

$$\tilde{y}={y}_{k+1}-{\widehat{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}\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 *y*_{i}
(*i* = 1,…,*n*) can be determined by comparing
its Mahalanobis distance *d*^{2}
(*y*_{i}) with the gating threshold
*G*. If *d*^{2}
(*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*_{1} represents a predicted track
estimate, and *O*_{1} –
*O*_{6} are six detections. Based on the
gating result, *O*_{1},
*O*_{2}, and
*O*_{3} 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}(|{S}_{ij}|)$$

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.)

| Observations | |||

O_{1} | O_{2} | O_{3} | O_{4} | |

T_{1} | 9 | 6 | X | 6 |

T_{2} | X | 3 | 10 | X |

T_{3} | 8 | 4 | X | X |

For this problem, the highlighted optimal solution can be found by enumeration.
Detection *O*_{3} 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={\displaystyle \sum _{i=0}^{n}{\displaystyle \sum _{j=0}^{m}{C}_{ij}{z}_{ij}}}$$

subject to two constraints:

$$\begin{array}{l}{\displaystyle \sum _{i=0}^{m}{z}_{ij}=1,\forall j}\\ {\displaystyle \sum _{j=0}^{n}{z}_{ij}}=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:

$$\left[\begin{array}{cccc}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{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
*T*_{1} and observations
*O*_{1},
*O*_{2}, and
*O*_{3}. Assume the association probability
of these three observations are *p*_{11},
*p*_{12}, and
*p*_{13}, and their residuals relative to
track *T*_{1} are $${\tilde{y}}_{{}_{11}}$$, $${\tilde{y}}_{{}_{12}}$$, and $${\tilde{y}}_{{}_{13}}$$, respectively. Then the weighted sum of the residuals associated
with track *T*_{1} is:

$${\tilde{y}}_{1}={\displaystyle \sum _{j=1}^{3}{p}_{1j}{\tilde{y}}_{1j}}$$

In the tracker, the weighted residual is used to update track
*T*_{1} in the correction step of the
tracking filter. In the filter, the probability of unassignment,
*p*_{10}, is also required to update track
*T*_{1}. 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*_{2} conflicts with
*T*_{1} on the assignment of observation
*O*_{3}. Therefore, to calculate the
association probability *p*_{13}, the joint
probability that *T*_{2} is not assigned to
*O*_{3} (that is
*T*_{2} is assigned to
*O*_{6} 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*_{1}resulting in hypothesis*T*_{10}Assign

*O*_{1}to*T*_{1}resulting in hypothesis*T*_{11}Assign

*O*_{2}to*T*_{1}resulting in hypothesis*T*_{12}Assign

*O*_{3}to*T*_{1}resulting in hypothesis*T*_{13}

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*_{10}
and *p*_{11} are larger than the threshold,
then only *T*_{10} and
*T*_{11} 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*_{011} = -10.2. Several track hypotheses
conflict with other in the table. For instance, the two most likely assignments,
*c*_{111} and
*c*_{121} 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*_{1},
*M*_{2}, and
*M*_{3} observations, respectively. Denote
an observation of scan 1, 2, and 3 as *i*, *j*,
and *k*, respectively. For example, *i* = 1, 2, …,
*M*_{1}. 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)=\underset{i,j,k}{\mathrm{min}}{\displaystyle \sum _{i=0}^{{M}_{1}}{\displaystyle \sum _{j=0}^{{M}_{2}}{\displaystyle \sum _{k=0}^{{M}_{3}}{c}_{ijk}{z}_{ijk}}}}$$

subject to three constraints:

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

where
*λ*_{k},
*k* = 1, 2, …, *M*_{3} 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.

## See Also

`assignTOMHT`

| `assignauction`

| `assignjv`

| `assignkbest`

| `assignkbestsd`

| `assignmunkres`

| `assignsd`

| `trackerGNN`

| `trackerJPDA`

| `trackerTOMHT`

## 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.