Segmentação de Imagens com Passeios Aleatórios …cef/mac499-12/monografias/...4 A segmenta˘c~ao esperada de uma imagem de ru do puro e igual a obtida em uma imagem uniforme. Je

IntroducaoO metodo de Passeios Aleatorios

Comparacoes com outros metodosImplementacao

ConclusoesReferencias

Segmentacao de Imagens comPasseios Aleatorios em Grafos

Jefferson Serafim Ascaneo

Orientador: Prof. Dr. Paulo A. V. de Miranda

Departamento de Ciencia da ComputacaoInstituto de Matematica e Estatıstica

Universidade de Sao Paulo

Novembro de 2012

Jefferson Serafim Ascaneo Segmentacao de Imagens com Passeios Aleatorios em Grafos

2/ 30




Agenda

1 Introducao

2 O metodo de Passeios Aleatorios

3 Comparacoes com outros metodos

4 Implementacao

5 Conclusoes

6 Referencias


3/ 30




Segmentacao de imagensObjetivos

Agenda

1 IntroducaoSegmentacao de imagensObjetivos



4 Implementacao

5 Conclusoes

6 Referencias


4/ 30





O que e segmentacao de imagens?

E a atribuicao de rotulos aos pixels de uma imagem,de forma que pixels que pertencam ao mesmo rotulotenham caracterısticas em comum.

Permite analisar cada segmento de forma separada,e isolar elementos de interesse.


5/ 30





Segmentacao de imagens com sementes

Alguns pixels ja estao rotulados,o algoritmo deve usar isto para determinaros rotulos dos pixels restantes.


6/ 30





Objetivos

Implementar o metodo de Passeios Aleatorios,e integra-lo aos programasCAOS (Computer-Aided Object Segmentation)e BIA (Brain Imae Analyzer).

Compara-lo a outros metodos, tambem baseados em grafos.


7/ 30




PreliminaresPasseios AleatoriosAplicacao a segmentacao de imagensO problema de DirichletPropriedades

Agenda

1 Introducao

2 O metodo de Passeios AleatoriosPreliminaresPasseios AleatoriosAplicacao a segmentacao de imagensO problema de DirichletPropriedades


4 Implementacao

5 Conclusoes

6 Referencias Jefferson Serafim Ascaneo Segmentacao de Imagens com Passeios Aleatorios em Grafos

8/ 30





Preliminares

Grafo G = (V ,E )e pesos w(e) > 0 para toda aresta e ∈ E .

Um vertice v ∈ V esta associado a um pixel da imagem.Os pesos sao determinados a partir da imagem original.Ex.: diferenca entre valores dos pixels. (complemento)


9/ 30





Passeios Aleatorios

Imagine um bebado andando pelos vertices do grafo.A probabilidade dele ir para um vertice vizinhoe proporcional ao peso da aresta.

Pr(eu,v ) =w(eu,v )∑

w∈N(u)

w(eu,w )

O passeio termina ao chegar em um vertice rotulado.


10/ 30





Aplicacao a segmentacao de imagens

Para cada vertice v e rotulo s,calcular a probabilidade de um passeio aleatorioque comeca em vterminar no rotulo s.

Atribuir o verticeao rotulo com maior probabilidadede ser o fim do passeio.


11/ 30





O problema de Dirichlet

Sejam

di =∑

∀j∈N(i)

w(ei ,j)

Lij =

di se i = j−wij se vi e vj sao adjacentes0 caso contrario


12/ 30






Uma versao combinatoria da integral de Dirichletpode ser definida como

D[x ] =1

2xTLx =

1

2

∑eij∈E

wij(xi − xj)2 (1)

Uma funcao harmonica combinatoria e uma funcao x queminimiza (1).


13/ 30






A funcao x e um vetor de tamanho |V |sujeito a seguinte restricao:

Escolha um rotulo s.xv = 1 se v pertence a se xv = 0 se v pertence a um rotulo diferente de s.

Precisamos encontrar o valor de xpara os vertices nao rotulados.


14/ 30





Solucao do Problema de Dirichlet

Separando os vertices emVM (marcados/rotulados) e VU (nao marcados):

D[xU ] =1

2

[xTMxTU

](LM BBT LU

)(xMxU

)(2)

=1

2(xTMLMxM + 2xTU BT xM + xTU LUxU) (3)


15/ 30





Solucao do Problema de Dirichlet

Diferenciando (3) e encontrando o ponto crıtico (que e omınimo):

LUxU = −BT xM

E um sistema linear esparso com |VU | variaveis desconhecidas.Como o grafo e conexo, possui solucao unica.

Solucionamos este sistema linear para cada rotulo s,encontrando as probabilidades que querıamos.


16/ 30





Propriedades do metodo

