segmentarea imaginilor tehnici de clusteringimag.pub.ro/ro/cursuri/archive/ai_curs4.pdf · e o...

1

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

SEGMENTAREA IMAGINILOR

TEHNICI DE CLUSTERING


C. VERTAN

Categorii de tehnici de segmentare pe regiuni

Thresholding (segmentare pe histograma)

Cresterea si fuziunea regiunilor

Segmentarea in spatiul caracteristicilor (generalizare thresholding)

pentru regiuni cu uniformitate a valorilor

pentru regiuni cu uniformitate a caracteristicilor (texturi)

2


C. VERTAN

Segmentarea in spatiul caracteristicilor (generalizare thresholding)

Spatiul caracteristicilor poate avea orice dimensionalitate.

Metode automate/ semi-automate.

Metodologia este analoga cuantizarii vectoriale folosite lacompresie.

Tipuri de metode de clustering

- iterative

- ierarhice


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

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

Segmentarea inseamna identificareagrupurilor de pixeli ce au caracteristiciasemanatoare.

Acest proces de grupare se numesteclustering.

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

compacte, densereprezentativebine separate ?

?

4


C. VERTAN

Spatiul caracteristicilor

original medie Reprezentarea spatiului2D al caracteristicilor


C. VERTAN


5


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 ==∀

6


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.


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

7


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.

8


C. VERTAN

Pasii 2 - 3 ai algoritmului (calcul apartenenta vector la o clasasi calculul prototipului unei clase poarta numele de iteratieLBG (Linde-Buzo-Gray).

Orice instanta LBG se caracterizeaza prin

initializare (aleatoare sau prin “spargere”)iteratie LBGevaluare conditie de oprire


C. VERTAN

segm.pe hist.

clustering ISODATA

original

9


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 ?

10

Fuzzy : de ce ?

« Computing with words » (Zadeh)

Numere Descrieri semantice ale obiectelorsi interactiunilor acestora.

Modele

Grade de apartenenta Multimi fuzzy Reguli(scalari) (functii) (sisteme bazate pe

inferenta)

Fuzzy ar permite adaptarea la o realitate graduala (nuantata).


C. VERTAN

Numerele corespund masurii in care un obiect din universulproblemei satisface o proprietate (sau o categorie) semantica;numerele sunt in [0,1].

« Inalt »1

01.81.50 inaltime (metri)

Multime fuzzy = functie de apartenenta a obiectelor la categoria data

Functia de apartenenta corespunde unui model natural (plauzibil)si nu este « machiavelica » (Bezdeck)

Fuzzy : cum ?


C. VERTAN

11

Un model «machiavelic» al categoriei «Inalt»:

1

01.80 inaltime2.1

Gradele de apartenenta nu sunt acelasi lucru cu probabilitatile !

Exemplul calatorului insetat (Bezdeck) :Calatorul insetat ce merge prin desert gaseste doua sticlepline cu lichid. Calatorul trebuie neaparat sa bea continutulunei sticle. Etichetele sticlelor nu sunt “clare”.

Fuzzy : cum ?


C. VERTAN

Probabilitatea unui continut «potabil » : 0.9

Gradul de apartenenta al continutului lacategoria «potabil» : 0.9

Gradul de apartenenenta nu se schimba dupa observatie !

Probabilitatea : o sansa din zece de a gasi in sticla acid.

Gradul de apartenenta : continutul este foarte potabil(ar putea fi bere).

Fuzzy ≠probabilitate


C. VERTAN

12

Probabilitatea unui continut «potabil » : 0.1

Gradul de apartenenta al continutului lacategoria «potabil» : 0.1

Gradul de apartenenenta nu se schimba dupa observatie !

Probabilitatea : noua sanse din zece de a gasi in sticla acid.

Gradul de apartenenta : continutul este foarte putin potabil(aproape sigur este acid).

Fuzzy ≠probabilitate


C. VERTAN


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)

13


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

λ

λλ

14


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 patratele distantelor 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)


2. calculeaza apartenenta fiecarui vector la clasele partitiei

3. calculeaza prototipurile claselor ca mediile ponderate ale vectorilor




C. VERTAN

15


C. VERTAN



C. VERTAN

FCM, 2 clase, grad de apartenenta la 2

binarizare dupa grad apartenentamaxima

16


C. VERTAN

FCM, 3 clase 1

23


C. VERTAN

segm. dupa gradmax. apartenenta

23

1

17


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

18


C. VERTAN

Clusteringfuzzy

“posibilist”Gradele de apartenenta ca tipicalitati :

- posibilitatea de inlocui prototipul clasei prinvectorul dat

- masura in care vectorul dat este un reprezentat tipic al clasei

Nu se mai utilizeaza conditia de normare probabilista a gradelor deapartenenta.

∑ ∑∑ ∑= == =

−−⎟⎟⎠

⎞⎜⎜⎝

⎛−=

C

1j

N

1i

