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

EP08_02 — 🟢 Homografia e RANSAC: A Votação por Inliers

8.14.2 EP08_02 🟢 Homografia e RANSAC: A Votação por Inliers

O RANSAC, apresentado na seção “Modelagem Matemática: Homografia e RANSAC”, repete um ciclo de três passos — sortear uma amostra mínima, estimar um modelo candidato, e contar quantas correspondências são consistentes com ele (os inliers) — mantendo ao final o modelo mais votado. A etapa de estimação do modelo a partir de 4 pontos (passo 2) envolve álgebra linear que foge ao escopo deste EP; aqui, você recebe diretamente um conjunto de homografias já candidatas — como se cada uma tivesse sido estimada a partir de uma amostra aleatória diferente — e é encarregado de reproduzir exatamente o passo decisivo do algoritmo: aplicar cada modelo a todas as correspondências e contar seus inliers, escolhendo o vencedor.

8.14.2.1 📋 Diretrizes de Implementação

  1. Correspondências: Ler o inteiro \(N\) e, em seguida, \(N\) linhas com quatro reais cada, \(x\ y\ x'\ y'\) — um ponto da imagem A e seu correspondente (possivelmente incorreto) na imagem B, exatamente como produzido pela etapa de matching do EP08_01.
  2. Modelos candidatos: Ler o inteiro \(K\) (número de homografias candidatas) e o real \(\varepsilon\) (limiar de erro de reprojeção). Em seguida, ler \(K\) linhas, cada uma com nove reais \(h_{11}\ h_{12}\ h_{13}\ h_{21}\ h_{22}\ h_{23}\ h_{31}\ h_{32}\ h_{33}\) — os elementos da matriz \(H\) candidata, em ordem de leitura por linha (row-major).
  3. Reprojeção: Para cada correspondência \((x,y,x',y')\) e cada modelo candidato \(H_k\), calcular o ponto projetado \[ \begin{bmatrix} \hat x \\ \hat y \\ \hat w \end{bmatrix} = H_k \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}, \qquad (\hat x / \hat w,\ \hat y / \hat w)\ \text{é o ponto projetado.} \]
  4. Erro de reprojeção: \(e = \sqrt{(\hat x/\hat w - x')^2 + (\hat y /\hat w - y')^2}\).
  5. Contagem de inliers: Uma correspondência é um inlier do modelo \(H_k\) se \(e \le \varepsilon\).
  6. Seleção do melhor modelo: O modelo vencedor é o de maior número de inliers; em caso de empate, escolha o de menor índice \(k\) (o primeiro encontrado durante o ciclo iterativo do RANSAC).
  7. Saída: Para cada modelo \(k\) de \(0\) a \(K-1\), na ordem de leitura, imprimir Modelo k: I inliers. Ao final, imprimir Melhor modelo: k_best com I_best inliers.

8.14.2.2 📌 Restrições Computacionais

  • Comparação inclusiva: um erro de reprojeção exatamente igual a \(\varepsilon\) conta como inlier (\(e \le \varepsilon\)).
  • Sem estimação de \(H\): as matrizes já são fornecidas prontas — não é necessário (nem esperado) resolver nenhum sistema linear.
  • Empate resolvido pelo menor índice, refletindo o comportamento natural de um algoritmo iterativo que percorre os modelos em ordem e só substitui o melhor encontrado até então quando um novo modelo o supera estritamente.

8.14.2.3 🧠 Fundamentação Teórica

Elemento Papel no RANSAC
Amostra mínima (4 pares) Suficiente para determinar os 8 graus de liberdade de uma homografia
Modelo candidato \(H_k\) Estimado a partir de uma amostra mínima; pode ser bom ou ruim, dependendo se a amostra continha outliers
Erro de reprojeção Mede o quão bem o modelo “prevê” cada correspondência observada
Inlier vs. outlier Correspondências consistentes com o modelo vencedor (inliers) vs. as demais, tipicamente correspondências incorretas do matching
Refinamento final Na prática, após escolher o melhor modelo, o RANSAC o recalcula usando apenas seus inliers — passo não exigido neste EP

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

Entrada:

  • Linha 1: Inteiro \(N\).
  • Próximas \(N\) linhas: quatro reais \(x\ y\ x'\ y'\).
  • Próxima linha: Inteiro \(K\) e real \(\varepsilon\).
  • Próximas \(K\) linhas: nove reais (elementos de \(H_k\), row-major).

Saída:

  • \(K\) linhas no formato Modelo k: I inliers.
  • Última linha: Melhor modelo: k_best com I_best inliers.

8.14.2.5 📌 Exemplos

Entrada Saída Observação
5
0 0 0 0
1 1 2 2
2 0 4 0
0 2 0 4
5 5 1 1
2 0.5
2 0 0 0 2 0 0 0 1
1 0 0 0 1 0 0 0 1		 Modelo 0: 4 inliers
Modelo 1: 1 inliers
Melhor modelo: 0 com 4 inliers		 O Modelo 0 (escala ×2) explica corretamente 4 das 5 correspondências; a 5ª, \((5,5)\to(1,1)\), é um outlier que nenhum dos dois modelos explica bem.
🎮 Simulador EP08_02: RANSAC — Contagem de Inliers Modelo: Escala ×2
O modelo candidato mapeia (x,y) → (2x,2y). Ajuste o limiar ε e veja quais correspondências tornam-se inliers ou outliers.
–
Figura 8.16: Simulador EP08_02: RANSAC — Votação por Inliers entre Modelos Candidatos 
%%writefile EP08_02.py
# Código Python
Writing EP08_02.py
TestSuite("EP08_02.py").run()
✔️ EP08_02.cases já existe em casos/
📋 6 caso(s) carregado(s) de casos/EP08_02.cases

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