Algoritmo Húngaro

Visão geral

O algoritmo Húngaro (Hungarian algorithm) é um método clássico em tempo polinomial (polynomial time) para resolver o problema de atribuição (assignment problem): dado um conjunto de trabalhadores e um conjunto de tarefas (ou trilhas e detecções, ou características e protótipos), encontrar um emparelhamento um-para-um de custo mínimo entre eles. Formalmente, ele computa um emparelhamento perfeito de custo mínimo (minimum-cost perfect matching) em um grafo bipartido completo (complete bipartite graph) (ou o melhor emparelhamento possível quando os lados têm tamanhos diferentes, via preenchimento com elementos fictícios).

Em sistemas modernos de inteligência artificial (AI), o algoritmo Húngaro é amplamente usado para associação de dados (data association) — especialmente em rastreamento de múltiplos objetos (multi-object tracking, MOT) e em pipelines de visão computacional fortemente baseados em correspondência — porque ele:

  • Produz uma atribuição globalmente ótima sob a função de custo escolhida
  • Executa em tempo polinomial (tipicamente (O(n^3)))
  • É simples de implantar: construir uma matriz de custos → resolver a atribuição → aplicar limiar/filtrar correspondências

Embora muitas bibliotecas o exponham como “Hungarian”, algumas usam descendentes mais rápidos (por exemplo, Jonker–Volgenant) enquanto fornecem a mesma interface e o mesmo tipo de solução.

O problema de atribuição (emparelhamento bipartido de custo mínimo (minimum-cost bipartite matching))

Configuração do problema

Você tem dois conjuntos:

  • Lado esquerdo: (n) itens (por exemplo, trilhas existentes)
  • Lado direito: (n) itens (por exemplo, novas detecções)

E uma matriz de custos (C \in \mathbb{R}^{n \times n}) onde (C_{ij}) é o custo de emparelhar o item esquerdo (i) com o item direito (j). O objetivo é selecionar exatamente uma correspondência por linha e por coluna minimizando o custo total.

Formulação por programação inteira

Seja (x_{ij} \in {0, 1}) indicando se (i) é atribuído a (j).

[ \min_{x} \sum_{i=1}^{n}\sum_{j=1}^{n} C_{ij} x_{ij} ] sujeito a [ \sum_{j=1}^{n} x_{ij} = 1 \quad \forall i ] [ \sum_{i=1}^{n} x_{ij} = 1 \quad \forall j ] [ x_{ij} \in {0,1} ]

Isso é um caso especial de atribuição linear (linear assignment). Um fato-chave: a relaxação de PL (LP relaxation) (substituindo (x_{ij}\in{0,1}) por (0 \le x_{ij} \le 1)) ainda produz um ótimo integral devido à unimodularidade total (total unimodularity), então não há lacuna de integralidade (integrality gap). O algoritmo Húngaro explora essa estrutura.

Casos retangulares (tamanhos diferentes dos conjuntos)

Na prática, você frequentemente tem (n \ne m) (por exemplo, 12 trilhas, 9 detecções). Tratamento padrão:

  • Tornar a matriz quadrada adicionando linhas/colunas fictícias (dummy rows/columns).
  • Atribuir um custo grande (ou um custo de “sem correspondência”) às atribuições fictícias.

Depois de resolver, correspondências envolvendo nós fictícios são interpretadas como trilhas/detecções não atribuídas.

Ideia central: reduções, zeros e atribuições aumentantes (augmenting assignments)

O algoritmo Húngaro normalmente é explicado por meio de uma sequência de operações na matriz que preservam a atribuição ótima, ao mesmo tempo que a tornam mais fácil de extrair a partir de zeros.

1) Reduções de linha e coluna criam zeros sem mudar o ótimo

Se você subtrai uma constante de cada elemento em uma linha, você reduz o objetivo de qualquer atribuição que use essa linha pela mesma constante (porque toda atribuição viável escolhe exatamente um elemento daquela linha). Portanto, a otimalidade relativa não muda.

Algoritmicamente:

  • Para cada linha (i), subtraia (\min_j C_{ij}) de todas as entradas dessa linha.
  • Para cada coluna (j), subtraia (\min_i C_{ij}) de todas as entradas dessa coluna.

Após essas reduções, toda linha e toda coluna têm pelo menos um zero.

Intuição: você está construindo um conjunto de correspondências candidatas “gratuitas” (zeros) que podem sustentar uma atribuição completa.

2) Escolha zeros independentes (uma atribuição provisória)

Uma atribuição válida corresponde a selecionar (n) zeros com:

  • Exatamente um zero em cada linha
  • Exatamente um zero em cada coluna

Eles são chamados de zeros independentes (independent zeros).

Se você consegue escolher (n) zeros independentes, você tem uma atribuição ótima (na matriz reduzida e, portanto, na original).

