Reconstrução de Curvas com
Algoritmos de Crust , B-Skeleton e
Gathan
• Antonio Luiz Vitalo Calomeni
• Rodrigo de Souza Lima Espinha
• Manuel Eduardo Loaiza Fernández
Motivação

Problema




Reconhecimento de fronteiras de objetos.
Dados: amostras de pontos.
Exemplo: visão computacional.
Necessidade de definir uma curva
baseada na amostragem dada.
Objetivo
A partir de uma
amostragem de pontos
obtermos a melhor
reconstrução possível
da(s) curva(s)
definida(s) por esses
pontos.

Algoritmos Desenvolvidos



Crust , B-Skeleton e Gathan.
Critério de Reconstrução se baseia na densidade da
amostragem de pontos.
Utilizam a Triangulação de Delaunay e Diagrama de
Voronoi como ferramentas básicas para definição
das arestas candidatas a serem parte da curva
reconstruída.
Algoritmo Crust


Seja S um conjunto finito
de pontos no plano, e V os
vértices do diagrama de
Voronoi de S ( vor(S) ).
Seja S’ a união S U V, e
considere a triangulação de
Delaunay de S’ ( del(S’) ).
Algoritmo Crust

Uma aresta da triangulação
de Delaunay de S’ pertence
ao Crust de S se ambos os
vértices pertencem a S, ou
alternativamente, se há um
disco vazio em seu interior
de pontos de S’ que toca
os vértices da aresta.
Algoritmo Crust


