Reconstrução de curvas através do Crust

IMPA - Geometria Computacional 2008

Professor: Luiz Henrique

Aluno: Eric Jardim {ejardim@impa.br}

Código-Fonte Código de Fortune para Voronoi (necessário)




Introdução

Será abordado neste trabalho o problema da reconstrução de uma curva plana a partir de um conjunto de pontos. Este problema encontra facilmente aplicações na área de Visão Computacional.

Método

O método de reconstrução é bastante simples. A partir de um conjunto de pontos, é computado um grafo cujos vértices são os pontos deste conjunto.

Definição (Crust). Dado um conjuto    de pontos no plano e seja    o conjunto dos vértices de Voronoi de   , então o Crust (ou a crosta) de    é o subgrafo da triangulação de Delaunay de   , restrito aos vértices de   .

Será mostrado que tendo os pontos da curva devidamente amostrados, o Crust fornece as arestas que ligam as amostras adjacentes (em relação á curva), gerando uma reconstrução poligonal correta da curva.

Critério para Reconstrução

Serão consideradas curvas planas fechadas, compactas e duas vezes diferenciáveis. Esta definição considera multiplas componentes conexas, mas não permite ramos, auto-interseções e pontos extremos.

Para definir as condições de amostragem, é necessário introduzir o conceito de eixo medial de uma curva, que desempenha para a curva um papel análogo ao diagrama de Voronoi de um conjunto finito de pontos.

Eixo Medial

Definição (Eixo Medial). O eixo medial de uma curva    é o fecho do conjunto de pontos do plano que possuem pelo menos dois pontos de    mais próximos a si.


Figura 1: Exemplo de eixo medial (curva em negrito)


O eixo medial será essencial para determinar uma boa amostragem de uma curva. Vamos estabelecer alguns resultados úteis sobre ele.

Lema 1. Seja    um disco contendo pelo menos dois pontos de uma curva   . Se    não é um segmento de curva então    contém um ponto do eixo medial de   . Em particular, se    contém ao menos duas componentes conexas, então    contém um ponto do eixo medial de   .

Lema 2. Seja    uma curva e    um conjunto (finito) de amostras, então um disco de Voronoi de    contém um ponto do eixo medial de   .

Fator de amostragem

A partir do eixo medial, podemos definir uma função sobre os pontos de uma curva que estabelecerá a densidade de amostras necessárias para a reconstrução.

Definição (LFS). O Local Feature Size (LFS) de um ponto   , ou apenas   , é a distância de    ao eixo medial de   .

Agora podemos definir uma condição de amostragem baseada no LFS dos pontos de uma curva, que está intimamente ligada ao eixo medial. Como vimos no Lema 2, a proximidade de centros de Voronoi também implica na proximidade de pontos do eixo medial.

Definição. Uma curva    é   amostrada por um conjunto    se para cada       tal que   

Com esta definição, o problema se reduz a encontrar um    tal que uma curva   amostrada possua seu Crust igual a sua reconstrução poligonal. Pelos resultados abaixo, é esperado que   .

Corolário 3. Um disco contendo um ponto    com diâmetro não maior que LFS(p) intersecta    num segmento de curva.

Corolário 4. Um disco centrado em um ponto    com raio não maior que LFS(p) intersecta    num segmento de curva.

Definição. Um disco de Voronoi da curva é um disco maximal, sem pontos amostrais em seu interior, centrado num ponto da curva. Este ponto é chamado de vértice de Voronoi da curva.

Corolário 5. Um disco de Voronoi de uma curva   amostrada    com   , intersecta    num segmento de curva.

Apesar de    trazer algumas propriedades, ainda não evita alguns problemas de ambiguidade na reconstrução (ver Figura 2).


Figura 2: Duas curvas distintas com mesma a amostragem


Observação 6. Seja    um conjunto de pontos no plano. Talvez não exista um grafo único em    que seja a reconstrução poligonal de uma curva   amostrada para   .

Ou seja, pode existir mais de uma curva   amostrada por    mas com reconstruções poligonais diferentes. Neste caso, o Crust de    não será a reconstrução poligonal correta para todas as curvas, para   .

