FFT-8(基8快速傅里叶变换)

1D傅里叶逆变换：

?

?2D傅里叶变换：

2D傅里叶变换通过两次1D傅里叶变换实现：

由此我们只需要关注1D的傅里叶变换如何处理，又因为我们处理图片的时候都是离散的点信息，最终我们得到的傅里叶变换是：

逆变换：

上述的傅里叶变换公式很直观，图像进行傅里叶变换时，像素点是n，最终转换到频域的时候，结果纹理存储的是k点的集合。（比较重要的是，傅里叶变换和逆变换不同点只有两个：(1/N)和(-kn)，这说明他们的算法实现可以共用）

?

快速傅里叶算法(FFT)：

先看一下一个8个采样点的快速傅里叶变换，它是基2，基4，基8的快速傅里叶算法的基础：

1.看下面不起眼的stage单词没，它对整个过程划分了几个阶段，个人感觉这里的划分有问题，应该是3个阶段。每个阶段有几个过程：(n个输入：log2(n+1)个阶段：nlog2(n)次复数乘法和加法)

(1)排序过程：黄颜色的部分，执行排序功能，让需要计算的两个值排在一起进行计算。

k = BIT_REVERSE(n)

(2)加权过程：蓝颜色部分，相乘的两个位置为奇数位的需要乘一个W(n0)，看上面好像只有第1个阶段是对的，其实第2个和第3个阶段如果排完序就是对的了。

(3)蝶形算法过程：

一次蝶形运算：两次复数加法 + 两次复数乘法 （复数加法：2次浮点加法 ? 复数乘法：4次浮点乘法+2次浮点加法） 一次蝶形运算 = 8次浮点乘 + 8次浮点加

?

FFT算法实现：

1.FFT：

2D的就是做两次1D的FFT运算
?
参考：
http://www.librow.com/articles/article-10