convolución discreta multidimensional

De forma similar al caso unidimensional, se utiliza un asterisco para representar la operación de convolución. El número de dimensiones de la operación se refleja en el número de asteriscos. Por ejemplo, una convolución de M dimensiones se escribiría con M asteriscos. A continuación se muestra una convolución de M dimensiones de señales discretas:

${\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})}$

Para señales de valor discreto, esta convolución se puede calcular directamente mediante lo siguiente:

${\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 región de soporte resultante de una convolución multidimensional discreta se determinará en función del tamaño y las regiones de soporte de las dos señales de entrada.

Se enumeran varias propiedades del operador de convolución bidimensional. Tenga en cuenta que estas también se pueden extender para señales de${\displaystyle N}$-dimensiones.

Propiedad conmutativa:

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

Propiedad asociada:

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

Propiedad distributiva:

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

Estas propiedades se ven en uso en la figura siguiente. Dado algún dato de entrada${\displaystyle x(n_{1},n_{2})}$que entra en un filtro con respuesta impulsional${\displaystyle h(n_{1},n_{2})}$y luego otro filtro con respuesta impulsional${\displaystyle g(n_{1},n_{2})}$, la salida viene dada por${\displaystyle y(n_{1},n_{2})}$Supongamos que la salida del primer filtro viene dada por${\ Displaystyle w (n_ {1}, n_ {2})}$, esto significa que:

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

Además, esa función intermedia se convoluciona con la respuesta impulsional del segundo filtro, y así la salida se puede representar mediante:

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

Utilizando la propiedad asociativa, esto se puede reescribir de la siguiente manera:

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

lo que significa que la respuesta impulsional equivalente para un sistema en cascada viene dada por:

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

Se puede realizar un análisis similar en un conjunto de sistemas paralelos, como se ilustra a continuación.

En este caso, está claro que:

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

Utilizando la ley distributiva, se demuestra que:

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

Esto significa que, en el caso de un sistema en paralelo, la respuesta impulsional equivalente viene dada por:

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

Las respuestas impulsionales equivalentes tanto en sistemas en cascada como en sistemas en paralelo pueden generalizarse a sistemas con${\displaystyle N}$-número de filtros. ^{[ 1 ]}

La convolución unidimensional fue un descubrimiento fundamental que permitió comparar fácilmente la entrada y la salida de un sistema lineal invariante a la traslación (LSI) (véase la teoría de sistemas LTI ), siempre que se conociera la respuesta impulsional del sistema de filtrado. Este concepto también se aplica a la convolución multidimensional, ya que el simple conocimiento de la respuesta impulsional de un filtro multidimensional permite realizar una comparación directa entre la entrada y la salida del sistema. Esto es de gran importancia, dado que muchas de las señales que se transmiten en el mundo digital actual son multidimensionales, incluyendo imágenes y vídeos. Al igual que la convolución unidimensional, la convolución multidimensional permite calcular la salida de un sistema LSI para una señal de entrada dada.

Por ejemplo, consideremos una imagen que se envía a través de una red inalámbrica sujeta a ruido electroóptico. Las posibles fuentes de ruido incluyen errores en la transmisión del canal, el convertidor analógico-digital y el sensor de imagen . Generalmente, el ruido causado por el canal o el sensor crea componentes de señal de alta frecuencia espacialmente independientes que se traducen en puntos claros y oscuros arbitrarios en la imagen. Para eliminar el contenido espectral de alta frecuencia de los datos de la imagen, se pueden multiplicar por la respuesta en frecuencia de un filtro de paso bajo, lo que, según el teorema de convolución, es equivalente a convolucionar la señal en el dominio espacio-temporal por la respuesta impulsional del filtro de paso bajo. A continuación se muestran varias respuestas impulsionales que realizan esta operación. ^{[ 2 ]}

Además de filtrar el contenido espectral, la convolución multidimensional permite la detección de bordes y el suavizado. Esto, una vez más, depende completamente de los valores de la respuesta impulsional que se utiliza para la convolución con la imagen de entrada. A continuación se muestran ejemplos típicos de respuestas impulsionales para la detección de bordes.

Además del procesamiento de imágenes, la convolución multidimensional puede implementarse para habilitar diversas aplicaciones. Dado que los filtros son comunes en los sistemas de comunicación digital, cualquier sistema que deba transmitir datos multidimensionales se beneficia de las técnicas de filtrado. Se utiliza en el procesamiento de video en tiempo real, el análisis de redes neuronales, el análisis de datos geofísicos digitales y mucho más. ^{[ 3 ]}

Una distorsión típica que se produce durante la captura o transmisión de imágenes y vídeo es el desenfoque causado por un proceso de filtrado de paso bajo. Este desenfoque puede modelarse mediante un filtrado gaussiano de paso bajo.

Se dice que una señal es separable si puede escribirse como el producto de múltiples señales unidimensionales. ^{[ 1 ]} Matemáticamente, esto se expresa de la siguiente manera:

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

Algunas señales separables fácilmente reconocibles incluyen la función escalón unitario y la función impulso delta de Dirac.

${\displaystyle u(n_{1},n_{2},...,n_{M})=u(n_{1})u(n_{2})...u(n_{M})}$ (función escalón unitario)

${\displaystyle \delta (n_{1},n_{2},...,n_{M})=\delta (n_{1})\delta (n_{2})...\delta (n_{M})}$ (función impulso delta de Dirac)

La convolución es una operación lineal. Por lo tanto, la convolución multidimensional de señales separables puede expresarse como el producto de muchas convoluciones unidimensionales. Por ejemplo, consideremos el caso en que x y h son funciones separables.

${\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})}$

