Convoluzione discreta multidimensionale - Multidimensional discrete convolution

Nell'elaborazione del segnale, multidimensionale convoluzione discreta riferisce alla operazione matematica tra due funzioni f e g su un n -dimensionale reticolo che produce una terza funzione, anche di n -dimensioni. La convoluzione discreta multidimensionale è l'analogo discreto della convoluzione multidimensionale di funzioni sullo spazio euclideo. È anche un caso speciale di convoluzione sui gruppi quando il gruppo è il gruppo di n -uple di interi.

Definizione

Dichiarazione del problema e nozioni di base

Simile al caso unidimensionale, viene utilizzato un asterisco per rappresentare l'operazione di convoluzione. Il numero di dimensioni nell'operazione data si riflette nel numero di asterischi. Ad esempio, una convoluzione M- dimensionale verrebbe scritta con M asterischi. Quanto segue rappresenta una convoluzione M -dimensionale di segnali discreti:

${\displaystyle y(n_{1},n_{2},...,n_{M})=x(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*h(n_{1},n_{2},...,n_{M})}$

Per i segnali a valori discreti, questa convoluzione può essere calcolata direttamente tramite quanto segue:

${\displaystyle \sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }...\sum _{k_{M} =-\infty }^{\infty }h(k_{1},k_{2},...,k_{M})x(n_{1}-k_{1},n_{2}-k_{ 2},...,n_{M}-k_{M})}$

La risultante regione di supporto di uscita di una convoluzione multidimensionale discreta sarà determinata in base alla dimensione e alle regioni di supporto dei due segnali di ingresso.

Sono elencate diverse proprietà dell'operatore di convoluzione bidimensionale. Si noti che questi possono essere estesi anche per segnali di -dimensioni. ${\displaystyle N}$

Proprietà commutativa:

${\displaystyle x**h=h**x}$

Proprietà associata:

${\displaystyle (x**h)**g=x**(h**g)}$

Proprietà distributiva:

${\displaystyle x**(h+g)=(x**h)+(x**g)}$

Queste proprietà sono viste in uso nella figura seguente. Dato un ingresso che va in un filtro con risposta all'impulso e poi un altro filtro con risposta all'impulso , l'uscita è data da . Supponiamo che l'output del primo filtro sia dato da , questo significa che: ${\displaystyle x(n_{1},n_{2})}$${\displaystyle h(n_{1},n_{2})}$${\displaystyle g(n_{1},n_{2})}$${\displaystyle y(n_{1},n_{2})}$${\displaystyle w(n_{1},n_{2})}$

${\displaystyle w=x**h}$

Inoltre, tale funzione intermedia è poi convoluta con la risposta all'impulso del secondo filtro, e quindi l'uscita può essere rappresentata da:

${\displaystyle y=w**g=(x**h)**g}$

Usando la proprietà associativa, questo può essere riscritto come segue:

${\displaystyle y=x**(h**g)}$

il che significa che la risposta all'impulso equivalente per un sistema in cascata è data da:

${\displaystyle h_{eq}=h**g}$

Un'analisi simile può essere eseguita su una serie di sistemi paralleli illustrati di seguito.

In questo caso è chiaro che:

${\displaystyle y=(x**h)+(x**g)}$

Utilizzando la legge distributiva, si dimostra che:

${\displaystyle y=x**(h+g)}$

Ciò significa che nel caso di un sistema parallelo, la risposta all'impulso equivalente è fornita da:

${\displaystyle h_{eq}=h+g}$

Le risposte all'impulso equivalenti sia nei sistemi in cascata che nei sistemi paralleli possono essere generalizzate a sistemi con -numero di filtri. ${\displaystyle N}$

Motivazione e applicazioni

La convoluzione in una dimensione è stata una scoperta potente che ha permesso di confrontare facilmente l'input e l'output di un sistema lineare shift-invariant (LSI) (vedi teoria del sistema LTI ) purché fosse nota la risposta all'impulso del sistema di filtri. Questa nozione si estende anche alla convoluzione multidimensionale, poiché anche la semplice conoscenza della risposta all'impulso di un filtro multidimensionale consente di effettuare un confronto diretto tra l'ingresso e l'uscita di un sistema. Questo è profondo poiché molti dei segnali che vengono trasferiti nel mondo digitale oggi sono di molteplici dimensioni, tra cui immagini e video. Simile alla convoluzione unidimensionale, la convoluzione multidimensionale consente il calcolo dell'uscita di un sistema LSI per un dato segnale di ingresso.

Ad esempio, si consideri un'immagine inviata su una rete wireless soggetta a rumore elettro-ottico. Le possibili fonti di rumore includono errori nella trasmissione del canale, il convertitore da analogico a digitale e il sensore di immagine. Di solito il rumore causato dal canale o dal sensore crea componenti del segnale ad alta frequenza spazialmente indipendenti che si traducono in punti chiari e scuri arbitrari sull'immagine reale. Al fine di liberare i dati dell'immagine dal contenuto spettrale ad alta frequenza, può essere moltiplicato per la risposta in frequenza di un filtro passa-basso, che in base al teorema di convoluzione, equivale a convolure il segnale nel dominio tempo/spaziale di la risposta all'impulso del filtro passa basso. Diverse risposte all'impulso che lo fanno sono mostrate di seguito.

Oltre a filtrare il contenuto spettrale, la convoluzione multidimensionale può implementare il rilevamento e il livellamento dei bordi. Anche questo dipende interamente dai valori della risposta all'impulso che viene utilizzata per convolure con l'immagine in ingresso. Di seguito sono illustrate le tipiche risposte all'impulso per il rilevamento dei bordi.

