1
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
SEGMENTAREA IMAGINILOR
EXTRAGEREA CONTURURILOR
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)
Contur:
margine a unei regiuni
zona de variatie puternica a valorilor pixelilor
2
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Extragere contur = identificare a pixelilor in a caror vecinatatese produc variatii importante ale valorilor (nivelului de gri).
Marimea variatiei = intesitatea tranzitiei / conturului
Directia variatiei = directia perpendiculara tranzitiei / conturului
Extragerea conturului prin tehnici derivative(gradient al functiei imagine).
3
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Tehnica de gradient
Fie imaginea f, modelata printr-o functie continua de doua variabile.
Derivata functiei imagine dupa o directie r oarecare este:
ry
yyxf
rx
xyxf
ryxf
∂∂
∂∂+
∂∂
∂∂=
∂∂ ),(),(),(
θθ sin),(cos),(),(y
yxfx
yxfr
yxf∂
∂+∂
∂=∂
∂
)(sincos),( θθθ Fffr
yxfyx =+=
∂∂
x
y
rθ
derivate dupa directii ortogonale fixate
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Tehnica de gradient
Ceea ce intereseaza este :
directia r dupa care derivata este maxima(pe ce directie este tranzitia cea mai puternica)
valoarea maxima a acestei derivate(cat de puternica este tranzitia)
)(sincos),( θθθ Fffr
yxfyx =+=
∂∂
Trebuie studiata variatia acestei expresii in functie de θ.
θθθθ
θθθ
cossinsincos),(yxyx ffff
ryxf +−=
∂∂+
∂∂=⎟
⎠⎞
⎜⎝⎛
∂∂
∂∂
4
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
θθθ
cossin),(yx ff
ryxf +−=⎟⎠⎞
⎜⎝⎛
∂∂
∂∂
Tehnica de gradient
0),( =⎟⎠⎞
⎜⎝⎛
∂∂
∂∂
ryxf
θx
y
ff
arctan0 =θ
directia pe care aparevariatia maxima.
Variatia maxima este :
2200
sincos),(),(max yxyx ffffr
yxfr
yxf +=+=∂
∂=∂
∂== θθθθ θθ
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Tehnica de gradient
Implementare:
calcul derivate verticala/ orizontala in fiecare pixel
calcul variatie maxima in fiecare pixel
daca variatia maxima intr-un pixel este suficient de mare,pixelul respectiv este pixel de contur
pentru pixelii de contur se calculeaza orientarea
5
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Tehnica de gradient
Ce inseamna in discret derivarea pe directia orizontala/ verticala ?
Derivarea este o operatie liniara, deci se va implementa printr-unfiltru liniar (definit de nucleul/ vecinatatea de filtrare).
Pentru o comportare derivativa suma ponderilor vecinatatilor estenula.
000101000
−010000010 −
010000010
−000101
000−
derivate pe directie orizontala derivate pe directie verticalaWy Wx
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Tehnica de gradient
22),(max yx ffr
yxf +=∂
∂
x
y
ff
arctan0 =θ
Wxfx(m,n)
Wyfy(m,n)f
Comparator
harta de orientari
harta binarade contururi
harta de intensitatide tranzitie
6
Tehnica de gradient
Dezavantaj: derivata amplifica zgomotul.
Derivata trebuie combinata cu o filtrare de netezire, care sa opreceada.
Netezirea trebuie sa fie orientata, pe directie perpendicularadirectiei de derivare.
000101000
−01000010
c ⊕101
0101
−−−
cc=
010000010 −
00011000
c ⊕1100011
c
c −−−=
nucleerotitecu 90°
Tehnica de gradient
Valori particulare pentru constanta de ponderare c:
Wy Wx
c=1
c=2
2=c
gradient Prewitt
gradient izotrop
gradient Sobel
101101101
−−−
111000111 −−−
101202
101
−−−
121000121 −−−
101202101
−−−
121000121 −−−
7
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Operatorul compas
Nu toate orientarile sunt utile: precizia de reprezentare pe ogrila discreta a unei drepte cu o orientare fixata este limitata.
Se pot reprezenta usor verticale, orizontale, diagonale.
De ce sa nu se calculeze intensitatea de variatie a imaginii numaidupa aceste directii ?
ii
fmax7...0=
W0f0(m,n)
W1f1(m,n)
f
Comparator
harta de orientari
harta binarade contururi
harta de intensitatide tranzitieW2
f2(m,n)
W3f3(m,n)
W4f4(m,n)
W5f5(m,n)
W6f6(m,n)
W7f7(m,n)
i
i
fmaxarg4
7...0
π
=
8
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Operatorul compas
S = 4
N = 0
E = 2V = 6
Pornind de la o vecinatate debaza, restul vecinatatilor se obtinprin deplasari circulare alefrontierei vecinatatii cu o pozitie.
101202101
−−−
Sobel E
210101012
−−−
Sobel SE
121000121 −−−
Sobel S
....
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Contururile extrase nu sunt “finale”: in general sunt groasesi au puncte lipsa (inchiderea contururilor se face prin folosireainformatiei de orientare si reducerea pragului de definitie apixelilor de contur).
Exista extractoare “optimale” ale contururilor, in sensulpastrarii pozitiei spatiale a tranzitiei (localizare) si identificariitranzitiilor lente (precizie) – filtrele Canny si Deriche.
9
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Modelarea 1D
S(x) - muchie ideala de inaltime Hn(x) - zgomot alb, gaussian, aditiv
I(x) - muchie reala
I(x) = S(x) + n(x)
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Filtrul liniar cautat : f
Pentru implementarea discreta a filtrului, folosind o fereastracentrata de dimensiune K, avem:
10
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Raportul semnal-zgomot la o pozitie oareacare x0 este:
Criteriul 1 de optimizat: maximizarea raportului semnal-zgomotin pozitia de tranzitie (muchia), cu constrangerea ca raspunsul pentruun semnal constant sa fie nul.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Criteriul 2 de optimizat - localizarea buna: minimizeaza eroareapatratica medie dintre pozitia reala a muchiei si cel mai apropiatvarf din raspunsul filtrului r(x).
xl* este pozitia unui maxim local in raspunsul filtrului.
Maximizarea lui SNR x LOC produce acelasi filtru optim,
11
Criteriul 3 de optimizat - maxime rare: varfurile (maximele)din raspunsul filtrului r(x) trebuie sa fie, in medie, separate decel putin o distanta xPeak (impusa).
Filtrul optim depinde de raportul xPeak/K.Pentru un raport mai mare ca 0.5, filtrul optim seamana cu oderivata de gaussiana.
cu
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Criteriul 3 este important, intrucat el stabileste parametrul deproiectare al filtrului: largimea de banda = dispersia gaussieneide baza din care provine filtrul optim.
Cu cat dispersia σr creste, detectia (SNR) se imbunatatestesi localizarea (LOC) devine mai putin precisa.
12
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Canny 2D
Ca si la tehnica simpla de gradient, extragerea contururilor sebazeaza pe amplitudinea derivatei directionale in directiaperpendiculara conturului local.
normala:
gaussiana:
derivatadirectionala:
Directia tranzitiei celei mai abrupte e data tot de gradient:
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Implementare Canny 2D
2y
2x RR)x(S +=
Thr)x(Spt,RR
arctanx
y0 >= θ
WxRx(m,n)
WyRy(m,n)f
Detectie varfharta de intensitatide tranzitie
Detectie varf = suprimare non-maxime in directia normalei,multi-scala si praguire cu histerezis de-a lungul conturului.
13
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Observatii
Derivata partiala a gaussianei pe o directie
Dimensiunea suportului filtrului
de obicei K = 7, 9, 11 pentru σr = 1, 4/3, 5/3
IRx
Ry
S
eliminarea valorilor ne-maximalepe dir. perpendiculara conturului.
14
In practica - suprimarea non-maximelor locale- praguire cu histerezis
contur
directia perpendicularape contur
q este un punct pastrat camaxim daca valoarea sa(gradientul imaginii in q)este mai mare decat valoriledin punctele alaturate, r si p.
valorile acestea trebuiescinterpolate.
15
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
In practica - suprimarea non-maximelor locale- praguire cu histerezis
Se folosesc doua praguri de selectie a punctelor de contur:- un prag mare de selectie a unui punct sigur de contur (maxim inharta de intensitati de tranzitie sau gradient)- un prag mic care selecteaza puncte din vecinatatea punctuluide gradient mare - urmareste obtinerea de muchii continue chiar candvariatia gradientului muchiei este mica.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
modele de muchii (contururi)
16
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Zero-crossing (Marr)
Folosirea derivatei secunde pentru detectia contururilor.
Raspunsul maxim al derivatei intai este trecerea prin zero aderivatei a doua.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
In practica se foloseste operatorul LoG - Laplacian of Gaussian(pt a include prop de netezire in operator).
2
22
2)yx(
22
22
2
2
e11x),x(Gx
σ
σσσ
+−
⎟⎟⎠
⎞⎜⎜⎝
⎛−=
∂∂
2
22
2)yx(
22
22
2
2
e11y),y(Gy
σ
σσσ
+−
⎟⎟⎠
⎞⎜⎜⎝
⎛−=
∂∂
2
22
2)yx(
2
22
222 e2yx1),y,x(G σ
σσσ
+−
⎟⎟⎠
⎞⎜⎜⎝
⎛−+=∇
Mai ramane problema determinarii trecerilor prin zero…
17
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Cvadrante de impartire a vecinatatii 3x3a punctului curent verificat pttranzitia prin zero.
Tranzitia prin zero inseamna ca intre 2cvadrante valoarea derivatei isi schimbasemnul.
Deci vom avea de determinat daca existaun cvadrant de valoare medie pozitiva siun cvadrant de valoare medie negativa.
1
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
SEGMENTAREA IMAGINILOR
EXTRAGEREA CONTURURILOR:Metode ne-derivative
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Gradientul morfologic
grad f = f ⊕ b – f Θ b == max - min
b = element structurant plat
Metode neliniare
Conturul interior/ exterior (morfologic)
Δ f = f ⊕ b – f
δ f = f – f Θ b
se poate arata ca, pentruun element structurant plat cusuport V8, acesta este unoperator compas
Metodele produc harti de intensitati de tranzitie, ce trebuiepraguite….
2
contur exterior
contur interior
gradient morfologic
element structurant platcu suport 5 x 5
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Operatori morfologici directionali
(V4)
(V8 - V4)
3
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Abordarea de suprafata
Local (in jurul pixelului curent testat) valorile functiei imaginesunt vazute ca punctele unei suprafete, ale carei variatii determinacaracteristicile de contur sau interior de regiune uniforma.
Suprafata inseamna reprezentarea in 3D - triplete (x, y, f(x,y)).
Suprafetele pot fi aproximate/ interpolate cu forme analitice;formele analitice pot fi analizate matematic pentru a determinaexact tranzitii, pante, inflexiuni, …
4
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Aproximarea suprafetei: cea mai potrivita cuadrica
In jurul pixelului curent suprafata functiei imagine este aproximatain sensul erorii patratice minime cu o functie cuadrica (formapatratica):
pixel curent - (m,n)
Coeficientii A - E se determina din minimizarea erorii patricemedii de aproximare a valorilor reale din imagine, in vecinatateapixelului curent, prin valoarea functiei de suprafata, z.
, cu
Pentru o vecinatate V8 (3 x 3), eroarea de aproximare este:
Coeficientii se obtin din anularea derivatelor partiale ale erorii dupaA - E:
5
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Solutii :
Expresii liniare, se pot obtine prin filtrari liniare ale imaginii cunuclee de filtrare convenabil alese.
Ce intereseaza este insa expresia analitica a variatiei suprafetei,adica ecuatia analitica a planului tangent la suprafata in pixelulcurent.
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Ecuatia planului tangent suprafetei va fi deci:
Derivatele imaginii (ale suprafetei) sunt date de coeficientiiC si D (coeficientii liniari din expresia planului tangent).Ce erau insa C si D, dpdv al implementarii si formulei de calcul ?
Prewitt !
6
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Aproximarea suprafetei: cel mai potrivit plan
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Aproximarea suprafetei: cea mai potrivita cubica(abordarea topografica - “relief”)
Suprafata este vazuta ca relieful unui teren (“creste” si “vai”).
Ecuatia de tip cubic:
Coeficientii se determina prin aproximarea in sensul erorii patraticemedii minime intr-o vecinatate 5 x 5 a pixelului curent. Modul decalcul este analog celui de la aproximarea cu cuadrica, rezultandcoeficienti ce pot fi calculati prin filtrarea liniara a imaginii cu masticonvenabil alese.
Suprafata este apoi reprezentata in coordonate polare (α, ρ).
7
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Determinarea vailor si crestelor se face prin:
, adica
Apoi, distanta pana la profilul de tranzitie este :
De unde directia de tranzitie este:
si este acceptat daca δ < 0.5
8
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Varianta: modelarea locala a suprafetei prin baza de polinoame
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Modelul Hueckel al contururilor
9
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Metoda Mero si Vassy
LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR
C. VERTAN
Alte metode
tehnici de relaxare bazate pe modelare Markov
tehnici de detectie statistica
tehnici bazate pe conceptul de contururi active