1 Filtro di smoothing Gaussiano Appartengono a questa categoria i filtri lineari di smoothing che...

1

Filtro di smoothing GaussianoAppartengono a questa categoria i filtri lineari di smoothing che definiscono i coefficienti della maschera di convoluzione in accordo alla funzione gaussiana.

Tali filtri si dimostrano molto efficaci per attenuare il rumore di tipo gaussiano presente nell’immagine.

La funzione di trasferimento h(l,k) modellata dalla funzione gaussiana discreta con media zero e` data da:

h l k cel k

( , )( )

2 2

22

c fattore di normalizzazione che per semplicità` si assume uguale a 1

2

Filtro di smoothing Gaussiano

è l’unico parametro che modella la funzione di trasferimento e definisce l’area di influenza del filtro gaussiano

Il peso dei coefficienti della maschera è inversamente proporzionale alla distanza dei pixel rispetto a quello centrale (i pixel a distanza maggiore di circa 3 non avranno nessuna influenza per il filtraggio).

3


Proprieta` del filtro gaussiano

• Simmetria circolare• Monotono decrescente (nel dominio spaziale e delle frequenze) • Separabile.

SIMMETRIA CIRCOLARE

Il filtro Gaussiano esegue l’operazione di smoothing in modo identico in tutte le direzioni.

Da cio` consegue che il filtro opera in maniera indipendente dall’orientazione delle strutture presenti nell’immagine. Questa proprietà è dimostrata convertendo le coordinate cartesiane (l,k) in coordinate polari (r, ) nella funzione Gaussiana

Dove il raggio polare è r2=l2+k2

h r cer

( , )

2

22

4


Proprieta’ del filtro nel domino delle frequenze

5


Proprieta’ di separabilita` del filtro gaussiano

Siano h(i,j) e f(i,j) rispettivamente la funzione di trasferimento e l’immagine da filtrare, segue:

l k

kjlifklhjifjihjig ),(),(),(*),(),(

l k

kl

kjlife ),(2

22

2

)(

),(

2

2

2

2

22 kjlifeek

k

l

l

6


Proprieta’ di separabilita` del filtro gaussiano

I passi essenziali sono cosi riassunti:

1. Eseguire la convoluzione con maschera orizzontale e salva il risultato in modo trasposto rispetto all’inizio. (Convoluzione orizzontale)

2. Eseguire la convoluzione con la stessa maschera orizzontale. (Convoluzione verticale)

3. Eseguire la trasposizione dell’immagine per riportarla nella posizione originale.(Immagine filtrata)

7


FILTRO GAUSSIANO DISCRETO

I coefficienti della maschera di convoluzione sono calcolati analiticamente considerando la funzione di distribuzione gaussiana:

E` noto che gli effetti del filtro sono controllati dai valori della varianza 2 e dalle dimensioni della maschera L×L.

Per una maschera 7x7, varianza 2=2 e normalizzando il valore massimo del picco uguale ad 1 nella posizione centrale (0,0) della maschera, i valori discreti prodotti da tale equazione sono:

h i j kei j

( , )

2 2

22

8



In molti sistemi di elaborazione immagine e` comodo considerare i coefficienti del filtro con valori interi. Per tale scopo si calcola un adeguato valore della costante k

Se si vuole far corrispondere una valore minimo (per esempio 1) ai vertici della maschera ed un valore massimo k in corrispondenza del coefficiente centrale, si ha:

knuovovalore h

valoreattuale hN

min ( , )

_ ( , ) .

3 3

3 3

1

0 01191

9



