Hungarian Algorithm

ハンガリー法は、2つの集合のうち小さい方のすべての要素を組み合わせる、最小コストの一対一マッチングを求める厳密な最適化手法です。選択されたすべてのペアの合計コストを最小化します。コンピュータビジョンでは、検出結果と追跡対象の物体、または予測結果と学習ターゲットを対応付けます。

Harold W. Kuhnは1955年に割り当て問題に対するハンガリー法でこの手法を紹介しました。ハンガリー法とKuhn–Munkresアルゴリズムは、同じアルゴリズム群の別名です。この名称は、手法の基礎となる研究を行ったハンガリーの数学者、Dénes KőnigとJenő Egerváryにちなんでいます。

ハンガリー法の仕組み#

入力はコスト行列です。各行は一方の集合の要素を、各列はもう一方の集合の要素を表し、各値は要素をペアにするコストを示します。正方行列の場合、解では各行と各列からそれぞれ1つの値だけを選択します。貪欲法では個々の魅力的なペアを選択しますが、ハンガリーマッチングでは全体の合計コストを最小化します。

従来の行列の縮約手順では、各行の最小値をその行から引き、次に各列の最小値をその列から引きます。どの割り当ても各行と各列を1回ずつ使用するため、これらの縮約によって最適な完全割り当ては変わりません。すべてのゼロを覆う水平線と垂直線の本数を最小にします。n x n行列を覆うのにn本の線が必要な場合、同じ行または列を共有しないn個のゼロを選択します。それ以外の場合は、覆われていない値のうち最小の値を覆われていない要素から引き、覆う線の交点に加えてから、線で覆う手順を繰り返します。割り当てコストは元の行列を使って計算します。

効率的なハンガリー法の実装は、正方行列に対してO(n³)時間で実行されます。これは、完全割り当ての候補がn!通りあることと比べて効率的です。

コンピュータービジョンでの応用#

マルチオブジェクトトラッキング。 SORTのオリジナル設計では、各トラックの位置を予測するカルマンフィルターとハンガリー法による割り当てを組み合わせています。Intersection over unionは、予測されたバウンディングボックスと検出されたバウンディングボックスの重なりを測定します。SORTのリファレンス実装は、LAPJVまたはSciPyを使って割り当てを解き、重なりが小さい対応付けを除外し、対応付けられなかった検出結果にIDを割り当てます。

物体検出の学習。 DETRは、順序のない予測結果とラベル付き物体を対応付けるためにハンガリーマッチングを使用します。そのトランスフォーマーは予測スロットを生成し、マッチングでは分類コストとボックス位置コストを組み合わせます。スロット数が十分であれば、各ターゲットに1つの予測結果が割り当てられ、損失関数はアノテーションの順序に左右されません。対応付けられなかったスロットは「物体なし」クラスを学習します。Ultralyticsはこの割り当て方式をRT-DETRに適用しています。そのHungarianMatcherは、分類コスト、L1座標距離、generalized IoUコストを組み合わせます。線形割り当てバックエンドは、修正版Jonker–Volgenantソルバーを使って学習ペアを選択します。

Pythonでのハンガリーマッチング#

munkres Pythonパッケージはハンガリー法を実装しています。pip install munkresを使ってインストールし、サンプルのコスト行列を解きます。

from munkres import Munkres

costs = [
    [5, 9, 1],
    [10, 3, 2],
    [8, 7, 4],
]
solver = Munkres()
assignments = solver.compute(costs)
# Read costs from the original matrix.
minimum_cost = sum(costs[row][col] for row, col in assignments)
print(f"Minimum total cost: {minimum_cost}")

出力はMinimum total cost: 12です。これは、各行と各列から1つの値を選択した場合に得られる最小の合計値です。

関連手法と対応付けられない物体#

割り当て問題は解くべきタスクであり、ハンガリー法はそのソルバーの1つです。非極大値抑制は、画像内で競合する検出結果を除去します。物体再識別は、対応付けに外観情報を提供します。多くの場合、この情報は埋め込みとして表され、コサイン類似度で比較されます。このようなスコアをマッチングコストにできます。

グループのサイズが異なる場合、長方形行列が生成されます。追跡では、検出漏れや新たに出現した物体に対応するため、拒否ルールまたは未対応時のコストを定義したダミー要素も必要です。誤った対応付けが発生するとIDスイッチが起こり、トラックIDが別の物体に移ります。

SciPyの線形割り当てソルバーは、修正版Jonker–Volgenantアルゴリズムを使って同じ最適化問題を解きます。r x cの長方形行列に対して、実行可能な完全割り当てが存在する場合、ソルバーは正確にmin(r, c)個のペアを返します。