CODEWITHSUNDEEP
algorithmhungarian-algorithm
theateist
theateist

Reputation: 14399

algorithm to find closest object

I need to map blue objects to red ones by distance. The center of each object is known. The yellow and green objects, if they are shown, are hints. They help to decide which red object is more important.

For example, in the situation shown in image below:


enter image description here

I have a naive solution, but I'm not quite sure what to do instead of "????" below

Do you have any suggestions?

My naive solution in sort of pseudo-code:

for each BLUE:
   find group P=(YELLOW_BLUE, GREEN_BLUE and RED_BLUE) when each object in P is the closest to BLUE
   vector<RED> redCandidates
   for each O in P:
       if O is YELLOW OR O is GREEN
          find closest RED to O 
          insert RED to redCandidates

   if size of redCandidates is 0 -> return RED_BLUE
   else if size of redCandidates is 1 -> return redCandidates[0] since hint has more weight to the decision
   else if size of redCandidates is > 1 -> ????

UPDATE1
After looking into Minimum Cost Flow problem suggested by @ldog, I decided to use Hungarian Algorithm. I created bipartite graph where each blue node is connected to each red node and the weights on the edges are the distance between blue and red. enter image description here
Now, before I solve the graph, I need to apply rewards on the edges where yellow/green are close to red. I don't quite understand how to do that.
Let's say distance between blue 1 and the red 4 is D_1_4 = 10 and the distance between the yellow hint 11 and the red 4 is D_4_11 = 3. So, because D_1_4 > D_4_11, should I just add reward to the edge 1_4? Or, should I add the reward to each edge that enters node 4, meaning edges 1_4, 2_4 and 3_4?

Upvotes: 1

Views: 440

Answers (1)

ldog
ldog

Reputation: 12151

It seems your question is not fully formed and you are looking for a decent formulation of the things that you expressed in words.

Here are some suggestions:

  1. Use intersection over union for dealing with how to assign similarity for overlapping areas.
  2. There are many ways you could try to make what you expressed in words quantified, and therefore able to be optimized. One reasonable way to quantify what you expressed in words is as a minimization problem I will discuss below.

The minimization should assign one blue box to exactly one red box (given what you told me.) The green and yellow boxes are hints and are not included in this constraint, they are simply used to modify which red box is preferential over others. To formalize what you described in words, we have the set of red boxes R and the set of blue boxes B. There are m red boxes and n blue boxes with m >= n. Each pairing of blue box i with red box j has a preference w_{ij} (this preference is pre-calculated accounting for the hint boxes as well as spatial proximity.)

We wish to compute:

           max \sum_{i<j} w_{ij}x_{ij}
 such that 
           \sum_{k} x_{ik} = 1, \sum_{l} x_{lj} = 1, x_{ik} \in {0,1}

The variable x_{ij} is 1 if and only if blue box i is assigned to red box j, it is 0 otherwise.

This problem (is Totally Unimodular) and can be solved in polynomial time. In fact, it can be solved as an instance of the common Minimum Cost Flow problem. To do this, define a node in a graph for each blue box i, and a node in a graph for each red box j. Connect each blue node to each red node (directed blue->red) with an edge with weight -w_{ij} and capacity 1. Connect each blue node to the source (directed source -> blue) with an edge of capacity 1 and weight 0. Connect each red node to the sink (directed red->sink) with an edge of capacity 1 and weight 0. Give the source a supply of n and the sink a demand of n. Compute the Minimum Cost Flow on this graph (see for example lemon) and the resulting flow yields the maximum solution (alternatively minimum flow.)

Having described this in detail, I see this is already a common approach [1] to solve exactly problems like yours. Here is an implementation.

YMMV depending on how good you make your weights to be. You may want to try a machine learning approach to determine optimal weights using a ground truth dataset and an iterative refinement. The refinement can be computed for a fixed set of blue and red ground truth boxes by refining the weights w_{ij} until all other possible assignments other than the ground truth have a lower score of the optimization than the ground truth. This can be done iterative using any max-margin learning framework or technique, combined with the method I described above (and apparently is described in [1].)

[1] Zhang, Li, Nevatia: Global data association for multi-object tracking using network flows, CVPR (2008).

Upvotes: 1

Related Questions