Post on 02-Nov-2021
transcript
1
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
SEGMENTAREA IMAGINILOR
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
Segmentare pe regiuni:
cresterea (si fuziunea) regiunilor
segmentarea in spatiul caracteristicilor
segmentarea pe histograma
algoritimi generali de clustering
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 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
germene regiune,Tunif=10
Exemplu
2
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 :nu exista nici o cale uniforma caresa ii uneasca (deci se trece pestefrontiera)
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”
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.
3
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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 ?
?
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Histograma
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Exemplu
C=2T=170
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
C=3T1=40T2=100
C=4T1=40T2=100T3=
Exemplu
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Exemplu
histograma
histogramaponderata,minime adancite
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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
µµσµµ−
−+=
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
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 ?
?
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.
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.
6
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
?
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 ?
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)
7
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
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.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
FCM, C=3
FCM, C=4segmentare ideala (C=3)
Clusteringfuzzy
“probabilist”
Exemplu
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
8
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN