Aplicação de contornos ativos em modelagem baseada em imagenslivros01.livrosgratis.com.br/cp088886.pdf · Este trabalho propõe a execução do projeto de uma ferramenta de auxílio

Aplicação de contornos ativos emmodelagem baseada em imagens

Kátia Luciene Scorsolini Alexandre

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

SERVIÇO DE PÓS-GRADUAÇÃO DO ICMC-USP

Data de Depósito: 21/11/2005

Assinatura:

Aplicação de contornos ativos em modelagembaseada em imagens

Kátia Luciene Scorsolini Alexandre

Orientador: Prof. Dr. João do Espírito Santo Batista Neto

Dissertação apresentada ao Instituto de Ciências Matemáticas e de Computação

- ICMC/USP, como parte dos requisitos para obtenção do título de Mestre em

Ciências de Computação e Matemática Computacional.

USP - São Carlos

Novembro/2005

Conteúdo

1 Introdução 1

1.1 Caracterização do problema . . . . . . . . . . . . . . . . . . . . . . . . . . . .1

1.2 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Organização do texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2

2 Modelagem Baseada em Imagens 3

2.1 Técnicas de modelagem baseada em imagens . . . . . . . . . . . . . . . . . . .4

2.1.1 Técnicas puras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

2.1.2 Técnicas híbridas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Considerações finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14

3 Canoma 16

3.1 A ferramenta Canoma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17


4 Contornos Ativos 21

4.1 Conceito de contornos ativos . . . . . . . . . . . . . . . . . . . . . . . . . . . .22

4.1.1 Modelos paramétricos . . . . . . . . . . . . . . . . . . . . . . . . . . .22

i

4.1.2 Modelos geométricos . . . . . . . . . . . . . . . . . . . . . . . . . . . .35


5 Descrição do Método 41

5.1 Identificação do contorno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42

5.2 Detecção dos vértices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45

5.2.1 Vértices visíveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45

5.2.2 Vértices ocultos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49


6 Resultados 56

6.1 Parâmetros internos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .58

6.2 Parâmetros externos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59


7 Conclusões e Trabalhos Futuros 66

Referências Bibliográficas 67

ii

Lista de Figuras

2.1 Classificação das técnicasIBM: abordagens baseada em geometria, híbrida e baseada

em imagem (Debevec, 1996). . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

2.2 Utilização do softwarePhoto3Dpara o modelamento a partir de uma fotografia

(Apollo Software, 2004). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.3 a) Modelo em triangulação doDowning College Library; b) modelo 3D com tex-

tura e c) sua representação VRML utilizando o softwarePhotoBuilder(Cipolla

et al., 1999). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.4 Exemplos de utilização do softwarePhotoModeler: a) reconstrução de acidentes

automobilísticos; b) reconstrução de crimes e c) documentação de sítios e artefatos

históricos (Eos System Inc., 2004). . . . . . . . . . . . . . . . . . . . . . . . . .7

2.5 Aplicação da técnicatour into the picturesobre a imagem de uma ruela: a) definição

do ponto de fuga, de uma região retangular e das linhas radiais que partem do

ponto de fuga; b) imagem dividida em cinco regiões e c) a imagem renderizada de

um novo ponto de vista (Johnson, 2001). . . . . . . . . . . . . . . . . . . . . . .8

2.6 Ponto de fuga e linha de fuga (adaptada de (Kang et al., 2001)). . . . . . . . . . .9

iii

2.7 a) Imagem 2D dividida em duas regiões pela linha de fuga; b) modelo 3D e c)

coordenadas dos vértices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10

2.8 Reconstrução do modelo 3D da torre do relógio da Universidade de Berkeley uti-

lizando a abordagem algorítmica não-linear do sistemaFaçade: a) imagem origi-

nal com as margens definidas pelo usuário; b) modelo criado através de primitivas;

c) projeção do modelo na fotografia e d) a imagem renderizada (Debevec, 2004).12

2.9 Aplicação da técnicavoxel coloringem um dinossauro de brinquedo: a) imagem

original; b) e c) duas visões do modelo reconstruído a partir de 21 fotografias do

objeto (Seitz and Dyer, 1997). . . . . . . . . . . . . . . . . . . . . . . . . . . .14

3.1 Interface do software Canoma: um conjunto de primitivas 3D são utilizadas na

criação de um modelo aproximado do ambiente real. . . . . . . . . . . . . . . .17

3.2 Passos para a modelagem no Canoma: a) escolha de uma primitiva 3D; b) e c)

ajuste (matching) do aramado à geometria do objeto na cena; d) definição do plano

de referência; e) e f) visualizações do modelo. . . . . . . . . . . . . . . . . . . .20

4.1 Conjunto de pontos iniciais definidos pelo usuário na imagem original (Bianchi,

2003) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.2 Pontov(si) e seus vizinhos (vizinhança 3x3): a energia é calculada para cada

pontonj , onde j varia de 1 a 9. . . . . . . . . . . . . . . . . . . . . . . . . . . .25

4.3 a) Campo vetorial do modelo tradicional desnakee b) do modelo de potenciais de

distância. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26

4.4 Comportamento dos vetores em uma região côncava usando em a) o modelo de

potenciais de distância e b) o modelo. . . . . . . . . . . . . . . . . . . . . . . .27

4.5 O modeloballoon: a) snakecom dimensão menor que a da estrutura e posição

inicial distante dos contornos; b) sua posição após 100 iterações e c) sua posição

após 500 iterações (Pimentel, 2000). . . . . . . . . . . . . . . . . . . . . . . . .28

4.6 Campo doGVF para um objeto concâvo em forma de U: os vetores atraem o

contorno em direção à borda do objeto (Xu and Prince, 2004). . . . . . . . . . .29

iv

4.7 Segmentação de imagem de ressonância magnética utilizando o modeloGVF: a)

snakeinicializada externamente à estrutura e b) sua posição final (Pimentel, 2000).32

4.8 Aplicação do modeloGVFem objeto tridimensional: a) isosuperfície de um objeto

3D; b) posição dos planos A e B; c) e d) projeções da superfície nos respectivos

planos; e) configuração inicial da superfície deformável usandoGVF; f) posição

da superfície após 10; g) 40 e h) 100 iterações (Xu and Prince, 2000). . . . . . .32

4.9 Malha resultante de decomposição simplicial (triangulação) do domínio. . . . . .33

4.10 Comportamento da função característica: a atribuição de símbolos aos vértices é

dependente da evolução pré-definida dasnake. . . . . . . . . . . . . . . . . . . . 33

4.11 Projeção dos pontos do contorno inicial na grade: nós externos definidos como

‘queimados’ após prévia definição da evolução dasnake. . . . . . . . . . . . . . 34

4.12 Exemplo da evolução dasnakedescrita em 3 momentos: a) inicial; b) inter-

mediária e c) final (Machado et al., 2002). . . . . . . . . . . . . . . . . . . . . .35

4.13 Curva inicial em preto separando a imagem em duas regiões. . . . . . . . . . . .36

4.14 A frente propagante e a funçãolevel set: a snakeé definida pela intersecção da

superfície bi-dimensional com o plano xy (Sethian, 2004). . . . . . . . . . . . .37

4.15 SpliteMerge: o contorno inicial é formado por duas curvas que se unem conforme

crescem (Sethian, 2004). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38

4.16 Contorno projetado em uma malha: cada vértice armazena o tempo T em que foi

atingido pela frente propagante. . . . . . . . . . . . . . . . . . . . . . . . . . .38

4.17 A Superfície de Tempo de Chegada, fornecida pela função T(x,y), intercepta o

plano xy exatamente onde inicia-se a curva (Sethian, 2004). . . . . . . . . . . . .39

5.1 Framework do projeto: a) contorno inicial definido pelo usuário; b) contorno ex-

terno do objeto identificado após aplicação da técnica de contornos ativos e c)

localização dos vértices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41

v

5.2 Snake: obtenção do contorno do objeto de interesse. a) Imagem original a partir

da qual gera-se o mapa de arestas que será utilizado para o cálculo de b), o campo

GVF. Em c) o contorno externo do objeto identificado após aplicação do contorno

ativo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.3 Máscaras do operador de Sobel utilizadas para detectar a derivada de primeira

ordem a)na horizontal (Gx) e b)na vertical (Gy); c)filtro Laplaciano de vizinhança 4.43

5.4 Máscara do operador GDDI com vizinhança 7x7. . . . . . . . . . . . . . . . . .44

5.5 Campo de força após aplicação doGVF. . . . . . . . . . . . . . . . . . . . . . . 45

5.6 Processo de detecção dos vértices: a) o contorno encontrado pelasnakes; b) de-

tecção dos vértices visíveis (1, 2, 3, 4, 5, 6 e 7) e c) vértice oculto (8) estimado a

partir das coordenadas dos vértices visíveis. . . . . . . . . . . . . . . . . . . . .46

5.7 Processo de seleção de um vértice candidato para: a) uma amostragem de 10 pon-

tos e b) uma variação angular de15o. . . . . . . . . . . . . . . . . . . . . . . . . 47

5.8 Processo de seleção de um vértice candidato localizado fora da extremidade da reta.48

5.9 Vértices de um cubo e suas adjacências: os vértices 3 e 4 possuem três vértices

adjacentes, enquanto 1, 2, 5 e 6 possuem, inicialmente, conexões com somente

dois vértices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50

5.10 Cálculo dos pontos de fuga: as linhas tracejadas representam um ponto de fuga

finito (v) computado a partir das arestas-----→31 e -----→42, enquanto as linhas pontilhadas

representam um ponto de fuga infinito (u), computado a partir das arestas-----→35 e -----→46. 50

5.11 Projeção dos vértices nos pontos de fuga encontrados. . . . . . . . . . . . . . . .51

5.12 Computando os vértices ocultos. . . . . . . . . . . . . . . . . . . . . . . . . . .52

5.13 Cálculo do ponto de fuga para uma pirâmide: prolongando-se as arestas, o ponto

de fuga é representado em a) pelo vértice 1 e em b) pelo vértice 3. . . . . . . . .52

5.14 Reconstrução de uma pirâmide de base triangular. . . . . . . . . . . . . . . . . .53

5.15 Reconstrução de uma pirâmide de base quadrangular. . . . . . . . . . . . . . . .53

6.1 Interface do programa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .57

vi

6.2 a) Imagem original; b) contorno inicial definido pelo usuário e resultados dasnake

em c) após 6 iterações e em d) após 4 iterações. Um alto valor para alpha em d)

inibiu a expansão do contorno, resultando em uma convergência ruim. . . . . . .60

6.3 a) Imagem original; b) parâmetros utilizados na detecção dos vértices visíveis do

objeto; c) vértices visíveis detectados e d) localização do vértice oculto para uma

pirâmide de base quadrangular. . . . . . . . . . . . . . . . . . . . . . . . . . . .60

6.4 a) Parâmetros utilizados na detecção do contorno de um cubo; b) imagem original;

c) contorno inicial definido pelo usuário e resultado dasnakeobtidos em: d) 2

iterações, após aplicação do filtro Sobel; e) 6 iterações, após aplicação do filtro

Laplaciano e f) 5 iterações, após aplicação do filtro GDDI. . . . . . . . . . . . .61

6.5 a) Imagem original; b) parâmetros utilizados para a detecção dos vértices visíveis

do objeto; c) vértices visíveis detectados e d) estimativas das localizações dos

vértices ocultos (7 e 8). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62

6.6 a) Contorno inicial definido pelo usuário na imagem original; b) parâmetros uti-

lizados na detecção do contorno; c) posição final dasnake; d) parâmetros utiliza-

dos na detecção dos vértices visíveis do objeto; e) vértices visíveis localizados

pela ferramenta; f) vértices de grau 1 e 2 projetados nos pontos de fuga A e B e g)

identificação dos vértices ocultos. . . . . . . . . . . . . . . . . . . . . . . . . .62

6.7 a) Cálculo do contorno de um hexaedro e b) cálculo dos vértices do objeto. . . .63

6.8 a) Imagem 6.5a binarizada; Transformada de Hough para limiares b) 5; c) 20 e d)

30. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

vii

Agradecimentos

À Deus, por iluminar meus caminhos e guiar meus passos na conquista deste sonho.

Aos meus pais, Osmar e Kátia, meu dois amores, pelo apoio, paciência, amor e presença

constantes em minha vida.

Ao meu namorado Denis que, em todos os momentos, esteve ao meu lado e aos meus amados

irmãos e companheiros, Erik e Willian.

Ao meu orientador João do Espiríto Santo Batista Neto pelo inestimável auxílio, imensa

paciência e confiança no meu trabalho.

À todas as pessoas com quem pude conviver durante esses anos, às amizades que conquistei, que

compartilharam dos meus ideais e me incentivaram a prosseguir.

À minha tia Soraia pelo abrigo e carinho de sempre.

Existem outras pessoas não citadas aqui, algumas por não existirem palavras para descrever o

quão especiais são para mim!

viii

Resumo

Técnicas de modelagem baseada em imagens têm recebido considerável atenção da comu-

nidade de visualização computacional devido ao potencial de criar cenas realistas a partir de

um pequeno conjunto de imagens bi-dimensionais. Entretanto, a qualidade dos modelos gerados

pelas ferramentas atualmente disponíveis é extremamente dependente de entradas fornecidas pelo

usuário. Este trabalho propõe a execução do projeto de uma ferramenta de auxílio para sistemas

de modelagem baseada em imagens que utiliza o conceito de contornos ativos para aumentar o

grau de automação do processo de localização do contorno do objeto presente na fotografia, que

servirá de guia para a posterior localização dos vértices desse objeto. Através desta abordagem,

figuras geométricas mais simples, como pirâmides e hexaedros, puderam ser reconstruídas após a

recuperação das coordenadas de seus vértices.

.

Abstract

