aeacd 16. segmentarea imaginilor: edge-based...

33
Platformă de e-learning și curriculă e-content pentru învățământul superior tehnic AEACD 16. Segmentarea imaginilor: Edge-based segmentation

Upload: others

Post on 02-Feb-2020

13 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Platformă de e-learning și curriculă e-contentpentru învățământul superior tehnic

AEACD

16. Segmentarea imaginilor: Edge-based segmentation

Page 2: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation

• Determina regiunile analizand discontinuitatile din acestea▫ O muchie (edge corespunde cu o schimbare abrupta a intensitatii

imaginii)

• Exista trei tipuri de discontinuitati de baza in imaginile digitale:▫ Puncte

▫ Linii

▫ Muchii

• Diferenta dintre muchie, linie si punct este evidentiata in imaginea de mai jos:

Page 3: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (2)

• Detectia muchiilor:▫ Edge -> o schimbare semnificativa a intensitatii intr-o

imagine▫ Acestea apar de obicei la granita dintre doua regiuni

diferite ale unei imagini▫ Scopul este de a produce un desen doar din linii a unei

scene dintr-o imagine▫ Schimbarile de intensitate sunt produse de:

Evenimente geometrice▫ Ex: discontinuitati ale orientarii, culorii si texturii unei

suprafete Evenimente non-geometrice

▫ Ex: schimbari de luminozitate, umbre

▫ Detectia schimbarilor de intensitate in cadrul uneiimagini se face utilizand derivatele de ordin 1 si 2

Page 4: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS-Edge detection

Imagine preluata:http://www.scribd.com/doc/6577704/Presentation-2-Edge-Detection

Consideram descriptorii (edge descriptors):

• Normala la muchie (edge normal)

• Vector unitate ce se afla in directia schimbarii maxime de intensitate

• Directia muchiei (edge direction)

• Vector unitate perpendicular pe normala

• Pozitia muchiei (edge position)

• Pozitia la care muchia se afla in cadrul imaginii

• Contrastul muchiei (edge strength)

• Legat de contrastul local al imaginii de-a lungul normalei

Page 5: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS-Edge detection (2)• Tipuri de muchii

▫ Step edge

Intensitatea imaginii se schimba brusc de la o valoare pe o parte a discontinuitatii la alta pe celalalta parte

▫ Ramp edge

La fel ca la step edge, dar shimbarea intensitatii nu se face brusc, ci treptat pe o distanta finita

▫ Roof edge

O variatie treptata a intensitatii ca la ramp edge dar care revine la valoarea initiala

Imagine preluata:http://www.scribd.com/doc/16404926/Digital-Image-Processing-10-Image-Segmentation

Page 6: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS-Edge detection (3)

• 3 pasi fundamentali in detectia muchiilor

1. Nivelarea imaginii pentru reducerea zgomotelor Elimina zogomotele cat mai mult posibil fara a

distruge muchiile existente

2. Detectia punctelor de pe muchie Operatie locala care extrage toate punctele care au

potential de a devenii puncte ale unei muchii

3. Localizarea muchiilor Selectia dintre punctele candidate determinate la

pasul anterior a celor care apartin in mod real uneimuchii

Page 7: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS-Edge detection (4)

• Detectia muchiilor folosind derivatele (1D)

▫ Punctele aflate pe o muchie pot fi detectate: Determinand minima sau maxima locala folosind derivata de

ordin 1

Determinand taierea abscisei (zero-crossing) de catre derivata de ordinul 2

▫ Derivata de ordinul 1:

▫ Derivata de ordinul 2:

Page 8: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS-Edge detection (5)

Imagine preluata:http://www.scribd.com/doc/16404926/Digital-Image-Processing-10-Image-Segmentation

Page 9: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS-Edge detection (6)• Detectia muchiilor folosind gradientul (2D)

• Robert edge detector:▫ mastile de mai jos reprezinta aproximari

in punctele (x+1/2, y+1/2)

Page 10: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS-Edge detection (7)

• Cea mai simpla abordare pentru a folosi derivatele de ordinul 1 sau 2 pentru locatia fiecarui pixel este utilizarea filtrelor spatiale de forma:

• Masca se va aplica astfel: ▫ unde reprezinta valorile de gri corespunzatoare din imagine

Page 11: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS-Edge detection (8)Observati ca suma coeficientilor din toate mastile este zero, dand un raspuns egal cu zero in ariile cu intensitate constanta!

Page 12: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS-Edge detection (9)

Imagine preluata:http://www.scribd.com/doc/16404926/Digital-Image-Processing-10-Image-Segmentation

Page 13: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (3)

• Detectia liniilor▫ Reprezinta un caz particular al detectiei muchiilor

▫ Ne asteptam ca derivata de ordin 2 sa ofere rezultate mai bune

▫ Produce linii mai subtiri decat derivata de ordin 1

▫ Daca un anumit punct din imagine satisface |Rk|>|Rj|, pentru j≠k, este foarte probabil ca acest punct sa fie asociat cu o linie

▫ Folositor pentru a detecta linii de grosime 1 pixel

▫ Cum detectam linii mai groase de 1 pixel? (derivata de ordin 1)

Imagine preluata:http://www.scribd.com/doc/16404926/Digital-Image-Processing-10-Image-Segmentation

Page 14: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS- Line detection

Imagine preluata:http://www.scribd.com/doc/16404926/Digital-Image-Processing-10-Image-Segmentation

Page 15: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (4)• Detectia punctelor:

▫ Reprezinta un caz particular al detectiei muchiilor

▫ Consideram cazul punctelor izolate

▫ Utilizam derivata de ordinul 2

