References: Algorithms for Assignment and Transportation Problems, James Munkres, Journal of the Society for Industrial and Applied Mathematics Volume 5, Number 1, March, 1957 F. Burgeois and J.-C. Lasalle. An extension of the Munkres algorithm for the assignment problem to rectangular matrices. Communications of the ACM, 142302-806, 1971.
Public Types | |
typedef std::pair< code::Image< int >, HungarianMatch::Assignment > | PSPair |
Public Member Functions | |
HungarianMatch (int maxcost) | |
Nodes with cost > maxcost will be treated as unassigned. | |
Assignment | computeAssignment (const code::Image< int > &cost) |
Pass in a matrix where the (m,n)th element is the cost of assigning row no. | |
std::vector< Assignment > | computeKBestAssignments (const code::Image< int > &cost, int k) |
Pass in a matrix where the (m,n)th element is the cost of assigning row no. | |
Classes | |
struct | Assignment |
typedef std::pair<code::Image<int>, HungarianMatch::Assignment> w2img::HungarianMatch::PSPair |
w2img::HungarianMatch::HungarianMatch | ( | int | maxcost | ) | [inline] |
Nodes with cost > maxcost will be treated as unassigned.
The cost associated with a new track or a terminated track will be twice this.
Assignment w2img::HungarianMatch::computeAssignment | ( | const code::Image< int > & | cost | ) |
Pass in a matrix where the (m,n)th element is the cost of assigning row no.
m to column no. n. m need not be equal to n.
std::vector<Assignment> w2img::HungarianMatch::computeKBestAssignments | ( | const code::Image< int > & | cost, | |
int | k | |||
) |
Pass in a matrix where the (m,n)th element is the cost of assigning row no.
m to column no. n. m need not be equal to n. If there are duplicate solutions or the matrix is too small, you may not get K results back.
References: Murty, K. "An Algorithm for Ranking All the Assignments in Order of Increasing Cost", Operations Research, vol. 16, no. 3, pp 682-687 Cox, I. and Miller, M. On Finding Ranked Assignments with Application to Multitarget Tracking and Motion, IEEE Trans. on Aerospace and Electronics Systems vol. 31, no. 1, Jan. 1995, pp 486-489