lab3_pdi.pdf

Prelucrarea digitală a imaginilor – Laborator 3

Segmentarea imaginilor (1) - Detectia punctelor, a liniilor si

a muchiilor

1. Introducere 2. Detectia punctelor 3. Detectia muchiilor

a. Formularea problemei b. Operatori bazati pe derivata de ordin 1 (Roberts, Prewitt, Sobel,

Canny) c. Operatori bazati pe derivata de ordin 2 (Laplacian, Zero-crossing,

LoG) d. Limitari ale segmentarii bazate pe muchii

4. Detectia liniilor a. Formularea problemei b. Procesare locala c. Procesare globala - transformata Hough pentru linii

1. Introducere

The growing need for automated image analysis and interpretation in a wide range of applications necessitates the development of segmentation algorithms. Segmentation involves partitioning an image into a set of homogeneous and meaningful regions, such that the pixels in each partitioned region possess an identical set of properties or attributes. These sets of properties of the image may include gray levels, contrast, spectral values, or textural properties. The result of segmentation is a number of homogeneous regions, each having an unique label. An image is thus defined by a set of regions that are connected and non-overlapping, so that each pixel in the image acquires a unique region label that indicates the region it belongs to. The set of objects of interest in an image, which are segmented, undergoes subsequent processing, such as object classification and scene description.

Segmentation algorithms are based on one of the two basic properties of gray-level values: discontinuity and similarity among the pixels.

In the first category of algorithms, we partition an image based on abrupt changes in gray level. The principal areas of interest within this category are the detection of lines and edges in an image. Thus if we can extract the edges in an image and link them, then the region is described by the edge contour that contains it.

We may view the process of segmentation from another perspective. From this point of view, the connected set of pixels having more or less the same homogeneous intensity forms the regions. Thus the pixels inside the regions describe the region and the process of segmentation involves partitioning the entire scene in a finite number of regions.

The principal approaches in the second category are based on the similarity among the pixels within a region. While segmenting an image, various local properties of the pixels are utilized. The well-established segmentation techniques are: Histogram-based thresholding, Region growing, region splitting and merging, Clustering/Classification, Graph theoretic approach, Rule-based or knowledge-driven approach.


2. Detectia punctelor

Detectia punctelor izolate care se regasesc in arii cu intensitate constanta sau aproximativ constanta dintr-o imagine se poate face utilizand masca

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

−−−−−−−−

111181111

.

Spunem ca un punct izolat a fost detectat in locatia centrului mastii daca raspunsul mastii este mai mare decat o valoare de prag non-negativa. 3. Detectia muchiilor 3.a. Formularea problemei

Many approaches to image interpretation are based on edges, since analysis based on edge detection is insensitive to change in the overall illumination level. Edge detection highlights image contrast. Detecting contrast, which is difference in intensity, can emphasize the boundaries of features within an image, since this is where image contrast occurs. This is, naturally, how human vision can perceive the perimeter of an object, since the object is of different intensity to its surroundings. Essentially, the boundary of an object is a step-change in the intensity levels. The edge is at the position of the step-change.

To detect the edge position we can use first-order differentiation since this emphasizes change; first order differentiation gives no response when applied to signals that do not change. The first edge detection operators to be studied here are group operators which aim to deliver an output which approximates the result of first-order differentiation.

3.b. Operatori bazati pe derivata de ordin 1 (Roberts, Prewitt, Sobel, Canny) 3.b.1. Gradientul imaginii

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

∂∂

∂∂

=∂

∂+∂

∂=∇

yyxfxyxf

jyyxfi

