Segmentação com Grafos: Felzenszwalb and Huttenlocher method (FH)

Visão Geral de Segmentação Baseada em Grafos

Segmentação baseada em grafos é um termo genérico para métodos de segmentação baseada em regiões onde se modela as relações topológicas entre regiões através de um grafo e se utiliza este grafo no processo de conexão e reconexão de regiões objetivando atingir uma segmentação ótima. Há vários enfoques,

  1. algus onde o grafo é o aspecto central e
  2. outros, híbridos, onde parte do processo é realizado sob controle de um grafo e parte é realizada de outra forma.

Este capítulo é dedicado ao primeiro grupo.  Deste grupo escolhemos o método de Felzenszwalb and Huttenlocher como um modelo exemplar e que vamos utilizar para demonstrar o princípio. Métodos híbridos vamos abordar mais adiante através do exemplo da Pós-Segmentação baseada em Grafos: Método de Redes de Gradientes (GNM).

Método de Felzenszwalb and Huttenlocher

O algoritmo de segmentação utilizando grafo proposto em (FELZENSZWALB; HUTTENLOCHER,  2004), tem como base um predicado para medir os limites entre duas regiões, utilizando um grafo para a representação da imagem.

Inicialmente se tem a ideia de representar a imagem na forma de um grafo, remetendo à definição de grafo definido como

  • um conjunto não-vazio de nós (vértices)  e
  • um conjunto  de arcos (arestas)

tais que cada arco conecta dois nó s.

Com base nesta definição  tem-se um grafo G = (V, A) não direcionado com:

  • vértices vi  V sendo o conjunto  de elementos a ser segmentado e
  • as arestas (vi , v j ) A correspondendo o par de vértices vizinhos.

Cada aresta (vi , v j ) A possui um peso não negativo w(vi , v j ) correspondente  à medida de dissimilaridade  entre dois elementos vizinhos vi  e v j .

No caso de imagens os elementos em V são os pixels  e o peso w de uma aresta é uma medida de dissimilaridade  (e.g., diferença de cor, textura ou outra característica local) entre dois pixels conectados por uma aresta

No FH uma segmentação S e´ uma partição de V em componentes tal que cada componente C S corresponde  a uma componente  conexa em um grafo Gl = (V, Al) onde Al A.

Toda segmentação é induzida por um subconjunto  de arestas em A. Em termos de resultado de segmentação espera-se que possua arestas que conectem vértices  na mesma componente  conexa com pesos baixos  e arestas que conectem vértices de componentes conexas diferentes com pesos maiores.

Para o cálculo da medida de dissimilaridade  define-se um predicado que compara a diferença entre as componentes com a diferença interna de uma componente:

Int(C) = max w(e)e MinimumSpanningTree(C,E )      (1)

A árvore expandida de custo mínimo MinimumSpanningTree(C,E ) é calculada com base nas diferenças entre regiões:

mst-branco

Para a diferença  entre duas componentes C,C2 V define-se como sendo o valor da aresta de menor peso que liga duas componentes.  Definido pela equação (2)  abaixo:

Di f (C,C2 ) = min w(vi , v j ),  vi C, v j C2 e (vi ,v j ) E                  (2)

O predicado para comparação de regiões calcula  se existe alguma evidência de limites  entre duas componentes através da verificação se a diferença externa entre as componentes  Di f (C,C2 ) é relativamente  maior que a diferença interna de ao menos uma das componentes, Int(C1 ) e Int(C2 ).

Opredicado é definido como:

true   se    Di f (C,C2 ) > MInt(C,C2 )

D =

f alse                 caso contrário                        (3)

Onde a mínima diferença interna, MInt, é definida por:

MInt(C,C2 ) = min (Int(C1 ) + τ (C1 ), Int(C2 ) + τ (C2 ))                   (4)

O τ é a uma função de limiar que é utilizada para controlar o grau para o qual a diferença entre as componentes deve ser maior que a diferença interna. A função τ é definida por:

τ (C) = k/|C|   (5)

Onde |C| é o tamanho da componente C e k um parâmetro constante.  Uma vantagem desta função  de limiar é o fato que se pode  alterar  a função .

Exemplos de FH providos pelos Autores

Segmentation parameters: sigma = 0.5, K = 500, min = 50.

Segmentation parameters: sigma = 0.5, K = 1000, min = 100.

Exemplos de FH produzidos no LAPIX

Nos exemplos abaixo temos:

  1. Imagem original
  2. Padrão utilizado para gerar distância de Mahalanobis em RGB
  3. Segmentação com FH utilizando predicado de disimilaridade em RGB
  4. Segmentação com FH utilizando predicado de disimilaridade baseado em métrica de Mahalanobis

Clique nas imagens para ampliar.

fh0

fh1

fh2

Links

Internos

  1. Pós-Segmentação baseada em Grafos: Método de Redes de Gradientes (GNM)
  2. Extensão a FH: Weighted Felzenszwalb and Huttenlocher method (WFH)
  3. Artigo: Improving Graph-Based Image Segmentation Using Nonlinear Color Similarity Metrics [2015]
  4. Dissertação de Luis Eduardo de Carvalho (rascunho longo)

Externos

  1. Artigo: Effcient Graph-Based Image Segmentation [2004]
  2. Página do FH no MIT
  3. Código-Fonte do FH original no MIT

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.