将预测对象/区域唯一地分配给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与最高得分。
- ......只要这并不妨碍其他物体上更高匹配
- 由阈值可能保护,以避免像
到目前为止,我对这个想法糟糕的比赛。我现在的问题是:
- 这是否对应一个已知的(并且很好描述和解决的)算法问题?
- 是否已有算法/实现 此问题?
- 还是有没有人有一个想法如何实现这个在 有限的和有效的方式?
- 这是否对应于已知的(和充分描述的和解决)算法的问题?
是的,这是一个Assignment problem。
- 这个问题已经有算法/实现吗?
Hungarian method是一种设计用于解决分配问题的算法。它允许涉及某个得分/优先级,这可以通过重叠来表示。
- 还是有没有人有一个想法如何以有限和有效的方式实现这一点?
在各种语言中有几种实现。在这种情况下可能适用的MATLAB实现是this one。