segmentarea imaginilor extragerea contururiloralpha.imag.pub.ro/ro/cursuri/archive/ai_curs7.pdf ·...

of 27/27
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

Post on 21-Jan-2020

17 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

  • 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

    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 ffffryxf +−=

    ∂∂+

    ∂∂=⎟

    ⎠⎞

    ⎜⎝⎛

    ∂∂

    ∂∂

  • 4

    LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

    C. VERTAN

    θθθ

    cossin),( yx ffryxf +−=⎟⎠⎞

    ⎜⎝⎛

    ∂∂

    ∂∂

    Tehnica de gradient

    0),( =⎟⎠⎞

    ⎜⎝⎛

    ∂∂

    ∂∂

    ryxf

    θx

    y

    ff

    arctan0 =θ

    directia pe care aparevariatia maxima.

    Variatia maxima este :

    2200

    sincos),(),(max yxyx ffffryxf

    ryxf +=+=

    ∂∂=

    ∂∂

    == θθθθ θθ

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

    ∂∂

    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

  • 10

    LABORATORUL DE ANALIZA ŞI PRELUCRAREA IMAGINILOR

    C. VERTAN

    Masuri de calitate pentru detectoarele de contur

    - precizia de localizare pentru imagini de test marcate

    - procentul de detectie a muchiilor

    ai_curs7.pdft.pdf