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
v(s)  ( x(s), y(s)),s  [0,1]
que se move no domínio de uma imagem
para minimizar a função de energia :
1
   ( | v' ( s ) | 2   | v" ( s) | 2  ext (v( s)) ds
0 2
1
• Também conhecido como modelo tradicional.
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
•
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
modelo tradicional por um mapeamento da
distância euclidiana entre a curva e o edge map.
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
Algoritmo Greedy –
Deformação da Snake
43 56 39
67 34 21
77 54 29
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.

F   1n s   
Projeto de Computação Gráfica
P
|| P ||
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  t   ( x(t ), y(t )) ,definida
como:
 : [a, b]  2 ,  (t )  0, t  [a, b]
• O vetor tangente é calculado através da
fórmula:  ' (t )  ( x' (t ), y' (t )) .
• O vetor normal é encontrado utilizando-se a
seguinte definição: Vn    y' (t ) , x' (t ) 
 ||  ' (t ) || ||  ' (t ) || 


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:
Vi  Vi 1
Vi 1  Vi
Vi 

|| Vi  Vi 1 || || Vi 1  Vi ||
• O vetor normal é dado por:
Ni  (Vi y ,Vix )
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
Deslocamento
(Vd)
Vetor Normal
(Vn)
Energia Vd ,Vn
Projeto de Computação Gráfica
Gradiente
f ( x, y) 

f
x
, fy

• Mede variação de intensidade
• Realça arestas
• Calculado de forma discreta através
das máscaras:
fx
  1 0  1


 2 0 2 
 1 0 1 


  1  2  1


y 0 0 0
1 2 1


f
Projeto de Computação Gráfica
Gradiente  
Projeto de Computação Gráfica
Laplaciano
 f ( x, y ) 
2

2f
x 2

2f
y 2

• Informação direcional não disponível;
• Aumenta o ruído nas imagens
• Calculado por aproximação discreta, através
da matriz:
 0 1 0


 1 4 1
 0 1 0


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:
f ( x, y)   ext ( x, y)
• ext   | I ( x, y) |2 - para imagens em
preto e branco
2



|

(
G
*
I
)(
x
,
y
)
|
• ext
- para imagens em

tons de cinza
Projeto de Computação Gráfica
Gradient Vector Flow Snakes
Edge Map:
Possui três propriedades principais:
1. f tem vetores apontando para as arestas
e, nas arestas, são normais às mesmas
2. Esses vetores (f ) tem grande magnitude
apenas nas vizinhas das arestas
3. Em regiões homogêneas, onde I(x,y) é
constante, f é próximo de zero
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 SnakeCampo potencial
Visão Ampliada do campo
Campo potencial do GVF
Projeto de Computação Gráfica
Gradient Vector Flow Snake
• Definido como o campo vetorial
g ( x, y)  (u( x, y), v( x, y))
que minimiza a energia funcional:
    (u x  u y  v x  v y ) | f | 2 | v  f | 2 d x d y
2
2
2
2
• Computado através de um processo de
difusão dos vetores gradiente do edge
map da imagem
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,8
Rigidez: -0,4
Energia Externa: -1,0
Pressão:-0,6
Projeto de Computação Gráfica
Resultados do Balloon
Parâmetros Utilizados:
Elasticidade: 0,2
Rigidez: 0,2
Energia Externa: -0,6
Pressão:0,4
Projeto de Computação Gráfica
Resultados do Balloon
Parâmetros Utilizados:
Elasticidade: 0,6
Rigidez: 0,4
Energia Externa: -1,0
Pressão:-0.6
Projeto de Computação Gráfica
Resultados do Balloon
Parâmetros
Utilizados:
Elasticidade: -0.4
Rigidez: -0.2
Energia Externa:
1
Pressã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 bilevel 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.11311147, 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/materialdidatico/mo815/9802/curso/node73.html (22 abril de 2002)
Projeto de Computação Gráfica