Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Giovanni Mettivier » 8.Convoluzione e Correlazione


Convoluzione

Insieme con la correlazione, costituisce il legame essenziale tra il dominio spaziale e il dominio della frequenza, oltre che la base di molti algoritmi di image processing.
Date due funzioni continue 1D, f(x) e g(x), la loro convoluzione è definita da:

f(x)*g(x)= \int_{-infty}^{infty} f(\alpha)(x-\alpha)\,d\alpha

dove α è una variabile di comodo per l’integrazione.

Convoluzione (segue)

A titolo di esempio, consideriamo le due funzioni in figura.
Prima dell’integrazione, occorre costruire la g(x-α). A tal fine, bisogna ribaltare g(α) rispetto all’origine, in modo da ottenere g(-α), e quindi traslare la funzione così ottenuta di una quantità x.

A questo punto, per ciascun valore di x, f(α) deve essere moltiplicata per il corrispondente valore di g(x-α), ed infine il prodotto così ottenuto (area grigia nelle figure) deve essere integrato.

Passi del processo di convoluzione.

Passi del processo di convoluzione.


Convoluzione (segue)

Per x interno all’intervallo [0,1], il prodotto è 0 per a esterno all’intervallo [0,x]. Il risultato dell’integrazione è quindi x/2 per 0 ≤ x ≤ 1. Invece, per x interno all’intervallo [1,2], il risultato è 1 – x/2. Infine, il prodotto è 0 per x esterno all’intervallo [0,2].

Risultato della convoluzione delle funzioni definite precedentemente.

Risultato della convoluzione delle funzioni definite precedentemente.


Convoluzione (segue)

È importante analizzare il caso particolare della convoluzione di una f(x) con funzioni di tipo impulsivo.
L’impulso δ(x-x0) è definito dalla relazione:

f(x)*g(x)= \int_{-infty}^{infty} f(x) \delta(x-x_{0})\,dx = f(x_{0})

E può essere considerato come avente area unitaria in un intorno infinitesimo di x0 e area nulla altrove. Cioè:

\int_{-infty}^{infty} \delta(x-x_{0})\,dx = \int_{-x_{0}}^{+x_{0}}  \delta(x-x_{0})\,dx= 1

Si può dire pertanto che δ(x-x0) è localizzato in x = x0, e che l’ampiezza dell’impulso è determinata dal valore di f(x) in x = x0.

Convoluzione (segue)

Se per esempio f(x) = A, Aδ(x-x0) è un impulso di ampiezza A localizzato in x = x0.

Un esempio interessante di convoluzione è quella tra una funzione f(x) e un treno di impulsi. In questo caso, il risultato è la replica della f(x) nei punti di localizzazione degli impulsi.

Risultato della convoluzione tra una generica funzione f(x) ed un treno di impulsi.

Risultato della convoluzione tra una generica funzione f(x) ed un treno di impulsi.


Convoluzione Discreta

La convoluzione discreta di fe(x) e ge(x) è così definita:

f_{e}(x)*g_{e}(x)= \sum_{m=0}^{M-1} f_{e}(m)g_{e}(x-m)

per x = 0,1, …, M-1

Convoluzione 2D

Nel caso 2D, la convoluzione di due funzioni continue, f(x,y) e g(x,y), è definita come:
f(x,y)*g(x,y)=\int_{-infty}^{infty} \!\!\!\int_{-infty}^{infty} f(\alpha,\beta)g(x-\alpha, y-\beta)\,d\alpha\,d\beta

Convoluzione 2D Discreta

La formulazione della convoluzione 2D discreta assume che f(x,y) e g(x,y) siano due array discreti di dimensione A x B e C x D, rispettivamente.
La convoluzione 2D discreta di fe(x,y) e ge(x,y) è così definita:

f_{e}(x,y)*g_{e}(x,y)= \sum_{m=0}^{M-1} \sum_{n=0}^{M-1} f_{e}(m,n)g_{e}(x-m,y-n)

per x = 0, 1, …, M-1 e y = 0, 1, …, N-1

Convoluzione

Se effettuiamo la convoluzione tra una funzione rumorosa e un impulso rettangolare di larghezza finita, per ogni valore di x viene in pratica effettuate una media locale su un intervallo di ampiezza unitaria.

Questa operazione sopprime le oscillazioni rapide ovvero i dettagli, cioè le componenti di alta frequenza del segnale, mantenendone la forma, cioè le componenti di bassa frequenza.

Quindi possiamo considerare la g(x) come un filtro passa-basso: in pratica ha effettuato lo smoothing della funzione rumorosa.

Operazione di smoothing tramite convoluzione.