mijj

C

1j

N

1i

2ji

mijPCM )1u(uJ ημx


C. VERTAN

∑

∑

∑

=

=

=

=

=−=∂

∂

N

1i

mij

N

1ii

mij

j

N

1iji

mij

j

PCM

u

u

0)(u2J

xμ

μxμ

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛ −+

=⇒=

=−+−=∂

∂ −−

j

2ji

ij

1mijj

2ji

1mij

ij

PCM

1

1u2m

0)1u(mmuu

J

η

η

μx

μx

prototipul oricarei clase este o medie ponderataa tuturor vectorilor din setul de date, ponderaticu gradele lor de apartenenta la clasa respectiva.(conditie de buna aproximare a claselor prin prototip)

Clusteringfuzzy

“posibilist”

19


C. VERTAN

Clusteringfuzzy

“posibilist”⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛ −+

=

j

2ji

ij

1

1u

ημx

jη caracteristica a fiecarei clase (“largimea clasei”)(echivalentul unei “benzi de trecere de 3dB” - distanta lacare gradul de apartenenta al unui vector este 0.5).

∑

∑

=

=−

= N

1i

mij

N

1i

2ji

mij

j

u

uK

μxη

e o “distanta medie” caracteristicaclasei

Clusteringfuzzy

posibilist

PCM (Possibilistic C-Means)


2. calculeaza parametrii claselor (“largimea”)





20


C. VERTAN

Reglarea automata a numarului de clase C

Alegerea initiala gresita a numarului de clase determina erorile desupra-segmentare sau sub-segmentare.

Supra-segmentarea se poate corecta prin reunirea ulterioara aobiectelor deja determinate si este deci preferabila alegerea unui Cmai mare decat necesar.

Varianta 1 : se realizeaza partitii cu numar variabil de clase si sepastreaza partitia “cea mai buna”

Varianta 2 : algoritmul de partitionare isi modifica numarul de clasede exemplu eliminand clasele mici situate aproapede clase mai importante.


C. VERTAN

Aglomerareacompetitiva

∑ ∑∑ ∑= == =

⎟⎟⎠

⎞⎜⎜⎝

⎛−⎟⎟

⎠

⎞⎜⎜⎝

⎛−=

C

1j

2N

1iij

C

1j

N

1i

2ji

2ij uuJ αμx

∑ ∑ ∑∑∑ ∑= = === =

⎟⎟⎠

⎞⎜⎜⎝

⎛−−⎟⎟

⎠

⎞⎜⎜⎝

⎛−⎟⎟

⎠

⎞⎜⎜⎝

⎛−=

C

1j

N

1i

C

1jiji

2N

1iij

C

1j

N

1i

2ji

2ijCA 1uuuJ λαμx

Competitive Agglomeration

eroare de reprezentare a claselorprin prototip (ca la FCM)

constrangerea probabilista a gradelor de apartenenta (ca la FCM)vectorii sunt partajati intre clase.

termen de cardinalitate a claseloroptim pentru numar mic de clase

21


C. VERTAN

Aglomerareacompetitiva

∑

∑

∑

=

=

=

=

=−=∂∂

N

1i

2ij

N

1ii

2ij

j

N

1iji

2ij

j

CA

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.(conditie de buna aproximare a claselor prin prototip)

⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜

⎝

⎛

−

−−

−+=

∑

∑

=

=

C

1j2

jt

C

1j2

jt

k

s2st

FCMst

CAst 1

N

Nuu

μx

μx

μxα

Ns - cardinalitatea clasei s


C. VERTAN

AglomerareacompetitivaAlegerea termenului de echilibru intre cerintele

contrare :

∑ ∑

∑∑

= =

= =

⎟⎟⎠

⎞⎜⎜⎝

⎛

−=

C

1j

2N

1iij

C

1j

N

1i

2ji

2ij

u

u μxα

Dupa fiecare etapa de recalculare a gradelor de apartenenta, severifica daca exista clase cu cardinalitate mica, candidate laeliminare.

22

Aglomerarecompetitiva1. alege un set aleator de prototipuri

2. calculeaza parametrul de echilibrare



5. evalueaza cardinaliatea claselor; reduce clasele nesemnificative




C. VERTAN

23


C. VERTAN


C. VERTAN

Observatie

Elementele partitiei determinate prin clustering, ca si in cazulsegmentarii pe histograma, (deci multimile de pixeli ce au aceeasieticheta) nu sunt multimi conexe (pot avea mai mult de o singuracomponenta).

Nu se poate face nici o distinctie intre componente conexe diferitedin aceeasi clasa (adica intre obiectele de acelasi fel din scena).

Individualizarea componentelor dintr-o aceeasi clasa se faceprin aplicarea unei poceduri de etichetare.

24


C. VERTAN

segmentarea imaginilor tehnici de clusteringimag.pub.ro/ro/cursuri/archive/ai_curs4.pdf · e o...

Documents