Aplicando las propiedades de separabilidad, esto se puede reescribir de la siguiente manera:

${\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 )}}$

Se ve fácilmente entonces que esto se reduce al producto de convoluciones unidimensionales:

${\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 ]}}$

Esta conclusión puede extenderse entonces a la convolución de dos señales separables de dimensión M de la siguiente manera:

${\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 ]}}$

Entonces, cuando las dos señales son separables, la convolución multidimensional se puede calcular calculando${\displaystyle n_{M}}$convoluciones unidimensionales.

El método de filas y columnas se puede aplicar cuando una de las señales en la convolución es separable. El método explota las propiedades de separabilidad para lograr un método de cálculo de la convolución de dos señales multidimensionales que es más eficiente computacionalmente que el cálculo directo de cada muestra (dado que una de las señales es separable). ^{[ 4 ]} A continuación se muestra el razonamiento matemático detrás del enfoque de descomposición de filas y columnas (típicamente${\displaystyle h(n_{1},n_{2})}$es la señal separable):

${\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{aligned}}}$

El valor de${\displaystyle \sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2})}$ahora se puede reutilizar al evaluar otros${\displaystyle y}$valores con un valor compartido de${\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{aligned}}}$

Por lo tanto, la convolución resultante se puede calcular eficazmente realizando primero la operación de convolución en todas las filas de${\displaystyle x(n_{1},n_{2})}$y luego en todas sus columnas. Este enfoque se puede optimizar aún más teniendo en cuenta cómo se accede a la memoria dentro de un procesador de computadora.

Un procesador cargará los datos de señal necesarios para la operación dada. En los procesadores modernos, los datos se cargan desde la memoria a la caché del procesador, que tiene tiempos de acceso más rápidos que la memoria. La caché está particionada en líneas. Cuando se carga una línea de caché desde la memoria, se cargan varios operandos de datos a la vez. Consideremos el caso optimizado en el que una fila de datos de señal cabe completamente dentro de la caché del procesador. Este procesador en particular podría acceder a los datos fila por fila de manera eficiente, pero no columna por columna, ya que diferentes operandos de datos en la misma columna se encontrarían en diferentes líneas de caché. ^{[ 5 ]} Para aprovechar la forma en que se accede a la memoria, es más eficiente transponer el conjunto de datos y luego acceder a él fila por fila en lugar de intentar acceder a él columna por columna. El algoritmo queda entonces de la siguiente manera:

