Solutie imediata : cresterea regiunilor

1

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

SEGMENTAREA IMAGINILOR


C. VERTAN

Segmentarea = descompunerea imaginii in partile sale componente.

(reducerea numarului de culori dintr-o imagine este un caz particular)

Segmentare :- orientata pe regiuni- orientata pe contururi

(abordari duale)Erori :

supra-segmentarea : descompunerea imaginii in mai multe elemente(parti) decat necesar

sub-segmentarea : descompunerea imaginii in mai putine elemente(parti) decat necesar


C. VERTAN

Segmentare pe regiuni:

cresterea (si fuziunea) regiunilor

segmentarea in spatiul caracteristicilor

segmentarea pe histograma

algoritimi generali de clustering


C. VERTAN

Solutie imediata : cresterea regiunilor

Determinarea unor zone in care se verifica uniformitatea valorilorunei caracteristici.

punct de plecare : germene

front decrestere oprit deneuniformitate

directie de inaintarefront de crestere


C. VERTAN

Cresterea regiunilor

Etape de rezolvat :

alegerea germenilor (punctelor de start)

alegerea criteriului de uniformitate a regiunii

Germenii :

se aleg in regiuni uniforme (sa fie plasati in centrul regiunilor)se repartizeaza uniform in suportul spatial al imaginiivaloarea pixelilor germene trebuie sa fie reprezentativa pentru

distributia valorilor pixelilor din imagineeste preferabila alegerea unui numar mare de germeni, chiar

cu riscul supra-segmentarii


C. VERTAN

germene regiune,Tunif=10

Exemplu

2


C. VERTAN

Verificarea germenilor redundanti(germenii ce conduc la suprasegmentare)

germeni redundanti : toate caile ce ii unesc suntuniforme

germeni ne-redundanti :nu exista nici o cale uniforma caresa ii uneasca (deci se trece pestefrontiera)

Numarul de cai testate (“toate”) este redus din considerente de calcul.


C. VERTAN

Verificarea germenilor redundanti(germenii ce conduc la suprasegmentare)

Desi germenii sunt plasati in aceeasicomponenta, nu sunt declaratiredundanti : caile verificate care iiunesc traverseaza frontierele-obiect.

Obiectul va fi impartit (artificial)in doua componente.

Supra-segmentarea poate fi partial corectata prin “fuziunea regiunilor”


C. VERTAN

Cresterea efectiva a regiunilor

In jurul germenului se agrega pixeli vecini structurii deja existente,daca valoarea acestor pixeli este suficient de apropiata de valoareagermenului.

Cresterea trebuie imaginata ca fiind simultana pentru toti germeniialesi in imagine.

Cresterea se opreste cand pixelii ramasi ne-alocati unei regiuninu mai satisfac criteriul de uniformitate;

relaxarea criteriului de uniformitateconstruirea unei clase a pixelilor “a-tipici”.


C. VERTAN

Corectia rezultatelor : fuziunea regiunilor

Se verifica daca regiunile vecine nu ar putea fi reunite.

Criteriile de similaritate se refera in general la frontiera :procentul de pixeli slabi

procentul de pixeli tari

altele …

Concluzie : Procesul este complicat si de durata, necesita reglareamultor parametri. Cresterea regiunilor ar fi buna pentru separareaunui numar mic de obiecte fixate, nu pentru segmentarea imaginiiintregi.


C. VERTAN

Cine [si cum] defineste numarul necesar, corect, de parti aleimaginii ?

3 tipuri de elemente :cer, vegetatie, casa

4 tipuri de elemente :cer, vegetatie, lemn, zid

supra-segmentare ?(copac impartit in doua clase)

sub-segmentare ?(soarele este in clasa “cer”)


C. VERTAN

R

G

B

Tipurile de obiecte pot fi separate in spatiul caracteristicilor, dacarespectivele caracteristici sunt discriminante (de ex. culoarea).

Valori tipice pentru caracteristicileobiectele : prototipurile claselor.