CRUST( S )
1. V <- conjunto de vértices do diagrama de
Voronoi de S.
2. S' <- S U V
3. Obter a triangulação de Delaunay de S'.
4. Selecionar todas as arestas de del( S' ) que
ligam pontos do conjunto S original.
A complexidade será de O(n*logn).
Algoritmo B - Skeleton

Seja S um conjunto finito de
pontos no plano, com pontos
s1 e s2 pertencentes a S, a
uma distância d(s1, s2) entre
si. A região proibida de s1,s2
é a união dos dois discos de
raio beta*d(s1, s2) / 2
tocando s1 e s2.
Beta : 1, 3/2, 2
Algoritmo B - Skeleton

BETA_SKELETON( S, beta )
1. Obter a triangulação de Delaunay de
S.
2. Selecionar todas as arestas e, pertencentes a del( S ),
para as quais os centros dos circuncírculos dos
triângulos adjacentes a e estão em lados opostos em
relação a e, e seu raio é maior que :
(beta/2)*(comprimento(e)).
Região proibida pela
área dos círculos

A complexidade será de O(n*logn).
Algoritmo B - Skeleton

Aqui fazemos uma
comparação dos possíveis
resultados para uma amostra
de pontos com os algoritmos
Crust e B – Skeleton.
Crust
Skeleton
Condições de amostragem


Garantir qualidade da
reconstrução.
“Local Feature Size”

Relativo ao eixo medial

LFS(p) = d(p, m)
Condições de amostragem

Eixo medial
Condições de amostragem

Curva r-amostrada
d ( p, s)  r.d ( p, m)
Condições de amostragem

r<1


Triangulação de Delaunay contém os pares
de arestas adjacentes da curva.
r >= 1
 Pode não haver reconstrução única para a
curva.
Critérios para a amostragem

Crust

r < 0.4


r < 0.252


Contém as arestas que conectam os vértices
adjacentes da curva reconstruída.
Não contém arestas entre vértices não adjacentes
da curva reconstruída.
Condição de amostragem: r < 0.252
Critérios para a amostragem

Beta-Skeleton

Beta = 1.7


Maximiza o espaçamento permitido entre as
amostras.
r < 0.297
Comentários adicionais

Crust e Beta-Skeleton não tratam curvas com
“sharp corners” corretamente.



LFS(p) obriga amostragem infinita nesses locais.
Variação de beta introduz alguma flexibilidade.
Em geral, obtivemos melhores resultados
utilizando Crust…
Algoritmo Gathan


Trata sharp corners
Regulável por dois parâmetros
Trabalhos anteriores

Algoritmo proposto por Gielsen,
baseado no problema do Caixeiro
Viajante

Dado que a densidade da
amostragem é maior que um valor
de referência, a curva é
reconstruída, mesmo com sharp
corners
Algoritmo de Gielsen


Algoritmo não funciona para vários
componentes (solução exige conexão)
Não é clara a generalização para três
dimensões
Algoritmo Gathan

Condição de amostragem deve ser
modificada: seguindo a regra de Crust,
é necessária uma amostragem infinita
perto dos cantos.
Eixo medial (não encosta no canto)
Algoritmo Gathan

Condição de Crust não é suficiente:
Crust
“Ideal”
Condições Iniciais




Curva planar e simples, podendo
ter vários componentes.
Tangentes à esquerda e à direita
de qualquer ponto são definidas e
iguais, exceto nos cantos.
Curva pode ser fechada ou aberta.
Vizinhança dos cantos devem ser
bem amostradas (alta densidade).
Normais das Amostras

O algoritmo necessita da
estimativa das normais das
amostras.
normal
estimada
Estimando as Normais


Técnica de “poles”.
Dada uma amostra, seu “pole” é o
vértice de Voronoi mais distante,
pertencente à sua célula de Voronoi.
pole
amostra
Estimando as Normais

Se a célula é limitada:


A estimativa da normal é dada pela linha
que corta a amostra e seu “pole”.
Se a célula é ilimitada:

A estimativa é dada pela média dos raios
ilimitados da célula.
Tratando Cantos

Caso 1:
p3 se comporta como
corner point, normal ok
Tratando Cantos

Caso 2:
p1 e p2 são corner points.
Estimativa da normal errada
em ambos os pontos. Pode
levar a arestas incorretas.
Um pós-processamento corrige.
Condição de Amostragem


A condição de Crust funciona bem
para curvas suaves.
Logo, pode-se utilizá-la ao longo
da curva e definir uma outra na
“vizinhança” de um canto, pois
neste caso a condição de Crust
não funciona.
Condição de Amostragem


O que seria a “vizinhança” de um
canto?
Conceito de protective ball
protective ball de g
g
eixo medial
Condição de Amostragem





Se um ponto p da curva está dentro de
uma protective ball, deve-se possuir uma
amostra de distância no máximo:
k.r.ө
k  constante empírica (1/6)
r  raio da protective ball
ө  ângulo entre as tangentes de g
Fora da protective ball: mesma condição
de Crust.
Funcionamento

Técnica de Vizinhos mais próximos:



Estratégia para reconstrução de curvas
onde conecta-se as amostras com seus
vizinhos mais próximos, em cada lado
da normal estimada.
Algumas restrições: ângulo e rateio
Remoção de arestas inválidas
Condição de ângulo


A aresta pq só é candidata se sua
normal faz um ângulo agudo menor
que α com a normal da amostra.
α  parâmetro fornecido pelo usuário (entre 35 e
40 graus na maioria dos casos)
Condição de rateio

h/l > ρ

h  comprimento do dual (voronoi)
l  comprimento da aresta

ρ  parâmetro fornecido pelo usuário (1.7)

Remoção de arestas


Ainda assim, podem ter arestas
inválidas.
Deixar, para cada amostra, somente
as duas menores arestas incidentes.
O Algoritmo
Gathan(P, α, ρ)
Computar o diagrama de Voronoi Vp;
para cada p de P faça
Computar pole e estimar normal Np
Assuma E conjunto das arestas de Delaunay
incidentes a p que satisfazem as condições:
A. normal de cada aresta de E faz ângulo agudo
menor que α com Np
B. h/l > ρ
Manter apenas as menores arestas pq e ps de E em
cada lado de Np
fim para
Deletar aresta que não está entre as duas menores
que incidem em uma amostra