Multidimensional discrete convolution: Difference between revisions

Revision as of 23:16, 7 November 2015

Revision as of 23:17, 7 November 2015

Line 39:

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:

<math>y(n_1, n_2) = \sum_{k_1=-\infty}^{\infty} \sum_{k_2=-\infty}^{\infty} y(n_1, n_2) = x(n_1 - k_1, n_2 - k_2)h(k_1, k_2)</math>

Assuming that the output signal <math>y(n_1, n_2)</math> 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==