Content deleted Content added
Shaddowffax (talk | contribs) |
No edit summary |
||
Line 43:
<math>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)</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, 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==
| |||