Funcional de Mumford & Shah

Introdução

Uma questão central na visão computacional é a simplificação de uma dada imagem, reduzindo-se as informações dessa imagem para regiões mais ou menos homogêneas. Uma procura por partições da imagem em conjuntos finitos de áreas, onde a informação não útil da imagem original foi filtrada. Isto é conhecido como o problema da segmentação. O resultado é uma “caricatura” da realidade onde somente a parte importante está presente, sendo que os detalhes desnecessários e ruídos são extraídos. Como exemplo queremos detectar automaticamente defeitos em imagens de madeira por computador. Isto é também um dos principais interesses em aplicações industriais como controle de qualidade, inspeção automática de peças em fábricas ou visão robótica. Existem vários métodos usualmente utilizados para fazer isto, tais como eliminação de pequenas regiões, thresholding, algoritmos de expansão e compressão e filtros de frequência. Mais para várias aplicações esses métodos são muito imprecisos. Por exemplo, quando o método thresholding é aplicado para uma imagem de madeira, permanecerá uma quantidade enorme de pequenas regiões não desejáveis. Por outro lado se formos mais rigoroso nesse método, informações necessárias serão descartadas.


Imagem Original (Madeira)                                              Aplicado Thresholding
 

Segmentação Mumford-Shah

Este é um método mais preciso para a segmentação, baseado na equação funcional da energia de Mumford-Shah mostrada abaixo:


Imagem Original (Madeira)                                              Aplicado Mumford-Shah
 

Abaixo apresentamos uma sequência de imagens segmentadas pelo método Mumford-Shah. Na primeira imagem, cada ponto representa uma região. Na primeira segmentação, os pontos vizinhos foram agrupados numa mesma região segundo o critério de menor energia. O valor do nível de cinza dos pontos desta nova região é a média dos pontos agrupados.

 

Equação Funcional de Mumford-Shah

 

E(m,K)

– Energia funcional de Mumford-Shah em função de

m

e da fronteira K

g(x,y) – função intensidade de luz no ponto x,y.

W – Domínio da imagem, geralmente um retângulo.

K – Fronteira entre regiões.

Wi – Decomposição da imagem em “piece-wise”.

W = W1 È W2 È … È Wn È K

l(K) – comprimento dos arcos das bordas (fronteiras).

m(x,y) – função diferenciavél dentro de cada região Wi.

l – parâmetro de escala

A função g(x,y) é suave (valor de gradiente pequeno) dentro de cada região Wi (piece-wise), e é descontínua (valor de gradiente elevado) no cruzamento com as bordas (fronteiras entre regiões).
Para o nosso caso, a função m(x,y) será uma função constante, que é diferenciável dentro da região. E esse valor constante será a média dos valores de intensidade g(x,y) de cada ponto da região.

Agora vamos interpretar o significado de cada termo da equação funcional da energia de Mumford-Shah:

     Mede se m(x,y) é uma boa aproximação de g(x,y).
Quanto melhor a função m(x,y) se aproximar da função g(x,y), menor será a contribuição desse termo para o valor da energia.

    Calcula a variação mínima de m(x,y) dentro de cada região sem a borda.
No nosso caso como a função m(x,y) será o valor média dos pontos de g(x,y) dentro da região e portanto um valor constante, não existirá variação, assim este termo será sempre zero.

    Calcula o comprimento das fronteiras multiplicado por um parâmetro de escala l.
Quanto maior o comprimento das fronteiras, maior será a contribuição desse termo para o valor da energia. Ainda esse valor será multiplicado por um parâmetro que funciona como um peso.

Energia Funcional Simplificada de Mumford-Shah

m(x,y) – Função constante dentro de cada região e é a média dos valores de g(x,y) em cada região. A função da energia simplificada de Mumford-Shah fica em função apenas de K (fronteiras das regiões).

Critério de Junção

Dado duas regiões adjacentes Oi e Oj separadas por uma fronteira comum

d

(Oi, Oj) e o valor de energia E(

m

,K). Uma nova segmentação (

m

‘,K’) será obtida, removendo-se a fronteira comum

d

(Oi, Oj) dessas duas regiões adjacentes. Esta nova segmentação:

(m‘,K’) = (m,K) \ d(Oi, Oj) é agora chamada uma subsegmentação.

