segmentarea imaginilor color [ si multi ...alpha.imag.pub.ro/site_old/release/archive/21.pdfgermenii...

1

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

SEGMENTAREA IMAGINILOR COLOR

[ SI MULTI-COMPONENTA]


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

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 aleg 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

Verificarea germenilor redundanti(germenii ce conduc la suprasegmentare)

germeni redundanti : toate caile ce ii unesc suntuniforme

germeni ne-redundanti :exista o cale ne-uniforma careii uneste (deci se trece peste ofrontiera)

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”

2


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.


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 ?

?


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.

3


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.


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. LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

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

?

4


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 ?

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

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

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

5


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)


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

ji1m2

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


5. repeta de la 2 daca e cazul.


C. VERTANLABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

FCM, C=3

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

Clusteringfuzzy

“probabilist”

Exemplu

6


C. VERTAN

Clusteringfuzzy

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

A

B

C

clasa 1 clasa 2

prototip 1 prototip 2


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(mmuuJ

η

η

µ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”


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”)




6. repeta de la 2 daca e cazul.LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

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.

7


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


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.

Aglomerarecompetitiva1. alege un set aleator de prototipuri

2. calculeaza parametrul de echilibrare



5. evalueaza cardinaliatea claselor; reduce clasele nesemnificative


7. repeta de la 2 daca e cazul.


C. VERTANLABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

8


C. VERTAN

Dezvoltari :

- noi criterii de descriere a corectitudinii partitiei (inglobandposibilitatea controlarii numarului de clase)

→ algoritmi mai complecsi (JSEG)

- simplificarea algoritmilor prin controlul precis alnumarului de iteratii (convergentei) si numarului de clase

→ algoritmi ierarhici


C. VERTAN

segmentarea imaginilor color [ si multi ...alpha.imag.pub.ro/site_old/release/archive/21.pdfgermenii...

Documents