3
$\begingroup$

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!

$\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$
    – Ian
    May 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$
    – josh131
    May 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 Booth
    May 28, 2013 at 15:46
  • $\begingroup$ I rewrote the question so that there is no confusion. $\endgroup$
    – josh131
    May 29, 2013 at 8:09

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.