3) Se não existirem zeros independentes suficientes, “ajuste” para criar mais zeros

Se você ainda não consegue formar uma atribuição completa a partir de zeros, o algoritmo modifica a matriz preservando a otimalidade. Uma apresentação comum usa o número mínimo de linhas (linhas/colunas) necessárias para cobrir todos os zeros:

  • Cubra todos os zeros com o menor número possível de linhas horizontais/verticais.
  • Se o número de linhas for igual a (n), existe uma atribuição entre os zeros.
  • Caso contrário:
    • Seja (\delta) o menor valor descoberto.
    • Subtraia (\delta) de todo elemento descoberto.
    • Some (\delta) a todo elemento coberto duas vezes (interseção de uma linha coberta e uma coluna coberta).
    • Deixe elementos cobertos uma única vez inalterados.

Isso aumenta o número de zeros enquanto mantém o problema equivalente em um sentido dual preciso.

4) Atribuições aumentantes

Quando novos zeros aparecem, você tenta aumentar o tamanho do conjunto de zeros independentes. Isso é essencialmente um processo de caminho aumentante (augmenting path) em um grafo bipartido cujas arestas são as entradas zero:

  • Linhas e colunas são nós.
  • Um zero em ((i,j)) é uma aresta.
  • Mantenha um emparelhamento atual (um conjunto de zeros independentes).
  • Encontre um caminho aumentante para aumentar o tamanho do emparelhamento em 1.
  • Repita até encontrar um emparelhamento perfeito.

Isso é intimamente relacionado a algoritmos de emparelhamento bipartido; o método Húngaro combina isso com as etapas de atualização dual acima para garantir progresso e otimalidade.

Por que funciona: uma perspectiva dual / de custo reduzido (fundamentação teórica)

Uma visão mais profunda conecta o algoritmo à dualidade em programação linear.

Variáveis duais e custos reduzidos

O dual do PL de atribuição pode ser escrito usando potenciais (u_i) para linhas e (v_j) para colunas:

[ \max_{u,v} \sum_i u_i + \sum_j v_j ] sujeito a [ u_i + v_j \le C_{ij} \quad \forall i,j ]

