image processing - Uniquely assign predicted objects/regions to groundtruth objects/regions -

i have list of groundtruth objects (blue; 1-4) , list of predicted objects (red; a-d). calculate metrics evaluating performance of prediction, need assign predicted objects groundtruth objects. no object should used twice!

the graphic shows on right possible solutions (x, y, z) problem, purple areas indicate overlap between matched objects.

to implement this, created intersection matrix contains intersections (with overlap ratio [intersection/union]) of objects. visualized example sth below (e.g. meaning obj_2 overlaps 0.3 obj_a, 0.1 obj_b, 0.3 obj_c, , forth ...):

    intersection_matrix        |   b   c   d     --|-----------------     1 | 0.1 -   -   -     2 | 0.3 0.1 0.3     3 | -   -   0.8 -     4 | -   -   -   0.5  

the constraint each object used once translates each row , column having @ maximum 1 entry. first thought straightforward, having given bit of thought, find quite hard solve in optimal way.

as straightforward implementation started algorithm iterating on groundtruth-objects , assigning 1 max "score".

for = 1:length(groundtruth_objects)    highest_overlap = max(intersect_matrix(i,:));    % take prediction_object highest overlap match    match = find(intersect_matrix_iou(i,:) == highest_overlap);     % remove matched objects intersect_matrix (to avoid further matches)    intersect_matrix(i,:) = 0;        % remove groundtruth_object    intersect_matrix(:,match) = 0;    % remove prediction_object     % save matched pair entry in match matrix (which solution)    match_matrix(i,match) = highest_overlap; end 

this leads solution x, can bad demonstrated in example. iterating on prediction_objects instead leads solution y, quite here can equally bad.

    solution x              solution y              solution z        |   b   c   d         |   b   c   d         |   b   c   d     --|-----------------    --|-----------------    --|-----------------     1 | 0.1 -   -   -       1 | -   -   -   -       1 | 0.1 -   -   -     2 | -   -   0.3 -       2 | 0.3 -   -   -       2 | -   0.1 -   -     3 | -   -   -   0.1     3 | -   -   0.8 -       3 | -   -   0.8 -     4 | -   -   -   -       4 | -   -   -   0.5     4 | -   -   -   0.5 

problem is, determine whether match suited object, makes sense check whether same candidate wouldn't match better on object (where has higher score or might otherwise not covered @ all). there gets complicated, shown in left of graphic:

• to judge whether match obj_1 -> obj_a, need check obj_a, match obj_2.
• to judge on that, need check obj_b , obj_c, latter obj_3.
• to judge on that, need check obj_d, match obj_4 ...

i think optimal solution, 1 needs progress iteratively, indicated in graphic.

a possible (and meaningful) rule stating optimality be

1. match prediction obj highest score ...
2. ... long doesn't prevent higher matches on other objects
3. maybe protected threshold avoid bad matches

so far thoughts on this. questions are:

• does correspond known (and well-described , solved) algorithmic problem?
• are there algorithms/implementations problem?
• or have idea how implement in finite , efficient way?

1. does correspond known (and well-described , solved) algorithmic problem?

yes, assignment problem.

2. are there algorithms/implementations problem?

the hungarian method algorithm designed solve assignment problems. allows involve score/priority represented overlap here.

3. or have idea how implement in finite , efficient way?

there several implementations in various languages. matlab implementation might suited in case this one.