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:
-
-
-
-
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