1. Separe la señal bidimensional separable${\displaystyle h(n_{1},n_{2})}$en dos señales unidimensionales${\displaystyle h_{1}(n_{1})}$y${\displaystyle h_{2}(n_{2})}$
2. Realizar una convolución fila por fila sobre los componentes horizontales de la señal.${\displaystyle x(n_{1},n_{2})}$usando${\displaystyle h_{1}(n_{1})}$para obtener${\displaystyle g(n_{1},n_{2})}$
3. Transponer las componentes verticales de la señal${\displaystyle g(n_{1},n_{2})}$como resultado del Paso 2.
4. Realizar una convolución fila por fila sobre los componentes verticales transpuestos de${\displaystyle g(n_{1},n_{2})}$para obtener el resultado deseado${\displaystyle y(n_{1},n_{2})}$

Examine el caso en el que una imagen de tamaño${\displaystyle X\times Y}$se está pasando a través de un filtro separable de tamaño${\displaystyle J\times K}$La imagen en sí no es separable. Si el resultado se calcula utilizando el método de convolución directa sin aprovechar la separabilidad del filtro, esto requerirá aproximadamente${\displaystyle XYJK}$multiplicaciones y sumas. Si se tiene en cuenta la separabilidad del filtro, el filtrado se puede realizar en dos pasos. El primer paso tendrá${\displaystyle XYJ}$multiplicaciones y sumas y el segundo paso tendrá${\displaystyle XYK}$, lo que resulta en un total de${\displaystyle XYJ+XYK}$o${\displaystyle XY(J+K)}$multiplicaciones y sumas. ^{[ 6 ]} En la siguiente imagen se muestra una comparación de la complejidad computacional entre la convolución directa y la separable:

