快速傅立叶变换算法及其改进..doc

快速傅立叶变换算法及其改进 何广 离散傅立叶变换(DFT)是数字图像处理中应用十分广泛的一种变换，具有很好的实用性，例如：在进行图像低通滤波、高通滤波中，可以借助傅立叶变换把要在空域中解决的问题转换到频域中进行处理。而且更重要的是其快速算法----快速傅立叶变换（FFT）对其计算速度又有非常大的改进，从而使得该算法得到了更加广泛的应用。 将其离散化得到离散的傅立叶变换： u = 0, 1, 2, ...N-1 相应的二维傅立叶变换为： 相应的二维离散傅立叶变换为： 这样，对于一幅M*N的数字图像，如果用上面的公式直接进行计算其傅立叶变换，需要的完成的复数乘法和加法次数分别为M2N2和MN(M-1)(N-1)。对于目前常用的512*512的数字图像，其复数乘法和加法的次数都将达到5124≈700亿次。而利用快速傅立叶变换只需要时间（512* log2(512)）2 ≈2千万次 。 Cooley和Tukey于1965年提出了下面介绍的FFT算法，利用该算法在实现f(x)(x = 0,1,…,N-1)的离散傅立叶变换时，需要完成的复数乘法和加法的次数分别为1/2Nlog2(N)和Nlog2(N)。而直接用离散傅立叶变换的式子进行计算，需要进行的复数乘法和加法次数分别为N2N(N-1)≈N2。 首先有： 设W(N)= exp(-j2 /N) 是一个常数，一般称为铰链因子，N =2n其中n是一个正整数，因此N可表示为N = 2M，这里M仍然是一个正整数将N = 2M代入上式得到： Feven(u) = 1/M f(2x)W(M)ux u = 0,1,2,…M-1. Fodd (u) = 1/M f(2x+1)W(M)ux u = 0,1,2,…M-1. 于是得出FFT 的第一个递推公式： F(u)=1/2 ( Feven(u)+Fodd(u)W（2M）u ) F(u)可以通过奇部和偶部之和来计算。 W（M）u+M = WM）u 和W(2M)u+M = -W(2M)uu+M 的DFT为： F(u+M) = 1/2 [1/M f(2x)W(M)(u+M)x +1/M f(2x+1)W(M)(u+M)x W(2M)u+M] = 1/2 ( Feven(u)- Fodd(u)W(2M)u ) FFT的第二个递推公式： F(u+M)= 1/2(Feven(u)-Fodd(u)W(2M)u) F(u+M)可以通过F(u)偶部和奇部之差来计算,得出FFT的两个递推公式： F(u) = 1/2(Feven(u)+Fodd(u)W2Mu) F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu) N个点的变换，能够把原始表达式分成每个点数为N/2的两部分，分别计算得到Feven(u)和Food(u),然后，奇数部分和偶数部制和得到F(u)的前(N/2)各点的值，奇数部分和偶数部分之差得到后(N/2)个点的值。DFT来计算两个点的DFT，通过计算两个双点的DFT来计算四个点的DFT；以此类推，对于任何N=2mDFT的计算通过计算两个N/2点的DFT来计算N个点的DFT，这就是快速傅立叶变换（FFT）的方法。 M*N的数字图像，如果用DFT直接计算其傅立叶变换，需要的完成的复数乘法和加法次数分别为M2N2MN(M-1)(N-1)。对于目前常用的512*512的数字图像，用DFT计5124≈700亿次，而利用快速傅立叶变换只需要时间（512* log2(512)）2 2千万次 ,大大降低了算法的复杂度。 当输入数据序列为两个长度相同实数据时，可以用复序列的变换一次求得两个实序列的变换结果，从而节约运算量。而在实际的应用中，要求变换数据都是实序列，所以这种方法是很有效果的。如若有长度相同的实序列h(n)和g(n)，可以把它们组合成一个复序列y(n)，即: y(n)=h(n)+ig(n) i为复数单位i2=-1可得 Y(K)=(Hr(k)-Gi(k))+(Hi(k)+Gr(k)) Hr，Hi,Gr和Gi分别为h和g的傅立叶变换函数H和G的实部和虚部。Y为y的傅立叶变换。同时根据前面证明时，有: Y(k)=((Yr(k)+Yr(N-k))/2)+((Yr(k)-Yr(N-k))/2) +i((Yi(k)+Yi(N-K))/2)+(Yi(k)-Yi(N-k))/2)) H(k)=(Yr(k)+Yr(N-K))/2+i(Yi(k)-Yi(N-k))/2 G(k)=(Yi(k)+Yi(N-k))/2-i(Yr(k)-Yr(N-k))/2 这样，在求得Y(k)之后，通过式，做一次N点复序列的离散傅立叶变换，就能同时把两个N点实序