Image Based Modelling techniques has received considerable attention from the computer

vision community due to the potential to create realistic scenes from some bi-dimensional images.

However, the model’s quality generated by the tools available nowadays is extremely dependent

on entries provided by the user. This work proposes the execution of a help tool project for image

based modelling systems that uses the active contours concept to increase the process automation

degree of locating the contour of an object in the image, which will guide the vertex location

process of this object. Through this approach, simple geometric figures, as pyramids and squares,

could be reconstructed after the vertex coordinates recuperation.

CAPÍTULO

1

Introdução

1.1 Caracterização do problema

As técnicas de modelagem baseada em imagens procuram, através de um conjunto de ima-

gens, extrair informações a partir das quais seja possível reconstruir uma cena sob investigação.

Essas informações são compostas de vértices, arestas e/ou curvas que, idealmente, poderiam ser

extraídas de forma automática, por meio de técnicas de segmentação de imagens.

No entanto, o que se observa nas ferramentas atualmente disponíveis é a existência de um pro-

cesso bastante interativo e fortemente dependente do usuário para a identificação e posicionamento

das informações geométricas necessárias à reconstrução dos objetos da cena.

A ferramenta Canoma provê um exemplo claro dessa grande dependência. Durante a criação

do modelo, o usuário deve definir as primitivas (wire framesou aramados) que compõem a cena

e manualmente posicionar os vértices dos aramados sobre pontos correspondentes dos objetos

de interesse na imagem, de forma a determinar, com a maior precisão possível, os tamanhos e

posições dos aramados, a fim de que a modelagem resultante seja fiel aos objetos presentes em

1

Introdução

cena.

Esse processo manual, além de tedioso (principalmente se considerarmos cenas complexas

ou repetitivas), faz com que a precisão da modelagem esteja associada à exatidão do usuário no

posicionamento das primitivas.

1.2 Objetivo

Levando-se em conta a dependência do usuário durante a construção do modelo, um sistema

de modelagem baseada em imagens cujo processo de ajuste do aramado seja feito de maneira au-

tomática adquire uma relevância considerável, visto que essa automação proporciona ao resultado

final uma qualidade mais satisfatória ao aumentar a precisão do modelo.

Além de contribuir com um modelo mais preciso, tal funcionalidade facilitaria a utilização da

ferramenta por indivíduos com dificuldades motoras. Outro benefício do processo automático é o

fato de dispensar o uso de hardware específico para entrada de informações gráficas.

Uma possível abordagem para a automação do processo é a utilização de contornos ativos a fim

de realizar a detecção automática de bordas dos objetos de interesse na imagem. O usuário deverá,

deste modo, definir um contorno próximo ao objeto da cena que, através do uso de contornos

ativos, será automaticamente ajustado de tal forma que coincida com a borda do objeto desejado.

1.3 Organização do texto

Este trabalho está estruturado em seis capítulos. O segundo capítulo conceitua algumas das

principais técnicas de modelagem baseada em imagens. O capítulo 3 aborda especificamente a

técnica híbrida de modelagem ao demonstrar a interface da ferramenta Canoma e os procedimen-

tos necessários para a criação de um modelo baseado em uma imagem bi-dimensional. O quarto

capítulo apresenta o conceito e alguns modelos de contornos ativos. No capítulo 5 é demonstrada

a metodologia de trabalho utilizada para a construção da ferramenta, abordando as técnicas empre-

gadas e discorrendo sobre a idéia proposta. Finalmente, o capítulo 6 apresenta alguns resultados

obtidos através da aplicação da técnica implementada.

2

CAPÍTULO

2

Modelagem Baseada em Imagens

A transformação de cenas reais em um modelo computacional tridimensional a partir de fo-

tografias, ou seja, a utilização de imagens para direcionar a reconstrução de modelos geométricos

tridimensionais com o potencial de simplificar a representação de cenas com alto grau de com-

plexidade, é denominado Modelagem baseada em Imagens (Image-based Modeling- IBM).

Recentemente, essas técnicas têm desfrutado de considerável atenção na comunidade de visu-

alização computacional em virtude da capacidade de criação de imagens bastante realistas. Um

dos seus maiores benefícios é a habilidade em capturar detalhes do mundo real (Foley, 2000).

As seções subseqüentes descreverão algumas técnicas de modelagem baseada em imagens,

discutindo seus princípios básicos, suas potencialidades, limitações e exemplos de aplicação. Para

isso, é utilizada a classificação apresentada por Oliveira (Oliveira, 2002), onde as técnicas de

modelagem baseada em imagens são divididas em puras e híbridas, segundo a quantidade de

informação geométrica utilizada para a reconstrução de modelos tridimensionais.

3


2.1 Técnicas de modelagem baseada em imagens

Devido ao foto-realismo dos seus modelos, as técnicas de modelagem baseadas em imagens

(IBM) têm ganhado maior expressão. Essas técnicas apresentam a imagem como principal ele-

mento condutor do processo de reconstrução de modelos geométricos tridimensionais (Burschka

et al., 2003).

A figura 2.1 ilustra uma classificação das técnicas deIBM proposta por Debevec (Debevec,

1996). Nessa classificação, abordagens híbridas são definidas como a combinação de abordagens

baseada em imagem e baseada em geometria para modelar e renderizar arquiteturas a partir de

fotografias.

Figura 2.1: Classificação das técnicasIBM: abordagens baseada em geometria, híbrida e baseada em ima-gem (Debevec, 1996).

Enquanto a abordagem baseada em geometria delega maior responsabilidade ao usuário, a

abordagem baseada em imagem considera o computador o maior responsável pela tarefa. A abor-

dagem híbrida, segundo Debevec, divide a tarefa em dois estágios, um interativo e um automati-

zado, unindo as forças de usuário e computador a fim de produzir os melhores modelos possíveis

utilizando o menor número de fotografias.

4


A tabela 2.1 ilustra uma outra possível classificação das técnicas deIBM existente na lite-

ratura, apresentada por Oliveira (Oliveira, 2002), onde as técnicas são posicionadas em um espec-

tro imagem-geometria e a classificação entre abordagens exclusivamente puras ou geométricas se

dá pela quantidade de informação geométrica requerida no processo de modelamento.

Imagens Híbridas Geometria<—————————————————————————————————>

Puras

•Métodos de projeção •Passeio pela imagem •Otimização não-linear•Coloração de Voxel

Tabela 2.1: Técnicas de modelagem baseadas em imagem no espectro imagem - geometria (adaptada de(Oliveira, 2002)).

Este trabalho adotará, para a descrição de algumas técnicas, a classificação sugerida por

Oliveira.

2.1.1 Técnicas puras

Muitas técnicas de modelagem baseada em imagens dão maior enfoque à reconstrução de

modelos arquitetônicos, como edifícios, catedrais, entre outros. Isso se deve à abundância de

superfícies planas e de linhas paralelas e perpendiculares que podem ser exploradas para tornar a

reconstrução consideravelmente mais simples.

As técnicas puras de modelagem baseadas em imagens reconstroem modelos arquitetônicos

diretamente do conjunto de imagens de entrada, em geral, fotografias.

Métodos de projeção

Essas técnicas exploram propriedades de projeção da cena para reconstruir modelos geométri-

cos diretamente de um conjunto de fotografias. A integridade desses modelos depende da super-

fície coberta pelas imagens. Segundo Oliveira (Oliveira, 2002), todas as abordagens de projeção

são restritas à reconstrução de superfícies planas devido à dificuldade de se reconstruir formas

5


arbitrárias e à simplicidade de transformações de projeções planares.

Inicialmente, deve-se realizar a calibragem da câmera fotográfica, que determina a relação

espacial entre o mundo e a câmera com a qual é obtida a foto. Esse processo envolve, por exemplo,

cálculos de distância focal e de razão de aspecto, podendo ser feito através do uso de pontos de

fuga. Três pontos de fuga correspondentes a três conjuntos ortogonais de linhas paralelas fornecem

informação suficiente para a calibragem da câmera.

Após a calibragem, passa-se para a fase de criação do modelo 3D utilizando a fotografia como

imagem de fundo. No softwarePhoto3D(Apollo Software, 2004), um cursor tridimensional é

utilizado para encaixar e rotacionar recortes planos ao fundo da fotografia.

Figura 2.2: Utilização do softwarePhoto3Dpara o modelamento a partir de uma fotografia (Apollo Soft-ware, 2004).

Na figura 2.2, o cursor 3D consiste de quatro linhas e é dado pelo formato retangular em

destaque. Embora seja uma ferramenta simples, o uso de múltiplas imagens na construção de um

modelo pode provocar a ocorrência de erros. Como a construção é feita de forma incremental, se

a cada passo é introduzido um novo erro, o modelo resultante torna-se inconsistente.

Outro sistema que utiliza métodos de projeção sobre imagens fotográficas é oPhotoBuilder

(Cipolla et al., 1999). Nesse sistema, um modelowire-frameé reconstruído utilizando coordenadas

em três dimensões determinadas por triangulação. Para deixar o modelo mais realista, acrescenta-

se a textura oriunda das fotografias originais, conforme mostra a figura 2.3.

Após o desenvolvimento de um modelo simples da cena, é possível aumentar sua qualidade.

Isso pode ser feito automaticamente comparando-se a reconstrução e a textura mapeada no modelo

com a imagem original, a fim de determinar onde existem erros significativos no modelo.

Sistemas dessa natureza têm sido utilizados também na reconstrução de modelos de cenas

de crimes, de acidentes automobilísticos e de artefatos e sítios arqueológicos (figura 2.4). Um

6


(a) (b) (c)

Figura 2.3: a) Modelo em triangulação doDowning College Library; b) modelo 3D com textura e c) suarepresentação VRML utilizando o softwarePhotoBuilder(Cipolla et al., 1999).

exemplo é oPhotoModeler(Eos System Inc., 2004), que é capaz de realizar, além da reconstrução

do modelo, cálculos de medidas.

(a) (b) (c)

Figura 2.4: Exemplos de utilização do softwarePhotoModeler: a) reconstrução de acidentes automobilísti-cos; b) reconstrução de crimes e c) documentação de sítios e artefatos históricos (Eos System Inc., 2004).

2.1.2 Técnicas híbridas

Ao contrário das técnicas puras, as técnicas híbridas de modelagem baseada em imagens geram

modelos arquitetônicos através da aplicação de alguns modelos geométricos para guiar o processo

de reconstrução.

A seguir, serão apresentadas algumas dessas técnicas.

7


Passeio pela imagem (tour into the picture - TIP)

Considerada a mais simples das técnicas de modelagem baseada em imagens, aTIP gera, a

partir de uma única figura 2D, um modelo de cena extremamente simplificado consistindo apenas

de poucos polígonos mapeados com textura (Horry et al., 1997). A intenção não é construir um

modelo 3D preciso da cena, mas criar uma animação da cena sem a necessidade de múltiplas

fotografias.

O primeiroTIP, proposto por Horry (Horry et al., 1997), utiliza uma abordagem de modelagem

interativa denominada ‘spidery mesh’, devido à semelhança com uma teia de aranha.

Para criar um modelo, o usuário deve inicialmente, dividir a cena em objetos de primeiro

e segundo planos. Depois de removidos os objetos de primeiro plano, as lacunas deixadas na

imagem de segundo plano são preenchidas com as cores dospixelsvizinhos.

O usuário deve então especificar um ponto de fuga e uma região retangular na imagem, de-

vendo, em seguida, dividir essa imagem em, no máximo, cinco regiões (figura 2.5a). Uma dessas

regiões corresponde a um retângulo. Demais regiões são definidas por segmentos de linhas ra-

diais (spidery mesh), que se iniciam nas arestas do retângulo e estendem-se ao longo da direção

definida pelo ponto de fuga. Essas cinco regiões representam as faces de um paralelepípedo a

serem renderizadas como polígonos mapeados com textura (figura 2.5b).

(a) (b) (c)

Figura 2.5: Aplicação da técnicatour into the picturesobre a imagem de uma ruela: a) definição do pontode fuga, de uma região retangular e das linhas radiais que partem do ponto de fuga; b) imagem dividida em

cinco regiões e c) a imagem renderizada de um novo ponto de vista (Johnson, 2001).

8


Recuperar as coordenadas 3D para os vértices dessas faces é simples, pelo fato de cada duas

faces adjacentes serem perpendiculares. Variando a posição e orientação de uma câmera virtual,

consegue-se obter novas cenas a partir da original com diferentes ângulos de visão (figura 2.5c).

Os objetos de primeiro plano são re-introduzidos na cena como uma série de polígonos mapeados

com textura, cujas posições 3D são calculadas em relação ao modelo de segundo plano.

Percebe-se que a nova cena transmite a sensação do usuário estar navegando pela mesma, daí

a técnicaTIP ser utilizada para criar animações do tipofly-througha partir de fotografias, sem

utilizar múltiplas imagens bi-dimensionais de uma cena.

Visando solucionar problemas inerentes doTIP – spidery mesh, tais como a difícil generali-

zação para outros tipos de imagens (panorâmicas, por exemplo) e a dificuldade em se definir um

ponto de fuga quando a cena possui mais de um ponto de fuga ou não possui um bem definido,

foi proposta uma nova abordagem para a técnicaTIP, baseada em linhas de fuga (vanishing lines)

(Kang et al., 2001) ao invés de ponto de fuga. Essa abordagem é considerada mais simples e mais

geral.

Figura 2.6: Ponto de fuga e linha de fuga (adaptada de (Kang et al., 2001)).

Na figura 2.6 as linhas paralelas A e B (no plano objeto) aparecem na imagem como A’ e B’,

cuja intersecção define o ponto de fuga. A linha de fuga, paralela ao plano objeto e paralela à A e

9


à B, representa a intersecção do plano da imagem com o plano do horizonte. O horizonte visto em

