FACULDADE DE INFORMÁTICA DE PRESIDENTE
PRUDENTE
CONTORNOS ATIVOS SNAKES PARA A SEGMENTAÇÃO DE
IMAGENS DIGITAIS
FAGNER DANIEL DE MELO
Presidente Prudente – SP
2005
FACULDADE DE INFORMÁTICA DE PRESIDENTE
PRUDENTE
CONTORNOS ATIVOS SNAKES PARA A SEGMENTAÇÃO DE
IMAGENS DIGITAIS
FAGNER DANIEL DE MELO
Trabalho monográfico apresentado no
curso de graduação, Bacharelado em
Ciência da Computação, como requisito
parcial para sua conclusão.
Área de concentração: Processamento
Gráfico.
Orientadores:
MSc. Francisco Assis da Silva
MSc. Leandro Luiz de Almeida
Presidente Prudente – SP
2005
FICHA CATALOGRÁFICA
004
MELO, Fagner Daniel.
Contornos Ativos Snakes para a Segmentação
de Imagens Digitais Fagner Daniel de Melo. –
Presidente Prudente: UNOESTE: Universidade do
Oeste Paulista, 2005.
84p. : il
Monografia (Graduação) – Universidade do
Oeste Paulista – UNOESTE, Presidente
Prudente, SP, 2005.
Bibliografia
1. Segmentação de Imagens, 2. Contornos
Ativos. 3. Snake. I. Autor. II. Título.
DEDICATÓRIA
Dedico este trabalho a minha mãe Maria Rodrigues de Melo e ao meu
pai Antonio de Melo, que nunca mediram esforços e sempre estiveram presentes em
todos os momentos de sua realização. Aos meus irmãos Fabio, Fernando e Flávia
pelo carinho e confiança.
AGRADECIMENTOS
A minha família que, em todos os momentos de realização desta
pesquisa, esteve presente. A minha namorada que esteve sempre presente ao meu
lado com toda a sua irreverência.
Agradecimentos também ao professor orientador, MSc. Francisco Assis
da Silva e ao professor Co-Orientador, MSc. Leandro Luiz de Almeida que, na
rigidez de seus ensinamentos, fez aprimorar meus conhecimentos.
Em especial ao professor, Dr. Almir Olivette Artero, pela amizade e
auxílio no desenvolvimento do projeto.
Aos meus amigos Amandia, Diogo, Eli, Julierme, Marco Aurélio, Rafael,
Sidney e Vanderlei pelo companheirismo e os muitos momentos de alegria
compartilhados.
EPÍGRAFE
“[...] A imaginação é mais importante que o conhecimento. [...]”
Albert Einstein
MELO, Fagner Daniel. Contornos Ativos Snakes para a Segmentação de
Imagens Digitais. Presidente Prudente: UNOESTE, 2005. Monografia de
Graduação.
Orientador: MSc. Francisco Assis da Silva
Co-Orientador: MSc. Leandro Luiz de Almeida
RESUMO
Há alguns anos os métodos de detecção de bordas vêem se tornando um
importante recurso utilizado no processo de Segmentação de Imagens. Concentramse grandes esforços em experimentos de novas técnicas, que buscam suprir alguns
problemas encontrados nos métodos mais antigos, cujos resultados são publicações
nos mais conceituados periódicos científicos, tais como o método Gradient Vector
Flow e o T-Snakes. O método de Contornos Ativos Snake é uma solução para a
segmentação de imagens digitais, que possui a característica de movimentar uma
curva de maneira dinâmica sobre a imagem, até que se alinhe às bordas do objeto
de interesse. Este projeto apresenta o desenvolvimento de um novo método de
contornos ativos Snake que, baseado no modelo tradicional proposto por Kass,
Witkin e Terzopoulos, e nas suas evoluções, solucione os problemas dos métodos
tradicionais de forma simples e com desempenho computacional significativo. Para
tanto apresenta-se uma ferramenta para a execução dos métodos Snakes
desenvolvidos, de acordo com algumas energias envolvidas no processo, e que
servirá de base para aplicações em áreas específicas.
MELO, Fagner Daniel. Contornos Ativos Snakes para a Segmentação de
Imagens Digitais. Presidente Prudente: UNOESTE, 2005. Graduation Monograph.
Adviser: MSc. Francisco Assis da Silva
Co-Adviser: MSc. Leandro Luiz de Almeida
ABSTRACT
The some years ago the edges detention methods it became an important resource
used in the Images Segmentation process. Great efforts are concentrated in
experiments of new techniques to supply some problems found in the old methods,
whose resulted are publications in the best scientific periodic such as the Gradient
method Flow Vector and the T-Snakes. The Active Contours Snake method is a
solution for the segmentation of digital images. It has the characteristic to motion a
curve in a dynamic way on the image until found the edges of the interest object. This
project presents the development of a new Snake active contours method that based
in the traditional model by Kass, Witkin and Terzopoulos and in its evolutions, solves
the problems of the traditional methods of simple form and with significant
computational performance. A tool for the execution of the developed Snakes
methods is presented, in accordance with some involved energies in the process,
and that it will serve of base for applications in specific areas.
LISTA DE FIGURAS
FIGURA 1 – Representação da segmentação por Detecção de Bordas (OLIVEIRA,
2000). .................................................................................................................14
FIGURA 2 - Aplicação do Modelo Snake. .................................................................15
FIGURA 3 – Representação de uma Imagem Digital (RIBEIRO, 1998)....................19
FIGURA 4 – Arranjo matricial com respectivos níveis de cinza.................................20
FIGURA 5 – Representação: Imagem original e imagem com ruído (RIBEIRO, 1998).
...........................................................................................................................21
FIGURA 6 – Aplicação do filtro da média (RIBEIRO, 1998). .....................................22
FIGURA 7 – Aplicação do filtro da mediana (RIBEIRO, 1998). .................................24
FIGURA 8 – Curva de grau dois, definida a partir de três pontos (OLIVEIRA, 2000).
...........................................................................................................................25
FIGURA 9 – Representação da ação da curva do modelo de contornos ativos
(SILVA, 2003).....................................................................................................28
FIGURA 10 – Direção da força elástica atuando sobre um ponto pi. (OLIVEIRA,
2000) ..................................................................................................................32
FIGURA 11 – Ponto de contorno vi sobre a ação da energia de continuidade
(OLIVEIRA, 2000). .............................................................................................34
FIGURA 12 – Ação da força balão sobre um contorno inicial. ..................................35
FIGURA 13 – Utilização da matriz Egrad (7 x 7) para a obtenção da energia baseada
em gradiente (OLIVEIRA, 2000). .......................................................................38
FIGURA 14 – (a) Imagem original contendo alguns objetos (bordas) e algumas
terminações e (b) Snake obtida (OLIVEIRA, 2000)............................................39
FIGURA 15 – Algoritmo para contornos ativos (TRUCCO, 1998). ............................43
FIGURA 16 – (a) Imagem original com seu contorno inicial e (b) contorno final obtido
com o método original (XU; PRINCE, 1997). .....................................................44
FIGURA 17 – Determinação de uma nova força baseada no fluxo do vetor gradiente
(GVF) (XU; PRINCE, 1997)................................................................................45
FIGURA 18 – (a) contorno inicial, (b) contorno final obtido com o modelo de energias
tradicional, (c) contorno inicial (definido longe das bordas do objeto), (d)
contorno final utilizando GVF (XU; PRINCE, 1997). ..........................................47
FIGURA 19 – (a) contorno inicial (passando através das bordas do objeto), (b)
contorno obtido utilizando GVF (c) contorno inicial, aplicado no interior de um
conjunto de pontos (contorno subjetivo) e (d) resultado obtido utilizando GVF
(XU; PRINCE, 1997). .........................................................................................48
FIGURA 20 – (a) Imagem médica e o contorno inicial, (b) contorno final utilizando
GVF (OLIVEIRA, 2000). .....................................................................................48
FIGURA 21 – Triangulação Coxeter-Freudental. ......................................................49
FIGURA 22 – Representação do novo modelo em um determinado estado de
evolução (MACHADO, 2003). ............................................................................51
FIGURA 23 – Extração de atributos para objetos previamente segmentados via
extração de bordas (SÁ, 2005). .........................................................................53
FIGURA 24 – Contagem e mensuração automática de fibras musculares sem um
pré-processamento. ...........................................................................................54
FIGURA 25 – Contagem e mensuração automática de fibras musculares após a
etapa de pré-processamento. ...........................................................................54
FIGURA 26 – Utilização de contornos ativos para a determinação da área do disco
ótico. ..................................................................................................................55
FIGURA 27 – Utilização de contornos na análise de avalanches de neve, (a)
contorno obtido em um momento e (b) contornos obtidos em momentos
diferentes mostram a evolução da avalanche de neve. .....................................55
FIGURA 28 – Em análise o ponto p1: a deformação é iterativa e ocorre deslocando o
ponto analisado para um novo ponto central, que é o produto vetorial entre os
snaxels de p0p1 e p1p2. O processo segue iterativamente para todos os pontos
iterativamente.....................................................................................................58
FIGURA 29 – Em análise o ponto p1: a deformação é iterativa e ocorre deslocando o
ponto analisado em direção ao baricentro da curva. O processo segue
iterativamente para todos os pontos iterativamente...........................................59
FIGURA 30 – Representação da direção dos vetores normais para o processo de
expansão da curva.............................................................................................61
FIGURA 31 – Aplicação da energia externa utilizando-se de um limiar de duas
classes de tons de cinza. O histograma representa a quantidade de tons de
cinza da imagem original e da imagem sob o efeito limiar. ................................62
FIGURA 32 – Aplicação da energia externa utilizando-se de um limiar de duas faixas
de tons de cinza. O histograma representa a quantidade de tons de cinza da
imagem original e da imagem sob o efeito limiar (OLIVEIRA, 2000). ................63
FIGURA 33 – Aplicação da força de rotação.............................................................65
FIGURA 34 – Convolução Aperiódica. ......................................................................66
FIGURA 35 – Aplicação do filtro da média. ...............................................................67
FIGURA 36 – Exemplo da substituição do pixel mediano. ........................................67
FIGURA 37 – Aplicação do filtro da mediana. ...........................................................68
FIGURA 38 – Máscara do Operador Laplaciano.......................................................68
FIGURA 39 – Aplicação do Filtro Laplaciano com a operação de Negação de Cores
...........................................................................................................................68
FIGURA 40 – Aplicação do Filtro de Binarização pela Média Global. .......................69
FIGURA 41 – Aplicação do Filtro Limiar igual a 5. ....................................................70
FIGURA 42 – Agrupamento de Níveis de Cinza. ......................................................70
FIGURA 43 – Equação do Filtro Limiar. ....................................................................70
FIGURA 44 – Interface principal da Ferramenta de Segmentação por Contornos
Ativos Snake. .....................................................................................................71
FIGURA 45 – Representação da Classe TSnakes....................................................72
FIGURA 46 – Representação da Classe Snakes......................................................73
FIGURA 47 – Representação gráfica da estrutura de dados do projeto. ..................74
FIGURA 48 – Imagem recém aberta pela ferramenta...............................................77
FIGURA 49 – Configuração da Snake inicial.............................................................77
FIGURA 50 (a) – Deformação da Snake. ..................................................................78
FIGURA 50 (b) – Divisão da Snake...........................................................................78
FIGURA 51 – Contorno final dos objetos. .................................................................79
FIGURA 52 – Passos de uma situação crítica do experimento e resolução via Junção
de duas Snakes. ................................................................................................81
SUMÁRIO
1 INTRODUÇÃO......................................................................................................11
1.1
1.2
1.3
1.4
1.5
Classificação dos Métodos de Segmentação....................................................12
Modelo Baseado em Bordas e Contornos Ativos ..............................................13
Objetivos, Justificativas e Motivações do Projeto..............................................16
Trabalhos Correlatos e suas Aplicações ...........................................................17
Estrutura desta Monografia ...............................................................................18
2 CONCEITOS BÁSICOS .......................................................................................19
2.1 Imagem Digital ..................................................................................................19
2.2 Pré-Processamento...........................................................................................20
2.2.1 Ruídos ............................................................................................................21
2.2.2 Filtros..............................................................................................................21
2.2.2.1 Filtros da Média ...........................................................................................22
2.2.2.2 Filtro da Mediana .........................................................................................23
2.3 Curvas Splines ..................................................................................................24
3 O MODELO DE CONTORNOS ATIVOS ..............................................................27
3.1 Energia Interna..................................................................................................30
3.1.1 Modelo baseado na elasticidade e rigidez da curva .......................................30
3.1.2 Modelo Baseado na Continuidade e Força Balão ..........................................32
3.1.2.1 Energia de Continuidade .............................................................................33
3.1.2.2 Força Balão..................................................................................................34
3.2 Energia Externa.................................................................................................36
3.2.1 Energia da Intensidade da Imagem ................................................................36
3.2.2 Energia do Gradiente da Imagem...................................................................37
3.2.3 Energia das Terminações...............................................................................39
3.2.4 Outras energias externas ...............................................................................40
3.3 Energia Confinada.............................................................................................40
3.4 Normalização das Energias ..............................................................................41
3.5 Algoritmo Greedy ..............................................................................................41
4 OS MODELOS: GRADIENT VECTOR FLOW (GVF) E T-SNAKES ....................44
4.1 A nova força externa: Gradient Vector Flow......................................................44
4.2 O modelo T-Snakes ..........................................................................................49
5 APLICAÇÕES DOS MÉTODOS SNAKES ...........................................................52
5.1
5.2
5.3
5.4
Sistema Semi-Automático para Análise de Imagens Digitais ............................52
Contagem e Mensuração de Fibras Musculares ...............................................53
Medição do Disco Ótico ....................................................................................55
Análise de Avalanches ......................................................................................55
6 O PROJETO: DESENVOLVENDO UM MODELO DISCRETO DE SNAKE ........56
6.1 Energias Desenvolvidas....................................................................................57
6.1.1 Energias Internas ...........................................................................................57
6.1.1.1 Força Tradicional .........................................................................................57
6.1.1.2 Força Baricentro ..........................................................................................59
6.1.1.3 Força Mista ..................................................................................................60
6.1.1.4 Força Balão Tradicional e Força Balão Baricentro.......................................61
6.1.2 Energia Externa ..............................................................................................61
6.1.3 Energia Confinada ..........................................................................................64
6.1.3.1 Força de Rotação ........................................................................................64
6.1.3.2 Criação de Pontos Intermediários................................................................65
6.2 Filtros de Pré-Processamento Desenvolvidos...................................................65
6.2.1 Filtro da Média................................................................................................66
6.2.2 Filtro da Mediana ............................................................................................67
6.2.3 Filtro Laplaciano .............................................................................................68
6.2.4 Binarização pela Média: Local e Global..........................................................69
6.2.5 Filtro Limiar.....................................................................................................69
7 A FERRAMENTA DESENVOLVIDA ....................................................................71
7.1 Estruturas Utilizadas .........................................................................................72
7.2 Preenchimento dos Campos e Passos para a Deformação..............................75
7.3 Considerações Adicionais .................................................................................79
8 EXPERIMENTOS E RESULTADOS.....................................................................80
9 CONCLUSÕES.....................................................................................................82
REFERÊNCIAS BIBLIOGRÁFICAS.........................................................................83
11
1
INTRODUÇÃO
A segmentação (BALAN, 2003), é um processo essencial para análise
e identificação de características marcantes em uma imagem. Seu objetivo é
identificar os objetos que compõem uma cena, sendo, na maioria dos casos, o
grande responsável pelo sucesso ou fracasso dos resultados obtidos da análise.
Esta etapa consiste em abstrair objetos para utilizá-los em processos posteriores
como classificação, reconhecimento, dentre outros.
Algumas das ocorrências que dificultam a tarefa de segmentar uma
imagem de forma eficiente são (MIYASAKI, 2003):
•
Existência de ruído na imagem: o nível de ruído em uma imagem
pode ser devido a vários fatores: deficiência dos dispositivos de
imageamento, interferências eletromagnéticas, entre outros;
•
Baixo contraste na imagem: em algumas situações os objetos
presentes na imagem não apresentam uma boa separação nos tons
de cinza ou mesmo cores;
•
Falta de uma iluminação adequada: pode levar ao aparecimento de
áreas de sombra, que podem induzir a segmentação de um único
objeto em dois pedaços (área clara e área escura).
Para tanto existe a etapa que visa garantir em grande parte a correção
das imperfeições resultantes das imagens, sendo esta definida de préprocessamento de imagens. A função desta etapa é aprimorar as qualidades da
imagem para a etapa de segmentação, sendo feita por meio de filtros especializados
que visam a sua suavização (MARQUES, 1999).
Além da etapa de pré-processamento na segmentação de imagens,
pode-se utilizar uma outra etapa, que é também conhecida como pósprocessamento. O pós-processamento é utilizado para completar a tarefa de
segmentação, para os casos em que esta não obtiver bons resultados (OLIVEIRA,
2000).
12
Para o processo de segmentação são utilizadas duas propriedades
básicas: similaridade e descontinuidade. A similaridade procura pixels com a mesma
tonalidade ou pertencentes à mesma faixa de intensidade nos níveis de cinza. A
descontinuidade procura pixels que possuam tonalidades diferentes nos níveis de
cinza.
1.1
Classificação dos Métodos de Segmentação
De acordo com Gonzalez (GONZALEZ, 1987), os métodos de
segmentação podem ser classificados em: Limiarização, Detecção de Bordas e
Baseado em Regiões.
•
Limiarização: é considerado o método mais simples, onde todos os
pixels que pertencem a uma mesma faixa de intensidade compõem
uma mesma região. Sua funcionalidade se baseia na propriedade
de similaridade;
•
Detecção de Bordas: é usado para localizar regiões na imagem
onde os níveis de cinza dos pixels variam bruscamente; num pixel a
intensidade é uma e nos pixels imediatamente ao seu redor
possuem uma intensidade bem diferente. São conhecidas como
descontinuidades e podem aparecer na forma de pontos isolados,
linhas, segmentos ou curvas. A partir das descontinuidades são
formados os contornos dos objetos;
•
Crescimento por Regiões: tem o intuito de aumentar pequenos
grupos de pixels em grupos maiores, baseado em um conjunto
inicial, a partir deste conjunto, se junta os pixels vizinhos que
possuem propriedades semelhantes, como cor, textura, dentre
outras propriedades.
Existem vários métodos utilizados para a segmentação de imagens,
alguns muito antigos e a maioria apresentam deficiências em algumas situações.
13
Alguns, quando aplicados em imagens com altos níveis de ruídos e com diferentes
características de contexto podem não apresentar resultados satisfatórios. Sendo
assim, novos métodos que apresentem bons resultados, mesmo em situações
adversas, continuam ainda sendo investigados.
Este projeto utiliza a propriedade de descontinuidade e segue a
classificação segundo as abordagens envolvidas no processo de detecção de
bordas.
1.2
Modelo Baseado em Bordas e Contornos Ativos
Há alguns anos o assunto detecção de bordas vem desafiando
pesquisadores da área de Processamento de Imagens, cada vez mais surgem
experimentos de novas técnicas, cujos resultados são publicados nos mais
conceituados periódicos científicos mundiais. Este modelo é um dos processos
existentes para a segmentação de imagens digitais que vem apresentando
resultados satisfatórios. Por sua vez, ele tem a tarefa de dividir uma imagem em
suas unidades significativas, visando realçar as bordas de objetos de uma cena,
para posterior análise e compreensão.
De acordo com Gonzalez (GONZALEZ, 2000), a suposição inicial da
abordagem baseada em bordas é que ela é fundamental no processo de análise de
imagens, porque as bordas definem o contorno dos objetos presentes na imagem.
Sendo assim, justifica-se o grande interesse dos pesquisadores no estudo e
desenvolvimento de métodos voltados a esta área.
Como exemplo da abordagem tradicional baseada na detecção de
bordas, tem-se a figura 1, onde, dada uma imagem original com alto nível de ruído
realiza-se a segmentação por detecção de bordas mostrando os resultados obtidos
dessa segmentação.
14
(a)
(b)
(c)
(d)
FIGURA 1 – Representação da segmentação por Detecção de Bordas (OLIVEIRA, 2000).
De acordo com a figura 1 tem-se: (a) uma imagem original
apresentando alto nível de ruído, (b) imagem de bordas, (c) contorno obtido por
vetorização (utilizando linhas retas ao invés de uma abordagem via Splines) e (d)
forma esperada.
Grande parte dos métodos existentes para a segmentação de imagens
possui
algumas
restrições
quando
aplicados
em
imagens
de
diferentes
características de contexto, como altos níveis de ruídos e contraste, não
apresentando resultados satisfatórios no processo. Um modelo que, mesmo nestas
situações, apresenta uma melhor continuidade do contorno é a segmentação por
contornos ativos Snakes.
O Modelo de Contorno Ativo é uma vigorosa técnica de análise de
imagens, pois oferecem um único e poderoso método que mistura geometria, física e
teoria de aproximação.
Este modelo é caracterizado por tentar ajustar uma curva sobre a
borda de um objeto da imagem. As Snakes (KASS, 1988) são modelos que possuem
15
a capacidade de se deformar até se adequar ao objeto de interesse. A figura 2 trata
um contorno inicial (curva) e o resultado final da aplicação do modelo.
FIGURA 2 - Aplicação do Modelo Snake.
Com a deformação, as Snakes não retornam ao seu formato original,
pelo fato de que forças atuam sobre ela (KASS, 1988). Estas forças são devidas a
energias, que são conhecidas por energia interna e energia externa. A energia
interna é responsável por deformar a Snake enquanto a energia externa é
responsável por puxar, atrair a Snake em direção à borda do objeto. O termo modelo
deformável refere-se a uma curva que se deforma sob ação de forças internas e
externas.
O campo de atuação deste modelo é extensamente vasto, englobando
aplicações que envolvem detecção de bordas, modelagem de formas, segmentação
e rastreamento de movimentos.
Problemas associados principalmente com a inicialização da curva e
convergência a limites côncavos limitaram a utilidade das Snakes tradicionais. O
modelo do Fluxo de Vetor Gradiente (GVF) é uma nova força externa para contornos
ativos que resolve ambos os problemas em grande parte. Esta força externa é
computada como uma difusão dos vetores gradiente dos níveis de cinza derivados
da imagem. Com isso tem-se como resultado a insensibilidade a inicialização e uma
maior flexibilidade do contorno quando aplicada em regiões côncavas. Outro modelo
que apresenta resultados satisfatórios é o T-Snakes, que visa o tratamento de
mudanças topológicas dos objetos da imagem.
16
1.3
Objetivos, Justificativas e Motivações do Projeto
O objetivo desse projeto é realizar o desenvolvimento e implementação
de um novo modelo para a segmentação de imagens digitais via a abordagem de
contornos ativos Snake e que apresente uma evolução do modelo Snake tradicional.
Para tanto, realizou-se a investigação da utilização de contornos ativos Snakes na
segmentação de imagens digitais e conseqüentemente a análise e confronto dos
resultados obtidos desta investigação, objetivando o desenvolvimento de um modelo
com características próprias e conceitualmente simples. Um outro objetivo é realizar
experimentos dos algoritmos Snakes desenvolvidos com imagens de diferentes
características de contexto, com relação à iluminação, ruídos, topologia, cores, entre
outros. Neste contexto, desenvolveu-se uma ferramenta para auxiliar a execução
dos algoritmos implementados desta técnica, com o intuito de facilitar a realização
dos experimentos.
Esse é um importante recurso para a solução de problemas em
processamento de imagens digitais, particularmente para a etapa de segmentação
de imagens, mas muito utilizada também em rastreamento de movimento e
modelagem de formas. As aplicações que englobam esta técnica estão em
ascensão, com destaque para as áreas da medicina, cartografia e computação
gráfica. A forma suave dos objetos envolvidos nestas áreas, porém não regular,
incentiva à utilização de Snakes, devido à tendência dos contornos se deformarem e
se adequarem ao objeto, mantendo característica de suavidade da curva.
Outro fator relevante que justifica o uso desta técnica é a menor
sensibilidade a ruídos, podendo ser aplicada mais eficientemente em imagens com
altos níveis de ruídos, mantendo mesmo nestas situações uma melhor continuidade
do contorno.
As motivações que levaram a realização deste projeto se resumem ao
fato de que existem diversas propostas de segmentação de imagem, algumas muito
antigas e a maior parte delas apresentam alguma deficiência em alguma situação.
Sendo assim, a investigação de novos métodos que apresentem melhores
resultados para segmentação de imagens, como é o caso do modelo deformável
17
para localização de bordas Gradient Vector Flow GVF (Fluxo do Vetor Gradiente) e o
modelo para tratamento de mudanças topológicas T-Snakes, que vem suprindo os
problemas habituais encontrados nos modelos tradicionais, é um fator de extrema
importância. Tal investigação serviu de base para a solução adotada neste projeto.
Outra motivação é do fato de que as aplicações Snakes estão em constante
ascensão, com grande influência nas áreas de processamento de imagens,
imageamento médico, segmentação e rastreabilidade de movimentos (MIYASAKI,
2003).
1.4
Trabalhos Correlatos e suas Aplicações
Existem diversos trabalhos relacionados ao método de segmentação
por contornos ativos Snakes, sendo estes aplicados em uma vasta gama de
aplicações, como medicina, geografia, entre outros. Dentre estes, cita-se neste
projeto o trabalho de Silva (SILVA, 2003), “Geo-Snake: uma aplicação da técnica
Snake em imagens geográficas”. Este trabalho consiste em uma ferramenta para a
identificação de elementos específicos e características em imagens de satélite,
como por exemplo, a identificação de regiões e sub-regiões de mesmo relevo,
estradas, rodovias e tipos de vegetação.
Alguns trabalhos enfatizam a definição de novos modelos, que são
evolução do modelo de contornos ativos Snake tradicionais, e que buscam resolver
alguns de seus problemas e limitações para com isso garantir maior flexibilidade e
desempenho na segmentação de imagens digitais. O presente projeto segue a linha
desses novos modelos, buscando o desenvolvimento de um modelo próprio de
maneira simples e que resolva os problemas das Snakes tradicionais.
18
1.5
Estrutura desta Monografia
Após a síntese introdutória correspondente ao primeiro capítulo desta
monografia, apresentam-se os conceitos mais elaborados. O capítulo 2 fornece base
inicial para a elaboração do projeto, descrevendo os conceitos sobre imagens
digitais, pré-processamento de imagens, alguns filtros de suavização, e curvas
Splines.
O capítulo 3 corresponde a descrição do modelo de contornos ativos
tradicional, apresenta a formulação inicial proposta por Kass, Witkin e Terzopoulos
(KASS, 1988), algumas formas de se desenvolver as energias envolvidas no
processo de segmentação pelo método Snake e descrição lógica do algoritmo
Greedy. O capítulo 4 descreve os modelos Gradient Vector Flow (GVF) e o TSnakes que resolvem os problemas encontrados nas Snakes tradicionais com
grande eficiência e que serviram de base para o desenvolvimento de uma solução
própria. Algumas aplicações abordando o contexto do projeto serão apresentadas no
capítulo 5.
Descreve-se no capítulo 6 o projeto implementado, seus conceitos e
métodos que, tomando por base os conteúdos apresentados nos capítulos
anteriores, contribuíram para o desenvolvimento de uma solução autêntica para os
modelos de contornos ativos Snake. O capítulo 7 é referente à ferramenta
desenvolvida para execução de testes dos algoritmos implementados, buscando
enfatizar as estruturas utilizadas, a exploração e tradução dos conceitos teóricos
para a solução computacional e uma breve descrição da utilização da ferramenta.
Por fim, o capítulo 8 trata dos resultados obtidos por meio da realização
de experimentos com imagens diversas, vantagens e limitações do modelo proposto,
extensão do projeto para futuras versões e conclusões finais.
19
2
2.1
CONCEITOS BÁSICOS
Imagem Digital
Uma Imagem Digital é formada por um conjunto de pontos discretos de
tons de cinza e brilho, que são geralmente organizados em uma matriz de pixels
(PEREIRA, 1996). Um pixel é representado por um ponto (x, y) que corresponde à
sua localização na imagem. Como representado na figura 3.
Considera-se que, a localização (0, 0) corresponde ao canto superior
esquerdo da imagem, e f(x, y) corresponde ao tom de cinza ou cor da imagem na
posição (x, y).
Píxel
Imagem Digital
Nível de cinza do píxel
FIGURA 3 – Representação de uma Imagem Digital (RIBEIRO, 1998).
20
Uma Imagem Digital é uma imagem contínua amostrada em um
arranjo matricial M x N, sendo o valor de cada elemento da matriz o nível de cinza do
pixel correspondente no plano de imagem (figura 4).
FIGURA 4 – Arranjo matricial com respectivos níveis de cinza.
2.2
Pré-Processamento
A etapa de pré-processamento tem o objetivo do realce e suavização
de uma imagem de modo que a imagem resultante seja mais adequada para uma
aplicação específica, dada uma imagem original. A utilização de um préprocessamento (aplicação de filtros) antes da segmentação por contornos ativos
deve ser algo considerável (MENDELS, 1999), pois quanto melhor estiver à imagem
a ser segmentada maior é a possibilidade de uma segmentação eficiente.
A interpretação do resultado desta etapa normalmente é subjetiva e
dependente de conhecimento prévio do observador a respeito das imagens
analisadas. Não existem técnicas de suavização e realce capazes de resolver 100%
dos problemas que uma imagem digital possa apresentar, mas seus resultados são
relativamente satisfatórios, apresentando um bom desempenho (MARQUES, 1999).
Já estes problemas são referentes à principalmente ruídos existentes em imagens
digitais, mas também podem se influenciados por outros fatores como falta de
iluminação adequada e baixo contraste.
Serão apresentados alguns filtros na etapa de suavização para
eliminação de ruídos em imagens, sendo estes os por filtragem pela media e filtro da
mediana.
21
2.2.1 Ruídos
São causados por erros na transmissão de dados, onde os pixels
corrompidos ou são alterados para o valor máximo, ou tem alguns bits alterados,
causando uma diferença brusca de tons entre estes pixels e seus vizinhos
(RIBEIRO, 1998). A figura 5 demonstra uma imagem original sem ruído e a mesma
com alto nível de ruído.
Imagem Original
Imagem com Ruído
FIGURA 5 – Representação: Imagem original e imagem com ruído (RIBEIRO, 1998).
2.2.2 Filtros
Os filtros de passa baixa, também conhecidos como filtros de
suavização, são empregados na remoção de ruídos de alta freqüência espacial em
imagens digitais. Ruídos estes que são geralmente introduzidos durante o processo
de conversão analógico-digital (RIBEIRO, 1998).
Entre as técnicas de suavização conhecidas, existem as de suavização
conservativa, que são técnicas de redução de ruídos que têm seu nome derivado do
fato de empregar um algoritmo simples e rápido de filtragem que elimina o ruído de
forma a manter os detalhes de altas freqüências como os contornos da imagem.
Essa técnica é especialmente desenvolvida para remover picos de ruídos, porém
não é muito eficiente na redução de ruído aditivo.
22
2.2.2.1 Filtros da Média
O filtro da média é implementado da seguinte maneira, tem-se uma
janela que percorre toda a imagem, o elemento central dessa janela recebe a média
de todos os elementos da janela (RIBEIRO, 1998). Por exemplo, tem-se a janela 3x3
abaixo:
A média dos valores é: (12 + 238 + 244 + 244 + 245 + 245 + 247 + 250
+ 252) / 9 = 219. Assim o valor do pixel central que era 12 será 219.
A figura 6 mostra o exemplo da aplicação do filtro da média.
Imagem Original
Imagem com Ruído
Imagem após filtro 3x3
Imagem após filtro 5x5
FIGURA 6 – Aplicação do filtro da média (RIBEIRO, 1998).
23
2.2.2.2 Filtro da Mediana
Uma das principais limitações do filtro da média, em situações onde o
objetivo é a remoção de ruídos em imagens, está na sua incapacidade de preservar
bordas e detalhes finos de imagem. Para contorná-la, uma técnica alternativa é o
filtro da mediana. Nesta técnica, o nível de cinza do pixel central da janela é
substituído pela mediana dos pixels situados em sua vizinhança.
Neste filtro o pixel central é substituído pelo valor mediano de seus
vizinhos. O processo consiste em ordenar na forma crescente ou decrescente os
valores dos pixels e pegar o valor mediano (RIBEIRO, 1998). Por exemplo (Janela
3x3):
Ordenando os valores tem-se: 12, 238, 244, 244, 245, 245, 247, 250,
252. O quinto valor é o mediano, ou seja, o valor 245.
Um dos maiores problemas do filtro da mediana é o seu custo
computacional, pois para encontrar o pixel mediano é necessário que se ordenem
todos os valores da vizinhança, sendo relativamente mais lento do que o filtro da
média.
24
A figura 7 mostra o exemplo com a aplicação do filtro da mediana:
Imagem Original
Imagem com Ruído
Imagem após filtro media3x3
Imagem após filtro mediana 3x3
FIGURA 7 – Aplicação do filtro da mediana (RIBEIRO, 1998).
Este
método
apresenta
desempenho
particularmente
bom
em
situações onde a imagem é contaminada por bastante ruído .
2.3
Curvas Splines
Um dos motivos da escolha de Splines no método de segmentação por
contornos ativos é o fato de que elas são suficientemente flexíveis para representar
qualquer tipo de curva, preservando características da suavidade do objeto. A curva
é definida exclusivamente por um conjunto de pontos de controle, que funcionam
como pontos de atração sobre a curva (OLIVEIRA, 2000).
25
Segundo Angel (ANGEL, 1997), a interpolação utilizando Splines
propõe que o contorno do objeto seja dividido em um conjunto de partes ou
segmentos, sendo estes pequenas curvas ou arcos, que podem ser representados
adequadamente por polinômios de graus pequenos.
A figura 8 mostra a obtenção de uma curva de grau dois, tendo como
objetivo mostrar a sua forma de construção.
FIGURA 8 – Curva de grau dois, definida a partir de três pontos (OLIVEIRA, 2000).
Tendo definidos os pontos da curva p0 e p1 são tomadas às direções
das curvas, que são derivadas dos dois pontos que a definem. O objetivo é obter
uma curva suave, sem quebras bruscas do contorno. Através da interseção dos
vetores direção, que foram originados dos pontos p0 e p1, define-se o terceiro ponto
(v), sendo a curva de grau dois, definida por:
p(t) = b0 + b1t + b2t2, t∈ [-1,1]
(1)
Onde:
b0 =
p 0 + p1
+
2
v−
p 0 + p1
2
,
2
b1 =
p1 − p 0
2
e
p 0 + p1
−v
2
b2 =
2
Na figura 8 o ponto v atua como um ponto de atração da curva e
quando o mesmo é movido, arrasta também a curva em sua direção.
A interpolação utilizando uma Spline Cúbica consiste em repartir o
26
intervalo em k subintervalos e, em seguida, obter k polinômios de grau três para
cada um deles.
Algumas condições para a definição destes polinômios são (SILVA,
2004):
1. Em cada ponto de controle, devem ser iguais às inclinações dos
polinômios que nele incidem, de modo a proporcionar a suavidade
desejada;
2. Em cada ponto de controle, também precisam ser iguais às
curvaturas dos polinômios que neles incidem, constituindo no
conceito de energia potencial mínima.
A segmentação pelo método Snake possui grande dependência da
topologia dos objetos da imagem a ser segmentada. Objetos com menos curvas e
concavidades são relativamente mais fáceis de serem segmentados do que os
topologicamente mais complexos. A definição da Snake via a abordagem de Splines
viabiliza a segmentação para qualquer que seja o objeto, pois garante a suavidade
da curva desde o processo de deformação até a localização do contorno do objeto,
com isso tem-se como resultado final uma curva que melhor represente o objeto
real.
27
3
O MODELO DE CONTORNOS ATIVOS
O modelo de contornos ativos, em sua formulação original proposta por
Kass, Witkin e Terzopoulos (KASS, 1988), foi o método proposto para resolver o
problema de localização de bordas de objetos em imagem. A partir da sua
formulação foi possível resolver vários problemas de visão computacional e análise
de imagens.
Este modelo leva em consideração a propriedade da descontinuidade e
tem o objetivo de identificar bordas de objetos que compõem uma imagem, sendo
em geral aplicados conjuntamente com técnicas de filtragem e suavização usadas
na detecção de pontos de bordas. Estes métodos se iniciam em uma configuração
mais ou menos arbitrária, um contorno inicial, que evolui até contornar o objeto de
interesse. Devido a este comportamento dinâmico que se tem à definição de
“modelos deformáveis”.
A segmentação utilizando contornos ativos é caracterizada por tentar
ajustar uma curva, no caso desse projeto uma Spline, sobre uma imagem. A
movimentação da Spline ocorre de forma a tentar minimizar a energia funcional
(TRUCCO, 1998) que é dada pela combinação das energias da curva e da imagem,
trata-se de um modelo baseado em conceitos físicos. Devido ao fato da Spline se
mover constantemente buscando encontrar a borda e se ajustar aos níveis mínimos
de energia, a técnica é também conhecida como Snakes.
Algumas vantagens com a utilização de Snakes para a segmentação
de imagens, segundo a visão de Pichumani (PICHUMANI, 1997):
•
São fáceis de manipular, pelo fato das forças externas se
comportarem de uma forma intuitiva;
•
São autônomas e auto-adaptáveis na busca pelo estado de menor
energia;
•
São menos sensíveis ao ruído.
Podem
ser
utilizadas
para
seguir
dinamicamente
objetos
em
28
dimensões temporais, assim como em espaciais. Aplicação em rastreamento de
objetos.
Segundo Xu e Prince (XU; PRINCE, 1998), os modelos de contornos
ativos podem ser de dois tipos: modelos paramétricos, como as Snakes e modelos
geométricos ou implícitos, como os Level Set Methods (Métodos de Ajuste de Nível)
e os Fast Marching Methods (Métodos de Marcha Rápida).
Esse projeto enfatiza o modelo do tipo paramétrico, que sintetizam
curvas paramétricas ou superfícies dentro de um domínio de imagem e lhes permite
se orientar a características desejadas, normalmente extremidades.
Os modelos paramétricos são constituídos de curvas elásticas que
agem sobre a imagem até encontrar a borda do objeto de interesse, sendo o
processo realizado de maneira dinâmica. Nesta composição atuam basicamente
duas forças: a força elástica e a da imagem ou de restrição. Devido a estas forças é
que a Snake pode se transformar no molde do objeto e também ser atraída para as
bordas do objeto de interesse.
A figura 9 ilustra a composição e ação desse modelo para a detecção
de objetos de uma cena:
(a)
(b)
(c)
FIGURA 9 – Representação da ação da curva do modelo de contornos ativos (SILVA, 2003).
Este modelo necessita da especificação de uma curva inicial, cuja
posição é definida pelo usuário, como se observa em (a). Junto é associada uma
função objetivo, que é denominada por energia da Snake. Esta energia é composta
de duas partes: energia interna e a energia externa. A interna considera aspectos
físicos como elasticidade, que é a capacidade em que a curva tem de se deformar
29
sob a ação de uma força e retornar ao seu formato original quando a mesma é
removida e aspectos de rigidez, que é a resistência da curva de manter-se dobrada.
A energia externa considera as características da própria imagem. Em (b) tem-se a
representação da atuação dessas energias com o processo em andamento. A
Snake se conforma quando encontrar o limite do objeto (c).
De acordo com a definição de Kass, Witkin e Terzopoulos (KASS,
1988), uma Snake é uma curva v(s)=[x(s),y(s)] que se move pela imagem buscando
minimizar a energia funcional. O x(s) e o y(s) são as coordenadas x, y ao longo do
contorno e s ∈ [0, 1] é o comprimento do arco normalizado.
1
Esnake = ∫ Eint v( s ) + Eext v( s ) ds
(2)
0
A energia interna Eint é totalmente definida pela curva e a energia
externa Eext é derivada da imagem. Em (2), v(s) = (x(s), y(s)) é a representação
paramétrica do contorno.
A energia funcional definida em (2) é uma combinação de energias
interna e externa, a ferramenta matemática indicada para a sua solução é o cálculo
variacional, que determina o mínimo de um funcional (assim como o cálculo provê
um método para a determinação do mínimo de uma função ordinária) (Trucco, 98).
A correspondência do modelo com o contorno só é alcançada pela procura de um
vetor que minimize a soma dessas energias. A conformidade com o contorno é
alcançada quando a soma for igual à zero.
Uma discretização de (2) permite definir a energia da Snake como:
Esnake = ∑ Eint + Eext
(3)
Outras energias podem ser inseridas em (3), sendo comum à definição
de uma energia devida a certo conhecimento sobre a forma que o contorno do
objeto apresenta. Esta energia é conhecida como energia confinada, segundo Sonka
(SONKA, 1998).
30
E snake = ∑ Einterna + Eexterna + Econfinada
(4)
Cada uma destas energias principais pode ser composta de outras
energias, de forma a obter o comportamento desejado em cada situação.
3.1
Energia Interna
A energia interna é obtida a partir da própria curva, tendo como um de
seus principais objetivos deformar a Snake e manter a suavidade da curva. Neste
contexto, serão apresentados alguns modelos e definições desta energia. Seguem
abaixo os modelos com base na elasticidade e rigidez da curva e com base na
continuidade e força balão.
3.1.1 Modelo baseado na elasticidade e rigidez da curva
Este modelo foi proposto por Sonka (SONKA, 1998) sendo um modelo
relativamente simples para a energia interna. É baseado em conceitos de
elasticidade e rigidez da curva.
2
Einterna
dv
d 2v
= α ( s)
+ β ( s) 2
ds
ds
2
(5)
Por definição tem-se:
α(s) especifica a elasticidade da curva ou resistência ao se esticar.
β(s) especifica a rigidez da curva ou resistência ao se torcer.
Na implementação torna-se necessário o cálculo da curvatura, que,
utilizando a parametrização v(s) = (x(s), y(s)) é dada por:
31
k=
x ' y"− x" y'
( x' 2 + y ' 2 )3/ 2
(6)
Utilizando diferenças finitas tem-se as seguintes aproximações
(WILLIAMS; SHAH, 1992) para os termos em (5).
2
dv
2
≈ vi − vi −1 = ( xi − xi −1 ) 2 + ( yi − yi −1 ) 2
ds
(7)
e
2
d 2v
2
v
v
v
≈
−
2
+
= ( x i−1 − 2 x i + x i +1 ) 2 + ( y i−1 − 2 y i + y i+1 ) 2
i
−
i
i
+
1
1
2
ds
(8)
Na equação (7) e (8), assume-se que os pontos estejam igualmente
espaçados em intervalos unitários. Quando isso não ocorrer, a equação (7) precisa
ser dividida por d2 e a equação (8) por d4, onde d é a distância entre os pontos
(SILVA, 2004).
Como visto na equação (5), enquanto o termo α(s) controla a tensão ao
longo da curva, β(s) controla a rigidez. Assim, para o caso de β(s) = 0, tem-se uma
descontinuidade no local, o que possibilita o aparecimento de um canto. Quando
α(s) e β(s) forem iguais à zero tem-se uma quebra no contorno.
A tensão ao longo da curva pode ser medida por meio de uma função
que mede o comprimento do contorno, porém, observa-se que a Snake apresenta
um melhor comportamento se os pontos de controle são também mantidos
igualmente espaçados (Young, 1995). Partindo desta observação, uma forma mais
conveniente para a definição da energia é tomar a soma dos quadrados das
distâncias entre os pontos adjacentes. Uma energia assim definida deve apresentar
uma resposta mais rápida, se comparada com a energia obtida com o comprimento
total da curva. A energia elástica pode então ser escrita como:
n
Eelastica = k1 ∑ distancia( pi , pi−1 )2
i =1
(9)
32
onde: k1 é uma constante, a ser ajustada e, pi e pi-1 são pontos de controle
adjacentes.
A energia definida em (9) atua em um ponto de controle xi puxando-o
em direção da reta que liga os seus dois vizinhos xi-1 e xi+1, conforme mostra a figura
10. Isto pode ser realizado pela definição das componentes em X e Y desta energia.
EelasticaX ,i = k1[( xi−1 − xi ) + ( xi+1 − xi )]
(10)
E elasticaY ,i = k1 [ ( y i −1 − y i ) + ( y i +1 − y i )]
(11)
e
A figura 10 mostra geometricamente o comportamento desta energia.
pi+1
Força elástica sobre xi
pi
pi-1
FIGURA 10 – Direção da força elástica atuando sobre um ponto pi. (OLIVEIRA, 2000)
A energia interna deve ser capaz de forçar a preservação da forma do
contorno e também manter constante a distância entre os pontos do contorno
(OLIVEIRA, 2000).
3.1.2 Modelo Baseado na Continuidade e Força Balão
Uma outra forma de definir a energia interna é apresentada em
Mackiewich (MACKIEWICH, 2005), que a define como sendo a soma de uma
33
energia de continuidade (continuity energy) e uma força balão (ballon force). A
energia interna é então escrita como:
Einterna (vi ) = cEcont (vi ) + bEbal (vi )
(12)
onde: Econt(vi) é a energia de continuidade, que força a forma do contorno e, Ebal(vi) é
a força balão, que faz o contorno esticar ou encolher. Os parâmetros c e b são
pesos, utilizados para ajustar cada um destes termos. As energias Eext , Eint , Econt e
Ebal podem ser representadas por meio de matrizes, nas quais o elemento vi ocupa a
posição central. As dimensões pequenas destas matrizes definem uma pequena
região de processamento em torno deste elemento conforme mostra a figura 11, que
sugere a utilização de uma matriz 7x7.
3.1.2.1 Energia de Continuidade
A energia de continuidade Econt faz com que um contorno aberto tome a
forma de uma linha reta, enquanto que um contorno fechado é forçado a tomar a
forma de um círculo. A energia para cada elemento cjk(vi) na matriz Econt(vi) pode ser
escrita como MACKIEWICH (2005) :
c jk (vi ) =
1
p jk (vi ) − γ (vi −1 + vi +1
I (V )
2
(13)
onde:
1 n
I (V ) = ∑ v i+1 − v i
n i =1
2
(14)
é um fator de normalização, dado pela distância média entre os pontos de V
(contorno); A normalização é importante em (13) para que a Econt(vi) seja
independente do tamanho, localização e orientação de v. Em (13), pjk(vi) é o ponto
na imagem que corresponde espacialmente ao elemento da matriz de energia cjk(vi).
O parâmetro γ = 0.5 para um contorno aberto e, neste caso, o ponto de energia
mínima é exatamente o meio entre os pontos vi-1 e vi+1, conforme apresentado na
34
figura 11. Para o caso de contornos fechados, γ é definido como:
γ =
1
⎛ 2π ⎞
2 cos⎜ ⎟
⎝ n ⎠
(15)
Neste caso o ponto de mínima energia na matriz Econt(vi) é aquele que
empurra V, para a posição que mais torna o contorno parecido com um círculo.
vi-2
vi-1
Matriz
vi
definida
pela
Vizinhança de vi
vi’
vi+1
Contorno
Círculo
Centróide do contorno
vi+2
FIGURA 11 – Ponto de contorno vi sobre a ação da energia de continuidade (OLIVEIRA, 2000).
Na figura 11, o ponto vi é o local de menor energia na matriz, porque
está mais próximo do círculo que passa pelos pontos vi-1 e vi+1 (considera-se
também a necessidade de manter o afastamento eqüidistante entre os pontos do
contorno).
3.1.2.2 Força Balão
A força balão é definida para controlar a expansão e a contração do
contorno. Espera-se que a força balão auxilie um contorno inicial a se expandir até
35
as proximidades das bordas do objeto.
A figura 12 mostra a ação desta força, sobre uma imagem e um
suposto contorno inicial.
ti
Objeto
com
intensidade
Força
balão
ni
Contorno final (V)
uniforme
Contorno inicial (V)
FIGURA 12 – Ação da força balão sobre um contorno inicial.
A força balão deve ser grande em regiões homogêneas e pequena nas
regiões de bordas dos objetos (MACKIEWICH, 2005).
Cada elemento cjk(vi) da matriz Ebal(vi) pode ser expresso como o
produto vetorial :
c jk (vi ) = ni ⊗ (vi − p jk (vi ))
(16)
onde ni é o vetor normal de V no ponto vi e pjk(vi) é o ponto na vizinhança de vi
correspondente a entrada cjk(vi) na matriz energia. Assim, a força balão se torna
pequena nos pontos afastados de vi na direção ni. O vetor ni pode ser obtido a partir
de uma rotação do vetor tangente ti, dado por (figura 12):
ti =
vi − vi −1
v −v
+ i +1 i
vi − vi −1
vi +1 − vi
(17)
36
3.2
Energia Externa
Como visto, a energia externa é totalmente obtida a partir da imagem,
tendo diversas formas para sua definição. Algumas formas consideram as
informações referentes aos níveis de cinza dos pixels, outras consideram pixels de
bordas da imagem, entre outras formas.
Segundo Mackiewich (MACKIEWICH, 2005), levar em consideração a
informação dos níveis de cinza e também dos pontos de borda resultam na definição
da energia externa como sendo:
E externa (vi ) = mE mag (vi ) + gE grad (vi )
(18)
onde: Emag(vi) representa a energia que empurra o contorno para áreas com os
maiores níveis de cinza, enquanto que Egrad(vi) é a energia que empurra o contorno
em direção aos pontos de borda. Os parâmetros m e g são utilizados para ajustar a
participação de cada termo. O parâmetro m pode ainda ser ajustado para fazer o
contorno ser atraído por áreas escuras ou claras, dependendo do sinal adotado.
Outras energias podem ser também utilizadas para compor a energia
externa e, uma outra definição é (Sonka, 1998):
Eexterna(vi) = lEline(vi) + gEgrad(vi) + tEterm(vi)
(19)
As duas primeiras energias em (19) correspondem as duas energias
em (18), respectivamente, enquanto que Eterm(vi) é uma energia devida a presença
de terminações (pontas de linhas e cantos de objetos).
3.2.1 Energia da Intensidade da Imagem
A matriz de energia Emag(vi) ou Eline(vi) tem seus elementos cjk(vi)
definidos pelos valores dos níveis de cinza nos pontos correspondentes na imagem,
37
na vizinhança de vi (a matriz c é sobreposta à imagem no ponto vi, por isto a
definição de pontos correspondentes na imagem).
cjk(vi) = I(pjk(vi))
(20)
De forma a aumentar esta energia, pode-se tomar o quadrado das
intensidades dos níveis de cinza, e assim, a energia de intensidade fica:
n
E mag = k 2 ∑ imagem( xi , yi ) 2
i =1
(21)
3.2.2 Energia do Gradiente da Imagem
Os elementos c jk (vi ) da matriz de energia Egrad (vi ) podem ser
definidos por:
c jk (vi ) = − ∇I ( p jk (vi ))
(22)
Novamente pode ser realizada a definição das componentes em X e Y
desta energia, dadas por:
EgradX ,i = k3 [(imagem( xi +1 , yi ) − imagem( xi −1 , yi )]
(23)
EgradX ,i = k3 [(imagem( xi , yi +1 ) − imagem( xi , yi −1 )]
(24)
e
Na figura 13, o ponto vi que está na posição p4,4 da matriz deve ser
movido para a posição p2,6 (vi ) , que possui o maior gradiente.
38
Egrad (7 x 7)
FIGURA 13 – Utilização da matriz
para a obtenção da energia baseada em gradiente
(OLIVEIRA, 2000).
Observa-se que a direção do gradiente na borda do objeto deve ser
igual à norma da direção do contorno, assim, o valor de cada elemento da matriz
Egrad (vi ) pode ser definido pelo produto vetorial (OLIVEIRA, 2000):
c jk (vi ) = −ni ⊗ ∇I ( p jk (vi ))
(25)
onde ni é o vetor normal do contorno de vi .
Uma forma equivalente de definir os gradientes é utilizar localmente os
conhecidos operadores de gradiente, neste caso a energia, fica definida como:
Emag (i, j ) = g H (i, j )2 + gV (i, j )2
(26)
onde:
gH =
gV =
1
1
∑ ∑ Sobel
k =−1 I =−1
1
H
1
∑ ∑ Sobel
k =−1 I =−1
V
(i, j ) I t (i + k , j + l )
(i, j ) I t (i + k , j + l )
(27)
(28)
39
3.2.3 Energia das Terminações
As terminações das linhas e cantos dos objetos podem também ser
utilizados para influenciar o traçado do contorno, principalmente para a definição de
contornos subjetivos (OLIVEIRA, 2000), como os que aparecem na figura 14.
FIGURA 14 – (a) Imagem original contendo alguns objetos (bordas) e algumas terminações e (b)
Snake obtida (OLIVEIRA, 2000).
Uma possível definição para esta energia pode ser feita da seguinte
forma (SONKA, 1998): seja g uma versão ligeiramente suavizada da imagem f,
tomando ψ ( x, y ) as direções dos gradientes sobre a spline na imagem suavizada (g),
faça:
n( x, y ) = (cosψ ( x, y ),sin( x, y ))
(29)
nR ( x, y ) = ( − sinψ ( x, y ),cos( x, y ))
(30)
e
os vetores ao longo e perpendicular, respectivamente, às direções do gradiente
ψ ( x, y ) , então,
Eterm
ou ainda,
2
2
∂ψ ∂ g / ∂n R
=
=
∂ nR
∂ g / ∂n
(31)
40
Eterm =
(∂ 2 g / ∂y 2 )(∂g / ∂x) 2 − 2(∂ 2 g / ∂x∂y )(∂g / ∂x)(∂g / ∂y ) + (∂ 2 g / ∂x 2 )(∂g / ∂y )2
((∂g / ∂x) 2 + (∂g / ∂y ) 2 )
3
(32)
2
3.2.4 Outras energias externas
Diversas energias externas foram propostas para tentar modelar o
comportamento do contorno. Algumas dessas energias são (MARQUES, 1998):
A energia obtida com a soma de funções gaussianas centradas nos
pontos de bordas detectadas na imagem.
E (vk ) = −
1
M
∑ G (v
k
x∈ X
− x)
(33)
onde: G é a função gaussiana e M é o número de pontos de borda.
Uma energia baseada em redes elásticas, que pode ser definida por:
E (vk ) = −
1
M
∑ log ∑ G(v
x∈ X
i
− x)
(34)
i
Um modelo para a extração de regiões coloridas em imagens naturais
é apresentado em Ngoi e Jia (NGOI, 1999). Neste caso, as cores são utilizadas para
compor uma nova energia.
3.3
Energia Confinada
A energia confinada representa alguma informação que se possui à
respeito da forma do objeto, assim, para o caso de se desejar segmentar objetos
quadrados, é preciso que alguma atenção seja dada nos cantos da feição (atuando
na suavidade e rigidez da curva nestes locais). Observa-se que a energia confinada
41
é bem particular para cada tipo de aplicação (OLIVEIRA, 2000).
3.4
Normalização das Energias
Quando as energias definidas anteriormente são colocadas juntas na
equação (4), elas precisam operar de maneira a fazer que o contorno seja
empurrado para os limites do objeto na imagem. Além da necessidade de
determinações dos sinais de cada uma das componentes de energias, uma
normalização delas no intervalo [0,1] também se mostra atraente (MACKIEWICH,
2005).
3.5
Algoritmo Greedy
Este algoritmo apresenta um método para definir uma Snake sobre um
contorno em uma imagem digital. O algoritmo opera de forma local, na tentativa de
se obter uma solução global ótima. A grande vantagem do algoritmo está na sua
simplicidade (e conseqüentemente, baixo custo computacional), dispensando ainda
o conhecimento do cálculo variacional. Em seguida são apresentadas algumas
suposições iniciais e o algoritmo (OLIVEIRA, 2000).
A energia funcional é definida por :
(
)
E = ∫ α ( s ) Econt + β ( s ) Ecurv + γ ( s ) Eimage ds
(35)
Onde: Econt, Ecurv e Eimage são, respectivamente, as energias de continuidade do
contorno, a energia devida à suavidade (rigidez) da curva e a energia da imagem,
devida a atração das bordas. Como em (5), Econt é definida por :
E cont
dv
=
ds
2
Que no caso discreto pode ser escrita como :
(36)
42
Econt = || pi - pi-1 ||2
(35)
Com o objetivo de prevenir a formação de aglomerados de pontos de
contornos (é importante manter a eqüidistância entre os pontos do contorno), a
equação (35) pode ser modificada para:
E cont
⎞
⎛_
= ⎜ d − pi − pi −1 ⎟
⎠
⎝
2
(36)
_
Onde: d é a distância média entre os pares de pontos pi e pi-1. Quando || pi _
pi-1 || >> d , tem-se Econt ≈ || pi - pi-1 ||2.
O termo de suavidade deve ser capaz de impedir um excesso de
oscilações no contorno, o que, conforme já apresentado, pode ser feito através do
cálculo da curvatura, que pode ser aproximada (a curvatura pode ser aproximada
pela segunda derivada do contorno) por :
Ecurv = || pi-1 – 2pi + pi+1 ||2
(37)
Finalmente o termo Eimage pode ser obtido por meio do gradiente (38),
conforme já apresentado em (22).
Eimage = - || ∇I ||
_
(38)
_
Tomando I a imagem e p 1, ......, p N o conjunto contendo as posições
iniciais dos pontos do contorno. Deseja-se encontrar o contorno p1,......,pN, que
melhor se ajusta sobre o contorno da imagem, por meio da minimização da energia
funcional E.
N
E = ∑ (α i Econt + β i Ecurv + γ i Eimage )
i =1
(39)
com αi, βi e γi ≥ 0 e Econt, Ecurv e Eimage como em (36), (37) e (38), respectivamente.
O núcleo do algoritmo é constituído de dois passos (TRUCCO, 1998) e
as interações terminam quando um número predefinido dos pontos alcança um local
mínimo.
43
Observa-se que este algoritmo funciona bem apenas quando o
contorno inicial já está próximo do local da solução desejada (SILVA, 2004).
1. A vizinhança sobre a qual a energia funcional é localmente
minimizada é pequena (geralmente se utiliza janelas 3x3, 5x5 ou
7x7 centradas em cada ponto do contorno). A minimização da
energia é feita por comparações diretas dos valores da energia
funcional em cada localização.
2. Durante o segundo passo, o algoritmo procura por cantos
(curvaturas máximas ao logo do contorno). Se uma curvatura
máxima é encontrada em um ponto pj, βj recebe o valor zero,
desconsiderando a contribuição do termo de suavidade Ecurv no
ponto pj e tornando possível o aparecimento de um canto.
A figura 15 mostra o algoritmo definido segundo estas condições
(TRUCCO, 1998).
Algoritmo snake (snake algorithm)
A entrada é formada pela imagem I, que contém um contorno fechado de interesse e um
conjunto de pontos
p1, ...., pN definindo a posição inicial e a forma da Snake. Seja f a quantidade mínima de
pontos da Snake que precisam ser movidos em cada interação antes da convergência e
U(p) uma pequena vizinhança do ponto p.
_
_
no início, pi = p i ,
d = d , αi = βi = 1
e
γi = 1.2
Enquanto um número maior que f de pontos da Snake se movem na interação:
1 - para cada i = 1,....,N, encontre a localização de U(pi) para o qual o funcional E definido
em (36) é mínimo, e mova o ponto pi da snake para a localização;
2 – para cada i = 1,....,N, calcule a curvatura k da snake nos pontos pi, como
k = | pi-1 –2pi + pi+1 |
e verifique o máximos locais. Faça β = 0 para todos pj que a curvatura é um máximo local e
excedam um valor mínimo defindio pelo usuário;
_
3 – calcule o valor de d , média das distâncias;
FIGURA 15 – Algoritmo para contornos ativos (TRUCCO, 1998).
44
4
OS MODELOS: GRADIENT VECTOR FLOW (GVF) E T-SNAKES
Há duas dificuldades de chave com algoritmos de contorno ativos
tradicionais (XU; PRINCE, 1997), apresentados no capítulo anterior. A primeira se
refere ao contorno inicial que deve, em geral, estar perto do verdadeiro limite ou
então convergirá num provável resultado errado. A segunda é que os contornos
ativos têm dificuldades de progredirem em regiões de limite côncavo.
A figura 16 mostra uma imagem com um objeto que possui uma
concavidade e o resultado obtido utilizando o modelo tradicional de forças.
(a)
(b)
FIGURA 16 – (a) Imagem original com seu contorno inicial e (b) contorno final obtido com o método
original (XU; PRINCE, 1997).
Embora existam muitos métodos como os multiresolution e forças de
pressão, por exemplo, que foram propostos para resolver esses problemas
tradicionais, eles ou resolvem um problema ou resolvem ambos, mas, criando
dificuldades novas (XU; PRINCE, 1997).
Sendo assim, os modelos GVF e T-Snakes são evoluções da Snake
tradicional
que
além
de
resolverem
os
problemas
tradicionais
possuem
características e inovações próprias, sendo considerados atualmente os métodos
robustos, de melhor desempenho e mais flexíveis da literatura.
4.1
A nova força externa: Gradient Vector Flow
Essa nova de força externa para modelos de contorno ativos,
45
focalizando os problemas listados acima e os resolvendo em grande parte, pode ser
observada na figura 17.
FIGURA 17 – Determinação de uma nova força baseada no fluxo do vetor gradiente (GVF) (XU;
PRINCE, 1997).
As principais vantagens do GVF são que ele permite capturar a curva
em uma grande distância e, ainda pode forçá-la em regiões côncavas (XU; PRINCE,
1997).
Tal campo aponta em direção às bordas dos objetos quando próximo a
elas, mas varia suavemente sobre regiões homogêneas, se estendendo até a
fronteira da imagem. Estas propriedades garantem um maior alcance de captura da
Snake, de ambos os lados das bordas do objeto, além de forçá-la em direção a
regiões côncavas devido a um processo simultâneo de difusão (PIMENTEL, 2000).
É definido um campo de distribuição de bordas f(x, y) derivado de uma
imagem em tons de cinza I(x, y) com a propriedade de apresentar valores elevados
próximo às bordas de objetos (PIMENTEL, 2000).
f(x, y) = -Eext(x, y)
(40)
46
O gradiente ∇f tem vetores que apontam para as bordas e que, sobre
as bordas, são normais às mesmas. Estes vetores apresentam maiores magnitudes
apenas na vizinhança imediata das bordas. Sobre regiões homogêneas, onde I(x, y)
é praticamente constante, ∇f tende a zero e não há informação sobre bordas
próximas ou distantes (XU e PRINCE, 1997).
O campo GVF é então definido como o campo vetorial g(x, y) = (u(x, y),
v(x, y)) que minimiza a função de energia
(
)
E = ∫ ∫ µ u x2 + u y2 + v x2 + v y2 + ∇f
2
g − ∇f dxdy
2
(41)
Quando |∇f| é pequena, a energia é dominada pelas derivadas parciais
do campo vetorial, gerando um campo suave. Por outro lado, quando |∇f| é grande,
o segundo termo se domina integrando, e é minimizado quando g = ∇f. Isto produz o
efeito desejado de manter g praticamente igual ao gradiente da distribuição de
bordas quando este é alto, porém forçando o campo a variar suavemente em regiões
homogêneas. O parâmetro µ controla a relação entre o primeiro e o segundo termos
e é ajustado de acordo com o nível de ruído presente na imagem (maior nível de
ruído, maior µ) (XU; PRINCE, 1997).
O campo GVF pode ser determinado pela solução das equações de
Euler:
µ∇ 2u − (u − f x )( f x2 + f y2 ) = 0
(42a)
µ∇ 2 v − (v − f y )( f x2 + f y2 ) = 0
(42b)
Observa-se que em regiões homogêneas da imagem o segundo termo
das equações é nulo, e u e v são determinadas pela equação de Laplace. Assim,
nestas regiões o campo GVF resultante é interpolado a partir das bordas da região,
refletindo uma espécie de competição entre os vetores de borda, o que produz
vetores resultantes apontando para regiões côncavas de objetos (XU; PRINCE,
1997).
As equações (42) são tratadas tendo u e v como funções do tempo e
47
resolvendo (PIMENTEL, 2000):
(
2
(
2
2
)
(43a)
2
)
(43b)
ut ( x, y, t ) = µ∇ 2u ( x, y, t ) − (u ( x, y, t ) − f x ( x, y )) f x ( x, y ) + f y ( x, y )
vt ( x, y, t ) = µ∇ 2 v( x, y, t ) − (v( x, y, t ) − f v ( x, y )) f x ( x, y ) + f y ( x, y )
A solução em regime permanente destas equações parabólicas
lineares desacopladas é a solução desejada das equações de Euler (42). As
equações (43a e 43b) são conhecidas como equações gerais de difusão, presentes
na modelagem de diversos processos físicos como condução de calor, balanço de
massa em reatores e mecânica de fluídos (PIMENTEL, 2000).
Após a determinação do campo GVF, basta substituir a força potencial
externa tradicional por g(x, y) (PIMENTEL, 2000).
A figura 18 mostra alguns resultados obtidos com a inserção desta
nova energia.
FIGURA 18 – (a) contorno inicial, (b) contorno final obtido com o modelo de energias tradicional, (c)
contorno inicial (definido longe das bordas do objeto), (d) contorno final utilizando GVF (XU; PRINCE,
1997).
48
A figura 19 mostra que o método apresenta bons resultados mesmo
quando o contorno inicial cruza as fronteiras do objeto e, também, quando o
contorno do objeto é definido por um conjunto de pontos (contorno subjetivo).
FIGURA 19 – (a) contorno inicial (passando através das bordas do objeto), (b) contorno obtido
utilizando GVF (c) contorno inicial, aplicado no interior de um conjunto de pontos (contorno subjetivo)
e (d) resultado obtido utilizando GVF (XU; PRINCE, 1997).
A figura 20 mostra os resultados obtidos com este modelo, quando
aplicado sobre uma imagem médica (interior de um órgão - coração) (OLIVEIRA,
2000).
FIGURA 20 – (a) Imagem médica e o contorno inicial, (b) contorno final utilizando GVF (OLIVEIRA,
2000).
49
4.2
O modelo T-Snakes
O modelo T-Snakes visa uma segmentação de imagens capaz de lidar
com mudanças topológicas nos objetos. A capacidade de lidar com mudanças de
topologia é importante para poder segmentar objetos de contornos múltiplos e com
furos, concavidades ou ramificações. Esta capacidade permite que a Snake seja
dividida para criar múltiplos contornos ou, ainda, fundir vários em um só. Estas
operações são conhecidas como Split e Merge, respectivamente (MACHADO, 2003).
Define-se 3 componentes básicos para o modelo: triangulação, um
modelo discreto de Snake e uma função característica (MACHADO, 2003).
A triangulação busca a decomposição do domínio da imagem em
células para representá-las com objetos geométricos mais simples de dimensão n. A
triangulação utilizada neste projeto é a Coxeter-Freudental, considerada muito
simples, pois se diferem somente pela orientação e reflexão das células. Sendo
assim, decompõe-se a imagem em uma grade com quadrados iguais e divide-se
cada quadrado em 2 triângulos ou células simples (GIRALDI, 2005). A figura 21
representa a decomposição da imagem em células triangulares.
FIGURA 21 – Triangulação Coxeter-Freudental.
O componente modelo discreto de Snake é a força discreta, que é
baseada na Snake tradicional e que tem a finalidade da deformação em direção às
bordas do objeto. A força interna de tensão age para manter um espaçamento
uniforme entre os nós do modelo. A força interna de rigidez relaciona-se à suavidade
da Snake. O modelo possui também uma força interna normal usada para atrair a
Snake em direção às bordas dos objetos, procurando evitar que a Snake pare em
locais mínimos. A força externa ou força dos dados da imagem é definida em função
das características de interesse na imagem, no caso aqui considerando as bordas
dos objetos da cena.
50
A equação de evolução para o T-Snakes, que é aplicada a cada snaxel
a cada evolução, é o resultado de uma combinação entre estas forças. Uma
abordagem mais detalhada sobre estas forças e os parâmetros por elas utilizados
pode ser vista em Giraldi (2000).
A função característica permite a classificação dos triângulos da grade
utilizando os valores 0 ou 1 de seus vértices. A Snake não poderá atingir um
triângulo cujos vértices tenham valores iguais a 1 (nós queimados), e estes pontos
são os já visitados pela Snake. Por sua vez os nós da malha formados por triângulos
com valores iguais a 0 (não queimado) correspondem a regiões atingíveis pela
Snake (MACHADO, 2003). Os triângulos onde a função característica contém
valores de 0 e 1 são denominados triângulos de borda.
Para o algoritmo, projeta-se a Snake inicial fornecida pelo usuário
sobre a malha queimando os pontos externos a ela através da função que determina
se o nó está interno ou externo ao polígono. Esse processo é referente à
convergência da Snake. Para a deformação em expansão são queimados os nós
internos a Snake.
Em cada iteração do algoritmo de contração atualiza-se a posição das
snaxels através da ação das forças internas e externas, garantindo a evolução da
Snake. Ao final de cada iteração faz-se uma atualização da função característica e
determina-se o conjunto de nós da malha que serão queimados durante a evolução.
Os vértices do triângulo que possuírem todos os valores 1 ou 0 estão fora ou dentro
da Snake respectivamente e os triângulos onde a função característica muda de
valor são denominados triângulos de borda. A determinação dos triângulos de borda
corresponde ao limite onde as snaxels poderão se deformar, tanto para a contração
quanto para expansão. A condição de parada do algoritmo se faz quando todas as
snaxels estiverem sobre a borda do objeto (MACHADO, 2003).
A figura 22 demonstra a evolução da Snake, destacando os nós
queimados, internos e triângulos de borda num determinado estado de passo de
contração.
51
FIGURA 22 – Representação do novo modelo em um determinado estado de evolução (MACHADO,
2003).
Este modelo possui algumas limitações. A restrição à evolução imposta
pela condição de entropia usada, ou seja, “se um nó é queimado ele permanece
queimado”. Esta política é vantajosa no tratamento de mudanças topológicas, porém
tem a desvantagem de limitar a evolução da Snake em apenas expansão ou apenas
contração. Outra limitação é o fato do método de reparametrização da Snake
(projeção sobre a malha) ser extrínseco, isto é, depender não somente da forma do
contorno, mas também da maneira como o espaço foi dividido (decomposição
simplicial), bem como do seu posicionamento neste espaço.
52
5
5.1
APLICAÇÕES DOS MÉTODOS SNAKES
Sistema Semi-Automático para Análise de Imagens Digitais
A extração de informações em imagens é extremamente importante na
área biológica, onde a extração de atributos das imagens pode auxiliar no
diagnóstico de doenças. Atualmente a análise de imagens biológicas é realizada de
forma manual, ou apoiada por sistemas muito automatizados, que não inserem o
potencial humano no processo de análise e, conseqüentemente, não contemplam
todas as necessidades do usuário. Neste contexto, esta aplicação é um
processamento digital de imagens para extrair atributos de imagens médicas e
biológicas de forma semi-automática, auxiliando a obtenção de medidas dos objetos
(células e outros) imageados e apoiando a documentação das medidas extraídas. A
extração de atributos é composta principalmente pelas medidas de área, perímetro e
demais características dos objetos que pertencem à imagem, que possibilitam um
diagnostico mais preciso de uma pessoa com determinada doença (SÁ, 2005).
Existe certa dependência desta aplicação em relação às características
da imagem que se extrairão os atributos, uma vez que estas são imagens
fotográficas e possuem uma ampla gama de detalhes e imperfeições. Sendo assim,
a utilização do método Snake para a segmentação da imagem é um fator muito
interessante, pois após uma boa segmentação a imagem perde totalmente as
possíveis imperfeições originais e o processo de extração de seus atributos se torna
relativamente mais apropriado e eficiente, como é apresentada na figura 23.
53
FIGURA 23 – Extração de atributos para objetos previamente segmentados via extração de bordas
(SÁ, 2005).
5.2
Contagem e Mensuração de Fibras Musculares
O uso de imageamento em tomografia computadorizada, ressonância
magnética e radiografia são já relativamente comuns na área da medicina. A
aplicação dos métodos Snakes na contagem e mensuração de fibras musculares
possui resultados satisfatórios. As fibras, entretanto, não estando bem definidas
fazem com que o processo automático de procura das bordas "extravase" para
outras fibras ou mesmo não consiga delimitar uma fibra completamente, como
apresentado na figura 24, sendo realizado a contagem e mensuração automática em
uma imagem original em tons de cinza, sem prévio tratamento (MIYASAKI, 2003).
54
FIGURA 24 – Contagem e mensuração automática de fibras musculares sem um pré-processamento.
Uma idéia natural que surge é tentar fazer o fechamento das “bordas”
de cada fibra, para então submeter à imagem à contagem e mensuração
automaticamente usando o programa Image (MIYASAKI, 2003). O resultado após o
pré-processamento da imagem é apresentado na figura 25.
FIGURA 25 – Contagem e mensuração automática de fibras musculares após a etapa de préprocessamento.
55
5.3
Medição do Disco Ótico
A figura 26 mostra a sua aplicabilidade para medir o disco ótico (retina).
Trata-se de uma tarefa importante, que tem por objetivo monitorar mudanças na
forma e área do disco, que, em muitos casos, indicam problemas como o glaucoma
(atualmente, a segunda maior causa de cegueira) (SILVA, 2004).
FIGURA 26 – Utilização de contornos ativos para a determinação da área do disco ótico.
5.4
Análise de Avalanches
Em Ladret (1999) é sugerida a utilização de Snakes como uma boa
ferramenta para a análise de avalanches de neve. A figura 27 mostra esta aplicação
(SILVA, 2004).
(a)
(b)
FIGURA 27 – Utilização de contornos na análise de avalanches de neve, (a) contorno obtido em um
momento e (b) contornos obtidos em momentos diferentes mostram a evolução da avalanche de
neve.
56
6
O PROJETO: DESENVOLVENDO UM MODELO DISCRETO DE SNAKE
Uma definição em termos computacionais retrata uma Snake como um
conjunto
de
N
pontos
{vi (t ) = (xi (t ), yi (t )), i = 0, K , N − 1} ,
de
controle,
ou
snaxels,
cujas
posições:
são interligadas e variam no decorrer do tempo
(MACHADO, 2003).
Os modelos de energias utilizado no desenvolvimento do projeto são
baseados na Snake tradicional e em suas otimizações, e possui a característica de
atuar sobre a curva de maneira simples. Desenvolveu-se a deformação da Snake
tanto para processos de contração quanto para expansão, possuindo a
característica de manter, da melhor forma possível, as snaxels com critérios de
espaçamento equivalentes. Há um grande esforço em manter uma a eqüidistância
das snaxels, pois, de acordo com a literatura os algoritmos apresentam um melhor
comportamento nestas situações (YOUNG, 1995).
É de extrema importância a definição de alguns filtros de préprocessamento para uma melhor segmentação de objetos com alto nível de
detalhes, pois estes induzem a deformação erronia da Snake em encontrar
contornos que não são realmente os do objeto em questão. Neste contexto, também
foram desenvolvidos seis filtros de pré-processamento da imagem, estes seguem
descritos na seção 6.2.
Para a configuração inicial da Snake são considerados dois tipos de
polígonos fechados: circular e definido pelo usuário. Assim, a criação da Snake por
intermédio de um polígono circular é realizada por uma equação que descreve um
círculo, dado um ponto e seu raio. Para esta configuração também é necessário
especificar a quantidade de snaxels, que serão dispostos pela curva de maneira
eqüidistante. A configuração por um polígono definido pelo usuário descreve a curva
inicial pela interligação de snaxels escolhidas manualmente.
No entanto, a curva inicial depende de uma combinação de energias
para proporcionar a sua evolução até as bordas de interesse. A deformação da
Snake é feita através da ação da energia interna normal, de tensão, rigidez e da
energia externa, iterativamente sobre todos os snaxels.
57
Teoricamente tem-se a energia interna normal e de tensão agindo de
forma conjunta para movimentar e manter um espaçamento uniforme entre os
snaxels. A força interna de rigidez relaciona-se à suavidade da Snake, sendo
normalmente descrita através de Splines sobre as snaxels. Por fim, a energia
externa é definida em função das características de interesse na imagem, neste
caso as bordas (critérios de intensidade do nível de cinza dos pixels).
Em especial, foram desenvolvidos procedimentos para divisão de uma
Snake em outras, possibilitando a segmentação de vários objetos com somente uma
curva inicial, e procedimentos para junção de Snakes, unindo-as para a
segmentação de um objeto em comum. Estes dois procedimentos são acionados
quando houver sobreposição dos pontos de controle da curva.
6.1
Energias Desenvolvidas
As energias desenvolvidas são dispostas tanto para o modelo
convencional ou de contração quanto para o Balloon ou de expansão.
Independentemente do método escolhido para a segmentação é possível que se
realize a subdivisão de uma Snake em várias e a junção de várias em uma só.
6.1.1 Energias Internas
São derivadas da própria curva e possuem a finalidade de deformá-la
de forma a manter um critério de espaçamento de pontos de controle e garantir a
suavidade em se confrontar com a borda do objeto de interesse.
6.1.1.1 Força Tradicional
Esta força se baseia no modelo tradicional proposto por Kass, Witkin e
Terzopoulos e é definida pela componente da força elástica, onde tem o objetivo de
movimentar os pontos de controle em direção ao fechamento da curva ou contração
da Snake. Esta força possui a característica de que uma curva aberta tome a forma
de um segmento de reta e uma curva fechada tome a forma de um ponto.
58
A grande vantagem desta força é o fato de que a cada passo da
deformação da curva os pontos são mantidos com critérios de espaçamento
equivalentes. É muito importante que os pontos de controle sejam mantidos
igualmente espaçados e que haja uma quantidade suficiente destes pontos de
controle, pois a representação do contorno do objeto será melhor representada
nestas situações.
Para a deformação da curva define-se basicamente o cálculo mediante
o produto vetorial dos vetores correspondem aos três pontos de controle vizinhos.
Desta forma, a força elástica atua em um ponto de controle pi puxando-o em direção
ao centro da reta (ponto central), que interliga os seus dois vizinhos pi-1 e pi+1,
conforme mostra a figura 28.
Snake Inicial
FIGURA 28 – Em análise o ponto p1: a deformação é iterativa e ocorre deslocando o ponto analisado
para um novo ponto central, que é o produto vetorial entre os snaxels de p0p1 e p1p2. O processo
segue para todos os pontos iterativamente.
O processo deve ser definido para as componentes em X e Y de todos
os pontos de controle da curva. A definição do ponto central e a atração dos pontos
em sua direção é quem garante que os pontos de controle se deformarão mantendo
a equivalência de distância de seus vizinhos.
O produto vetorial desta força elástica é definido através das equações
para as componentes x e y dos pontos de controle:
⎡⎛ x + x ⎞⎤
EelasticaX ,i = k1 ⎢⎜ i −1 i +1 ⎟⎥
2
⎠⎦
⎣⎝
⎡⎛ y + y ⎞⎤
EelasticaY ,i = k1 ⎢⎜ i −1 i +1 ⎟⎥
2
⎠⎦
⎣⎝
(44)
A constante k define o quanto o ponto de controle deve ser atraído em
59
direção ao ponto central, uma vez que se k for relativamente grande pode ser que
ultrapasse as fronteiras do objeto em análise.
A grande desvantagem desta força é a não deformação em objetos
com limites côncavos, onde o máximo obtido é um segmento de reta nestas regiões.
Outra desvantagem é a não existência de uma força de rigidez referente a uma
maior suavização da curva.
6.1.1.2 Força Baricentro
A força baricentro também é definida pela força elástica, atuando de
forma a puxar os pontos de controle em direção ao baricentro da curva. O baricentro
é o ponto central da curva calculado através das médias dos componentes x e y de
todos os pontos.
Para a deformação dos pontos de controle é baseada na equação da
“Maior Distância” sendo realizada de maneira a movimentar no máximo em 1 pixel
em direção ao baricentro, podendo evidentemente a movimentação ser menor.
Primeiramente deve-se definir a maior distância entre os pontos e o baricentro da
curva e depois realizar a parametrização de todos os pontos em relação a maior
distância, proporcional a todos os pontos. Direção da força elástica atuando sobre
um ponto pi é apresentada na figura 29.
FIGURA 29 – Em análise o ponto p1: a deformação é iterativa e ocorre deslocando o ponto analisado
em direção ao baricentro da curva. O processo segue para todos os pontos iterativamente.
Esta força elástica é definida através das equações para as
componentes x e y dos pontos de controle, atraindo os pontos de controle em
direção ao baricentro (baricentro em x e y) da curva.
60
⎛ baricentroX − x ⎞
EelasticaX ,i = x ± ⎜
⎟
⎝ maiordis tan ciaX ⎠
⎛ baricentroY − y ⎞
EelasticaY ,i = y ± ⎜
⎟
⎝ maiordis tan ciaY ⎠ (45)
Se o ponto em análise for maior do que o baricentro da imagem para
os seus componentes x e y, então a operação utilizada será a subtração do ponto
em análise com a distância que este deve se deslocar em direção ao baricentro,
caso contrário à operação utilizada será a adição. É importante ressaltar que os
pontos de controle se deslocaram no máximo em 1 pixel (ponto de controle que tiver
a maior distância do baricentro da curva) e garantindo a proporção para as
distâncias menores.
Esta força possui a característica da deformidade em regiões
côncavas, pelo fato de serem atraídas, a cada iteração, para o baricentro da curva.
Esta deformação em concavidades não segue nenhuma relação com o objeto em
questão, sendo insuficiente para a maioria dos casos. Porém, esta força não
mantém os pontos de controle igualmente espaçados o que acarreta em uma
deformação ruim para alguns casos. A força Baricentro desempenha apenas o fator
de deformação da curva ou força elástica, a força de rigidez para uma melhor
suavização do contorno não foi estabelecida.
6.1.1.3 Força Mista
Desenvolvida por meio da união da força Tradicional e Baricentro.
Sendo assim, apresenta como características certa invasão em regiões côncavas do
objeto e a preservação de critérios de eqüidistância entre os pontos de controle,
proporcionando uma melhor segmentação de objetos que contenham pouca
concavidade. Esta força se apresenta como certo avanço em relação ao modelo
tradicional, mas, a segmentação de objetos com concavidades maiores ainda não
possuem resultados satisfatórios, pois essa força não age de forma “intuitiva” na
busca por regiões ou bordas ainda não exploradas.
61
6.1.1.4 Força Balão Tradicional e Força Balão Baricentro
A força balão preserva as mesmas características do modelo de força
tradicional ou baricentro, mas ao invés dos pontos de controle serem deformados
para o processo de contração da curva se estabelece o processo de sua expansão.
Neste contexto, para o desenvolvimento da força balão são
estabelecidas rotações de 180º da direção em que os pontos de controle
originalmente se deformariam, provocando conseqüentemente seu afastamento do
baricentro (para a força baricentro) ou a substituição do elemento k da equação (44)
pelo fator negativo de k (para a força tradicional).
A direção dos pontos de controle pode ser representada e
desenvolvida pelo vetor normal ao segmento de reta que liga os pontos vizinhos ao
ponto em análise. A representação gráfica da atuação da força balão de ambos os
casos pode ser observada na figura 30.
FIGURA 30 – Representação da direção dos vetores normais para o processo de expansão da curva.
6.1.2 Energia Externa
A energia externa é obtida a partir da própria imagem e considera os
pixels de borda, ou seja, a energia do gradiente da imagem. Sendo assim, possui a
característica que empurra a curva em direção aos pontos de borda do objeto em
segmentação, até encontrar uma forte descontinuidade dos tons de cinza que
conseqüentemente representa a borda do objeto de interesse.
62
Define-se então o confronto da curva com a borda do objeto através da
quebra brusca dos tons de cinza da imagem. Este por sua vez é estabelecido
através de um limiar de faixas de cinzas (variando de 2 até 255 – conforme a
necessidade do usuário), onde se busca num processo iterativo classificar o ponto
de controle em análise em uma classe de 0 a 255 e verificar se os n pontos vizinhos
pertencem à mesma classe (máscara de convolução).
Para sintetização do conceito abordado é apresentado o exemplo da
figura 31, onde se aplicará a energia do gradiente com um limiar de duas faixas de
tons de cinza. Com um limiar de duas faixas tem-se a representação da classe 0
(primeira faixa) de 0 a 127 e da classe 1 um (segunda faixa) de 128 a 255.
FIGURA 31 – Aplicação da energia externa utilizando-se de um limiar de duas classes de tons de
cinza. O histograma representa a quantidade de tons de cinza da imagem original e da imagem sob o
efeito limiar.
Para este exemplo é como se fossem consideradas, ao invés da
imagem original que contém uma grande quantidade de níveis de cinza, a imagem
com o efeito limiar de duas classes de cinza, onde os pixels com valores de 0..127
(faixa 0) pertencem à cor preta ou com valor 0, e os com valores de 128..255 (faixa
1) pertencentes à cor branca ou valor 255. A possível conformidade com a borda do
objeto será dada quando um ponto de controle da curva sair de uma classe 0
63
partindo para a classe 1 ou vice e versa, caracterizando uma descontinuidade.
A figura 32 representa a conformidade de um ponto de controle da
curva com a borda do objeto, definindo o seu critério de parada. O ponto vi que está
na posição p4,4 da matriz deve ser movido para a posição p2,6, (vi’) devido à
mudança limiar da classe 1 para a classe 0. Para a verificação é utilizado uma
máscara de convolução de N x N dimensões onde todos os pontos da máscara de
convolução devem pertencer a mesma classe limiar de vi, se algum ponto não
pertencer a mesma classe se encontrou um ponto de borda. A figura 31 é aplicada
uma máscara de convolução de dimensão 7x7.
FIGURA 32 – Aplicação da energia externa utilizando-se de um limiar de duas faixas de tons de
cinza. O histograma representa a quantidade de tons de cinza da imagem original e da imagem sob o
efeito limiar (OLIVEIRA, 2000).
A classe do ponto em análise vi é calculada pela da equação abaixo:
Classe de vi = Valor Inteiro (nível de cinza de vi dividido (256 dividido limiar))
Continuação do Exemplo:
Classe do ponto vi = Valor Inteiro (255 dividido (256 dividido 2));
Classe do ponto vi = Valor Inteiro (255 dividido 128);
Classe do ponto vi = 1.
{valor real = 1,99}
64
Quando algum elemento da máscara de convolução possuir a faixa
diferente da faixa do ponto em análise, este deve ser movimentado para a posição
do elemento de faixa diferente, onde provavelmente se encontrou a borda do objeto.
No exemplo acima a classe do elemento da máscara de convolução p2,6 é igual à
zero, com isso o ponto vi em análise (p4,4) deve ser movido para a posição p2,6,
(vi’) devido à mudança limiar da classe 1 para a classe 0 (descontinuidade = força
gradiente).
6.1.3 Energia Confinada
Apesar do fato da energia interna baricentro proporcionar certa
deformação da curva em limites côncavos esta não é realizada de forma “intuitiva” e
muito dependente do objeto a ser segmentado. Sendo assim, a energia confinada
busca o tratamento e melhoramento dos problemas encontrados nos modelos
tradicionais, principalmente no que diz respeito à deformação da curva em regiões
côncavas. Tal energia, assim como os modelos de segmentação via abordagem de
contornos
ativos
Snake
mais
robustos
da
literatura,
possui
energias
e
funcionalidades adicionais que permitam tal tratamento, de forma a buscar por
regiões de contorno ainda não exploradas. Define-se então uma nova energia:
E snake = ∑ Einterna + Eexterna + Econfinada
(46)
6.1.3.1 Força de Rotação
A força de rotação busca por pontos de controle da curva que ainda
não estão sob a borda do objeto onde, através de rotações dos vetores, procura-se
encontrar a borda atribuindo ao ponto de controle da curva o ponto de borda
encontrado.
Aplica-se esta força quando um ponto de controle pi encontrar a borda
do objeto e os seus pontos vizinhos ainda não o encontraram. Então, se estabelece
uma rotação de 45º nos sentidos horários e anti-horários do vetor composto pelos
pontos pi e pi+1 (podendo ser realizado também para o vizinho anterior) na busca
por um ponto de borda do objeto.
65
Tal força proporciona a sua ação de forma “intuitiva”, percorrendo
iterativamente os pontos de controle buscando encontrar de imediato um novo ponto
de borda.
A figura 33 apresenta a ação desta força sobre um vetor composto
pelos pontos pi e pi+1 em análise num processo iterativo:
FIGURA 33 – Aplicação da força de rotação.
6.1.3.2 Criação de Pontos Intermediários
A criação de pontos intermediários estabelece uma distância máxima
entre os pontos de controle. Ao se ultrapassar a distância máxima insere-se na curva
um ponto intermediário, permitindo uma melhor segmentação de objetos com alto
nível de detalhes e curvaturas finas. Deve-se ter uma quantidade razoável de pontos
de controle para segmentar um objeto de forma satisfatória, principalmente em
regiões curvilíneas.
6.2
Filtros de Pré-Processamento Desenvolvidos
O objetivo é que após o pré-processamento, a imagem resultante deve
ser mais adequada para a tarefa de segmentação.
Para o processamento da imagem original são aplicados templates de
acordo com uma máscara de convolução específica, deslocando-o por toda a
imagem de forma seqüencial e causando a transformação dos pixels. Utilizou-se no
projeto máscaras de organização ímpar (3x3, 5x5, etc.) com convolução aperiódica,
onde o resultado é substituído pelo “pixel do centro” da máscara. Para a utilização
de máscaras de organização par (2x2, 4x4, etc.) o resultado deve substituir o
66
“primeiro pixel” da máscara.
Na convolução aperiódica centra-se o template com o primeiro pixel da
imagem atribuindo o valor 0 aos valores inexistentes na imagem, como mostra a
figura 34 com uma máscara de convolução 3x3.
FIGURA 34 – Convolução Aperiódica.
Neste
contexto,
apresentam-se
os
filtros
espaciais
de
pré-
processamento desenvolvidos, suas funcionalidades, templates e o resultado que
este proporciona na imagem. Para a transformação da imagem deve-se percorrê-la
seqüencialmente por todos os seus pixels e aplicando o template específico. O
resultado será uma nova imagem processada.
6.2.1 Filtro da Média
O filtro da média é um tipo de filtro passa baixa que através de uma
máscara realiza a média da vizinhança. Uma Máscara de Média é tal que seus
pesos são positivos e a soma é igual a 1.
Dado uma imagem f(x,y) de N x N pixels:
g ( x, y ) =
1
M
∑ f ( n, m )
( n , m )∈S
onde:
S é o conjunto de coordenadas dos pontos na vizinhança de (x,y), incluindo (x,y);
M é o número total de pontos da vizinhança.
(47)
67
Exemplos de filtros passas baixa:
A figura 35 apresenta o resultado da aplicação desse filtro em uma
imagem original e o seu resultado.
FIGURA 35 – Aplicação do filtro da média.
6.2.2 Filtro da Mediana
Substitui o nível de cinza de cada pixel pelo nível de cinza mediano em
uma vizinhança do pixel.
O nível mediano de um conjunto de valores é tal que exista metade dos
valores menores e metade dos valores maiores. O exemplo da aplicação do filtro da
média é apresentado na figura 36. O pixel central de valor 15 será substituído pelo
valor 20 (nível mediano):
FIGURA 36 – Exemplo da substituição do pixel mediano.
A figura 37 apresenta o resultado da aplicação desse filtro em uma
imagem original e o seu resultado.
68
FIGURA 37 – Aplicação do filtro da mediana.
6.2.3 Filtro Laplaciano
Outra aplicação importante da convolução espacial de uma máscara
com a imagem é o realce (Sharpening) ou Filtragem Passa Alta. É chamada de
Máscara de Realce porque tende a realçar mudanças abruptas de Níveis de Cinza
na Imagem.
A Máscara do Filtro Passa Alta deve ter o peso central positivo e os
pesos periféricos negativos tal que a soma seja igual a Zero.
O exemplo de um filtro passa alta (Operador Laplaciano) é
representado na figura 38:
FIGURA 38 – Máscara do Operador Laplaciano.
A figura 39 apresenta o resultado da aplicação desse filtro em uma
imagem original e o seu resultado.
.
FIGURA 39 – Aplicação do Filtro Laplaciano com a operação de Negação de Cores.
69
6.2.4 Binarização pela Média: Local e Global
O objetivo é transformar uma imagem que possui diversos tons de
cinza em uma imagem em preto e branco, tendo um fator limiar dos níveis de cinza
da imagem. O limiar é resultado da média dos pixels realizada globalmente na
imagem ou localmente através de convolução consecutivas (filtro da média), onde os
pixels da imagens que possuírem o nível de cinza menor que a média serão
transformados para o valor 0 (preto) e os maiores que a média em valor 255
(branco).
Dado uma imagem f(x,y) de N x N pixels:
g ( x, y ) =
1
M
∑ f ( n, m )
(48)
( n , m )∈S
onde:
M é o número total de pontos da vizinhança;
S é o conjunto de coordenadas dos pontos na vizinhança de (x,y), incluindo (x,y);
Se f(x,y) < g(x,y)
então g(x,y) = 0;
senão g(x,y) = 255.
Na figura 40 tem-se uma imagem original com vários tons de cinza e o
resultado da aplicação do filtro de binarização pela média global.
FIGURA 40 – Aplicação do Filtro de Binarização pela Média Global.
6.2.5 Filtro Limiar
Transforma a imagem que contém diversos tons de cinza (0..255) em
uma nova imagem com uma quantidade menor de tons de cinza, de acordo com a
quantidade de limiares (grupos) especificados. A transformação é realizada através
de agrupamentos de faixa de cinza.
70
No exemplo mostrado na figura 41 tem-se uma imagem original e a
aplicação do filtro limiar com cinco limiares de níveis de cinza (5 grupos):
FIGURA 41 – Aplicação do Filtro Limiar igual a 5.
Sendo assim, os pixels da imagem que tinham o nível de cinza entre os
grupos gerados serão transformados de acordo com a figura 42, gerando uma nova
imagem com apenas cinco tons de cinza:
FIGURA 42 – Agrupamento de Níveis de Cinza.
Dado uma imagem f(x,y) de N x N pixels se aplicada à equação da
figura 43, percorre-se todos os pixels da imagem original (f(x,y) de 0..n-1, 0.n-1) e
gera-se uma nova imagem (g(x,y)):
FIGURA 43 – Equação do Filtro Limiar.
71
7
A FERRAMENTA DESENVOLVIDA
A ferramenta para segmentação de imagens por contornos ativos
Snakes foi implementada utilizando a linguagem C++Builder 5, sob a utilização da
programação orientada a objetos (OOP). O objetivo desta ferramenta é ilustrar a
dinâmica de funcionamento dos algoritmos implementados. É importante ressaltar
que a ferramenta atua apenas na etapa de segmentação de objetos pertencentes a
imagens digitais, não tendo uma aplicação específica em alguma área, mas, por sua
vez pode futuramente ser utilizada para esses fins, pois a programação orientada a
objetos possui como principal característica a reusabilidade de suas classes,
métodos e afins.
A utilização de uma interface simples e sugestiva permite aos usuários
um melhor entendimento dos passos realizados para a segmentação de um objeto.
Esta ferramenta é de caráter semi-automático, ou seja, são de extrema importância
a parametrização e experiência do usuário para a obtenção de resultados
satisfatórios. A figura 44 mostra a interface do sistema, com seus botões de
acionamento e campos devidamente rotulados, e painéis que referenciam as
imagens no processo de atuação da Snake e o seu resultado final.
FIGURA 44 – Interface principal da Ferramenta de Segmentação por Contornos Ativos Snake.
72
7.1
Estruturas Utilizadas
A ferramenta possui duas classes principais. A primeira é a classe
“TSnakes” que é referente a configuração do objeto a ser segmentado, método a ser
utilizado na segmentação, matriz que representa a imagem, lista que contém todas
as Snakes para tal segmentação e seus métodos para deformação e filtragem de
pré-processamento da imagem. A classe T-Snakes é mostrada na figura 45.
FIGURA 45 – Representação da Classe TSnakes.
A segunda é a classe “Snake”, mostrada na figura 46, possui a
configuração de cada curva, possui uma variável de instância para a cor e espessura
da curva, quantidade de pontos, lista de pontos de controle da curva com suas
respectivas posições (x, y) na imagem e seus métodos para manipulação dos dados.
73
FIGURA 46 – Representação da Classe Snakes.
74
Computacionalmente, as estruturas principais internas (não são de
interface) utilizadas na implementação do novo modelo e da ferramenta são:
•
Listas
Duplamente
Encadeadas
Circular:
utilizadas
para
a
representação das várias Snakes que podem estar em execução
simultaneamente e para a representação da lista de pontos de
controle da Snake. Cada elemento da lista possui um ponteiro
referenciando o elemento anterior e posterior, além da informação
principal. Como mostra a figura 47:
Objeto da Classe TSnake
Classe TSnake
Representação Lista de Snakes
Objeto da Classe Snake
Classe Snake
Representação da Curva (Lista de Pontos de Controle)
FIGURA 47 – Representação gráfica da estrutura de dados do projeto.
•
Matrizes: formam a representação da imagem, uma vez que uma
imagem é uma matriz de pixels de dimensões N x N,
correspondentes à altura e largura respectivamente. Cada elemento
da matriz possui a cor de cada pixel da imagem real;
•
Registros:
são
estruturas
criadas
pelo
desenvolvedor
que
correspondem a um conjunto de elementos. Por exemplo, o registro
Pontos possui os elementos x (PontosÆx) e y (PontosÆy)
75
correspondentes a sua localização na imagem.
7.2
Preenchimento dos Campos e Passos para a Deformação
Para melhor entendimento do funcionamento da Ferramenta serão
apresentados seus campos e como se realiza a segmentação de um objeto.
Corresponde aos filtros de pré-processamento da
imagem original, uma que vez que uma imagem préprocessada deve estar mais adequada para a tarefa de
segmentação.
Os
Filtros
são:
Média,
Mediana,
Laplaciano, Binarização Global e Local, e Filtro Mediano.
Para melhor entendimento dos filtros leia o capítulo
anterior.
Botões para abrir uma nova imagem a ser segmentada
(a ferramenta suporta apenas imagens .bmp - BitMaps),
salvar uma imagem segmentada (somente com o
contorno do objeto segmentado) e limpar a imagem em
atividade (limpar as Snakes e voltar ao estado inicial).
Informa a configuração da curva inicial definida pelo
usuário. Esta pode ser Circular (dados um ponto central
e o raio) ou ainda Aleatória (dados todos os pontos da
curva). A configuração da Curva Inicial depende da
quantidade de pontos iniciais (campo “Pontos”).
Informam a quantidade de pontos a serem gerados na
curva inicial, a cor da curva e sua respectiva espessura.
Após
parametrizar
estes
campos
e
configurar
a
localização da curva inicial deve-se efetuar a sua
geração no campo “Gerar Snake Inicial”.
76
Corresponde ao critério para a localização da borda do
objeto, onde o usuário deve informar o número de
limiares de cores. Para maior entendimento leia o
capítulo anterior em “Energia Externa”.
Informa
o
método
(Tradicional,
Baricentro,
Balão
Tradicional, Balão Baricentro e Misto) a ser utilizado para
a segmentação de imagens, tempo de pausa na
deformação e distância mínima entre os pontos (se os
pontos se distanciarem além da distância mínima é
criado um novo ponto intermediário), respectivamente.
Inicia a deformação de uma Snake na busca do contorno
do objeto, segundo o método escolhido. Possibilita a
parada forçada da deformação e a visualização do
resultado final da segmentação (borda do objeto).
A ferramenta foi desenvolvida de modo que se possa visualizar a
deformação da Snake desde sua configuração inicial até o confronto com a borda do
objeto de interesse, enfatizando de maneira clara o seu funcionamento. É possível a
segmentação de diversos objetos simultaneamente através da definição de várias
Snakes independentes, tanto para o processo de expansão quanto para contração
da curva. Também há a possibilidade de segmentar vários objetos com somente
uma Snake (para os casos de contração da curva, onde a curva se subdivide de
maneira dinâmica entre todos os objetos) ou ainda a junção de várias Snakes em
uma só (para os casos de expansão da curva).
Para maior sintetização dos conceitos e funcionamento da ferramenta
são apresentados os passos básicos para a segmentação de um objeto de 2 cores,
sem que haja a necessidade de um pré-processamento:
1. Abrir a imagem a ser segmentada. A figura 48 representa uma
imagem recém aberta pela ferramenta;
77
FIGURA 48 – Imagem recém aberta pela ferramenta.
2. Escolher o tipo da seleção (Circular ou Aleatória) da Curva Inicial;
3. Configurar a quantidade de Pontos de Controle iniciais, a cor e a
espessura da Snake;
4. Configurar os pontos iniciais obre a imagem de forma a envolver o
objeto. Se a seleção for do tipo “Circular”, então o usuário deve
fornecer o ponto central e o raio, com isso a ferramenta irá gerar
como curva inicial um circulo com a quantidade de pontos de
controle definidos no campo “Pontos”. Se o tipo for “Aleatório” o
usuário deve selecionar os pontos de controle da Snake Inicial um a
um, com no mínimo 25 pontos;
5. Gerar a Snake Inicial. A figura 49 representa a geração da Snake
inicial pela configuração “Circular”;
FIGURA 49 – Configuração da Snake inicial.
6. Definir o Limiar de Cores: como a imagem é binarizada (somente
duas cores), o número de limiares escolhido deverá ser igual a
78
dois. Com isso a Snake se deformará até sair de uma faixa limiar de
cores para a outra faixa, e conseqüentemente se confrontar com a
borda do objeto de interesse;
7. Escolher o método a ser utilizado na segmentação (podendo ser de
contração ou expansão da curva), o tempo de execução e a
distância mínima para a criação de pontos intermediários. Os
métodos estão dispostos e seguem as características de acordo
com as forças apresentadas no capítulo 6;
8. Iniciar a Deformação. A figura 50 (a) representa a deformação da
Snake pelo método da Força Mista e a figura 50 (b) a divisão em
duas Snakes para a segmentação de dois objetos.
FIGURA 50 (a) – Deformação da Snake.
FIGURA 50 (b) – Divisão da Snake.
9. Visualizar o Resultado Final. Na figura 51 tem-se o contorno final
segmentado pelo método de contornos ativos Snake via a
ferramenta desenvolvida no projeto;
79
FIGURA 51 – Contorno final dos objetos.
10. Salvar o contorno do objeto segmentado pelo método de contornos
ativos Snake.
7.3
Considerações Adicionais
Pelo fato da ferramenta desenvolvida ser de caráter semi-automático é
necessário que haja uma boa habilidade do usuário para a segmentação de imagens
mais complexas, principalmente das que exigem critérios de pré-processamento.
Pode ser que dependendo do objeto a ser segmentado obtenha-se
como resultado final um contorno inconstante, isso se deve pelo fato da ferramenta
não ser implementada com a abordagem de Splines que, teoricamente deixariam o
contorno do objeto mais suave e próximo da realidade.
80
8
EXPERIMENTOS E RESULTADOS
Para a realização de experimentos foram utilizadas imagens com
diferentes características de contexto e de naturezas distintas. Sendo assim, foi
considerado no processo de segmentação, realizado por meio da ferramenta
proposta, as seguintes imagens: preto e branco, coloridas, geométricas, abstratas e
fotográficas. Estas por sua vez são pertencentes a diferentes áreas como imagens
de ressonância magnética, imagens de células e fibras musculares da área da
medicina; imagens de formas simples como quadrados, círculos, triângulos e
imagens abstratas da área da geometria em geral; entre outras. A ferramenta
apresentou, em geral, resultados satisfatórios para todos os tipos de imagens.
A segmentação de imagens fotográficas é um processo que requer
grande habilidade do usuário na especificação de filtros de pré-processamento antes
da tarefa de segmentação por contornos ativos pela ferramenta, pelo fato destas
imagens apresentarem altos níveis de detalhes. Contudo, a ferramenta obteve
resultados satisfatórios mesmo nestas situações.
Em experimentos com imagens que possuem concavidade na região
próxima ao baricentro da curva a segmentação não pode ser efetuada por completo
com somente uma Snake, pelo fato de as forças desenvolvidas se confrontarem e de
certa forma se anularem. A solução adotada foi a utilização de mais Snakes, onde
ao encontrarem provocam a fusão das Snakes em uma só, segmentando os objetos
que possuem estas características.
Este experimento pode ser demonstrado na figura 52. O passo 1
mostra que a curva não conseguiu a deformação em contração correta do objeto e
foi necessária a configuração de uma nova Snake (passo 2) para que se tenha a
fusão posterior num processo de expansão das curvas.
Os passos de 3 a 5 demonstram as Snakes se deformando na busca
pela borda do objeto e o processo de junção de ambas. O resultado final da
segmentação é apresentado no passo 6.
81
FIGURA 52 – Passos de uma situação crítica do experimento e resolução via Junção de duas
Snakes.
82
9
CONCLUSÕES
O método de contornos ativos é uma vigorosa técnica para o processo
de segmentação de imagens digitais que vem apresentando resultados satisfatórios
nas diversas áreas de atuação.
O presente projeto é uma ferramenta de segmentação de imagens,
atuando num processo inicial e retornando parâmetros para a viabilização de
processos posteriores, como análise, reconhecimento e classificação. Por exemplo:
pode ser aplicada para cálculos de perímetros e área de objetos de uma imagem,
modelagem de forma e objetos 3D, rastrear movimentos de vídeos, entre outros.
A forma como o método é implementado, através da definição de
energias, facilita a modificação do método original, possibilitando diversas
adaptações e, conseqüentemente, a obtenção de melhores resultados em cada área
de aplicação.
Além das Energias tradicionais conhecidas na literatura que foram
estudas (intensidade, força balão, etc.), foram criadas outras energias para a
solução de alguns problemas tradicionais de segmentação em regiões côncavas. As
energias desenvolvidas são: a Energia da Rotação e a Energia de Pontos
Intermediários.
Para projetos futuros pode-se realizar a implementação, testes e
verificação da viabilidade do uso de curvas Splines e Bezier na tentativa de uma
maior suavização do contorno das segmentações, definição de algoritmos de pósprocessamento da segmentação por Snakes (quando não produzir o resultado
esperado) e implementação e aplicação dos métodos Snake Gradient Vector Flow e
T-Snakes.
83
REFERÊNCIAS BIBLIOGRÁFICAS
ANGEL, E. Interactive Computer Graphics Top-Down Approach with Opengl.
New York: Pearson, 1999.
BALAN, A. G. R. Técnicas de Segmentação de Imagens Aéreas para Contagem
de População de Aves. São Paulo: [s.n.], 2003.
GIRALDI, G.A. Dual T-Snakes. Thesis Developed at COPPE-UFRJ (Brazil). Disponível em
<http://virtual01.lncc.br/~giraldi/Tese/>. Acesso em 12 de Agosto de 2005.
GONZALEZ, R. C.; Woods, R. E. Processamento Digital de Imagens. São Paulo:
Edgard Blücher, 2000.
MARQUES, J, S. A Link Between Image-Based and Feature-Based Active
Contours. SIGNAL PROCESSING, nº 67, p. 271- 278, 1998.
MACKIEWICH, B. Active Contour Models (“Snakes”).
Disponível em
<http://www.cs.sfu.ca/people/Faculty/Atkins/papers/blairthesis/main/node28.html>.
Acesso em 05 de Abril de 2005.
MENDELS, F., HENEGHAN, C., THIRAN J. P. Identification of the Optic Disk
Boundary in Retinal Images using Active Contours, submitted, 1999.
NGOI, K. P., JIA, J.C. An Active Contour Model for Color Region Extraction in
Natural Scenes, IMAGE AND VISION COMPUTING, p. 955-966, 1999.
PICHUMANI, R. Construction of A Three-Dimensional Geometric Model for
Segmentation and Visualization of Cervical Spine Images. Ph.D thesis, Medical
Informatics of Stanford University, 1997.
RIBEIRO, B. Suavização de Imagens – Image Smoothing. Disponível em
<http://www.ic.uff.br/~aconci/suavizacao.pdf>. Acesso em 30 de Abril de 2005
SANTOS, V. T. Segmentação de Imagens Mamográficas para Detecção de
Nódulos em Mamas Densas. São Paulo: [s.n.], 2002.
SONKA, M.; HLAVAC, V.; BOYLE, R. Image Processing, Analysis and Machine
Vision. Chapamn & Hall Computing: London, 1998.
TRUCCO, E.; VERRI, A. Introductory Techniques for 3-D Computer Vision.
Prentice Hall: New Jersey, 1998.
WILLIAMS, D.; SHAH M. A Fast Algorithm for Active Contours and Curvature
Estimation. CVGIP:IMAGE UNDERSTANDING, vol. 55, nº 1, January, p. 14-26,
1992.
KASS, M.; WITKIN, A.; TERZOPOULOS, D. Snakes: Active Contour Models. In:
INTERNATIONAL JOURNAL OF COMPUTER VISION, 1988.
XU, C.; PRINCE, J. L., Gradient Vector Flow: A New External Force for Snakes,
IEEE PROC. CONF. ON COMP. VIS. PATT. RECOG., p. 66-71, 1997.
XU, C.; PRINCE, J. L. Generalized Gradient Vector Flow External Forces for
Active Contours. SIGNAL PROCESSING, nº 71, p. 131-139, 1998.
84
YOUNG,
D.
Active
Contour
Models
(Snakes).
Disponível
em
<http://www.cogs.svsx.ac.uk/users/davidy/teachvision/vision7.html>. Acessado em
22 de Outubro de 2005.
PIMENTEL, B. Segmentação de Imagens Médicas utilizando modelos de Active
Contour. Departamento de Ciência da Computação da Universidade Federal de
Minas
Gerais.
Disponível
em
<http://www.verlab.dcc.ufmg.br/projetos/brunosp/modsnake.htm>. Acesso em 27 de
Abril de 2005.
PEREIRA, A. Estudo e Implementação de Filtros para Processamento Digital
de Imagem. Bacharelado em Ciência da Computação, Faculdade de Informática de
Presidente Prudente – FIPP, p.11-12, 1996. (Monografia em Bacharelado em
Ciência da Computação).
MACHADO, C. C. M.; GALVÃO, L. R.; VANDERLEI, T. A.; SANTOS W. Y. R. Uma
ferramenta de extração de bordas utilizando T-Snakes. Centro de Informática,
Universidade Federal de Pernambuco – UFPE. Recife – PE, 2003.
MARQUES, O. F.; VIEIRA H. N., Processamento Digital de Imagens. Rio de
Janeiro: Brasport, 1999.
MIYASAKI, R., Splines e Contorno Ativo em Aplicações de Imagens Médicas.
UNESP - Licenciatura em Matemática. Presidente Prudente, 2003.
OLIVEIRA, M. C. F., Segmentação de Imagens por Contornos Ativos Snakes,
Instituto de Ciências Matemáticas e de Computação, 2000.
SÁ, A. O., Sistema Semi-Automático para Análise de Imagens, Bacharelado em
Ciência da Computação, Faculdade de Informática de Presidente Prudente – FIPP,
2005. (Monografia em Bacharelado em Ciência da Computação).
SILVA, F. A.; ALMEIDA, L. L.; PEREIRA, J. R.;BARBEIRO, T. L. S., Contornos
Ativos – Snakes, Departamento de Engenharia Elétrica, Escola de Engenharia de
São Carlos – USP, 2004.
SILVA, J. P. M., Geo-Snake : uma aplicação da técnica snake em imagens
geográficas. Escola de Informática – Curso em Ciência da Computação. Pelotas,
2003. (Monografia em Bacharelado em Ciência da Computação).