如何在 c++ 中执行 2D 快速傅立叶变换

Question

我看到有一个帖子关于这个话题，但没有任何回复。
如何编写一个函数来对给定图像 f 执行二维快速傅立叶变换？
可以假设对于某些整数 m 和 n，宽度 = 2^m，高度 = 2^n，并且输入图像已经正确填充。
输入： f - 以复数表示的 2D 图像
输出： F - 变换后的系数，也以复数表示

void FFT2D(Complex<double> *f, Complex<double> *F, int width, int height)
{

}

对于每个认为我希望你为我编程的人：
我不知道。只是想要一些关于它应该如何工作的理论解释

Answer 1

您可以使用 FFTW 库 来执行此操作：

#include <fftw.h>

void FFT2D(Complex<double> *f, Complex<double> *F, int width, int height){   
  fftw_plan p = fftw_plan_dft_2d(width, height, f, F, FFTW_FORWARD, FFTW_ESTIMATE);            
  fftw_execute(p); 
  fftw_destroy_plan(p);
}

Answer 2

我怀疑有人会为您编写 FFT 实现。这是不平凡且耗时的（您也表现出零努力）。

你明白它背后的数学原理吗？如果您了解其背后的数学原理，则需要查看各种 FFT 算法（想到的是 Cooley Tukey）并简单地实现它们。而且，这听起来像是一个家庭作业问题。

但既然你问了，这里有一个由 Google 提供的 DFT 和 FFT 的 C 实现： http://paulbourke.net/ Miscellaneous/dft/

PS：你想为我编写一个A*实现吗？