Operazione di smoothing tramite convoluzione.


Convoluzione

Consideriamo il caso in cui la f(x) rappresenta una transizione piuttosto lenta, tipicamente un contorno o un edge, e la g(x), invece, presenta un lobo centrale positivo e due laterali negativi.

Convoluzione.

Convoluzione.


Convoluzione

La convoluzione tra queste funzioni ha come risultato una funzione che mostra una pendenza maggiore di quella della f(x), con una evidenziazione delle componenti di alta frequenza del segnale, e una sovraelongazione (ringing) sui due lati dell’edge.
Quindi la g(x) ha il comportamento tipico di un filtro passa-alto: in pratica ha effettuato lo sharpening della f(x).

Operazione di sharpening tramite convoluzione.

Operazione di sharpening tramite convoluzione.


Convoluzione

La definizione di convoluzione discreta:

g(x,y) = f_{e}(x,y)*g_{e}(x,y)= \sum_{m=0}^{M-1} \sum_{n=0}^{M-1} f_{e}(m,n)g_{e}(x-m,y-n)

ricorda da vicino l’operazione di una maschera spaziale, la cui uscita in ogni punto dell’immagine, come è noto, vale:

R = w_{1}z_{1} + w_{1}z_{1} ... + w_{1}z_{1} = \sum_{i=1}^{9} w_{i}z_{i}

Convoluzione e Filtraggio

Infatti l’espressione ge(x-m, y-n) per ogni coppia di coordinate (x,y) in cui va calcolato il valore dell’uscita g, indica che rispetto agli assi m e n la h deve essere ribaltata e poi traslata di x posizioni lungo m e di y posizioni lungo n.
Successivamente i valori della f vengono moltiplicati per quelli della h ribaltata e traslata, e la loro somma così “pesata” contribuisce al valore dell’uscita g. Naturalmente si sommano solo i termini corrispondenti agli indici per i quali il prodotto è diverso da zero, per esempio nove per una maschera 3 x 3 per ogni coppia (x,y).

La sola differenza tra l’operazione di convoluzione e quella di filtraggio spaziale precedentemente definita sta nel fatto che quest’ultima non prevede il ribaltamento.

Correlazione

Date due funzioni continue 1D, f(x) e g(x), la loro correlazione è definita da (vedi figura) dove α è una variabile di comodo per l’integrazione e f* è la complessa coniugata di f.
La differenza con la convoluzione è che la g(x) non è ribaltata attorno all’origine. Pertanto il calcolo della correlazione richiede, per ciascun valore di x, solo lo scorrimento di g(x) rispetto a f(x) e l’integrazione del prodotto così ottenuto.

Correlazione.

Correlazione.


Correlazione Discreta


Correlazione

Le due operazioni coincidono se la maschera è simmetrica rispetto al suo punto centrale, come avviene per la maggior parte dei filtri adoperati per il miglioramento della qualità.
Per i motivi suddetti le maschere spaziali sono anche dette maschere di convoluzione.

Convoluzione

La convoluzione può essere effettuata utilizzando i seguenti metodi:

  1. Trasformazione con finestra mobile;
  2. Shift multiply add.;
  3. Trasformata di Fourier.

Finestra Mobile

L’oggetto w(s,t) è una matrice rettangolare di numeri.

La matrice è la finestra mobile.

Il pixel (x,y) nell’immagine di output è la somma pesata dei pixel dell’immagine originale nell’intorno di (x, y) indicati dalla matrice.

Ogni pixel nell’intorno di (x, y) è moltiplicato per il corrispondente valore della matrice — dopo che la matrice è stata ruotata di 180º.

La somma di questi prodotti è il valore del pixel (x, y) nell’immagine di output.

Formula: Finestra mobile.

Formula: Finestra mobile.

Esempio del processo di trasformazione con finestra mobile.

Esempio del processo di trasformazione con finestra mobile.


Finetrsa Mobile (segue)

Risultato di un filtraggio con una matrice 9×9.

Risultato di un filtraggio con una matrice 9x9.


Shift-Multiply-Add

L’immagine è copiata 1 volta per ogni elemento della maschera di convoluzione.

Ogni copia è shiftata rispetto all’originale per lo spostamento associato all’elemento della maschera.

Ogni copia è moltiplicata per il valore del suo elemento della maschera associato.

L’insieme delle immagini shiftate e moltiplicate è sommato pixel per pixel.

Shift-Multiply-Add

Se si moltiplica l’immagine per una funzione delta si ottiene una immagine shiftata.

Se si moltiplica l'immagine per una funzione delta si ottiene una immagine shiftata.


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion