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.

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 to

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