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

---

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

---