segmentarea imaginilor extragerea contururilor - …imag.pub.ro/ro/cursuri/archive/ai_curs7.pdf ·...

1

LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

C. VERTAN

SEGMENTAREA IMAGINILOR

EXTRAGEREA CONTURURILOR


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


C. VERTAN


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


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


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


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 +=+=∂

∂=∂

∂== θθθθ θθ


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


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


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


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


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

....


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


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)


C. VERTAN

Filtrul liniar cautat : f

Pentru implementarea discreta a filtrului, folosind o fereastracentrata de dimensiune K, avem:

10


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.


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


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


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:


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


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


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.


C. VERTAN

modele de muchii (contururi)

16


C. VERTAN

Zero-crossing (Marr)

Folosirea derivatei secunde pentru detectia contururilor.

Raspunsul maxim al derivatei intai este trecerea prin zero aderivatei a doua.


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


C. VERTAN


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


C. VERTAN

SEGMENTAREA IMAGINILOR

EXTRAGEREA CONTURURILOR:Metode ne-derivative


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


C. VERTAN

Operatori morfologici directionali

(V4)

(V8 - V4)

3


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


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


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.


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


C. VERTAN

Aproximarea suprafetei: cel mai potrivit plan


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


C. VERTAN


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


C. VERTAN

Varianta: modelarea locala a suprafetei prin baza de polinoame


C. VERTAN

Modelul Hueckel al contururilor

9


C. VERTAN

Metoda Mero si Vassy


C. VERTAN

Alte metode

tehnici de relaxare bazate pe modelare Markov

tehnici de detectie statistica

tehnici bazate pe conceptul de contururi active

10


C. VERTAN

Masuri de calitate pentru detectoarele de contur

- precizia de localizare pentru imagini de test marcate

- procentul de detectie a muchiilor

segmentarea imaginilor extragerea contururilor - …imag.pub.ro/ro/cursuri/archive/ai_curs7.pdf ·...

Documents