Multidimensional discrete convolution

In signal processing, multidimensional convolution refers to the mathematical operation between two functions f and g of n-dimensions that produces a third function, also of n-dimensions. Multidimensional convolution is a direct extension of the one-dimensional convolution case.

Definition

Similar to the one-Dimensional case, an asterisk is used to represent the convolution operation. The number of dimensions in the given operation is reflected in the number of asterisks. For example, the following represents a two-Dimensional convolution:

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

For discrete-valued signals, this two-dimensional convolution can be directly computed via the following:

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

This same form concept is readily extendable to the n-dimensional case.

Problem Statement & Basics

Motivation & Applications

Row-Column Decomposition with Separable Signals

Separable Signals

A signal is said to be separable if it can be written as the product of multiple 1-Dimensional signals ^[1]. Mathematically, this is expressed as the following:

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

Some readily recognizable separable signals include the unit step function, and the delta-dirac impulse function.

${\displaystyle u(n_{1},n_{2},...,n_{M})=u(n_{1})u(n_{2})...u(n_{M})}$  (unit step function)

${\displaystyle \delta (n_{1},n_{2},...,n_{M})=\delta (n_{1})\delta (n_{2})...\delta (n_{M})}$  (delta-dirac impulse function)

Convolution is a linear operation. It then follows that the multidimensional convolution of separable signals can be expressed as the product of many one-dimensional convolutions. For example, consider the case where x and h are both separable functions.

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

By applying the properties of separability, this can then be rewritten as the following:

${\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_{1})x(n_{1}-k_{1}){\bigg )}}$ 

It is readily seen then that this reduces to the product of two one-dimensional convolutions:

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

This conclusion can then be extended to the convolution of two M-dimensional signals as follows:

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

Row-Column Decomposition

Overlap and Add and Overlap and Save

Another method to perform multidimensional convolution is the overlap and add approach. This method helps reduce the computational complexity often associated with multidimensional convolutions due to the vast amounts of data inherent in modern day digital systems. For example, consider a two-dimensional convolution using a direct computation:

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

Assuming that the output signal ${\displaystyle y(n_{1},n_{2})}$  has N nonzero coefficients, this direct computation would need N multiplies and N adds in order to compute. This means that if a 512 x 512 image were to be computed using a 10 x 10 two-dimensional filter, 26,214,400 multiplies and adds would be necessary. Using an FFT instead, the complexity can be drastically reduced, but the frequency response of the filter, the Fourier transform of the input, and the time-___domain input signal would all have to be stored in memory. This is where overlap and add method comes in.

Instead of performing convolution on the blocks of information in their entirety, the information can be broken up into smaller blocks resulting in smaller FFTs, less computational complexity, and less storage needed. This can be expressed mathematically as follows:

<math> x(n_1, n_2) = \sum_{i=1}^{L_1} \sum_{j=1}^{L2}x

The Helix Transform

Similar to row-column decomposition, the helix transform computes the multidimensional convolution by incorporating one-dimensional convolutional properties and operators. Instead of using the separability of signals,

References

1. Dudgeon, Dan; Mersereau, Russell (1983), Multidimensional Digital Signal Processing, Prentice-Hall, p. 8