Dissertação
dissertacao_thales_06_02_2007.pdf
Documento PDF (3.7MB)
Documento PDF (3.7MB)
Universidade Federal de Alagoas
Programa de Pós-Graduação em Matemática
DISSERTAÇÃO DE MESTRADO
Rio São Francisco
Registro Automático de Superfícies Usando
Spin-Image
MATEMÁTICA
A ciência
do infinito
Thales Miranda de Almeida Vieira
Maceió
6 de Fevereiro de 2007
Agradecimentos
A minha família.
Ao meu orientador, Adelailson Peixoto, pela dedicação, oportunidade e apoio
fundamentais para a realização deste trabalho.
Aos professores Luiz Velho e Thomas Lewiner, pela disponibilidade e atenção concedidas
e suas grandes colaborações neste trabalho.
Ao professor Vinicius Mello, por suas importantes sugestões e críticas a este trabalho.
Ao Departamento de Matemática da Universidade Federal de Alagoas, pelo apoio
concedido desde a Iniciação Científica.
À FAPEAL, pelo apoio financeiro.
i
Resumo
Este trabalho descreve um método baseado em três etapas para reconstrução de modelos
a partir de malhas capturadas de scanners 3D. Malhas obtidas a partir de diferentes
pontos de visão de um scanner têm sua representação em sistemas de coordenadas local.
Portanto, para a reconstrução final do modelo, é necessário realizar um alinhamento
dessas malhas, ou registro. O algoritmo mais famoso para realizar registro de nuvens de
pontos é o algoritmo ICP. Porém, um dos requisitos desse algoritmo é uma estimativa
inicial do alinhamento das malhas, que muitas vezes é feita manualmente. Para
automatizar esse processo, este trabalho utiliza descritores spin-image para identificar
regiões de sobreposição entre as malhas e estimar seus alinhamentos. Após este registro
inicial, o alinhamento é refinado através do algoritmo ICP, e finalmente o modelo é
reconstruído usando uma técnica chamada VRIP.
Palavras-chave:
range-images.
registro de superfícies, spin-images, reconstrução 3d, malhas,
ii
Abstract
This work describes a method based on three stages for reconstructing a model from a
given set of scanned meshes obtained from 3D scanners. Meshes scanned from different
scanner’s view points have their representation in local coordinate systems. Therefore,
for final model reconstruction, an alignment of the meshes is required. The most popular
algorithm for cloud data registration is the ICP algorithm. However, ICP requires an
initial estimate of mesh alignment, which is, many times, done manually. To automate
this process, this work uses a surface representation called spin-images to identify overlap
areas between the meshes and to estimate their alignment. After this initial registration,
the alignment is refined by the ICP algorithm, and finally the model is reconstructed
using a method called VRIP.
Keywords: surface registration, spin-images, 3d reconstruction, meshes, range-images.
iii
Sumário
1 Introdução
1.1 Registro de Superfícies . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Estrutura do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1
3
3
4
4
2 Descrição Geral do Método
2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Alinhamento Inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Refinamento do Registro . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Reconstrução da Malha Final . . . . . . . . . . . . . . . . . . . . . . . . .
5
5
5
7
8
3 Alinhamento Automático Inicial
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Descritores Spin-Images . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Spin-maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Spin-images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3 Parâmetros das Spin-images . . . . . . . . . . . . . . . . . . . . . .
3.2.4 Textured Spin-Images . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.5 Comparação de Spin-Images . . . . . . . . . . . . . . . . . . . . . .
3.3 Seleção de Pontos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Seleção Aleatória de Pontos . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Seleção por Curvatura Local . . . . . . . . . . . . . . . . . . . . . .
3.4 Geração de Correspondências . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Filtragens de Correspondências . . . . . . . . . . . . . . . . . . . . . . . .
3.5.1 Filtragem Usando Medidas de Similaridade . . . . . . . . . . . . . .
3.5.2 Filtragem Usando Consistência Geométrica . . . . . . . . . . . . . .
3.5.3 Agrupamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Cálculo da Transformação: Algoritmo de Horn . . . . . . . . . . . . . . . .
3.7 Validação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
10
10
11
12
13
14
15
16
17
17
21
22
22
23
23
24
26
4 Refinamento do Registro usando ICP
4.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Visão Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Seleção de Pontos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Geração de Correspondências . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 Kd-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
28
28
29
30
30
iv
SUMÁRIO
4.5
4.6
4.7
v
Atribuição de Pesos às Correspondências . . . . . . . . . . . . . . . . . . . 31
Rejeição de Correspondências . . . . . . . . . . . . . . . . . . . . . . . . . 32
Métricas de Erro e Minimização . . . . . . . . . . . . . . . . . . . . . . . . 33
5 Reconstrução da Malha Final
5.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Integração Volumétrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Marching Cubes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
35
35
38
6 Resultados e Discussão
6.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1 Criação de Spin-images . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.2 Filtragem de Correspondências . . . . . . . . . . . . . . . . . . . .
6.2.3 Algoritmo ICP . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.4 Cálculo de Curvatura e Resolução das Malhas . . . . . . . . . . . .
6.3 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
40
40
40
43
44
44
45
7 Conclusão e Trabalhos Futuros
50
Lista de Figuras
Registro de superfícies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Malhas geradas a partir de range images capturadas de diferentes pontos
de visão de um objeto. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2.1
2.2
2.3
2.4
Procedimento para registro automático de superfícies . . . . . . . . . . . .
Primeira etapa: alinhamento inicial de um par de malhas. . . . . . . . . .
Segunda etapa: refinamento do alinhamento entre duas malhas usando ICP.
Terceira etapa: Construção da malha final usando VRIP. . . . . . . . . . .
6
7
8
9
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
Base criada pelo ponto orientado (p, n) e coordenadas (α, β) de um ponto x. 11
Spin-map com sua respectiva Spin-image. . . . . . . . . . . . . . . . . . . . 12
Efeito de diferentes bin sizes em spin-images. . . . . . . . . . . . . . . . . 14
Spin-map e spin-image convencional e com textura. . . . . . . . . . . . . 15
Malha com pontos de alta medida de curvatura κ21 + κ22 destacados. . . . . 18
Região de Voronoi de uma vizinhança estrelada. . . . . . . . . . . . . . . . 19
Exemplo de histograma utilizado para detecção de outliers . . . . . . . . . 22
Agrupamento e validação. . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.1
4.2
Processo de criação de uma kd-tree bidimensional. . . . . . . . . . . . . . . 31
Rejeição de pares contendo pontos de fronteira. . . . . . . . . . . . . . . . 33
5.1
5.2
Cálculo da função de distância com sinal di (v). . . . . . . . . . . . . . . . . 36
Efeito da função de distância D(v) em duas curvas alinhadas com pequeno
erro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.1
1.2
2
6.1
6.2
Pontos correspondentes e suas spin-images. . . . . . . . . . . . . . . . . . . 41
Maior espaçamento possível entre duas visões de um objeto contendo as
regiões de alta curvatura. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.3 Registro inconsistente devido à simetria. . . . . . . . . . . . . . . . . . . . 44
6.4 Malhas em diferentes resoluções com pontos de maior curvatura destacados. 45
6.5 Registro de malhas com diferentes resoluções. . . . . . . . . . . . . . . . . 46
6.6 Malhas alinhadas do coelho. . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.7 Modelo reconstruído do coelho. . . . . . . . . . . . . . . . . . . . . . . . . 47
6.8 Malhas alinhadas da cabeça. . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.9 Modelo reconstruído da cabeça. . . . . . . . . . . . . . . . . . . . . . . . . 48
6.10 Malhas alinhadas do cavalo. . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.11 Modelo reconstruído do cavalo. . . . . . . . . . . . . . . . . . . . . . . . . 49
7.1
Modelo de um vaso simétrico. . . . . . . . . . . . . . . . . . . . . . . . . . 51
vi
Capítulo 1
Introdução
1.1
Registro de Superfícies
O problema de registro de superfícies consiste em obter as transformações espaciais que
realizem o melhor alinhamento entre um conjunto de malhas que representam visões de
um mesmo objeto (Figura 1.1).
(a) Superfícies antes do registro
(b) Superfícies registradas.
Figura 1.1: Registro de superfícies.
Atualmente, a modelagem de objetos tridimensionais a partir de objetos reais pode
ser feita utilizando-se scanners 3D. Esses equipamentos são capazes de capturar pontos
tridimensionais a partir de um determinado ponto de visão, utilizando o conceito de range
images, como em (Levoy et al. 2000) e (Neugebauer 1997).
As range images pertencem a uma classe especial de imagens digitais, onde cada pixel
da imagem expressa a distância entre o ponto de visão e um ponto da cena. A partir
dessas imagens, é possível gerar malhas através de triangulações dos pixels.
Porém, é impossível realizar uma varredura completa de um objeto qualquer a partir
de uma única visão, devido a limitações topológicas e geométricas, como obstruções, por
exemplo. Isso justifica a necessidade de captura de várias range images para a reconstrução
1
1.1. REGISTRO DE SUPERFÍCIES
2
de um objeto (Figura 1.2). Essas range images vão gerar malhas mi cujos pontos são
descritos em sistemas de coordenadas locais Si . Portanto, essas malhas precisam ser
registradas, ou alinhadas, de acordo com um sistema de coordenadas global.
Figura 1.2: Malhas geradas a partir de range images capturadas de diferentes pontos de
visão de um objeto.
Do ponto de vista matemático, dadas duas malhas mA e mB , onde o sistema de
coordenadas de mA é fixado como sistema de coordenadas global, o registro de superfícies
consiste em encontrar o melhor movimento rígido T , composto por uma rotação e uma
translação, que, aplicado a mB , otimize sua posição no sistema de coordenadas global, ou
o sistema de coordenadas de mA .
Atualmente, uma das abordagens mais utilizadas para realizar o registro entre duas
malhas parcialmente sobrepostas envolve a análise de similaridades geométricas e de cor
(textura) das regiões de sobreposição.
Um dos algoritmos mais utilizados no processo de registro de superfícies é o ICP
(Iterative Closest Point), desenvolvido por Besl & Mckay (1992). Através de um
processo iterativo, o algoritmo original ICP cria pares Pi = {xAi , xBi } de pontos
correspondentes nas 2 malhas, usando como critério a proximidade dos pontos, e encontra
uma transformação que minimiza o erro de alinhamento entre as 2 malhas. Essa
1.2. OBJETIVOS
3
transformação pode ser calculada minimizando-se a função de erro dada por
N
1 X
kxAi − (RxBi + t)k2 ,
f (R, t) =
N i=1
(1.1)
onde N é a quantidade de pares, e R e t representam a matriz de rotação e o vetor de
translação. A transformação encontrada é aplicada as pontos da malha mB e o processo
é repetido até que as transformações encontradas sejam desprezíveis. Este algoritmo será
explorado mais detalhadamente no capítulo 4.
Porém, devido a problemas de mínimo local, uma das exigências do ICP é que
as malhas tenham uma estimativa inicial do alinhamento, e que apenas a região
de sobreposição seja levada em conta. Isso descarta a possibilidade de alinhamento
automático usando apenas o ICP.
1.2
Objetivos
Dado um conjunto de malhas que representem um determinado objeto, este trabalho
apresenta uma estratégia para alinhar automaticamente todos os pares de malhas que
possuam regiões de sobreposição, e finalmente gerar um modelo final. Inicialmente, é
utilizada uma estratégia baseada em descritores de superfície Spin-Images (Johnson 1997)
e Textured Spin-Images (Brusco et al. 2005) para geração de correspondências entre pontos
das malhas, e consequentemente uma estimativa inicial do alinhamento entre malhas com
regiões de sobreposição considerável. Em seguida, o algoritmo ICP é executado para
refinar o alinhamento. Finalmente, o modelo final é reconstruído usando um método
volumétrico desenvolvido por Curless & Levoy (1996) chamado VRIP.
1.3
Contribuições
Este trabalho apresenta uma solução para realizar todo o processo de registro de superfícies
e reconstrução de modelos tridimensionais que integra três módulos independentes. A
principal contribuição deste trabalho é que a integração dos módulos permite o registro e
reconstrução das malhas de forma completamente automática.
O primeiro módulo é responsável pelo alinhamento automático inicial e foi
implementado neste trabalho utilizando descritores spin-images. Neste trabalho, são
apresentadas algumas idéias para melhorar este procedimento, como, por exemplo, utilizar
funções das curvaturas principais para selecionar pontos
A segunda etapa realiza o refinamento do alinhamento e também foi implementada
neste trabalho, utilizando uma variante do algoritmo ICP.
1.4. APLICAÇÕES
4
Na última etapa, os resultados foram obtidos utilizando-se um pacote chamado
MeshMerge, desenvolvido por Rocchini et al. (2004).
Finalmente, este trabalho apresenta uma análise de todo o procedimento realizada a
partir de alguns experimentos.
1.4
Aplicações
O processo de registro de superfícies é um problema de alto interesse para diversas áreas da
ciência, como a robótica, as engenharias, a medicina, a geologia, a modelagem geométrica
e a visão computacional.
Os objetos alinhados podem ser utilizados, por exemplo, para localização de modelos,
reconhecimento de objetos 3D, rastreamento em tempo real e, finalmente, reconstrução de
objetos tridimensionais a partir de malhas obtidas de scanners tridimensionais ou outros
equipamentos.
1.5
Estrutura do Trabalho
Este trabalho está estruturado da seguinte forma:
Capítulo 2. Apresenta uma visão geral da estratégia adotada neste trabalho.
Capítulo 3. Contém definições envolvendo os descritores spin-images e seus
parâmetros, descreve o procedimento para geração das correspondências entre pontos,
incluindo suas filtragens, além do cálculo do alinhamento inicial estimado e validações.
Capítulo 4. Descreve cada etapa do algoritmo ICP original e algumas de suas
variantes mais relevantes, dando ênfase à implementação realizada.
Capítulo 5. Descreve o método para reconstrução de modelos a partir de malhas
pré-alinhadas, que é implementado no VRIP.
Capítulo 6. Exibe resultados obtidos neste trabalho e discute alguns pontos
relevantes do problema.
Capítulo 7. Apresenta as conclusões sobre o trabalho desenvolvido e idéias para
trabalhos futuros.
Capítulo 2
Descrição Geral do Método
2.1
Introdução
Este capítulo apresenta uma visão geral do procedimento adotado para registro
automático de superfícies e reconstrução de objetos tridimensionais. Esse método tem
como dados de entrada um conjunto de malhas que representam diferentes visões de
um objeto. Essas malhas podem ser obtidas, por exemplo, a partir de range images
capturadas por scanners 3D. Opcionalmente, além da informação de geometria, pode
haver informação de textura associada às malhas. Podemos dividir o procedimento em
três etapas:
1. Na primeira etapa, as malhas são testadas duas a duas para verificar a existência
de áreas de sobreposição e estimar um alinhamento inicial.
2. A segunda etapa recebe as malhas pré-alinhadas e executa o algoritmo ICP para
refinar os alinhamentos, minimizando a métrica de erro dada pela Equação 3.23.
3. A terceira etapa aplica um método para reconstrução de uma única malha que
represente o objeto, a partir das malhas alinhadas pelo ICP. A malha reconstruída
é o resultado final do procedimento.
A Figura 2.1 ilustra o processo de registro automático de superfícies adotado neste
trabalho.
2.2
Alinhamento Inicial
Dado um conjunto de malhas M = {mi }, onde cada malha é representada em um sistema
de coordenadas local, é necessário determinar os pares de malhas que possuem regiões
de sobreposição, ou mais especificamente, determinar pares de pontos localizados em
diferentes malhas que representem um mesmo ponto no objeto real. Esse procedimento é
5
2.2. ALINHAMENTO INICIAL
6
Figura 2.1: Procedimento para registro automático de superfícies
realizado comparando-se as malhas duas a duas, de modo que no final desta etapa, seja
possível identificar os pares de malhas com regiões de sobreposição e estimativas de suas
transformações de alinhamento.
Neste trabalho, essas correspondências são realizadas utilizando-se descritores spinimages, que são imagens bidimensionais criadas por pontos orientados da superfície que
fornecem uma descrição local da geometria da superfície e são invariantes por movimentos
rígidos. Com esse propósito, foi utilizada também uma extensão das spin-images,
desenvolvida recentemente, chamada textured spin-images (Brusco et al. 2005). Esses
descritores consideram, além da geometria, informações de textura dos objetos. O capítulo
6 apresenta uma breve análise comparativa entre os 2 métodos.
A representação de pontos por imagens bidimensionais abre espaço para a utilização de
técnicas de comparação de imagens. Pontos correspondentes devem ter imagens parecidas.
A análise bruta de similaridade entre imagens é um algoritmo quadrático, pois envolve
a comparação de cada imagem de uma malha com todas as imagens de uma segunda
malha. Portanto, é conveniente a escolha de pontos específicos das malhas para geração
de spin-images. Neste trabalho, a curvatura local da superfície foi o parâmetro utilizado
para seleção dos pontos geradores de spin-images.
2.3. REFINAMENTO DO REGISTRO
7
Em seguida, os pares de pontos com spin-images similares passam por filtragens, e
finalmente são agrupados para o cálculo de uma transformação que melhor aproxime esses
pares de pontos. Esse cálculo é feito pelo Algoritmo de Horn (1987).
A transformação encontrada é aplicada à malha, e finalmente é realizada uma validação
final para avaliar a qualidade da transformação. Caso a transformação não seja aceita,
novos grupos são criados e testados até que se encontre uma transformação consistente
ou não seja possível realizar novos agrupamentos. Neste último caso, o alinhamento
entre as duas malhas não é realizado, por exemplo, devido a não existência de regiões de
sobreposição entre as malhas
A Figura 2.2 exibe um diagrama ilustrando o procedimento acima para cada par de
malhas. Esta etapa será descrita em detalhes no capítulo 3.
Figura 2.2: Primeira etapa: alinhamento inicial de um par de malhas.
2.3
Refinamento do Registro
Uma vez que as malhas estão pré-alinhadas, é possível detectar as regiões de sobreposição
usando distância entre ponto e superfície. Pontos da primeira malha que estejam próximos
à segunda malha pertencem à região de sobreposição. Com esses requisitos validados, é
possível aplicar o algoritmo ICP para refinar os registros entre as malhas.
Neste trabalho, o algoritmo ICP original foi implementado com a utilização de uma
kd-tree (Bentley 1975), para acelerar o processo de seleção de pontos mais próximos.
2.4. RECONSTRUÇÃO DA MALHA FINAL
8
Além disso, foi utilizado um critério de rejeição de pares de acordo com um threshold de
distância, para eliminar pares fora da região de sobreposição, e a métrica de erro dada
pela Equação 3.23.
A Figura 2.3 exibe um diagrama ilustrando os passos do algoritmo ICP, que é o tema
principal do capítulo 4.
Figura 2.3: Segunda etapa: refinamento do alinhamento entre duas malhas usando ICP.
2.4
Reconstrução da Malha Final
A etapa final do procedimento é a reconstrução de uma única malha a partir das malhas
alinhadas pelo ICP. Dados os pares de malhas alinhados e suas respectivas transformações,
é possível, através de composição de transformações, representar todas as malhas num
sistema de coordenadas global, desde que o grafo de alinhamento seja conexo.
Uma técnica chamada VRIP é capaz de realizar a reconstrução da malha final. Dado
um conjunto de malhas representadas num sistema de coordenadas global, esta técnica
define um volume e uma função de distância em cada vértice do volume. Finalmente,
a malha resultante é extraída aplicando-se o algoritmo Marching Cubes (Lorensen &
Cline 1987) com uma tabela para resolver ambiguidades definida por Montani et al. (1994).
Esse processo é exibido na Figura 2.4.
2.4. RECONSTRUÇÃO DA MALHA FINAL
Figura 2.4: Terceira etapa: Construção da malha final usando VRIP.
O capítulo 5 descreve os passos da técnica implementada no VRIP.
9
Capítulo 3
Alinhamento Automático Inicial
3.1
Introdução
Este capítulo define os descritores spin-images e seus parâmetros, descreve os passos
para detecção de regiões de sobreposição entre duas malhas, e consequentemente suas
respectivas transformações espaciais para o alinhamento inicial das superfícies.
3.2
Descritores Spin-Images
Os descritores spin-images (Johnson 1997) são imagens bidimensionais que descrevem
propriedades globais da geometria de um objeto a partir de bases locais criadas em pontos
orientados da superfície. Dentre suas principais características, destaca-se a invariância
por movimentos rígidos, ou seja, as spin-images de uma superfície não variam se nela
forem aplicadas transformações de rotação e translação.
Essa característica implica que, dadas duas malhas extraídas de range images criadas
a partir de diferentes visões de um mesmo objeto, suas spin-images serão iguais em pontos
correspondentes, ou seja, pontos que representem um mesmo ponto do objeto real.
Portanto, considerando o problema de registro de superfícies, as spin-images se
apresentam como boas candidatas para realizar a descrição de pontos das superfícies.
Desse modo, a geração de correspondências entre pontos tridimensionais pertencentes a
malhas extraídas de diferentes visões de um objeto pode ser feita através da comparação de
imagens bidimensionais, pois pontos correspondentes devem ter spin-images semelhantes.
Outros problemas comuns no processo de registro de superfícies, como a presença de
oclusões, buracos e ruídos podem ser parcialmente resolvidos com o uso das spin-images,
e serão discutidos neste capítulo.
As subseções seguintes descrevem os passos para geração das spin-images e discutem
seus principais parâmetros. Além disso, os descritores textured spin-images serão definidos
como uma extensão das spin-images.
10
3.2. DESCRITORES SPIN-IMAGES
3.2.1
11
Spin-maps
Um ponto orientado numa superfície é um ponto associado a uma direção. Para a criação
de spin-images, associa-se aos pontos da superfície o seu vetor normal. Este vetor pode
ser calculado, por exemplo, como o vetor normal a um plano de mínimos quadrados que
melhor se encaixa nos vértices vizinhos ao ponto.
Cada ponto orientado p com vetor normal n define uma sistema de coordenadas local,
usando o plano P , tangente à superfície em p, e a reta L, que passa por p e é paralela a n.
A base desse sistema de coordenadas, (α, β), é definida pela distância perpendicular à reta
L, e pela distância perpendicular com sinal até o plano P , respectivamente (Figura 3.1).
Isso define um sistema de coordenadas cilíndricas, onde não é possível obter a coordenada
de ângulo polar.
Figura 3.1: Base criada pelo ponto orientado (p, n) e coordenadas (α, β) de um ponto x.
Transformando pontos da superfície em pontos no sistema de coordenadas definido
acima, teremos uma aplicação denominada spin-map. Essa aplicação projeta pontos da
superfície em pontos bidimensionais, dado um ponto orientado O = (p, n). Portanto, um
spin-map é uma aplicação SO : R3 → R2 , que mapeia
µq
SO (x) → (α, β) =
¶
kx − pk
2
− (n · (x − p))2 , n · (x − p)
.
(3.1)
A imagem da aplicação spin-map será utilizada para a criação da spin-image. Desde
já, é interessante ressaltar que, como o sistema de coordenadas utilizado depende de
uma base atrelada a um ponto orientado da superfície, esta aplicação é invariante por
movimentos rígidos da superfície.
3.2. DESCRITORES SPIN-IMAGES
3.2.2
12
Spin-images
A imagem de uma aplicação spin-map é um conjunto de pontos bidimensionais, projetados
a partir de pontos da superfície, que descreve a geometria do objeto.
Porém, conjuntos desse tipo não são modelos ideais para realização de comparações,
devido a variações de amostragem, visão e ruído, por exemplo, o que não garante a exata
posição entre vértices em duas malhas obtidas de diferentes visões. Por outro lado, a
geometria global da superfície será a mesma.
Para extrair as propriedades globais desses conjuntos desconsiderando os efeitos de
variações locais em posições de vértices, é realizada uma discretização da imagem da
aplicação spin-map.
Nessa discretização, o espaço bidimensional é dividido em pequenas caixas, ou bins.
Observando este espaço como uma imagem, onde cada pixel é determinado por um bin,
determina-se o tom de cinza de cada pixel de acordo com a quantidade de pontos contidos
em seu bin. A esta imagem, daremos o nome de spin-image. A Figura 3.2 exibe o conjunto
imagem de uma aplicação spin-map e sua respectiva spin-image.
(a) Spin-map
(b) Spin-image
Figura 3.2: Spin-map com sua respectiva Spin-image.
Para suavizar o processo de acúmulo de pontos nos bins, deixando a imagem menos
sensível à posição exata dos pontos, é interessante utilizar uma interpolação bilinear para
distribuir valores pelos bins vizinhos, com peso determinado pela posição relativa do ponto
no bin.
3.2. DESCRITORES SPIN-IMAGES
3.2.3
13
Parâmetros das Spin-images
Alguns parâmetros são fundamentais para o sucesso na geração de correspondências entre
pontos utilizando spin-images. Destacam-se o tamanho dos bins, ou bin size, a largura da
imagem, ou image width, e o ângulo suporte.
Tamanho dos bins
O tamanho dos bins, ou das caixas, é fundamental para a criação de uma spin-image com
uma boa descrição da superfície. Bins grandes podem tornar a descrição da superfície não
muito clara. Bins pequenos podem não ser suficientes para anular os efeitos das posições
individuais dos pontos.
A maneira mais natural de medir o tamanho dos bins é como um múltiplo da resolução
da malha, que é definida como a mediana dos comprimentos de todas as arestas da malha.
A Figura 3.3 exibe três spin-images obtidas de um mesmo ponto orientado com
diferentes tamanhos de bins. Na Figura 3.3(a), é possível ver claramente que o tamanho
pequeno dos bins não resolve o problema da posição individual dos pontos. Na Figura
3.3(b), bins grandes prejudicam a descrição da superfície. Finalmente, a Figura 3.3(c) é
um exemplo de descrição adequada da superfície por spin-images.
Largura da imagem
A largura da imagem, ou image width, determina a quantidade de bins, ou pixels da
imagem, na horizontal e na vertical. Uma vez fixado o tamanho dos bins, quanto maior a
largura da imagem, maior a região da superfície que será descrita pela spin-image.
Denomina-se distância suporte o produto do tamanho dos bins pela largura da imagem.
Essa distância indica o quão distante os pontos da superfície podem estar do ponto
orientado para fazerem parte da spin-image. Portanto, este é outro parâmetro relevante
para alcançar uma descrição adequada da superfície.
Larguras muito altas, ou distâncias suporte muito altas, podem gerar spin-images
diferentes quando geradas de pontos correspondentes de diferentes visões, pois cada
visão possui suas próprias regiões de oclusão. Por outro lado, larguras muito baixas, ou
distâncias suporte muito baixas, descrevem regiões pequenas da superfície, que podem,
inclusive, ser semelhantes a regiões diferentes da mesma superfície, o que geraria falsas
correspondências.
Ângulo suporte
O ângulo suporte indica o ângulo máximo entre a normal do ponto orientado da base
da spin-image e as normais dos pontos da superfície. Pontos com ângulos maiores serão
desconsiderados na criação das spin-images.
3.2. DESCRITORES SPIN-IMAGES
14
(a) 0.5× resolução da malha
(b) 8× resolução da malha
(c) 2.5× resolução da malha
Figura 3.3: Efeito de diferentes bin sizes em spin-images.
A importância deste parâmetro é semelhante à importância da distância suporte para
excluir pontos de regiões distantes da base.
3.2.4
Textured Spin-Images
As Textured Spin-Images, ou TSI, são extensões das spin-images que consideram
informação de textura na formação das imagens. Sua formulação é parecida com a original.
Seja x um ponto da superfície e I(x) a luminância associada aos valores (R, G, B) da
textura da superfície em x. É necessário quantizar a luminância I(x) em L intervalos de
tons de cinza li .
Um spin-map com textura é uma extensão da Equação 3.1, definido pela aplicação
µq
T SIO (x) → (α, β, li ) =
¶
kx − pk
2
− (n · (x − p))2 , n · (x − p), l
i
.
(3.2)
A partir do spin-map com textura, é possível criar uma spin-image com textura.
Porém, neste caso os bins não vão acumular a quantidade de pontos que caem em cada
um, mas seus tons de cinza quantizados li .
3.2. DESCRITORES SPIN-IMAGES
15
Além disso, fazendo L = 1, existirá apenas um intervalo [0, 1] de tons de cinza, o
que caracteriza as spin-images convencionais. Desse modo, as spin-images podem ser
consideradas um caso particular das spin-images com textura.
A Figura 3.4 exibe um spin-map e suas spin-images convencional e com textura, com
L = 4.
(a) Spin-map
(b) Spin-image convencional
(c) Spin-image com textura
Figura 3.4: Spin-map e spin-image convencional e com textura.
3.2.5
Comparação de Spin-Images
Naturalmente, imagens criadas por pontos correspondentes pertencentes a diferentes
visões não serão exatamente iguais. É necessário aplicar técnicas para medir a similaridade
entre imagens, e criar correspondências entre os pares de pontos que apresentem imagens
mais parecidas.
Neste trabalho, as técnicas de comparação de imagens utilizadas foram aquelas
adotadas por Johnson (1997).
Define-se o coeficiente de correlação linear entre duas imagens P e Q pela função
3.3. SELEÇÃO DE PONTOS
16
P P
pi qi − pi qi
R(P, Q) = q¡ P
P 2¢ ¡ P 2
P 2¢ ,
2
N pi − ( pi ) N qi − ( qi )
N
P
(3.3)
onde pi e qi são os tons de cinza dos pixels de P e Q, e N é a quantidade de pixels
da imagem. Este coeficiente deve variar entre −1, quando as imagens são totalmente
diferentes, e 1, quando as imagens forem idênticas. Portanto, valores mais altos de R
indicam imagens mais parecidas.
Porém, nem sempre se espera que spin-images de pontos correspondentes sejam
similares por toda a imagem. Isso ocorre, por exemplo, por que uma spin-image criada
a partir de uma determinada visão pode não conter dados de uma região que uma outra
visão pode ter, ou seja, espera-se que as visões tenham oclusões.
Essas oclusões ocorrem normalmente em regiões inteiras das superfícies, e implicam
que regiões das spin-images não contenham esses dados. Seguindo esse raciocínio, uma
maneira de resolver parcialmente esse problema é desconsiderar bins que não contenham
dados em alguma das imagens P ou Q no cálculo do coeficiente de correlação linear.
Porém, utilizando-se puramente o coeficiente de correlação linear, alguns casos
apresentarão resultados não desejados. Por exemplo, duas imagens com pequena região
de sobreposição podem ter um coeficiente alto c1 , se apenas estão região de sobreposição
for parecida, enquanto duas imagens com grande região de sobreposição podem ter um
coeficiente menor que c1 , se forem um pouco menos parecidas em sua grande região de
sobreposição. Faz-se necessário, então, o uso de uma outra técnica que leve em conta a
quantidade de pixels na região de sobreposição.
Neste caso, uma técnica que resolve bem este problema é a medida de similaridade,
que considera, além do coeficiente de correlação linear, sua variância, para medir sua
confiabilidade. Define-se a medida de similaridade pela função
µ
2
C(P, Q) = (atanh(R(P, Q))) − λ
1
N −3
¶
,
(3.4)
onde N é a quantidade de pixels na região de sobreposição e λ é um peso associado à
variância.
Para estimar λ, é necessário, para cada spin-image criada, medir a quantidade de bins
que possuem valor não nulo. Define-se λ como a metade da mediana desses valores.
3.3
Seleção de Pontos
O processo de criação e comparação de spin-images tem alto custo computacional e de
armazenamento na memória. Seja m a quantidade de pontos da primeira malha, e n
a quantidade de pontos da segunda malha. Para a geração de correspondências entre
3.3. SELEÇÃO DE PONTOS
17
pontos dessas malhas, é necessário criar e armazenar m spin-images de uma malha e
n spin-images da segunda malha, e comparar todas as spin-images de uma malha com
todas as spin-images da outra malha. Esse procedimento resulta num algoritmo de ordem
quadrática.
Portanto, criar spin-images para todos os pontos das malhas torna-se um processo
inviável, tanto computacionalmente, quanto em termos de armazenamento na memória.
Uma maneira de resolver esse problema é efetuar uma seleção de pontos nas malhas para
criação e comparação de spin-images.
Neste trabalho, foram implementadas duas técnicas para seleção de pontos nas malhas.
A primeira é a seleção aleatória de pontos em ambas as malhas. A segunda é a seleção
de acordo com a curvatura local da superfície.
As subseções seguintes descrevem essas duas técnicas.
3.3.1
Seleção Aleatória de Pontos
A seleção aleatória é um procedimento simples onde uma determinada proporção de pontos
das malhas é selecionado aleatoriamente para criação de spin-images.
Porém, esse método não garante que os pontos selecionados em uma malha serão
iguais aos pontos selecionados na segunda malha. Isso pode tornar impossível o registro
das malhas. Uma variante para resolver esse problema é selecionar todos os pontos de
uma malha, e selecionar aleatoriamente uma pequena proporção na segunda malha. Ainda
assim, nada garante que os pontos selecionados aleatoriamente na segunda malha façam
parte de uma região do objeto que não pertença à primeira malha.
3.3.2
Seleção por Curvatura Local
A seleção por curvatura local da superfície é um processo mais elaborado que envolve
cálculos de curvatura em todos os pontos das malhas. Uma proporção dos pontos com
maior curvatura é selecionado em ambas as malhas para a criação de spin-images.
2
Neste trabalho, foram analisadas a curvatura gaussiana κ1 κ2 , a curvatura média κ1 +κ
,
2
a curvatura principal máxima κ1 e a soma dos quadrados das curvaturas principais κ21 +κ22 .
A medida que apresentou melhores resultados na geração das correspondências foi a soma
dos quadrados das curvaturas principais. A Figura 3.5 exibe uma malha com seus 15%
pontos de maior medida κ21 + κ22 destacados.
Seguem abaixo alguns conceitos preliminares da Geometria Diferencial e a técnica
utilizadas para cálculo das curvaturas, baseada em (Meyer et al. 2003).
3.3. SELEÇÃO DE PONTOS
18
Figura 3.5: Malha com pontos de alta medida de curvatura κ21 + κ22 destacados.
Conceitos de Geometria Diferencial
Seja S uma superfície diferenciável bidimensional em R3 . Para cada ponto p ∈ S, é
possível calcular seu plano tangente, ortogonal a seu vetor normal n.
Para cada direção unitária eθ do plano tangente, define-se a curvatura normal κN (θ)
como a curvatura da curva que é a intersecção da superfície com o plano contendo n e eθ .
As curvaturas principais κ1 e κ2 serão, respectivamente, o maior e o menor valor das
curvaturas normais, considerando-se todas as direções eθ em p.
A curvatura média em p é definida como a média das curvaturas normais de p, de
acordo com a equação
1
κH =
2π
Z 2π
κN (θ)dθ.
(3.5)
0
A partir dessas definições, é possível formular uma famosa definição da curvatura
média, dada por
κ1 + κ2
κH =
.
(3.6)
2
Finalmente, a curvatura Gaussiana é definida pela equação
κG = κ1 κ2 .
(3.7)
A técnica utilizada neste trabalho, faz uso de uma importante relação entre
minimização da área da superfície e a curvatura média, dada pela equação
2κH n =
∇A
,
diam(A)→0 A
lim
onde A é um pequeno elemento de área orientada.
(3.8)
3.3. SELEÇÃO DE PONTOS
19
O operador K(p) = 2κH (p)n(p) é chamado de operador de Laplace-Beltrami. Uma
vez conhecido o vetor K(p), o cálculo do vetor normal n( p) e da curvatura κH (p) são
imediatos.
Descrições mais detalhadas dos conceitos acima são encontradas em (Carmo 2005).
Médias espaciais
As definições acima devem ser adaptadas para superfícies discretas, ou malhas. Nesta
técnica, essa adaptação é feita utilizando médias espaciais. Neste caso, as propriedades de
um ponto serão analisadas de acordo com um espaço contido em sua vizinhança imediata,
ou vizinhança estrelada. Com essa idéia, a curvatura Gaussiana discreta κ̂G , por exemplo,
é definida pela equação
ZZ
1
κ̂G =
κG dA,
(3.9)
A A
onde A é uma determinada área contida na vizinhança estrelada do ponto.
As áreas utilizadas para o cálculo das médias espaciais são regiões de Voronoi.
Considere o conjunto de faces triangulares, vértices e arestas que formam a vizinhança
estrelada de um ponto. Os polígonos que determinam os elementos de área são formados
pelo ponto central da estrela, os pontos médios das arestas que conectam cada vértice com
o ponto central, e os circuncentros dos triângulos. A união desses polígonos é chamada
região de Voronoi, ou AV oronoi , como ilustrado na Figura 3.6.
Figura 3.6: Região de Voronoi de uma vizinhança estrelada.
O cálculo da área de uma região de Voronoi é feita triângulo a triângulo. Se
os triângulos da vizinhança estrelada não são obtusos, é possível utilizar propriedades
geométricas simples para chegar à equação
AV oronoi =
1 X
(cot αij + cot βij )kxi − xj k2 .
8
(3.10)
xj ∈N1 (i)
Caso existam triângulos obtusos, a área deve ser calculada triângulo a triângulo. Os
triângulos não obtusos terão área igual à área de Voronoi neste triângulo. Se um triângulo
3.3. SELEÇÃO DE PONTOS
20
obtuso tiver ângulo obtuso no ponto central da estrela, a área será metade da área do
triângulo. Senão, sua área será um quarto da área do triângulo. Essa nova área será
chamada AM ixed .
Curvatura Média Discreta
Para a obtenção das normais da superfície e curvatura média, o operador Laplace-Beltrami
será calculado. Inicialmente, o Laplaciano da superfície em relação aos parâmetros u e v é
calculado, usando a discretização da superfície como espaço paramétrico conforme. Desse
modo, é possível obter a relação
ZZ
ZZ
K(x)dA = −
AM
∆u,v xdudv.
(3.11)
AM
Usando o teorema de Gauss, chega-se à formulação final
ZZ
K(x)dA =
AM
1 X
(cot αij + cot βij )(xi − xj ),
2
(3.12)
xj ∈N1 (i)
onde αij e βij são os ângulos opostos à aresta determinada pelos pontos (xi , xj ) e N1 (i) é
o conjunto de vértices na vizinhança estrelada do vértice xi .
Usando a região AM ixed e a Equação 3.12, chega-se ao operador
K(xi ) =
X
1
2AM ixed
(cot αij + cot βij )(xi − xj ).
(3.13)
xj ∈N1 (i)
A partir deste operador, a curvatura média κH é facilmente obtida extraindo-se metade
da norma de K.
Curvatura Gaussiana Discreta
A seguinte equação é consequência do Teorema de Gauss-Bonnet:
ZZ
κG dA = 2π −
AM
X
²j ,
(3.14)
j
onde ²j são os ângulos externos da fronteira da região. A partir dessa equação, é possível
chegar à forma
ZZ
n
X
κG dA = 2π −
θj ,
(3.15)
AM
j=1
onde θj é o ângulo do triângulo j no vértice xi e n é a quantidade de triângulos.
3.4. GERAÇÃO DE CORRESPONDÊNCIAS
21
Finalmente, o operador de curvatura Gaussiana discreto é dado por
κG (xi ) =
1
AM ixed
Ã
2π −
n
X
!
θj
.
(3.16)
j=1
Curvaturas Principais Discretas
Tendo conhecimento das curvaturas média e Gaussiana, o cálculo das curvaturas principais
é direto, dado pelas equações
p
κ1 (xi ) = κH (xi ) + ∆(xi )
p
κ2 (xi ) = κH (xi ) − ∆(xi ),
(3.17)
(3.18)
onde ∆(xi ) = κ2H (xi ) − κG (xi ).
3.4
Geração de Correspondências
Após a criação das spin-images de pontos selecionados, o próximo passo é efetuar as
comparações entre as spin-images. Para cada ponto p associado a uma spin-image, a
maneira mais simples de encontrar seu ponto correspondente seria encontrar o ponto
cuja imagem tenha a maior medida de similaridade com sua imagem, ou seja, a imagem
mais parecida. Porém, nem sempre imagens parecidas implicam pontos correspondentes,
devido à simetria de objetos, por exemplo.
A técnica utilizada neste trabalho para encontrar correspondências baseia-se na análise
de um histograma das medidas de similaridade (Johnson 1997). Bons candidatos a
correspondências se encontram no topo do histograma. Portanto, é necessário definir
um threshold para separar esses bons candidatos, ou outliers do histograma.
Estatisticamente, distribuições bem comportadas, como é o caso das medidas de
similaridade das spin-images, podem ter seus outliers identificados pelo estudo dos quartis.
Seja fs a diferença entre o maior quartil e o menor quartil. Os outliers extremos
encontram-se 3fs acima do maior quartil (Devore 1999). Este valor será justamente o
threshold utilizado para identificar outliers.
A Figura 3.7 exibe um exemplo de histograma, destacando-se a mediana m, o menor
e maior quartil q1 e q2 , respectivamente, o valor de fs = q2 − q1 , e o threshold de distância
q2 + 3fs . Os valores destacados em tom mais escuro são os outliers.
Uma vez identificados, os outliers serão dados como pontos correspondentes de p. A
próxima seção trata da filtragem aplicada a essas correspondências para eliminar falsos
pares de pontos.
3.5. FILTRAGENS DE CORRESPONDÊNCIAS
22
Figura 3.7: Exemplo de histograma utilizado para detecção de outliers
3.5
Filtragens de Correspondências
Já foi visto que pontos correspondentes devem ter spin-images parecidas. Porém, a
recíproca nem sempre é verdadeira. Duas razões frequentes para que um ponto encontre
mais de um ponto correspondente pela análise das medidas de similaridade são: a simetria
do modelo e o fato de pontos próximos criarem spin-images parecidas. Além disso, o ponto
pode pertencer a uma região fora da região de sobreposição entre as malhas. Neste caso,
não existem pontos correspondentes na outra malha, o que contribui para a criação de
falsas correspondências.
Portanto, é necessário realizar filtragens que garantam a consistência das
correspondências. Neste trabalho são realizadas duas filtragens. A primeira baseiase numa análise estatística das medidas de similaridade das correspondências. A
segunda realiza um teste de consistência geométrica entre os pontos correspondentes.
As correspondências que passam por essas duas filtragens são agrupadas para o cálculo de
uma transformação que melhor alinhe os pontos correspondidos. As subseções seguintes
descrevem essas filtragens e o critério utilizado para agrupar correspondências.
3.5.1
Filtragem Usando Medidas de Similaridade
Seja M o conjunto das medidas de similaridade das imagens das correspondências, e
m o maior valor desse conjunto. Esta filtragem elimina todas as correspondências que
apresentem medida de similaridade abaixo de uma certa fração de m. Neste trabalho, as
3.5. FILTRAGENS DE CORRESPONDÊNCIAS
23
correspondências com medida de similaridade abaixo da metade de m foram descartadas
nesta primeira filtragem.
As correspondências envolvendo pontos contidos em regiões onde não há sobreposição
entre as superfícies devem ser descartados nesta filtragem, pois como não há
correspondências consistentes envolvendo tais pontos, suas medidas de similaridade devem
ser baixas, provavelmente abaixo da metade de m.
3.5.2
Filtragem Usando Consistência Geométrica
Após a primeira filtragem, as correspondências devem passar por uma filtragem de
consistência geométrica.
Duas correspondências C1 = [s1 , m1 ] e C2 = [s2 , m2 ] serão consideradas
geometricamente consistentes se |ks1 − s2 k − km1 − m2 k| < ε, para ε suficientemente
pequeno, onde s1 e m1 são pontos correspondentes das malhas, assim como s2 e m2 . Em
termos de coordenadas spin-map, isso é equivalente a analisar as funções
kSm2 (m1 ) − Ss2 (s1 )k
,
(kSm2 (m1 )k + kSs2 (s1 )k) /2
(3.19)
Dgc (C1 , C2 ) = max(dgc (C1 , C2 ), dgc (C2 , C1 )),
(3.20)
dgc (C1 , C2 ) =
onde S é a aplicação spin-map definida pela Equação 3.1 e a função max retorna o maior
de seus parâmetros. O quociente da Equação 3.19 normaliza a diferença das distâncias
de acordo com a média das normas das coordenadas spin-map. Se Dgc é pequeno, então
as correspondências são geometricamente consistentes.
Para realizar a filtragem em várias correspondências, é necessário criar um
procedimento que teste cada correspondência C com todas as outras, e verificar se uma
quantidade razoável de correspondências é consistente com C. Em caso afirmativo, C
passa pela filtragem. Em caso negativo, C é removida e o teste continua.
Finalmente, é necessário definir dois parâmetros. O primeiro é chamado threshold
de consistência geométrica (Tgc ). Se Dgc (C1 , C2 ) < Tgc , então C1 e C2 são considerados
geometricamente consistentes.
O segundo parâmetro, propGC , determina a proporção mínima de correspondências
que devem ser geometricamente consistentes com C para que C passe na filtragem.
3.5.3
Agrupamento
Após as filtragens, as correspondências apresentam um bom grau de consistência. O
próximo passo a ser executado é o agrupamento de algumas correspondências utilizando
critérios que garantam o cálculo de uma boa transformação. Cada grupo criado com pelo
menos duas correspondências deve ser capaz de gerar uma transformação.
3.6. CÁLCULO DA TRANSFORMAÇÃO: ALGORITMO DE HORN
24
Nesta etapa, serão utilizados dois critérios: a consistência geométrica, através da
função dgc , e a distância entre as correspondências. Quanto mais espalhadas as
correspondências estiverem, maiores as chances de se obter uma boa transformação,
minimizando o efeito de ruídos. Esses dois requisitos são combinados para gerar as funções
wgc (C1 , C2 ) =
dgc (C1 , C2 )
1 − e−((kSm2 (m1 )k+kSs2 (s1 )k)/(2γ))
Wgc (C1 , C2 ) = max(wgc (C1 , C2 ), wgc (C2 , C1 ))
(3.21)
(3.22)
Se C1 e C2 forem geometricamente consistentes e distantes, Wgc será pequeno. A
variável γ deve ser definida em k vezes a resolução da malha. Esse valor estimula o
agrupamento de correspondências distantes pelo menos k vezes a resolução da malha.
Neste trabalho, foi utilizado k = 4.
Seja n a quantidade de correspondências. Será possível realizar n agrupamentos, um
para cada correspondência. Segue abaixo o procedimento para geração do grupo de uma
correspondência C.
Seja Gi o grupo gerado por Ci e Tgc o threshold de consistência geométrica definida
anteriormente. Este grupo deve ser inicializado com a correspondência Ci , ou seja, Gi =
{Ci }. Para cada correspondência Cj , se Wgc (Ci , Cj ) < Tgc , adiciona-se Cj ao grupo Gi .
Cada grupo vai gerar uma transformação, que ao ser aplicada à malha deve passar
por uma validação final. Uma vez encontrada uma transformação válida, o processo pára,
e esta transformação será o alinhamento inicial resultante. A seção seguinte descreve o
Algoritmo de Horn, responsável pelo cálculo de uma transformação dado um grupo de
correspondências.
3.6
Cálculo da Transformação: Algoritmo de Horn
Dado um grupo de correspondências, formadas por pontos em dois sistemas de
coordenadas locais, a saber, os sistemas de coordenadas das duas malhas, é necessário
encontrar o movimento rígido que minimize a distância entre os pares de pontos. Uma
solução para esse problema usando mínimos quadrados foi desenvolvida por Horn (1987),
e será brevemente descrita nesta seção.
Neste método, as rotações são representadas por quatérnios, que podem ser vistos
como vetores no R4 , e as translações são representadas por vetores do R3 . O vetor de
registro de uma superfície será denotado por um vetor ~q = [~qR |~qT ]t , onde ~qR é um quatérnio
representando a rotação, e ~qT é um vetor do R3 representando a translação.
3.6. CÁLCULO DA TRANSFORMAÇÃO: ALGORITMO DE HORN
25
O objetivo desse método é encontrar a transformação ~q que minimize uma função de
mínimos quadrados dada pela equação
n
1X
f (~q) =
kp2,i − R(~qR )~p1,i − ~qT k2 ,
n i=1
(3.23)
onde n é a quantidade de correspondências, pk,i são pontos da malha k, e R(~qR ) é a matriz
de rotação associada ao quatérnio ~qR . Essa matriz é dada pela fórmula
2
2(q1 q2 − q0 q3 )
2(q1 q3 + q0 q2 )
q0 + q12 − q22 − q32
R(~qR ) = R(q0 , q1 , q2 , q3 ) = 2(q1 q2 + q0 q3 )
q02 + q22 − q12 − q32
2(q2 q3 − q0 q1 ) .
2(q1 q3 − q0 q2 )
2(q2 q3 + q0 q1 )
q02 + q32 − q12 − q22
Este método encontra a melhor rotação através da análise dos autovetores de uma
matriz simétrica Q 4 × 4.
Dado um grupo de correspondências de pontos das malhas m1 e m2 , é necessário,
inicialmente, calcular os centróides c1 e c2 dos pontos das malhas m1 e m2 ,
respectivamente, de acordo com a fórmula
n
1X
ck =
pk,i ,
n i=1
(3.24)
onde pk,i é um ponto da malha k.
Em seguida, são definidos novos pontos p0k,i , de acordo com a equação
p0k,i = pk,i − ck .
(3.25)
A matriz Q utiliza nove produtos Sij , dados pela equação
Smn =
n
X
p01,i (m)p02,i (n),
(3.26)
i=1
onde p01,i (m) e p02,i (n) são coordenadas dos pontos, com 1 < m < 3 e 1 < n < 3.
Finalmente, Q é dada por
(S11 + S22 + S33 )
S23 − S32
S31 − S13
S12 − S21
S
−
S
(S
−
S
−
S
)
S
+
S
S
+
S
23
32
11
22
33
12
21
31
13
.
Q=
S
−
S
S
+
S
(−S
+
S
−
S
)
S
+
S
31
13
12
21
11
22
33
23
32
S12 − S21
S31 + S13
S23 + S32
(−S11 − S22 + S33 )
3.7. VALIDAÇÃO
26
O autovetor unitário correspondente ao maior autovalor dessa matriz será a melhor
rotação ~qR . A melhor translação ~qT será dada por
~qT = c2 − R(~qR )c1 .
(3.27)
A transformação ~q pode então ser aplicada a todos os pontos da malha m1 . A validação
desta transformação utiliza os pontos transformados da malha m1 e os pontos da malha
m2 . Este processo é descrito na seção seguinte. Maior rigor matemático do Algoritmo de
Horn pode ser encontrado em (Horn 1987).
3.7
Validação
A etapa final do alinhamento automático inicial é a validação da transformação. Uma
vez encontrada uma transformação que passe pelo teste de validação, o algoritmo pára e
inicia-se a etapa de refinamento do registro.
Uma transformação será considerada válida se a região de sobreposição entre as duas
superfícies após aplicar a transformação for maior que uma certa razão da área das
superfícies. Um ponto p pertencente a uma malha m1 estará na região de sobreposição
das malhas m1 e m2 se existir q ∈ m2 tal que kp − qk < Dv , onde Dv é um threshold de
distância que deve ser definido entre 1 e 2 vezes a resolução da malha.
Como o algoritmo de Horn minimiza a distância entre as correspondências, estas devem
ser automaticamente consideradas pertencentes à região de sobreposição. Em seguida,
novas correspondências pertencentes à região de sobreposição são criadas da seguinte
maneira: para cada correspondência (p1 , p2 ), com p1 ∈ m1 , selecionam-se todos os vizinhos
p1,i de p1 em m1 conectados por arestas. Seja q o ponto mais próximo de p1,i em m2 . Se
kp1,i − qk < Dv , então a correspondência (p1,i , q) é criada. Esse processo é repetido para
todos os vizinhos de p1 , e para cada correspondência, até que não seja possível criar
novas correspondências. Se a quantidade de correspondências finais for maior que uma
certa razão da quantidade de pontos das malhas, então a transformação é validada. Caso
contrário, um novo agrupamento é feito e uma nova transformação é calculada.
A Figura 3.8 ilustra o processo de validação. A Figura 3.8(a) exibe duas malhas e seus
pontos correspondentes agrupados. Após o cálculo da transformação usando o algoritmo
de Horn, as malhas são alinhadas, como mostra a Figura 3.8(b). Finalmente, a Figura
3.8(c) exibe a região de sobreposição detectada, em tom mais escuro. Boas transformações
alcançam regiões de sobreposição com, no mínimo, 30% do total de pontos das malhas.
Uma vez obtida uma transformação válida, um pequeno ajuste na transformação é
calculado. Utilizando agora o conjunto de correspondências final, o algoritmo de Horn é
novamente aplicado. Como a quantidade de pares de pontos agora é maior, será possível
3.7. VALIDAÇÃO
27
(a) Grupo de correspondências entre duas malhas.
(b) Alinhamento inicial das malhas
após aplicação do Algoritmo de Horn
usando um grupo de correspondências.
(c) Região
de
sobreposição
detectada para validação da
transformação
Figura 3.8: Agrupamento e validação.
obter uma transformação mais precisa. Finalmente, esta nova transformação é aplicada
e inicia-se a etapa de refinamento, tema do próximo capítulo.
Capítulo 4
Refinamento do Registro usando ICP
4.1
Introdução
Este capítulo descreve o algoritmo ICP e algumas de suas variantes. Este algoritmo é
responsável pelo registro final entre duas superfícies previamente alinhadas de acordo
com o método descrito no capítulo anterior.
4.2
Visão Geral
O algoritmo ICP (Iterative Closest Point) (Besl & Mckay 1992) é a técnica mais utilizada
atualmente para realizar registro de superfícies. Dadas duas malhas pré-alinhadas, o ICP
executa um processo iterativo para refinar a transformação inicial até convergir para um
mínimo local. Se o alinhamento inicial for bom, o ICP converge corretamente. Ao final
deste processo, as duas malhas com alinhamento estimado terão um alinhamento mais
preciso.
Seja M1 = {~pi } o conjunto de pontos da malha m1 e M2 = {~qi } o conjunto de pontos
da malha m2 . O algoritmo ICP original segue os passos abaixo, para cada iteração k:
1. Para cada ponto p~i , calcule seu ponto mais próximo ~xi ∈ M2 ;
2. Encontre a transformação ~qk que minimiza a distância entre os pares de pontos
(~pi , ~xi ) usando o algoritmo de Horn e encontre o erro dk dado pela Equação 3.23;
3. Aplique a transformação ~qk aos pontos de M1 ;
4. Se dk − dk−1 < τ , onde τ é um threshold pequeno, o processo pára. Senão, volte
para o primeiro passo.
A transformação resultante será a composição das transformações ~qi , ou seja, ~q = ~qk ◦
~qk−1 ◦ · · · ◦ ~q1 .
28
4.3. SELEÇÃO DE PONTOS
29
Nos últimos anos, muitas variantes desse algoritmo foram desenvolvidas, afetando
todos os estágios do procedimento. Segundo Rusinkiewicz & Levoy (2001), o algoritmo
ICP pode ser dividido em seis estágios:
1. Seleção de pontos em uma ou nas duas malhas;
2. Geração de correspondências entre os pontos selecionados;
3. Atribuição de pesos nos pares de pontos;
4. Rejeição de pares de acordo com algum critério;
5. Determinação de uma métrica de erro;
6. Minimização da métrica de erro.
As seções seguintes definem os estágios do algoritmo, descrevendo algumas de suas
variantes, inclusive a solução implementada neste trabalho. As análises comparativas das
diversas variantes foram realizadas por Rusinkiewicz & Levoy (2001).
4.3
Seleção de Pontos
O primeiro estágio do algoritmo ICP utiliza algum critério para seleção dos pontos que
serão considerados na geração de correspondências. As estratégias mais utilizadas são:
• Seleção de todos os pontos;
• Amostragem uniforme dos pontos (Turk & Levoy 1994);
• Amostragem aleatória dos pontos a cada iteração (Masuda et al. 1996);
• Amostragem uniforme no espaço das normais (Rusinkiewicz & Levoy 2001).
Além disso, em paralelo a todas as estratégias acima existe a opção de realizar a
amostragem em apenas uma das malhas. Neste caso, deve se considerar todos os pontos
de uma malha e aplicar alguma das técnicas acima à outra malha.
Fazendo-se uma análise da convergência em função do número de iterações realizadas,
todas as estratégias apresentam resultados semelhantes em grande parte dos modelos
(Rusinkiewicz & Levoy 2001). Este trabalho adota a estratégia de seleção de todos os
pontos, tendo em vista a simplicidade do método.
4.4. GERAÇÃO DE CORRESPONDÊNCIAS
4.4
30
Geração de Correspondências
A geração dos pares de pontos é a etapa mais importante do algoritmo ICP. Além de ser
geralmente a etapa que requer maior custo computacional, a geração de correspondências
consistentes é determinante para obtenção de transformações precisas.
Para cada ponto p ∈ M1 selecionado em uma malha, os critérios mais utilizados para
determinar seu ponto correspondente são:
• Encontrar seu ponto mais próximo em m2 (Besl & Mckay 1992);
• Encontrar a intersecção do raio que sai do ponto p, na direção de sua normal, com
a malha m2 (Chen & Medioni 1992);
• Projetar o ponto p na malha m2 do ponto de vista do scanner gerador da range
image de m2 (Blais & Levine 1995);
Um critério opcional que pode ser utilizado nos métodos acima é a restrição apenas
a pares que tenham ângulo entre suas normais limitado, por exemplo, a 45◦ . Segundo
Rusinkiewicz & Levoy (2001), apesar de apresentar performance inferior em alguns tipos
de geometria, os algoritmos de ponto mais próximo são robustos em grande parte das
geometrias. Por essa razão, o algoritmo de ponto mais próximo com restrição de ângulo
de normais limitado foi a técnica implementada neste trabalho.
Nesta técnica, para cada ponto pi ∈ M1 , calcula-se o ponto mais próximo xi ∈ M2 .
Supondo que uma malha tenha n pontos e a segunda malha tenha m pontos, este
procedimento tem complexidade O(nm). Para acelerar esse processo, Simon (1996) propôs
a utilização de uma kd-tree para busca dos pontos mais próximos. Desse modo, a busca
pelo ponto mais próximo se restringe a uma busca numa árvore binária, reduzindo a
complexidade do algoritmo para O(n log m)
A subseção seguinte descreve os passos para criação e busca em uma kd-tree.
4.4.1
Kd-trees
Uma kd-tree é uma árvore binária que generaliza o método de bisecção para k dimensões.
Dado um ponto p ∈ M1 , o problema de busca do ponto mais próximo de p em M2 pode ser
resolvido com uma kd-tree tridimensional. O processo de criação da kd-tree segue abaixo.
Inicialmente, é necessário dividir o espaço com um plano paralelo ao plano yz que
passe por um ponto q de M2 de modo que a quantidade de pontos em cada subespaço seja
igual. O subespaço abaixo do plano será o filho à esquerda, e o subespaço acima do plano
será o filho à direita. O ponto q pode ser facilmente identificado como a mediana das
coordenadas x dos pontos. Esse procedimento continua nos filhos deste nó, dividindo-se o
espaço sucessivamente pelos planos yz, xz e xy, até que não haja mais que um ponto em
4.5. ATRIBUIÇÃO DE PESOS ÀS CORRESPONDÊNCIAS
31
cada subespaço. Estes pontos estarão associados às folhas da árvore. Os nós das árvores
devem incluir duas informações fundamentais. A primeira é o ponto q que divide seu
espaço. O segundo é um código t informando se o plano divisor é paralelo ao plano yz, xz
ou xy. Esse processo de criação tem complexidade O(n log n). A Figura 4.1 ilustra essa
idéia no caso bidimensional.
Figura 4.1: Processo de criação de uma kd-tree bidimensional.
O processo de busca é um algoritmo recursivo. Inicialmente, devem se definir um
threshold Dmax que será a distância máxima aceita para que um ponto em M2 seja
candidato a ponto mais próximo. Este valor deve estar entre 1 e 2 vezes a resolução
da malha. Ao término do processo, haverá uma pequena lista de candidatos a ponto mais
próximo. Finalmente, os pontos dessa lista são testados um a um para identificação do
ponto mais próximo.
Dado um ponto p ∈ M1 , a busca começa pela raiz da árvore. Se kp − qk < Dmax , q é
adicionado na lista de candidatos. Se a coordenada indicada pelo parâmetro t for menor
que a mesma coordenada de q, a busca segue pelo filho à esquerda. Senão, a busca segue
pelo filho à direita, até chegar a uma folha da árvore, quando o algoritmo retorna a lista
de candidatos.
4.5
Atribuição de Pesos às Correspondências
Opcionalmente, é possível atribuir um peso a cada correspondência criada, de acordo com
algum critério que meça a confiabilidade do par de pontos. Duas estratégias interessantes
4.6. REJEIÇÃO DE CORRESPONDÊNCIAS
32
para estimar e atribuir pesos às correspondências consideram a distância entre o par de
pontos e o ângulo de suas normais.
Na primeira estratégia, pares de pontos com distâncias altas terão pesos baixos. Seja
Distmax a maior distância dentre os pares de pontos. Segundo Godin et al. (1994), os
pesos podem ser estimados de acordo com a equação
W =1−
Dist(p1 , p2 )
,
Distmax
(4.1)
onde p1 e p2 são pontos de cada correspondência.
A segunda estratégia analisa o ângulo entre as normais dos pares de pontos, de acordo
com o produto escalar dado pela equação
W = n1 · n2 ,
(4.2)
onde n1 e n2 são os vetores normais de cada par de pontos.
Essas estratégias apresentam, de modo geral, performance ligeiramente superior ao
uso de pesos constantes nos pares de pontos (Rusinkiewicz & Levoy 2001). Desse modo,
neste trabalho foi adotada a estratégia de utilizar pesos constantes.
4.6
Rejeição de Correspondências
Esta etapa é fundamental para a rejeição de pares de pontos fora da região de sobreposição
das malhas. De modo geral, as estratégias mais utilizadas para rejeição de pares de pontos
utilizam como critério a distância entre os pontos. Seguem abaixo algumas das estratégias
mais utilizadas.
• Rejeição das correspondências cuja distância seja maior que uma distância
determinada pelo usuário;
• Rejeição dos n% pares mais distantes (Pulli (1999) sugere 10%);
• Rejeição das correspondências cuja distância seja maior que um múltiplo do desvio
padrão das distâncias (Masuda et al. (1996) sugere 2.5 vezes o desvio padrão).
Seguindo a idéia de detecção de áreas de sobreposição descrita no capítulo anterior, este
trabalho utiliza um threshold de distância determinado como um múltiplo da resolução
da malha. Bons resultados são alcançados definindo a distância máxima entre 1 e 2 vezes
a resolução da malha.
Outra idéia interessante para rejeição de pares consiste em descartar todas as
correspondências contendo pontos na fronteira das malhas. Este procedimento rejeita
pares que contém pontos da fronteira de uma malha e pontos da segunda malha localizados
4.7. MÉTRICAS DE ERRO E MINIMIZAÇÃO
33
nas proximidades da fronteira da primeira malha, porém fora da região de sobreposição.
A Figura 4.2 ilustra essa idéia. Esta estratégia também foi implementada neste trabalho.
Figura 4.2: Rejeição de pares contendo pontos de fronteira.
4.7
Métricas de Erro e Minimização
Uma vez determinadas as correspondências consistentes com seus determinados pesos, é
necessário definir uma métrica para estimar o erro de alinhamento entre esses pares de
pontos. Finalmente, calcula-se a transformação que minimize a métrica de erro.
As duas métricas mais utilizadas para estimar erro de alinhamento são a média da
soma dos quadrados das distâncias entre os pares de pontos e a média da soma dos
quadrados das distâncias entre ponto e plano.
Seja pi um ponto da malha m1 e xi seu ponto correspondente da malha m2 . A média
da soma dos quadrados das distâncias é definida pela função
n
f (q) =
1X
kxi − R(qR )pi − qT k2 .
n i=1
(4.3)
O método mais utilizado para encontrar a transformação que minimiza essa aplicação é o
algoritmo de Horn, descrito no capítulo anterior. Outras soluções para essa minimização
são a decomposição de valor singular (Arun et al. 1987), matrizes ortonormais (Horn
et al. 1988) e quatérnios duais (Walker et al. 1991). A precisão numérica e estabilidade
desses métodos é semelhante, segundo Eggert et al. (1997).
A segunda métrica utiliza a distância entre ponto e plano para estimar o erro, de
acordo com a função dada por
n
f (~q) =
1X 0
2
kx − R(~qR )~pi − ~qT k ,
n i=1 i
(4.4)
onde x0i = r| minr∈Si kr − R(~qR )~pi − ~qT k e Si é o plano que contém o ponto xi e tem
normal igual à normal de xi .
4.7. MÉTRICAS DE ERRO E MINIMIZAÇÃO
34
Neste caso, não existem soluções diretas. Os métodos de solução mais utilizados são o
método não linear Levenberg-Marquardt (Levenberg 1944) ou através de uma linearização
do problema, fazendo sin θ ∼ θ e cos θ ∼ 1, considerando θ pequeno.
Neste trabalho, foi implementada a métrica da média da soma dos quadrados das
distâncias entre os pares de pontos com solução dada pelo algoritmo de Horn.
Após a transformação ser encontrada e aplicada à malha, o algoritmo ICP retorna
à etapa de geração de correspondências. Como a transformação alterou a posição dos
pontos, diferentes correspondências podem ser geradas, resultando em uma transformação
diferente. Após algumas iterações, as transformações tendem a ser cada vez menores,
fazendo com que os novos pares de pontos não sejam diferentes dos anteriores. Neste
caso, a transformação se aproxima da identidade e o algoritmo pára.
Com o alinhamento final determinado pela transformação resultante do algoritmo ICP,
as malhas são alinhadas num sistema de coordenadas global. A etapa final consiste em
extrair um único modelo a partir de várias malhas alinhadas. O próximo capítulo descreve
uma técnica para extração de malhas em volumes.
Capítulo 5
Reconstrução da Malha Final
5.1
Introdução
Este capítulo descreve uma técnica desenvolvida por Curless & Levoy (1996) para
reconstrução de modelos a partir de malhas alinhadas chamada VRIP.
Esta técnica pode ser dividida em duas etapas. A primeira etapa realiza uma
integração volumétrica das malhas, criando um volume contendo as malhas alinhadas e
definindo uma função de distância. A segunda etapa executa um método muito conhecido
para extração de malhas a partir de volumes, chamado Marching Cubes (Lorensen &
Cline 1987). As seções seguintes descrevem essas etapas.
5.2
Integração Volumétrica
Dado um conjunto M = {m1 , m2 , . . . , mn } de malhas alinhadas em um sistema de
coordenadas global com seus respectivos pontos de visão pi do scanner, é necessário definir
um volume contendo todas as malhas. A resolução desse volume deve ser coerente com as
resoluções e dimensões das malhas. Resoluções de volume muito altas são inúteis, pois o
nível de detalhe do modelo final depende da resolução das malhas. Resoluções de volume
baixas causam perda nas informações das malhas.
Tendo em mãos o volume com boa resolução e contendo todas as malhas, o próximo
passo é definir neste volume uma função implícita de distância com sinal D : V → R, onde
V é o conjunto de vértices do volume. Essa distância será uma estimativa da distância
do vértice à malha final. Se, por exemplo, D(v) = 0 para algum vértice v, então a malha
deve passar por este vértice. Dado o volume com sua respectiva função de distância bem
definida, o algoritmo Marching Cubes realiza a extração da malha final.
A função D será construída a partir da combinação de n funções de distância com
sinal d1 (v), d2 (v), . . . , dn (v), e funções de peso w1 (v), w2 (v), . . . , wn (v).
35
5.2. INTEGRAÇÃO VOLUMÉTRICA
36
Cada função di (v) está associada a uma malha mi e representa, em cada vértice v, a
distância com sinal de v à malha. Seja pi o ponto de visão do scanner em relação à malha
mi , e ri,v (t) = pi + t · (v − pi ) o raio que sai do ponto de visão em direção ao vértice v.
O próximo passo será calcular a interseção qi,v de ri,v com mi . Finalmente, a função de
distância com sinal di (v) fica bem definida da seguinte maneira:
di (v) = kqi,v − pi k − kv − pi k.
(5.1)
A Figura 5.1 ilustra o cálculo de di (v).
Figura 5.1: Cálculo da função de distância com sinal di (v).
Opcionalmente, é possível atribuir pesos aos vértices do volume, de acordo, por
exemplo, com a incerteza do triângulo da malha que contenha a interseção qi,v . Tendo
conhecimento dos vetores normais aos vértices deste triângulo, é possível, através de uma
interpolação linear, obter o vetor normal em qi,v . Um critério bastante utilizado para
definir o peso de um vértice v do volume é o produto escalar do vetor normal em qi,v e
o vetor direção da visão do scanner. Ângulos menores implicam maior confiabilidade no
processo de captura, devido à iluminação mais adequada.
Os pesos wi (v) são associados às funções de distância di (v), e finalmente a função
D(v) será calculada como uma média das funções de distância di (v) ponderada pelos
pesos wi (v). Essa função é dada por
Pn
i=1 wi (v)di (v)
.
D(v) = P
n
i=1 wi (v)
(5.2)
Além disso, o peso final W (v) é dado por
W (v) =
n
X
i=1
wi (v).
(5.3)
5.2. INTEGRAÇÃO VOLUMÉTRICA
37
Uma maneira incremental de realizar os cálculos de D(v) e W (v) é através das funções
Di+1 (v) =
Wi (v)Di (v) + wi+1 (v)di+1 (v)
Wi (v) + wi+1 (v)
Wi+1 (v) = Wi (v) + wi+1 (v).
(5.4)
(5.5)
Uma malha resultante da reconstrução a partir de duas malhas alinhadas e com mesmo
ponto de visão do scanner deve ter sua região de sobreposição definida como a média
das regiões de sobreposição das duas malhas, de acordo com a Equação 5.2. Portanto,
essa técnica elimina os pequenos erros de alinhamento ainda existentes. Um exemplo
bidimensional é exibido na Figura 5.2, onde duas curvas m1 e m2 alinhadas com pequeno
erro são exibidas na Figura 5.2(a) e a curva resultante mf é exibida na Figura 5.2(b).
(a) Curvas m1 e m2 alinhadas com pequeno erro.
(b) Curva resultante mf .
Figura 5.2: Efeito da função de distância D(v) em duas curvas alinhadas com pequeno
erro.
Um último critério fundamental para o sucesso do método é a definição de um
threshold, a partir do qual as distâncias serão desprezadas, fixando o peso do vértice como
nulo. Considere o caso em que o modelo apresente duas malhas m1 e m2 que intersectem,
respectivamente, as retas r1,v e r2,v , para um mesmo vértice v do volume. Além disso, essas
duas malhas representam lados opostos do objeto, sem região e sobreposição. Sob essas
5.3. MARCHING CUBES
38
condições, o cálculo da função D(v) vai retornar uma média inconsistente das duas malhas,
considerando-as como duas malhas sobrepostas. Existindo tal threshold, as malhas opostas
não iriam interferir entre si. Além disso, os custos computacionais ficariam restritos às
vizinhanças das malhas.
O valor desse threshold deve ser grande o suficiente para que as "rampas"de distância
nas vizinhanças das malhas fiquem bem definidas, e pequeno o suficiente para evitar a
influência de malhas opostas.
Como a função de distância apresenta valores positivos e negativos, este threshold deve
ser convertido em dois valores Dmin e Dmax , negativo e positivo, respectivamente, que
determina o intervalo onde as distâncias serão consideradas, na vizinhança das malhas. O
valor utilizado em (Curless & Levoy 1996) é de metade do intervalo máximo de incerteza.
Detalhes para implementação eficiente desta técnica são encontrados no seu artigo
original (Curless & Levoy 1996).
5.3
Marching Cubes
Nesta seção o algoritmo Marching Cubes original (Lorensen & Cline 1987) é descrito.
É importante destacar que diversas variantes desta técnica existem atualmente. A
implementação do VRIP se baseia numa variante que utiliza tabelas para resolver algumas
das ambiguidades.
O Marching Cubes é um algoritmo bastante popular para extrair isosuperfícies de
dados volumétricos. Seja D uma função escalar implícita definida no volume, como a
função de distância definida na seção anterior. A superfície que satisfaz D(v) = α, com
α constante, é chamada isosuperfície definida por α. Dada uma função D definida nos
vértices de um volume e um valor α, a extração de sua isosuperfície pode ser aproximada
por uma isosuperfície linear por partes, composta de um conjunto de triângulos.
O algoritmo padrão realiza uma varredura voxel por voxel, verificando quais voxels a
superfície intersecta. Caso haja interseção, novos triângulos da superfície são criados. Esse
processo envolve a verificação dos valores da função de distância em cada vértice. Neste
caso específico, serão consideradas a função de distância D com valor α = 0. Portanto,
se houver variação de sinal da função de distância nos vértices do voxel, a isosuperfície
intersecta o voxel.
A geração dos triângulos é composta de duas etapas. A primeira etapa determina
o padrão topológico de intersecção através de uma tabela de 256 casos, que pode ser
resumida a 15 casos, desconsiderando-se simetrias de rotação e reflexão. A segunda etapa
determina a geometria de cada vértice dos triângulos da isosuperfície, usando interpolações
lineares nas arestas do voxel. Finalmente, a isosuperfície será formada pelo conjunto de
5.3. MARCHING CUBES
39
triângulos e vértices extraídos dos voxels do volume. Mais detalhes podem ser encontrados
em (Lorensen & Cline 1987) e (Newman & Yi 2006).
Capítulo 6
Resultados e Discussão
6.1
Introdução
Este capítulo discute alguns aspectos relevantes da técnica adotada e exibe resultados
alcançados neste trabalho. Exemplos de todo o processo de registro de superfícies e
reconstrução dos modelos ilustram este capítulo.
6.2
Resultados
A implementação da técnica adotada neste trabalho foi testada em diversos modelos
e analisada sob diversos aspectos, como topologia, geometria, curvatura, presença de
ruídos, diferentes resoluções das malhas, áreas de sobreposição e espaçamento angular
entre visões.
O ponto mais relevante para o sucesso do procedimento é a definição dos parâmetros
envolvendo criação de spin-images, filtragem de correspondências, algoritmo ICP e
reconstrução do modelo. Segue abaixo uma análise dos parâmetros, utilizando malhas
normalizadas numa caixa unitária com resolução entre 0.014 e 0.028, e quantidade de
vértices entre 800 e 13.000 pontos.
6.2.1
Criação de Spin-images
Uma das etapas mais importantes do procedimento é a criação de spin-images que
apresentem boa descrição da geometria da superfície. Os parâmetros analisados foram
o tamanho dos bins, a resolução da malha e o ângulo suporte.
O tamanho dos bins que resultou em maior sucesso no registro das malhas foi de 2.6
vezes a resolução da malha, para todos os tipos de geometria e topologia. Esse valor é
capaz de fornecer uma boa descrição da superfície, desconsiderando ruídos moderados. A
medida que o nível de ruído vai aumentando e alterando as normais dos vértices, pior a
40
6.2. RESULTADOS
41
descrição das superfícies, pois a formulação das spin-images é muito sensível à direção
das normais.
O segundo parâmetro envolvido na criação das spin-images é a largura da imagem.
Para um tamanho de bin fixo, quanto maior a largura da imagem, maior será a região
da superfície descrita, e mais consistentes as comparações entre os pontos da superfície.
Este valor deve ser definido de acordo com as dimensões da malha, fornecendo a maior
descrição possível da região de sobreposição entre as duas malhas. Para malhas com
resolução entre 0.014 e 0.028 na caixa unitária, resoluções entre 13 × 13 e 18 × 18 pixels
apresentaram bons resultados.
Finalmente, o ângulo suporte é um parâmetro que deve ser definido da mesma maneira
que o parâmetro anterior, garantindo a maior descrição possível da superfície comum
entre as duas malhas. O ângulo suporte que apresentou melhores resultados nas malhas
analisadas foi de 60◦ . A Figura 6.1 exibe dois pontos correspondentes e suas spin-images
similares, criadas de acordo com os parâmetros acima.
(a) Pontos correspondentes em duas malhas capturadas de diferentes pontos
de visão do scanner.
(b) Spin-image do primeiro ponto.
(c) Spin-image do segundo ponto.
Figura 6.1: Pontos correspondentes e suas spin-images.
6.2. RESULTADOS
42
Outro parâmetro analisado foi a quantidade de pontos selecionados nas malhas para
criação de spin-images, levando em consideração a seleção por curvatura local. Esse tópico
exige uma discussão mais detalhada, envolvendo o espaçamento angular entre as visões e
a curvatura das malhas.
Para registrar duas malhas, uma quantidade razoável de pontos selecionados em uma
das malhas deve pertencer ao conjunto de pontos selecionados na outra malha. Usando o
critério de curvatura local, isso implica que as regiões de curvatura mais acentuada devem
pertencer à região de sobreposição das malhas. Esse deve ser o critério utilizado para
determinar o espaçamento angular entre as visões. Quanto maior o espaçamento, maior
será a porção do modelo capturada por duas malhas. Quanto menor o espaçamento,
maior a região de sobreposição entre as duas malhas e, consequentemente, maiores as
chances de sucesso do registro das superfícies. Portanto, o procedimento mais adequado
para a captura das malhas é usar o maior espaçamento possível, de modo que as regiões
de maior curvatura estejam contidas na região de sobreposição, como na Figura 6.2, onde
parte da boca, nariz e um olho está contido nas duas malhas, que tem os pontos de
maior curvatura destacados. Outros aspectos como oclusões também devem ser levadas
em conta na determinação do ângulo de espaçamento.
Figura 6.2: Maior espaçamento possível entre duas visões de um objeto contendo as
regiões de alta curvatura.
Em alguns casos, os pontos de maior curvatura local não são os pontos mais
interessantes para gerar spin images. Se esses pontos estiverem concentrados numa
pequena região da malha, o registro será realizado levando-se em conta apenas essa
pequena região, e consequentemente estará mais sujeito a erros, devido à existência de
ruído. Maior qualidade do registro é obtido quando os pontos estão mais espalhados pelo
6.2. RESULTADOS
43
modelo. Este é um dos critérios utilizado no agrupamento de correspondências, como
descrito no capítulo 3.
Espaçamentos angulares entre 45◦ e 60◦ apresentaram bons resultados na maioria dos
modelos analisados. A partir de 15% do total de pontos das malhas, grande parte das
malhas obtidas com espaçamento angular neste intervalo foram registradas com sucesso.
Valores acima de 15% tornam o processo mais caro computacionalmente e sem grandes
melhorias na qualidade do alinhamento.
6.2.2
Filtragem de Correspondências
Os próximos parâmetros a serem analisados envolvem a filtragem das correspondências.
Os parâmetros analisados foram o threshold de consistência geométrica Tgc , a proporção
das correspondências propGC que devem ser geometricamente consistentes a uma dada
correspondência para que esta passe na filtragem e a área mínima de sobreposição entre
as malhas para que a transformação seja validada.
O valor determinado para o threshold de consistência geométrica Tgc é fundamental
no processo de filtragem. Valores altos não filtram correspondências inconsistentes,
gerando transformações inválidas. Valores muito baixos podem excluir correspondências
consistentes, que são valiosas para o cálculo da transformação. Valores no intervalo entre
0.12 e 0.2 apresentaram os melhores resultados.
Do mesmo modo, é necessário definir corretamente o parâmetro propGC para a
filtragem correta das correspondências. Este threshold apresentou bons resultados entre
20% e 25% da quantidade de correspondências.
Finalmente, a área mínima de sobreposição para validar as transformações deve ser
definida de acordo com a área de sobreposição esperada. Para um espaçamento angular
entre 45◦ e 90◦ , geralmente a quantidade de pontos da região de sobreposição é maior que
40% dos pontos, se a geometria não for muito complexa.
É interessante destacar que o sucesso da etapa de alinhamento automático está
diretamente ligado à captura das malhas pelo scanner, onde deve-se priorizar a obtenção
de regiões de sobreposição com boa geometria para a estimação do alinhamento.
Outro aspecto importante é o custo computacional desta etapa. Em malhas com mais
de cinco mil pontos, o processo torna-se bastante lento. Uma alternativa interessante é
realizar uma simplificação nas malhas, calcular os alinhamentos nas malhas simplificadas,
e aplicar as transformações encontradas nas malhas originais. As malhas que apresentaram
melhores resultados, sem custo computacional muito alto, tinham, em média, três mil
pontos.
Apesar de todas as filtragens e validações aplicadas, existem casos onde o registro é
inconsistente. A Figura 6.3 exibe um exemplo onde as duas malhas apresentam lados
opostos de um objeto que apresentam uma certa simetria, fazendo com que spin-images
6.2. RESULTADOS
44
de diferentes pontos sejam iguais. Como os lados são simétricos, os testes de consistência
geométrica também são validados. Finalmente, a transformação encontrada também
resulta em uma grande região de sobreposição. Porém, o alinhamento é claramente
inconsistente.
Figura 6.3: Registro inconsistente devido à simetria.
6.2.3
Algoritmo ICP
Dadas duas malhas previamente alinhadas usando descritores spin-image, o algoritmo
ICP implementado neste trabalho apresentou ótimos resultados no alinhamento final
das malhas. Para este sucesso, foi fundamental a correta identificação das regiões de
sobreposição que foram utilizadas no registro.
Como já foi descrito no capítulo 4, a detecção das regiões de sobreposição é feita
usando-se um threshold de distância que descarta pares de pontos distantes. Este threshold
apresentou bons resultados com valor definido entre 1 e 1.5 vezes a resolução da malha.
É interessante destacar também que o uso de kd-trees acelerou bastante o alinhamento.
6.2.4
Cálculo de Curvatura e Resolução das Malhas
A técnica utilizada para o cálculo das curvaturas discretas utiliza a vizinhança estrelada
para estimar a curvatura de cada vértice. Em resoluções muito altas, este cálculo pode
não ser interessante devido, por exemplo, à presença de ruídos nas malhas. Neste caso,
os pontos de maior curvatura selecionados não serão os mais interessantes.
A Figura 6.4 exibe duas malhas em diferentes resoluções, onde é possível observar que
a presença de ruído na malha com maior resolução prejudica a seleção correta dos pontos
de maior curvatura.
6.3. EXEMPLOS
(a) Malha com 13.000 pontos.
45
(b) Malha com 3.000 pontos.
Figura 6.4: Malhas em diferentes resoluções com pontos de maior curvatura destacados.
Outro aspecto importante é o registro de malhas com diferentes resoluções. Definindose corretamente o tamanho dos bins das spin-images e sua resolução, o efeito de diferentes
resoluções é normalizado pelas spin-images. Malhas com alta resolução implicam muitos
pontos em cada bin. Malhas com baixa resolução adicionam poucos pontos em cada bin.
Como o tom de cinza de cada pixel é normalizado de acordo com a maior quantidade de
pontos em um único bin, as imagens serão parecidas. A Figura 6.5 exibe duas malhas
com 3.000 pontos e 1.000 pontos respectivamente, e o resultado do alinhamento.
6.3
Exemplos
Esta seção apresenta exemplos de alinhamento e reconstrução de modelos.
Foram
utilizados três objetos.
O primeiro, é um coelho cujas malhas apresentam
aproximadamente 900 vértices. A Figura 6.6 exibe as malhas alinhadas e a Figura 6.7
apresenta o modelo reconstruído com o MeshMerge. Foram utilizadas 10 malhas alinhadas
para a reconstrução total do modelo. É possível observar a presença de alguns buracos no
modelo final. Diversas técnicas podem ser aplicadas para resolver este problema (Curless
& Levoy 1996).
O segundo exemplo é uma cabeça de uma boneca obtida com um scanner. O modelo
foi reconstruído com 5 malhas com aproximadamente 3200 vértices cada uma. A Figura
6.8 mostra as malhas após o alinhamento, e a Figura 6.9 exibe o modelo final.
Finalmente, o terceiro exemplo é um cavalo com geometria distinta das anteriores.
Foram necessárias 9 malhas com aproximadamente 3500 vértices cada uma para que o
modelo completo pudesse ser reconstruído. Assim como no exemplo do coelho, também é
possível observar alguns pequenos buracos no modelo reconstruído. A Figura 6.10 exibe
as malhas alinhadas, e a Figura 6.11 o modelo reconstruído com o MeshMerge.
6.3. EXEMPLOS
46
(a) Malhas com 3.000 pontos e 1.000 pontos.
(b) Malhas registradas.
Figura 6.5: Registro de malhas com diferentes resoluções.
6.3. EXEMPLOS
47
(a) Lado traseiro do coelho.
(b) Lado esquerdo do coelho.
Figura 6.6: Malhas alinhadas do coelho.
Figura 6.7: Modelo reconstruído do coelho.
6.3. EXEMPLOS
48
(a) Lado esquerdo da cabeça.
(b) Lado direito da cabeça.
Figura 6.8: Malhas alinhadas da cabeça.
(a) Lado esquerdo da cabeça.
(b) Lado direito da cabeça.
Figura 6.9: Modelo reconstruído da cabeça.
6.3. EXEMPLOS
49
(a) Lado esquerdo do cavalo.
(b) Frente do cavalo.
Figura 6.10: Malhas alinhadas do cavalo.
Figura 6.11: Modelo reconstruído do cavalo.
Capítulo 7
Conclusão e Trabalhos Futuros
Este trabalho apresentou um procedimento para alinhamento automático e reconstrução
de modelos a partir de malhas capturadas de scanners. Utilizando o conceito de spin
images, o método utilizado é capaz de suprir o principal requisito do algoritmo ICP: uma
estimativa inicial do alinhamento.
O procedimento é baseado na integração de três módulos. O primeiro módulo é
responsável pelo cálculo da estimativa inicial do alinhamento, usando o conceito de spinimages. O segundo módulo aplica o algoritmo ICP para um refinamento do alinhamento.
Esses primeiros módulos foram implementados neste trabalho. O terceiro módulo realiza
a reconstrução do modelo a partir das malhas alinhadas, usando um pacote chamado
VRIP.
De modo geral, o alinhamento automático inicial apresentou bons resultados nos
testes realizados com malhas dentro dos parâmetros definidos neste trabalho, inclusive
utilizando-se spin-images com textura, que aparentemente apresentaram pequenas
melhoras na qualidade do registro. O sucesso do algoritmo ICP foi consequente da
qualidade do alinhamento inicial. Finalmente, o VRIP foi capaz de realizar com sucesso
a reconstrução dos modelos a partir das malhas registradas.
Segue abaixo uma lista de melhorias que poderiam ser aplicadas ao método apresentado
em trabalhos futuros:
• Grafo de alinhamento: Atualmente, dado um conjunto de n malhas, o registro
é testado e efetuado duas a duas, resultando num algoritmo quadrático. A
implementação de uma estrutura de grafo pode otimizar esse processo.
• Análise de parâmetros: Apesar de apresentar bons resultados com os parâmetros
definidos neste trabalho, um estudo mais aprofundado dos parâmetros das spinimages pode otimizar o processo.
• Seleção por curvatura local da superfície: Como já foi citado anteriormente, a técnica
utilizada para cálculo da curvatura discreta apresenta deficiências, principalmente
50
51
em malhas com alta resolução. A aplicação de outras técnicas de curvatura pode
melhorar o processo de seleção de pontos.
• Análise das spin-images com textura: Uma análise mais detalhada das spin-images
com textura é interessante, principalmente para realizar registro de superfícies
simétricas, como vasos, por exemplo (Figura 7.1).
• Variantes do algoritmo ICP: A implementação de variantes do algoritmo ICP pode
implicar melhores resultados na qualidade do registro das superfícies.
Figura 7.1: Modelo de um vaso simétrico.
Referências Bibliográficas
Arun, K. S., Huang, T. S. & Blostein, S. D. (1987), ‘Least-squares fitting of two 3-d point
sets’, IEEE Trans. Pattern Anal. Mach. Intell. 9(5), 698–700.
Bentley, J. L. (1975), ‘Multidimensional binary search trees used for associative searching’,
Commun. ACM 18(9), 509–517.
Besl, P. J. & Mckay, N. D. (1992), ‘A method for registration of 3-d shapes’, IEEE
Transactions on Pattern Analysis and Machine Intelligence 14(2), 239–256.
Blais, G. & Levine, M. D. (1995), ‘Registering multiview range data to create 3d computer
objects’, IEEE Trans. Pattern Anal. Mach. Intell. 17(8), 820–824.
Brusco, N., Andreetto, M., Giorgi, A. & Cortelazzo, G. M. (2005), 3d registration
by textured spin-images, in ‘3DIM ’05: Proceedings of the Fifth International
Conference on 3-D Digital Imaging and Modeling’, IEEE Computer Society,
Washington, DC, USA, pp. 262–269.
Carmo, M. P. (2005), Geometria Diferencial de Curvas e Superfícies, 1 edn, SBM, Rio de
Janeiro.
Chen, Y. & Medioni, G. (1992), ‘Object modelling by registration of multiple range
images’, Image Vision Comput. 10(3), 145–155.
Curless, B. & Levoy, M. (1996), ‘A volumetric method for building complex models from
range images’, Computer Graphics 30(Annual Conference Series), 303–312.
Devore, J. L. (1999), Probability and Statistics for Engineering and Sciences, 5 edn,
Duxbury.
Eggert, D. W., Lorusso, A. & Fisher, R. B. (1997), ‘Estimating 3-d rigid body
transformations: a comparison of four major algorithms’, Mach. Vision Appl. 9(56), 272–290.
Godin, G., Rioux, M. & Baribeau, R. (1994), Three-dimensional registration using range
and intensity information, in S. F. El-Hakim, ed., ‘Proc. SPIE Vol. 2350, p. 279-290,
Videometrics III, Sabry F. El-Hakim; Ed.’, pp. 279–290.
52
REFERÊNCIAS BIBLIOGRÁFICAS
53
Horn, B. (1987), ‘Closed-form solution of absolute orientation using unit quaternions’, J.
Optical Soc. Am 4, 629–642.
Horn, B. K. P., Hilden, H. M. & Negahdaripour, S. (1988), ‘Closed-form solution of
absolute orientation using orthonormal matrices’, Journal of the Optical Society of
America A 5, 1127–1135.
Johnson, A. (1997), Spin-Images: A Representation for 3-D Surface Matching, PhD thesis,
Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
Levenberg, K. (1944), ‘A method for the solution of certain problems in least squares’,
Quart. Appl. Math 2, 164–168.
Levoy, M., Pulli, K., Curless, B., Rusinkiewicz, S., Koller, D., Pereira, L., Ginzton, M.,
Anderson, S., Davis, J., Ginsberg, J., Shade, J. & Fulk, D. (2000), The digital
michelangelo project: 3d scanning of large statues, in ‘SIGGRAPH ’00: Proceedings
of the 27th annual conference on Computer graphics and interactive techniques’,
ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, pp. 131–144.
Lorensen, W. E. & Cline, H. E. (1987), Marching cubes: A high resolution 3d surface
construction algorithm, in ‘SIGGRAPH ’87: Proceedings of the 14th annual
conference on Computer graphics and interactive techniques’, ACM Press, New York,
NY, USA, pp. 163–169.
Masuda, T., Sakaue, K. & Yokoya, N. (1996), Registration and integration of multiple
range images for 3-d model construction, in ‘ICPR ’96: Proceedings of the 1996
International Conference on Pattern Recognition (ICPR ’96) Volume I’, IEEE
Computer Society, Washington, DC, USA, p. 879.
Meyer, M., Desbrun, M., Schröder, P. & Barr, A. H. (2003), Discrete differentialgeometry operators for triangulated 2-manifolds, in H.-C. Hege & K. Polthier, eds,
‘Visualization and Mathematics III’, Springer-Verlag, Heidelberg, pp. 35–57.
Montani, C., Scateni, R. & Scopigno, R. (1994), ‘A modified look-up table for implicit
disambiguation of marching cubes’, The Visual Computer 10(6), 353–355.
Neugebauer, P. J. (1997), Geometrical cloning of 3d objects via simultaneous registration
of multiple range images, in ‘SMA ’97: Proceedings of the 1997 International
Conference on Shape Modeling and Applications (SMA ’97)’, IEEE Computer
Society, Washington, DC, USA, p. 130.
Newman, T. S. & Yi, H. (2006), ‘A survey of the marching cubes algorithm’, Computers
& Graphics 30(5), 854–879.
REFERÊNCIAS BIBLIOGRÁFICAS
54
Pulli, K. (1999), ‘Multiview registration for large data sets’, 3dim 00, 0160.
Rocchini, C., Cignoni, P., Montani, C. & Scopigno, R. (2004), ‘Vclab 3d scanning
tools range maps merge: Meshmerge v.2.0’, http://vcg.isti.cnr.it/joomla/
index.php?option=com_content&task=view&id=107&Itemid=48. Última consulta
em Fevereiro de 2007.
Rusinkiewicz, S. & Levoy, M. (2001), ‘Efficient variants of the icp algorithm’, 3dim 00, 145.
Simon, D. (1996), Fast and Accurate Shape-Based Registration, PhD thesis, Robotics
Institute, Carnegie Mellon University, Pittsburgh, PA.
Turk, G. & Levoy, M. (1994), Zippered polygon meshes from range images, in
‘SIGGRAPH ’94: Proceedings of the 21st annual conference on Computer graphics
and interactive techniques’, ACM Press, New York, NY, USA, pp. 311–318.
Walker, M. W., Shao, L. & Volz, R. A. (1991), ‘Estimating 3-d location parameters using
dual number quaternions’, CVGIP: Image Underst. 54(3), 358–367.
