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:

Para a diferença  entre duas componentes C1 ,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 (C1 ,C2 ) = min w(vi , v j ),  vi ∈ C1 , 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 (C1 ,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 (C1 ,C2 ) > MInt(C1 ,C2 )

D =

f alse                 caso contrário                        (3)

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

MInt(C1 ,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.

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