【数字图像处理】2.3:FFT算法理解与c语言的实现
【数字图像处理】2.3:FFT算法理解与c语言的实现

简单的说,为了速度。我们承认DFT很有用,但是我们发现他的速度不是很快,1D的DFT原始算法的时间复杂度是 $O(n^2)$ ,这个可以通过公式观察出来,对于2D的DFT其时间复杂度是 $O(n^4)$ ,这个速度真的很难接受,也就是说,你计算一幅1024x768的图像时,你将等大概

【数字图像处理】2.2:二维DFT
【数字图像处理】2.2:二维DFT

由于只是为了观察结果,所以使用了固定大小的二维数组,若实际工作中应该根据需要动态分配内存。如下结果:上面为原始数据,中间为DFT后的数据,最下面为IDFT后的结果。