Hungarian Algorithm

L’algorithme hongrois est une méthode d’optimisation exacte qui trouve l’appariement un-à-un de coût minimal associant chaque élément de l’ensemble le plus petit des deux à un élément de l’autre. Il optimise le coût total de toutes les paires sélectionnées. En vision par ordinateur, il associe les détections aux objets suivis, ou les prédictions aux cibles d’entraînement.

Harold W. Kuhn l’a présenté en 1955 dans The Hungarian Method for the Assignment Problem. La méthode hongroise et l’algorithme de Kuhn–Munkres sont deux noms désignant la même famille d’algorithmes. Son nom rend hommage aux mathématiciens hongrois Dénes Kőnig et Jenő Egerváry, dont les travaux constituent le fondement de cette méthode.

Fonctionnement de l’algorithme hongrois#

L’entrée est une matrice de coûts : chaque ligne représente un élément d’un ensemble, chaque colonne représente un élément de l’autre ensemble, et chaque entrée mesure le coût de leur association. Pour une matrice carrée, la solution sélectionne exactement une entrée par ligne et par colonne. Une stratégie gloutonne choisit les paires individuellement attrayantes ; l’algorithme hongrois trouve le coût total minimal à l’échelle globale.

Dans la procédure classique de réduction de matrice, soustrais le minimum de chaque ligne à tous les éléments de cette ligne, puis le minimum de chaque colonne à tous les éléments de cette colonne. Ces réductions préservent la meilleure affectation complète, car chaque affectation utilise une fois chaque ligne et chaque colonne. Couvre tous les zéros avec le moins de lignes horizontales et verticales possible. Si une matrice n x n nécessite n lignes, sélectionne n zéros sans partager de ligne ni de colonne. Sinon, soustrais la plus petite valeur non couverte aux entrées non couvertes, ajoute-la aux intersections des lignes de couverture, puis répète le test de couverture. Calcule le coût de l’affectation à partir de la matrice d’origine.

Les implémentations efficaces de l’algorithme hongrois s’exécutent en temps O(n³) pour les matrices carrées, contre n! affectations complètes possibles.

Applications en vision par ordinateur#

Suivi multi-objets. La conception originale de SORT combine l’affectation hongroise avec un filtre de Kalman, qui prédit la position de chaque trajectoire. L’intersection sur l’union mesure le chevauchement entre les boîtes englobantes prédites et détectées. L’implémentation de référence de SORT résout le problème d’affectation avec LAPJV ou SciPy, rejette les associations présentant un faible chevauchement et crée des identités pour les détections non appariées.

Entraînement à la détection d’objets. DETR utilise l’appariement hongrois pour associer des prédictions non ordonnées à des objets annotés. Son Transformer produit des emplacements de prédiction, et l’appariement combine les coûts de classification et de localisation des boîtes. Avec suffisamment d’emplacements, chaque cible reçoit une prédiction, ce qui rend la fonction de perte indépendante de l’ordre des annotations ; les emplacements non appariés apprennent la classe « aucun objet ». Ultralytics applique cette formulation d’affectation dans RT-DETR : son HungarianMatcher combine les coûts de classification, de distance de coordonnées L1 et d’IoU généralisée. Son backend d’affectation linéaire utilise un solveur Jonker–Volgenant modifié pour sélectionner les paires d’entraînement.

Appariement hongrois en Python#

Le package Python munkres implémente la méthode hongroise. Installe-le avec pip install munkres, puis résous sa matrice de coûts d’exemple :

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

Le résultat est Minimum total cost: 12, la somme minimale possible en sélectionnant une entrée par ligne et par colonne.

Méthodes connexes et objets non appariés#

Le problème d’affectation est la tâche ; l’algorithme hongrois est l’un des solveurs possibles. La suppression non maximale élimine les détections concurrentes dans une image. La réidentification d’objets fournit des informations d’apparence pour l’association, souvent au moyen d’embeddings comparés à l’aide de la similarité cosinus. Ces scores peuvent servir de coûts d’appariement.

Des groupes de tailles inégales produisent des matrices rectangulaires. Le suivi nécessite également des règles de rejet ou des entrées fictives avec des coûts de non-appariement définis pour gérer les détections manquantes et les objets qui apparaissent. Une association erronée entraîne un changement d’identité : l’ID de suivi est attribué à un autre objet.

Le solveur d’affectation linéaire de SciPy résout le même problème d’optimisation à l’aide d’un algorithme Jonker–Volgenant modifié. Pour une matrice rectangulaire r x c, il renvoie exactement min(r, c) paires lorsqu’une affectation complète réalisable existe.