xyxfyxf ),(

),(),(),(),(

(1)

→→+=∇ jGiGyxf yx),(

Amplitudinea (mărimea gradientului) este:

2222

yx GGyf

xff +=⎟⎟⎠

⎞⎜⎜⎝

⎛∂∂+⎟

⎠⎞⎜

⎝⎛∂∂=∇ (2)

Variaţia maximă este în direcţia:

( ) ⎟⎟⎠

⎞⎜⎜⎝

⎛=

x

y

GG

arctgyx,α (3)

În aplicaţii, pentru a nu lucra cu radicali, se aproximează mărimea gradientului prin:


sau { }yx

yx

GGf

GGf

,max=∇

+=∇ (4)

Aproximarea discretă a gradientului:

yyxfyyxf

yfG

xyxfyxxf

xfG

y

x

Δ−Δ+≈

∂∂=

Δ−Δ+≈

∂∂=

),(),(

),(),(

(4`)

Deoarece 1=Δ=Δ yx , ⇒

),()1,(),(),1(yxfyxfGyxfyxfG

y

x

−+=−+=

(5)

Aceste aproximări corespund convoluţiei funcţiei imagine cu măştile:

]11[1 −=M şi ⎥⎦

⎤⎢⎣

⎡−=11

2M

3.b.2. Operatori care aproximeaza gradientul imaginii O regiune din imaginea de prelucrat (funcţia f(x,y)) de dimensiune 3x3 o notăm:

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

987

654

321

zzzzzzzzz

)1,1(

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

),(

9

3

2

1

5

++↔

−+↔−↔

−−↔↔

yxfz

yxfzyxfzyxfz

yxfz

Aproximarea făcută anterior este:

)( 56 zzGx −= , )( 58 zzGy −= (6) Alte aproximari pentru amplitudinea gradientului si mastile corespunzatoare sunt prezentate in Figura 1 (aproximarile Sobel, Prewitt si Roberts).


Figura 1. Operatori (masti) de detectie a muchiilor si aproximarea derivatei de ordin 1

implementata de fiecare (vezi SPG - Lab 12)


3.b.3. Detectorul Canny Metoda Canny de detectie a muchiilor poate fi sumarizata astfel:

1. Pentru a reduce zgomotul, imaginea este netezita cu un filtru Gaussian cu o deviatie standard specificata, σ .

2. In fiecare punct se calculeaza gradientul local 2/122 ][),( yx GGyxg += , si directia

muchiei )(tan 1xy GG−=α . Pentru calcularea xG si yG poate fi utilizata

oricare din tehnicile discutate anterior. Un punct de tip muchie este definit ca fiind un punct a carui amplitudine a gradientului este maxim local in directia gradientului.

3. Punctele de tip muchie determinate in pasul (2) determina aparitia unor creste in imaginea amplitudinii gradientului. Algoritmul itereaza pixelii aflati in varful acestor creste si ii seteaza pe 0 pe aceia care nu se afla strict pe varful unei creste astfel incat sa se obtina o linie subtire, proces cunoscut sub numele de suprimare non-maximala. Pixelii de pe creste sunt apoi comparati cu doua valori de prag, T1 si T2, cu T1 < T2. Pixelii cu valori mai mari decat T2 sunt considerati pixeli de pe muchii ’tari’. Pixelii cu valori intre T1 si T2 sunt considerati pixeli de pe muchii ’slabe’.

4. In final, algoritmul realizeaza o conectare a muchiilor prin incorporarea pixelilor slabi 8-conectati cu pixeli tari.

3.b.4. Detectia muchiilor utilizand functia MATLAB edge

Conform celor discutate anterior, ideea de baza in detectia muchiilor este de a gasi locatii in imagine unde intensitatea se modifica rapid, utilizand unul din urmatoarele doua criterii generale:

1. gasirea locatiilor unde prima derivata a functiei intensitate este mai mare in amplitudine decat o valoare de prag specificata;

2. gasirea locatiilor unde a doua derivata a functiei intensitate prezinta o trecere prin zero.

Functia edge disponibila in IPT (Image Processing Toolbox) furnizeaza mai

multe estimari (aproximari) ale derivatei in baza criteriilor de mai sus. Pentru unele din aceste estimari este posibil a se specifica daca detectorul este sensibil la muchiile orizontale, verticale sau la ambele tipuri. Sintaxa generala a acestei functii este:

[g,t] = edge(f, ’method’, parameters) unde f este imaginea de intrare, method este una din aproximarile disponibile (vezi Tabelul 1), iar parameters reprezinta parametrii aditionali ce pot fi specificati. La iesire, g este un array de valori logice care contine valori de 1 in locatiile in care au fost detectate puncte de tip muchie in f si 0 in rest. Parametrul t este optional si furnizeaza valoarea de prag utilizata de functia edge pentru a determina daca valorile gradientului sunt suficient de mari pentru a fi considerate muchii.


Detector muchii Proprietati de baza Sobel Detecteaza muchii utilizand aproximarea

Sobel a gradientului (Fig. 1). Prewitt Detecteaza muchii utilizand aproximarea

Prewitt a gradientului (Fig. 1). Roberts Detecteaza muchii utilizand aproximarea

Roberts a gradientului (Fig. 1). Laplacian of Gaussian Detecteaza muchii prin cautarea locatiilor

unde a doua derivata a functiei intensitate prezinta o trecere prin zero dupa aplicarea unui filtru Gaussian (vezi sect. 3.c.).

Zero Crossings Detecteaza muchii prin cautarea locatiilor unde a doua derivata a functiei intensitate prezinta o trecere prin zero dupa aplicarea unui filtru specificat de utilizator (vezi sect. 3.c.).

Canny Detecteaza muchii prin cautarea maximelor locale ale gradientului imaginii. Gradientul este calculat utilizand derivata unui filtru Gaussian. Metoda utilizeaza doua valori de prag pentru detectarea muchiilor slabe si a muchiilor tari, si include muchiile slabe in rezultat doar daca acestea sunt conectate cu muchii tari. Astfel este mai probabil ca metoda sa detecteze muchiile slabe reale (vezi sect. 3.b.3).

Tabelul 1. Metode de detectie a muchiilor disponibile in functia edge Sintaxa de apel a functiei edge pentru operatorii bazati pe derivata de ordin 1:

[g,t] = edge(f, ’sobel’, T, dir) [g,t] = edge(f, ’prewitt’, T, dir) [g,t] = edge(f, ’roberts’, T, dir) [g,t] = edge(f, ’canny’, T, sigma)

dir specifica directia preferata a muchiilor detectate: ’horizontal’, ’vertical’, ’both’(implicit). In cazul detectorului Canny, parametrul T este un vector T=[T1, T2] continand cele doua valori de prag explicate in sectiunea 3.b.3, iar sigma este deviatia standard a filtrului de netezire (valoarea implicita este 1).

3.c. Operatori bazati pe derivata de ordin 2 (Laplacian, Zero-crossing, LoG) 3.c.1. Laplacianul imaginii f(x,y) – funcţia imagine – continuă


( ) 2

2

2

22

yf

xffff

∂∂+

∂∂=Δ=∇=∇∇ (15)

În continuare căutăm o formă discretă pentru relaţia (15): [ ] [ ]

[ ] [ ]2

)'4(

2

2

2

)'4(

2

2

),(),(),(),(

),(),(),(),(

yyyxfyxfyxfyyxf

yf

yyf

xyxxfyxfyxfyxxf

xf

xxf

ΔΔ−−−−Δ+≈⎟⎟⎠

⎞⎜⎜⎝

⎛∂∂

∂∂=

∂∂

ΔΔ−−−−Δ+≈⎟

⎠⎞⎜

⎝⎛∂∂

∂∂=

∂∂

Deoarece ⇒=Δ=Δ 1yx

),(2)1,()1,(

),(2),1(),1(

2

2

2

2

yxfyxfyxfyf

yxfyxfyxfxf

+−++=∂∂

+−++=∂∂

(16)

Implementarea discretă a laplaceianului se obţine sumând relaţiile (16) ⇒ [ ] ),(4)1,()1,(),1(),1(2 yxfyxfyxfyxfyxff −−+++−++=∇ (17)

Ecuaţia (17) poate fi implementată folosind următoarea mască:

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡−=

010141010

0L (17’)

Masca 0L asigură un răspuns izotropic la ratoţia cu un increment de 90 . Direcţiile diagonale pot fi incorporate în direcţia Laplaceianului astfel:

[ ][ ] ),(4)1,1()1,1()1,1()1,1(

),(4)1,()1,(),1(),1(1

yxfyxfyxfyxfyxfyxfyxfyxfyxfyxff

−+++−+++−+−−+−−+++−++=∇ (18)

Masca corespunzătoare este:

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡−=

111181111

1L (19)

Acest filtru este izotropic pentru rotaţiile la 45 .

Obs. Se pot folosi şi măştile în care punctul central este pozitiv:

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

−−−

−=

010141010

2L (20)

Respectiv

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

−−−−−−−−

=111181111

3L (21)

În urma aplicării laplaceianului, regiunile în care există discontinuităţi pronunţate vor apărea mai luminoase (contururile) iar cele în care nivelurile de gri variază lent se vor întuneca. Aceasta înseamnă că se produc imagini care au contururi şi alte discontinuităţi de culori deschise toate imprimate pe un fond întunecat (negru).


Prin urmare se obţine o accentuare a contururilor intr-o imagine prin simpla adunare dintre imaginea iniţială şi laplaceianul imaginii. Obs. În cazul în care coeficientul central al măştii laplaceianului este negativ, se poate face scădere. Deci accentuarea contururilor se poate face prin:

⎩⎨⎧

∇+∇−

=)(),(),()(),(),(

),( 2

2

byxfyxfayxfyxf

yxg (22)

(a) pentru coeficient central negativ (b) pentru coeficient central pozitiv

Ecuaţia (22)(a) este de fapt implementată printr-o singură mască. De exemplu, înlocuind expresia laplaceianului dată de (17) rezultă:

[ ])1,()1,(),1(),1(),(5),( −+++−++−= yxfyxfyxfyxfyxfyxg (23) Masca corespunzătoare este:

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

−−−

−=

010151010

0A (24)

În cazul laplaceianului dat de relaţia (18) se obţine masca:

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

−−−−−−−−

=111191111

1A (25)

3.c.2. Laplacian of a Gaussian (LoG) Consideram functia Gaussiana

2

2

2)( σr

erh−

−= (26) unde 222 yxr += si σ reprezinta deviata standard. Aceasta este o functie de netezire care, la convolutia cu o imagine va produce un efect de blur. Gradul de netezire este determinat de valoarea lui σ . Laplacianul acestei functii (a doua derivata in functie de r ) este

2

2

24

222 )()( σ

σσ

r

errh−−−=∇ . (27)

Din motive evidente aceasta functie se numeste Laplacian of a Gaussian (LoG). Deoarece derivarea de ordin 2 este o operatie lineara, convolutia (filtrarea) unei imagini cu )(2 rh∇ este acelasi lucru cu convolutia imaginii cu o functie de netezire si apoi calcularea Laplacianului rezultatului. Astfel, aplicarea operatorului LoG are doua efecte: netezeste imaginea (astfel reducand zgomotul) si calculeaza Laplacianul care furnizeaza o image cu muchii duble.


Figura 2. Derivatele de ordin 1 si 2 intr-o zona in care au loc variatii bruste ale

functiei imagine (muchie de tip treapta). Sintaxa de utilizare a detectorului LoG folosind functia edge este

[g,t] = edge(f, ’log’, T, sigma) unde sigma este deviatia standard. Valoarea implicita a parametrului sigma este 2. Ca si in cazul celorlalti operatori, functia edge ignora orice muchie care nu are amplitudinea gradientului mai mare decat T. Daca nu este furnizata o valoare pentru


T, functia alege o valoare de prag in mod automat. Setarea valorii 0 pentru T produce muchii care reprezinta contururi inchise, o caracteristica cunoscuta a metodei LoG.

3.c.3. Zero-crossing Acest detector este bazat pe acelasi concept ca si metoda LoG, dar convolutia este realizata utilizand o functie de filtrare specificata, H. Sintaxa de apel al functiei edge este

[g,t] = edge(f, ’zerocross’, T, H). 3.d. Limitari ale segmentarii bazate pe muchii The principal limitations of edge detection methods are:


(a) The edges extracted using the classical methods often do not necessarily correspond to boundary objects. In many low-quality images, captured using low quality imaging devices, some of the conventional methods produce spurious edges and gaps and their applicabilities are thus limited.

(b) The edge detection techniques depend on the information contained in the local neighborhood of the image. Most of the edge detection techniques do not consider model-based information embedded in an image.

(c) In most of the cases the edge detection strategies ignore the higher order organization which may be meaningfully present in the image.

(d) After the edge points are extracted from the image, these points are linked in order to determine boundaries. This is usually done by first associating edge elements into edge segments and then by associating segments into boundaries. The edge linking process sometimes leads to discontinuities and gaps in the image.

(e) The edge linking methods often resort to arbitrary interpolation in order to complete boundary gaps.

(f) It is often difficult to identify and classify spurious edges.

4. Detectia liniilor 4.a. Formularea problemei

In mod ideal, metodele discutate in sectiunea anterioara ar trebui sa furnizeze pixeli care se afla doar pe muchii. In practica, acest set de pixeli rareori caracterizeaza in mod complet o muchie datorita zgomotului, intreruperilor muchiei datorate iluminarii neuniforme si a altor efecte ce introduc false discontinuitati ale intensitatii. Astfel, algoritmii de detectie a muchiilor sunt urmati in mod tipic de proceduri de conectare pentru asamblarea pixelilor in muchii semnificative. 4.b. Procesare locala

Una din cele mai simple abordari pentru conectarea punctelor de tip muchie este de a analiza caracteristicile pixelilor intr-o vecinatate mica (ex. 3x3 sau 5x5) a fiecarui punct (x,y) ce a fost catalogat drept punct de tip muchie prin una din metodele discutate. Toate punctele similare in raport cu un set de criterii predefinite sunt conectate formand o muchie.

Cele doua proprietati principale utilizate pentru stabilirea similaritatii pixelilor-muchie sunt (1) marimea gradientului si (2) directia gradientului.

Prima proprietate este data de valoarea f∇ definita in Ec. 2. Astfel, un pixel-muchie de coordonate ( 00 , yx ) dintr-o vecinatate predefinita a ( yx, ) este similar in marime cu pixelul ( yx, ) daca

Eyxfyxf ≤∇−∇ |),(),(| 00 , (28) unde E este o valoare de prag, non-negativa. Directia (unghiul) vectorului gradient este dat in Ec. 3. Un pixel-muchie de coordonate ( 00 , yx ) dintr-o vecinatate predefinita a ( yx, ) are un unghi similar cu pixelul ( yx, ) daca

Ayxyx <− |),(),(| 00αα , (29)


unde A este o valoare unghiulara de prag, non-negativa. Un punct din vecinatatea predefinita a pixelului ( yx, ) este conectat cu pixelul ( yx, ) daca atat criteriul de magnitudine cat si cel de directie sunt satisfacute. Acest proces este repetat pentru fiecare locatie din imagine. Pe masura ce centrul vecinatatii este mutat de la un pixel la altul, trebuie pastrata o evidenta a punctelor conectate. O procedura simpla este de a asigna un nivel de gri diferit fiecarui set de pixeli conectati. 4.c. Procesare globala - transformata Hough pentru linii 4.c.1. Transformata Hough

Dat fiind un set de puncte dintr-o imagine (binara), se doreste gasirea unor subseturi ale acestor puncte localizate pe linii drepte. O solutie posibila este de a gasi mai intai toate liniile determinate de fiecare pereche de puncte si apoi de a gasi toate subseturile de puncte care sunt apropiate de anumite linii. Problema acestei proceduri este ca implica gasirea a 2~)1( nnn − linii si apoi efectuarea a 3~2))1(( nnnn − comparatii ale fiecarui punct cu fiecare linie. Aceasta abordare este restrictiva din punct de vedere computational. Pe de alta parte, in cazul transfromatei Hough, se considera un punct ),( ii yx si toate liniile ce trec prin acest punct. Prin acest punct trec o infinitate de linii, toate satisfacand ecuatia baxy ii +−= . Scriid aceasta ecuatie sub forma ii yaxb +−= si considerand planul ab (denumit si spatiul parametrilor) se obtine ecuatia unei singure linii pentru o pereche fixa ),( ii yx . Mai mult, un al doilea punct ),( jj yx are de asemenea asociata o linie in spatiul parametrilor, si aceasta linie intersecteaza linia asociata cu ),( ii yx in )','( ba , unde 'a este panta iar 'b interceptul liniei ce contine atat punctul ),( ii yx cat si ),( jj yx in planul xy . De fapt, toate punctele de pe aceasta linie au asociate linii in spatiul parametrilor care se intersecteaza in punctul )','( ba . Figura 3 ilustreaza acest concept.

Figura 3. (stanga) Planul xy . (dreapta) Spatiul parametrilor.


In principiu, pot fi trasate liniile din spatiul parametrilor corespunzatoare tuturor punctelor ),( ii yx din imagine, si, apoi, liniile in imagine sa fie identificate prin numarul mare de intersectii ale liniilor din spatiul parametrilor. Totusi, o dificultate practica a acestei abordari este aceea ca a (panta liniei) tinde spre infinit pe masura ce linia se apropie de directia verticala. O modalitate de a rezolva aceasta problema este de a utiliza reprezentarea unei linii utilizand coordonate polare:

θθρ sincos yx += . (30)

Figura 4. (stanga) Parametrizarea ),( θρ a liniilor din planul xy . (mijloc) Curbe

sinusoidale in planul ),( θρ ; punctul de intersectie, )','( θρ , corespunde parametrilor liniei ce uneste ),( ii yx si ),( jj yx . (dreapta) Divizarea planului ),( θρ in celule

acumulator.

Figura 4 ilustreaza interpretarea geometrica a parametrilor ρ si θ . O linie orizontala are °= 0θ si ρ egal cu intersectia cu axa x. In mod similar, o linie verticala are °= 90θ si ρ egal cu intersectia cu axa y pozitiva, sau °−= 90θ si ρ egal cu intersectia cu axa y negativa. Fiecare curba sinusoidala din Figura 4 (mijloc) reprezinta o familie de linii ce trec printr-un anumit punct ),( ii yx . Punctul de intersectie )','( θρ corespunde liniei ce trece atat prin ),( ii yx cat si prin ),( jj yx .

Faptul ca transformata Hough este atractiva din punct de vedere computational provine din sub-divizarea spatiului parametrilor ),( θρ in asa-numite celule de acumulare ca in Figura 4 (dreapta), unde ),( maxmin ρρ si ),( maxmin θθ sunt intervalele prevazute pentru valorile parametrilor. Uzual, intervalele maxime de valori sunt

°≤≤°− 9090 θ si DD ≤≤− ρ , unde D reprezinta distanta dintre colturile imaginii. Celula de coordonate ),( ji , cu valoarea acumulator ),( jiA , corespunde patratului asociat cu coordonatele ),( ji θρ din spatiul parametrilor. Initial aceste celule au valorile setate pe zero. Apoi, pentru fiecare punct muchie ),( kk yx din planul imaginii, se variaza θ in intervalul subdivizat si se calculeaza valorile ρ corespunzatoare utilizand ecuatia θθρ sincos kk yx += . Valorile ρ rezultate sunt apoi rotunjite la cea mai apropiata celula pe axa ρ . Celula acumulator corespunzatoare este incrementata. La terminarea acestei proceduri, o valoare Q in ),( jiA semnifica faptul ca Q puncte din planul xy se afla pe linia jji yx θθρ sincos += . Numarul de subdiviziuni din planul ),( θρ determina acuratetea coliniaritatii acestor puncte.

Functia MATLAB [H, THETA, RHO] = hough(BW) calculeaza transformata Hough a imaginii binare BW.


THETA (in degrees) and RHO are the arrays of rho and theta values over which the Hough transform matrix, H, was generated. [H, THETA, RHO] = hough(BW,PARAM1,VAL1,PARAM2,VAL2) sets various parameters. Parameter names can be abbreviated, and case does not matter. Each string parameter is followed by a value as indicated below:

'ThetaResolution'- Real scalar between 0 and 90, exclusive.

'ThetaResolution' specifies the spacing (in degrees) of the Hough transform bins along the theta axis. Default: 1.

'RhoResolution' - Real scalar between 0 and norm(size(BW)),

exclusive. 'RhoResolution' specifies the spacing of the Hough transform bins along the rho axis. Default: 1. 4.c.2. Detectia varfurilor in spatiul Hough Primul pas in utilizarea transformatei Hough pentru detectia liniilor si conectare il reprezinta detectia varfurilor (maximelor) in spatiul parametrilor. Gasirea unui set semnificativ de varfuri distincte in transformata Hough poate fi o problema dificila. Datorita quantizarii in spatiul imaginii digitale, a cuantizarii in spatiul parametrilor transformarii Hough, precum si a faptului ca, in mod obisnuit, muchiile in imagini nu sunt perfect drepte, varfurile transformatei Hough tind sa fie localizate in mai mult de o celula acumulator. O strategie de a depasi aceasta problema poate fi urmatoarea:

1. determinarea celulei Hough cu cea mai mare valoare si inregistrarea locatiei acesteia;

2. suprimarea (setarea pe zero) celulelor Hough in imediata vecinatate a maximului gasit in pasul 1;

3. repetarea primilor doi pasi pana cand se detecteaza numarul de varfuri dorit, sau pana se atinge o valoare de prag specificata.

IPT MATLAB pune la dispozitie o functie houghpeaks pentru rezolvarea acestei probleme:

PEAKS = houghpeaks(H,NUMPEAKS) locates peaks in the Hough transform matrix, H, generated by the HOUGH function. NUMPEAKS specifies the maximum number of peaks to identify. PEAKS is a Q-by-2 matrix, where Q can range from 0 to NUMPEAKS. Q holds the row and column coordinates of the peaks. If NUMPEAKS is omitted, it defaults to 1.

PEAKS = houghpeaks(...,PARAM1,VAL1,PARAM2,VAL2) sets various parameters. Parameter names can be abbreviated, and case does not matter. Each string parameter is followed by a value as indicated below: 'Threshold' Nonnegative scalar. Values of H below 'Threshold' will not be considered to be peaks. Threshold can vary from 0 to Inf. Default: 0.5*max(H(:)) 'NHoodSize' Two-element vector of positive odd integers: [M N].'NHoodSize' specifies the size of the suppression neighborhood. This is the


neighborhood around each peak that is set to zero after the peak is identified. Default: smallest odd values greater than or equal to size(H)/50. 4.c.3. Detectia si conectarea liniilor utilizand transformata Hough

Odata ce a fost identificat un set de varfuri in tranformata Hough, ramane de determinat daca exista segmente de linie asociate cu aceste varfuri, precum si pozitiile de start si end ale acestor linii.

Pentru fiecare varf, primul pas este de a gasi locatia tuturor pixelilor diferiti de zero din imagine care au contribuit la acel varf. Pixelii asociati cu locatiile gasite trebuie grupati in segmente de linie. Urmatoarea strategie poate fi utilizata:

1. rotatia locatiilor pixelilor cu θ−°90 atsfel incat sa fie asezati aproximativ pe o linie verticala;

2. sortarea locatiilor pixelilor dupa coordonatele x rotite; 3. localizarea golurilor in linie; ignorarea golurilor de mici dimensiuni are ca

efect unirea segmentelor adiacente separate de spatii mici; 4. returnarea informatiilor despre segmentele de linie mai lungi decat o

valoare minima prestabilita. IPT MATLAB pune la dispozitie o functie houghlines pentru extragerea segmentelor de linie pe baza transformatei Hough: LINES = HOUGHLINES(BW, THETA, RHO, PEAKS) extracts line segments in the image BW associated with particular bins in a Hough transform. THETA and RHO are vectors returned by function HOUGH. Matrix PEAKS, which is returned by function HOUGHPEAKS, contains the row and column coordinates of the Hough transform bins to use in searching for line segments. HOUGHLINES returns LINES structure array whose length equals the number of merged line segments found. Each element of the structure array has these fields: point1 End-point of the line segment; two-element vector point2 End-point of the line segment; two-element vector theta Angle (in degrees) of the Hough transform bin rho Rho-axis position of the Hough transform bin The end-point vectors contain [X, Y] coordinates. LINES = HOUGHLINES(...,PARAM1,VAL1,PARAM2,VAL2) sets various parameters. Parameter names can be abbreviated, and case does not matter. Each string parameter is followed by a value as indicated below: 'FillGap' Positive real scalar. When HOUGHLINES finds two line segments associated with the same Hough transform bin that are separated by less than 'FillGap' distance, HOUGHLINES merges them into a single line segment. Default: 20 'MinLength' Positive real scalar.


Merged line segments shorter than 'MinLength' are discarded. Default: 40 TEMA

1. Detectati muchiile in imaginea building.tif utilizand, pe rand, operatorii prezentati (Sobel, Prewitt, Roberts, Canny si LoG). Comparati performantele metodelor

a. utilizand valorile implicite ale parametrilor; b. variind valorile parametrilor pentru a evidentia toate muchiile

semnificative. Care operator furnizeaza cele mai bune rezultate?

2. Analizati urmatoarea imagine care contine linii in spatiul parametrilor Hough.

Ce puteti spune despre imaginea initiala?

3. Implementati o functie MATLAB pentru afisarea pixelilor corespunzatori unei

celule acumulator din spatiul Hough. 4. Evidentiati cele mai semnificative 5 segmente de linie in imaginea building.tif

utilizand transformata Hough. a. Calculati si afisati transformata Hough a imaginii; b. Determinati cele mai semnificative 5 varfuri in spatiul Hough; c. Determinati segmentele de linie corespunzatoare acestor varfuri si

desenati-le in imaginea originala.

lab3_pdi.pdf

Documents