111111111 ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡= K Appendice A

⎥

⎥

⎥

⎦

⎤

⎢

⎢

⎢

⎣

⎡

=

1

1

1

1

1

1

1

1

1

K

Appendice

A

Definizioni:

Kernel (Nucleo): E’ una matrice di numeri di ridotte dimensioni che viene utilizzata nelle convoluzioni di immagini. Kernel di dimensioni diverse e contenenti diversi pattern di numeri danno luogo a risultati differenti in convoluzione. Ad esempio:

è un Kernel per un filtro mediatore con un “vicinato” 3x3.

Spesso viene utilizzato un Kernel 3x3, anche se Kernel più grossi (tipo 5x5) possono essere utilizzati per uno smoothing più efficace. Talvolta un kernel più piccolo può essere applicato più di una volta per produrre un effetto simile ma non identico a quello che si avrebbe se si utilizzasse un unico filtro più grande.

vicino. L’idea è quella di sostituire ciascun valore dei pixel in un immagine con il valor medio dei suoi vicini, incluso se stesso. Questo ha l’effetto di eliminare i valori dei pixel che non sono rappresentativi delle regioni vicine. Come gli altri filtri di convoluzione è basato su un nucleo, kernel, che rappresenta la forma e le dimensioni del “vicinato” che viene campionato quando si calcola la media.

Spesso viene utilizzato un kernel quadrato 3x3, del tipo:

⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ = 9 / 1 9 / 1 9 / 1 9 / 1 9 / 1 9 / 1 9 / 1 9 / 1 9 / 1 K

Calcolare la convoluzione in avanti di un immagine con un kernel di questo tipo dà luogo all’operazione di filtraggio in media.

Convoluzione: E’ una operazione matematica, fondamentale in molti

operatori che processano le immagini in Computer Vision. E’ un modo per “moltiplicare” insieme due diversi vettori di numeri, generalmente di dimensioni diverse ma nello stesso spazio per produrne un terzo nel medesimo spazio. Nell’ambito della Computer Vision, uno dei due array è in genere una immagine a livelli di grigio, il secondo è invece un array di dimensioni più piccole, chiamato kernel, come mostrato in fig.A1

La convoluzione si esegue facendo scorrere il kernel sull’immagine, iniziando dall’angolo in alto a sinistra, in modo da muovere il kernel attraverso tutte le posizioni dove il kernel sta per intero dentro i controrno dell’immagine. Ciascuna posizione del kernel corrisponde ad un singolo valore in uscita, il cui valore si ottiene moltiplicando insieme i valori del kernel e quelli dei pixel dell’immagine sottostante, per ciascuna delle celle del kernel e quindi sommando insieme i prodotti ottenuti. Ad esempio per l’esempio riportato nella figura precedente, il valore del pixel in basso a destra della immagine ottenuta dalla convoluzione è dato da:

23 69 22 68 21 67 13 59 12 58 11 57 57

I

K

I

K

I

K

I

K

I

K

I

K

O

=

+

+

+

+

+

Se l’immagine ha M righe e N colonne e il kernel ha m righe e n colonne, allora le dimensioni dell’immagine ottenuta dalla convoluzione avrà: M-m+1 righe e N-n+1 colonne. La formula che esprime la convoluzione risulta:

∑∑

=

I

K

O

dove Oi,j esprime la immagine prodotta come risultato.

In alcune implementazioni, la convoluzione produce una immagine d’output più grande di questa, perché viene rimosso il vincolo che il kernel si possa muovere su posizioni dove è contenuto per intero nell’immagine e il kernel scorre su tutte le posizioni per cui anche il solo angolo sinistro del kernel risulti sopra l’immagine. Dunque il kernel si sovrappone all’immagine sopra il bordo destro e sinistro dell’immagine. In questo modo l’immagine finale ha le stesse dimensioni dell’immagine iniziale. In questo caso, tuttavia, per calcolare i pixel dell’angolo sinistro e destro dell’immagine finale è necessario inventare i pixel dell’immagine di partenza per le celle in cui il Kernel si estende fuori dell’immagine di partenza. Tipicamente vengono scelti valori per i pixel pari a 0 per le regioni fuori dell’immagine, anche se questo può distorcere l’immagine finale in quei punti. In questi

casi conviene rimuovere n-1 pixel dal lato destro e m-1 pixel dal basso dell’immagine.

Operatore di smoothing Gaussiano: L’operatore di smoothing

