谭升
非主流人工智能科学家 我和外面那些妖艳的货不一样

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

为什么需要FFT

简单的说,为了速度。我们承认DFT很有用,但是我们发现他的速度不是很快,1D的DFT原始算法的时间复杂度是 $O(n^2)$ ,这个可以通过公式观察出来,对于2D的DFT其时间复杂度是 $O(n^4)$ ,这个速度真的很难接受,也就是说,你计算一幅1024×768的图像时,你将等大概。。。大概。。。我也没试过,反正很久。不信的自己去试试。所以找到一种快速方法的方法计算FFT势在必行。 以下为DFT公式
Center      
计算一个4点DFT。计算量如下:
Center 1

如何得到FFT

通过观察DFT公式,我们发现DFT计算每一项 $X[u]$ 的时候都遍历了完整的 $x[n]$ 所以,我们的想法就是能不能通过其他的 $X[u+m]$(m为一个整数,可正可负)得到 $X[u]$ ,也就是充分利用之间的计算结构来构建现在的结果,这种方法就很容易表现成迭代的形式。本文介绍基2的FFT,及离散信号 $x[n]$ 的个数为2的k次方,即如果完整的离散信号中有N个信分量 ${x_1,x_2,x_3….x_N}$ 其中 $N=1<<k$。

数学基础

FFT的数学基础其实就是:

Center 2

Center 3

旋转因子具有以下性质:

Center 4

这些性质使得我们可以利用前面的计算结果来完成出后续的计算。

Center 5

最终算法

Center 6

8-FFT

废话不多说,和上面一样:

计算过程为:

Center 7

结果为:

Center 8

$2^n$-FFT

同理,推广到2^n,可以得到类似的结果,不过我们发现,为了使输出结果为顺序结果,输入的顺序经过了一系列的调整,而且每一步WN的幂次参数也是变化,我们必须得到其变化规律才能更好的编写程序:

观察WN的变化规律为:

Center 9

节点距离(设为z)就是从WN的0次幂开始连续加到$W_N$的z次幂。然后间隔为z个式子,再次从0次幂加到z次。重复以上过程:

Center 10

例如第二级,间隔z=2,节点为实心黑色点,节点0,1,不做操作,节点$2W_8^0$,节点 $3W_8^2$ ,节点4,5不做操作。。

其内在规律就是节点i是否乘以WN:

节点 $i*W_N^{step}$

step每次增加的数量由当前的所在的计算级决定

输入参数重新排序

Center 11

i行表示数组下标,蓝色数字表示实际数据:其内在规律就是,下标为偶数的将被映射到自己本身下标的 $\frac{1}{2}$ 处,下表为奇数时被映射到数组后半段 $(size_{n/2})$ 的(下标-1)$\frac{1}{2}$处,将排列后的数据分为前后两个部分,递归次过程,直到只有两个元素。则停止。过程如下:

Center 12
Center 13
Center 14
Center 15
Center 16

观察算法

观察至此,我们已经基本把FFT蝶形算法的所有特征都搞定了,接下来就是使用代码来实现了。

Center 17

实现代码

测试结果

Center 18
Center 19

其中时间都为s,FFT优势明显

Share

You may also like...

说点什么

avatar
  Subscribe  
提醒

由于博客移至wordpress,部分公式和代码显示不正常,博主正在努力修改,如发现公式显示错误,请及时在文章下留言,感谢您的帮助,尽请原谅!