Oltre all'elaborazione delle immagini, è possibile implementare la convoluzione multidimensionale per consentire una varietà di altre applicazioni. Poiché i filtri sono molto diffusi nei sistemi di comunicazione digitale, qualsiasi sistema che deve trasmettere dati multidimensionali è assistito da tecniche di filtraggio. Viene utilizzato nell'elaborazione video in tempo reale, nell'analisi della rete neurale, nell'analisi dei dati geofisici digitali e molto altro.

Una tipica distorsione che si verifica durante le applicazioni di acquisizione o trasmissione di immagini e video è la sfocatura causata da un processo di filtraggio passa-basso. La sfocatura introdotta può essere modellata utilizzando il filtro passa-basso gaussiano.

Scomposizione riga-colonna con segnali separabili

Segnali separabili

Un segnale si dice separabile se può essere scritto come il prodotto di più segnali unidimensionali. Matematicamente, questo è espresso come segue:

${\displaystyle x(n_{1},n_{2},...,n_{M})=x(n_{1})x(n_{2})...x(n_{M})}$

Alcuni segnali separabili facilmente riconoscibili includono la funzione di passo unitario e la funzione di impulso dirac-delta.

${\displaystyle u(n_{1},n_{2},...,n_{M})=u(n_{1})u(n_{2})...u(n_{M})}$ (funzione passo unitario)

${\displaystyle \delta (n_{1},n_{2},...,n_{M})=\delta (n_{1})\delta (n_{2})...\delta (n_{ M})}$ (funzione di impulso dirac-delta)

La convoluzione è un'operazione lineare. Segue quindi che la convoluzione multidimensionale di segnali separabili può essere espressa come il prodotto di molte convoluzioni unidimensionali. Ad esempio, considera il caso in cui x e h sono entrambe funzioni separabili.

${\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h(k_{1},k_{2})x(n_{1}-k_{1},n_{2}-k_{2}) }$

Applicando le proprietà di separabilità, questa può essere riscritta come segue:

${\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})={\bigg (}\sum _{k_{1}=-\infty }^{ \infty }h(k_{1})x(n_{1}-k_{1}){\bigg )}{\bigg (}\sum _{k_{2}=-\infty }^{\infty } h(k_{2})x(n_{2}-k_{2}){\bigg )}}$

Si vede facilmente quindi che questo si riduce al prodotto di circonvoluzioni unidimensionali:

${\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})={\bigg [}x(n_{1})*h(n_{1}) {\bigg ]}{\bigg [}x(n_{2})*h(n_{2}){\bigg ]}}$

Questa conclusione può quindi essere estesa alla convoluzione di due segnali M -dimensionali separabili come segue:

${\displaystyle x(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*h(n_{1},n_{2},. ..,n_{M})={\bigg [}x(n_{1})*h(n_{1}){\bigg ]}{\bigg [}x(n_{2})*h(n_ {2}){\bigg ]}...{\bigg [}x(n_{M})*h(n_{M}){\bigg ]}}$

Quindi, quando i due segnali sono separabili, la convoluzione multidimensionale può essere calcolata calcolando convoluzioni unidimensionali. ${\displaystyle n_{M}}$

Scomposizione riga-colonna

Il metodo riga-colonna può essere applicato quando uno dei segnali nella convoluzione è separabile. Il metodo sfrutta le proprietà di separabilità per ottenere un metodo di calcolo della convoluzione di due segnali multidimensionali più efficiente dal punto di vista computazionale rispetto al calcolo diretto di ciascun campione (dato che uno dei segnali è separabile). Quanto segue mostra il ragionamento matematico dietro l'approccio di scomposizione riga-colonna (tipicamente è il segnale separabile): ${\displaystyle h(n_{1},n_{2})}$

${\displaystyle {\begin{aligned}y(n_{1},n_{2})&=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}= -\infty }^{\infty }h(k_{1},k_{2})x(n_{1}-k_{1},n_{2}-k_{2})\\&=\sum _ {k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h_{1}(k_{1})h_{2}(k_{ 2})x(n_{1}-k_{1},n_{2}-k_{2})\\&=\sum _{k_{1}=-\infty }^{\infty }h_{1 }(k_{1}){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1 },n_{2}-k_{2}){\Bigg ]}\end{allineato}}}$

Il valore di può ora essere riutilizzato quando si valutano altri valori con un valore condiviso di : ${\displaystyle \sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{ 2})}$${\displaystyle y}$${\displaystyle n_{2}}$

${\displaystyle {\begin{aligned}y(n_{1}+\delta ,n_{2})&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_ {1}){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-[k_{1}- \delta ],n_{2}-k_{2}){\Bigg ]}\\&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1} +\delta ){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_ {2}-k_{2}){\Bigg ]}\end{allineato}}}$

Pertanto, la convoluzione risultante può essere calcolata in modo efficace eseguendo prima l'operazione di convoluzione su tutte le righe di , e poi su tutte le sue colonne. Questo approccio può essere ulteriormente ottimizzato tenendo conto del modo in cui si accede alla memoria all'interno di un processore del computer. ${\displaystyle x(n_{1},n_{2})}$