uma paisagem, por exemplo, é uma linha de fuga formada pelas linhas paralelas no plano objeto.

A linha de fuga distingue a região na imagem que corresponde ao plano do objeto da região

correspondente ao espaço acima dele. Na figura 2.7a, os vértices de 1 a 4 representam os quatro

cantos da imagem, enquanto os vértices 5 e 6 representam a intersecção da linha de fuga com a

margem da imagem.

(a) (b)

(c)

Figura 2.7: a) Imagem 2D dividida em duas regiões pela linha de fuga; b) modelo 3D e c) coordenadas dosvértices.

Na figura 2.7c as coordenadas dos vértices 1’ a 6’ são computadas a partir dos vértices 1 a 6

(os vértices 2 e 4 coincidem com 2’ e 4’) para serem utilizados na construção do modelo da cena

(figura 2.7b) e para renderização.

10


Abordagem de otimização não-linear (non-linear optimization approaches)

Debevec propôs uma abordagem híbrida de modelagem baseada em imagens, implementada

no sistemaFaçade(Debevec et al., 1996). Essa abordagem utiliza algoritmos de otimização não-

linear para reconstruir modelos tridimensionais texturizados de elementos arquitetônicos a partir

de um conjunto esparso de fotografias e possui dois componentes: um método de modelagem

fotogramétrico interativo (que recupera a geometria básica da cena explorando restrições que são

características da arquitetura) e um algoritmo estéreo baseado no modelo para realizar compara-

ções (que recupera o desvio entre a cena e o modelo básico). A renderização utiliza um mapea-

mento de textura dependente da localização da câmera, ou seja, do ponto de vista do observador.

Segundo Debevec (Debevec, 1996), a recuperação do modelo torna-se mais simples quando

as imagens são obtidas a partir de câmeras calibradas.

A posição da câmera no espaço, contudo, não precisa, necessariamente, ser conhecida. De

acordo com a fotogrametria, ou seja, a ciência e tecnologia de se obter informações confiáveis

através de imagens (Brito and Coelho, 2002), é matematicamente possível deduzir a localização de

pontos ou a posição original da câmera quando se tem um número suficiente de pontos observados

em múltiplas imagens.

Somente cinco parâmetros internos da câmera são relevantes para o método de modelagem

fotogramétrico:

• a coordenada x do centro de projeção,

• a coordenada y do centro de projeção,

• a distância focal,

• a razão de aspecto e

• o ângulo entre os eixos ópticos (normalmente 90o).

Para construir o modelo tridimensional de uma fotografia no sistemaFaçade, o usuário precisa

selecionar um pequeno número de fotografias, podendo refinar o modelo ao incluir mais imagens

11


no projeto até que se encontre o nível de detalhe desejado. O usuário instancia os componentes

geométricos do modelo (figura 2.8b) sem fornecer qualquer tipo de valores numéricos, pois estes

são recuperados pelo próprio sistema. Em seguida, o usuário deve marcar margens na imagem

original (figura 2.8a) e fazer suas respectivas correspondências às margens do modelo. Quanto

maior o número de correspondências, mais precisa será a reconstrução.

(a) (b) (c) (d)

Figura 2.8: Reconstrução do modelo 3D da torre do relógio da Universidade de Berkeley utilizando a abor-dagem algorítmica não-linear do sistemaFaçade: a) imagem original com as margens definidas pelo usuário;b) modelo criado através de primitivas; c) projeção do modelo na fotografia e d) a imagem renderizada (De-

bevec, 2004).

O sistemaFaçadecalcula os tamanhos e posições relativas dos componentes do modelo que

melhor se encaixam nas margens marcadas na fotografia. A precisão do modelo é verificada

projetando-o na fotografia original (figura 2.8c). Finalmente, pode-se gerar uma nova visão do

modelo ao reposicionar uma câmera virtual (figura 2.8d) para uma posição ou altitude dificilmente

obtidas com uma câmera fotográfica.

A cena é representada por meio de blocos poliedrais cujos parâmetros definem seu tamanho

e forma. A escolha por blocos poliedrais deve-se ao fato de que a maioria das cenas arquitetôni-

cas pode ser melhor modelada combinando-se primitivas geométricas à presença de elementos

arquitetônicos comuns em cada bloco e à redução do número de parâmetros que o algoritmo de

12


reconstrução precisa recuperar. A figura 2.8 é parametrizada por apenas 33 variáveis. Se cada seg-

mento de linha na cena fosse tratado independentemente, o modelo teria 2.896 parâmetros, uma

redução que realça a eficiência do método.

Essa abordagem, entretanto, não recuperava superfícies de revolução e arcos. Para modelar

uma superfície curva, o usuário deveria definir um bloco em formato de esfera e manualmente

ajustar sua largura e altura a fim de alinhá-lo com a fotografia. Uma posterior adição ao sistema

Façaderealizada por Borshukov (Borshukov, 1997) eliminou esse obstáculo.

O software Canoma (Capítulo 3) é inspirado na abordagem híbrida do sistemaFaçadede De-

bevec e, embora similares, possui uma interface mais amigável, onde as primitivas são sobrepostas

aos objetos e ajustadas à estrutura tridimensional da fotografia (Oliveira, 2002).

Coloração devoxel(voxel coloring)

O voxel coloring(Seitz and Dyer, 1997) é uma técnica que tem como objetivo determinar

cores paravoxelsem um volume 3D a fim de maximizar a integridade da fotografia a partir de

um conjunto de imagens calibradas, ou seja, visa reproduzir com precisão a imagem de entrada,

preservando cor, textura e resolução dopixel.

As vantagens dessa técnica advêm do fato de as oclusões serem explicitamente modeladas,

de sua relativa independência da geometria amostrada e da distância da câmera não degradar a

precisão ou o tempo de execução.

O algoritmo devoxel coloringdiscretiza a cena em um conjunto devoxelsque são percorridos

e coloridos em uma ordem especial. A cor dovoxelé computada uma única vez em uma ordem

que garanta concordância com a imagem, ou seja, a cor dopixel na imagem equivale à cor do

voxelcorrespondente aopixelna cena.

A figura 2.9 mostra ovoxel coloringcomputado de uma rotação completa de um dinossauro

de brinquedo. A figura 2.9b representa a reconstrução do objeto a partir de um ponto de vista

correspondente ao da imagem original (figura 2.9a) com o objetivo de demonstrar a integridade

com a qual a fotografia foi recuperada. Até mesmo detalhes, como o local onde se dá corda ao

brinquedo e os dedos das mãos, foram reconstruídos.

13


(a) (b) (c)

Figura 2.9: Aplicação da técnicavoxel coloringem um dinossauro de brinquedo: a) imagem original; b) ec) duas visões do modelo reconstruído a partir de 21 fotografias do objeto (Seitz and Dyer, 1997).

A demanda de tempo de processamento e espaço de armazenamento é linearmente dependente

do número de imagens. Logo, com o aumento da taxa de amostragem, obtém-se uma melhora na

qualidade da imagem e, conseqüentemente, um aumento no tempo de execução.

2.2 Considerações finais

Este capítulo descreveu algumas técnicas baseadas em imagens para a reconstrução de mode-

los geométricos 3D. Seguindo uma classificação proposta na literatura, foram apresentadas as

principais técnicas puras e híbridas de modelagem baseada em imagens, tendo como objetivo

principal fornecer uma descrição dos métodos, focando seus aspectos fundamentais.

As técnicas puras utilizam técnicas de visão computacional para determinar a estrutura de uma

cena a partir de múltiplas fotografias, gerando alguns problemas inerentes: as fotografias precisam

ser muito semelhantes, com espaços muito próximos umas das outras e, em geral, são necessárias

várias entradas do usuário para a obtenção de resultados mais confiáveis.

Técnicas híbridas de modelagem, por sua vez, requerem um pequeno conjunto de fotografias

a partir do qual é extraído interativamente um modelo geométrico básico da cena fotografada

por meio de um simples e eficiente sistema de modelagem fotogramétrico. Os pares de imagens

podem ser espaçados uma vez que a técnica em questão recupera com precisão a profundidade das

imagens. Essas técnicas conseguem gerar grandes modelos arquiteturais com um número muito

14


menor de fotografias do que as técnicas puras de modelagem.

Contudo, apesar dos grandes avanços obtidos com as técnicas deIBM, criar modelos comple-

tos de ambientes reais ainda é uma árdua tarefa. Em virtude disso, são fornecidos procedimentos

semi-automáticos para auxiliar os usuários na recuperação de informações, como geometria e tex-

tura, bem como para solucionar possíveis ambigüidades durante a reconstrução dos modelos.

O próximo capítulo descreve a interface da ferramenta Canoma, que utiliza uma técnica híbrida

de modelagem (algoritmo de otimização não-linear), através da demonstração de suas funcionali-

dades e procedimentos para modelagem.

15

CAPÍTULO

3

Canoma

Modelar cenas tridimensionais a partir de imagens bidimensionais não é uma tarefa fácil. A

correta estimativa de perspectiva, tamanho e forma dos objetos é um processo detalhista. Muitos

programas disponíveis atualmente visam facilitar essa tarefa, como é o caso do software Canoma

(Canoma, 2004; Stevens, 1999)1.

O Canoma utiliza uma abordagem algorítmica não-linear e permite a rápida criação de mode-

los 3D fotorealistas a partir de uma ou mais fotografias digitais. Os modelos são geometricamente

simples e utilizam, como fonte de textura, a própria imagem.

Este capítulo descreve o princípio básico do software e alguns recursos disponíveis em sua

interface.1Produto desenvolvido pela empresaMetaCreations Inc., adquirido pelaAdobe Systems Inc

16

Canoma

3.1 A ferramenta Canoma

A figura 3.1 apresenta a janela principal da ferramenta Canoma que possibilita modelar ima-

gens 2D em cenas tridimensionais que podem ser rotacionadas, ampliadas e exportadas para outros

aplicativos. Algumas possíveis utilidades dessa ferramenta são modelar móveis e dormitórios para

locação e venda através da Internet e visualizar possíveis reformas.

Figura 3.1: Interface do software Canoma: um conjunto de primitivas 3D são utilizadas na criação de ummodelo aproximado do ambiente real.

O software possui em sua palheta formas úteis de aramados (wire frames), tais como mesa,

arcos, telhados e escadas. O usuário deve primeiramente carregar a fotografia e, em seguida,

selecionar uma dessas formas geométricas, como mostra a figura 3.2a. Uma deficiência desse

sistema deve-se ao fato de não tratar facilmente superfícies curvas ou esferas. Ao tentar modelar

um domo, por exemplo, o programa ficará um pouco limitado.

17

Canoma

O ideal é iniciar o processo de modelagem pelos objetos maiores, pois os primeiros modelos

criados ajudam a determinar a posição da câmera e a perspectiva. Objetos maiores oferecem uma

maior definição, e uma perspectiva bem definida permite uma melhor operação. A perspectiva

pode também ser estabelecida através do uso de objetos temporários, que podem ser removidos

após a finalização do modelo, como por exemplo um plano de referência (figura 3.2d) indicando

as direções de fuga.

Posteriormente, o operador deve mover esse aramado a fim de alinhar e fixar os seus vértices e

faces com os respectivos vértices e faces visíveis do objeto (figuras 3.2b e c). Como o alinhamento

é feito manualmente, a qualidade do resultado depende da precisão do usuário.

Quando há mais objetos na cena, o usuário pode escolher se vai ou não modelá-los. Caso ele

opte por não modelar um objeto, este será projetado na cena como uma textura de outro objeto e

terá uma aparência ‘achatada’. Caso contrário, deve-se acrescentar novos aramados, correlacioná-

los e, quando possível, alinhá-los aos já existentes. Ao alinhar o telhado e as paredes de uma casa,

por exemplo, garante-se que o telhado está realmente posicionado acima das paredes.

Se existirem muitos objetos, o usuário pode selecionar a opçãosolomodee deixar visível

somente o objeto que estiver sendo modelado, minimizando, assim, a geração de erros.

O software disponibiliza, ainda, a ferramentaGlue, que une os vértices dos aramados a fim

de facilitar o movimento e o estabelecimento de novas correlações. A textura é adicionada ao

modelo diretamente da fotografia, porém, com uma única fotografia não é possível criar texturas

para partes ocultas da imagem.

Após a geração do modelo 3D (figura 3.2f), o usuário pode caminhar pela cena e observá-la de

distintos ângulos. Os modelos podem ser exportados em formatos comuns, incluindo DXF, WRL

e MetaStream.


Foram abordados neste capítulo os fundamentos básicos da interface de uma das ferramen-

tas disponíveis atualmente que simplifica o processo de modelagem de uma cena 3D a partir de

18

Canoma

imagens 2D, denominada Canoma.

Pôde-se perceber que o Canoma possui uma quantidade razoável de recursos, tais como formas

úteis de aramados, e uma interface intuitiva e fácil de usar. No entanto, o posicionamento do

aramado sobre os objetos da cena, necessário para o modelamento 3D, depende completamente

de entradas fornecidas pelo usuário.

A proposta deste trabalho insere-se especificamente neste contexto: implementar mecanismos

que permitam diminuir o grau de dependência do usuário no posicionamento dos aramados sobre

os objetos através da automação desse processo, aumentando, assim, o grau de precisão do modelo.

O terceiro capítulo apresenta o conceito de contornos ativos, através da discussão de seus

modelos e de algumas técnicas existentes. Os contornos ativos constituem uma família de técnicas

destinadas a encontrar automaticamente contornos em objetos e foram escolhidos para solucionar

o problema descrito acima.

19

Canoma

(a) (b)

(c) (d)

(e) (f)

Figura 3.2: Passos para a modelagem no Canoma: a) escolha de uma primitiva 3D; b) e c) ajuste (matching)do aramado à geometria do objeto na cena; d) definição do plano de referência; e) e f) visualizações do

modelo.

20

CAPÍTULO

4

Contornos Ativos

Há muito percebe-se a necessidade do desenvolvimento de técnicas que sejam capazes de

automatizar o processo de detecção de objetos em imagens. Para tanto, algoritmos de segmentação

baseados em regiões, em bordas e em texturas são vastamente utilizados e considerados passos

fundamentais para a análise e identificação de características relevantes em uma imagem.

O modelo de Contornos Ativos (Active Contour), primeiramente proposto por Kass em 1987

(Kass et al., 1987), é um método de segmentação baseada em informações da região e, sobretudo,

das bordas, utilizado para localizar objetos e descrever sua forma.

Este capítulo apresenta inicialmente o modelo de contornos ativos, seus princípios, fundamen-

tos e conceitos. Aborda, em seguida, o modelo paramétrico tradicional (snakes), suas principais

características e deficiências. Em seguida, são apresentados modelos de contornos ativos alter-

nativos que minimizam tais deficiências. Trata, ainda, dos modelos geométricosLevel Sete Fast

Marching((Sethian, 2004)) e, finalmente, discorre sobre as razões da escolha pela implementação

de um modelo paramétrico.

21

Contornos Ativos

4.1 Conceito de contornos ativos

Utilizados para a detecção de contornos de objetos da cena e geralmente aplicados conjun-

tamente com técnicas de filtragem empregadas na detecção de pontos de bordas, os contornos

ativos utilizam curvas definidas sobre o domínio da imagem que podem mover-se, controladas por

ação de forças internas (intrínsecas à geometria da curva) e externas (derivadas da imagem), em

busca de uma posição de equilíbrio, ou seja, a localização do contorno da estrutura de interesse

(Pimentel, 2000; Machado et al., 2002). Na literatura, existem dois tipos principais de modelos de

contornos ativos: modelos paramétricos, como assnakes, e modelos geométricos, como oLevel

Sete oFast Marching.

O modelo paramétrico, abordado neste trabalho, representa curvas e superfícies explicitamente

na sua forma paramétrica permitindo, assim, a interação direta com o modelo, além de propor-

cionar uma representação mais compacta para sua implementação em tempo real.

Os modelos geométricos definem curvas que se movimentam de acordo com uma função ve-

locidade. Essa função pode depender de diversas grandezas físicas que, por sua vez, dependem de

características extraídas da imagem e de restrições geométricas da própria função. Uma vantagem

dessa abordagem é que o conjunto inicial não deve necessariamente ser uma única curva, mas um

conjunto de curvas independentes que podem se fundir para adaptar-se à topologia local.

4.1.1 Modelos paramétricos

Baseado em uma abordagem de funcional de energia, o modelo paramétrico consiste basica-

mente em uma curva (ou superfície) elástica que pode adequar-se dinamicamente às fronteiras

do objeto em resposta a ações de forças internas e externas. Esse modelo apresenta uma formu-

lação matemática que integra, em um único processo, parâmetros como propriedades da imagem,

estimativas iniciais de fronteiras, propriedades desejadas do contorno e restrições conhecidas do

tipo de imagem processada com o propósito de atrair a curva em direção a uma borda através de

iterações, ficando em equilíbrio sobre a mesma ao atingir o valor mínimo de energia do sistema.

Devido à maneira pela qual a curva original se move em direção a características desejadas da

22

Contornos Ativos

imagem (normalmente bordas), o modelo paramétrico original de contornos ativos é denominado

snakes.

Nesse modelo, a curva possui uma posição inicial especificada pelo usuário e uma função

objetiva associada, denominada energia dasnake.

Essa energia é composta pela energia inerente à própria curva (interna), como elasticidade e

rigidez, e pela energia do ambiente (externa), como forças de pressão. A evolução da posição

da snakeé dada pela solução de uma equação de minimização da sua energia, sendo que no

estado final, sua configuração não mais se altera, uma vez que qualquer movimento aumentaria

sua energia.

O modelo paramétricosnake

Primeiramente, devem ser definidos na imagem de entrada os pontos que compõem o contorno

inicial (figura 4.1). Esses pontos definem o vetorv(s) = (x(s),y(s)), ondex e y são conhecidos e

representam as coordenadas dos pontos do contorno.

Figura 4.1: Conjunto de pontos iniciais definidos pelo usuário na imagem original (Bianchi, 2003)

A curva inicial move-se no domínio espacial da imagem a fim de minimizar a função de energia

dada pela seguinte equação:

E =∫ 1

0

12(α| v′(s) |2 + β| v′′(s) |2) + Eext(v(s))ds (4.1)

O primeiro termo da equação 4.1 representa a energia interna dasnake. A constanteα controla

23

Contornos Ativos

a tensão dasnake, ou seja, determina quanto o contorno pode ser esticado ou contraído enquanto

β é responsável pela elasticidade e determina quais pontos podem ser ‘entortados’ para gerar

cantos. A derivada de primeira ordemv′, controlada porα, tende a valores altos quando uma

descontinuidade é encontrada na curva, enquanto a derivada de segunda ordemv”, controlada por

β, tende a altos valores conforme a curva se ‘dobra’. O usuário pode guiar o contorno para uma

característica conhecida na imagem, ajustando, a cada processo, os valores deα eβ. Portanto, se

estima-se a existência de um canto,β deve tender a zero.

O segundo termo representa a energia externa, ou seja, a energia que atrai asnakepara os

contornos da estrutura de interesse na imagem, sendo que o termoEext deriva da imagem e tem

seu menor valor em regiões de borda (contornos), devendo, portanto, ser baixa onde o gradiente

for alto. Desta forma, dada uma imagem em tons de cinza, a energia externa pode ser obtida com

a aplicação de um filtro passa alta qualquer.

O filtro passa alta é aplicado com o intuito de reduzir o nível de ruído encontrado na imagem

original e aumentar o contraste na imagem, realçando o contorno e melhorando o alcance de

captura dasnake.

A fim de minimizar a energia E representada na equação 4.1, asnakedeve satisfazer a seguinte

equação de Euler:

αv′′(s)− βv′′′′(s)−∇Eext = 0 (4.2)

Um resultado para a equação acima pode ser encontrada ao solucionar-se o sistema discreto

iterativamente. A cada iteração são calculadas a energia para cada pontov(si) da curva e a energia

para os seus pontos vizinhos, como mostra a figura 4.2. Assim, o ponto que possuir a menor

energia será escolhido como nova posição para o pontov(si).

Quando qualquer movimento aumenta o valor da equação de energia, asnakese estabiliza e

seu formato não mais se altera.

24

Contornos Ativos

Figura 4.2: Pontov(si) e seus vizinhos (vizinhança 3x3): a energia é calculada para cada pontonj , onde jvaria de 1 a 9.

Adições ao modelo original

Apesar da simplicidade do modelo e de sua formulação matemática ser bastante intuitiva,

alguns problemas limitam o uso dasnake.

Em primeiro lugar, o contorno inicial, definido manualmente pelo usuário, deve ser similar e

estar relativamente próximo da fronteira real para garantir a convergência correta, caso contrário,

ruídos presentes no interior do objeto atrairão asnakepara seus mínimos locais, gerando, assim,

falsas bordas. A razão para a fraca convergência é revelada ao observar a figura 4.3a, onde a

magnitude das forças externas é pequena, limitando o alcance de captura.

A fim de solucionar esse problema e melhorar a performance do algoritmo algumas sugestões

foram propostas, dentre elas destacam-se aplicação de forças de pressão (Cohen, 1991), métodos

de multiresolução (Leroy et al., 1996) e potenciais de distância (Cohen and Cohen, 1993). A

idéia básica desses métodos é aumentar o alcance de atração dos campos de energia externa e

corretamente direcionar asnakepara a fronteira real (figura 4.3b).

Entretanto, embora aumentem a magnitude dos vetores, essas propostas não são capazes de

solucionar um segundo problema: a dificuldade de convergência em geometrias côncavas. Esse

fato pode ser explicado recorrendo-se à figura 4.4a, onde pode ser observado que, apesar de

apontarem em direção ao objeto, na concavidade os vetores apontam horizontalmente em direções

opostas. Não havia nenhum método que fornecesse uma solução satisfatória, pois as abordagens

até então propostas, tais como forças de pressão ou a utilização de pontos de controle (Davatzikos

25

Contornos Ativos

(a)

(b)

Figura 4.3: a) Campo vetorial do modelo tradicional desnakee b) do modelo de potenciais de distância.

26

Contornos Ativos

(a) (b)

Figura 4.4: Comportamento dos vetores em uma região côncava usando em a) o modelo de potenciais dedistância e b) o modelo.

and Prince, 1995), solucionavam um problema, porém criavam uma nova dificuldade.

A solução para a fraca convergência em regiões côncavas foi somente apresentada em 1998

pelo modeloGradient Vector Flow(GFV), proposto por Xu e Prince. O comportamento dos

vetores do campoGVF, apontando em direção à região côncava do objeto, é ilustrado na figura

4.4b.

Finalmente, outro empecilho presente no modelo original pode ser descrito como a incapaci-

dade de lidar com mudanças topológicas, limitando a segmentação de objetos de múltiplos con-

tornos, com buracos ou ramificações. O modeloT-Snakes(Topologically Adaptable Snakes), intro-

duzido por McInerney e Terzopoulos (1999), elimina esse problema, permitindo que asnakeseja

dividida para criar múltiplos contornos ou fundindo vários contornos em um só (split emerge).

Alguns dos modelos citados serão apresentados nas seções subseqüentes.

O modeloBaloon

Proposto para solucionar o problema referente à inicialização do contorno, o modeloballoon

tem como idéia principal o acréscimo de uma componente de força normal ao vetor de forças

27

Contornos Ativos

externas a fim de promover um crescimento ou encolhimento uniforme da curva, de acordo com o

sentido e módulo dessa força. Dessa forma, o segundo termo da equação 4.1 que antes se referia

somente à imagem, passa a ser dado pela equação 4.3:

Eext(v(s)) = k1−→n (v(s))− k2 −

Egradiente(v(s))‖Egradiente(v(s))‖

(4.3)

onde−→n é um vetor unitário normal à curva no pontov(s) e k1 é a amplitude dessa força. O

desenvolvimento completo desta técnica pode ser encontrado em (Cohen and Cohen, 1993).

Mesmo com uma estrutura inicial definida distante do contorno desejado, através da utilização

de forças de pressão, o modeloballoon converge para o resultado esperado, como ilustrado na

figura 4.5.

(a) (b) (c)

Figura 4.5: O modeloballoon: a) snakecom dimensão menor que a da estrutura e posição inicial distantedos contornos; b) sua posição após 100 iterações e c) sua posição após 500 iterações (Pimentel, 2000).

Esse novo modelo aumenta o alcance de captura dasnake, mas requer uma prévia definição de

sua evolução, ou seja, o contorno deve ser iniciado para crescer ou encolher.

O modeloGradient Vector Flow- GVF

Um novo campo de força estática denominadoGVF (Xu and Prince, 1998) aponta em direção

às bordas dos objetos quando próximo a elas, variando suavemente sobre regiões homogêneas e

extendendo-se até a fronteira da imagem (figura 4.6).

Primeiramente, é definido um mapa de arestasf(x, y) qualquer (binário ou em nível de cinza)

derivado da imagemI(x, y) (Xu and Prince, 1997).

28

Contornos Ativos

Figura 4.6: Campo doGVF para um objeto concâvo em forma de U: os vetores atraem o contorno emdireção à borda do objeto (Xu and Prince, 2004).

f(x, y) = −∇Eext(x, y) (4.4)

Convém ressaltar três importantes propriedades dos mapas de arestas. Primeiro, o campo∇f

tem os vetores apontando em direção às bordas. Segundo, esses vetores geralmente têm uma maior

magnitude na vizinhança imediata das bordas. E terceiro, em regiões homogêneas, ondeI(x, y) é

constante,∇f é zero.

O algoritmo dogradient vector flowé computado como a difusão do vetor gradiente sobre o

mapa de arestas derivado da imagem, não sendo alterado durante a evolução dasnake.

Sendoµ correspondente à quantidade de ruído presente na imagem, oGVF é definido como o

campo de vetoresv(x, y) = [u(x, y), v(x, y)] que minimiza a equação:

E =∫ ∫

µ(u2x + u2

y + v2x + v2

y) + |∇f |2|v −∇f |2dxdy (4.5)

29

Contornos Ativos

Quando∇f é pequeno, a energia é denominada pela soma dos quadrados das derivadas par-

ciais do campo de vetor, forçando o campo a variar suavemente em regiões homogêneas (onde

I(x, y) é constante) através de interpolação do campoGVF na região próxima da borda, criando,

assim, um efeito suave onde não há dados.

O campoGVF é então normalizado entre [0,1], podendo, assim, dar início ao processo de

deformação dasnake, quando o conjunto de pontos definidos pelo usuário será interpolado para

formar a curva inicial que será ajustada até que o contorno do objeto na cena seja encontrado.

Os parâmetrosα (elasticidade),β (rigidez),γ (viscosidade) eκ (peso forca externa), forneci-

dos pelo usuário, formam a matriz pentadiagonal Anxm (n representa as linhas da imagem e m, as

colunas), conforme abaixo:

Dado:

a=β

b= -α - 4 β

c= 2α + 6 β

d= -α - 4 β

e=β

A =

c d e a . . .

b c d e . . .

a b c d . . .

e a b c . . ....

......

......

Através de decomposição LU (método de Crout com pivotamento parcial) calcula-se a inversa

da matriz A. Quando o determinante for diferente de zero, a matriz A pode ser decomposta no

produto A=LU, onde L é uma matriz triangular inferior e U é uma matriz triangular superior cujos

elementos da diagonal possuem valores fixos (Uii=1). A associação a um processo de pivotamento

parcial (troca de colunas) evita pivôs nulos e é essencial para a estabilidade do método (Press et al.,

1986).

30

Contornos Ativos

As equações 4.6 e 4.7 fornecem as novas posições de x e y.

x = inv(A) ∗ (γ ∗ x + κ ∗ vfx) (4.6)

y = inv(A) ∗ (γ ∗ y + κ ∗ vfy) (4.7)

Dentre as vantagens desse modelo sobre o tradicional, devem ser mencionadas:

• uma menor dependência da posição inicial, obtida ao ampliar-se a magnitude dos vetores,

extendendo-os a toda a imagem;

• a habilidade de mover-se em regiões côncavas. Pode ser observado na figura 4.3c que os

vetores não mais apontam horizontalmente no interior da região côncava (figura 4.3b), mas

para baixo (no exterior da figura) e para cima (internamente);

• não é necessário conhecimento prévio sobre a evolução da curva (figura 4.7) (Xu and Prince,

2000) .

O modeloGVF pode ser facilmente estendido para o caso 3D. A figura 4.8 utiliza superfícies

deformáveisGVF em uma imagem 3D. A figura 4.8a ilustra o objeto a ser reconstruído. O campo

GVFé computado e resulta em dois planos (figura 4.8b) onde é, posteriormente, projetado (figuras

4.8c e 4.8d).

A superfície deformável é inicializada como uma esfera (4.8e). Nas figuras 4.8f, 4.8g e 4.8h

observam-se respectivamente os resultados parciais após 10 e 40 iterações e o resultado final após

100 iterações. A superfície resultante é mais suave do que a superfície original devido à ação de

forças internas.

31

Contornos Ativos

(a) (b)

Figura 4.7: Segmentação de imagem de ressonância magnética utilizando o modeloGVF: a) snakeinicial-izada externamente à estrutura e b) sua posição final (Pimentel, 2000).

Figura 4.8: Aplicação do modeloGVF em objeto tridimensional: a) isosuperfície de um objeto 3D; b)posição dos planos A e B; c) e d) projeções da superfície nos respectivos planos; e) configuração inicialda superfície deformável usandoGVF; f) posição da superfície após 10; g) 40 e h) 100 iterações (Xu and

Prince, 2000).

O modeloT-Snakes

Dentre as abordagens existentes para tratar as limitações topológicas do modelo tradicional,

destaca-se oT-snakes(McInerney and Terzopoulos, 1999) que, independentemente da inicializa-32

Contornos Ativos

ção do contorno (interno ou externo à estrutura), gera resultados semelhantes.

Esse modelo possui três componentes: triangulação da imagem (figura 4.9), um modelosnake

discreto (responsável pela evolução dos pontos em direção à borda de interesse) e uma função

característica.

Figura 4.9: Malha resultante de decomposição simplicial (triangulação) do domínio.

Segundo este modelo, umasnakeé definida como um conjunto de N pontos conectados cuja

posição varia no tempo. A cada ponto (snaxels) estão associadas, além de uma posição, uma força

de tensão, uma força de rigidez, uma força normal e uma força externa. A equação doT-snakes,

aplicada a cadasnaxeldurante as iterações, é uma combinação dessas forças.

A função característica atribui o símbolo + (ou o valor 1) aos vértices dos triângulos já visita-

dos (figura 4.10) e que, portanto, não poderão ser atingidos novamente, evitando, assim, problemas

de oscilação dasnake.

Figura 4.10: Comportamento da função característica: a atribuição de símbolos aos vértices é dependenteda evolução pré-definida dasnake.

33

Contornos Ativos

O modeloT-snakesrequer uma definição prévia sobre o comportamento da curva (se irá ex-

pandir ou contrair). Deste modo, os nós internos ou externos ao contorno são definidos como

‘queimados’ (pequenos círculos sobre os vértices na figura 4.11). A cada passo da evolução, a

função característica é atualizada e uma vez queimado, o nó permanece nesse estado. Quando

todos os pontos da malha possuem valor 0 ou 1, determinam-se os triângulos de borda (triângulos

onde a função característica muda de valor).

Figura 4.11: Projeção dos pontos do contorno inicial na grade: nós externos definidos como ‘queimados’após prévia definição da evolução dasnake.

Na figura 4.12 vemos um exemplo de execução desse modelo. Primeiramente, o usuário in-

forma os pontos iniciais e, então, os nós da grade externos ao contorno são queimados (figura

4.12a). Em seguida, vê-se asnakemomentos antes da mudança topológica (figura 4.12b) e, por

fim, o estado final dasnakecom os objetos detectados (figura 4.12c). O que seleciona os objetos

não é exatamente asnake, mas as regiões da grade onde os nós não foram queimados, embora

essas regiões sejam selecionadas através da trajetória dasnake.

Esse método possui algumas limitações como a restrição à evolução devido à irreversibilidade

dos valores nos vértices, limitando asnake, como já dito anteriormente, a contrair-se ou expandir-

se. Além disso, se o objeto de interesse possui concavidades profundas, a resolução da malha deve

ser suficiente para que a snake se acomode à borda desejada, evitando problemas de performance.

Dentre as vantagens pode-se citar a sua generalidade (que permite tanto agrupamento quanto

particionamento da snake) e a possibilidade de ser facilmente estendido para superfícies, uma vez

34

Contornos Ativos

(a) (b) (c)

Figura 4.12: Exemplo da evolução dasnakedescrita em 3 momentos: a) inicial; b) intermediária e c) final(Machado et al., 2002).

que seus elementos básicos (triangulação, reparametrização, função característica) são eficiente-

mente estendíveis ao caso 3D ((McInerney, 1997)apud(Giraldi et al., 2004)).

4.1.2 Modelos geométricos

A maioria das técnicas numéricas utiliza marcadores que tentam rastrear o movimento do

contorno ao comportarem-se como bóias presas por uma corda que se movem a uma velocidade F.

Quando essas bóias se cruzam ou o contorno tenta se dividir, é muito difícil manter sua organização

(Sethian, 1987).

Os modelos geométricos, ao invés de seguirem a evolução do contorno em si, definem uma

curva que se move de acordo com uma função velocidade F (equação 4.8) a fim de rastrear a

evolução da superfície.

F = F (L,G, I) (4.8)

onde, L corresponde às propriedades locais (direção normal e curvatura), G às propriedades

35

Contornos Ativos

globais dependentes da posição e forma da curva e I representa o gradiente de tons de cinza.

Os dois métodos existentes distinguem-se quanto à função velocidade possuir características

monótonas ou não. Se a curva é representada como nível zero de uma função de dimensão maior,

tal que o movimento da curva esteja ‘embutido’ no movimento da nova função, o método é de-

nominadolevel set. Porém, se a função velocidade apresenta sempre valores positivos (fazendo

com que a curva sempre se propague para fora) ou negativos (a curva se propaga para dentro), o

método é denominadofast marching.

As principais vantagens desses modelos são a capacidade de gerar cantos e lidar com mudanças

topológicas.

O modeloLevel Set

Introduzido por Osher e Sethian (1988), o modelolevel setfoi desenvolvido para tratar pro-

blemas onde a função velocidade varia, logo ela pode ser positiva em alguns lugares e negativa em

outros, ou seja, o contorno pode tanto avançar como recuar.

Suponha uma curva que separa duas regiões (figura 4.13) e uma função velocidade F, depen-

dente de vários efeitos físicos, que diz como mover cada ponto da imagem. Imagine que a região

interna à curva seja composta de gelo e a região externa, de água. Se o gelo derreter a região

interna diminui e se o gelo congelar, ela aumenta. A velocidade dependerá, portanto, da diferença

de temperatura entre as duas regiões.

Figura 4.13: Curva inicial em preto separando a imagem em duas regiões.

Ao invés de seguir a evolução do contorno em si, essa abordagem constrói, a partir da curva

36

Contornos Ativos

original (figura 4.14a), uma função de maior dimensão, denominadalevel set(conjunto de níveis),

que intercepta o plano xy exatamente na posição da curva (figura 4.14b), ou seja, a curva é repre-

sentada pelo nével zero dessa função.

Figura 4.14: A frente propagante e a funçãolevel set: a snakeé definida pela intersecção da superfíciebi-dimensional com o plano xy (Sethian, 2004).

Essa função aceita como entrada qualquer ponto no plano e, como saída, devolve a altura desse

ponto. A curva inicial é denominada nível zero já que seus pontos encontram-se na altura zero.

A evolução da snake está vinculada à evolução da superfície (e vice-versa). Ao contrário de

mover o contorno, move-se a superfície em forma de cone (figura 4.14b), ou seja, a funçãolevel set

expande, sobe ou desce. Enquanto a curva pode entortar-se, a função é bem comportada, lidando

naturalmente com mudanças topológicas (figura 4.15).

O modeloFast Marching

Outro modelo geométrico, também proposto por Sethian, é denominadofast marching. Ele

foi desenvolvido para tratar problemas onde o sinal da função velocidade nunca muda, portanto o

contorno ou se expande ou se retrai.

Suponha, agora, uma curva que separa duas regiões (figura 4.13) e uma função velocidade F>0

que diz como mover cada ponto da imagem. Imagine que a região interna à curva seja composta de

ácido que corrói a região externa. A velocidade da corrosão dependerá da resistência do material ao

ácido: partes mais resistentes do material a diminuem, enquanto partes mais corrosivas a aceleram.

37

Contornos Ativos

Figura 4.15: Split e Merge: o contorno inicial é formado por duas curvas que se unem conforme crescem(Sethian, 2004).

Ao invés de seguir a evolução do contorno em si, como a maioria das técnicas numéricas, o

fast marchingutiliza uma abordagem fixa, já que cada ponto será atravessado somente uma vez.

Figura 4.16: Contorno projetado em uma malha: cada vértice armazena o tempo T em que foi atingido pelafrente propagante.

Para cada ponto T da malha (figura 4.16) a função T(x,y) fornece o tempo em que cada

ponto(x,y) foi atingido. A partir dessa função constrói-se uma superfície (figura 4.17) que fornece

o tempo de chegada.

As vantagens desse modelo advém do fato do comportamento da função não depender da

forma adquirida pelo contorno (assim como nolevel set) e da rapidez do cálculo da posição do

contorno para um determinado instante.

38

Contornos Ativos

Figura 4.17: A Superfície de Tempo de Chegada, fornecida pela função T(x,y), intercepta o plano xyexatamente onde inicia-se a curva (Sethian, 2004).


Neste capítulo foram apresentados conceitos relacionados a contornos ativos além de alguns

modelos existentes utilizados em segmentação de imagens. Tais modelos dividem-se basicamente

em dois grupos: paramétricos (representação explícita do contorno) e geométricos (representação

implícita do contorno através de uma curva de nível zero de uma função de maior dimensão).

Ambos os modelos dependem, respectivamente, da definição de um termo de energia externa e

de uma função velocidade para que o contorno converja para as bordas das estruturas de interesse

na imagem.

Embora os modelos geométricos admitam mudanças topológicas no contorno e formação de

cantos, alguns modelos paramétricos procuram minimizar esse tipo de problema. Portanto, na

prática, ambos podem ser explorados.

Além das habilidades topológicas, os métodos geométricos possuem boa estabilidade e fácil

extensão para superfícies bi-dimensionais. Entretanto, o uso de uma dimensão extra torna este

método pouco intuitivo, dificultando a incorporação de informações adicionais (de forma, por

exemplo) ou vínculos (como pontos atratores) e a interação com o usuário (Giraldi et al., 2004).

Por outro lado, a representação explícita de uma curva fechada que evolui ao longo do tempo

39

Contornos Ativos

a fim de minimizar uma função de energia dependente de fatores externos é bastante intuitiva,

tornando os modelos paramétricos bem mais simples que os geométricos tanto quanto à represen-

tação do contorno, quanto à sua implementação, embora sua formulação original apresente alguns

problemas e careça de ferramentas para solucioná-los.

Vale destacar que ainda não existe um método robusto o suficiente que garanta resultados

precisos para qualquer configuração de imagem (Pimentel, 2000). A correta convergência do

contorno em ambos os casos, além de ser muito dependente da qualidade da imagem e do nível de

ruído apresentado, depende também de sua inicialização, podendo fazer com que o processo seja

repetido diversas vezes até que o resultado encontrado satisfaça o usuário.

Devido à convergência em superfícies côncavas, à autonomia quanto à inicialização do con-

torno (contração ou expansão) e ao fato de que não será necessário tratar mudanças topológicas,

o modelo desnakeescolhido como ponto de partida para a implementação será oGVF - Gradient

Vector Flow.

40

CAPÍTULO

5

Descrição do Método

Este projeto de pesquisa propõe a implementação de um mecanismo automatizado de so-

breposição e posicionamento de primitivas gráficas sobre objetos presentes em cena com o ob-

jetivo de aumentar a precisão e minimizar a dependência do usuário nas ferramentas de mode-

lagem baseada em imagens. Para o desenvolvimento deste trabalho, o projeto foi dividido em

duas etapas, conforme ilustrado na figura 5.1.

Figura 5.1: Framework do projeto: a) contorno inicial definido pelo usuário; b) contorno externo do objetoidentificado após aplicação da técnica de contornos ativos e c) localização dos vértices.

A primeira etapa consiste na identificação do contorno do objeto de interesse na cena por meio

41


Figura 5.2: Snake: obtenção do contorno do objeto de interesse. a) Imagem original a partir da qual gera-seo mapa de arestas que será utilizado para o cálculo de b), o campoGVF. Em c) o contorno externo do objeto

identificado após aplicação do contorno ativo.

do modeloGVF de contornos ativos (subseção 4.1.1). De posse dos resultados e de informações

geométricas do objeto de interesse, inicia-se a segunda etapa, cuja finalidade é identificar todos os

vértices do objeto.

Nas seções seguintes, serão descritos os procedimentos e técnicas utilizados na execução das

