evaluating individual terms of 2D DFT (Goertzel?) - Signal Processing Stack Exchange most recent 30 from dsp.stackexchange.com 2019-11-12T18:22:36Z https://dsp.stackexchange.com/feeds/question/21642 https://creativecommons.org/licenses/by-sa/4.0/rdf https://dsp.stackexchange.com/q/21642 2 evaluating individual terms of 2D DFT (Goertzel?) firescape https://dsp.stackexchange.com/users/13732 2015-02-13T23:52:16Z 2015-02-20T14:19:50Z <p>I'm looking for a fast way to do a 2D discrete Fourier transform of an image at many arbitrary frequencies. I know the Goertzel algorithm works for 1D, but is it possible to generalize it in 2D? Or any other useful algorithms? Two solutions that I know, but which I'm afraid might be too slow, are directly using the DFT equation, and zero padding and doing an FFT. Alternately, the frequencies might not need to be completely arbitrary but could be sub-arrays of the array of frequencies given by an FFT with high frequency resolution.</p> https://dsp.stackexchange.com/questions/21642/evaluating-individual-terms-of-2d-dft-goertzel/21643#21643 0 Answer by Oscar for evaluating individual terms of 2D DFT (Goertzel?) Oscar https://dsp.stackexchange.com/users/8009 2015-02-20T14:12:53Z 2015-02-20T14:19:50Z <p>The 2D DFT is separable, so you can conceptually compute it by applying 1D DFTs in both directions. For the Goertzel algorithm you can first apply it for a specific column for each row, and then use that column and apply it again to obtain the individual term. Most likely, you can rewrite the Goertzel algorithm to do this in one go, but the computational savings are quite small (for an $N \times N$ image, you would need $N^2 + N$ multiplications using the separable approach, while a 2D version would give $N^2$ multiplications).</p>