Camminata Aleatoria

Grafi Camminata aleatoria e funzioni armoniche Problema di Dirichlet e struttura dellalgoritmo Esempi

Camminata aleatoria per la segmentazione diimmagini

Relazione di statistica e probabilita`

Sebastiano Roncoroni

Universita` degli Studi dellInsubria

9 dicembre 2013

Sebastiano Roncoroni Camminata aleatoria per la segmentazione di immagini


Introduzione

Il problema della segmentazione consiste nel localizzare le aree diunimmagine che sono legate tra loro per affinita` di contenuto (adesempio, intensita` o colore).

Immagine originale (a sinistra) e immagine segmentata (a destra). Lasegmentazione e` utilizzata in diagnostica medica per isolare edevidenziare parti di unimmagine.



Introduzione

Presentiamo un algoritmo (procedimento che risolve un problema inun numero finito di passaggi) per la segmentazione utilizzando comeoggetto matematico di riferimento la camminata aleatoria definita suun grafo. Il grafo e` indotto dallimmagine facendo corrispondere adogni pixel un vertice ed associando agli archi un valore numericolegato al gradiente della caratteristica considerata (p.e. intensita`).

immagine grafo

vertici

archi



Introduzione

Come funziona lalgoritmo?1 Lutilizzatore sceglie un numero piccolo di pixel ( vertici) ai quali

pre-assegna unetichetta. Chiamiamo questi vertici i verticipre-etichettati. Due vertici pre-etichettati possono avere la stessaetichetta.

2 Sia K il numero totale di etichette distinte utilizzate. Sia s lindiceche contraddistingue letichetta assegnata ad un vertice, quindi sassume valori s = 1, ...,K .

3 Lalgoritmo calcola la probabilita` che una camminata aleatoria cheparta da ogni vertice non pre-etichettato (e che muove lungo gliarchi) raggiunga per primo, tra tutti i vertici pre-etichettati, unvertice con etichetta s = 1.

4 Ripetiamo il calcolo del punto 3 per tutti i valori di s.5 La segmentazione e` ottenuta assegnando ad ogni pixel letichetta per

la quale la probabilita` calcolata e` massima.



Esempio

0.71

0.41

0

0.08

0.53

0.24

0.15

0.67

0.47

0.27

0.14

0.54

0.41

0.23

0

I tre pixel pre-etichettati dallutilizzatore (a sinistra), e la probabilita` cheuna camminata aleatoria che parta da ogni pixel non etichettatoraggiunga per primo il pixel etichettato in blu (a destra).



Esempio

0.27

0.53

0.76

0

0.33

0.54

0.53

0.13

0.24

0.30

0.28

0.16

0.19

0.16

0

0.03

0.06

0

0.16

0

0.14

0.22

0.32

0.20

0.29

0.43

0.58

0.30

0.40

0.61

Probabilita` che una camminata aleatoria che parta da ogni pixel nonetichettato raggiunga per primo il pixel etichettato in verde (a sinistra) equello etichettato in rosso (a destra).



Esempio

La segmentazione finale si ottiene assegnando ad ogni pixel letichettaper la quale la probabilita` calcolata e` massima.



Schema della presentazione

Lo schema della presentazione e` il seguente:

introduzione ai grafi

camminata aleatoria e funzioni armoniche

problema di Dirichlet e struttura dellalgoritmo

proprieta` dellalgoritmo

esempi di applicazione



Definizione di grafo

Definizione

Un grafo G e` un insieme finito e non vuoto V assieme ad una relazionesimmetrica e irriflessiva R. V e` linsieme dei vertici ed ogni elemento di Vviene detto un vertice. Chiamiamo E linsieme delle coppie simmetrichein R; E e` linsieme degli archi ed ogni elemento in E e` un arco.

Notiamo che linsieme degli archi E determina completamente larelazione R, usualmente quindi un grafo G e` definito in termini degliinsiemi V ed E. La cardinalita` |V | dellinsieme dei vertici si dice ordine delgrafo mentre |E | e` la taglia del grafo.



Esempio

V = {v1, v2, v3, v4}E = {v1v2, v1v3, v2v3, v3v4}|V | = n = 4|E | = m = 4

G :

v1 v2

v3

v4

Sia v un vertice di G: il numero di archi di G incidenti su v e` chiamato ilgrado di v e si indica d(v). Per esempio, per il grafo riportato in figura siha d(v3) = 3. In un grafo pesato ad ogni arco eij corrisponde un valorenumerico w(eij) detto peso dellarco. In questo caso il grado di un verticesi definisce secondo la formula:

d(vi ) =eij

w(eij)

dove la somma e` estesa a tutti gli archi eij incidenti sul vertice vi . .



Grafi connessi

Un cammino v1 v2 in un grafo G e` una sequenza alternata di vertici edarchi che comincia in v1 e termina in v2, in modo che ogni arcocongiunga i due vertici immediatamente precedenti e successivi. Lasequenza e` dunque determinata univocamente elencando i soli vertici. Unsentiero in G e` un cammino in G che non ripete alcun vertice.

{v1, v3, v4, v3, v2} e` un cammino in G{v1, v3, v2} e` un sentiero in G G :

v1 v2

v3

v4

Definizione

Due vertici v1 e v2 in un grafo G si dicono connessi se esiste un sentierov1 v2 in G. Un grafo G si dice connesso se ogni sua coppia di vertici e`una coppia di vertici connessi.



Camminata aleatoria

Definizione

Una camminata aleatoria in Zd e` una sequenza di variabili aleatorie Snche comincia con probabilita` 1 da S0 = x Zd e in cui n N Sn e`definita:

Sn = x + X1 + ...+ Xn

dove le Xj sono variabili aleatorie indipendenti e identicamente distribuitet.c. per ogni indice di tempo j e per ogni indice di dimensionalita` k:

P{Xj = ek} = P{Xj = ek} = 12d

con ek il k-esimo vettore della base canonica di Zd .



Camminata aleatoria

Consideriamo ad esempio il caso d = 2: la camminata aleatoria e` quindidefinita in Z2

x

y

Si ha per le variabili aleatorie Xj :

P{Xj = (1, 0)} = P{Xj = (1, 0)} = 14

P{Xj = (0, 1)} = P{Xj = (0,1)} = 14

Ad ogni step quindi la camminata procede con uguale probabilita` su, giu`,a destra o a sinistra. La camminata aleatoria dellesempio e` definita dallasomma:

S22 = (1,2) + (0, 1) + (1, 0) + (0,1) + ...Sebastiano Roncoroni Camminata aleatoria per la segmentazione di immagini


Proprieta`

Enunciamo di seguito senza dimostrazione alcune proprieta` dellecamminate aleatorie in Zd :

Proprieta`

Omegeneita` temporale: sia Sn una camminata aleatoria in Zd :n,m, k N

P{Sn+k = y |Sn = x} = P{Sm+k = y |Sm = x}

Proprieta`

Simmetria: sia Sn una camminata aleatoria in Zd : n, k N

P{Sn+k = y |Sn = x} = P{Sn+k = x |Sm = y}

Una classe speciale di funzioni che andiamo di seguito a introdurre sonole funzioni armoniche. Le proprieta` sopra riportate permettono diutilizzare una camminata aleatoria in Zd per costruire funzioni armoniche.



Proprieta`

Sn+k = y

Sn = x

Sm+k = y

Sm = x

Proprieta` di omogeneita` temporale: la probabilita` di trovarsi nellaposizione y dopo n + k passi data la posizione x dopo n passi e`indipendente da n, cioe` e` indipendente da tutto il percorso precedente.



Proprieta`

y

x

Proprieta` di simmetria: la probabilita` di trovarsi nella posizione y dopon + k passi data la posizione x dopo n passi e` uguale alla probabilita` ditrovarsi nella posizione x dopo n + k passi data la posizione y dopo npassi. La camminata aleatoria muove con uguale probabilita` avanti eindietro.



definizione di bordo in Zd

Definizione

Sia A un sottoinsieme limitato di Zd . Il bordo di A e` linsieme:

A = {z Zd : z / A,x A : |z x | = 1}

La chiusura di A e` linsieme:

A = A A

Esempio di bordo di un insieme in Z2:



Proprieta` del valor medio

La definizione seguente e` utile per introdurre il Laplaciano in uno spaziodiscreto:

Definizione

Sia A un sottoinsieme di Zd . Una funzione F : A R ha la proprieta` delvalor medio se x A:

F (x) =y

1

2dF (y)

dove le somme sono estese a tutti i punti y Zd : |x y | = 1.



Proprieta` del valor medio

Questo significa che il valore che la funzione assume in un punto del suodominio e` uguale alla media dei valori che assume nei puntiimmediatamente circostanti. Per esempio per una funzione F definita inZ2:

x

y

1 2 30

1

2

3

Il valore che F assume nel punto (2, 1) e` dato da:

F (2, 1) =1

4[F (1, 1) + F (3, 1) + F (2, 0) + F (2, 2)]



Funzioni di piu` variabili

Il concetto di derivata (ordinaria) per una funzione di una variabile f (x) e`generalizzato dalle derivate parziali per una funzione di piu` variabilif (x1, x2, ..., xn). Ad esempio sia f (x) = x

2 una funzione di una variabile:

df

dx= 2x

Sia invece g(x , y) = x2 + y 2 + xy una funzione di due variabili. Laderivata parziale rispetto a x si calcola considerando y come unacostante e derivando nel modo ordinario rispetto a x :

g

x= 2x + y

Analogamente la derivata parziale rispetto a y si calcola considerando xcome una costante e derivando nel modo ordinario rispetto a y :

g

y= 2y + x



Operatori

Il gradiente di una funzione e` un operatore che associa ad una funzione dipiu` variabili il vettore delle sue derivate parziali, e si indica con il simbolo. Ad esempio per una funzione f (x , y) di due variabili:

f (x , y) =(f

x,f

y

)Il concetto di derivata seconda per funzioni di una variabile si estendeimmediatamente alle derivate parziali: il Laplaciano di una funzione e` unoperatore che associa ad una funzione di piu` variabili uno scalare datodalla somma delle derivate parziali seconde. Il Laplaciano si indica con ilsimbolo . Ad esempio:

f (x , y) =2f

x2+2f

y 2



Laplaciano in uno spazio discreto

In uno spazio continuo una funzione f si dice armonica se:

dk=1

2f

x2k= f = 0

Con loperatore Laplaciano. Lanalogo in Z si ottiene tramite leapprossimazioni:

F

x(c) F (c + 1) F (c)

2F

x2(c) F (c + 1) 2F (c) + F (c 1)

Definiamo quindi il Laplaciano discreto in Zd :

LF (x) =y

1

2d[F (y) F (x)]

dove le somme sono estese a tutti i punti y Zd : |x y | = 1.Sebastiano Roncoroni Camminata aleatoria per la segmentazione di immagini


Laplaciano in uno spazio discreto

Nel caso d = 1 le definizioni di Laplaciano discreto e derivata secondadiscreta, a meno del termine costante 12d =

12 , coincidono:

2F

x2(c) F (c + 1) 2F (c) + F (c 1)

LF (c) =

y :|cy |=1

1

2d[F (y) F (c)] = 1

2[F (c 1) 2F (c) + F (c + 1)]

c c + 1c 1 x

Ricordiamo la condizione che una funzione deve soddisfare per possederela proprieta` del valor medio:

F (x) =y

1

2dF (y)

La somiglianza formale con il Laplaciano discreto e` alla base dello strettolegame tra funzioni armoniche e funzioni con la proprieta` del valor medio.



Definizione di funzione armonica in Zd

Definizione

Sia A un sottoinseme limitato di Zd . Una funzione F : A R si dicearmonica se x A vale

LF (x) = 0

Le funzioni armoniche cos` definite godono di numerose proprieta`: inprimo luogo si puo` mostrare che una funzione e` armonica se e solo sepossiede la proprieta` del valor medio. Unaltra proprieta` importante checostituisce il punto di partenza per formulare il problema di Dirichlet e`che i valori che una funzione armonica F assume nellinterno del suodominio (cioe` in A) sono univocamente determinati dai valori che assumesul bordo A, nel senso che se esiste una seconda funzione armonica Gcon lo stesso dominio di F t.c. F = G su A allora vale F = G sullinterodominio A.



Problema di Dirichlet

In base alle precedenti affermazioni e` dunque ben posto il seguenteproblema di Dirichlet:

Definizione

Dato A Zd e data F : A R, il problema di Dirichlet consiste neltrovare unestensione F di F in A t.c. F sia armonica sullintero dominio.

data F definita sul bordo A

trovo F armonica definita sullintero dominio A



Uscita dal dominio

Come anticipato, la camminata aleatoria permette di costruire unasoluzione al problema di Dirichlet: in particolare il problema di Dirichlet e`analogo al problema di uscita dal dominio di una camminata aleatoria:

Definizione

Sia Sn una camminata aleatoria in A Zd . Il tempo di uscita T e`definito:

T = min {k N : Sk A}

Se A e` un sottoinsieme limitato di Zd allora il tempo di uscita T e` finitocon probabilita` 1.



Uscita dal dominio

Esempio di uscita dal dominio per una camminata aleatoria definita inZ2: i cerchi in nero sono i punti di A, i cerchi in bianco al loro interno ipunti di A.

x

yT = 12

T = 2

Il tempo di uscita T rappresenta il numero minimo di passi necessariperche` la camminata aleatoria si trovi su un punto del bordo A.



Il teorema seguente riassume la connessione esistente tra camminataaleatoria e problema di Dirichlet:

Teorema

Sia A un sottoinsieme limitato di Zd . Data F : A R, ! F : A Rarmonica, e tale funzione e` data da:

F (x) = E(F (ST xA )) =zA

F (z)P{ST xA = z}

dove T xA denota il tempo di uscita dal dominio A di una camminataaleatoria che comincia in x.

Quindi, il valore che la funzione F assume in un punto x A e` dato dallesomme su tutti i punti z appartenenti al bordo A del valore che Fassume in z (infatti F e` definita solo su A) per la probabilita` che unacamminata aleatoria che cominci da x esca dal dominio proprio dal puntoz (cioe` la probabilita` che z sia il primo punto del bordo su cui si viene atrovare la camminata aleatoria).



Principio di Dirichlet

Una semplificazione ulteriore del problema e` fornita dal principio diDirichlet, che enunciamo per una funzione u definita in uno spaziocontinuo:

Teorema

Sia u : Rn R soluzione del problema di Dirichlet con condizioni albordo u(x) = g(x) su , allora u si ottiene minimizzando il seguenteintegrale di Dirichlet:

D[u] =

|u|2d

dove indica loperatore gradiente.



Induzione di un grafo dallimmagine

Siamo ora in grado di presentare lalgoritmo di segmentazione con ilformalismo piu` adeguato: lobiettivo finale e` quello di calcolare laprobabilita` che una camminata aleatoria che parte da ogni pixel nonetichettato raggiunga per primo uno dei pixel pre-etichettatidallutilizzatore.In primo luogo, limmagine da analizzare verra` considerata nel seguitocome un grafo connesso e pesato: il grafo e` indotto dallimmaginefacendo corrispondere ad ogni pixel un vertice e assegnando i pesi degliarchi w(eij) wij attraverso la formula:

wij = exp ((gi gj)2)

dove gi e` lintensita` dellimmagine al pixel i-esimo e e` un parametrolibero dellalgoritmo. Dalla formula leggiamo inoltre wij = wji cioe` ilgrafo e` anche non-direzionato.



Funzionamento dellalgoritmo

In virtu` del principio di Dirichlet, il nostro obiettivo e` adesso quello diriscrivere lintegrale di Dirichlet per funzioni definite sul grafo ( in Z2) etrovare la funzione x(vi ) xi che ne minimizza il valore. Imponendo leopportune condizioni al bordo, xi rappresenta la probabilita` desiderataper la camminata aleatoria che parta dalli-esimo vertice non etichettato.

Consideriamo inizialmente il caso molto semplificato di un grafo di ordinee taglia uguali a 4:

V = {v1, v2, v3, v4}E = {e12, e13, e24, e34} G :

v1 v2

v3 v4



Matrice di incidenza e matrice costitutiva

Introduciamo la matrice di incidenza A che rappresenta loperatoregradiente (mentre AT rappresenta loperatore divergenza):

Aeijvk =

+1 i = k

1 j = k0 altrimenti

A e` una matrice m n indicizzata dallarco eij e dal vertice vk .Denominiamo inoltre matrice costitutiva C la matrice diagonale m m icui elementi lungo la diagonale sono i pesi wij di ogni arco.Per il nostro esempio si ha dunque:

A =

1 1 0 01 0 1 00 1 0 10 0 1 1

C =

w12 0 0 00 w13 0 00 0 w24 00 0 0 w34



Laplaciano e operatore di Laplace-Beltrami

Come nel caso continuo, loperatore Laplaciano L nel caso discreto siottiene dalla composizione degli operatori divergenza e gradiente, dunque:

L = ATA

Questa definizione tuttavia non contiene alcuna informazione circa i pesiassociati agli archi: il Laplaciano deve essere generalizzato dalloperatoredi Laplace-Beltrami:

L = ATCA

Quindi:

L = ATCA =

w12 + w13 w12 w13 0w12 w12 + w24 0 w24w13 0 w13 + w34 w34

0 w24 w34 w34 + w24



integrale di Dirichlet

Lintegrale di Dirichlet si scrive quindi:

D[x ] =1

2(Ax)TC (Ax) =

1

2xTLx =

1

2

eijE

wij(xi xj)2

Dividiamo ora linsieme V dei vertici in due insiemi disgiunti VM (verticipre-etichettati) e VU (vertici non etichettati) t.c. V = VM VU .Assumiamo senza perdita di generalita` che in L e in x i vertici sianoordinati in modo che i vertici etichettati vengano prima di quelli nonetichettati. Nel nostro esempio supponiamo:

VM = {v1, v2}VU = {v3, v4} G :

v1 v2

v3 v4Sebastiano Roncoroni Camminata aleatoria per la segmentazione di immagini


Quindi loperatore Laplaciano diventa:

L =

w12 + w13 w12 w13 0w12 w12 + w24 0 w24w13 0 w13 + w34 w34

0 w24 w34 w34 + w24

E possiamo riscrivere lintegrale di Dirichlet:

D[xU ] =1

2

[xTM x

TU

] [LM BBT LU

] [xMxU

]cioe`, svolgendo i conti:

D[xU ] =1

2(xTMLMxM + 2x

TU B

T xM + xTU LUxU)

LM B

BT LU



Ponendo la derivata di D[xU ] rispetto a xU uguale a zero otteniamo unsistema di equazioni lineari in |VU | incognite la cui soluzione costituisce ilminimo dellintegrale di Dirichlet:

LUxU = BT xMCioe`, grazie al teorema di Dirichlet il problema (complicato) di calcolarela probabilita` che una camminata aleatoria che parta da un punto di VUraggiunga per primo uno dei punti di VM con una data etichetta si e`ridotto alla soluzione di equazioni di primo grado!Nel nostro esempio otteniamo un sistema di due equazioni nelle dueincognite x3 e x4:{

(w13 + w34)x3 w34x4 = w13x1w34x3 + (w34 + w24)x4 = w24x2



Condizioni al bordo

A questo punto non resta che imporre le opportune condizioni al bordo:

Notiamo che mentre nellenunciato generale del problema di Dirichletimporre le condizioni al bordo significa fissare i valori che la funzioneassume su A, nel nostro caso specifico cio` equivale a fissare i valori (0oppure 1) della probabilita` su tutti i vertici pre-etichettati.

Sia s lindice che contraddistingue una delle K etichette considerate,s = 1, 2, ...,K .

Chiamiamo x si la probabilita` che una camminata aleatoria che partadal vertice non pre-etichettato vi raggiunga per primo un verticemarcato con letichetta s.

Sia Q(vj) la funzione definita sullinsieme VM il cui valore e` lindices associato alletichetta del vertice vj .

La probabilita` cercata si ottiene imponendo le condizioni al bordo:

x sMj =

{+1 se Q(vj) = s

0 se Q(vj) 6= sSebastiano Roncoroni Camminata aleatoria per la segmentazione di immagini


Esempio

Il teroema di Dirichlet richiede di fissare le condizioni al bordo: Nel casogenerale devo imporre i valori che F assume sui punti del bordo A. Nelcaso particolare dellalgoritmo devo specificare i valori della probabilita` sututti i vertici in VM (vertici pre-etichettati).

0.27

0.53

0.76

0

0.33

0.54

0.53

0.13

0.24

0.30

0.28

0.16

0.19

0.16

0

1



Segmentazione

La segmentazione finale e` ottenuta risolvendo per ognuna delle Ketichette (cioe` per ognuna delle K diverse condizioni al bordo) il sistema:

LUxs = BT x sM

ed assegnando ad ogni vertice in VU letichetta s t.c.:

x si = max{x si }Ks=1



Un esempio piu` complicato

Alcune proprieta` dellalgoritmo non possono essere visualizzateconsiderando un grafo di soli 4 vertici: un grafo realmente indotto daunimmagine come quella utilizzata nellintroduzione di questapresentazione conta 104 vertici. Consideriamo quindi il grafo seguente,piu` complicato:

V = {v1, v2, ..., v6}E = {v1v2, v1v5, ..., v15v16}|V | = 16|E | = 24



La matrice dincidenza A e` una matrice 24 16. La prima riga di A, adesempio, e` data da:

(A)1 =[

1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 ]Loperatore Laplaciano e` rappresentato da una matrice quadrata 24 24.La prima riga di L e`, ad esempio:

(L)1 =[w12 + w15 w12 0 0 w15 0 0 0 0 0 0 0...

...0 0 0 0 0 0 0 0 0 0 0 0]

Due osservazioni:

La matrice A, in generale, non e` una matrice quadrata.

Gli elementi di L diversi da zero sono in numero molto minore deglielementi di L uguali a zero: si dice che L e` una matrice sparsa. Cio`comporta una notevole semplificazione computazionale.



Proprieta` qualitative dellalgoritmo

Le seguenti proprieta` sono motivate sia da argomenti teorici che daapplicazioni pratiche; viene mostrata la stabilita` dellalgoritmo nellecondizioni di:

Confini deboli: quando sono parte di confini piu` marcati lalgoritmoindividua confini deboli di oggetti distinti; altri algoritmi (p.e.graph cuts) non offrono lo stesso risultato.

Rumore sperimentale: lalgoritmo restituisce una segmentazioneaffidabile anche in presenza di rumore sperimentale.

Regioni ambigue: una regione non etichettata e localmente costanteche deve essere assegnata a regioni con etichette diverse vieneattribuita.

1 Alla regione con cui condivide la maggiore superficie.2 In caso di pareggio al punto 1) alla regione con intensita` piu` simile

alla propria.3 Divisa in due sotto-regioni in caso di pareggio ai punti precedenti.



Esempi di applicazione

Una prima applicazione dellalgoritmo di segmentazione ad unimmaginein scala di grigio:

Immagine originale con in evidenza i quattro pixel pre-etichettati (asinistra) e probabilita` che una camminata aleatoria che parta da ognipixel non marcato raggiunga per primo il pixel etichettato in rosso (adestra). Bianco= probabilita` massima, nero= probabilita` minima.




Attribuzione ad ogni pixel non marcato delletichetta che massimizza laprobabilita` (a sinistra) e segmentazione finale dellimmagine (a destra).




Applicazione dellalgoritmo ad unimmagine neutra con 100 puntipre-etichettati generati in modo random: la segmentazione prodotta e`equivalente ad una tassellatura di Voronoi del piano.

Attribuzione ad ogni pixel non marcato delletichetta che massimizza laprobabilita` (a sinistra) e segmentazione finale dellimmagine (a destra).



Conclusioni

Concludiamo riassumendo le principali caratteristiche discusse:

Lalgoritmo presentato utilizza la camminata aleatoria definita su ungrafo per produrre la segmentazione dellimmagine.

Grazie alle proprieta` delle funzioni armoniche ed al teorema diDirichlet il problema si riduce computazionalmente alla soluzione diun sistema di equazioni lineari.

La segmentazione ottenuta e` stabile anche in condizioni critiche(rumore, confini deboli, regioni ambigue).

lutilizzazione dellalgoritmo e` intuitiva e richiede un numero piccolodi input esterni (segmentazione soddisfacente anche con soli trepixel pre-etichettati).


GrafiCamminata aleatoria e funzioni armonicheProblema di Dirichlet e struttura dell'algoritmoEsempi

Camminata Aleatoria

Documents

Transcript of Camminata Aleatoria