Hungarian Algorithm

Der ungarische Algorithmus ist ein exaktes Optimierungsverfahren, das die kostengünstigste Eins-zu-eins-Zuordnung findet, bei der jedes Element der kleineren von zwei Mengen zugeordnet wird. Er minimiert die Gesamtkosten aller ausgewählten Paare. In der Computer Vision verbindet er Detektionen mit verfolgten Objekten oder Vorhersagen mit Trainingszielen.

Harold W. Kuhn führte ihn 1955 in The Hungarian Method for the Assignment Problem ein. Ungarisches Verfahren und Kuhn-Munkres-Algorithmus sind alternative Namen für dieselbe Algorithmenfamilie. Der Name ehrt die ungarischen Mathematiker Dénes Kőnig und Jenő Egerváry, deren Arbeit die Grundlage des Verfahrens bildet.

So funktioniert der ungarische Algorithmus#

Die Eingabe ist eine Kostenmatrix: Jede Zeile steht für ein Element aus einer Menge, jede Spalte für ein Element aus der anderen Menge, und jeder Eintrag gibt die Kosten für ihre Zuordnung an. Bei einer quadratischen Matrix wählt die Lösung genau einen Eintrag pro Zeile und Spalte aus. Ein gieriges Verfahren legt sich auf attraktive Einzelpaare fest; das ungarische Zuordnungsverfahren findet das globale Minimum der Gesamtkosten.

Beim klassischen Matrixreduktionsverfahren ziehst du das Minimum jeder Zeile von allen Einträgen dieser Zeile ab und anschließend das Minimum jeder Spalte von allen Einträgen dieser Spalte. Diese Reduktionen erhalten die beste vollständige Zuordnung, da jede Zuordnung jede Zeile und jede Spalte genau einmal verwendet. Überdecke alle Nullen mit möglichst wenigen horizontalen und vertikalen Linien. Wenn für eine n x n-Matrix n Linien erforderlich sind, wähle n Nullen aus, von denen sich keine zwei eine Zeile oder Spalte teilen. Andernfalls ziehst du den kleinsten nicht überdeckten Wert von allen nicht überdeckten Einträgen ab und addierst ihn an den Schnittpunkten der deckenden Linien. Wiederhole anschließend die Überdeckungsprüfung. Berechne die Kosten der Zuordnung anhand der ursprünglichen Matrix.

Effiziente Implementierungen des ungarischen Algorithmus benötigen bei quadratischen Matrizen O(n³) Zeit, verglichen mit den n! möglichen vollständigen Zuordnungen.

Anwendungen in der Computer Vision#

Verfolgung mehrerer Objekte. Das ursprüngliche SORT-Design kombiniert die ungarische Zuordnung mit einem Kalman-Filter, der die Position jeder Spur vorhersagt. Der Intersection over Union-Wert misst die Überlappung zwischen vorhergesagten und detektierten Begrenzungsrahmen. Die Referenzimplementierung von SORT löst die Zuordnungsaufgabe mit LAPJV oder SciPy, verwirft Zuordnungen mit geringer Überlappung und erstellt Identitäten für nicht zugeordnete Detektionen.

Training zur Objekterkennung. DETR verwendet die ungarische Zuordnung, um ungeordnete Vorhersagen mit annotierten Objekten zu paaren. Sein Transformer erzeugt Vorhersageplätze, und die Zuordnung kombiniert Kosten für Klassifizierung und Boxposition. Bei ausreichend vielen Plätzen erhält jedes Ziel eine Vorhersage, sodass die Verlustfunktion unabhängig von der Reihenfolge der Annotationen ist; nicht zugeordnete Plätze lernen die Klasse „kein Objekt“. Ultralytics verwendet diese Zuordnungsformulierung in RT-DETR: Der HungarianMatcher kombiniert Klassifizierungskosten, L1-Koordinatenabstände und Kosten für generalisierte IoU. Das Backend für lineare Zuordnung verwendet einen modifizierten Jonker-Volgenant-Löser, um Trainingspaare auszuwählen.

Ungarische Zuordnung in Python#

Das Python-Paket munkres implementiert das ungarische Verfahren. Installiere es mit pip install munkres und löse dann die Beispielkostenmatrix:

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}")

Die Ausgabe ist Minimum total cost: 12, die kleinstmögliche Summe, wenn pro Zeile und Spalte jeweils ein Eintrag ausgewählt wird.

Verwandte Verfahren und nicht zugeordnete Objekte#

Das Zuordnungsproblem ist die Aufgabe; der ungarische Algorithmus ist ein Lösungsverfahren. Nicht-Maximum-Unterdrückung entfernt konkurrierende Detektionen innerhalb eines Bildes. Die Wiedererkennung von Objekten liefert Informationen zum Erscheinungsbild für die Zuordnung, häufig über Embeddings, die anhand der Kosinusähnlichkeit verglichen werden. Solche Werte können als Zuordnungskosten dienen.

Unterschiedlich große Gruppen ergeben rechteckige Matrizen. Für die Objektverfolgung sind außerdem Zurückweisungsregeln oder Dummy-Einträge mit festgelegten Kosten für nicht zugeordnete Objekte erforderlich, um fehlende Detektionen und neu auftauchende Objekte zu berücksichtigen. Eine falsche Zuordnung führt zu einem Identitätswechsel: Eine Spur-ID wird auf ein anderes Objekt übertragen.

Der Solver für lineare Zuordnung von SciPy löst dasselbe Optimierungsproblem mit einem modifizierten Jonker-Volgenant-Algorithmus. Bei einer rechteckigen r x c-Matrix gibt er genau min(r, c) Paare zurück, sofern eine zulässige vollständige Zuordnung existiert.