Con questi nuovi valori dei coefficienti, e` necessario normalizzare i valori della funzione di convoluzione con una costante , ossia

g i j h i j f i j( , ) ( , ) * ( , )

1

1

11153

3

3

3

/ ( , )h i jji

10

Estrazione dei bordiEdging

11

L’operazione di estrazione degli Edge di una immagine risulta ancora oggi essere una operazione fondamentale per l’analisi delle immagini

In questo capitolo, saranno descritti gli algoritmi più comuni per determinare i bordi conoperatori locali (Local Edge Detector - LED)

Tali algoritmi assegnano un valore di bordo a ciascun pixel ma nessuna informazione è generata per legare insieme i vari pixel di bordo (Link Edge) per formare segmenti di bordo

Gli algoritmi LED sono Operatori Locali che determinano le variazioni locali dei valori di livello di grigio dell’immagine oppure le variazioni locali della derivata prima della funzione intensità.

Tali discontinuità locali nelle vicinanze dei bordi possono essere di vario tipo.

12

• Discontinuità a gradino (Step-Edge)• Discontinuità a linea• Discontinuità lineare (Ramp Edge)• Discontinuità lineare con salita e discesa (Roof Edge)

13

Gli algoritmi LED possono essere raggruppati nelle seguenti categorie:

• Operatori basati sulla differenziazione• Operatori basati sull'approssimazione del modello di Edge

14

Filtro Gradiente

Mentre i filtri di smoothing attenuano strutture in alta frequenza, quelli di edging devono esaltare le discontinuità

L’operatore che assolve a tale compito è l’operatore di derivata prima.

Per una immagine bidimensionale f(x,y), le derivate parziali prime f/x e f/y definiscono le discontinuita` dell’immagine nella direzione degli assi coordinati x e y

L’orientazione dei bordi nell’immagine non necessariamente coincide con gli assi coordinati. Da cio` consegue la necessita` di calcolare le derivate direzionali dell’immagine f per ogni punto (x,y) nella direzione r di massima discontinuita` dei livelli di grigio (massimo locale della derivata di f).

15

L’operatore che presenta queste caratteristiche e` il gradiente. Il gradiente di f(x,y) nel punto A nella generica direzione r con

angolo e` dato da:

sincosy

f

x

f

r

y

y

f

r

x

x

f

r

f

16

Siamo interessati a trovare il valore massimo

da cui

0cossin

y

f

x

f

r

f

)/arctan(),( xygmx ffyx

17

Viene d’ora un poi chiamato vettore gradiente il valore massimo della derivata (f/r)gmx nella direzione di massima variazione,

che in notazione differenziale e` definita da:

Una misura quantitativa della massima variazione di f nella direzione definita dal gradiente f e` dato dal modulo del vettore gradiente definito come

Il modulo e la direzione del gradiente sono indipendenti dalle coordinate (x,y) del sistema di riferimento.

jy

fi

x

ffGradf

f f fx y2 2

18

Per ridurre la complessita` computazionale il modulo del gradiente puo` essere approssimato considerando i valori assoluti:

oppure

Il modulo |f| e la direzione gmx del gradiente sono indipendenti

dalla scelta del sistema di riferimento, ossia sono invarianti con la rotazione degli assi coordinati.

f f fx y

),max( yx fff

19

APPROSSIMAZIONE DEL FILTRO GRADIENTE

Per una immagine digitale di dimensione NN, il vettore gradiente può essere approssimato sostituendo la differenziazione in due direzioni ortogonali lungo i rispettivi assi coordinati con le differenze finite sempre nelle rispettive direzioni x ed y.

Le seguenti approssimazioni sono date per le righe:

20

Queste approssimazioni conducono alle seguenti maschere di convoluzione h:

R e C identificano le maschere per le righe e le colonne. Il simbolo indica il pixel in elaborazione nel caso di maschere

asimmetriche I simboli (+, -, ed s) indicano maschere di convoluzione

calcolate rispettivamente con la differenza in avanti, all’indietro e simmetrica.

21

Il filtro simmetrico delle differenze si comporta come un filtro passa-basso e puo` essere pensato come la combinazione di un filtro di smoothing ed un filtro di esaltazione dei bordi:

La maschere di convoluzione orizzontale e verticale trovate sono utilizzate solo per l’estrazione dei bordi dominanti in direzione perpendicolare agli operatori stessi.

sh

1

0

1

2

1

1

1

2

1*

1

1*

1012

111

2

1*11*

1

1

CCCs

RRRs

Bhh

Bhh

22

Per tale scopo possono essere applicati i seguenti operatori di convoluzione:

g i j f i j h i j f i l h lR R Rl

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

1

1

g i j f i j h i j f l j h lC C Cl

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

1

1

23

Applicazione dei due filtri orizzontali e verticali

24

Riassumendo, l’estrazione dei bordi prevede diversi passi:

1. Filtraggio dell’immagine applicando in modo indipendente le maschere di convoluzione hR ed hC.