Para señales unidimensionales, el teorema de convolución establece que la transformada de Fourier de la convolución entre dos señales es igual al producto de las transformadas de Fourier de esas dos señales. Por lo tanto, la convolución en el dominio del tiempo es igual a la multiplicación en el dominio de la frecuencia. Matemáticamente, este principio se expresa de la siguiente manera:$${\displaystyle y(n)=h(n)*x(n)\longleftrightarrow Y(\omega )=H(\omega )X(\omega )}$$Este principio se puede extender directamente al tratamiento de señales multidimensionales.$${\displaystyle y(n_{1},n_{2},...,n_{M})=h(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*x(n_{1},n_{2},...,n_{M})\longleftrightarrow Y(\omega _{1},\omega _{2},...,\omega _{M})=H(\omega _{1},\omega _{2},...,\omega _{M})X(\omega _{1},\omega _{2},...,\omega _{M})}$$Esta propiedad se extiende fácilmente al uso con la transformada discreta de Fourier (DFT) de la siguiente manera (tenga en cuenta que la convolución lineal se reemplaza por una convolución circular donde${\displaystyle \otimes }$se utiliza para denotar la operación de convolución circular de tamaño${\displaystyle N}$):

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

Al tratar con señales de múltiples dimensiones:$${\displaystyle y(n_{1},n_{2},...,n_{M})=h(n_{1},n_{2},...,n_{M})\otimes {\overset {M}{\cdots }}\otimes x(n_{1},n_{2},...,n_{M})\longleftrightarrow Y(k_{1},k_{2},...,k_{M})=H(k_{1},k_{2},...,k_{M})X(k_{1},k_{2},...,k_{M})}$$Las convoluciones circulares aquí serán de tamaño${\displaystyle N_{1},N_{2},...,N_{M}}$.

La motivación para utilizar el método de convolución circular radica en su fundamento en la transformada discreta de Fourier (DFT). La premisa de la convolución circular consiste en calcular las DFT de las señales de entrada, multiplicarlas y, posteriormente, calcular la transformada inversa de Fourier. Es fundamental utilizar una DFT suficientemente grande para evitar el aliasing. La DFT se puede calcular numéricamente al trabajar con señales de longitud finita. Una ventaja de este método es que, al requerir la DFT y la transformada inversa de Fourier, permite utilizar algoritmos eficientes como la transformada rápida de Fourier (FFT). La convolución circular también se puede calcular en el dominio espacio-temporal, no solo en el dominio de la frecuencia.

Consideremos el siguiente caso en el que se toman dos señales de extensión finita x y h . Para ambas señales, existe una DFT correspondiente como sigue:

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

La región de apoyo de${\displaystyle x(n_{1},n_{2})}$es${\displaystyle 0\leq n_{1}\leq P_{1}-1}$y${\displaystyle 0\leq n_{2}\leq P_{2}-1}$y la región de apoyo de${\displaystyle h(n_{1},n_{2})}$es${\displaystyle 0\leq n_{1}\leq Q_{1}-1}$y${\displaystyle 0\leq n_{2}\leq Q_{2}-1}$.

La convolución lineal de estas dos señales se expresaría como:$${\displaystyle y_{linear}(n_{1},n_{2})=\sum _{m_{1}}\sum _{m_{2}}h(m_{1},m_{2})x(n_{1}-m_{1},n_{2}-m_{2})}$$Dadas las regiones de apoyo de${\displaystyle x(n_{1},n_{2})}$y ${\displaystyle h(n_{1},n_{2})}$, la región de apoyo de${\displaystyle y_{linear}(n_{1},n_{2})}$Se presentará entonces de la siguiente manera:

$${\displaystyle 0\leq n_{1}\leq P_{1}+Q_{1}-1}$$$${\displaystyle 0\leq n_{2}\leq P_{2}+Q_{2}-1}$$Basándose en las regiones de soporte de las dos señales, una DFT de tamaño${\displaystyle N_{1}\times N_{2}}$debe usarse donde${\displaystyle N_{1}\geq \max(P_{1},Q_{1})}$y${\displaystyle N_{2}\geq \max(P_{2},Q_{2})}$Dado que se debe utilizar la misma DFT en ambas señales, en caso de que se necesite una DFT de mayor tamaño que la longitud de la señal, esta se rellena con ceros hasta alcanzar la longitud requerida. Tras multiplicar las DFT y calcular la DFT inversa del resultado, la convolución circular resultante viene dada por:

${\displaystyle y_{circular}(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 ]}}$para${\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\}}$

El resultado será que${\displaystyle y_{circular}(n_{1},n_{2})}$será una versión espacialmente aliase del resultado de la convolución lineal${\displaystyle y_{linear}(n_{1},n_{2})}$Esto se puede expresar de la siguiente manera:

${\displaystyle y_{circular}(n_{1},n_{2})=\sum _{r_{1}}\sum _{r_{2}}y_{linear}(n_{1}-r_{1}N_{1},n_{2}-r_{2}N_{2}){\mathrm {\,\,\,for\,\,\,} }(n_{1},n_{2})\in R_{N_{1}N_{2}}}$

Luego, para evitar el aliasing entre las réplicas espacialmente aliasadas,${\displaystyle N_{1}}$y${\displaystyle N_{2}}$Debe elegirse de acuerdo con las siguientes condiciones:

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

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

Si se cumplen estas condiciones, entonces los resultados de la convolución circular serán iguales a los de la convolución lineal (tomando el período principal de la convolución circular como región de soporte). Es decir:

${\displaystyle y_{circular}(n_{1},n_{2})=y_{linear}(n_{1},n_{2})}$para${\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}$

El teorema de convolución y la convolución circular se pueden utilizar de la siguiente manera para obtener un resultado equivalente al de realizar la convolución lineal: ^{[ 8 ]}