Un processore caricherà i dati del segnale necessari per l'operazione data. Per i processori moderni, i dati verranno caricati dalla memoria nella cache dei processori, che ha tempi di accesso più rapidi rispetto alla memoria. La cache stessa è partizionata in righe. Quando una riga della cache viene caricata dalla memoria, vengono caricati più operandi di dati contemporaneamente. Considera il caso ottimizzato in cui una riga di dati del segnale può essere contenuta interamente nella cache del processore. Questo particolare processore sarebbe in grado di accedere ai dati in modo efficiente per riga, ma non per colonna poiché diversi operandi di dati nella stessa colonna si troverebbero su diverse linee di cache. Per trarre vantaggio dal modo in cui si accede alla memoria, è più efficiente trasporre il set di dati e quindi assestarlo per riga piuttosto che tentare di accedervi per colonna. L'algoritmo diventa quindi:

1. Separare il segnale bidimensionale separabile in due segnali unidimensionali e${\displaystyle h(n_{1},n_{2})}$${\displaystyle h_{1}(n_{1})}$${\displaystyle h_{2}(n_{2})}$
2. Eseguire la convoluzione per riga sulle componenti orizzontali del segnale usando per ottenere${\displaystyle x(n_{1},n_{2})}$${\displaystyle h_{1}(n_{1})}$${\displaystyle g(n_{1},n_{2})}$
3. Trasporre le componenti verticali del segnale risultante dal passaggio 2.${\displaystyle g(n_{1},n_{2})}$
4. Eseguire la convoluzione per righe sulle componenti verticali trasposte di per ottenere l'output desiderato${\displaystyle g(n_{1},n_{2})}$${\displaystyle y(n_{1},n_{2})}$

Accelerazione computazionale dalla scomposizione riga-colonna

Esaminare il caso in cui un'immagine di dimensioni viene passata attraverso un filtro di dimensioni separabile . L'immagine stessa non è separabile. Se il risultato viene calcolato utilizzando l'approccio della convoluzione diretta senza sfruttare la separabilità del filtro, ciò richiederà approssimativamente moltiplicazioni e addizioni. Se si tiene conto della separabilità del filtro, il filtraggio può essere eseguito in due fasi. Il primo passaggio avrà moltiplicazioni e addizioni e il secondo passaggio avrà , risultando in un totale di o moltiplicazioni e addizioni. Un confronto della complessità computazionale tra convoluzione diretta e separabile è riportato nell'immagine seguente: ${\displaystyle X\times Y}$${\displaystyle J\times K}$${\displaystyle XYJK}$${\displaystyle XYJ}$${\displaystyle XYK}$${\displaystyle XYJ+XYK}$${\displaystyle XY(J+K)}$

Convoluzione circolare di segnali multidimensionali a valori discreti

La premessa dietro l'approccio della convoluzione circolare sui segnali multidimensionali è sviluppare una relazione tra il teorema di convoluzione e la trasformata discreta di Fourier (DFT) che può essere utilizzata per calcolare la convoluzione tra due segnali di estensione finita e valori discreti.

Teorema di convoluzione in più dimensioni

Per i segnali unidimensionali, il teorema di convoluzione afferma che la trasformata di Fourier della convoluzione tra due segnali è uguale al prodotto delle trasformate di Fourier di quei due segnali. Pertanto, la convoluzione nel dominio del tempo è uguale alla moltiplicazione nel dominio della frequenza. Matematicamente, questo principio è espresso attraverso quanto segue:

Questo principio è direttamente estendibile per trattare segnali di più dimensioni.Questa proprietà è facilmente estesa all'uso con la trasformata discreta di Fourier (DFT) come segue (si noti che la convoluzione lineare è sostituita con la convoluzione circolare dove è usata per denotare l'operazione di convoluzione circolare di dimensione ): ${\displaystyle\otimes}$${\displaystyle N}$

${\displaystyle y(n)=h(n)\otimes x(n)\longleftrightarrow Y(k)=H(k)X(k)}$

Quando si tratta di segnali di più dimensioni:

Le circonvoluzioni circolari qui saranno di dimensioni . ${\displaystyle N_{1},N_{2},...,N_{M}}$

Approccio a convoluzione circolare

La motivazione alla base dell'utilizzo dell'approccio della convoluzione circolare è che si basa sul DFT. La premessa alla base della convoluzione circolare è prendere le DFT dei segnali di ingresso, moltiplicarle tra loro e quindi prendere la DFT inversa. È necessario prestare attenzione in modo che venga utilizzato un DFT sufficientemente grande in modo che non si verifichi l'aliasing. La DFT è calcolabile numericamente quando si tratta di segnali di estensione finita. Un vantaggio di questo approccio è che poiché richiede di prendere la DFT e la DFT inversa, è possibile utilizzare algoritmi efficienti come la trasformata di Fourier veloce (FFT). La convoluzione circolare può essere calcolata anche nel dominio tempo/spaziale e non solo nel dominio della frequenza.

Scelta della dimensione DFT per evitare l'aliasing

Si consideri il seguente caso in cui vengono presi due segnali di estensione finita x e h . Per entrambi i segnali esiste una DFT corrispondente come segue:

${\displaystyle x(n_{1},n_{2})\longleftrightarrow X(k_{1},k_{2})}$ e ${\displaystyle h(n_{1},n_{2})\longleftrightarrow H(k_{1},k_{2})}$

La regione di supporto di is e e la regione di supporto di is e . ${\displaystyle x(n_{1},n_{2})}$${\displaystyle 0\leq n_{1}\leq P_{1}-1}$${\displaystyle 0\leq n_{2}\leq P_{2}-1}$${\displaystyle h(n_{1},n_{2})}$${\displaystyle 0\leq n_{1}\leq Q_{1}-1}$${\displaystyle 0\leq n_{2}\leq Q_{2}-1}$

