PDI+VC · Exercício de Programação

EP08_01 — 🟢 Distância de Hamming e Correspondência de Descritores Binários

8.14.1 EP08_01 🟢 Distância de Hamming e Correspondência de Descritores Binários

O ORB, usado no Projeto Prático 1 deste capítulo, descreve a vizinhança de cada ponto de interesse como uma sequência de bits — e, por isso, a comparação entre dois descritores não usa a distância euclidiana do k-NN do Capítulo 7, e sim a distância de Hamming: o número de posições em que os bits diferem. Antes de chamar cv2.BFMatcher(cv2.NORM_HAMMING), você foi encarregado de implementar manualmente essa correspondência (matching) por força bruta — a mesma etapa que, executada internamente pelo OpenCV, precede a estimação robusta da homografia por RANSAC.

8.14.1.1 📋 Diretrizes de Implementação

  1. Quantidades: Ler os inteiros \(N\) e \(M\) — número de descritores extraídos da imagem A e da imagem B, respectivamente.
  2. Descritores de A: Ler \(N\) linhas, cada uma contendo um descritor binário (uma string de caracteres 0 e 1, todos do mesmo comprimento).
  3. Descritores de B: Ler \(M\) linhas, no mesmo formato.
  4. Limiar: Ler o inteiro \(\tau\) — distância de Hamming máxima aceitável para considerar uma correspondência válida.
  5. Distância de Hamming: Para dois descritores binários \(a\) e \(b\) de mesmo comprimento, \[ d_H(a, b) = \sum_{k} \mathbb{1}[a_k \neq b_k], \] ou seja, a contagem de posições em que os bits diferem.
  6. Correspondência por vizinho mais próximo: Para cada descritor \(a_i\) de A (\(i\) na ordem de leitura, começando em \(0\)), calcule sua distância de Hamming a todos os descritores de B e encontre o de menor distância. Em caso de empate entre dois ou mais descritores de B com a mesma distância mínima, escolha o de menor índice.
  7. Filtragem pelo limiar: Se a menor distância encontrada for \(\le \tau\), a correspondência é válida; caso contrário, \(a_i\) não possui correspondência.
  8. Saída: Para cada \(i\) de \(0\) a \(N-1\), na ordem de leitura, imprimir uma linha: i j d se houver correspondência válida (onde \(j\) é o índice do descritor de B escolhido e \(d\) sua distância), ou i -1 caso contrário. Ao final, imprimir Total correspondências válidas: X.

8.14.1.2 📌 Restrições Computacionais

  • Mesmo comprimento: todos os descritores (de A e de B) têm exatamente o mesmo número de bits.
  • Força bruta: compare cada descritor de A a todos os de B — não é necessário nenhum tipo de indexação ou estrutura de aceleração.
  • Desempate por menor índice em B, e nunca por ordem de leitura de A (que já é natural, pois cada \(a_i\) é tratado de forma independente).

8.14.1.3 🧠 Fundamentação Teórica

Elemento Papel na correspondência ORB
Descritor binário (BRIEF) Cada bit é o resultado de uma comparação de intensidade entre dois pixels da vizinhança
Distância de Hamming Métrica de dissimetria entre strings binárias; muito mais rápida de calcular que a distância euclidiana (operação XOR + contagem de bits)
Vizinho mais próximo Critério de correspondência: cada ponto de A é pareado ao ponto de B com descritor mais similar
Limiar \(\tau\) Filtra correspondências pouco confiáveis antes mesmo do RANSAC — mas, como discutido no capítulo, algumas correspondências incorretas ainda passam, exigindo a robustez do RANSAC

8.14.1.4 📦 Especificação de Entrada e Saída (VPL)

Entrada:

  • Linha 1: Inteiros \(N\) e \(M\).
  • Próximas \(N\) linhas: um descritor binário por linha (string de 0s e 1s).
  • Próximas \(M\) linhas: um descritor binário por linha, no mesmo formato.
  • Última linha: Inteiro \(\tau\).

Saída:

  • \(N\) linhas, uma por descritor de A, no formato i j d ou i -1.
  • Última linha: Total correspondências válidas: X.

8.14.1.5 📌 Exemplos

Entrada Saída Observação
3 3
10101010
11110000
00001111
10101011
00001110
11111111
2		 0 0 1
1 -1
2 1 1
Total correspondências válidas: 2		 O descritor 11110000 não encontra correspondência: seu vizinho mais próximo está a distância 4, acima do limiar \(\tau=2\).
🎮 Simulador EP08_01: Distância de Hamming entre Descritores Binários Descritores de 8 Bits
Clique em qualquer bit do Descritor B para invertê-lo e observe a distância de Hamming mudar em tempo real.
Descritor A (Fixo)
Descritor B (Clique para Inverter)
–
Figura 8.15: Simulador EP08_01: Distância de Hamming entre Dois Descritores Binários 
%%writefile EP08_01.py
# Código Python
Writing EP08_01.py
TestSuite("EP08_01.py").run()
✔️ EP08_01.cases já existe em casos/
📋 6 caso(s) carregado(s) de casos/EP08_01.cases

🔍 Testando Python: EP08_01.py
⚠️ EP08_01.py: Arquivo sem conteúdo (menos de 3 linhas). Testes ignorados.