2. Calcolare il quadrato per ogni pixel delle due immagini ottenute al passo 1).

3. Somma i pixel omologhi delle due immagini del passo 2

4. Calcola la radice quadrata dell’immagine del passo 3. L’immagine risultante e` l’immagine degli Edge

5. Calcola l’arcotangente per ogni valore di gC/gR (conponenti

di gradiente orizzontale e verticale) calcolate nel passo 1). L’immagine risultante e` la mappa di orientazione dei bordi.

25

OPERATORE DI ROBERTS

Un modo alternativo per approssimare la differenziazione e` quello suggerito da Roberts:

Le maschere di convoluzione sono

f i j f i j f i jx ( , ) ( , ) ( , ) 1 1

f i j f i j f i jy ( , ) ( , ) ( , ) 1 1

x

y

f

fji arctan

4,

hR

1 0

0 1

hC

0 1

1 0

26

MANIPOLAZIONE DELL’IMMAGINE GRADIENTE

A questo punto, ottenuta l’immagine gradiente, vanno ricercati i bordi.

Alcune definizioni per verificare se un pixel è di bordo sono:

a)

b)

dove IT e` un valore di grigio da assegnare ai pixel classificati come bordi mediante la

soglia T come in precedenza

g i jf i j

f i j,

,

,

se f i j T

altrimenti

,

g i jI

f x y

T,

,

se f i j T

altrimenti

,

27

c)

dove IB e` un valore di grigio da assegnare ai pixel non classificati come bordi mediante

la soglia T. Separazione dei bordi dallo sfondo.

d)

g i j

f i j

IB,

,

se f i j T

altrimenti

,

g i jI

IT

B,

se f i j T

altrimenti

,

28

OPERATORE DI SOBEL

Gli operatori descritti basati sul gradiente generano bordi con spessore di almeno due pixel.

Per attenuare questi inconvenienti, l’operatore di Sobel esegue simultaneamente la differenziazione rispetto ad un asse coordinato e calcola una media locale in direzione ortogonale.

Le componenti del gradiente con l’operatore di Sobel sono calcolati nella direzione degli assi coordinati x ed y, coinvolgendo per ciascun pixel in elaborazione (i,j) i pixel nelle sue vicinanze incluse nella finestra 3x3 come mostrato in figura:

29

OPERATORE DI SOBEL

f i j C KD E A KH Gx ,

f i j A KB C G KF Ey , dove la costante K e` scelta uguale a 2 ed i pixel vicini a quello in elaborazione (i,j) hanno una influenza in relazione ai corrispondenti pesi indicati con A,B,..,E.

Scegliendo una finestra piu` grande 33 per la stima del gradiente, l’effetto di smoothing aumenta rispetto all’operatore con finestra 22, diminuendo in tal modo la sensibilità dell’operatore dalle fluttuazioni dei valori di intensità presenti nell’immagine

hR

1 0 1

2 0 2

1 0 1

hC

1 2 1

0 0 0

1 2 1

30

OPERATORE DI SOBEL

hR

1 0 1

2 0 2

1 0 1

hC

1 2 1

0 0 0

1 2 1

Le convoluzioni discrete per le componenti orizzontale e verticale dell’operatore di Sobel sono:

1

1

1

1

1

1

1

1

),(),(),(*),(),(

),(),(),(*),(),(

l lCCC

l kRRR

klhkjlifjihjifjig

klhkjlifjihjifjig

L’operatore di Sobel definisce il modello del gradiente con la nota formula:

f g gR C2 2

31

OPERATORE DI PREWITT

Differisce dall’operatore di Sobel solo per il valore della costante K che e` dimezzato ossia posta uguale a 1. In questo modo, le maschere di convoluzione diventano:

Diversamente dall’operatore di Sobel, i pixel piu` vicini (nord, sud, est, ovest) al pixel in elaborazione non hanno un peso maggiore ma contribuiscono alla stima del gradiente spaziale con lo stesso peso.

hR

1 0 1

1 0 1

1 0 1

hc

1 1 1

0 0 0

1 1 1

32

OPERATORE DI FREI&CHEN

Questo operatore assegna alla costante K il valore 2 pesando i pixel vicini in modo omogeneo ed in tal modo il valore del gradiente e` uguale in presenza di bordi verticali, orizzontali ed obliqui.