La convoluzione lineare di questi due segnali sarebbe data come:

Date le regioni di sostegno di e , la regione di sostegno di sarà quindi data come segue: ${\displaystyle x(n_{1},n_{2})}$${\displaystyle h(n_{1},n_{2})}$${\displaystyle y_{lineare}(n_{1},n_{2})}$

In base alle regioni di supporto dei due segnali, deve essere utilizzata una DFT di dimensione dove e poiché la stessa dimensione DFT deve essere utilizzata su entrambi i segnali. Nel caso in cui sia necessaria una dimensione DFT maggiore dell'estensione di un segnale, il segnale viene riempito di zero fino a raggiungere la lunghezza richiesta. Dopo aver moltiplicato le DFT e aver preso la DFT inversa sul risultato, la convoluzione circolare risultante è quindi data da: ${\displaystyle N_{1}\times N_{2}}$${\displaystyle N_{1}\geq \max(P_{1},Q_{1})}$${\displaystyle N_{2}\geq \max(P_{2},Q_{2})}$

${\displaystyle y_{circolare}(n_{1},n_{2})=\sum _{r_{1}}\sum _{r_{2}}{\Bigg [}\sum _{m_{1} =0}^{Q_{1}-1}\sum _{m_{2}=0}^{Q_{2}-1}h(m_{1},m_{2})x(n_{1} -m_{1}-r_{1}N_{1},n_{2}-m_{2}-r_{2}N_{2}){\Bigg ]}}$ per ${\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}$

${\displaystyle R_{N_{1}N_{2}}\triangleq \{(n_{1},n_{2}):0\leq n_{1}\leq N_{1}-1,0\leq n_ {2}\leq N_{2}-1\}}$

Il risultato sarà una versione con alias spaziale del risultato della convoluzione lineare . Questo può essere espresso come segue: ${\displaystyle y_{circolare}(n_{1},n_{2})}$${\displaystyle y_{lineare}(n_{1},n_{2})}$

${\displaystyle y_{circolare}(n_{1},n_{2})=\sum _{r_{1}}\sum _{r_{2}}y_{lineare}(n_{1}-r_{1 }N_{1},n_{2}-r_{2}N_{2}){\mathrm {\,\,\,per\,\,\,} }(n_{1},n_{2}) \in R_{N_{1}N_{2}}}$

Quindi, per evitare l'aliasing tra le repliche con alias spaziale, e deve essere scelto per soddisfare le seguenti condizioni: ${\displaystyle N_{1}}$${\displaystyle N_{2}}$

${\displaystyle N_{1}\geq P_{1}+Q_{1}-1}$

${\displaystyle N_{2}\geq P_{2}+Q_{2}-1}$

Se queste condizioni sono soddisfatte, i risultati della convoluzione circolare saranno uguali a quelli della convoluzione lineare (prendendo il periodo principale della convoluzione circolare come regione di supporto). Questo è:

${\displaystyle y_{circolare}(n_{1},n_{2})=y_{lineare}(n_{1},n_{2})}$ per ${\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}$

Riepilogo della procedura utilizzando DFT

Il teorema di convoluzione e la convoluzione circolare possono quindi essere utilizzati nel modo seguente per ottenere un risultato uguale all'esecuzione della convoluzione lineare:

1. Scegli e per soddisfare e${\displaystyle N_{1}}$${\displaystyle N_{2}}$${\displaystyle N_{1}\geq P_{1}+Q_{1}-1}$${\displaystyle N_{2}\geq P_{2}+Q_{2}-1}$
2. Zero pad i segnali e in modo che siano entrambi di dimensioni${\displaystyle h(n_{1},n_{2})}$${\displaystyle x(n_{1},n_{2})}$${\displaystyle N_{1}\times N_{2}}$
3. Calcola i DFT di entrambi e${\displaystyle h(n_{1},n_{2})}$${\displaystyle x(n_{1},n_{2})}$
4. Moltiplicare i risultati delle DFT da ottenere ${\displaystyle Y(k_{1},k_{2})=H(k_{1},k_{2})X(k_{1},k_{2})}$
5. Il risultato dell'IDFT di sarà quindi uguale al risultato dell'esecuzione della convoluzione lineare sui due segnali${\displaystyle Y(k_{1},k_{2})}$

Sovrapponi e aggiungi

Un altro metodo per eseguire la convoluzione multidimensionale è l' approccio di sovrapposizione e aggiunta . Questo metodo aiuta a ridurre la complessità computazionale spesso associata alle circonvoluzioni multidimensionali dovute alle grandi quantità di dati inerenti ai moderni sistemi digitali. Per brevità si prende come esempio il caso bidimensionale, ma gli stessi concetti possono essere estesi a più dimensioni.

Considera una convoluzione bidimensionale usando un calcolo diretto:

${\displaystyle y(n_{1},n_{2})=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\ infty }x(n_{1}-k_{1},n_{2}-k_{2})h(k_{1},k_{2})}$

Supponendo che il segnale di uscita abbia N coefficienti diversi da zero e che la risposta all'impulso abbia M campioni diversi da zero, questo calcolo diretto richiederebbe MN moltiplica e MN - 1 aggiunge per calcolare. Utilizzando invece una FFT, la risposta in frequenza del filtro e la trasformata di Fourier dell'ingresso dovrebbero essere memorizzate. Le enormi quantità di calcoli e l'uso eccessivo dello spazio di archiviazione della memoria pongono un problema problematico man mano che vengono aggiunte più dimensioni. È qui che entra in gioco il metodo di sovrapposizione e aggiunta di convoluzione. ${\displaystyle y(n_{1},n_{2})}$

