segmentarea imaginilor (orientata pe regiuni...

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

SEGMENTAREA IMAGINILOR(ORIENTATA PE REGIUNI)

THRESHOLDING

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

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

Exemplu

C=2T=170

Segmentare

Evident, segmentarea inseamna ca pentru fiecare pixel din imagine,in functie de valoarea acestuia (si poate si alte valori din imagine)si in functie de parametri specifici unui anume metode, sa se decidacare componenta din care respectivul pixel face parte.

Parametrii care particularizeaza o metoda generala pentru oanume imagine pot sa depinda

doar de valoare pixelilor

de valoarea pixelilor si de caracteristicide vecinatate ale pixelilor

de valoarea pixelilor, de caracteristicide vecinatate ale pixelilor si de pozitiain imagine

segm. globala

segm. locala

segm. dinamica

segm. adaptiva

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Segmentare globalaMetoda concavitatilor histogramei

Minimele histogramei sunt vazute ca niste concavitati alefunctiei h(i).

Determinam concavitatile ca diferenta fata de anvelopa convexaa functiei histograma.

0 50 100 150 200 250 3000

0.002

0.004

0.006

0.008

0.01

masura de “echilibru”a pragului de segmentarefata de diferentele deconcavitate

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Segmentare globalaMetode bazate pe histograma cumulativa

functia de rapartitie asociatahistogramei

Presupunand ca obiectele de interes sunt de nivel de griinchis si ocupa o arie relativa P% din imagine, atunci pragulde segmentare T se determina prin:

Pentru obiecte de interes luminoase,

H(T) ≅ 1- P

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Segmentare globalaMetode bazate pe histograma cumulativa

( ) 2/32 )x('H1)x(''H)x(C−

+=

Pragurile se aleg in punctele de curbura 0 ale functiei derepartitie a imaginii.

( ) 2/32 )(1)(')( −+= xhxhxC

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN0 50 100 150 200 250 300

-0.005

0

0.005

0.01

0.015

0.02

0.025

0.03

0.035

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Riddler

cu

backgroundforeground

mbmf

Topt

Ramesh et al – gasirea pragului prin aproximarea formei

presupune aproximarea histogramei cu functie treapta;inaltimea treptelor sunt mediile valorilor histogrameide o parte si de alta a pragului.

mb

mfTopt

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Segmentare globalaDeterminarea pragurilor ca problema de cuantizare

Cuantizare = aproximarea unui set de valori dat (in general uninterval de valori) cu un numar fixat de valori din aceeasi gama,in sensul minimizarii unei erori de aproximare.

Cuantizarea optimala Lloyd-Max:

Cuantizarea trebuie sa minimize eroarea patratica mediede aproximare a dateor cu valorile cuantizate.

Necunoscute: valori de aproximare, intervale de cuantizare

Lloyd-Max

1.

2.

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Pentru segmentare, numarul de valori de aproximare estenumarul de clase de obiecte dorite, valorile de aproximare (cevor constitui etichetele) sunt mijloacele intervalelor claselor(si sunt putin importante) iar pragurile de segmentare corespundlimitelor intervalelor de cuantizare.

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Aceasta revine la a minimiza varianta medie a partitiei, adicasuma variantelor claselor partitiei ponderate cu probabilitatilelor de aparitie.

Caracterizarea partitionarii bune prin generarea de moduri “inguste”se regaseste in majoritatea metodelor de alegere a pragurilorde segmentare, chiar daca formulata diferit.

Exemple clasice sunt metodele Otsu si respectiv Fisher.

Segmentare globalaMetoda Fisher

Partitionarea optima minimizeaza momentele de inertieale claselor fata de media lor.

de minimizat

de maximizat

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Segmentare globalaMetoda Otsu

Partitionarea optima minimizeaza unul dintre rapoartele dintre- varianta partitiei si varianta globala-

Cel mai simplu: minimizareavariantei medii globale de partitionare

In acest caz, metoda Otsu e identica cu cuantizarea optimala.

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Implementare:

Cel mai simplu in cazul binarizarii (un prag) - functia criteriude optimizat este calculata pentru toate valorile posibile alenivelelor de gri, cu valoirle statistice ce corespund claselor(probabilitati, medii, variante) evaluate iterativ.

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ε

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Optim : 0)(

=dT

Tdε

∫∫+∞

∞−

+=T

T

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

)()( 2211 TpPTpP =

ecuatie rezolvabila (necunoscuta T), in conditiile in carese stiu probabilitatile claselor si forma functiilor dedensitate de probabilitate ce modeleaza clasele.

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Daca variantele claselor sunt egale,pragul este:

2

1

21

221 ln

2 PPT

μμσμμ−

−+

=

In cazul particular cel mai curent, distributiile ce caracterizeaza

obiectele sunt normale (gaussiene).

⎟⎟⎠

⎞⎜⎜⎝

⎛ −−= 2

2

2 2)(exp

2

1))(,(i

i

i

iiixxNσμ

πσσμ

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

- costuri/ penalitati ?

- mai mult de doua clase ?

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

SEGMENTAREA IMAGINILOR(ORIENTATA PE REGIUNI)

THRESHOLDING

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Segmentare globalaMetoda Bhattacharyya

Ipoteza: clasele de obiecte pot fi modelate cu distributii gaussiene.

Metoda: descompunerea histogramei imaginii in moduri normale.

⎟⎟⎠

⎞⎜⎜⎝

⎛ −−= 2

2

2 2)x(exp

2

1)x)(,(Nσμ

πσσμ

2

22

2)x(2ln)x)(,(Nln

σμπσσμ −

−−=

nmxx)x)(,(Nlndxd

22 +=+−=σμ

σσμ

Obs. ca :

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

0 50 100 150 200 2500

0.002

0.004

0.006

0.008

0.01

0 50 100 150 200 250-0.1

0

0.1

0.2

0.3

Unui mod gaussian ii corespunde o dreapta descrescatoare in domeniulfunctiei discriminant (derivata logaritmului densitatii de probabilitate).

histogramatrimodala

functia discriminant(derivata logaritmuluihistogramei)

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

In functia discriminant se vor identifica deci domeniile pe carefunctia este descrescatoare. Aceste domenii separa modurilenormale in histograma.

Parametrii modurilor sunt obtinuti din parametrii dreptei deaproximare a functiei discriminant.

nmxx)x)(,(Nlndxd)z(z 22 +=+−==

σμ

σσμ

Segmentarea se va face dupa praguri alese pe capetele intervalelorde descrestere a functiei discriminant.

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

0 50 100 150 200 250 3000

0.1

0.2

0.3

Alternativ: nivelele de gri din interiorul fiecarui mod sunt inlocuitecu media modului respectiv.

Segmentarea poate fi vazuta astfel ca o problema de aproximarea valorilor imaginii.

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Original:230 nivele gri

Aproximare 1:22 nivele gri

SNR= 29.6 dB

Aproximare 2:13 nivele gri

SNR=20.4 dB

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Original:247 nivele gri

Aproximare 1:40 nivele griSNR= 35 dB

Aproximare 2:13 nivele griSNR=24 dB

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Observatii:

Numarul de moduri nu poate fi controlat decat prin impunereaunei lungimi minime a unui interval de descrestere a functieidiscriminant si a unei erori mici de aproximare cu o dreapta.

Putem considera ca metoda imi asigura o legatura intre conceptelede segmentare si cuantizare (aproximare a valorilor initiale cualte valori, in numar mai mic).

Apar probleme daca ipoteza de normalitate a modurilor nueste adevarata.

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Separabilitatea modurilor si masuri de eroare

Inegalitatea Cebasev:

Pentru orice variabila aleatoare de dispersie σ, probabilitatea cavariabila aleatoare sa fie mai departata cu k×σ fata de media sa estecel mult

( ) 21Probk

kx ≤≥− σμ

Fata de o distributie normala, estimarea de mai sus este “larga”.

“aproape toate valorile sunt apropiate de medie”

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Inegalitatea Cantelli:

Derivata din inegalitatea anterioara (Cebasev) numai pentru k>0si valori mai mari ca media variabila aleatoare:

( ) 21Probk

kx ≤≥− σμ

( ) 211Probk

kx+

≤≥− σμ

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Inegalitatea Visochanski-Petunin:

Derivata din inegalitatea anterioara (Cebasev) numai pentrudistributii unimodale:

( ) 21Probk

kx ≤≥− σμ

( )38,

94Prob 2 ≥≤≥− kk

kx σμ

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Inegalitatea Gauss:

Pentru orice variabila aleatoare de dispersie σ, probabilitatea cavariabila aleatoare sa fie mai departata cu k×σ fata de modul sau estecel mult

( )( ) ( )

( ) ( )⎪⎪⎩

⎪⎪⎨

⎧

+−⋅<

+−⋅−

+−⋅≥

+−⋅

≤≥−

2

22

2

22

2

22

2

22

2

34,

311

34,

94

Prob

σσμ

σσμ

σσμ

σσμ

σmkmk

mkmkkmx

( )22 mx −=τ

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Algoritmul EXPECTATION MAXIMIZATION (EM)

( ) ( )

{ }

∑

∑

=

=

=

=

=

==

K

ii

Kiiii

K

iiiii xfxNxh

1

...12

1

2

1

,,

|)(,)(

α

σμαθ

θσμα

Se presupune ca valorile pixelilor sunt rezultatul unui amestecde distributii normale (GMM = Gaussian Mixture Models)

Cunoastem valorile individuale x si histograma h(x), dorim sagasim vectorul de parametri θ.

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Obiectiv: dandu-se N observatii x, sa se gaseasca θ ca estimat deplauzibilitate maxima:

( )θθθ

|,...,maxarg 1 Nxxf=

Algoritm:1. Initializare

2. Pas E (expectation)

• Pe baza lui θ curent, fiecare punct de date este asociat unei gaussiene (ca probabilitate de apartenenta)

3. Pas M (maximization)• Pe baza valorilor datelor, se determina noii parametri ai gaussienelor

4. Se repeta 2-3 pana la convergenta (~zeci de iteratii)

Implementare EM

• Pas E (estimarea probabilitatii punctului t asociat distributiei gaussiene j):

• Pas M (estimare noi parametri):

,

1

( , )1,..., 1,...,

( , )j t j j

t j Ki t i ii

f xw j K t N

f x

α μ

α μ=

Σ= = =

Σ∑,

1

,1

,1

,1

,1

1

( )( )

Nnewj t j

tN

t j tnew tj N

t jtN new new T

t j t j t jnew tj N

t jt

wN

w x

w

w x x

w

α

μ

μ μ

=

=

=

=

=

=

=

− −Σ =

∑

∑∑∑

∑

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

0 50 100 150 200 250 3000

0.002

0.004

0.006

0.008

0.01

0.012

0.014

0 50 100 150 200 250 3000

0.002

0.004

0.006

0.008

0.01

0.012

0.014

0 50 100 150 200 250 3000

0.002

0.004

0.006

0.008

0.01

0.012

0.014

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

0 50 100 150 200 250 3000

0.002

0.004

0.006

0.008

0.01

0.012

0.014

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN0 50 100 150 200 250

0

0.005

0.01

0.015

0.02

0.025

0.03

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN0 50 100 150 200 250

0

0.005

0.01

0.015

0.02

0.025

0.03

0.035

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Next: metode locale si adaptive.

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Segmentare globalaMetoda Kittler-Illingworth

Dar daca parametrii mixturii de distributii nu se cunosc ?

Metoda K-I propune un mod de estimare a parametrilor statisticiai modurilor histogramei prin functii criteriu legate de masurainformatiei.

Cazul cel mai simplu: binarizarea.

Histograma reala : h(i)

Histograma bimodala teoretica: p(i)

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

h(i)

H - ipoteza ca nivelul i provine din hH’ - ipoteza ca nivelul i provine din p

Pr (H) = Pr (H’)

Informatia medie in favoarea uneia dintre ipotezele H/ H’este data de:

J de minimizat sau termenul 2 de maximizatCum am presupus ca mixtura este normala (gaussiana) si avemexpresia pentru p(i),

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Pentru o aproximare buna a parametrilor statistici ai modurilor

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Segmentare globalaMetode entropice (Pun/ Kapur & Sahoo)

Trebuie maximizata informatia medie pe nivel de gri ce corespundepartitionarii cu un set de praguri de segmentare date.

cu

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

Separabilitatea Nakagawa

separabilitatea modurilor histogramei inseamna:

Pentru moduri vecine normale,