etapas acima mencionadas.

5.1 Identificação do contorno

No modelo tradicional desnakes, o campo de força do mapa de arestas fica restrito, princi-

palmente, às áreas próximas às regiões de bordas. Como visto anteriormente, o modeloGVF visa

expandir esse campo para toda a imagem, aumentando o poder de captura dasnake. A figura 5.2

ilustra o processo de obtenção do contorno do objeto.

Inicialmente, por meio da aplicação de um filtro passa-alta sobre a imagem original, gera-se

o mapa de arestas que será utilizado durante o cálculo do novo campo de força. De acordo com

a imagem manipulada, o usuário deve selecionar o filtro adequado entre os três filtros disponíveis

na interface, a fim de realçar as bordas, antes de iniciar asnake.

42


(a) (b) (c)

Figura 5.3: Máscaras do operador de Sobel utilizadas para detectar a derivada de primeira ordem a)nahorizontal (Gx) e b)na vertical (Gy); c)filtro Laplaciano de vizinhança 4.

O filtro passa-alta aumenta o contraste na imagem ao atenuar as baixas freqüências e ressaltar

as altas freqüências, normalmente expressas por bordas ou limites entre áreas de diferentes va-

lores de níveis de cinza (Gonzales, 1987). Foram implementados os filtros Sobel, Laplaciano e o

Gradiente da Derivada Direcional Integrada (GDDI) (Zuniga and Haralick, 1987).

O operador de Sobel é um filtro não-linear, computado a partir da primeira derivada, para

realçar bordas, por meio da convolução de duas máscaras 3x3, Gx e Gy (figura 5.3a e 5.3b), sobre

a imagem original. O filtro Laplaciano é um operador diferencial de segunda ordem que utiliza

uma máscara com um alto valor central, cercado de valores negativos na direção N-S e E-W e

valor zero para os pesos da máscara, conforme figura 5.3c. Um problema decorrente do uso da

segunda derivada é a sensibilidade a ruídos.

O terceiro filtro, GDDI, utiliza uma máscara 7x7 (figura 5.4), cujos coeficientes representam

a forma paramétrica de um polinômio cúbico. Segundo Haralick (Zuniga and Haralick, 1987),

o filtro apresenta resultados superiores quando comparados aos filtros tradicionais para imagens

com alto nível de ruído, além da localização e estimativas mais precisas sobre a orientação das

arestas.

Para imagens binárias, que apresentam somente o contorno do objeto, como um aramado, o

uso do filtro é desnecessário, bastando somente normalizar o mapa de arestasf , a fim de que varie

entre 0 e 1, de acordo com a equação 5.1.

f = 1− I/MAX (5.1)

43


Figura 5.4: Máscara do operador GDDI com vizinhança 7x7.

Gerado o mapa de arestas, segue-se para uma nova etapa onde, iterativamente, computa-se o

GVF, gerando o novo campo de força ilustrado na figura 5.5.

Após a normalização do campoGVF, inicia-se o processo de deformação da curva (contorno

ativo). Nesse momento, o usuário deve definir ao menos três pontos que serão interpolados para

formar a curva inicial que será ajustada a fim de encontrar o contorno do objeto na cena.

Anteriormente, foi mencionado que, para oGVF-snakes, um prévio conhecimento sobre a

evolução do contorno é dispensável, ou seja, não é necessário saber se o contorno deve expandir-

se ou contrair-se. Sendo assim, o conjunto de pontos é dinamicamente interpolado durante a

evolução dasnakede tal forma que obedeça uma distância pré-estabelecida. Essa característica

oferece ao usuário a possibilidade de definir um contorno aleatório, tanto internamente como do

lado externo do objeto.

Ao final do processo de evolução dasnake, as coordenadas de cada ponto do contorno encon-

trado são armazenadas em uma estrutura de dados. Dado que a curva convergiu corretamente para

a borda do objeto, essas coordenadas (que representam o contorno do objeto) são aplicadas sobre

o mapa de arestas a fim de obter o valor da média e do desvio padrão desses pontos para que,

posteriormente, os vértices do objeto possam ser calculados, como será elucidado a seguir.

44


Figura 5.5: Campo de força após aplicação doGVF.

5.2 Detecção dos vértices

Conforme a figura 5.6, que representa a figura geométrica de um cubo, o processo de detecção

dos vértices subdivide-se em duas etapas. Primeiramente são computados os vértices visíveis (1,

2, 3, 4, 5, 6 e 7), ou seja, os vértices localizados na parte frontal do objeto na cena e que, portanto,

podem ser visualizados na imagem. A partir de suas coordenadas, estima-se a localização dos

vértices ocultos (vértice 8). O método utilizado durante essas etapas será descrito nas subseções

5.2.1 e 5.2.2, respectivamente.

5.2.1 Vértices visíveis

Dada a média e o desvio padrão anteriormente obtidos, computados a partir do contorno final,

inicia-se o processo de detecção dos vértices. Nesta etapa, objetiva-se encontrar o maior número

possível de vértices visíveis do objeto.

Para alcançar tal objetivo, o mapa de arestas é percorrido e os pontos cujos valores pertençam

ao intervalo previamente calculado são identificados como possíveis vértices. Observa-se que,

potencialmente, todos os pontos do contorno são vértices, já que os mesmos satisfazem essa pre-

45


Figura 5.6: Processo de detecção dos vértices: a) o contorno encontrado pelasnakes; b) detecção dosvértices visíveis (1, 2, 3, 4, 5, 6 e 7) e c) vértice oculto (8) estimado a partir das coordenadas dos vértices

visíveis.

missa. Se um ponto é candidato a vértice, dá-se início ao processo de seleção.

Para isso, faz-se mister que o usuário defina, através da interface, três parâmetros essenciais

para o prosseguimento do cálculo. São eles:

• amostragem de pontos - define quantos pontos consecutivos serão analisados em conjunto;

• variação angular - define quão refinada será a busca para cada vértice candidato;

• correspondência dos pontos - define, percentualmente, quantos pontos da amostragem de-

vem, necessariamente, satisfazer a condição de pertencer ao intervalo calculado a partir da

média do contorno final.

O valor desses parâmetros varia de acordo com a geometria do objeto, suas angulações e

proporções, sendo que, um bom resultado dependerá de uma análise adequada.

Na figura 5.7a, por exemplo, foi criado um vetor de dez elementos, posto que foi definida

pelo usuário uma amostragem de 10 pontos. Mantendo-se o vértice candidato como seu primeiro

elemento, o vetor é rotacionado360o no sentido anti-horário a partir da origem (eixo x) de acordo

com a variação angular informada que, neste exemplo, é de15o (figura 5.7b). Logo, para esse

46


(a)

(b)

Figura 5.7: Processo de seleção de um vértice candidato para: a) uma amostragem de 10 pontos e b) umavariação angular de15o.

caso, cada vértice candidato será analisado em 24 angulações diferentes, partindo do ângulo0o,

variando de 15 em 15 graus, até atingir uma rotação completa (360o).

Ao rotacionar o vetor em torno do vértice candidato busca-se por segmentos de reta que partam

47


Figura 5.8: Processo de seleção de um vértice candidato localizado fora da extremidade da reta.

desse ponto. Para que isso aconteça os valores dos 10 elementos1 do vetor no mapa de arestas

também devem pertencer ao intervalo calculado anteriormente, ou seja, devem fazer parte do

contorno do objeto.

Sempre que um segmento de reta é encontrado, o ângulo em relação à origem é armazenado.

É importante observar que o ângulo cujo complementar já tenha sido anteriormente armazenado

será desconsiderado. Portanto, um vértice candidato localizado num ponto intermediário da reta

(figura 5.8) não será considerado vértice, visto que ao detectar-se um segmento de reta para o

ângulo180o, por exemplo, este não será armazenado, pois o seu complementar já foi previamente

encontrado.

Ao final da rotação, se o vértice candidato possuir mais de um ângulo não consecutivo ar-

mazenado, ele é classificado como um vértice do objeto.

Quando o mapa de arestas houver sido totalmente percorrido e o maior número possível de

vértices visíveis na imagem houver sido localizado, pode-se, então, prosseguir para a próxima

etapa, o cálculo dos vértices ocultos.

1O terceiro parâmetro que o usuário deve definir (correspondência dos pontos), conforme explicitado, irá representarquantos destes pontos devem realmente satisfazer essa condição.

48


5.2.2 Vértices ocultos

Conhecendo-se a localização dos vértices visíveis, o próximo passo é encontrar os vértices

localizados na face oculta do objeto e que, portanto, não são visíveis na imagem.

Para realizar essa tarefa, é necessário ter-se um conhecimento prévio da geometria do objeto

em questão. O usuário deve, portanto, optar pela forma geométrica mais adequada, ou seja, que

mais se assemelhe ao objeto. A partir dessa definição, sabe-se quantos vértices o objeto possui,

logo, sabe-se quantos vértices ainda restam ser identificados. As formas disponibilizadas, cubo,

pirâmide de base triangular e pirâmide de base quadrangular, foram baseadas nos objetos apresen-

tados na interface da ferramenta Canoma (capítulo 3).

Dada a média calculada a partir dos pontos do contorno dasnake, calcula-se, no mapa de

arestas, a existência de segmentos de retas que conecte cada par de vértices visíveis localizados na

etapa anterior (seção 5.2.1). Nesse instante, é criada uma lista de adjacências (semelhante a teoria

de grafos) que armazenará as conexões encontradas. A lista de adjacências comporta-se como um

grafo não direcionado e conectado, onde os nós representam os vértices da figura geométrica e

cada conexão representa uma aresta do objeto.

Uma segunda etapa do processo é ilustrada na figura 5.9 e consiste em dividir essa lista em

dois grupos: vértices de grau 2 ou 1 (que possuem menos de três conexões) e vértices de grau

maior ou igual a 3 (que possuem três ou mais adjacências) (figura 5.9).

Dado que um conjunto de linhas paralelas num espaço tridimensional converge para um único

ponto no plano da imagem, chamado ponto de fuga (Cantoni et al., 2001), através da equação

da reta e da relação de inclinação entre arestas opostas, as coordenadas desse ponto podem ser

encontradas.

Durante esse cálculo são empregados somente os vértices que possuem mais de três adjacên-

cias, porquanto partem desses pontos segmentos de retas em três direções. Note que, como são

considerados os três eixos de coordenadas, mais de um ponto de fuga (finito ou infinito) será

encontrado, como exemplifica a figura 5.10.

Os vértices que possuem menos de três conexões e que, portanto, não foram incluídos no

49


Figura 5.9: Vértices de um cubo e suas adjacências: os vértices 3 e 4 possuem três vértices adjacentes,enquanto 1, 2, 5 e 6 possuem, inicialmente, conexões com somente dois vértices.

Figura 5.10: Cálculo dos pontos de fuga: as linhas tracejadas representam um ponto de fuga finito (v)computado a partir das arestas−→31 e−→42, enquanto as linhas pontilhadas representam um ponto de fuga infinito

(u), computado a partir das arestas−→35 e−→46.

50


Figura 5.11: Projeção dos vértices nos pontos de fuga encontrados.

cálculo, são conectados aos pontos de fuga encontrados, dando origem aos segmentos de reta

mostrados na figura 5.11.

E, finalmente, as intersecções entre essas retas representam os vértices ocultos do objeto na

cena (figura 5.12). Como pode ser observado, os vértices procurados conectar-se-ão aos vértices

com menor número de conexões.

Para o cálculo dos vértices ocultos de um hexaedro qualquer, utiliza-se o mesmo procedimento

utlizado para o cubo, pois o cálculo do ponto de fuga para ambos enquadra-se dentro do mesmo

princípio, ou seja, prolongando-se as arestas, estas encontrar-se-ão em um ponto comum da ima-

gem e esse ponto não faz parte do objeto.

Entretanto, uma pirâmide não se comporta da mesma maneira, visto que o ponto de fuga dessa

figura geométrica é representado por um de seus vértices (figura 5.13). Nota-se que os pontos de

fuga encontrados nas figuras 5.13a e 5.13b coincidem com os vértices da pirâmide classificados

como vértices que possuem três ou mais conexões. Basta, portanto, definir qual destes dois vértices

51


Figura 5.12: Computando os vértices ocultos.

(a) (b)

Figura 5.13: Cálculo do ponto de fuga para uma pirâmide: prolongando-se as arestas, o ponto de fuga érepresentado em a) pelo vértice 1 e em b) pelo vértice 3.

52


Figura 5.14: Reconstrução de uma pirâmide de base triangular.

Figura 5.15: Reconstrução de uma pirâmide de base quadrangular.

é o vértice principal da pirâmide, o vértice com o qual irá ser conectado o vértice oculto. Para isso,

foi definido um critério baseado na distância entre os vértices. O vértice com três ou mais conexões

(1 ou 3, de acordo com a figura 5.13) que apresentar a maior distância com relação aos vértices

que possuem menos de três conexões (2 e 4), será o escolhido. Baseado nessa definição, como

pode ser observado na pirâmide ilustrada na figura 5.13, o vértice principal é o de número 1.

Se o usuário optar por reconstruir uma pirâmide de base triangular simplesmente conectam-se

os vértices 2 e 4 (vértices com menos de três adjacências), criando-se, assim, um modelo tridi-

mensional do objeto (figura 5.14).

Porém, se o usuário desejar uma pirâmide de base quadrangular soma-se os vetores que for-

mam a base da pirâmide (−→32 e−→34) e encontra-se o vértice oculto 5, como mostra a figura 5.15.


Neste capítulo foi apresentado o método de trabalho proposto para a identificação de obje-

tos. O trabalho consistiu de duas etapas. Na primeira etapa foi implementado o modeloGVF de

53


contornos ativos. Esse modelo foi escolhido, principalmente, por seu poder de convergência em