Scomposizione in blocchi di convoluzione più piccoli

Invece di eseguire la convoluzione sui blocchi di informazioni nella loro interezza, le informazioni possono essere suddivise in blocchi più piccoli di dimensioni x risultando in FFT più piccole, meno complessità computazionale e meno spazio di archiviazione necessario. Questo può essere espresso matematicamente come segue: ${\displaystyle L_{1}}$${\displaystyle L_{2}}$

${\displaystyle x(n_{1},n_{2})=\sum _{i=1}^{P_{1}}\sum _{j=1}^{P_{2}}x_{ij} (n_{1},n_{2})}$

dove rappresenta il segnale di ingresso x , che è una sommatoria di segmenti di blocco, con e . ${\displaystyle x(n_{1},n_{2})}$${\displaystyle N_{1}}$${\displaystyle N_{2}}$${\displaystyle P_{1}P_{2}}$${\displaystyle P_{1}=N_{1}/L_{1}}$${\displaystyle P_{2}=N_{2}/L_{2}}$

Per produrre il segnale di uscita, viene eseguita una convoluzione bidimensionale:

${\displaystyle y(n_{1},n_{2})=x(n_{1},n_{2})**h(n_{1},n_{2})}$

Sostituendo i risultati in quanto segue: ${\displaystyle x(n_{1},n_{2})}$

${\displaystyle y(n_{1},n_{2})=\sum _{i=1}^{P_{1}}\sum _{j=1}^{P_{2}}x_{ij} (n_{1},n_{2})**h(n_{1},n_{2})}$

Questa convoluzione aggiunge più complessità rispetto a una convoluzione diretta; tuttavia, poiché è integrato con una convoluzione rapida FFT, l'aggiunta di sovrapposizione esegue più velocemente ed è un metodo più efficiente in termini di memoria, rendendolo pratico per grandi insiemi di dati multidimensionali.

Ripartizione della procedura

Sia di dimensioni : ${\displaystyle h(n_{1},n_{2})}$${\displaystyle M_{1}\times M_{2}}$

1. Suddividi l'input in blocchi di dimensioni non sovrapposti .${\displaystyle x(n_{1},n_{2})}$${\displaystyle L_{1}\times L_{2}}$
2. Zero pad in modo che abbia le dimensioni ( ) ( ).${\displaystyle h(n_{1},n_{2})}$${\displaystyle L_{1}+M_{1}-1}$${\displaystyle \times}$${\displaystyle L_{2}+M_{2}-1}$
3. Usa DFT per ottenere .${\displaystyle H(k_{1},k_{2})}$
4. Per ogni blocco di ingresso:
   1. Il punto zero deve essere di dimensioni ( ) ( ).${\displaystyle x_{ij}(n_{1},n_{2})}$${\displaystyle L_{1}+M_{1}-1}$${\displaystyle \times}$${\displaystyle L_{2}+M_{2}-1}$
   2. Prendi la trasformata di Fourier discreta di ogni blocco per dare .${\displaystyle X_{ij}(k_{1},k_{2})}$
   3. Moltiplicare per ottenere .${\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2})H(k_{1},k_{2})}$
   4. Prendi la trasformata di Fourier discreta inversa di per ottenere .${\displaystyle Y_{ij}(k_{1},k_{2})}$${\displaystyle y_{ij}(n_{1},n_{2})}$
5. Trova sovrapponendo e sommando gli ultimi campioni di con i primi campioni di per ottenere il risultato.${\displaystyle y(n_{1},n_{2})}$${\displaystyle (M_{1}-1)}$${\displaystyle \times}$ ${\displaystyle (M_{2}-1)}$${\displaystyle y_{ij}(n_{1},n_{2})}$${\displaystyle (M_{1}-1)}$ ${\displaystyle \times}$${\displaystyle (M_{2}-1)}$${\displaystyle y_{i+1,j+1}(n_{1},n_{2})}$

Metodo di funzionamento pittorico

Per visualizzare più chiaramente il metodo di sovrapposizione-aggiunta, le seguenti illustrazioni esaminano il metodo graficamente. Supponiamo che l'input abbia un supporto di una regione quadrata di lunghezza N in entrambe le direzioni verticale e orizzontale come mostrato nella figura sottostante. Viene quindi suddiviso in quattro segmenti più piccoli in modo tale da essere ora composto da quattro quadrati più piccoli. Ogni blocco del segnale aggregato ha dimensioni .${\displaystyle x(n_{1},n_{2})}$${\displaystyle (N/2)}$ ${\displaystyle \times}$ ${\displaystyle (N/2)}$

Quindi, ogni componente è convoluto con la risposta all'impulso del filtro. Si noti che un vantaggio per un'implementazione come questa può essere visualizzato qui poiché ciascuna di queste convoluzioni può essere parallelizzata su un computer, purché il computer abbia memoria e risorse sufficienti per archiviare e calcolare contemporaneamente.

Nella figura sottostante, il primo grafico a sinistra rappresenta la convoluzione corrispondente alla componente dell'ingresso con la corrispondente risposta all'impulso . A destra di questo, l'ingresso è quindi convoluto con la risposta all'impulso . ${\displaystyle x_{0,0}}$${\displaystyle h(n_{1},n_{2})}$${\displaystyle x_{1,0}}$${\displaystyle h(n_{1},n_{2})}$

