User @Paul_R wrote that you need to zeropad an image of 1920*1080 = 2^20,984
to 2048*2048 = 2^22 when using the Cooley-Tukey FFT?
Why don't we just zeropad it to 2^21=2048*1024?
Asked
Active
Viewed 69 times
-1
-
If you're using FFTW anyway, you really don't need to pad; the software is smart enough to perform a prime factor FFT. – J. M. ain't a mathematician Jun 02 '13 at 12:48
-
@J.M. Can you answer my question about the FFTW? http://dsp.stackexchange.com/questions/9395/does-the-fftw-have-a-cost-of-knlog-2n – user8005 Jun 02 '13 at 12:50
-
Sorry, no account there. But, as noted in the implementation notes for FFTW, the prime factor algorithms are asymptotically $n\log,n$, with the difficulty in the factorization of your array's dimensions. – J. M. ain't a mathematician Jun 02 '13 at 12:52
-
I think that this question (or a closely related one) has been asked and answered on at least three different SE sites: math, dsp and cs. – Dilip Sarwate Jun 03 '13 at 02:53
1 Answers
1
Because changing $1080$ to $1024$ is truncating your data, throwing away 56 of the columns.
-
Why can't we move those 56 columns? So it will fit inside? 2^21 pixels? – user8005 Jun 02 '13 at 14:10
-
You can rearrange the data any way you like; but then you'd be doing an FFT on the rearranged data rather than the data you actually care about. – Jun 02 '13 at 14:26
-
Someone wrote "The algorithm that Cooley and Tukey presented in their classic paper (Math. Comp. 19 (1965), 297-301. http://dx.doi.org/10.1090/S0025-5718-1965-0178586-1) can be applied to any composite length. The performance advantages are greatest for highly composite lengths, of which powers-of-2 are one example, and lengths of powers-of-2 result in other advantages on binary computers, so it has become a common misconception that the algorithm is only applicable to signals whose length is a power of 2." Does that mean we don't need any zeropadding at all? – user8005 Jun 02 '13 at 18:44
-
-