Triangulation of Points Constrained to a Plane

1. Formulação do Problema

O artigo aborda o problema de triangulação em pipelines de Estrutura a partir do Movimento (SfM), focando especificamente em pontos 3D confinados a um plano comum (pontos coplanares).

• Contexto: Em muitos cenários do mundo real (ambientes internos, fachadas urbanas), características visuais residem em superfícies planares. Métodos de triangulação padrão tratam pontos como elementos genéricos em $\mathbb{P}^3$, ignorando essa restrição geométrica.
• Questão: Tratar pontos coplanares como pontos 3D genéricos introduz graus de liberdade desnecessários, levando a uma maior complexidade algébrica, solucionadores mais lentos e precisão reduzida ao reconstruir a partir de dados de imagem ruidosos.
• Objetivo: Derivar a complexidade algébrica intrínseca da triangulação planar, desenvolver solucionadores eficientes e demonstrar que a aplicação explícita de restrições planares melhora a precisão e a estabilidade da reconstrução em comparação com métodos sem restrições.

2. Metodologia

Os autores empregam geometria algébrica aplicada para modelar o problema, utilizando especificamente variedades multivista e graus de Distância Euclidiana (ED).

A. Formulação Matemática

• Variedade Multivista Ancorada no Plano ($M^\Pi_C$): Os autores definem uma variedade algébrica específica representando todas as correspondências de imagem possíveis de pontos que residem em um plano fixo $\Pi$ observado por $m$ câmeras.
  • Diferentemente da variedade multivista padrão (que tem dimensão 3), a variedade ancorada no plano é isomorfa a $\mathbb{P}^2$ (dimensão 2).
  • As correspondências de imagem são caracterizadas por homografias planares ($H_{ji}$) entre as vistas, derivadas das matrizes da câmera e da equação do plano.
• Grau de Distância Euclidiana (EDdeg): Este invariante mede o número de pontos críticos complexos do problema de otimização: encontrar o ponto na variedade mais próximo dos dados de imagem ruidosos. Ele serve como um proxy para a complexidade algébrica do solucionador.

B. Derivação Teórica

• Teorema Principal: Os autores provam que, para $m \geq 2$ câmeras calibradas genéricas, o grau ED da variedade multivista de pontos ancorados no plano afim é:
  $$\text{EDdeg}(M^\Pi_C) = \frac{9}{2}m^2 - \frac{13}{2}m + 3$$
• Estratégia de Prova: A prova envolve calcular a característica de Euler topológica da variedade e suas interseções com a "hipersuperfície de distância" e o "plano no infinito". Eles utilizam:
  • Teorema de Bertini: Para estabelecer a suavidade de divisores genéricos.
  • Estratificação de Whitney: Para lidar com singularidades (nós) decorrentes da interseção de divisores no infinito.
  • Fibras de Milnor: Para corrigir a característica de Euler para pontos singulares.

C. Desenvolvimento de Solucionadores

Com base no grau ED teórico, os autores constroem solucionadores mínimos para $m=2$ e $m=3$ vistas:

• Redução do Problema: A otimização é reduzida à busca de raízes de um sistema polinomial em duas variáveis ($a, b$) representando as coordenadas no plano.
• Implementação:
  • Continuação Homotópica (HC): Implementada via HomotopyContinuation.jl.
  • Base de Gröbner (GB): Implementada usando um gerador automático para criar templates de eliminação.
• Desempenho: O solucionador GB para 2 vistas leva ~6,9 $\mu$s, enquanto o solucionador HC leva ~172,9 $\mu$s. Para 3 vistas, o GB leva ~82,9 $\mu$s e o HC leva ~1341,6 $\mu$s.

3. Contribuições Principais

1. Fórmula de Complexidade Algébrica: Derivação da fórmula de forma fechada para o grau ED da triangulação planar ($\frac{9}{2}m^2 - \frac{13}{2}m + 3$), quantificando a dificuldade intrínseca do problema.
2. Caracterização Geométrica: Prova de que as variedades multivista ancoradas no plano são isomorfas a $\mathbb{P}^2$ e são suaves, simplificando a estrutura algébrica em comparação com o caso 3D geral.
3. Solucionadores Eficientes: Desenvolvimento de solucionadores mínimos especializados para 2 e 3 vistas que exploram a restrição planar, reduzindo significativamente o número de soluções a encontrar (por exemplo, 8 soluções para $m=2$ versus contagens mais altas em casos sem restrições).
4. Validação Empírica: Experimentos abrangentes em dados sintéticos e do mundo real demonstrando desempenho superior em relação a métodos sem restrições.

4. Resultados Experimentais

A. Dados Sintéticos

• Configuração: Câmeras, planos e pontos gerados aleatoriamente com ruído gaussiano adicionado ($\epsilon = 10^{-12}$).
• Comparação: Triangulação com restrição planar (P.C) vs. Triangulação sem restrições (P.UC).
• Descobertas:
  • Precisão: O método com restrição (P.C) produz erros de triangulação significativamente menores (erro relativo médio logarítmico) em 2, 3 e 4 vistas.
  • Tempo de Execução: O método com restrição é mais rápido devido à dimensionalidade reduzida do espaço de busca.

B. Dados do Mundo Real (Conjunto de Dados Lamar)

• Configuração: Utilização da sequência CAB do conjunto de dados Lamar (cenas internas com carrinho NavVis M6). A verdade fundamental foi obtida via varredura a laser.
• Pipeline:
  1. Detecção de planos usando uma rede de profundidade monoculular e RANSAC (sem usar profundidade GT).
  2. Triangulação de pontos usando três estratégias: Sem restrições (P.UC), Com restrições (P.C) e Híbrida (P.H).
• Descobertas:
  • Precisão: Para $m=3$, o erro de pico para o método com restrição (P.C) foi de ~4 cm, comparado a ~10 cm para o método sem restrições (P.UC).
  • Estabilidade: Os métodos com restrição produziram menos triangulações "falhas" (outliers) em comparação com a abordagem sem restrições.
  • Abordagem Híbrida: Uma estratégia híbrida (usando GB primeiro, recaindo para HC ou sem restrições se o erro de reprojeção for alto) provou ser robusta.

5. Significado e Impacto

• Avanço Teórico: O artigo preenche a lacuna entre a geometria algébrica e a visão computacional, fornecendo uma análise de complexidade rigorosa para uma restrição geométrica específica e altamente relevante (planaridade).
• Utilidade Prática: Os resultados sugerem que pipelines padrão de SfM (como o COLMAP) poderiam melhorar significativamente a qualidade e a velocidade da reconstrução detectando e utilizando explicitamente restrições planares durante a etapa de triangulação, em vez de tratar todos os pontos como entidades 3D genéricas.
• Direções Futuras: Os autores propõem estender esta estrutura para triangulação de linhas e desenvolver solucionadores aproximados (semelhantes às aproximações existentes de triangulação 3 vistas rápidas) para reduzir ainda mais o tempo de execução mantendo a estabilidade.

Em resumo, este trabalho demonstra que aproveitar o "priori planar" não é apenas uma heurística, mas uma necessidade algebricamente fundamentada para reconstrução 3D de alta precisão e eficiente em ambientes estruturados.