superfícies côncavas, já que técnicas de modelagem baseadas em imagens dedicam-se, principal-

mente, a reconstruir cenas arquitetônicas.

Numa segunda fase, o trabalho dedicou-se a calcular as coordenadas dos vértices do objeto.

Foi elucidado neste capítulo que, para encontrar todos os vértices do objeto a fim de reconstruí-

lo, primeiramente deve-se conhecer as coordenadas dos vértices visíveis para, posteriormente,

calcular os vértices ocultos na cena.

O capítulo 4 apresenta alguns modelos teóricos utilizados na detecção de contornos e descreve,

em detalhes, o modelo GFV adotado neste trabalho. Contudo, existe na literatura uma técnica

conhecida como Transformada de Hough (Hough, 1962) que também pode ser utilizada para o

mesmo fim.

A Transformada de Hough é uma técnica de segmentação baseada em bordas utilizada na

detecção de linhas e curvas em uma imagem (Sonka et al., 1998) e, embora não seja necessário

conhecer sua posição, é preciso ter informações sobre a geometria do objeto procurado (retas,

círculos ou elipses).

Primeiramente, uma imagem em nível de cinza deve ser pré processada, por um filtro passa-

alta a fim de detectar as bordas existentes. A seguir, a imagem é binarizada por meio de um limiar,

tal que somente as bordas mais realçadas sejam mantidas (representadas por pixels escuros - 0),

tendo ao fundo um conjunto de pixels claros (pixel de valor 1).

O princípio desta técnica é que existe um número infinito de linhas que passa por um ponto

de borda qualquer, detectado pelo filtro, em orientações distintas. A proposta da Transformada é

definir quais destas linhas sobrepõem o maior número de pixels presentes na imagem binária que

correspondem às bordas.

Para tanto, cria-se um espaço discreto de Hough (no caso da detecção de retas com notação

polar, este espaço será bi-dimensional e pode ser definido pelos parâmetrosr - distância da origem

- e o ânguloθ) em que cada ponto representa uma reta. Este espaço será, então, computado e

cada ponto conterá a quantidade de pixels (na imagem binarizada) que passam por aquela reta

específica.

54


As arestas resultantes podem ser facilmente recuperadas, escolhendo-se do espaço de Hough,

os pontos (retas) que apresentarem valores altos.

No capítulo 6 serão demonstrados alguns exemplos e resultados obtidos pelo método proposto.

Foi, também, incluído um exemplo de detecção de vértices e arestas por meio da Transformada de

Hough. O desempenho desse método é comparado com aquele proposto neste trabalho.

55

CAPÍTULO

6

Resultados

Embora este projeto de pesquisa vise, além de aumentar a precisão, automatizar o processo de

modelagem, ainda faz-se necessário que o usuário defina, via interface, algumas variáveis durante

a execução do programa.

A figura 6 ilustra a interface desenvolvida na qual podem ser visualizados os parâmetros em-

pregados nas duas etapas descritas no capítulo anterior: a etapa de identificação do contorno e a

de localização dos vértices do objeto. Após dar início ao processo, a partir da seleção da imagem

desejada, o próximo passo é definir um contorno inicial e, através da adaptação dos parâmetros

apresentados no lado esquerdo da interface, encontrar o contorno do objeto de interesse.

Quando a ferramenta atingir um resultado satisfatório obtido pela correta convergência da

snake, segue-se para o processo de cálculo dos vértices desse objeto. Mais uma vez, o usuário

deverá fornecer dados que facilitem essa busca através dos parâmetros dispostos ao lado direito da

interface. Os resultados de cada passo são mostrados na parte central da figura.

Existem, ainda, parâmetros internos previamente definidos que são calculados ao longo da

execução do programa sem a interferência do usuário.

56

Resultados

Figura 6.1: Interface do programa.

57

Resultados

A seguir, serão mostrados alguns exemplos e resultados obtidos através da aplicação da técnica

desenvolvida sobre algumas figuras geométricas fornecidas na ferramenta Canoma (capítulo 3). A

influência dos parâmetros no comportamento do contorno ativo e na localização dos vértices será,

também, analisada.

6.1 Parâmetros internos

Dentre alguns parâmetros intrínsecos ao funcionamento do programa, foram definidos:

• Interpolação do conjunto inicial de pontos: a distância estabelecida entre um ponto e outro

dasnakenão deve ser maior que 3.0 pixels e menor que 0.2. Para isso, o conjunto de pontos

é dinamicamente reparametrizado a fim de que obedeça essa relação.

• Número de iterações para o cálculo do GVF: conforme descrito no capítulo 5, o campo GVF

é gerado antes da execução dasnake, portanto esse campo é computado somente uma vez

para cada imagem. Porém, embora independente dasnake, seu cálculo também é iterativo

e, de acordo com (Xu and Prince, 1998), o tempo necessário para garantir a convergência do

GVF depende do espaçamento entre os pixels dos eixos x e y (∆ x e∆ y, respectivamente)

e da quantidade de ruído da imagem (µ), tal que:

∆t <= (∆x ∗∆y)/4 ∗ µ (6.1)

Observar-se que, quanto maior o ruído (µ), mais lenta será a taxa de convergência, pois o

intervalo de tempo (∆ t) entre uma iteração e outra será menor.

Nos testes realizados, o número de iterações foi fixado em√

MxN , sendo M e N definidos

como a altura e a largura da imagem, respectivamente.

• Normalização dos mapas de arestas: todos os mapas foram normalizados entre 0 e 1.

58

Resultados

6.2 Parâmetros externos

Como dito anteriormente, os parâmetros externos são aqueles que podem ser alterados pelo

usuário, devendo ser por ele definidos a partir de características da imagem e do objeto que se

deseja encontrar.

Esses parâmetros podem ser separados em duas categorias: parâmetros dasnake, utilizados

durante a identificação do contorno, e parâmetros para identificação dos vértices.

• Parâmetros dasnake- alpha, beta, gamma, kappa e musão as cinco principais variáveis

utilizadas nessa fase do processo, sendo que:

– alphacontrola a elasticidade;

– beta- responsável pela rigidez;

– gamma- representa a viscosidade;

– kappa- peso da força externa;

– mu- quantidade de ruído presente na imagem.

Os parâmetrosalphae betadevem ser definidos pelas características do objeto de interesse

na imagem, através de uma análise de sua forma e angulações, enquantogamma, kappa e

mudevem ser baseados nas características da própria imagem e não mais no objeto.

• Parâmetros para identificação do contorno - além dos parâmetros dasnake, mais quatro

parâmetros devem ser definidos: variação angular, amostragem de pontos, pontos coinci-

dentes e a forma geométrica do objeto de interesse, conforme apresentado no capítulo 5.

A seguir serão apresentados alguns exemplos e resultados obtidos após a adaptação dos parâme-

tros acima descritos ao objeto de interesse.

A figura 6.2 representa uma pirâmide com vértices agudos. A fim de identificar corretamente o

contorno desse objeto, a variávelbetadeve tender a zero, pois um alto valor impediria o contorno

59

Resultados

Figura 6.2: a) Imagem original; b) contorno inicial definido pelo usuário e resultados dasnakeem c) após 6iterações e em d) após 4 iterações. Um alto valor para alpha em d) inibiu a expansão do contorno, resultando

em uma convergência ruim.

Figura 6.3: a) Imagem original; b) parâmetros utilizados na detecção dos vértices visíveis do objeto; c)vértices visíveis detectados e d) localização do vértice oculto para uma pirâmide de base quadrangular.

de formar ‘quinas’, ou seja, de se dobrar para formar os cantos do objeto.Alphacontrola a tensão

dasnake, portanto um valor alto para essa variável impediria o contorno de se expandir.

Dando sequência ao processo para esse objeto, os parâmetros referentes ao cálculo dos vértices

devem ser testados e adequados a fim de obter um resultado satisfatório. A figura 6.3 ilustra

os valores atribuídos a essas variáveis durante o cálculo dos vértices de uma pirâmide de base

quadrangular.

Devido a quantidade de ângulos agudos presentes no objeto da figura 6.3, uma variação angular

superior a11o não seria capaz de identificar todos os quatro vértices visíveis, enquanto que, um

60

Resultados

Figura 6.4: a) Parâmetros utilizados na detecção do contorno de um cubo; b) imagem original; c) contornoinicial definido pelo usuário e resultado dasnakeobtidos em: d) 2 iterações, após aplicação do filtro Sobel;

e) 6 iterações, após aplicação do filtro Laplaciano e f) 5 iterações, após aplicação do filtro GDDI.

valor menor localizaria falsos vértices.

Um ponto importante a ser destacado é que, neste exemplo, não foi necessária a prévia apli-

cação de um filtro, visto que se tratava de uma imagem binária. Porém, ao manipular imagens

em nível de cinza, deve-se optar por um dos filtros disponíveis na interface (Sobel, Laplaciano ou

GDDI).

A figura 6.4, ilustra o comportamento dasnakequando da seleção desses filtros. Os parâmetros

referentes à localização do contorno devem ser definidos conforme explicação anterior.

Após a correta identificação do contorno do cubo em nível de cinza e adaptação dos parâmetros

necessários, os vértices visíveis e ocultos podem ser identificados. Observa-se na figura 6.5 que o

vértice posteriormente rotulado como 7, que deveria ter sido facilmente identificado pelo sistema

e, portanto, ser classificado como um vértice visível, não é localizado na primeira etapa (vértices

visíveis), provavelmente devido à inclinação da reta ou à sua angulação. Entretanto, ao identificar

as coordenadas do vértice de número 4, os demais vértices (ocultos) podem ser localizados.

A figura 6.6 ilustra mais um caso de detecção de bordas e vértices para um cubo em nível de

cinza, onde a projeção em perspectiva é mais visível. Os pontos de fuga localizados são mostrados

na figura 6.6e.

61

Resultados

Figura 6.5: a) Imagem original; b) parâmetros utilizados para a detecção dos vértices visíveis do objeto; c)vértices visíveis detectados e d) estimativas das localizações dos vértices ocultos (7 e 8).

Figura 6.6: a) Contorno inicial definido pelo usuário na imagem original; b) parâmetros utilizados nadetecção do contorno; c) posição final dasnake; d) parâmetros utilizados na detecção dos vértices visíveisdo objeto; e) vértices visíveis localizados pela ferramenta; f) vértices de grau 1 e 2 projetados nos pontos de

fuga A e B e g) identificação dos vértices ocultos.

62

Resultados

Os procedimentos utilizados durante a localização dos vértices de um cubo podem ser gene-

ralizados para outras figuras geométricas (hexaedros), conforme ilustrado na figura 6.7.

(a)

(b)

Figura 6.7: a) Cálculo do contorno de um hexaedro e b) cálculo dos vértices do objeto.

(a) (b)

(c) (d)

Figura 6.8: a) Imagem 6.5a binarizada; Transformada de Hough para limiares b) 5; c) 20 e d) 30.

A figura 6.8 ilustra a aplicação da Transformada de Hough para a imagem 6.5a. A imagem

binária, na qual as principais bordas aparecem representadas com pixels escuros, corresponde à

63

Resultados

figura 6.8a. As figuras 6.8b, 6.8c e 6.8d são, respectivamente, o resultado da Transformada de

Hough para os segmentos de reta com quantidade de pixels (limiar no espaço de Hough) iguais a

5, 20 e 30.

Embora não sejam mostrados nas imagens, os vértices podem ser calculados de maneira trivial

na Transformada de Hough, uma vez que cada ponto no espaço designa uma reta, bastando, para

isso, computar os pontos de intersecção para cada par de retas. A dificuldade, no entanto, é definir

com precisão quais, dentre todos os vértices computados, verdadeiramente pertencem ao cubo.

Observe que a dificuldade é inversamente proporcional ao limiar no espaço de Hough (5,

20 e 30). Embora fosse trivial encontrar a intersecção das retas (possíveis vértices) não haveria

nenhuma indicação de quais destes pontos seriam os verdadeiros vértices do cubo.


Alguns resultados obtidos com a implementação da técnica desenvolvida foram mostrados

neste capítulo. Através da adaptação das variáveis, bons resultados foram obtidos para as figuras

geométricas inicialmente propostas.

Foram realizados testes aplicando-se transformada de Hough (Hough, 1962) às imagens uti-

lizadas, para fins de comparação, porém os resultados encontrados foram inferiores aos resultados

obtidos através do método proposto nesta pesquisa.

Embora a Transformada de Hough forneça um mecanismo elegante de detecção de arestas

(segmentos de reta), nenhuma informação acerca dos vértices é fornecida. No caso do método

proposto, tal informação provém do mapa de arestas, necessário para o cálculo dasnake. Por meio

desse mapa, pode-se calcular a localização dos vértices com precisão.

No caso da Transformada de Hough, essa densidade de segmentos poderia ser diminuída ao

reduzir-se a resolução do espaço de Hough (por exemplo, aumentando o valor do ângulo entre as

retas). No entanto, isso pode impedir que certos segmentos de retas sejam identificados, impedindo

a detecção posterior dos vértices.

O capítulo subseqüente apresenta as conclusões e discorre a respeito de possíveis trabalhos

64

Resultados

futuros.

65

CAPÍTULO

7

Conclusões e Trabalhos Futuros

Utilizando o conceito de contornos ativos, este trabalho propôs um mecanismo de automação

da detecção de arestas e vértices para algumas formas geométricas.

Um levantamento bibliográfico sobre ferramentas de modelagem baseada em imagens foi apre-

sentado e nenhuma funcionalidade como a descrita neste trabalho foi encontrada. Todas elas

requerem uma precisa localização dos vértices e arestas para posterior renderização, porém esse

processo é feito sempre de forma manual.

Essa nova abordagem mostrou-se bastante funcional e conseguiu atingir seus objetivos para

primitivas mais simples. Isso se deve ao fato de que o mecanismo incorpora informações ge-

ométricas do objeto a ser encontrado e, também, àsnakeimplementada,GVF, que possui um

grande poder de convergência sobre o contorno original do objeto.

As características acima citadas, conferem ao método um desempenho superior ao obtido com

técnicas tradicionalmente utilizadas para fins semelhantes como, por exemplo, a Transformada de

Hough.

66

Conclusões e Trabalhos Futuros

Trabalhos Futuros

Mesmo para formas geométricas simples, o mecanismo baseado em snake para detecção de

bordas e vértices, apresentaria um desempenho ruim se tais formas possuíssem texturas mais com-

plexas (imagine uma caixa de fósforos com desenhos e padrões aleatórios nas suas faces).

Este problema poderia ser contornado, ao incorporar a Transformada de Hough ao método

proposto. A Transformada poderia ser inicialmente aplicada a fim de eliminar o efeito das texturas

sobre as faces e localizar as principais bordas do objeto (segmentos de retas, por exemplo). O

espaço de Hough seria usado para redefinir o cálculo do mapa de arestas, do qual depende a

convergência do contorno ativo. Em locais onde há pouco incidência de segmentos de reta, o

mapa apresentaria baixa atração ou repulsão.

Alguns melhoramentos secundários, que tornariam o método mais preciso e abrangente, su-

gerem direções para outros trabalhos futuros:

• posicionamento automático do contorno inicial, por meio do cálculo de massa do objeto;

• reposicionamento manual dos pontos não computados automaticamente pelasnake;

• expansão da base de objetos com a inclusão de novas figuras geométricas, como arcos e

telhados.

67

Referências Bibliográficas

Apollo Software (2004). Photo3d. Disponível em: <http://www.photo3d.com>. Acesso em:

16/11/05.

Bianchi, A. G. C. (2003).Caracterização, Modelagem e Simulação Matemático-Computacional

da Dinâmica do Crescimento e Conexões de Células Neurais. PhD thesis, IFSC-USP.

Borshukov, G. D. (1997). New algorithms for modeling and rendering architectures from pho-

tographs. Master’s thesis, University of California at Berkeley.

Brito, J. and Coelho, L. (2002). Fotogrametria digital. Disponível em: <http://e-

foto.sourceforge.net>. Acesso em: 11/02/04.

Burschka, D., Cobzas, D., Dodds, Z., Hager, G., Jagersand, M., and Yerex, K. (2003). Recent

methods for image-based modeling and rendering.

Canoma (2004). Disponível em: <http://www.canoma.com>. Acesso em: 23/03/05.

Cantoni, V., Lombardi, L., Porta, M., and Sicard, N. (2001). Vanishing point detection: Represen-

tation analysis and new approaches. InProceedings of the IEEE International Conference on

Image Analysis and Processing, volume 11, pages 90–94.

68


Cipolla, R., Robertson, D., and Boyer, E. (1999). Photobuilder - 3d models of architectural scenes

from uncalibrated images. InProceedings of the IEEE International Conference on Multime-

dia Computing and Systems, volume 1, pages 25–31.

Cohen, L. D. (1991). On active contour models and ballons.CVGIP: Image Understand, 53:211–

218.

Cohen, L. D. and Cohen, I. (1993). Finite-element methods for active contours models and ballons

for 2d and 3d images.IEEE Transactions on Pattern Analysis and Machine Intelligence,

15(11):1131–1147.

Davatzikos, C. and Prince, J. L. (1995). An active contour model for mapping the cortex. InIEEE

Trans. Med. Imag., volume 14, pages 65–80.

Debevec, P. E. (1996).Modeling and Rendering Architecture from Photographs. PhD thesis,

University of California at Berkeley.

Debevec, P. E. (2004). Paul debevec home page. Disponível em: <http://www.debevec.org>.

Acesso em: 14/10/05.

Debevec, P. E., Taylor, C. J., and Malik, J. (1996). Modeling and rendering architecture from

photographs: A hybrid geometry- and image-based approach.Proceedings of SIGGRAPH

96, pages 11–20.

Eos System Inc. (2004). Photomodeler. Disponível em: <http://www.photomodeler.com>. Acesso

em: 28/06/05.

Foley, J. (2000). Getting there: The top ten problems left.IEEE Computer Graphics and Appli-

cations, Special Issue on the future of computer graphics, 20:66–68.

Giraldi, G. A., Feijóo, R. A., and Farias, R. C. (2004). Visualização científica apli-

cada ao estudo da hemodinâmica do sistema cardiovascular humano. Disponível em:

<http://virtual01.lncc.br/monografia>, Laboratório Nacional de Computação Científica.


69


Gonzales, R. C. (1987).Digital Image Processing. 2nd edition.

Horry, Y., Anjyo, K., and Arai, K. (1997). Tour into the picture: Using a spidery mesh interface to

make animation from a single image. InProceedings of the ACM SIGGGRAPH, New York,

pages 225–232. ACM Press/Addison-Wesley Publishing Co. New York, NY, USA.

Hough, P. V. C. (1962). A method and means for recognition complex patterns. US Patent.

Johnson, D. (2001). Tip - tour into the picture. Disponível em: <http://www-

users.itlabs.umn.edu/classes/Fall-2001/csci5980/notes/TOUR_INTO_PICTURE.ppt>.


Kang, H. W., Pyo, S. H., Anjyo, K., and Shin, S. Y. (2001). Tour into the picture using a vanishing

line and its extension to panoramic images.Eurographics, 20(3).

Kass, M., Witkin, A., and Terzopoulos, D. (1987). Snakes: Active contour models.International

Journal of Computer Vision, 1(4):321–331.

Leroy, B., Herlin, I., and Cohen, L. D. (1996). Multi-resolutions algorithms for active contour

models. In12th. Int. Conf. Analysis and Optimization of Systems, pages 58–65.

Machado, A. C. C., Galvão, L. R., Vanderlei, T. A., and Santos, W. Y. R. (2002). Uma ferramenta

de extração de bordas utilizando t-snakes.Revista Eletrônica de Iniciação Científica.

McInerney, T. and Terzopoulos, D. (1999). Topology adaptive deformable surfaces for medical

image volume segmentation.IEEE Transactions on Medical Imaging, 18(10):840–850.

McInerney, T. J. (1997).Topologically Adaptable Deformable Models for Medical Image Analysis.

PhD thesis, Department of Computer Science, University of Toronto.

Oliveira, M. (2002). Image-based modeling and rendering techniques: a survey.RITA - Revista

de informática teórica e aplicada, (2):37–66.

70


Pimentel, B. S. (2000). Segmentação de imagens médicas utilizando modelos de active con-

tours. Disponível em: <http://www.lrvpa.dcc.ufmg.br/vision/snake/artigo.htm>, Laboratório

de Visão Computacional e Robótica. Acesso em: 10/08/05.

Press, W. H., Flannery, B. P., Teukolsky, S. A., and Vetterling, W. T. (1986).Numerical Recipes:

The Art of Scientific Computing. Cambridge University Press, Cambridge (UK) and New

York, 1st edition.

Seitz, S. M. and Dyer, C. R. (1997). Photorealistic scene reconstruction by voxel coloring. In

Proceedings of the Computer Vision and Pattern Recognition Conference, pages 1067–1073.

Sethian, J. A. (1987). Numerical methods for propagating fronts. InVariational Methods for Free

Surface Interfaces, Proceedings of the Vallambrosa Conference.

Sethian, J. A. (2004). Fast marching and level set web site. Disponível em:

<http://math.berkeley.edu/ sethian>. Acesso em: 05/11/05.

Sonka, M., Hlavac, V., and Boyle, R. (1998).Image Processing, Analysis, and Machine Vision.

PWS Publishing, 2nd edition.

Stevens, L. (1999).Canoma - Manual do usuário. MetaCreations Corp., 6303 Carpinteria Avenue,

Carpinteria, CA 93013.

Xu, C. and Prince, J. L. (1997). Gradient vector flow: A new external force for snakes. InIEEE

Proc. Conf. Comp. Vis. Patt. Recog. (CVPR), pages 66–71.

Xu, C. and Prince, J. L. (1998). Snakes, shapes, and gradient vector flow.IEEE Transaction on

Image Processing, 7(3):359–369.

Xu, C. and Prince, J. L. (2000). Gradient vector flow deformable models. Handbook of Medical

Imaging, edited by Isaac Bankman, Academic Press.

Xu, C. and Prince, J. L. (2004). Active contours and gradient vector flow. Disponível em:

71


<http://iacl.ece.jhu.edu/projects/gvf>, Image Analysis and Communications Lab. Acesso em:

19/10/05.

Zuniga, O. A. and Haralick, R. M. (1987). Integrated directional derivative gradient operator.

17:508–517.

72

Livros Grátis( http://www.livrosgratis.com.br )

Milhares de Livros para Download: Baixar livros de AdministraçãoBaixar livros de AgronomiaBaixar livros de ArquiteturaBaixar livros de ArtesBaixar livros de AstronomiaBaixar livros de Biologia GeralBaixar livros de Ciência da ComputaçãoBaixar livros de Ciência da InformaçãoBaixar livros de Ciência PolíticaBaixar livros de Ciências da SaúdeBaixar livros de ComunicaçãoBaixar livros do Conselho Nacional de Educação - CNEBaixar livros de Defesa civilBaixar livros de DireitoBaixar livros de Direitos humanosBaixar livros de EconomiaBaixar livros de Economia DomésticaBaixar livros de EducaçãoBaixar livros de Educação - TrânsitoBaixar livros de Educação FísicaBaixar livros de Engenharia AeroespacialBaixar livros de FarmáciaBaixar livros de FilosofiaBaixar livros de FísicaBaixar livros de GeociênciasBaixar livros de GeografiaBaixar livros de HistóriaBaixar livros de Línguas










http://www.livrosgratis.com.br/cat_1/administracao/1







http://www.livrosgratis.com.br/cat_2/agronomia/1







http://www.livrosgratis.com.br/cat_3/arquitetura/1







http://www.livrosgratis.com.br/cat_4/artes/1







http://www.livrosgratis.com.br/cat_5/astronomia/1







http://www.livrosgratis.com.br/cat_6/biologia_geral/1









http://www.livrosgratis.com.br/cat_8/ciencia_da_computacao/1











http://www.livrosgratis.com.br/cat_9/ciencia_da_informacao/1











http://www.livrosgratis.com.br/cat_7/ciencia_politica/1









http://www.livrosgratis.com.br/cat_10/ciencias_da_saude/1











http://www.livrosgratis.com.br/cat_11/comunicacao/1







http://www.livrosgratis.com.br/cat_12/conselho_nacional_de_educacao_-_cne/1















http://www.livrosgratis.com.br/cat_13/defesa_civil/1









http://www.livrosgratis.com.br/cat_14/direito/1







http://www.livrosgratis.com.br/cat_15/direitos_humanos/1









http://www.livrosgratis.com.br/cat_16/economia/1







http://www.livrosgratis.com.br/cat_17/economia_domestica/1









http://www.livrosgratis.com.br/cat_18/educacao/1







http://www.livrosgratis.com.br/cat_19/educacao_-_transito/1









http://www.livrosgratis.com.br/cat_20/educacao_fisica/1









http://www.livrosgratis.com.br/cat_21/engenharia_aeroespacial/1









http://www.livrosgratis.com.br/cat_22/farmacia/1







http://www.livrosgratis.com.br/cat_23/filosofia/1







http://www.livrosgratis.com.br/cat_24/fisica/1







http://www.livrosgratis.com.br/cat_25/geociencias/1







http://www.livrosgratis.com.br/cat_26/geografia/1







http://www.livrosgratis.com.br/cat_27/historia/1







http://www.livrosgratis.com.br/cat_31/linguas/1







Baixar livros de LiteraturaBaixar livros de Literatura de CordelBaixar livros de Literatura InfantilBaixar livros de MatemáticaBaixar livros de MedicinaBaixar livros de Medicina VeterináriaBaixar livros de Meio AmbienteBaixar livros de MeteorologiaBaixar Monografias e TCCBaixar livros MultidisciplinarBaixar livros de MúsicaBaixar livros de PsicologiaBaixar livros de QuímicaBaixar livros de Saúde ColetivaBaixar livros de Serviço SocialBaixar livros de SociologiaBaixar livros de TeologiaBaixar livros de TrabalhoBaixar livros de Turismo

http://www.livrosgratis.com.br/cat_28/literatura/1







http://www.livrosgratis.com.br/cat_30/literatura_de_cordel/1











http://www.livrosgratis.com.br/cat_29/literatura_infantil/1









http://www.livrosgratis.com.br/cat_32/matematica/1







http://www.livrosgratis.com.br/cat_33/medicina/1







http://www.livrosgratis.com.br/cat_34/medicina_veterinaria/1









http://www.livrosgratis.com.br/cat_35/meio_ambiente/1









http://www.livrosgratis.com.br/cat_36/meteorologia/1







http://www.livrosgratis.com.br/cat_45/monografias_e_tcc/1







http://www.livrosgratis.com.br/cat_37/multidisciplinar/1





http://www.livrosgratis.com.br/cat_38/musica/1







http://www.livrosgratis.com.br/cat_39/psicologia/1







http://www.livrosgratis.com.br/cat_40/quimica/1







http://www.livrosgratis.com.br/cat_41/saude_coletiva/1









http://www.livrosgratis.com.br/cat_42/servico_social/1









http://www.livrosgratis.com.br/cat_43/sociologia/1







http://www.livrosgratis.com.br/cat_44/teologia/1







http://www.livrosgratis.com.br/cat_46/trabalho/1







http://www.livrosgratis.com.br/cat_47/turismo/1







Documents

Aplicação de contornos ativos em modelagem baseada em imagenslivros01.livrosgratis.com.br/cp088886.pdf · Este trabalho propõe a execução do projeto de uma ferramenta de auxílio