1. Elegir${\displaystyle N_{1}}$y${\displaystyle N_{2}}$para satisfacer${\displaystyle N_{1}\geq P_{1}+Q_{1}-1}$y${\displaystyle N_{2}\geq P_{2}+Q_{2}-1}$
2. Rellenar con ceros las señales${\displaystyle h(n_{1},n_{2})}$y${\displaystyle x(n_{1},n_{2})}$de tal manera que sean ambos${\displaystyle N_{1}\times N_{2}}$en tamaño
3. Calcular las DFT de ambos${\displaystyle h(n_{1},n_{2})}$y${\displaystyle x(n_{1},n_{2})}$
4. Multiplica los resultados de las DFT para obtener${\displaystyle Y(k_{1},k_{2})=H(k_{1},k_{2})X(k_{1},k_{2})}$
5. El resultado de la IDFT de${\displaystyle Y(k_{1},k_{2})}$será entonces igual al resultado de realizar una convolución lineal sobre las dos señales.

En lugar de realizar la convolución en los bloques de información en su totalidad, la información se puede dividir en bloques más pequeños de dimensiones.${\displaystyle L_{1}}$incógnita${\displaystyle L_{2}}$ lo que resulta en transformadas rápidas de Fourier (FFT) más pequeñas, menor complejidad computacional y menor necesidad de almacenamiento. Esto se puede expresar matemáticamente de la siguiente manera:

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

dónde${\displaystyle x(n_{1},n_{2})}$representa el${\displaystyle N_{1}}$incógnita${\displaystyle N_{2}}$señal de entrada, que es una suma de${\displaystyle P_{1}P_{2}}$segmentos de bloques, con${\displaystyle P_{1}=N_{1}/L_{1}}$y${\displaystyle P_{2}=N_{2}/L_{2}}$.

Para producir la señal de salida, se realiza una convolución bidimensional:

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

Sustituyendo por${\displaystyle x(n_{1},n_{2})}$da como resultado lo siguiente:

${\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})}$

Esta convolución añade más complejidad que una convolución directa; sin embargo, al estar integrada con una convolución rápida FFT, la superposición-suma es más rápida y consume menos memoria, lo que la hace práctica para grandes conjuntos de datos multidimensionales.

Dejar${\displaystyle h(n_{1},n_{2})}$ser de tamaño${\displaystyle M_{1}\times M_{2}}$:

1. Entrada de interrupción${\displaystyle x(n_{1},n_{2})}$en bloques de dimensiones que no se superponen${\displaystyle L_{1}\times L_{2}}$.
2. Almohadilla cero${\displaystyle h(n_{1},n_{2})}$de tal manera que tenga dimensiones (${\displaystyle L_{1}+M_{1}-1}$)${\displaystyle \times }$(${\displaystyle L_{2}+M_{2}-1}$).
3. Utilice DFT para obtener${\displaystyle H(k_{1},k_{2})}$.
4. Para cada bloque de entrada:
   1. Almohadilla cero${\displaystyle x_{ij}(n_{1},n_{2})}$ser de dimensiones (${\displaystyle L_{1}+M_{1}-1}$)${\displaystyle \times }$(${\displaystyle L_{2}+M_{2}-1}$).
   2. Tomar la transformada discreta de Fourier de cada bloque para obtener${\displaystyle X_{ij}(k_{1},k_{2})}$.
   3. Multiplica para obtener${\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2})H(k_{1},k_{2})}$.
   4. Tomar la transformada discreta inversa de Fourier de${\displaystyle Y_{ij}(k_{1},k_{2})}$Llegar${\displaystyle y_{ij}(n_{1},n_{2})}$.
5. Encontrar${\displaystyle y(n_{1},n_{2})}$superponiéndose y añadiendo el último${\displaystyle (M_{1}-1)}$${\displaystyle \times }$${\displaystyle (M_{2}-1)}$muestras de${\displaystyle y_{ij}(n_{1},n_{2})}$con el primero${\displaystyle (M_{1}-1)}$${\displaystyle \times }$${\displaystyle (M_{2}-1)}$muestras de ${\displaystyle y_{i+1,j+1}(n_{1},n_{2})}$para obtener el resultado. ^{[ 11 ]}

Para visualizar el método de superposición y suma con mayor claridad, las siguientes ilustraciones lo examinan gráficamente. Supongamos que la entrada${\displaystyle x(n_{1},n_{2})}$tiene una región cuadrada de soporte de longitud N tanto en dirección vertical como horizontal, como se muestra en la figura siguiente. Luego se divide en cuatro segmentos más pequeños de tal manera que ahora está compuesto por cuatro cuadrados más pequeños. Cada bloque de la señal agregada tiene dimensiones${\displaystyle (N/2)}$${\displaystyle \times }$${\displaystyle (N/2)}$.

Luego, cada componente se convoluciona con la respuesta impulsional del filtro. Cabe destacar que una ventaja de esta implementación se puede apreciar aquí, ya que cada una de estas convoluciones se puede paralelizar en una computadora, siempre que esta cuente con suficiente memoria y recursos para almacenar y calcular simultáneamente.

En la figura siguiente, el primer gráfico de la izquierda representa la convolución correspondiente al componente de la entrada.${\displaystyle x_{0,0}}$con la correspondiente respuesta impulsional${\displaystyle h(n_{1},n_{2})}$A la derecha de eso, la entrada${\displaystyle x_{1,0}}$Luego se convoluciona con la respuesta impulsional.${\displaystyle h(n_{1},n_{2})}$.

El mismo proceso se aplica a las otras dos entradas, respectivamente, y se suman para formar la convolución. Esto se muestra a la izquierda.

Supongamos que la respuesta impulsional del filtro ${\displaystyle h(n_{1},n_{2})}$tiene una región de apoyo de${\displaystyle (N/8)}$en ambas dimensiones. Esto implica que cada convolución convoluciona señales con dimensiones${\displaystyle (N/2)}$${\displaystyle \times }$${\displaystyle (N/8)}$en ambos${\displaystyle n_{1}}$y${\displaystyle n_{2}}$direcciones, lo que lleva a la superposición (resaltada en azul) ya que la longitud de cada convolución individual es equivalente a:

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

en ambas direcciones. La porción azul más clara se correlaciona con la superposición entre dos convoluciones adyacentes, mientras que la porción azul más oscura se correlaciona con la superposición entre las cuatro convoluciones. Todas estas porciones de superposición se suman a las convoluciones para formar la convolución combinada.${\displaystyle y(n_{1},n_{2})}$. ^{[ 12 ]}

El método de superposición y guardado es muy similar a los métodos de superposición y suma, con algunas excepciones notables. El método de superposición y suma implica una convolución lineal de señales de tiempo discreto, mientras que el método de superposición y guardado utiliza el principio de convolución circular. Además, el método de superposición y guardado solo utiliza un relleno de ceros único de la respuesta impulsional, mientras que el método de superposición y suma implica un relleno de ceros para cada convolución en cada componente de entrada. En lugar de utilizar relleno de ceros para evitar el aliasing en el dominio del tiempo, como su contraparte de superposición y suma, el método de superposición y guardado simplemente descarta todos los puntos de aliasing y guarda los datos anteriores en un bloque para copiarlos en la convolución del siguiente bloque.

En una dimensión, las diferencias en el rendimiento y el almacenamiento entre ambos métodos son mínimas. Sin embargo, en el caso de convolución multidimensional, el método de superposición y guardado se prefiere al de superposición y suma en términos de velocidad y capacidad de almacenamiento. ^{[ 13 ]} Al igual que en el caso de superposición y suma, el procedimiento se basa en el caso bidimensional, pero puede extenderse fácilmente a todos los procedimientos multidimensionales.

Dejar${\displaystyle h(n_{1},n_{2})}$ser de tamaño${\displaystyle M_{1}\times M_{2}}$:

