UTILIZAÇÃO DE UM MODELO DE CONTORNO ATIVO PARA EXTRAÇÃO DE BORDAS EM IMAGENS
UTILIZAÇÃO DE UM MODELO DE CONTORNO ATIVO PARA EXTRAÇÃO DE ARESTAS EM IMAGENS
( Instituto Militar de Engenharia )
( Instituto de Matemática Pura e Aplicada )
Esse projeto é fruto de um trabalho realizado por Bruno Eduardo Madeira sob a orientação do professor Luiz Velho durante o curso de Processamento de Imagens ministrado regularmente no Instituto de Matemática Pura e Aplicada ( IMPA ).
Um agradecimento especial deve ser feito ao professor Gilson Giraldi da UFRJ que indicou os artigos que serviram como base para realização do trabalho, além de fornecer uma série de dicas para a implementação do protótipo.
Os artigos utilizados como referência foram os seguintes:
On Active Contours Models and Ballons, Laurent D. Cohen
Tracking Deformable Objects in the Plane Using an Active Contour Model, Fréderic Leymarin & Martin D. Levine
Verificar a aplicabilidade de modelos de contorno ativo como uma ferramenta de extração de arestas e segmentação em imagens.
Os modelos de Contorno Ativo foram introduzidos por Kass, Witkin e Terzoupoulos em 1987. A idéia geral do modelo é a utilização de uma curva de minimização de energia para extrair características importantes de uma imagem. Essa energia associada à curva é definida de forma a que ela seja mínima quando a curva se encontre sobre uma região com as características que se deseja extrair, dessa forma a função de energia passa a funcionar como uma função objetivo em um problema de otimização.
As aplicações de modelos de contorno ativo que mais se destacam se encontram nas áreas: processamento de imagens médicas, segmentação e tracking.
O modelo matemático adotado foi baseado no modelo de Snakes original proposto por Kass e Terzopolos utilizando uma força "Balloon" proposto por L. D.Cohen .
Nesse modelo definimos uma Snake como sendo uma curva plana parametrizada:
O parâmetro s é responsável por definir o formato da curva e o parâmetro t permite que a curva se deforme com o tempo.
Define-se uma função de energia potencial associada a Snake, de forma que essa energia seja mínima quando a Snake se encontre sobre as arestas da imagem. Dessa maneira o problema de extração de arestas é convertido em um problema de otimização.
O problema de otimização a ser resolvido é o de encontrar a curva que minimiza o seguinte funcional de energia:
O termo torna a Snake resistente à tração, e o termo torna a Snake resistente a flexão.
O termo faz com que a Snake tente se posicionar nas regiões da imagem onde o módulo do gradiente é alto, ou seja,
esse é o termo responsável pela detexão das arestas.
A equação de Euler-Lagrange associada a esse funcional é:
Um problema nessa EDP está no fato de que a Snake inicial deve estar muito próxima das arestas da imagem para que estas causem uma atração sobre a Snake. Isso fez com que fosse inserido na EDP uma força normal a curva ( Ballon ), como sugerido por Cohen. Dessa forma a Snake apresenta uma dinâmica interna que pode ser utilizada para "inflar" ou "esvaziar" a Snake. Quando a Snake passa sobre uma aresta as forças entram em equilíbrio e o sistema entra em um estado estacionário.
Por uma questão de simplicidade optou-se por definir o coeficiente de resistência a tração e o coeficiente de resistência a flexão como constantes ao longo da Snake.
Dessa forma a EDP que foi utilizada no protótipo foi a seguinte:
onde n é o vetor normal unitário à Snake no ponto ( p, q ).
Acrescentou-se a essa EDP uma restrição que conciste em restringir o espaço de curvas admissíveis apenas as curvas fechadas. Essa restrição é importante pois serve como condição de contorno para o sistema.
É evidente que uma abordagem algébrica para essa EDP é impraticável, o que sugere uma abordagem numérica para o problema.
Para que a EDP apresentada anteriormente seja solucionada numericamente, é necessário que a Snake seja discretizada no tempo e no espaço.
A discretização da Snake no espaço corresposde a escolha de uma forma de representação para sua geometria. Optou-se por utilizar uma representação por aproximação poligonal. Dá-se o nome de snaxel à cada vertice da linha poligonal que representa a Snake.
A discretizacão da Snake no tempo está intimamente ligado à solução da EDP. Para que pudesse ser feito um esquema simples de solução por diferenças finitas, foi utilizado uma discretização uniforme.
Foram feitas as seguintes aproximaçoes por diferenças finitas para as derivadas parciais:
O gradiente de uma imagem Ψ calculada no pixel ( i , j ) é aproximado da seguinte maneira:
O valor do gradiente em um ponto qualquer da imagem é calculado utilizando interpolação bilinear do gradiente calculado nos quatro pixeis que envolvem esse ponto.
O vetor normal unitário calculado em cada snaxel foi aproximado pela soma dos vetores normais dos lados adjacentes ao snaxel
Essas aproximações levam a um esquema de solução da EDP onde a Snake evolui no tempo através da solução de um sistema linear pentadiagonal.
Xt é uma matriz que contém em cada linha a coordenada de um snaxel da Snake
P é uma matriz que contém em cada linha o valor calculado em cada snaxel, onde ψ é a imagem e n é o vetor unitário normal à Snake.
hi é a distância entre o snaxel xi e o snaxel xi+1
I é a matriz identidade
τ é o tamanho dos intervalos de discretização do tempo
Foi necessário acrescentar uma heurística de inserção e remoção de snaxels para evitar erros numéricos gerados pela discretização das derivadas, por esse motivo as dimensões das matrizes do sistema são alteradas durante as iterações.
Foi acrescentado também uma restrição sobre o deslocamento dos snaxels. Os snaxels não podem se deslocar de uma distância superior a um pixel em uma única iteração.