UTILIZAÇÃO DE UM MODELO DE CONTORNO ATIVO PARA EXTRAÇÃO DE ARESTAS EM IMAGENS

 

 

 

Bruno Eduardo Madeira

( Instituto Militar de Engenharia )

 

Luiz Velho

( Instituto de Matemática Pura e Aplicada )

 

 

CRÉDITOS

    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  

 

OBJETIVO

    Verificar a aplicabilidade de modelos de contorno ativo como uma ferramenta de extração de arestas e segmentação em imagens.

 

INTRODUÇÃO

    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.  

 

MODELO MATEMÁTICO

   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.

 

REPRESENTAÇÃO DO MODELO

   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.

             

    Onde temos:

  

                   

     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.

 

FUNCIONAMENTO DO PROTÓTIPO

 Os seguintes passos são executados para que as arestas sejam extraídas:

         1) A Imagem inicial é carregada.                                       2)  Eliminam-se  os ruídos da imagem 

 

        3) Calcula-se a norma do gradiente da imagem                4)  Define-se a curva   inicial 

     

 

5) Soluciona-se iterativamente a EDP até que o sistema atinja um estado estacionário

 

 

EXEMPLOS DE RESULTADOS  OBTIDOS