1. Insertar${\displaystyle (M_{1}-1)}$columnas y${\displaystyle (M_{2}-1)}$filas de ceros al comienzo de la señal de entrada ${\displaystyle x(n_{1},n_{2})}$en ambas dimensiones.
2. Divida la señal correspondiente en segmentos superpuestos de dimensiones (${\displaystyle L_{1}+M_{1}-1}$)${\displaystyle \times }$(${\displaystyle L_{2}+M_{2}-1}$) en el que cada bloque bidimensional se superpondrá por${\displaystyle (M_{1}-1)}$${\displaystyle \times }$${\displaystyle (M_{2}-1)}$.
3. Almohadilla cero${\displaystyle h(n_{1},n_{2})}$de tal manera que tenga dimensiones (${\displaystyle L_{1}+M_{1}-1}$)${\displaystyle \times }$(${\displaystyle L_{2}+M_{2}-1}$).
4. Utilice DFT para obtener${\displaystyle H(k_{1},k_{2})}$.
5. Para cada bloque de entrada:
   1. Tomar la transformada discreta de Fourier de cada bloque para obtener${\displaystyle X_{ij}(k_{1},k_{2})}$.
   2. Multiplica para obtener${\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2})H(k_{1},k_{2})}$.
   3. Tomar la transformada discreta inversa de Fourier de${\displaystyle Y_{ij}(k_{1},k_{2})}$Llegar${\displaystyle y_{ij}(n_{1},n_{2})}$.
   4. Deshazte del primero${\displaystyle (M_{1}-1)}$${\displaystyle \times }$${\displaystyle (M_{2}-1)}$para cada bloque de salida${\displaystyle y_{ij}(n_{1},n_{2})}$.
6. Encontrar${\displaystyle y(n_{1},n_{2})}$adjuntando el último${\displaystyle (L_{1}\times L_{2})}$muestras para cada bloque de salida${\displaystyle y_{ij}(n_{1},n_{2})}$. ^{[ 11 ]}

Para comprender la transformada helicoidal, es útil entender primero cómo una convolución multidimensional puede descomponerse en una convolución unidimensional. Supongamos que las dos señales que se van a convolucionar son:${\displaystyle X_{M\times N}}$y${\displaystyle Y_{K\times L}}$, lo que da como resultado una salida${\displaystyle Z_{(M-K+1)\times (N-L+1)}}$Esto se expresa de la siguiente manera:

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

A continuación, se crean dos matrices que rellenan con ceros cada entrada en ambas dimensiones de manera que cada entrada tenga dimensiones equivalentes, es decir

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

donde cada una de las matrices de entrada ahora tiene dimensiones${\displaystyle (M+K-1)}$${\displaystyle \times }$${\displaystyle (N+L-1)}$. Entonces es posible implementar un ordenamiento lexicográfico por columnas para convertir las matrices modificadas en vectores,${\displaystyle X''}$y${\displaystyle Y''}$Para minimizar el número de muestras no importantes en cada vector, cada vector se trunca después de la última muestra en las matrices originales.${\displaystyle X}$y${\displaystyle Y}$respectivamente. Dado esto, la longitud del vector${\displaystyle X''}$y ${\displaystyle Y''}$son dados por:

