groundtruthオブジェクト/領域に予測オブジェクト/領域を一意的に割り当てます。

Question

私はgroundtruthオブジェクト（青; 1-4）と予測オブジェクト（赤; a-d）のリストを持っています。予測のパフォーマンスを評価するためのメトリックを計算するには、予測オブジェクトをgroundtruthオブジェクトに割り当てる必要があります。オブジェクトは2度使用しないでください！

グラフィックは、問題の可能な解決策（X、Y、Z）を右側に示します。紫色の領域は、一致するオブジェクトとの重なりを示します。

これを実現するために、私はすべてのオブジェクトの（重複率[交差点/ユニオン]を有する）の交点を含ん交差点マトリックスを作成しました。可視化され例えば、それは（例えば... obj_2のは等々、obj_aと0.3と重なるobj_bと0.1、OBJ_Cと0.3、および意味）以下のようなSTHになります：

intersection_matrix 

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

各オブジェクトが使用されている制約1回だけは最大で1つのエントリを持つ各行と列に変換されます。私はまずこれが簡単だと考えましたが、少し考えてみると、これを最適な方法で解決することは非常に困難です。

わかりやすい実装として、グランドトゥルースオブジェクトを反復処理し、そのオブジェクトに最大の「スコア」を割り当てるアルゴリズムから始めました。

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につながりますが、これは例で示すように実際には悪いことがあります。 predict_objectsを反復する代わりにSolution 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_2の一致可能性があり、obj_aチェックする必要があります。
• これを判断するには、obj_bとobj_cをチェックする必要があります。obj_bとobj_cはobj_3でも可能です。
• は...我々はまた、obj_4一致する可能性があり、obj_dチェックする必要があり、その上で私が最適な解決策を考える

を判断するためには、グラフィックに示されているように、反復的に進行する必要があります。最適性を述べ

可能（と意味の）ルールが

1. はAS LONGこれは、他のオブジェクトの高い試合を妨げないよう...
2. ...スコアが最も高いobjを予測と一致するだろう多分今のところ、これで私の考えを

のような悪い試合を避けるために、しきい値により保護

。私の質問は次のとおりです：

• これは既知の（そしてよく説明され解決された）アルゴリズム問題に対応していますか？
• この問題のアルゴリズム/実装は既にありますか？
• 誰かが 有限で効率的な方法でこれを実装する方法を知っていますか？

Answer 1

1. 知ら（及び十分に記載及び解決）アルゴリズムの問​​題に、この対応していますか？

はい、これはAssignment problemです。

2. この問題のアルゴリズム/実装は既にありますか？

Hungarian methodは、割り当て問題を解決するために設計されたアルゴリズムです。ここで重複することによって表現できる一定のスコア/優先順位を含むことができます。

3. これを有限で効率的な方法で実装する方法はありますか？

さまざまな言語でいくつかの実装があります。この場合に適したMATLABの実装はthis oneです。