Lo stesso processo viene eseguito rispettivamente per gli altri due input e vengono accumulati insieme per formare la convoluzione. Questo è raffigurato a sinistra.

Supponiamo che la risposta all'impulso del filtro abbia una regione di supporto in entrambe le dimensioni. Ciò comporta che ogni convolves convoluzione segnali con dimensioni sia e direzioni, che porta alla sovrapposizione (evidenziati in blu) poiché la lunghezza di ogni singola spira è equivalente a: ${\displaystyle h(n_{1},n_{2})}$${\displaystyle (N/8)}$${\displaystyle (N/2)}$ ${\displaystyle \times}$ ${\displaystyle (N/8)}$${\displaystyle n_{1}}$${\displaystyle n_{2}}$

${\displaystyle (N/2)}$ ${\displaystyle +}$${\displaystyle (N/8)}$ ${\displaystyle -}$${\displaystyle 1}$ = ${\displaystyle (5/8)N-1}$

in entrambe le direzioni. La porzione blu più chiara è correlata alla sovrapposizione tra due circonvoluzioni adiacenti, mentre la porzione blu più scura è correlata alla sovrapposizione tra tutte e quattro le circonvoluzioni. Tutte queste porzioni sovrapposte vengono sommate insieme alle circonvoluzioni per formare la convoluzione combinata . ${\displaystyle y(n_{1},n_{2})}$

Sovrapponi e salva

Il metodo di sovrapposizione e salvataggio, proprio come il metodo di sovrapposizione e aggiunta, viene utilizzato anche per ridurre la complessità computazionale associata alle convoluzioni a tempo discreto. Questo metodo, abbinato alla FFT, consente di filtrare enormi quantità di dati attraverso un sistema digitale riducendo al minimo lo spazio di memoria necessario utilizzato per i calcoli su enormi array di dati.

Confronto per sovrapporre e aggiungere

Il metodo di sovrapposizione e salvataggio è molto simile ai metodi di sovrapposizione e aggiunta con alcune eccezioni degne di nota. Il metodo di sovrapposizione-aggiunta implica una convoluzione lineare di segnali a tempo discreto, mentre il metodo di sovrapposizione-salvataggio implica il principio della convoluzione circolare. Inoltre, il metodo di sovrapposizione e salvataggio utilizza solo un'imbottitura zero una tantum della risposta all'impulso, mentre il metodo di aggiunta sovrapposizione prevede un'imbottitura zero per ogni convoluzione su ciascun componente di ingresso. Invece di utilizzare zero padding per impedire l'aliasing nel dominio del tempo come la sua controparte di aggiunta di sovrapposizione, il salvataggio di sovrapposizione scarta semplicemente tutti i punti di aliasing e salva i dati precedenti in un blocco per essere copiati nella convoluzione per il blocco successivo.

In una dimensione, le differenze di metrica di prestazioni e archiviazione tra i due metodi sono minime. Tuttavia, nel caso della convoluzione multidimensionale, il metodo di salvataggio per sovrapposizione è preferito rispetto al metodo di aggiunta per sovrapposizione in termini di velocità e capacità di memorizzazione. Proprio come nel caso di sovrapposizione e aggiunta, la procedura richiama il caso bidimensionale ma può essere facilmente estesa a tutte le procedure multidimensionali.

Ripartizione della procedura

Sia di dimensioni : ${\displaystyle h(n_{1},n_{2})}$${\displaystyle M_{1}\times M_{2}}$

1. Inserisci colonne e righe di zeri all'inizio del segnale di ingresso in entrambe le dimensioni.${\displaystyle (M_{1}-1)}$${\displaystyle (M_{2}-1)}$${\displaystyle x(n_{1},n_{2})}$
2. Dividere il segnale corrispondente in segmenti di dimensioni sovrapposti ( ) ( ) in cui ogni blocco bidimensionale si sovrapporrà di .${\displaystyle L_{1}+M_{1}-1}$${\displaystyle \times}$${\displaystyle L_{2}+M_{2}-1}$${\displaystyle (M_{1}-1)}$ ${\displaystyle \times}$ ${\displaystyle (M_{2}-1)}$
3. Zero pad in modo che abbia le dimensioni ( ) ( ).${\displaystyle h(n_{1},n_{2})}$${\displaystyle L_{1}+M_{1}-1}$${\displaystyle \times}$${\displaystyle L_{2}+M_{2}-1}$
4. Usa DFT per ottenere .${\displaystyle H(k_{1},k_{2})}$
5. Per ogni blocco di ingresso:
   1. Prendi la trasformata di Fourier discreta di ogni blocco per dare .${\displaystyle X_{ij}(k_{1},k_{2})}$
   2. Moltiplicare per ottenere .${\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2})H(k_{1},k_{2})}$
   3. Prendi la trasformata di Fourier discreta inversa di per ottenere .${\displaystyle Y_{ij}(k_{1},k_{2})}$${\displaystyle y_{ij}(n_{1},n_{2})}$
   4. Sbarazzarsi del primo per ogni blocco di output .${\displaystyle (M_{1}-1)}$${\displaystyle \times}$${\displaystyle (M_{2}-1)}$${\displaystyle y_{ij}(n_{1},n_{2})}$
6. Trova allegando gli ultimi campioni per ogni blocco di output .${\displaystyle y(n_{1},n_{2})}$${\displaystyle (L_{1}\times L_{2})}$${\displaystyle y_{ij}(n_{1},n_{2})}$

