Convoluzione 2D nell’elaborazione delle immagini

Questo articolo fornisce informazioni sulla convoluzione bidimensionale e sullo zero-padding rispetto all’elaborazione digitale delle immagini.

Nel mio precedente articolo “Better Insight into DSP: Learning about Convolution”, ho discusso la convoluzione e le sue due importanti applicazioni nel campo dell’elaborazione dei segnali. Lì, i segnali erano presumibilmente considerati unidimensionali nel dominio spaziale. Tuttavia, il processo di convoluzione può essere portato avanti anche su segnali multidimensionali.

In questo articolo, cercheremo di capire meglio il processo e le conseguenze della convoluzione bidimensionale, usata ampiamente nel campo dell’elaborazione delle immagini.

La definizione di convoluzione 2D

La convoluzione che coinvolge segnali unidimensionali viene chiamata convoluzione 1D o semplicemente convoluzione. Altrimenti, se la convoluzione viene eseguita tra due segnali che si estendono lungo due dimensioni reciprocamente perpendicolari (cioè, se i segnali sono di natura bidimensionale), allora si parla di convoluzione 2D. Questo concetto può essere esteso per coinvolgere segnali multidimensionali, per cui possiamo avere una convoluzione multidimensionale.

Nel dominio digitale, la convoluzione viene eseguita moltiplicando e accumulando i valori istantanei dei campioni sovrapposti corrispondenti a due segnali di ingresso, uno dei quali viene capovolto. Questa definizione di convoluzione 1D è applicabile anche alla convoluzione 2D, tranne che, in quest’ultimo caso, uno degli ingressi è capovolto due volte.

Questo tipo di operazione è ampiamente utilizzato nel campo dell’elaborazione digitale delle immagini, dove la matrice 2D che rappresenta l’immagine sarà convoluta con una matrice relativamente più piccola chiamata kernel 2D.

Un esempio di convoluzione 2D

Proviamo a calcolare il valore del pixel dell’immagine in uscita risultante dalla convoluzione della matrice immagine x di dimensioni 5×5 con il kernel h di dimensioni 3×3, mostrato di seguito nella figura 1.

Figura 1: Matrici di input, dove x rappresenta l’immagine originale e h rappresenta il kernel. Immagine creata da Sneha H.L.

Per realizzare ciò, la procedura passo per passo da seguire è delineata qui sotto.

Passo 1: Inversione della matrice

Questo passo comporta il capovolgimento del kernel lungo, diciamo, le righe seguito da un capovolgimento lungo le colonne, come mostrato nella figura 2.

Figura 2: Rappresentazione grafica dell’inversione di matrice. Immagine creata da Sneha H.L.

Come risultato, ogni elemento (i,j)° del kernel originale diventa l’elemento (j,i)° della nuova matrice.

Passo 2: Far scorrere il kernel sull’immagine ed eseguire l’operazione MAC ad ogni istante

Sovrapporre il kernel invertito sull’immagine, avanzando pixel per pixel.

Per ogni caso, calcolare il prodotto dei pixel che si sovrappongono e calcolare la loro somma. Il risultato sarà il valore del pixel di uscita in quella particolare posizione. Per questo esempio, si assumerà che i pixel non sovrapposti abbiano un valore di ‘0’. Ne discuteremo più in dettaglio nella prossima sezione su “Zero Padding”.

Nel presente esempio, inizieremo a far scorrere il kernel prima in senso di colonna e poi avanzeremo lungo le righe.

Pixel riga per riga

Prima, copriamo completamente la prima riga e poi avanziamo alla seconda, e così via.

Durante questo processo, la prima sovrapposizione tra il kernel e i pixel dell’immagine risulterebbe quando il pixel in basso a destra del kernel cade sul valore del primo pixel in alto a sinistra della matrice dell’immagine. Entrambi questi valori di pixel sono evidenziati e mostrati in colore rosso scuro nella figura 3a. Quindi, il valore del primo pixel dell’immagine di uscita sarà 25 × 1 = 25.

In seguito, facciamo avanzare il kernel lungo la stessa riga di un solo pixel. A questo punto, due valori della matrice del kernel (0, 1 – mostrati nel carattere rosso scuro) si sovrappongono a due pixel dell’immagine (25 e 100 rappresentati nel carattere rosso scuro) come mostrato nella figura 3b. Quindi, il valore del pixel di uscita risultante sarà 25 × 0 + 100 × 1 = 100.

Figura 3a, 3b. Risultati della convoluzione ottenuti per i pixel di uscita nella posizione (1,1) e (1,2). Immagine creata da Sneha H.L.

Figura 3c, 3d: Risultati della convoluzione ottenuti per i pixel di uscita nelle posizioni (1,4) e (1,7). Immagine creata da Sneha H.L.

Avanzando in modo simile, tutti i valori dei pixel della prima fila nell’immagine di uscita possono essere calcolati. Due esempi di questo tipo corrispondenti al quarto e al settimo pixel della matrice di uscita sono mostrati nelle figure 3c e 3d, rispettivamente.

Se facciamo scorrere ulteriormente il kernel lungo la stessa riga, nessuno dei pixel del kernel si sovrappone a quelli dell’immagine. Questo indica che abbiamo finito lungo la riga attuale.

Spostamento verticale verso il basso, avanzamento orizzontale