Planitude

Mostraremos agora que se uma curva está devidamente amostrada, suas amostras adjacentes possuem uma inclinação mínima razoável, garantindo que entre elas a curva é quase reta.

Lema 7. Um disco tangente a uma curva    em um ponto    com raio até    não contém pontos de    em seu interior.


Figura 3


Observação 8. Com base na Figura 3, se    é uma amostra e    um vértice de Voronoi adjacente a    e    e considerando   , onde    é o centro de um círculo tangente à curva em   , valem as seguintes afirmações:
  1.   
  2.   
  3.   
  4.   


Lema 9. Para uma curva   amostrada com   , o ângulo formado entre duas amostras adjacentes e um vértice de voronoi é pelo menos   

Lema 10. Para uma curva   amostrada com   , o ângulo formado entre três amostras adjacentes é pelo menos   

Erro de reconstrução

Como a reconstrução da curva é poligonal, há evidentemente um erro de reconstrução associado. É possível majorar este erro em função do fator de amostragem   .

Lema 11. Seja    uma curva   amostrada com   . Existe um disco de Voronoi da curva tocando cada par de amostras adjacentes.

Teorema 12. Seja    uma curva   amostrada com    por   . A triangulação de Delaunay de    contém uma aresta entre cada par de arestas adjacentes.

Teorema 13. A distância de um ponto    em uma curva   amostrada    a algum ponto da reconstrução poligonal é no máximo   .

Logo, para manter uma distância máxima    entre um ponto    e sua recontrução, basta que cada amostra esteja numa distância menor que   

Crust

Como visto na definição acima, o crust é um subgrafo da triangulação de Delaunay de um conjunto de amostras    e seus centros de Voronoi   .

Apesar do Teorema 12 garantir que há sempre uma aresta passando por amostras adjacentes em   , não é garantido para qualquer    isso seja verdade para   .

Desta forma, falta provar duas coisas: que dado    suficientemente pequeno, sempre há uma aresta do crust passando por amostras adjacentes e que não há arestas passando por amostras não-adjacentes. Isto será feito em duas etapas.

Teorema 14. O crust de uma curva   amostrada com    contém uma aresta entre cada par de amostras adjacentes.

Teorema 15. crust de uma curva   amostrada com    não contém arestas entre pares de amostras não-adjacentes.

Implementação

Para cálculo dos centros de Voronoi e triangulação de Delaunay, foi utilizado o famoso aplicativo desenvolvido por Steve Fortune [2] disponível na internet.

Além disto, foi criada uma interface gráfica para inclusão, remoção, translação e zoom de pontos amostrais além de utilidades como carregar/salvar pontos e exibição centros de Voronoi, triangulação de Delaunay e o crust.

Conclusão e melhorias

Este trabalho é extremamente interessante, pois a computação do crust é extremamente simples e não depende de nenhum método aproximado, mas apenas de pura geometria.

Obviamente, a computação de uma reconstrução correta depende de uma amostragem que esteja de acordo com o Teorema 15. Nem sempre é possível ter uma amostragem controlada, quando não se conhece a priori a curva a ser reconstruída. Isto é muito natural se imaginarmos que estamos inserindo as amostras interativamente, apenas imaginando a curva, mas sem ter de fato as regras geométricas que a definem.

Quanto a melhorias há duas claras vertentes. A primeira, seria a possibilidade de trabalhar com curvas mais sofisticadas que possuem pontos extremos, quinas, bifurcações ou auto-interseções. A priori, tendo conhecimento destes pontos críticos, não parece difícil adaptar o crust. A segunda linha de melhorias seria uma adaptação do crust para reconstrução poliedral de superfícies através de amostras. Isto é claramente útil para extração de geometrias a partir do scanning de objetos.

Referências

[1] Amenta, N. Bern, M. and Eppstein, D. - "The Crust and the Beta-Skeleton: Combinatorial Curve Reconstruction", Graphical models and image processing: GMIP, vol 60, n. 2, pages 125--135, 1997

[2] The Stony Brook Algorithm Repository
http://www.cs.sunysb.edu/~algorith/implement/fortune/implement.shtml