${\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 longitud de la convolución de estos dos vectores,${\displaystyle Z''}$, se puede derivar y demostrar que es:

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

La longitud de este vector es equivalente a las dimensiones de la matriz de salida original.${\displaystyle Z}$, lo que hace que la conversión de nuevo a una matriz sea una transformación directa. Por lo tanto, el vector,${\displaystyle Z''}$, se convierte de nuevo a forma matricial, lo que produce la salida de la convolución discreta bidimensional. ^{[ 14 ]}

Al trabajar con una malla cartesiana bidimensional, una transformada de Fourier a lo largo de cualquiera de los ejes da como resultado que el plano bidimensional se convierta en un cilindro, ya que el extremo de cada columna o fila se une a su respectiva parte superior, formando así un cilindro. El filtrado en una hélice se comporta de manera similar, excepto que en este caso, la parte inferior de cada columna se une a la parte superior de la siguiente, lo que da como resultado una malla helicoidal. Esto se ilustra a continuación. Las celdas sombreadas representan los coeficientes del filtro.

Si esta estructura helicoidal se divide y se desenrolla en una tira unidimensional, los mismos coeficientes de filtro en el plano cartesiano bidimensional coincidirán con los mismos datos de entrada, lo que dará como resultado un esquema de filtrado equivalente. Esto garantiza que una convolución bidimensional pueda realizarse mediante un operador de convolución unidimensional, ya que el filtro bidimensional se ha desenrollado a un filtro unidimensional con intervalos de ceros que separan los coeficientes del filtro.

Suponiendo que se utilizó algún filtro bidimensional de paso bajo, como por ejemplo:

Luego, una vez que el espacio bidimensional se convirtió en una hélice, el filtro unidimensional se vería de la siguiente manera:

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

Nótese que en el filtro unidimensional no hay ceros iniciales, como se ilustra en la tira de filtrado unidimensional después de ser desenrollada. Se podría haber convolucionado toda la tira unidimensional; sin embargo, es menos costoso computacionalmente simplemente ignorar los ceros iniciales. Además, ninguno de estos valores cero posteriores necesitará almacenarse en memoria, lo que preserva valiosos recursos de memoria. ^{[ 15 ]}

Las transformaciones helicoidales para implementar filtros recursivos mediante convolución se utilizan en diversas áreas del procesamiento de señales. Si bien el análisis de Fourier en el dominio de la frecuencia es efectivo cuando los sistemas son estacionarios, con coeficientes constantes y datos muestreados periódicamente, se vuelve más difícil en sistemas inestables. La transformada helicoidal permite procesos de migración post-apilamiento tridimensionales que pueden procesar datos para variaciones tridimensionales en la velocidad. ^{[ 15 ]} Además, se puede aplicar para ayudar con el problema de la extrapolación implícita del campo de ondas tridimensional. ^{[ 16 ]} Otras aplicaciones incluyen algoritmos útiles en la regularización de datos sísmicos, filtros de error de predicción y atenuación de ruido en sistemas digitales geofísicos. ^{[ 14 ]}

La convolución gaussiana se puede aproximar eficazmente mediante la implementación de un filtro de respuesta de impulso finito (FIR). El filtro se diseñará con versiones truncadas de la gaussiana. Para un filtro bidimensional, la función de transferencia de dicho filtro se definiría de la siguiente manera: ^{[ 17 ]}

${\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}}}$

dónde

${\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})}$

Elegir valores más bajos para${\displaystyle r_{1}}$y${\displaystyle r_{2}}$Esto dará como resultado realizar menos cálculos, pero producirá una aproximación menos precisa, mientras que elegir valores más altos producirá una aproximación más precisa, pero requerirá un mayor número de cálculos.

Otro método para aproximar la convolución gaussiana es mediante pasadas recursivas a través de un filtro de caja. Para aproximar la convolución unidimensional, este filtro se define de la siguiente manera: ^{[ 17 ]}

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

Normalmente, se realizan 3, 4 o 5 pasadas recursivas para obtener una aproximación precisa. ^{[ 17 ]} A continuación se presenta un método sugerido para calcular r : ^{[ 18 ]}

${\displaystyle \sigma ^{2}={\frac {1}{12}}K((2r+1)^{2}-1)}$ donde K es el número de pasadas recursivas a través del filtro.

Entonces, dado que la distribución gaussiana es separable en diferentes dimensiones, se deduce que los pasos recursivos a través de filtros unidimensionales (aislando cada dimensión por separado) producirán una aproximación de la convolución gaussiana multidimensional. Es decir, la convolución gaussiana M- dimensional podría aproximarse mediante pasos recursivos a través de los siguientes filtros unidimensionales:

${\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}}{1-{z_{M}}^{-}1}}}$

Las convoluciones gaussianas se utilizan ampliamente en el procesamiento de señales e imágenes. Por ejemplo, el desenfoque de imágenes se puede lograr con una convolución gaussiana donde${\displaystyle \sigma }$Este parámetro controlará la intensidad del desenfoque. Valores más altos corresponderán, por lo tanto, a un resultado más borroso. ^{[ 19 ]} También se utiliza comúnmente en aplicaciones de visión artificial, como la detección de características mediante la transformada de características invariante a la escala (SIFT). ^{[ 20 ]}