DFT/FFT: What did N stand for again?

So if I have an image of the size: 1920×1080 and I want to apply a convolution filter of 3x3. Take the formula for DFT $N^2$ and FFT $N \log N$. What should I fill in for N in this case?

migrated from scicomp.stackexchange.comMay 20 '13 at 21:02

This question came from our site for scientists using computers to solve scientific problems.

• There really isn't enough information here to answer the question. What do you mean by $N$? Number of operations? Number of DFT coefficients? If so, in which dimension? The best answer I can give right now is that N is the fourteenth letter of the English alphabet. – Phonon May 20 '13 at 21:10
• Simultaneously cross posted at cs.stackexchange.com/questions/12170/…. – Wandering Logic May 21 '13 at 2:56

Your image is M rows x N cols, and a 2D FFT requires 1D FFTs on all rows followed by 1D column-wise FFTs on the result.

So you have:

$M N \log N + N M \log M = MN (\log M + \log N) = MN \log MN$

operations in total.

The DFT case can be derived using a similar method - this is left as an exercise for the reader.

• The complexity thus corresponds to an FFT of size $MN$. – niaren May 21 '13 at 7:49
• @Paul_R For a FFT like the Cooley-Tukey one, do I need to round both the row and column count to 2048 for both the image and the 3x3 kernel? So M = N = 2048. – user1095332 May 22 '13 at 18:21
• If you're doing convolution in the frequency domain then you need to pad the kernel to the same dimensions as the image prior to calculating the FFT. And if your FFT only supports 2^n points then yes, you'll need to pad M, N too. – Paul R May 22 '13 at 18:48
• Do I really need 2048*2048 or just 2048*1024 points? – user1095332 May 23 '13 at 10:17
• Well if your dimensions are 1920×1080 and you only have a power of 2 FFT then yes, you'll need to go to 2048x2048. Alternatively use an FFT which supports other radices, e.g. FFTW supports combinations of powers of small primes (2, 3, 5, 7), so you could then go to e.g. 2048x1536. – Paul R May 23 '13 at 10:43

In DFT-FFT operation the N stands for Number of samples you have in that Sequence.

For example If you have matrix function like with 3*3 order then It means in the first sequence you got 3 Samples and in the second sequence you got 3 samples.

Here stood for the number of samples in the given function sequence.

• That is a strange way to formulate an answer, 3 samples + 3 samples = 6 samples? With 9 pixels??? To which number should I round to get a power of 2 for FFT? – user1095332 May 22 '13 at 18:20