3


C. VERTAN

R

G

Segmentarea inseamna identificareagrupurilor de pixeli ce au caracteristiciasemanatoare.

Acest proces de grupare se numesteclustering (denumirea generala).

Algoritmii de clustering urmarescidentificarea automata a unor grupuride puncte din spatiul caracteristicilorce sunt :

compacte, densereprezentativebine separate ?

?


C. VERTAN

Cea mai simpla caracteristica: nivelul de gri

Presupunem ca nivelul de gri este reprezentativ si suficient pentrucaracterizarea tipurilor de obiecte din imagine.

Trebuie deci identificate “concentrarile” de nivele de gri,adica modurile din histograma imaginii. Fiecare mod bineidentificat va corspunde unui tip de obiecte din imagine.


C. VERTAN

Histograma

Histograma = functie ce asociaza fiecarui nivel de gri posibilprobabilitatea [sa] de aparitie in imagine.

h(u) = numar pixeli de nivel de gri “u” / numar total pixeli

( ) 1L,...,1,0u,u)n,m(fMN

1)u(h1M

0m

1N

0n−=−= ��

−

=

−

= δ

Histograma este o functie de densitate de probabilitate.

�−

==

1L

0u1)u(h

Histograma descrie continutul “de culoare/ de gri” al imaginii.


C. VERTAN

Histograma


C. VERTAN

Segmentarea pe histograma = Thresholding (praguire)

gasirea “pragurilor” de separare dintre modurile histogrameide nivele de gri a imaginii.

Fie Tk pragurile de segmentare pe histograma.

g(m,n) = Ek, daca Tk ≤ f(m,n) ≤ Tk+1

Ek este eticheta ce se atribuie tipului de obiecte k

T0 = 0, TC = L, k = 0, 1, ..., L-1

Caz particular : C = 2 (binarizarea)

��

>≤

=TnmfETnmfE

nmg),(,),(,

),(1

0


C. VERTAN

Evident, alegerea pragurilor de segmentare Tk este cruciala.

obiecte foarte luminoaseobiectegri mediu

obiecteintunecate

T1 T2

Pragurile se aleg pe minimele histogramei (separatia dintre moduri).

4


C. VERTAN

Exemplu

C=2T=170


C. VERTAN

C=3T1=40T2=100

C=4T1=40T2=100T3=

Exemplu


C. VERTAN

Daca minimele histogramei nu sunt usor de identificat ?

Segmentare pe histograma ponderata

uunmfnmwMN

uhM

m

N

n∀−= ��

= =,)),((),(1)('

1 1δ

w(m,n) masura locala, caracteristica pixelului

)j,i(∆ Laplacianul imaginii

),(11),(

nmnmw

∆+=

),(),( nmnmw ∆=

adancirea minimelor din histograma

separatiile dintre moduri devin maxime


C. VERTAN

Exemplu

histograma

histogramaponderata,minime adancite


C. VERTAN

Segmentarea cu prag optim

Sa presupunem cunoscute: numarul de tipuri de obiecte dinimagine, proportiile in care acestea ocupa suprafata imaginiisi distributia nivelelor de gri caracteristice fiecarui tip de obiect.

�

�

=

=

=

=

C

ii

C

iii

P

xpPxh

1

1

1

)()( Pentru binarizare C=2 :

1)()()(

21

2211

=++=

PPxpPxpPxh

Pentru binarizare va trebui determinat pragul T ce separa modurile.

Pragul este “optim” in sensul minimizarii unei erori.


C. VERTAN

Eroarea de segmentare este data de pixelii prost etichetati:nivel de gri mai mic ca T, desi provin din p2nivel de gri mai mare ca T, desi provin din p1

��+∞

∞−

+=T

T

dxxpPdxxpPT )()()( 1122ε

5


C. VERTAN

Optim : 0)( =

dTTdε

��+∞

∞−

+=T

T

dxxpPdxxpPT )()()( 1122ε)()( 2211 TpPTpP =

In cazul particular cel mai curent, distributiile ce caracterizeazaobiectele sunt normale (gaussiene).

Daca variantele lor sunt egale, pragul este:

2

1

21

221 ln

2 PPT

µµσµµ−

−+=


C. VERTAN

Dar daca nivelul de gri nu este suficient ?(si la histograma ponderata se foloseau caracteristici suplimentare)

Dar daca imaginile nu sunt scalare ?(imaginile color au 3 numere/ pixel) ....

Segmentarea generala in spatiul caracteristicilor prin clustering.


C. VERTAN

R

G

Segmentarea inseamna identificareagrupurilor de pixeli ce au caracteristiciasemanatoare.

Acest proces de grupare se numesteclustering (denumirea generala).

Algoritmii de clustering urmarescidentificarea automata a unor grupuride puncte din spatiul caracteristicilorce sunt :

compacte, densereprezentativebine separate ?

?


C. VERTAN

ClusteringPunerea problemei :

un set de N puncte, descrise de vectori de dimensiune ptrebuie impartit in C clase (grupuri, clustere).

)x,...,x,x(N,...,2,1i},{X

ip2i1ii

i

===

xx

Impartirea (partitionarea) setului de puncte in clase :indice de apartenenta a fiecarui punct (carei clase ii apartine)

Exprimarea cantitativa a conceptului de “partitionare buna”.criterii de calitate a partitiei.


C. VERTAN

ClusteringApartenenta punctelor la clase

C,...,2,1j,N,...,2,1i,uij ==

Apartenenta punctului xi la clasa j :

Modele de clustering :

Net (binar) :

��

∉∈

=ji

jiij Clasa,0

Clasa,1u

xx

Nuantat (fuzzy) :

]1,0[uij ∈C,...,2,1j,N,...,2,1i ==∀


C. VERTAN

ClusteringMasuri de calitate a claselor

clase compacte : centrul clasei este “aproape” de toate puncteleclasei (punctele clasei sunt bine aproximate decentrul clasei).

clasa are suficient de multe puncte

clase bine separate : distantele dintre centrele claselor sa fie catmai mari.

Cele doua cerinte sunt adeseori contradictorii.

6


C. VERTAN

Clusteringnet

Basic ISODATA (k-means, C-means)

ISODATA = Iterative Self Organizing Data Analysis Technique

Se fixeaza numarul de clase dorit, C.

Calitatea partitiei (a claselor) e caracterizata de eroarea globala deaproximare a vectorilor de date prin prototipurile claselor.

� ��= ==

��

��

�−===

C

1j

N

1i

2jiij

C

1jjjij u),u(JJ µxµ ε

jµ prototipul (centroidul) clasei j


C. VERTAN

Clusteringnet

Basic ISODATA (C-means)

�

�

�

=

=

=

=

=−=∂∂

N

1iij

N

1iiij

j

N

1ijiij

j

u

u

0)(u2J

xµ

µxµ

prototipurile claselor sunt mediile aritmeticeale vectorilor de date ce apartin claselor.

��

�� ≠∀−≤−=

rest ,0jk,,1u kiji

ijµxµx orice vector apartine

clasei de al careiprototip este cel maiapropiat.

Clusteringnet

Basic ISODATA (C-means)

1. alege un set aleator de prototipuri

2. calculeaza apartenenta fiecarui vector la una dintre claselepartitiei (vectorii apartin clasei de al carei prototip suntcei mai apropiati)

3. calculeaza prototipurile claselor ca media aritmetica a vectorilorapartind fiecarei clase

4. evalueaza criteriu de oprire :eroare globala suficient de mica ?numar de iteratii suficient de mare ?au fost vectori care sa isi schimbe apartenenta ?au fost prototipuri care s-au modificat semnificativ ?

5. repeta de la 2 daca e cazul.


C. VERTAN

ClusteringnetProblema :

“oscilatii” ale vectorilor intre clase

alocarea vectorilor situati la egala distanta fata de clase

Clasa 1 Clasa 2

prototip 1

prototip 2

x

?


C. VERTAN

Clusteringfuzzy

Orice vector apartine oricarei clase, dar intr-o masura maimare sau mai mica.

uij sunt gradele de apartenenta [fuzzy] ale vectorilor la clase.

Probleme

de ce fuzzy ?

ce semnificatie au gradele de apartenenta ?

cum se modifica criteriile obiective de calitate ?


C. VERTAN

ClusteringfuzzyModuri de interpretare a gradelor de apartenenta

Clustering “probabilist” - gradele de apartenenta reprezinta masurain care vectorii sunt “impartiti” claselor

�=

=C

1jij 1u (constrangerea de normare probabilista)

Clustering “posibilist” - gradele de apartenenta reprezinta masurain care vectorii sunt “tipici” pentru clase

(faa constrangeri de normare)

7


C. VERTAN

Clusteringfuzzy

“probabilist”FCM - Fuzzy C-Means (Fuzzy Isodata)

Se fixeaza numarul de clase dorit, C.

Calitatea partitiei (a claselor) e caracterizata de eroarea globala deaproximare a vectorilor de date prin prototipurile claselor.

� ��= ==

��

��

�−===

C

1j

N

1i

2ji

mij

C

1jjjij u),u(JJ µxµ ε

jµ prototipul (centroidul) clasei jm gradul de fuzificare al partitiei

� �� = == =

��

�

�

��

�

�−−��

�

��

�−=

N

1i

C

1jiji

C

1j

N

1i

2ji

mijFCM 1uuJ λµx


C. VERTAN

�

�

�

=

=

=

=

=−=∂

∂

N

1i

mij

N

1ii

mij

j

N

1iji

mij

j

FCM

u

u

0)(u2J

xµ

µxµ

prototipul oricarei clase este o medie ponderataa tuturor vectorilor din setul de date, ponderaticu gradele lor de apartenenta la clasa respectiva.

Clusteringfuzzy

“probabilist”

1m

C

1k

1m2

ki

i

C

1kik

1m1

2ji

iiji

2ji

1mij

ij

FCM

m1u

mu0mu

uJ

−

=

−−=

−−

��

�

�

��

�

�

−=�=

��

�

�

��

�

�

−=�=−−=

∂∂

��

µx

µxµx

λ

λλ


C. VERTAN

Clusteringfuzzy

“probabilist”

�

�

= −

−

=

−−

−−

=

−

−=

C

1kki

1m2

ji1m

2

ij

C

1k

1m2

ki

1m2

jiij

),(dist

1),(dist

1

u

u

µx

µx

µx

µx

gradele de apartenenta depindinvers proportional de patrateledistantelor de la vectorul de datela prototipurile claselor

rezolva problema gradelor de apartenenta egale in cazul vectoriloregal distantati de prototipuri ale claselor.

Clusteringfuzzy

probabilist

FCM (Fuzzy Isodata)

1. alege un set aleator de prototipuri

2. calculeaza apartenenta fiecarui vector la clasele partitiei

3. calculeaza prototipurile claselor ca mediile ponderate ale vectorilor

4. evalueaza criteriu de oprire :eroare globala suficient de mica ?numar de iteratii suficient de mare ?au fost vectori care sa isi schimbe apartenenta ?au fost prototipuri care s-au modificat semnificativ ?

5. repeta de la 2 daca e cazul.


C. VERTAN


C. VERTAN

FCM, C=3

FCM, C=4segmentare ideala (C=3)

Clusteringfuzzy

“probabilist”

Exemplu


C. VERTAN

Clusteringfuzzy

“probabilist”Limitarile modelului de “impartire” a vectoruluiintre clase.

A

B

C

clasa 1 clasa 2

prototip 1 prototip 2

8


C. VERTAN

Solutie imediata : cresterea regiunilor

Documents

Transcript of Solutie imediata : cresterea regiunilor