Hungarian Algorithm

L'algoritmo ungherese è un metodo di ottimizzazione esatto che trova l'abbinamento uno-a-uno a costo minimo, associando ogni elemento dell'insieme più piccolo a un elemento dell'altro insieme. Ottimizza il costo totale di tutte le coppie selezionate. Nella visione artificiale, associa i rilevamenti agli oggetti tracciati oppure le previsioni ai target di addestramento.

Harold W. Kuhn lo presentò nel 1955 in Il metodo ungherese per il problema dell'assegnamento. Il metodo ungherese e l'algoritmo di Kuhn–Munkres sono nomi alternativi per la stessa famiglia di algoritmi. Il nome rende omaggio ai matematici ungheresi Dénes Kőnig e Jenő Egerváry, il cui lavoro è alla base del metodo.

Come funziona l'algoritmo ungherese#

L'input è una matrice dei costi: ogni riga rappresenta un elemento di un insieme, ogni colonna rappresenta un elemento dell'altro insieme e ciascuna voce misura il costo dell'abbinamento. Per una matrice quadrata, la soluzione seleziona esattamente una voce per riga e per colonna. Una strategia greedy si impegna su singole coppie allettanti; l'abbinamento ungherese trova il minimo globale del costo totale.

Nella classica procedura di riduzione della matrice, sottrai a ogni riga il suo valore minimo, poi a ogni colonna il suo valore minimo. Queste riduzioni preservano il miglior assegnamento completo, perché ogni assegnamento utilizza una volta ogni riga e ogni colonna. Copri tutti gli zeri con il minor numero possibile di linee orizzontali e verticali. Se per una matrice n x n servono n linee, seleziona n zeri senza righe o colonne in comune. Altrimenti, sottrai il valore scoperto più piccolo dalle voci non coperte, aggiungilo nelle intersezioni delle linee di copertura e ripeti la verifica della copertura. Calcola il costo dell'assegnamento usando la matrice originale.

Le implementazioni efficienti dell'algoritmo ungherese hanno una complessità temporale O(n³) per le matrici quadrate, rispetto alle n! possibili assegnazioni complete.

Applicazioni nella computer vision#

Tracciamento di più oggetti. Il progetto originale SORT combina l'assegnamento ungherese con un filtro di Kalman, che prevede la posizione di ogni traccia. L'intersezione sull'unione misura la sovrapposizione tra le scatole di delimitazione previste e quelle rilevate. L'implementazione di riferimento di SORT risolve l'assegnamento usando LAPJV o SciPy, rifiuta le associazioni con scarsa sovrapposizione e assegna identità ai rilevamenti non abbinati.

Addestramento del rilevamento degli oggetti. DETR usa l'abbinamento ungherese per associare previsioni non ordinate agli oggetti etichettati. Il suo transformer genera slot di previsione e l'abbinamento combina i costi di classificazione e di localizzazione delle scatole. Se gli slot sono sufficienti, ogni target riceve una previsione, rendendo la funzione di perdita indipendente dall'ordine delle annotazioni; gli slot non abbinati apprendono la classe «nessun oggetto». Ultralytics applica questa formulazione dell'assegnamento in RT-DETR: il suo HungarianMatcher combina i costi di classificazione, distanza L1 delle coordinate e IoU generalizzata. Il suo backend di assegnamento lineare usa un risolutore Jonker–Volgenant modificato per selezionare le coppie di addestramento.

Abbinamento ungherese in Python#

Il pacchetto Python munkres implementa il metodo ungherese. Installalo con pip install munkres, quindi risolvi la sua matrice dei costi di esempio:

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

L'output è Minimum total cost: 12, la somma minima ottenibile selezionando una voce per riga e per colonna.

Metodi correlati e oggetti non abbinati#

Il problema dell'assegnamento è il compito; l'algoritmo ungherese è uno dei risolutori. La soppressione non massima rimuove i rilevamenti in competizione all'interno di un'immagine. La re-identificazione degli oggetti fornisce informazioni sull'aspetto per l'associazione, spesso tramite embedding confrontati usando la similarità coseno. Questi punteggi possono diventare costi di abbinamento.

Dimensioni diverse dei gruppi producono matrici rettangolari. Il tracciamento richiede anche regole di rifiuto o voci fittizie con costi definiti per gli elementi non abbinati, così da gestire rilevamenti mancanti e oggetti appena apparsi. Un'associazione errata causa uno scambio di identità: l'ID di una traccia viene trasferito a un altro oggetto.

Il risolutore di assegnamento lineare di SciPy risolve lo stesso problema di ottimizzazione usando un algoritmo Jonker–Volgenant modificato. Per una matrice rettangolare r x c, restituisce esattamente min(r, c) coppie quando esiste un assegnamento completo ammissibile.