Se a energia dessa nova subsegmentação for menor que a energia anterior (antes de juntarmos as duas regiões), ou seja:

E(m‘,K’) < E(m,K)

então,  é interessante a junção dessas duas regiões. Porém antes de juntarmos estas duas regiões devemos fazer o mesmo para todas as regiões vizinhas à estas duas regiões Oi e Oj e verificarmos qual é a junção que ocasionará o maior decréscimo de energia.

Caso não se encontre nenhuma região adjacente que ocasione nenhum decréscimo de energia, ou seja:

E(m‘,K’) >= E(m,K)

então, a segmentação (m,K) é chamada de 2-normal.

Quando não for mais possível juntar nenhuma região, deve-se aumentar o valor de lambda. O incremento de lambda poderá ser linear ou exponencial.

Implementando o Modelo Simplificado Mumford-Shah

O critério de juntar duas regiões Oi e Oj está na dependência do sinal de E(K)\

d

(Oi, Oj) – E(K), no qual é apenas o decréscimo de energia. Assim a equação para o critério fica:


onde:

|Oi| – Área da região Oi

|Oj| – Área da região Oj

mi – valor de intensidade da região i

mj – valor de intensidade da região j

ld(Oi, Oj) – Comprimento da fronteira entre as regiões Oi e Oj

O critério foi calculado da seguinte maneira:

 

Exemplos


Imagem Original                                                   Lambda 1 – 800

Lambda 1 – 10.000                                           Lambda 1 – 100.000

Imagem Original                                                          Lambda 1 – 800

 

Observação

Uma vez definida as regiões ficou fácil determinar as bordas de interesse da imagem original. Onde o valor da intensidade muda de valor é uma borda, assim pintamos esse ponto de preto, caso ele se mantenha o mesmo pintamos de branco. Assim para os exemplos anteriores temos:

 

Links

Internos

  1. SMS – The supervised color image segmentation method

Externos

  1. Implementação de Mumford & Shah para GPU (Real-Time Minimization of the Piecewise Smooth Mumford-Shah Functional)
  2. Artigo MS GPU: Real-Time Minimization of the Piecewise Smooth Mumford-Shah Functional
  3. Material de Imagem: The Berkeley Segmentation Dataset and Benchmark

Sobre o Autor

possui graduação em Ciências da Computação pela Universidade Federal de Santa Catarina (1989) e Doutorado Acadêmico (Dr. rer.nat.) em Ciências da Computação pela Universidade de Kaiserslautern (1996). Atualmente é professor Associado da Universidade Federal de Santa Catarina, onde é professor do Programa de Pós-graduação em Ciência da Computação e dos cursos de graduação em Ciências da Computação e Sistemas de Informação. É também professor e orientador de doutorado do Programa de Pós-Graduação em Ciências da Computação da Universidade Federal do Paraná - UFPR. Tem experiência nas áreas de Produção de Conteúdo para TV Digital Interativa, Informática em Saúde, Processamento e Análise de Imagens e Engenharia Biomédica, com ênfase em Telemedicina, Telerradiologia, Sistemas de Auxílio ao Diagnóstico por Imagem e Processamento de Imagens Médicas, com foco nos seguintes temas: analise inteligente de imagens, DICOM, CBIR, informática médica, visão computacional e PACS. Coordena o Instituto Nacional de Ciência e Tecnologia para Convergência Digital - INCoD. É também Coordenador Técnico do Sistema Integrado Catarinense de Telemedicina e Telessaúde (STT/SC), coordenador do Grupo de Trabalho Normalização em Telessaúde do Comitê Permanente de Telessaúde/Ministério da Saúde e membro fundador e ex-coordenador da Comissão Informática em Saúde da ABNT - ABNT/CEET 00:001.78. Atualmente também é membro da comissão ISO/TC 215 - Health Informatics. Foi coordenador da RFP6 - Conteúdo - do SBTVD - Sistema Brasileiro de TV Digital/Ministério das Comunicações. Foi o criador e primeiro Coordenador do Núcleo de Telessaúde de Santa Catarina no âmbito do Programa Telessaúde Brasil do Ministério da Saúde e da OPAS - Organização Pan-Americana de Saúde e criador do Núcleo Santa Catarina da RUTE - Rede Universitária de Telemedicina.