2
$\begingroup$

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.

$\endgroup$

migrated from stackoverflow.com Feb 20 '15 at 13:45

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ Goertzel algorithm just applies Goertzel filter. You can derive something similarly for 2D. The problem is that your frequency response in 2D is now defined by 2 components, so the filter isn't quite simply defined as in the 1D case. $\endgroup$ – thang Feb 14 '15 at 0:51
  • $\begingroup$ for arbitrary frequencies I see only one possibility and that is implement fast algorithm directly for 2D instead of using 1D transforms which need the full frequency range computed. That is not that easy as it sounds... because arbitrary frequencies broke most of the optimizations options for DFFT and the 2D recursion is also a bit complicated to code properly. not to mention the added overhead from more recursion layers in comparison to usage of 1D transforms to compute 2D case .... so in the end you can end up with worse runtimes then the standard full range 2D DFFT $\endgroup$ – Spektre Feb 14 '15 at 7:10
0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ what separable approach gives you $O(N^2)$? FFT in 2D is $O(N^2*log(N))$. DFT in 2D is $O(N^3)$. $\endgroup$ – thang Mar 3 '15 at 22:05
  • 1
    $\begingroup$ @thang: The one I described. Note that I am talking about computing one tap in the frequency domain, which is $O(N^2)$ in itself, not all. Goertzel would only help avoid computing lots of different coefficients. $\endgroup$ – Oscar Mar 5 '15 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.