将预测对象/区域唯一地分配给groundtruth对象/区域

我有一个groundtruth对象（蓝色; 1-4）和预测对象（红色; a-d）列表的列表。要计算评估预测性能的指标，我需要将预测对象分配给groundtruth对象。不应该使用两次对象！将预测对象/区域唯一地分配给groundtruth对象/区域

图形右侧显示了问题的一些可能解决方案（X，Y，Z），其中紫色区域表示匹配对象之间的重叠。

为了实现这一点，我将创建包含一个交叉点的交集矩阵（具有重叠率[交叉口/联盟]）中的所有对象。对于可视化例如它看起来像某物下面（例如意obj_2重叠0.3与OBJ_A，0.1与obj_b，0.3与obj_c，等等...）：

intersection_matrix 

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

该每个对象使用的约束只有一次转换为每行最多有一个条目。我首先认为这很简单，但让它有一些思考，我觉得这很难以最佳方式解决。

作为一个直截了当的实现，我开始使用一个算法迭代groundtruth对象，并指定最大“分数”的算法。

for i = 1:length(groundtruth_objects) 
    highest_overlap = max(intersect_matrix(i,:)); 
    % take prediction_object with highest overlap as match 
    match = find(intersect_matrix_iou(i,:) == highest_overlap); 

    % remove matched objects from intersect_matrix (to avoid further matches) 
    intersect_matrix(i,:) = 0;  % remove groundtruth_object 
    intersect_matrix(:,match) = 0; % remove prediction_object 

    % save matched pair as entry in match matrix (which is the solution) 
    match_matrix(i,match) = highest_overlap; 
end

这导致了解决方案X，如示例中所示，这可能非常糟糕。迭代预测对象反而会导致解决方案Y，这在这里相当不错，但同样不好。

Solution X    Solution Y    Solution Z 

     | a b c d   | a b c d   | a 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

问题是，以确定是否匹配真正适合的对象，是有意义的检查相同的候选人是否将不匹配较好的另一个对象（其中有一个更高的分数或否则可能根本没有被覆盖）。但它很快变得复杂，如图所示的图形左：

以判断是否匹配obj_1 - > OBJ_A，我们需要检查OBJ_A，这也可以匹配obj_2。
为此判断，我们需要检查obj_b和obj_c，其中后者也可以obj_3。
要判断上，我们需要检查obj_d，这也符合obj_4 ...

我认为最佳的解决方案，需要反复的进度，如在图形表示。

的可能（和有意义）的规则，说明最优会

比赛预测OBJ与最高得分。
......只要这并不妨碍其他物体上更高匹配
由阈值可能保护，以避免像

到目前为止，我对这个想法糟糕的比赛。我现在的问题是：

这是否对应一个已知的（并且很好描述和解决的）算法问题？
是否已有算法/实现此问题？
还是有没有人有一个想法如何实现这个在有限的和有效的方式？

来源

2017-04-06 Honeybear

这是否对应于已知的（和充分描述的和解决）算法的问题？

是的，这是一个Assignment problem。

这个问题已经有算法/实现吗？

Hungarian method是一种设计用于解决分配问题的算法。它允许涉及某个得分/优先级，这可以通过重叠来表示。

还是有没有人有一个想法如何以有限和有效的方式实现这一点？

在各种语言中有几种实现。在这种情况下可能适用的MATLAB实现是this one。

来源

2017-05-11 11:07:00 Honeybear

将预测对象/区域唯一地分配给groundtruth对象/区域

回答

相关问题