1 Segmentos conectados as sementes;

2 A K-tupla de probabilidades para cada verticee igual a media ponderadadas probabilidades dos vertices vizinhos;

3 A solucao das probabilidades e unica;

4 A segmentacao esperada de uma imagem de ruıdo puroe igual a obtida em uma imagem uniforme.


17/ 30




Segmentacao do calcaneoClassificacoes

Agenda

1 Introducao


3 Comparacoes com outros metodosSegmentacao do calcaneoClassificacoes

4 Implementacao

5 Conclusoes

6 Referencias


18/ 30





(a) RM de um pe (b) Gabarito (c) Sementes

Figura: (a) Fatia de uma imagem 3D de RM de um pe de nossos dadosexperimentais. (b) Gabarito de segmentacao do osso calcaneo. (c)Exemplo de um conjunto de sementes obtido pela erosao e dilatacao dogabarito de segmentacao.


19/ 30





(a) IRFC (b) RFC+GC (c) Passeios Aleatorios

Figura: Resultados de segmentacao do calcaneo.


20/ 30





0 5

10 15 20 25 30 35 40

1st 2nd 3rd

Fre

qu

en

cy

IRFCRFC+GC

RW(p=20)

0 5

10 15 20 25 30 35 40

1st 2nd 3rd

Fre

qu

en

cy

IRFCRFC+GC

RW(p=20)

(a) Segmentacao do calcaneo (b) Segmentacao do talus

Figura: Para cada imagem individual, os metodos podem ser classificadosde acordo com seus valores medios do coeficiente de Dice, comoprimeiro (melhor), segundo, ou terceiro (pior). Calculando a frequenciapara cada posicao de classificacao, temos a distribuicao de classificacao:(a) para a segmentacao do calcaneo, e (b) para a segmentacao do talus.


21/ 30





0.5

0.6

0.7

0.8

0.9

1

0 2 4 6 8 10

Dic

e

Erosion radius (pixels)

IRFCRFC+GC

RW(p=20)

(a) Acuracia media pelo coeficientede Dice

0

100

200

300

400

500

600

0 2 4 6 8 10

Tim

e (

ms)

Erosion radius (pixels)

IRFCRFC+GC

RW(p=20)

(b) Tempo medio de execucao

Figura: Segmentacao 2D de fatias da coluna vertebral, em imagens detomografia computadorizada. Alem de ter um desempenho inferiorneste conjunto de imagens, o algoritmo de Passeios Aleatorios (RW)possui tempo de execucao bem acima dos outros algoritmos.


22/ 30




SegmentacaoInterface

Agenda

1 Introducao



4 ImplementacaoSegmentacaoInterface

5 Conclusoes

6 Referencias


23/ 30





(a) Marcadores (b) Segmentacao (c) Probabilidades

Figura: Segmentacao de um passaro com marcadores de objeto e fundo


24/ 30





Figura: Resultado de uma segmentacao 2D no programa CAOS


25/ 30





Figura: Resultado de uma segmentacao 3D de uma ressonanciamagnetica sintetica (do BrainWeb - Simulated Brain Database) noprograma BIA


26/ 30




Agenda

1 Introducao



4 Implementacao

5 Conclusoes

6 Referencias


27/ 30




Conclusoes

Apresenta resultados superiores em alguns conjuntos de imagens.

Porem, possui grande sensibilidade a certos parametros.

Os pesos das arestas do grafoforam elevados a uma potencia p,e os resultados obtidos variaram bastantede acordo com este valor.


28/ 30




Conclusoes

Alem disso, tambem possui sensibilidadea localizacao das sementes,algo que nao ocorre com outros metodos.

Testes com raios de erosao diferentes para objeto e fundomostram que, em algumas imagens,o desempenho e significativamente reduzidoquando as sementes nao estao equidistantes da borda correta.


29/ 30




Agenda

1 Introducao



4 Implementacao

5 Conclusoes

6 Referencias


30/ 30




Referencias

P.G. Doyle and J.L. Snell.

Random walks and electric networks.

Carus mathematical monographs. Mathematical Association of America,1984.

Leo Grady.

Random walks for image segmentation.

IEEE Trans. Pattern Anal. Mach. Intell., 28(11):1768–1783, November2006.

Ali K. Sinop and Leo Grady.

A Seeded Image Segmentation Framework Unifying Graph Cuts AndRandom Walker Which Yields A New Algorithm.

In Computer Vision, 2007. ICCV 2007. IEEE 11th InternationalConference on, pages 1–8. IEEE, 2007.


Documents

Segmentação de Imagens com Passeios Aleatórios …cef/mac499-12/monografias/...4 A segmenta˘c~ao esperada de uma imagem de ru do puro e igual a obtida em uma imagem uniforme. Je