La trasformata dell'elica

Simile alla decomposizione riga-colonna, la trasformata elica calcola la convoluzione multidimensionale incorporando proprietà e operatori convoluzionali unidimensionali. Invece di utilizzare la separabilità dei segnali, tuttavia, mappa lo spazio delle coordinate cartesiane in uno spazio delle coordinate elicoidali consentendo una mappatura da uno spazio multidimensionale a uno spazio unidimensionale.

Convoluzione multidimensionale con metodi di convoluzione unidimensionale

Per comprendere la trasformata dell'elica, è utile prima capire come una convoluzione multidimensionale può essere scomposta in una convoluzione unidimensionale. Supponiamo che i due segnali da convolure siano e , che risulta in un'uscita . Questo è espresso come segue: ${\displaystyle X_{M\times N}}$${\displaystyle Y_{K\times L}}$${\displaystyle Z_{(M-K+1)\times (N-L+1)}}$

${\displaystyle Z(i,j)=\sum _{m=0}^{M-1}\sum _{n=0}^{N-1}X(m,n)Y(im,jn) }$

Successivamente, vengono create due matrici che riempiono di zero ogni input in entrambe le dimensioni in modo tale che ogni input abbia dimensioni equivalenti, cioè

${\displaystyle \mathbf {X'} ={\begin{bmatrix}X&0\\0&0\\\end{bmatrix}}}$ e ${\displaystyle \mathbf {Y'} ={\begin{bmatrix}Y&0\\0&0\\\end{bmatrix}}}$

dove ciascuna delle matrici di input è ora di dimensioni . È quindi possibile implementare l'ordinamento lessicografico per colonne al fine di convertire le matrici modificate in vettori, e . Per ridurre al minimo il numero di campioni non importanti in ciascun vettore, ciascun vettore viene troncato dopo l'ultimo campione nelle matrici originali e rispettivamente. Detto questo, la lunghezza del vettore e sono dati da: ${\displaystyle (M+K-1)}$${\displaystyle \times}$${\displaystyle (N+L-1)}$${\displaystyle X''}$${\displaystyle Y''}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X''}$${\displaystyle Y''}$

${\displaystyle l_{X''}=}$ ${\displaystyle (M+K-1)}$${\displaystyle \times}$${\displaystyle (N-1)}$ + ${\displaystyle M}$

${\displaystyle l_{Y''}=}$${\displaystyle (M+K-1)}$${\displaystyle \times}$${\displaystyle (L-1)}$ + ${\displaystyle K}$

La lunghezza della convoluzione di questi due vettori, , può essere derivata e mostrata come: ${\displaystyle Z''}$

${\displaystyle l_{Z''}=}$ ${\displaystyle l_{Y''}+}$${\displaystyle l_{X''}}$ ${\displaystyle =(M+K-1)}$${\displaystyle \times}$${\displaystyle (N+L-1)}$

Questa lunghezza del vettore è equivalente alle dimensioni dell'output della matrice originale , rendendo la riconversione in una matrice una trasformazione diretta. Pertanto, il vettore, , viene riconvertito in forma matriciale, che produce l'output della convoluzione discreta bidimensionale. ${\displaystyle Z}$${\displaystyle Z''}$

Filtraggio su un'elica

Quando si lavora su una mesh cartesiana bidimensionale, una trasformata di Fourier lungo entrambi gli assi farà sì che il piano bidimensionale diventi un cilindro poiché l'estremità di ogni colonna o riga si attacca alla rispettiva parte superiore formando un cilindro. Il filtraggio su un'elica si comporta in modo simile, tranne che in questo caso la parte inferiore di ogni colonna si attacca alla parte superiore della colonna successiva, risultando in una mesh elicoidale. Questo è illustrato di seguito. I riquadri scuri rappresentano i coefficienti del filtro.

Se questa struttura elicoidale viene quindi tagliata e srotolata in una striscia unidimensionale, gli stessi coefficienti di filtro sul piano cartesiano 2-d corrisponderanno agli stessi dati di input, risultando in uno schema di filtraggio equivalente. Ciò garantisce che una convoluzione bidimensionale possa essere eseguita da un operatore di convoluzione unidimensionale poiché il filtro 2D è stato svolto su un filtro 1D con spazi di zeri che separano i coefficienti del filtro.

Supponendo che sia stato utilizzato un filtro bidimensionale passa-basso, come ad esempio:

0	-1	0
-1	4	-1
0	-1	0

Quindi, una volta che lo spazio bidimensionale è stato convertito in un'elica, il filtro unidimensionale avrà il seguente aspetto:

${\displaystyle h(n)=-1,0,...,0,-1,4,-1,0,...,0,-1,0,...}$

Notare nel filtro unidimensionale che non ci sono zeri iniziali come illustrato nella striscia filtrante unidimensionale dopo essere stata srotolata. L'intera striscia unidimensionale avrebbe potuto essere convoluta; tuttavia, è meno costoso dal punto di vista computazionale ignorare semplicemente gli zeri iniziali. Inoltre, nessuno di questi valori zero del lato posteriore dovrà essere archiviato in memoria, preservando preziose risorse di memoria.

Applicazioni

