Hungarian Algorithm

O algoritmo húngaro é um método de otimização exato que encontra a correspondência um para um de menor custo, associando cada elemento do menor de dois conjuntos. Ele otimiza o custo total de todos os pares selecionados. Em visão computacional, associa deteções a objetos rastreados ou previsões a alvos de treinamento.

Harold W. Kuhn introduziu-o em 1955 em O método húngaro para o problema de atribuição. Método húngaro e algoritmo de Kuhn–Munkres são nomes alternativos para a mesma família de algoritmos. O nome homenageia os matemáticos húngaros Dénes Kőnig e Jenő Egerváry, cujo trabalho serve de base ao método.

Como funciona o algoritmo húngaro#

A entrada é uma matriz de custos: cada linha representa um elemento de um conjunto, cada coluna representa um elemento do outro conjunto e cada entrada mede o custo de associá-los. Para uma matriz quadrada, a solução seleciona exatamente uma entrada por linha e coluna. Uma estratégia gulosa escolhe pares individualmente atraentes; a correspondência húngara encontra o mínimo global do custo total.

No clássico procedimento de redução de matriz, subtrai o mínimo de cada linha dessa linha e, em seguida, o mínimo de cada coluna dessa coluna. Essas reduções preservam a melhor atribuição completa, pois cada atribuição usa cada linha e coluna uma vez. Cobre todos os zeros com o menor número possível de linhas horizontais e verticais. Se forem necessárias n linhas para uma matriz n x n, seleciona n zeros sem linhas ou colunas em comum. Caso contrário, subtrai o menor valor não coberto das entradas não cobertas, adiciona-o nas interseções das linhas de cobertura e repete o teste de cobertura. Calcula o custo da atribuição usando a matriz original.

Implementações eficientes do algoritmo húngaro têm complexidade O(n³) para matrizes quadradas, em comparação com as n! atribuições completas possíveis.

Aplicações em visão computacional#

Rastreamento de múltiplos objetos. O projeto original do SORT combina a atribuição húngara com um filtro de Kalman, que prevê a posição de cada trajetória. A interseção sobre união mede a sobreposição entre as caixas delimitadoras previstas e detetadas. A implementação de referência do SORT resolve a atribuição usando LAPJV ou SciPy, rejeita associações com baixa sobreposição e cria identidades para deteções sem correspondência.

Treinamento de deteção de objetos. O DETR usa correspondência húngara para associar previsões não ordenadas a objetos anotados. O seu Transformer produz posições de previsão, e a correspondência combina custos de classificação e localização das caixas. Com posições suficientes, cada alvo recebe uma previsão, tornando a função de perda independente da ordem das anotações; as posições sem correspondência aprendem a classe «sem objeto». A Ultralytics aplica esta formulação de atribuição no RT-DETR: o seu HungarianMatcher combina custos de classificação, distância de coordenadas L1 e IoU generalizada. O seu backend de atribuição linear usa um solucionador Jonker–Volgenant modificado para selecionar os pares de treinamento.

Correspondência húngara em Python#

O pacote Python munkres implementa o método húngaro. Instala-o com pip install munkres e, em seguida, resolve a matriz de custos de exemplo:

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

A saída é Minimum total cost: 12, a menor soma possível ao selecionar uma entrada por linha e coluna.

Métodos relacionados e objetos sem correspondência#

O problema de atribuição é a tarefa; o algoritmo húngaro é um dos solucionadores. A supressão não máxima remove deteções concorrentes numa imagem. A reidentificação de objetos fornece informações de aparência para a associação, muitas vezes por meio de embeddings comparados usando a similaridade do cosseno. Essas pontuações podem tornar-se custos de correspondência.

Tamanhos diferentes dos grupos produzem matrizes retangulares. O rastreamento também precisa de regras de rejeição ou entradas fictícias com custos definidos para objetos sem correspondência, a fim de lidar com deteções ausentes e objetos que aparecem recentemente. Uma associação incorreta causa uma troca de identidade: o ID de uma trajetória é transferido para outro objeto.

O solucionador de atribuição linear do SciPy resolve o mesmo problema de otimização usando um algoritmo Jonker–Volgenant modificado. Para uma matriz retangular r x c, retorna exatamente min(r, c) pares quando existe uma atribuição completa viável.