hC

1 2 1

0 0 0

1 2 1

hR

1 0 1

2 0 2

1 0 1

33

OPERATORI A CONFRONTO

34

OPERATORI A CONFRONTO

Il problema di mediare tra esaltazione delle alte frequenze per la ricerca dei bordi e l’attenuazione del rumore

La maschera di convoluzione combinata risulta la seguente:

Se si considerano le maschere hR(i,j) dell’operatore di Prewitt ed hSMOOTH(i,j)=1/9 il filtro

media di smoothing di 33, si ottiene la maschera di convoluzione combinata dell’operatore gradiente 55 nella forma:

h i j h i j hGRAD SMOOTH( , ) ( , ) *

11011

22022

33033

22022

11011

111

111

111

*

101

101

101

181

91

31

Rh

35

OPERATORE DERIVATA DELLA GAUSSIANA (DroG)

L’operatore gradiente basato sulla derivata della gaussiana e` ottenuto applicando prima l’operatore di smoothing gaussiano e successivamente derivando rispetto agli assi coordinati.

h i jie

ieR

i j i j

( , )

2 2

2

2 2

222

2

36

OPERATORE GRADIENTE DIREZIONALE

In diverse applicazioni è conveniente calcolare i bordi per un numero definito di direzioni

Questo può essere realizzato mediante la convoluzione dell’immagine di input f(i,j) con diverse maschere hk i cui pesi

modellano le risposte impulsive con gradiente direzionale.Il gradiente direzionale è espresso da

g i j f i j hk k( , ) ( , ) *dove hk è la risposta impulsiva del gradiente nella direzione

k k 2 4

dove k può assumere valori da 0 (per indicare la direzione nord) a 7

01

2

7

37


Le maschere di convoluzione corrispondenti alle k direzioni sono ottenute partendo con k=0 e ruotando in modo circolare di /4 ogni elemento esterno della maschera 33.

g i j g i jk

k( , ) max{ ( , )} k=0,...,7

38


39


• La somma dei pesi di ogni maschera è zero

• Consegue che nelle zone omogenee l’operatore sarà zero.

• Valore massimo si ha quando la configurazione dei livelli di grigio dei pixel meglio concordano con i modelli rappresentati dalle maschere.

• Altri operatori gradiente possono essere definiti con altre rotazioni: per esempio di /6 con maschere di dimensioni 55.

• Con maschere ancora più grandi si possono calcolare le direzioni dei bordi in modo più preciso con una buona riduzione del rumore ma con la necessità di notevole tempo di calcolo.

40

OPERATORE LAPLACIANO

Uso della derivata seconda per accentuare ulteriormente i bordi

Si usa l’operatore di Laplace così definito

22

2

2

2f x yf

x

f

y( , )

Applicare l’operatore Laplaciano ad una immagine f(i,j) per localizzare facilmente i pixel di bordo corrispondenti al pixel dove il fianco di salita o di discesa di 2f passa per lo zero (da positivo a negativo e viceversa).

Questa transizione di 2f per lo zero è chiamato anche zero crossing e corrisponde al pixel di bordo

41


Più sensibile al rumore rispetto agli altri operatori,

Non fornisce informazioni di direzione del bordo, e può generare doppi bordi

Nel dominio spaziale discreto, l’operatore laplaciano può essere approssimato considerando le differenze dei valori di intensità invece delle derivate.

La componente orizzontale dell’operatore laplaciano è approssimata come segue:

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

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

),()1,(

),()1,(2

2

jifjifjif

jifjifjifjifx

jif

x

jifx

jifjif

x

f

x

f X

differenza in avanti

42


2

2 1 2 1f

xf i j f i j f i j ( , ) ( , ) ( , )

Con la traslazione di un pixel in orizzontale, ottenuta sostituendo j con j-1 si calcola il valore approssimato del laplaciano nel punto (i,j) definito da:

operando in modo analogo per la componente verticale si ottiene:

2

2 1 2 1f

yf i j f i j f i j ( , ) ( , ) ( , )

Queste approssimazioni conducono alle corrispondenti maschere di convoluzione orizzontale e verticale:

hR 1 2 1 hC

1

2

1

h i j( , )

0 0 0

1 2 1

0 0 0

0 1 0

0 2 0

0 1 0

0 1 0

1 4 1

0 1 0

Dalla combinazione delle componenti orizzontali e verticali si ottiene una singola maschera di convoluzione del laplaciano:

43

LAPLACIANO DELLA GAUSSIANA

Marr ed Hildreth hanno definito un operatore per l’estrazione dei bordi, chiamato laplaciano della gaussiana (LOG) combinando l’effetto del filtro gaussiano (smoothing) con quello dell’operatore laplaciano (per esaltare i bordi).

g x y h x y f x y( , ) { ( , ) * ( , )}2

h x y ex y

( , )( )

2 2

22

g x y h x y f x y( , ) { ( , )}* ( , ) 2

44

LAPLACIANO DELLA GAUSSIANA

2

22

2

22

24

2222

)(22

log

2),(),(

yxyx

eyx

eyxhyxh

45

DIFFERENZA DI GAUSSIANE - DoG

Una buona approssimazione al filtro di Marr-Hildreth è ottenuto con un operatore basato sulla differenza di due Gaussiane con differente valore di :

dove

con A>B e 1<2

Marr ed Hildreth hanno trovato che con 2/1=1.6 si ha la migliore

approssimazione al filtro Laplaciano della Gaussiana

h r h r h rDoG G G( , , ) ( , ) ( , ) 1 2 1 2

h r AeG

r

( , ) 1

2

2

12

h r BeG

r

( , ) 2

2

2

22

46

DIFFERENZA DI GAUSSIANE - DoG

47

OPERATORE DI CANNY

La presenza di discontinuità nell’immagine, causate dalla fluttuazione dei sensori e dalla elettronica associata della telecamera, producono valori di gradiente anche in zone dell’immagine che dovevano essere omogenee (bordi sparsi ed artefatti).

Queste discontinuità dovute al rumore, possono non essere facilmente filtrate poichè spesso sono differenti rispetto alle caratteristiche del filtro

Un operatore che approssima la misura di gradiente per estrarre i bordi deve risolvere due caratteristiche contrapposte:

- attenuare il rumore- localizzare i bordi accuratamente quanto possibile.

48

OPERATORE DI CANNY

Se si esagera con la prima caratteritica, si hanno problemi nel localizzare i bordi in quanto il processo di smoothing può aggiungere incertezza sulla posizione del valore di massima discontinuità

Se si esagera con la seconda caratteristica, si ha l’inconveniente di aumentare la sensibilità dell’operatore ed estrarre bordi che in realtà sono da attribuire al rumore

Un operatore lineare basato sulla derivata prima della Gaussiana DroG risulta essere un buon compromesso tra localizzare i bordi e la non dipendenza del rumore

L’operatore di Canny è risultato essere ottimale per risolvere il compromesso tra la localizzazione accurata dei bordi e l’influenza dal rumore.

49

OPERATORE DI CANNY

Le caratteristiche dell’operatore di Canny sono

- Buona determinazione dei bordi, il rapporto segnale rumore (snr) del gradiente è massimizzato per ottenere la probabilità minore di errore nella determinazione di un bordo reale e di ottenere una probabilità minima nel considerare un falso bordo

- Buona localizzazione, punti identificati come bordi sono il più vicino possibile al centro del bordo reale

- Risposta singola, l’operatore dovrebbe produrre una unica risposta per uno stesso bordo

50

OPERATORE DI CANNY

Vediamo ora come possono essere descritte matematicamente le caratteristiche ottimali proposte da Canny

La prima e la seconda caratteristica può essere soddisfatta considerando l’operatore DroG, la Derivata della Gaussiana, come operatore che meglio approssima il rapporto segnale rumore e localizzazione

Primo passoIl primo passo dell’operatore di Canny è quello di convolvere l’immagine f(i,j) con un filtro

di smoothing Gaussiano h(i,j;) producendo una immagine g(i,j) data da:

dove controlla il livello di smoothing

Secondo passoSuccessivamente sono stimate le derivate parziali gx e gy, il modulo ed orientazione del

gradiente per ogni pixel (i,j) dell’immagine g.

g i j f i j h i j( , ) ( , ) * ( , ; )

51

OPERATORE DI CANNY

Le derivate parziali sono approssimate, usando per ogni pixel (i,j) finestre 22, e considerando le prime differenze:

Il modulo ed orientazione del gradiente sono calcolati dalle note formule:

g i j g i j g i j g i j g i jx ( , ) ( , ) ( , ) ( , ) ( , / 1 1 1 1 2

2/)1,1()1,(),1(),(),( jigjigjigjigjig y

M i j g gx y( , ) 2 2

),(

),(arctan),( jig

jigji

x

y

52

OPERATORE DI CANNY

Terzo passo

Siamo ora interessati a calcolare la posizione del bordo, la sua orientazione e possibilmente considerare anche il modulo del bordo in relazione al modulo del gradiente M(i,j).

Un modo per localizzare i punti di bordi potrebbe essere quello di considerare punti dell’immagine gradiente M(i,j) con valori alti

Questo approccio non risulterebbe robusto per identificare i bordi

poiché l’immagine gradiente ha l’effetto di accentuare le zone con discontinuità di livelli di grigio e conseguentemente nell’immagine gradiente M(i,j) il problema della localizzazione si ridurrebbe a trovare i punti di massimo locale.

53

OPERATORE DI CANNY

L’operatore di Marr-Hildreth localizza in corrispondenza degli zeri nella derivata seconda globale (ricordiamo che non fornisce la direzione del bordo in quanto è usato l’operatore laplaciano)

L’operatore di Canny invece, annulla la derivata seconda direzionale per trovare l’orientazione del gradiente e quindi la direzione ortogonale al bordo

Questo è espresso dalla equazione:

0sincos2

2

r

g

r

g

r

g yx

54

OPERATORE DI CANNY

La localizzazione dei bordi non risulta un compito molto semplice anche in presenza di bordi ben delineati perchè non sempre risulta con valore zero la derivata seconda dell’immagine smussata g

Una buona strategia può essere quella di considerare l’andamento dei pixel localmente per cercare i valori a zero della derivata seconda.

Si considera una finestra di dimensioni adeguate centrata sul pixel in elaborazione

55

OPERATORE DI CANNY

Quindi si cercano i massimi locali nell’immagine gradiente (modulo) nella direzione perpendicolare al bordo dove la derivata seconda direzionale è nulla

Questo processo è chiamato soppressione dei non massimi locali (non-maximal suppression-nms).

Tale processo assottiglia i picchi in M(i,j) ponendo a zero tutti i punti di M(i,j) lungo la direzione (i,j) del gradiente che non sono valori di picco.

),();,( ),( jijiMnmsjiN

56

OPERATORE DI CANNY

Quarto Passo

Riduzione dei frammenti dei falsi bordi presenti in N(i,j),

Tutti i valori di N(i,j) al di sotto di un certo valore di soglia sono impostati a zero

57

OPERATORE DI CANNY

I passi essenziali dell’operatore (algoritmo) di Canny sono così riassunti:

1-L’immagine originale f(i,j) è convoluta con il filtro Gaussiano h(i,j;) ottenendo l’immagine smussata g(i,j)

2-Calcola le seguenti informazioni (immagini) associate al gradiente per ciascun pixel dell’immagine smussata g(i,j):

-gx(i,j) derivata prima parziale (componente orizzontale)

-gy(i,j) derivata prima parziale (componente verticale)

-M(i,j) modulo del gradiente-(i,j) direzione del gradiente

3-Non-maximal suppression (NMS) all’immagine modulo del gradiente M(i,j) ottenendo come risultato l’immagine N(i,j)

58

OPERATORE DI CANNY

4-Attivare una procedura euristica che utilizza adeguate soglie per l’immagine N(i,j) allo scopo di attenuare la presenza di falsi bordi e di collegare contorni interrotti

5-Ripetere eventualmente i 4 passi precedenti con valori crescenti di k ottenendo le immagini di bordo N(i,j; k) per avere diversi

risultati dell’operatore di Canny

6-Possibilità di integrare i risultati conseguiti N(i,j; k) a diverse

scale in relazione al contesto applicativo.

1 Filtro di smoothing Gaussiano Appartengono a questa categoria i filtri lineari di smoothing che...

Documents

Transcript of 1 Filtro di smoothing Gaussiano Appartengono a questa categoria i filtri lineari di smoothing che...