Main Content

assignkbest

Assignment using k-best global nearest neighbor

collapse all in page

Syntax

[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment)
[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment,k)
[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment,k,algorithm)

Description

[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment) returns a table of assignments, 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.

[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment,k)also specifies the number, 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.

example

[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment,k,algorithm) also specifies the algorithm, algorithm, for finding the assignments.

Examples

collapse all

Open Live Script

Create a cost matrix containing prohibited assignments. Then, use the assignkbest function to find the 5 best solutions.

Set up the cost matrix to contain some prohibited or invalid assignments by inserting Inf into the matrix.

costMatrix = [10 5 8 9; 7 Inf 20 Inf; Inf 21 Inf Inf; Inf 15 17 Inf; Inf inf 16 22];
costOfNonAssignment = 100;

Find the 5 best assignments.

[assignments,unassignedrows,unassignedcols,cost] = ...
    assignkbest(costMatrix,costOfNonAssignment,5)
assignments=5×1 cell array
    {4x2 uint32}
    {4x2 uint32}
    {4x2 uint32}
    {4x2 uint32}
    {4x2 uint32}


unassignedrows=5×1 cell array
    {[3]}
    {[3]}
    {[3]}
    {[4]}
    {[5]}


unassignedcols=5×1 cell array
    {0x1 uint32}
    {0x1 uint32}
    {0x1 uint32}
    {0x1 uint32}
    {0x1 uint32}


cost = 5×1

   147
   151
   152
   153
   154

Input Arguments

collapse all

Cost matrix, specified as an M-by-N matrix. M is the number of tracks to be assigned and N is the number of detections to be assigned. Each entry in the cost matrix contains the cost of a track and detection assignment. The matrix may contain Inf entries to indicate that an assignment is prohibited. The cost matrix cannot be a sparse matrix.

Data Types: single | double

Cost of non-assignment, specified as a scalar, a two-element vector of scalars, or a two-element cell array of vectors.

  • When specified as a scalar, it represents the cost of leaving tracks or detections unassigned. Higher values increase the likelihood that every object is assigned. The value cannot be set to Inf.

  • When specified as a two-element scalars, the first element represents the cost of leaving detections unassigned and the second element represents the cost of leaving tracks unassigned.

  • When specified as a two-element cell of vectors, each element in the first vector represents the cost of leaving the specific detection unassigned and each element of the second vector represents the cost of leaving the specific track unassigned. The length of the first vector is equal to the number of detections and the length of the second vector is equal to the number of tracks.

Tip

The costofnonassignment is half of the maximum cost that a successful assignment can have.

Data Types: single | double

Number of best solutions, specified as a positive integer.

Data Types: single | double

Assignment algorithm, specified as 'jv' for the Jonker-Volgenant algorithm, 'munkres' for the Munkres algorithm, 'auction' for the Auction algorithm, or 'matchpair' for the match pair algorithm. When 'jv' is selected, the function uses heuristics defined in [3] to improve the algorithm performance.

Example: 'jv'

Data Types: char | string

Output Arguments

collapse all

Assignment of tracks to detections, returned as a k-element cell array. k is the number of best solutions. Each cell contains an Li-by-2 matrix of pairs of track indices and assigned detection indices. Li is the number of assignment pairs in the ith solution cell. The first column of each matrix contains the track indices and the second column contains the assigned detection indices.

Indices of unassigned tracks, returned as a k-element cell array. Each cell is a Pi vector where Pi = M - Li is the number of unassigned rows in the ith cell. Each element is the index of a row to which no columns are assigned. k is the number of best solutions.

Data Types: uint32

Indices of unassigned detections, returned as a k-element cell array. Each cell is a Qi vector where Qi = M - Li is the number of unassigned detections in the ith cell. Each element is the index of a column to which no rows are assigned. k is the number of best solutions.

Data Types: uint32

Total cost of solutions, returned as a k-element vector. Each element is a scalar value summarizing the total cost of the solution to the assignment problem.

Data Types: single | double

References

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

Extended Capabilities

C/C++ Code Generation
Generate C and C++ code using MATLAB® Coder™.

Version History

Introduced in R2018b

See Also

Functions