w2img::HungarianMatch Class Reference

List of all members.

Detailed Description

Finds the optimal assocation in polynomial time.

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.

Author:
Lakshman
Version:
Id
w2img_HungarianMatch.h,v 1.4 2011/01/25 21:08:28 lakshman Exp
See also:
MultipleHypothesesTracker


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


Member Typedef Documentation

typedef std::pair<code::Image<int>, HungarianMatch::Assignment> w2img::HungarianMatch::PSPair


Constructor & Destructor Documentation

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.


Member Function Documentation

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


Generated on Fri May 4 13:40:23 2012 for WDSS-IIw2algs by  doxygen 1.4.7