1
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
SEGMENTAREA IMAGINILOR COLOR
[ SI MULTI-COMPONENTA]
LABORATORUL DE ANALIZA ŞI PRELUCRAREA 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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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”.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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”)
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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 ?
?
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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 ==∀
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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).
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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 ?
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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 ?
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
5
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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)
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
λ
λλ
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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)
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.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTANLABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
FCM, C=3
FCM, C=4segmentare ideala (C=3)
Clusteringfuzzy
“probabilist”
Exemplu
6
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Clusteringfuzzy
“probabilist”Limitarile modelului de “impartire” a vectoruluiintre clase.
A
B
C
clasa 1 clasa 2
prototip 1 prototip 2
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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”
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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)
1. alege un set aleator de prototipuri
2. calculeaza parametrii claselor (“largimea”)
3. calculeaza apartenenta fiecarui vector la clasele partitiei
4. calculeaza prototipurile claselor ca mediile ponderate ale vectorilor
5. 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 ?
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
3. calculeaza apartenenta fiecarui vector la clasele partitiei
4. calculeaza prototipurile claselor ca mediile ponderate ale vectorilor
5. evalueaza cardinaliatea claselor; reduce clasele nesemnificative
6. 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 ?
7. repeta de la 2 daca e cazul.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTANLABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
8
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN