fft方法的matlab实现

1、FFTUniversity of Science and Technology of Beijing沈政伟v一，Fourier 级数v二，连续FourierTransformv三，一维离散傅立叶变换（Discrete Fourier Transform）.v一，Fourier 级数v法国著名科学家傅立叶在1807年向法国国家科学院提交的一篇报告中提出：“任何周期函数都可以用一系列正弦波（谐波）来线性表示”Fourier 级数考虑正弦波，显然该函数周期为 ，对应的频率为 而一般的乐器发出的声音以及电压等信号都可以通过具有不同频率的正弦波函数叠加来表示。比如：信号在持续为 的时间内分别振动次数为

2、1,20,100次，而其中频率为1的分量振幅最大，达到100，从而具有决定性作用。 )sin(ktk2k100sin( )3sin(20 )0.5sin(100 )ttt2v v在一般情形下，信号可以用下面正弦波的无穷和形式来进行分解。v在这个公式中，通过由Riemann-Lebesgue引理 知道：（为什么？）v这表明一般实际信号（能量有限）中的高频成分会随着频率的增大，相应的变小，信号中的主要成分为少数系数（频率低的部分）所控制。而信号的高频成分对应着信号中的细节部分，而低频成分对应着信号的主要的信息)(tfkkkktbktaatf)sin()cos()(00limlimkkkkbav二，

3、连续FourierTransformv前面我们讨论的函数傅立叶级数都是在具有有限周期（尤其是以 为周期的函数）情形下进行展开的，但是无论是在理论上还是在实践中，对于非周期函数性质的讨论都是非常有必要的。v如何从周期函数的傅立叶级数展开扩展到非周期函数的傅立叶“级数”性质？或者是周期函数可以展开成为傅立叶级数的形式，那么是否非周期函数也可以展开成为傅立叶级数的形式呢？2v一维傅立叶变换的定义v定理：设函数设函数 ，即上的分即上的分段光滑函数，那么这个函数的傅立叶变换定义为：段光滑函数，那么这个函数的傅立叶变换定义为：v或者或者v条件部分也可以这样描述：条件部分也可以这样描述：设为实变量设为实变量

4、x的的连续且可积函数连续且可积函数1( )( )f xL Rdxxf）（1( )( )2ixff x edx2( )( )ixff x edx ( )f xv这种定义是有意义的，并且函数可以通过其这种定义是有意义的，并且函数可以通过其傅立叶反演而得到：傅立叶反演而得到：v或者或者v在上面的式子中知道：，并且会注意到实在上面的式子中知道：，并且会注意到实函数的傅立叶变换通常是复数形式函数的傅立叶变换通常是复数形式v)(xf1( )()2ixf xfed2( )( )ixf xfed1i )(xf( )( )( )fRiIv指数形式为：v其中：为幅值函数，称为函数（信号）的傅立叶谱而 称为相角傅立

5、叶谱的平方，称为是能量谱或者是功率谱()()()iffe22()()()fRI()fx1( )( )tan( )IR 22( )( )( )ERI题目：求门函数的傅立叶变换)(xf0( )0AxXf x其他v结果是：v其中用到了欧拉公式所以门函数所对应的傅立叶谱是：( )sin()iXAfX e)(xfsin()( )XfAXXcossini tetit-TT0Atx(t)X()02ATv二维傅立叶变换的定义v设函数设函数 是连续可积的，即即那么这个函数的傅立叶变换定义为：那么这个函数的傅立叶变换定义为：( , )f x y,Rf x y dxdy （）2()(,)(,)juxvyF u vf

6、x y edxdy 2()1222122(,)(,)(,)(,)(,)(,)(,)ta n(,)(,)(,)(,)ju xv yfxyFu ved u d vFu vRu vIu vIu vu vRu vEu vRu vIu v 幅 值相 角能 量v傅立叶变换的性质v（），线性性v（），可分离性v（），平移性v（），共轭性v（），尺度变换特性v（），卷积定理v（），arseval定理221( )()2f xdtfdReal Part, Imaginary Part, Magnitude, Phase, SpectrumReal part:Imaginary part:Magnitude-pha

7、se representation:Magnitude(spectrum):Phase(spectrum):PowerSpectrum:Mean of image/ DC component:Highest frequency component:“Half-shifted”Image:Conjugate Symmetry:Magnitude Symmetry:2D DFT Properties2D DFT PropertiesSpatial domain differentiation:Frequency domain differentiation:Laplacian:v三，一维离散傅立叶

8、变换（Discrete Fourier Transform）.v离散傅立叶变换的优点：（）比在时域直接对数字信号进行处理所需要的运算量要小；（）具有快速算法v如果将一维连续函数用取个间隔取样增量的方法进行离散化，变为离散函数v或者是：)( xfx)(xf0000 ( ), (), (2 ),(1) )f xf xx f xxf xNx 0( )()0,1 ,21f nf x n xnN v那么取样之后一维离散函数的离散傅立叶变换定义为：v反变换定义为：()fn1012( )( ) expNniunF ufnNN102( )( ) expNuiunfxF uN0,1, 2,10,1, 2,1nN

9、uN其 中 ，v注意（）上面两个公式是对离散后函数的准确的离散傅立叶变换；（）也是一个取个等量间隔取样之后的离散函数，它可以表示成为并且可以证明函数在空间域和频率域取样间隔和之间的关系是：（）离散傅立叶变换总是存在的，它并不需要考虑连续傅立叶变换所需要的可积的条件( )f n0()()FuFunuu( )F u)(xfx1uN x uv一维的v如果对：v令v那么，上述的公式变为：v1012( )( )expNniunF uf nNN2expiWN102( )( ) expNuiunfnF uN101()()Nu nnFufn WN101( )( )NunufnF u WNv写成矩阵的形式为：2

10、00000121012(1)(1)(0)(0)(1)(1)1(2)(2)(1)(1)NNNNN NWWWWFfWWWWFfFfNF Nf NWWWW2000001210(1)2(1)(1)(0)(0)(1)(1)(2)(2)(1)(1)NNNNN NWWWWfFWWWWfFfFf NF NWWWW A 4x4 imagejjjjjjjj111111111111336632452889863111111111111144XFFX Compute its 2D-DFT:3366324528898631Xjjjjjjjjjjjj111111111111554213463795542134161921

11、21jjjjjjjjjjjj81174459413611136134574811945235277MATLAB function: fft2lowest frequency componenthighest frequency componentjjjjjjjjjjjj81174459413611136134574811945235277XReal part:114546116135411423277realX874913013047895050imagX60.1306. 840. 685. 932.141132.14134 . 606. 860.1385. 939. 5339. 577mag

12、nitudeX51. 209. 247. 215. 100. 214. 300. 214. 347. 209. 251. 215. 119. 1019. 10phaseXImaginary part:Magnitude:Phase:Computation of 2D-DFT: Examplejjjjjjjjjjjjjjjjjjjj1111111111118117445941361113613457481194523527711111111111141244*FXF Compute the inverse 2D-DFT:X3366324528898631jjjjjjjjjjjj554213463

13、7955421341619212111111111111141MATLAB function: ifft2Centered RepresentationFrom Gonzalez & Woodsvuhighhighhighhigh(-N/2, N/2)(N/2, N/2)low(N/2, -N/2)(-N/2, -N/2)From Prof. Al BovikMATLAB function: fftshiftExample:Log-Magnitude VisualizationFrom Gonzalez & Woods)1log(rcs2D-DFTcenteredApply t

14、o Images2D-DFT centered log intensity transformationv并不是一种新的变换方式，它是离散傅立叶变换的一种算法，这种方法是建立在分析离散傅立叶变换中的多余运算的基础上，进而消除这些重复多余运算的思想下得到的，从而减少了运算，节省了时间，达到快速运算的目的v是以的组成状况而分为许多种算法，我们在这里只介绍为的整数次幂的算法v令v那么，一维离散傅立叶变换公式为：2e x pNiWN101()()Nu nNnFufn WN2 (0,1, 2,),0 1nNnn u其 中当 然分 别 为 ， ， 2，N-1vFFT是利用 的两个特点来提高计算效率的。v（

15、1） 的对称性 （2） 的周期性nNWnNW()*()NnnnNNNWWWnNW()nn NNNWWv在此基础上，将分解成为和对应的偶数和奇数两部分，n的取值范围由原来的到变为到v令v因此，离散傅立叶变换可以写成为下面的形式：(2 )fn(21)fn (0,1,2,3,1)2( )(21)gNnh nfn（n）=f(2n)( )f n1112200011222(21)0011220022( )( )( )( )(2 )(21)(2 )(21).NNNunununNNNnnnNNununNNnnNNununuNNNnnF uf n Wg n Wh n Wfn WfnWfn WfnWW111220

16、0011222(21)0011220022( )( )( )( )(2 )(21)(2 )(21).( ).( )NNNunununNNNnnnNNu nunNNnnNNununuNNNnnuNF uf n Wg n Wh n Wfn WfnWfn WfnWWG uWH uv其中的v因为所以v所以，我们得到2NuuNNWW 21NNW0 ,1,12Nu ()( ).( )2uNNF uG uWH u()()2NGuGu()( )2NH uH uv因此，一个求点的离散傅立叶变换可以被分为两个求点的离散傅立叶变换如果取，则上式变为：0818283808182838(0 )(0 ).(0 )(1)(

17、1).(1)( 2 )( 2 ).( 2 )(3)(3).(3)( 4 )(0 ).(0 )(5 )(1).(1)(6 )( 2 ).( 2 )(7 )(3).(3)FGWHFGWHFGWHFGWHFGWHFGWHFGWHFGWH这是上面公式的蝶型运算图v 由于 和 的过程仍然是常规的离散傅立叶变换,因此,也可以按照上述规则进行分解,记 为计算 的DFT运算,记 为计算 的DFT计算,用 表示 ， 为计算 的DFT计算 (4)H(4)G( )A u(2 )Gn( )B u(21)Gn ( )C u(2 )Hn( )D u(21)Hn08280828(0)(0). (0)(1)(1). (1)(

18、2)(0). (0)(3)(1). (1)GAW BGAW BGAW BGAW B08280828(0)(0). (0)(1)(1). (1)(2)(0). (0)(3)(1). (1)HCW DHCW DHCW DHCW Dv由于 现在都是两点的DFT了，因此不需要再分解，可以直接从原始数据计算得到( )A u( )Bu( )C u( )Du0808(0)(0). (4)(1)(0). (4)AfWfAfWf0808(0)(2). (6)(1)(2). (6)BfWfBfWf0808(0)(1). (5)(1)(1). (5)CfWfCfWf0808(0)(3). (7)(1)(3). (7

19、)DfWfDfWfvFFT的实现v二维离散Fourier变换v Mean of image/ DC component:Highest frequency component:“Half-shifted”Image:Conjugate Symmetry:Magnitude Symmetry:2D DFT PropertiesvBasics of filtering in the frequency domainv f (x,y)h(x,y)g(x,y)( , )( , )( , )g x yf x yh x yG(u,v)H(u,v)F(u,v) =DFTIDFTDFTIDFTDFTIDFTi

20、nput imageimpulse response(filter)output imagev Ideal lowpass, bandpass and highpasslow-frequency maskmid-frequency maskhigh-frequency maskvSome basic filters and their propertiesFrom Gonzalez & WoodsIdeal lowpass filtering with cutoff frequencies set at radii values of 5, 15, 30, 80, and 230, r

21、espectively2D-DFT Domain Filter DesignGaussian Lowpass FiltervD(u,v): distance from the origin of FTvParameter: =D0 (cutoff frequency)vThe inverse FT of the Gaussian filter is also a GaussianH(u,v) eD2(u,v)/22Image Enhancement in theFrequency Domain using GLPFImage Enhancement in theFrequency Domain

22、Butterworth Filter (lowpass)vHigh-frequency emphasis: Adding a constant to a highpass filter to preserve the low-frequency components.nvuDDvuH20),(/11),(（A）幅频特性 （B）相频特性由图可见，随n的增大，幅频特性在截止频率处下降得越快，则越接近于理想低通滤波器。Sharpening (Highpass) FilteringvImage sharpening can be achieved by a highpass filtering pro

23、cess, which attenuates the low-frequency components without disturbing high-frequency information.v Zero-phase-shift filters: radially symmetric and completely specified by a cross section.Hhp(u,v) 1 Hlp(u,v)Ideal Filter (Highpass)vThis filter is the opposite of the ideal lowpass filter.00),( if 1),( if 0),(DvuDDvuDvuHButterworth Filter (Highpas