I have a matrix of M measurements and N objects. Each cell contains a cost of assignment a particular measurement to the object. I want to assign them optimally. As the condition, only one measurement can go to one object, and one measurement can go to only one object. I want to set some cost threshold, in effect there may be some measurement or object, which is not assigned at all. How can I do it? I was recently thinking of the auction algorithm, which however will never leave any unassigned measurement or object. If that is false, correct me please. Or help with some alternative solution. Thanks for your time!
$\begingroup$
$\endgroup$
4
-
$\begingroup$ If I'm reading this correctly, are you trying to correlate objects in memory with physical objects that you've detected with a sensor? $\endgroup$– IanMay 28, 2013 at 14:28
-
$\begingroup$ yes .. there is matrix with costs for each pair and I want to assign optimally with possibility that some measurement or object is left unconnected. So far I see auction algorithm assigns optimally but with no possibility of leaving some unassigned. $\endgroup$– josh131May 28, 2013 at 14:39
-
$\begingroup$ It is better to add clarifications to your question than add another comment in response to a query. That way, if your edit clears up any confusion, the query can be tidied up (deleted) later, so that the comments don't distract viewers from the question itself. $\endgroup$– Mark BoothMay 28, 2013 at 15:46
-
$\begingroup$ I rewrote the question so that there is no confusion. $\endgroup$– josh131May 29, 2013 at 8:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The Hungarian Algorithm should be suitable for this case. You have already generated the cost matrix that describes the cost of each measurement to each object. The algorithm determines the assignments that yield the minimum total cost. It can handle cases with more measurements that objects (false positives) and more objects than measurements (when an object isn't detected). (These cases have non-square cost matrices.)
This will assign all measurements if the number of objects if M measurements <= N objects. However, you can then go back and look at the individual costs of the assignments and apply a threshold to weed out matches with low scores.
There are many libraries in various programming languages for this algorithm. One I've used and is well documented is the munkres python library.