▫ Se recomanda utilizarea filtrului Laplacian si binarizare dupa detectie

Imagine preluata:http://cs.joensuu.fi/pages/koles/image/Segmentation.pdf

Page 16: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (5)

• Pentru a putea detecta schimbarile de intensitate in toate directiile se foloseste un detector de muchii isotropic

• Laplacian – pentru detectia muchiilor

Pune la dispozitie un operator isotropic

Implementarea este mai putin costisitoare -> o singura masca

Nu ofera informatii despre directia muchiilor

Foarte sensibil la zgomote

Mask:

Page 17: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS – Laplacian (2)• Laplacian of Gaussian (LoG)

▫ Pentru a reduce efectul zgomotelor imaginea este intai nivelata cu un filtru low-pass

▫ Pentru LoG filtrul low-pass este:

σ controleaza nivelarea

Page 18: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS – Laplacian (3)

Page 19: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (6)

Consideram ca o muchie este mai puternica (“strong” edge) dacacontrastul local al imaginii de-a lungul normalei este mai mare, in caz contrar spuneam ca este slaba (“weak” edge)

Consideram magnitudinea:

,deoarece radicalul esteo operatie costisitoare, unde

Scop: conectarea muchiilor pentru a obtine conturul obiectelor

Abordari: Relaxarea muchiilor

Edge linking: determinarea marginilor

Hysteresis thresholding

Transformata Hough

Page 20: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (7)

• Edge relaxation (relaxarea muchiilor)▫ Considera nu numai magnitudinea si adiacenta ci si contextul:

O muchie slaba (“weak” edge) pozitionata intre doua muchii puternice (“strong edge”) este posibil sa apartina aceleiasi margini

Muchiile izolate nu sunt sustinute de un context ceea ce inseamna ca nu apartin nici unei margini

Contextul in care sunt pozitionate muchiile este considerat la ambele capete

Vecinatatea unei muchii este diferita de vecinatatea unui pixel:

Page 21: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (8)

Page 22: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (9)

• Edge linking:▫ Doua proprietati principale sunt folosite pentru a stabili

similaritatea dintre pixelii de pe muchii: Valoarea raspunsului operatorului gradient folosit pentru a obtine

pixelii de pe muchii

Directia gradientului

▫ Pasii de baza ai algoritmului: Fiecare punct (s,t) de pe o muchie este procesat in comparatie cu

un punct original (x,y)

Un punct de pe o muchie va fi legat de un alt punct ce apartine unei muchii din vecinatatea sa daca cele doua criterii de mai jos sunt satisfacute (exprimate partial si mai sus):

si unde E este un prag pozitiv pentru magnitudine; A este un

prag pozitiv pentru unghiul format de doua directii

Page 23: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (10)

Page 24: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (11)

Page 25: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (12) Hysteresis thresholding

▫ Suprimarea punctelor false de maxim:

▫ fie a1 si a2 doua puncte calculate prin interporale liniara

▫ pentru fiecare punct p se verifica

daca conditiile nu sunt verificate acesta

e suprimat (setat la 0)

▫ Imaginea obtinuta in urma aceste procesari inca maicontine puncte de maxim local datorat zgomotelor

Page 26: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (13)

• O schema efectiva in continuare este utilizarea a doua praguri▫ un prag mic tl

▫ un prag ridicat th (de obicei th=2*tl)

• Algoritm▫ Se produc doua imagini binare obtinute cu cele doua

praguri: obtinuta cu tl si obtinuta cu th

▫ Se leaga muchiile din in contururi:

Se uita in cand o zona lipsa este gasita

Examinand cei 8 vecini in , aduna puncte de pe muchie din pana cand peste zona lipsa se traseaza o legatura pana la o muchie in

Page 27: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (14)

Page 28: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

Edge-based segmentation (15)• Transformata Hough

▫ Ecuatia unei linii are forma:

▫ Considerand punctul transformata Hough pentru acest punct este

▫ Se genereaza un set de linii

cmxy

iiii ymxccmxy

cmxy

),( ii yx

y

xImage Space

m

c

),( cm

Parameter Space

Page 29: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS – Hough (2)• Ecuatia liniei in coordonate polare:

▫ unde

▫ dorim ca avand sa determinam

▫ rezulta ca transformata Hough pentru un punct este o sinusoida

• Fiecare posibilitate (linie/sinusoidala) care trece printr-un punct ce se afla pe o muchieeste adaugata intr-un acumulator (2D)

),( ii yx

y

xImage Space

Hough Space

0sincos yx

max0

20

),(

sincos yx

Page 30: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS – Hough (3)

• Algoritm

▫ Gasim toate muchiile din imagine

▫ Pentru fiecare punct xi de pe o muchie

Pentru fiecare posibilitate (linie/sinusoidala) pj din acumulator care trece prin xi Se incrementeaza pozitia in acumulator

Se cauta maximele din acumulator

Daca se doreste se mapeaza fiecare maxim din acumulator inapoi in spatiul imagine

Page 31: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS – Hough (4)

Page 32: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS – Hough (5)

• Transformata Hough pentru cercuri:

▫ Ecuatia cercului:

▫ Avem trei parametri: centrul si raza r

▫ Doar doi parametri daca raza cercului este cunoscuta

▫ Acumulatorul aici este 3D (3 parametri)

222 )()( rbyax ii

Page 33: AEACD 16. Segmentarea imaginilor: Edge-based segmentationandrei.clubcisco.ro/cursuri/f/f-sym/5master/analiza-extragerea-continutului/16... · Puncte Linii Muchii •Diferenta dintre

EBS – Hough (6)