Gaussiano è un operatore di convoluzione 2D che viene utilizzato per “confondere” (blurring) le immagini e rimuoverne i dettagli e il rumore. In questo senso è simile a un filtro mediatore, rispetto al quale utilizza un diverso nucleo (kernel) che rappresenta la forma di una “gobba” Gaussiana. L’idea è quella di utilizzare la distribuzione Gaussiana 2D:

) 2 /( ) ( 2 2 2 2

2

1

)

,

,

(

πσ

σ

e

y

x

G

=

come una funzione di “distribuzione di punti”. Dato che l’immagine è una collezione di pixel discreti, è necessario utilizzare una approssimazione della funzione Gaussiana prima di calcolarne la convoluzione. In teoria una distribuzione Gaussiana è non-nulla ovunque, ma questo richiederebbe un nucleo di convoluzione Gaussiano infinitamente largo, ma in pratica è quasi nulla oltre a distanza tre volte il valore della deviazione standard rispetto alla media, perciò si può troncare il kernel a questo punto. Un esempio di Kernel di convoluzione Gaussiano a valori interi, che approssima una funzione Gaussiana con σ=1 è:

⎥

⎥

⎥

⎥

⎥

⎥

⎦

⎤

⎢

⎢

⎢

⎢

⎢

⎢

⎣

⎡

=

1

4

7

4

1

4

16

26

16

4

7

26

41

26

7

4

16

26

16

4

1

4

7

4

1

273

1

K

Una volta che un kernel adatto è stato calcolato, allora lo smoothing gaussiano può essere realizzato attraverso metodi di convoluzione. La convoluzione può essere calcolata velocemente dato che l’equazione per la funzione Gaussiana isotropica 2D mostrata è separabile nelle componenti

convoluzione con una funzione Gaussiana a 1D nella direzione x e con una convoluzione con una funzione Gaussiana a 1D nella direzione y. Infatti, l’operatore Gaussiano è infatti il solo operatore simmetrico completamente circolare che può essere scomposto in questo modo. Ad esempio la componente x a 1D del kernel che determina il kernel 2D proposto poco sopra risulta:

[

.

006

0

.

061

0

.

242

0

.

383

0

.

242

0

.

061

0

.

006

]

=

x

K

La componente y è la stessa ma orientata verticalmente. Usando le due componenti si può calcolare la convoluzione più velocemente.

Una delle giustificazioni principali per usare la funzione Gaussiana come smoothing filter è dovuta alla risposta in frequenza. Molti filtri basati sulla convoluzione si comportano come filtri in frequenza passabasso. Essi rimuovono le alte componenti spaziali di un’immagine. La risposta in frequenza di un filtro di convoluzione può essere calcolata considerando la Trasformata di Fourier del filtro.

L’operatore Gaussiano non solo ha utilità in applicazioni ingegneristiche. Sembra infatti che alcune cellule nelle vie visuali del cervello spesso hanno una risposta approssimativamente Gaussiana. La figura 6 mostra le risposte in frequenza di un filtro mediatore con larghezza 7 e di un filtro Gaussiano con σ=3.

Da una parte, entrambi i filtri attenuano le alte frequenze più che le basse, ma il filtro mediatore mostra delle oscillazioni nella sua risposta in frequenza. Dall’altra parte il filtro Gaussiano non presenta oscillazioni. Infatti la curva della risposta in frequenza è essa stessa metà di una Gaussiana. Quindi scegliendo in modo appropriato la dimensione del filtro Gaussiano è possibile essere abbastanza sicuri sul range di frequenze spaziali ancora presenti nell’immagine dopo il filtraggio, il chè non è il caso del filtro mediatore.

Scale-Space: Si intende una famiglia di segnali derivati, usati per rappresentare il segnale originale (nel nostro caso l’immagine) a vari livelli di scala. A ciascun membro della famiglia viene associato un valore che esprime il corrente parametro di scala. Il requisito essenziale è che un segnale (un’immagine) a livello più alto (coarse) di scala deve contenere meno strutture che un segnale (un’immagine) a livello più basso (fine) di scala. Se si guardasse il numero di estremi locali come misura della

smoothness è necessario che il numero di estrami locali nello spazio non

aumenti se si passa da un livello di scala più basso a uno più alto. Si può dimostrare che la famiglia di funzioni generate dalla convoluzione con un Kernel Gaussiano possiede queste proprietà nel caso continuo.