Il prossimo passo sarebbe quello di avanzare verticalmente verso il basso di un singolo pixel prima di ricominciare a muoversi orizzontalmente. La prima sovrapposizione che si verificherebbe è quella mostrata nella figura 4a ed eseguendo l’operazione MAC su di esse; otteniamo il risultato come 25 × 0 + 50 × 1 = 50.

Dopo questo, possiamo far scorrere il kernel in direzione orizzontale fino a quando non ci sono più valori che si sovrappongono tra il kernel e le matrici dell’immagine. Uno di questi casi, corrispondente al sesto valore di pixel della matrice di uscita (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200) è mostrato nella figura 4b.

Figura 4a, 4b. Risultati della convoluzione ottenuti per i pixel di uscita nelle posizioni (2,1) e (2,6). Immagine creata da Sneha H.L.

Questo processo di spostamento di un passo verso il basso seguito dalla scansione orizzontale deve essere continuato fino all’ultima riga della matrice dell’immagine. Tre esempi casuali riguardanti i pixel di uscita nelle posizioni (4,3), (6,5) e (8,6) sono mostrati nelle figure 5a-c.

Figura 5a. Risultati della convoluzione ottenuti per i pixel di uscita a (4,3). Immagine creata da Sneha H.L.

Figura 5b. Risultati della convoluzione ottenuti per i pixel di uscita a (6,5). Immagine creata da Sneha H.L.

Figura 5c. Risultati della convoluzione ottenuti per i pixel di uscita a (8,6). Immagine creata da Sneha H.L.

Step

Quindi la matrice di uscita risultante sarà:

Figura 6. La matrice di uscita risultante del nostro esempio. Immagine creata da Sneha H.L.

Zero Padding

La formulazione matematica della convoluzione 2-D è data da

$$ y\left=somma_{m=-\infty}^\infty\sum_{n=-\infty}^\infty h\left \cdot x\left $$

dove, x rappresenta la matrice dell’immagine di ingresso da convolvere con la matrice del kernel h per ottenere una nuova matrice y, che rappresenta l’immagine di uscita. Qui, gli indici i e j riguardano le matrici dell’immagine mentre quelli di m e n si occupano di quella del kernel. Se la dimensione del kernel coinvolto nella convoluzione è 3 × 3, allora gli indici m e n vanno da -1 a 1. Per questo caso, un’espansione della formula presentata risulta in

$$ y\sum_{m=-\infty}^\infty h\cdot x\left + h\left \cdot x\left + h\left \cdot x\left $$

$$ y\left= h\left \cdot x\left + h\left \cdot x\left + h\cdot x\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left + h\left $$

Questo indica che per ottenere ogni pixel di uscita, devono essere eseguite 9 moltiplicazioni i cui fattori sono gli elementi dei pixel sovrapposti dell’immagine e del kernel. Tuttavia, mentre abbiamo calcolato il valore del nostro primo pixel di uscita, abbiamo eseguito una sola moltiplicazione (Figura 3a replicata come Figura 7a). Cosa significa questo? Implica un’incoerenza con la forma di equazione della convoluzione 2-D?

No, non proprio. Perché, il risultato ottenuto dalla somma di nove termini prodotto può essere uguale al prodotto di un solo termine se l’effetto collettivo degli altri otto termini prodotto è uguale a zero. Uno di questi modi è il caso in cui ogni prodotto degli altri otto termini si valuta a zero. Nel contesto del nostro esempio, questo significa che tutti i termini del prodotto corrispondenti ai pixel non sovrapposti (tra l’immagine e il kernel) devono diventare zero per rendere i risultati della formula di calcolo uguali a quelli del calcolo grafico.

Dalla nostra conoscenza elementare della matematica, sappiamo che se almeno uno dei fattori coinvolti nella moltiplicazione è zero, allora il prodotto risultante è anche zero. Con questa analogia, possiamo affermare che, nel nostro esempio, abbiamo bisogno di avere un pixel immagine a valore zero corrispondente a ogni pixel non sovrapposto della matrice del kernel. La rappresentazione pittorica di questo sarebbe quella mostrata nella figura 7b. Una cosa importante da notare qui è che tale aggiunta di zeri all’immagine non altera l’immagine in nessun senso eccetto la sua dimensione.

Figura 7: Zero-padding mostrato per il primo pixel dell’immagine (disegnato da me)

Questo processo di aggiunta di zeri extra è noto come zero padding ed è richiesto di essere fatto in ogni caso in cui non ci sono pixel dell’immagine che si sovrappongono ai pixel del kernel. Per il nostro esempio, lo zero padding richiede di essere effettuato per ogni pixel che si trova lungo le prime due righe e colonne e per quelli che appaiono lungo le ultime due righe e colonne (questi pixel sono mostrati in carattere blu nella figura 8). In generale, il numero di righe o colonne da riempire a zero su ogni lato dell’immagine di ingresso è dato da (numero di righe o colonne nel kernel – 1).

Figura 8

Una cosa importante da menzionare è il fatto che lo zero padding non è l’unico modo per trattare gli effetti dei bordi causati dalla convoluzione. Altre tecniche di imbottitura includono l’imbottitura replicata, l’estensione periodica, il mirroring, ecc. (Digital Image Processing Using Matlab 2E, Gonzalez, Tata McGraw-Hill Education, 2009).

Sommario

Questo articolo mira a spiegare il metodo grafico della convoluzione 2-D e il concetto di imbottitura zero rispetto all’elaborazione delle immagini digitali.