Estudo Comparativo entre os Modelos Snakes: Balloon e Gradient Vector Flow

Projeto de Computação Gráfica

Estudo Comparativo entre os Modelos Snakes:

Balloon e Gradient Vector Flow

http://www.cin.ufpe.br/~adss/cg

Projeto de Computação Gráfica

Equipe:

• Adeline Sousa (líder)• Carla Nascimento• Fábio Urquiza• Iannê Nogueira

Projeto de Computação Gráfica

Introdução a Snakes

• Snakes, ou contornos ativos, são curvas definidas no domínio de uma imagem, que se movem sob influências de forças internas (curva) e externas (imagem), procurando minimizar a sua energia.

Projeto de Computação Gráfica

Tipos de Modelos de Snakes

• Modelos Geométricos : Consideram uma curva ou superfície de

forma arbitrária, que se move em sua direção normal, de acordo com uma função velocidade F, e utilizam equações de movimento para rastrear a evolução desta curva.

Projeto de Computação Gráfica

Tipos de Modelos de Snakes

• Modelos Paramétricos • A snake é definida como uma curva

que se move no domínio de uma imagem para minimizar a função de energia :

• Também conhecido como modelo tradicional.

dssvsvsv ext ))((|)("||)('|(2

1 221

0

]1,0[)),(),(()( ssysxsv

Projeto de Computação Gráfica

Evolução Algumas propostas para a resolução dos problemas

do modelo tradicional:

• Distance Snakes: Substitui a energia externa do modelo tradicional por um mapeamento da distância euclidiana entre a curva e o edge map.

• Balloon Snakes: Acrescenta um componente de força normal ao vetor de forças externas da curva.

• Gradient Vector Flow: Define o modelo de forças externas utilizando um novo campo potencial estático denominado gradient vector flow.

Projeto de Computação Gráfica

O Projeto

• Inicialmente, seriam estudados os algoritmos Distance Based e o GVF, devido a falta de documentação sobre o modelo Distance, decidiu-se comparar os modelos Balloon e GVF.

• Estes modelos foram implementados baseando-se no algoritmo Greedy.

Projeto de Computação Gráfica

Algoritmo Greedy

• Proposto por William e Shah• Variação do modelo tradicional, com

convergência mais rápida (O(nm) x O(nm³)), porém mais sensível a ruído

• Calcula a energia total para cada ponto da snake e sua vizinhança e o move para a posição de menor energia.

Projeto de Computação Gráfica

Algoritmo Greedy – Deformação da Snake

Projeto de Computação Gráfica

43

56

39

67

34

21

77

54

29

43

56

39

67

34

21

77

54

29

Algoritmo Greedy – Deformação da Snake

Projeto de Computação Gráfica

Adaptação

• O algoritmo Greedy original faz uso de diferentes pesos para a rigidez , elasticidade e imagem para cada ponto da curva.

• Na implementação dos nossos algoritmos, usamos apenas um único valor dos pesos para todos os pontos.

Projeto de Computação Gráfica

Balloon Snake

Projeto de Computação Gráfica

Balloon Snake

Projeto de Computação Gráfica

Balloon Snake

• Idéia principal: Acrescentar uma componente de força normal à curva ao vetor de forças externas da snake para promover um crescimento ou encolhimento uniforme do balloon.

||||1 P

PsnF

Projeto de Computação Gráfica

Balloon Snake

• Sensível à inicialização da curva. • Os coeficientes de elasticidade e rigidez

têm grande influência no comportamento da snake.

• Pode ser inicializada dentro ou fora da imagem, porém o usuário precisa indicar se o balloon deve contrair ou expandir.

• Se a curva inicial corta a imagem, não se consegue decidir para que direção se mover (expandir ou encolher).

Projeto de Computação Gráfica

Cálculo do Vetor Normal• Cálculo do vetor normal a cada ponto

da curva.• Dada uma curva ,definida

como:

• O vetor tangente é calculado através da fórmula: .

• O vetor normal é encontrado utilizando-se a seguinte definição:

],[,0)(,],[: 2 battba

||)('||

)(',

||)('||

)('

t

tx

t

tyVn

))(),(( tytxt

))('),('()(' tytxt

Projeto de Computação Gráfica

Cálculo do Vetor Normal à Snake

•Para o caso discreto, utilizamos a seguinte definição de vetor tangente, onde i é o índice do ponto da snake:

• O vetor normal é dado por:

|||||||| 1

1

1

1

ii

ii

ii

iii VV

VV

VV

VVV

),(xy iii VVN

Projeto de Computação Gráfica

Cálculo da Energia do Balloon

• Energia abordada como trabalho para realizar um deslocamento

• W = deslocamento x força• Força = Força Normal• Deslocamento = Distância entre

um ponto da curva e seus vizinhos

Projeto de Computação Gráfica

Cálculo da Energia do Balloon

Vetor Normal (Vn)

Vetor Deslocamento (Vd)

nd VVEnergia ,

Projeto de Computação Gráfica

Gradiente

101

202

101

121

000

121

yfxfyxf

,),(

• Mede variação de intensidade

• Realça arestas

• Calculado de forma discreta através das máscaras:

yfxf

Projeto de Computação Gráfica

Gradiente

Projeto de Computação Gráfica

Laplaciano

• Informação direcional não disponível; • Aumenta o ruído nas imagens • Calculado por aproximação discreta, através da

matriz:

010

141

010

2

2

2

2

),(2

y

f

x

fyxf

Projeto de Computação Gráfica

Laplaciano

Projeto de Computação Gráfica

Gradient Vector Flow Snake

Projeto de Computação Gráfica

Gradient Vector Flow Snake

Edge Map:

• - para imagens em preto e branco

• - para imagens em tons de cinza

2|),(| yxIext

2|),)(*(| yxIGext

),(),( yxyxf ext

Projeto de Computação Gráfica

Gradient Vector Flow Snakes

Edge Map:Possui três propriedades principais:1. tem vetores apontando para as

arestas e, nas arestas, são normais às mesmas

2. Esses vetores ( ) tem grande magnitude apenas nas vizinhas das arestas

3. Em regiões homogêneas, onde I(x,y) é constante, é próximo de zero

f

f

f

Projeto de Computação Gráfica

Gradient Vector Flow Snakes

• Define um novo campo potencial denominado Gradient Vector Flow (GVF)

• O GVF possui campos que apontam em direção às bordas do objeto, mas que variam suavemente em regiões homogêneas

Projeto de Computação Gráfica

Gradient Vector Flow Snake- Campo potencial

Campo potencial do GVF

Visão Ampliada do campo

Projeto de Computação Gráfica

Gradient Vector Flow Snake

• Definido como o campo vetorial

que minimiza a energia funcional:

• Computado através de um processo de

difusão dos vetores gradiente do edgemap da imagem

)),(),,((),( yxvyxuyxg

yxyxyxddfvfvvuu 222222

||||)(

Projeto de Computação Gráfica

GVF - Características

• Consegue convergir sobre formas côncavas;

• Em termos de distância do objeto, é pouco sensível à inicialização;

• Não é necessário conhecimento a priori, a respeito da expansão ou contração.

Projeto de Computação Gráfica

Campo Potencial GVF x Balloon

• Estático• Nem puramente

irrotacional, nem puramente solenoidal

• Denso

• Dinâmico• Irrotacional• Esparso

Projeto de Computação Gráfica

Resultados

Projeto de Computação Gráfica

Resultados do Balloon

Parâmetros:

Elasticidade: 0,8Rigidez: -0,4Energia Externa: -1,0Pressão:-0,6

Projeto de Computação Gráfica

Resultados do Balloon

Parâmetros Utilizados:

Elasticidade: 0,2Rigidez: 0,2Energia Externa: -0,6Pressão:0,4

Projeto de Computação Gráfica

Resultados do Balloon

Parâmetros Utilizados:

Elasticidade: 0,6Rigidez: 0,4Energia Externa: -1,0Pressão:-0.6

Projeto de Computação Gráfica

Resultados do Balloon

Parâmetros Utilizados:

Elasticidade: -0.4Rigidez: -0.2Energia Externa: 1Pressão:0,4

Projeto de Computação Gráfica

Dificuldades Encontradas

• Conceitos matemáticos• Conceitos de Energia da imagem• Encontrar material sobre o

algoritmo Distance Based • Tempo para desenvolvimento do

projeto

Projeto de Computação Gráfica

Extensões do Projeto

• Adicionar outros modelos de snakes

• Melhorar a visualização da comparação dos modelos de snakes

• Adaptar o software para trabalhar com imagens coloridas

Projeto de Computação Gráfica

Referências

• Dumitras, A.; Venetsanopoulos, A. N., A comparative study of snake models with application to object shape description in bi-level and gray-level images. Proceedings of IEEE-Eurasip Workshop on Nonlinear Signal and Image Processing, Baltimore, USA, 2001

• Xu, C.; Prince, J. L., Gradient Vector Flow: A New External Force for Snakes. Proc. IEEE Conf. on Comp. Vis. Patt. Recog. (CVPR), Los Alamitos: Comp. Soc. Press, pp. 66-71, June 1997

• Xu, C.; Prince, J. L., Snakes, Shapes, and Gradient Vector Flow. IEEE Transactions on Image Processing, 359-369, March 1998.

• Cohen, L.D., On active contour models and ballons, CVGIP: Image Understanding, vol.53, no.2, pp.211-218, March 1991.

Projeto de Computação Gráfica

Referências

• Cohen, L.D.; Cohen, I., Finite-element methods for active contour models and ballons for 2-D and 3-D images, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.15, no.11,pp.1131-1147, November 1993.

• Shulze, M.A.; Active Contours Applet. URL: http://www.markschulze.net/snakes/index.html (22 abril 2002)

• Krasilovskiy ,S.; Active Contours. URL: http://web.mit.edu/stanrost/www/cs585p3/p3.html (22 abril 2002)

• Weissetein’s, Eric. World of Mathematics. URL : http://mathworld.wolfram.com/ (22 abril de 2002)

• Departamento de Ciência da Computação Unicamp - Processamento de Imagens. URL: http://www.dcc.unicamp.br/~cpg/material-didatico/mo815/9802/curso/node73.html (22 abril de 2002)