Main Content

Assignment using k-best global nearest neighbor

`[`

returns a table of assignments, `assignments`

,`unassignedrows`

,`unassignedcolumns`

,`cost`

] = assignkbest(`costmatrix`

,`costofnonassignment`

)`assignments`

, of detections to tracks
using the Jonker-Volgenant algorithm. The algorithm finds the global nearest neighbor (GNN)
solution that minimizes the total cost of the assignments.

The cost of each potential assignment is contained in the cost
matrix, `costmatrix`

. Each matrix entry represents the cost of a possible
assignments. Matrix rows represent tracks and columns represent detections. All possible
assignments are represented in the cost matrix. The lower the cost, the more likely the
assignment is to be made. Each track can be assigned to at most one detection and each detection
can be assigned to at most one track. If the number of rows is greater than the number of
columns, some tracks are unassigned. If the number of columns is greater than the number of
rows, some detections are unassigned. You can set an entry of `costmatrix`

to
`Inf`

to prohibit an assignment.

`costofnonassignment`

represents the cost of leaving tracks or
detections unassigned. Higher values increase the likelihood that every existing object is
assigned.

All inputs must all be single precision or all be double precision.

The function returns a list of unassigned tracks, `unassignedrows`

, a
list of unassigned detections, `unassignedcolumns`

, and the cost of
assignment, `cost`

.

`[`

also
specifies the number, `assignments`

,`unassignedrows`

,`unassignedcolumns`

,`cost`

] = assignkbest(`costmatrix`

,`costofnonassignment`

,`k`

)`k`

, of *k*-best global nearest
neighbor solutions that minimize the total cost of assignments. In addition to the best
solution, the function uses the Murty algorithm to find the remaining *k*-1
solutions.

`[`

also specifies the algorithm, `assignments`

,`unassignedrows`

,`unassignedcolumns`

,`cost`

] = assignkbest(`costmatrix`

,`costofnonassignment`

,`k`

,`algorithm`

)`algorithm`

, for finding the
assignments.

[1] Murty, Katta G. "*An
algorithm for ranking all the assignments in order of increasing cost.*"
Operations research 16, no. 3 (1968): 682-687.

[2] Samuel Blackman and Robert Popoli.
*Design and Analysis of Modern Tracking Systems*, Artech House,
1999.

[3] Miller, M. L., et al.
“*Optimizing Murty’s Ranked Assignment Method.*” IEEE Transactions on
Aerospace and Electronic Systems, vol. 33, no. 3, July 1997, pp. 851–62. DOI.org (Crossref),
doi:10.1109/7.599256.