Hungarian Algorithm

El algoritmo húngaro es un método de optimización exacto que encuentra el emparejamiento uno a uno de menor coste entre todos los elementos del conjunto más pequeño de dos conjuntos. Optimiza el coste total de todos los pares seleccionados. En visión artificial, conecta las detecciones con los objetos seguidos o las predicciones con los objetivos de entrenamiento.

Harold W. Kuhn lo presentó en 1955 en El método húngaro para el problema de asignación. Método húngaro y algoritmo de Kuhn-Munkres son nombres alternativos para la misma familia de algoritmos. Su nombre rinde homenaje a los matemáticos húngaros Dénes Kőnig y Jenő Egerváry, cuyo trabajo constituye la base del método.

Cómo funciona el algoritmo húngaro#

La entrada es una matriz de costes: cada fila representa un elemento de un conjunto, cada columna representa un elemento del otro y cada valor mide el coste de emparejarlos. Para una matriz cuadrada, la solución selecciona exactamente un valor por fila y columna. Una estrategia voraz se decide por pares individuales atractivos; el emparejamiento húngaro encuentra el mínimo global.

En el procedimiento clásico de reducción de matrices, resta el mínimo de cada fila a todos los valores de esa fila y, después, el mínimo de cada columna a todos los valores de esa columna. Estas reducciones conservan la mejor asignación completa porque cada asignación utiliza una vez cada fila y cada columna. Cubre todos los ceros con el menor número de líneas horizontales y verticales. Si se necesitan n líneas para una matriz n x n, selecciona n ceros sin compartir filas ni columnas. De lo contrario, resta el menor valor descubierto a los valores descubiertos, súmalo en las intersecciones de las líneas de cobertura y repite la comprobación de cobertura. Calcula el coste de la asignación con la matriz original.

Las implementaciones eficientes del algoritmo húngaro se ejecutan en tiempo O(n³) para matrices cuadradas, frente a las n! asignaciones completas posibles.

Aplicaciones en visión artificial#

Seguimiento de varios objetos. El diseño original de SORT combina la asignación húngara con un filtro de Kalman, que predice la posición de cada trayectoria. La intersección sobre la unión mide el solapamiento entre las cajas delimitadoras predichas y detectadas. La implementación de referencia de SORT resuelve la asignación con LAPJV o SciPy, descarta las asociaciones con poco solapamiento y asigna identidades a las detecciones sin emparejar.

Entrenamiento de detectores de objetos. DETR utiliza el emparejamiento húngaro para emparejar predicciones desordenadas con objetos etiquetados. Su transformador genera posiciones de predicción, y el emparejamiento combina los costes de clasificación y de localización de las cajas. Con suficientes posiciones, cada objetivo recibe una predicción, lo que hace que la función de pérdida sea independiente del orden de las anotaciones; las posiciones sin emparejar aprenden la clase «sin objeto». Ultralytics aplica esta formulación de asignación en RT-DETR: su HungarianMatcher combina los costes de clasificación, distancia de coordenadas L1 e IoU generalizada. Su implementación del algoritmo de asignación lineal utiliza un algoritmo modificado de Jonker-Volgenant para seleccionar los pares de entrenamiento.

Emparejamiento húngaro en Python#

El paquete munkres de Python implementa el método húngaro. Instálalo con pip install munkres y, después, resuelve su matriz de costes de ejemplo:

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

El resultado es Minimum total cost: 12, la suma más pequeña posible al seleccionar un valor por fila y columna.

Métodos relacionados y objetos sin emparejar#

El problema de asignación es la tarea; el algoritmo húngaro es una de las formas de resolverlo. La supresión no máxima elimina las detecciones que compiten entre sí dentro de una imagen. La reidentificación de objetos aporta información sobre la apariencia para establecer asociaciones, a menudo mediante incrustaciones comparadas con la similitud coseno. Estas puntuaciones pueden convertirse en costes de emparejamiento.

Los tamaños desiguales de los grupos producen matrices rectangulares. El seguimiento también necesita reglas de rechazo o entradas ficticias con costes definidos para los elementos sin emparejar, a fin de adaptarse a las detecciones ausentes y a los objetos que aparecen por primera vez. Una asociación incorrecta provoca un cambio de identidad: el ID de seguimiento pasa a otro objeto.

El solucionador de asignación lineal de SciPy resuelve el mismo problema de optimización mediante un algoritmo modificado de Jonker-Volgenant. Para una matriz rectangular r x c, devuelve exactamente min(r, c) pares cuando existe una asignación completa factible.