Defina o custo reduzido (reduced cost): [ C'{ij} = C{ij} - u_i - v_j ] A viabilidade dual implica (C'{ij} \ge 0). Arestas onde (C'{ij} = 0) são restrições justas (tight).

  • Reduções de linha/coluna podem ser interpretadas como inicializar e atualizar (u) e (v) para fazer muitos custos reduzidos virarem zero.
  • O algoritmo busca um emparelhamento perfeito usando apenas arestas justas (com custo reduzido zero).
  • Se não existe emparelhamento perfeito entre as arestas justas, o algoritmo ajusta os potenciais (via atualização por (\delta)) para criar novas arestas justas, mantendo a viabilidade.

Folga complementar

Se você encontra um emparelhamento perfeito que usa apenas arestas de custo reduzido zero, então a folga complementar (complementary slackness) vale, e o emparelhamento é ótimo para o problema primal.

Essa interpretação dual explica por que a etapa “subtrair o mínimo descoberto / somar nas interseções” não é um truque: é uma atualização controlada das variáveis duais que preserva a viabilidade e aumenta a chance de encontrar um ótimo primal entre arestas justas.

Exemplo resolvido passo a passo (matriz pequena)

Considere 3 trabalhadores e 3 tarefas com custos:

[ C= \begin{bmatrix} 4 & 1 & 3 \ 2 & 0 & 5 \ 3 & 2 & 2 \end{bmatrix} ]

Passo 1: Redução por linhas

Mínimos por linha: ([1, 0, 2]). Subtraia:

[ \begin{bmatrix} 3 & 0 & 2 \ 2 & 0 & 5 \ 1 & 0 & 0 \end{bmatrix} ]

Passo 2: Redução por colunas

Mínimos por coluna: min col1 = 1, min col2 = 0, min col3 = 0. Subtraia da coluna 1:

[ C'= \begin{bmatrix} 2 & 0 & 2 \ 1 & 0 & 5 \ 0 & 0 & 0 \end{bmatrix} ]

Passo 3: Encontrar zeros independentes

Os zeros estão em:

  • Linha1: col2
  • Linha2: col2
  • Linha3: col1, col2, col3

Podemos escolher:

  • (Linha1, Col2)
  • (Linha3, Col1)

Mas então a Linha2 tem apenas col2 como zero, que já foi tomada. Não há zeros independentes suficientes para uma atribuição completa.

Passo 4: Cobrir zeros com o número mínimo de linhas

Todos os zeros podem ser cobertos com 2 linhas (por exemplo: cobrir a coluna 2 e a linha 3). Como 2 < 3, precisamos ajustar.

Elementos descobertos são aqueles que não estão na linha 3 coberta e não estão na coluna 2 coberta:

  • (Linha1, Col1) = 2
  • (Linha1, Col3) = 2
  • (Linha2, Col1) = 1
  • (Linha2, Col3) = 5

O menor valor descoberto é (\delta = 1).

  • Subtraia 1 de todas as entradas descobertas.
  • Some 1 às entradas cobertas duas vezes (interseção da linha 3 com a coluna 2: entrada (3,2)).

Resultado: [ \begin{bmatrix} 1 & 0 & 1 \ 0 & 0 & 4 \ 0 & 1 & 0 \end{bmatrix} ]

Agora podemos escolher zeros independentes:

  • (Linha1, Col2)
  • (Linha2, Col1)
  • (Linha3, Col3)

Isso corresponde a uma atribuição ótima na matriz original:

  • Trabalhador1 → Tarefa2 (custo 1)
  • Trabalhador2 → Tarefa1 (custo 2)
  • Trabalhador3 → Tarefa3 (custo 2) Custo total = 5.

Complexidade e desempenho prático

  • O algoritmo Húngaro clássico executa em (O(n^3)) para uma matriz (n \times n).
  • O espaço é tipicamente (O(n^2)) para armazenar a matriz e estruturas auxiliares.

Para muitas cargas de trabalho em IA, (O(n^3)) é aceitável porque (n) costuma ser o número de objetos ativos por frame (de dezenas a poucas centenas). Se você precisa emparelhar milhares de itens com frequência, pode ser necessário:

  • Filtragem por restrição de candidatos (gating) (reduzir (n) e esparsificar candidatos)
  • Métodos aproximados
  • Solvers alternativos (por exemplo, fluxo de custo mínimo (min-cost flow) explorando esparsidade)

Uso prático em IA: associação de dados em rastreamento de múltiplos objetos (MOT)

Onde a atribuição aparece em MOT

Em pipelines de rastreamento por detecção (tracking-by-detection), cada frame produz detecções. O rastreador mantém um conjunto de estados previstos das trilhas. A pergunta central a cada frame é:

Qual detecção pertence a qual trilha?

Isso é exatamente um problema de atribuição:

  • Nós à esquerda: trilhas previstas
  • Nós à direita: detecções
  • Custo (C_{ij}): dissimilaridade entre a trilha (i) e a detecção (j)

O algoritmo Húngaro fornece o emparelhamento globalmente de menor custo total sob a métrica escolhida.

Esse padrão aparece em muitos sistemas, incluindo baselines clássicos de MOT e rastreadores baseados em características profundas. É comumente combinado com um modelo de movimento como um Filtro de Kalman e, às vezes, com embeddings de aparência aprendidos via redes profundas (veja também Aprendizado Métrico).

Funções de custo típicas

Você precisa definir uma matriz de custos. Escolhas comuns:

  • Sobreposição geométrica (caixas delimitadoras):
    • Custo = (1 - \mathrm{IoU}(b_i, b_j)) onde (\mathrm{IoU}) é a interseção sobre união (IoU, intersection over union)
  • Consistência de movimento usando uma predição de filtro de Kalman:
    • Custo = distância de Mahalanobis (Mahalanobis distance) entre o centro/tamanho previstos e observados da caixa
  • Distância de aparência:
    • Custo = distância cosseno (cosine distance) entre embeddings de reidentificação (ReID, re-identification)
  • Custo combinado:
    • (C = \lambda C_{\text{motion}} + (1-\lambda) C_{\text{appearance}})

Na prática, você frequentemente faz restrição de candidatos: se um par candidato é impossível (muito distante, interseção sobre união baixa), defina o custo como um número muito grande (ou marque como inválido) para que não seja escolhido.

Tratando “sem correspondência”: falhas e novos objetos

MOT real inclui:

  • Detecções não correspondidas → criar novas trilhas
  • Trilhas não correspondidas → marcar como ausentes; remover após (k) ausências

Padrões comuns:

  1. Construir uma matriz de custos entre trilhas atuais e detecções.
  2. Opcionalmente restringir pares inválidos.
  3. Resolver a atribuição.
  4. Aceitar apenas correspondências com custo abaixo de um limiar.
  5. Trilhas/detecções restantes ficam sem correspondência e são tratadas separadamente.

Mini exemplo: emparelhando trilhas com detecções

Suponha que você tenha 3 trilhas e 4 detecções, com custo = (1-\mathrm{IoU}) (menor é melhor). Você pode preencher para ficar quadrado:

  • Trilhas (T_1..T_3)
  • Detecções (D_1..D_4)
  • Adicionar uma trilha fictícia (T_4) (ou detecção fictícia) com custos de “sem correspondência”.

O algoritmo Húngaro então produz:

  • Até 3 correspondências reais
  • A(s) detecção(ões) restante(s) correspondida(s) ao fictício → tratada(s) como novos objetos

Esse “preenchimento com nós fictícios” é a ponte padrão entre emparelhamento perfeito e o emparelhamento parcial necessário no rastreamento.

Uso prático em pipelines de visão além de MOT

Atribuição ao estilo Húngaro aparece em qualquer lugar em que você precisa de pareamento um-para-um consistente:

  • Correspondência de pontos-chave ao impor correspondências um-para-um após computar uma matriz de similaridade
  • Avaliação de segmentação/detecção de instâncias (por exemplo, emparelhar instâncias previstas com ground truth usando custos de IoU)
  • Descoberta de objetos / pós-processamento de agrupamento onde protótipos devem ser atribuídos a slots
  • Ajuste baseado em modelo onde múltiplas hipóteses competem por observações limitadas

Ele também é usado conceitualmente em modelos de previsão de conjuntos (por exemplo, treinamento no estilo DETR) para emparelhar consultas de objeto previstas com objetos do ground truth; a perda de treinamento usa uma etapa de emparelhamento bipartido ótimo (frequentemente Húngaro) para definir a supervisão.

Observações de implementação e exemplo de código

Usando SciPy (recomendado em Python)

SciPy expõe uma interface padrão de atribuição; internamente pode usar uma variante otimizada, mas fornece o mesmo tipo de resultado.

import numpy as np
from scipy.optimize import linear_sum_assignment

C = np.array([
    [4, 1, 3],
    [2, 0, 5],
    [3, 2, 2]
], dtype=float)

row_ind, col_ind = linear_sum_assignment(C)  # minimizes total cost
assignment = list(zip(row_ind, col_ind))
total_cost = C[row_ind, col_ind].sum()

print("assignment:", assignment)
print("total_cost:", total_cost)

Matrizes retangulares e preenchimento com fictícios

Se o seu rastreador tem (n) trilhas e (m) detecções:

  • Se o seu solver suporta retangular diretamente (muitos suportam), use isso.
  • Caso contrário, preencha para (k \times k) onde (k = \max(n,m)).

Ao preencher:

  • Custos de fictício-para-real devem refletir sua penalidade de “sem correspondência”.
  • Tenha cuidado: definir custos fictícios baixos demais pode fazer o solver preferir resultados sem correspondência; altos demais podem forçar correspondências ruins. Muitos sistemas, em vez disso, resolvem normalmente e então rejeitam correspondências acima de um limiar.

Restrição de candidatos e estabilidade numérica

  • Use restrição de candidatos para definir pares impossíveis com um custo grande (por exemplo, (10^6)).
  • Evite usar inf se a biblioteca não conseguir lidar com isso.
  • Normalize custos para que termos diferentes (interseção sobre união, Mahalanobis, aparência) sejam comparáveis.

Relação com outras ideias algorítmicas

  • O algoritmo Húngaro é um método polinomial especializado para um problema de otimização estruturado, em contraste com problemas NP-difíceis em que você pode recorrer a Algoritmos de Aproximação.
  • Ele usa ideias que lembram otimização primal–dual (primal–dual) e caminhos aumentantes, conectando-se a tópicos mais amplos em otimização combinatória e algoritmos em grafos.
  • Em rastreamento, ele é tipicamente um componente em um loop maior com filtragem (por exemplo, Filtro de Kalman) e, às vezes, modelos de similaridade aprendidos.

Armadilhas comuns e boas práticas

  • Projeto ruim do custo: o algoritmo é tão bom quanto sua matriz de custos. Se o custo não codifica a noção correta de “mesmo objeto”, a atribuição ótima ainda estará errada.
  • Tratamento de sem-correspondência: decida se vai lidar com “sem atribuição” via preenchimento ou via limiarização (ou ambos).
  • Incompatibilidade de escala em custos combinados: se você misturar movimento e aparência, calibre-os; caso contrário, um termo domina.
  • Cenas congestionadas: o algoritmo Húngaro garante um ótimo global, mas com custos ambíguos muitas atribuições podem ficar quase empatadas. Adicionar pistas de aparência ou um gating de movimento mais forte geralmente ajuda.

Resumo

O algoritmo Húngaro resolve o problema de atribuição de custo mínimo (emparelhamento bipartido de custo mínimo) em tempo polinomial, classicamente (O(n^3)). Seu poder prático vem de um conjunto limpo de operações — reduções de linha/coluna, criação e exploração iterativa de zeros (arestas justas) e crescimento de um emparelhamento via atribuições aumentantes — com uma base sólida em dualidade de PL e folga complementar.

Em IA e visão computacional, ele é um componente essencial para associação de dados: dada uma matriz de custos entre trilhas e detecções (ou previsões e alvos), o algoritmo Húngaro fornece um emparelhamento um-para-um rápido e globalmente ótimo que se integra de forma natural a pipelines em tempo real.