Le trasformazioni dell'elica per implementare filtri ricorsivi tramite convoluzione vengono utilizzate in varie aree dell'elaborazione del segnale. Sebbene l'analisi di Fourier nel dominio della frequenza sia efficace quando i sistemi sono stazionari, con coefficienti costanti e dati periodicamente campionati, diventa più difficile nei sistemi instabili. La trasformata dell'elica consente processi di migrazione post-stack tridimensionali in grado di elaborare i dati per variazioni tridimensionali di velocità. Inoltre, può essere applicato per aiutare con il problema dell'estrapolazione implicita del campo d'onda tridimensionale. Altre applicazioni includono algoritmi utili nella regolarizzazione dei dati sismici, filtri di errore di previsione e attenuazione del rumore nei sistemi digitali geofisici.

convoluzione gaussiana

Un'applicazione della convoluzione multidimensionale utilizzata nell'elaborazione di segnali e immagini è la convoluzione gaussiana. Questo si riferisce alla convoluzione di un segnale in ingresso con la funzione di distribuzione gaussiana.

La distribuzione gaussiana campionata a valori discreti in una dimensione è data dalla seguente (assumendo ):${\displaystyle \mu =0}$

Questo è facilmente esteso a un segnale di dimensioni M (assumendo che rimanga costante per tutte le dimensioni e ):${\displaystyle \sigma}$${\displaystyle \mu _{1}=\mu _{2}=...=\mu _{M}=0}$Una proprietà importante da riconoscere è che il segnale dimensionale M è separabile in modo tale che:Quindi, la convoluzione gaussiana con segnali a valori discreti può essere espressa come segue:

${\displaystyle y(n)=x(n)*G(n)}$

${\displaystyle y(n_{1},n_{2},...,n_{M})=x(n_{1},n_{2},...,n_{M})*... *G(n_{1},n_{2},...,n_{M})}$

Approssimazione tramite filtro FIR

La convoluzione gaussiana può essere efficacemente approssimata tramite l'implementazione di un filtro a risposta all'impulso finita (FIR). Il filtro sarà progettato con versioni troncate della gaussiana. Per un filtro bidimensionale, la funzione di trasferimento di tale filtro sarebbe definita come segue:

${\displaystyle H(z_{1},z_{2})={\frac {1}{s(r_{1},r_{2})}}\sum _{n_{1}=-r_{1 }}^{r_{1}}\sum _{n_{2}=-r_{2}}^{r_{2}}G(n_{1},n_{2}){z_{1}}^ {-n_{1}}{z_{2}}^{-n_{2}}}$

dove

${\displaystyle s(r_{1},r_{2})=\sum _{n_{1}=-r_{1}}^{r_{1}}\sum _{n_{2}=-r_{ 2}}^{r_{2}}G(n_{1},n_{2})}$

La scelta di valori più bassi per e comporterà l'esecuzione di meno calcoli, ma produrrà un'approssimazione meno accurata, mentre la scelta di valori più elevati produrrà un'approssimazione più accurata, ma richiederà un numero maggiore di calcoli. ${\displaystyle r_{1}}$${\displaystyle r_{2}}$

Approssimazione per filtro scatola

Un altro metodo per approssimare la convoluzione gaussiana è tramite passaggi ricorsivi attraverso un filtro a scatola. Per approssimare la convoluzione unidimensionale, questo filtro è definito come segue:

${\displaystyle H(z)={\frac {1}{2r+1}}{\frac {z^{r}-z^{-r-1}}{1-z^{-}1}} }$

In genere, vengono eseguiti passaggi ricorsivi 3, 4 o 5 volte per ottenere un'approssimazione accurata. Un metodo suggerito per calcolare r è quindi dato come segue:

${\displaystyle \sigma ^{2}={\frac {1}{12}}K((2r+1)^{2}-1)}$ dove K è il numero di passaggi ricorsivi attraverso il filtro.

Quindi, poiché la distribuzione gaussiana è separabile attraverso diverse dimensioni, ne consegue che i passaggi ricorsivi attraverso filtri unidimensionali (isolando ciascuna dimensione separatamente) forniranno quindi un'approssimazione della convoluzione gaussiana multidimensionale. Cioè, la convoluzione gaussiana M- dimensionale potrebbe essere approssimata tramite passaggi ricorsivi attraverso i seguenti filtri unidimensionali:

${\displaystyle H(z_{1})={\frac {1}{2r_{1}+1}}{\frac {{z_{1}}^{r_{1}}-{z_{1}} ^{-r_{1}-1}}{1-{z_{1}}^{-}1}}}$

${\displaystyle H(z_{2})={\frac {1}{2r_{2}+1}}{\frac {{z_{2}}^{r_{2}}-{z_{2}} ^{-r_{2}-1}}{1-{z_{2}}^{-}1}}}$

${\displaystyle \vdots}$

${\displaystyle H(z_{M})={\frac {1}{2r_{M}+1}}{\frac {{z_{M}}^{r_{M}}-{z_{M}} ^{-r_{M}-1}}}}} {z_{M}}^{-}1}}}$

Applicazioni

Le circonvoluzioni gaussiane sono ampiamente utilizzate nell'elaborazione di segnali e immagini. Ad esempio, la sfocatura dell'immagine può essere ottenuta con la convoluzione gaussiana in cui il parametro controllerà l'intensità della sfocatura. Valori più alti corrisponderebbero quindi a un risultato finale più sfocato. È anche comunemente usato nelle applicazioni di visione artificiale come il rilevamento delle funzionalità di trasformazione invariante della scala (SIFT). ${\displaystyle \sigma}$

Guarda anche

• convoluzione
• Kernel (elaborazione delle immagini)
• Elaborazione del segnale

Riferimenti