傅里叶变换在图像处理中的应用研究.docx

《傅里叶变换在图像处理中的应用研究.docx》由会员分享，可在线阅读，更多相关《傅里叶变换在图像处理中的应用研究.docx（25页珍藏版）》请在课桌文档上搜索。

1、学科分类号：解南人女科技等诲本科生毕业论文题口（中文）：傅里叶变换在图像处理中的应用研（英文）：ThCAr）PIiCa1.ionOfFcuricrTransfonnInI1.nagCProcessing学生姓名：_学号一系部：专业年级：指导老师：职称：摘要关键词Abstract1Keywords11 .引言21.1 1本文的探讨背景21.2 探讨现状和前景21.3 本文探讨的思路及内容支配22 .傅里叶变换和图像处理技术32. 1傅里叶变换概述4连续傅里叶变换41.1.2 离散停里叶变换41.1.3 二维离散傅里叶变换41.1.4 1.4二维傅立叶变换的性质及其在图像中的表现41.2 图像处理

2、技术概述4模拟图像处理4数字图像处理41.3 图像傅里叶变换4图像傅里叶变换的物理意义4傅里叶变换在图像处理中的作用4傅里叶变换在图像压缩中的原理4傅里叶变换在图像压缩中的实现43 .图像傅里叶变换快速算法63.1 离散傅里叶变换运算量估计73.2 离散傅里叶变换的快速算法73.3 FFT算法的基本思想73.4 FFT的几种经典算法73.5 几种算法的比较73.6 算法的改进73.6.1 算法的改进原理43.6.2 算法中有待探讨的问题44 .基于MAT1.AB的图像离散傅立叶变换的探讨64. 1MAT1.AB软件概述75. 2MAT1.AB实现图像离散傅里叶变换76. 3MAT1.AB实现图

3、像压缩7参考文献8致谢8附录IO原创性声明11傅里叶变换在图象处理中的应用探讨摘要：傅立叶变换探讨是应用数学的一个Hi要方向，一个多世纪以来，傅立叶变换作为数学工具被快速的应用到图像和语音分析等众多领域，何立叶变换（FT）作为数字图像处理技术的基础，通过花时空域和频率域来回切换图像,时图像的信息特征进行提取和分折，简化计算工作砥，被誉为描述图像信息的其次种语言。本文试图班FMAT1.AB数学分析工具环境下从工程和试角度动身，较为直观地探讨了傅立叶变换在图像处理中的应用.同时，引用了一种改进的快速傅立叶变换（FFr）算法,为傅立叶变换在图像压缩中的实现供应了更为有利的条件，关键词:傅立叶变换；F

4、FTiMAT1.AB；图像处理：图象压缩TheApp1.icationofFOUrierTransformInImageProcessingAbstracttTheresearchofFouriertransformisanimportantdirectionoftheapp1.iedmathematics.Beingusedasthemathematics1.ooktheFouriertransformhasbeenquick1.yapp1.iedtoana1.yzetheimageandSPecCh.Etc.Fouriertransfbnn（E）nownasthesecond1.angua

5、getodescribetheimage,isthefoundationofimageprocessing,whichse1.ectsandana1.yzesIheinformationfeaturesbychangingtheimagefromtimespacedomainandfrequencydomain.Meanwhi1.e,itcansimp1.ifiedtheca1.cu1.ation.Fromtheang1.eoftheengineeringandexperimentationintheMAT1.AB,thepaperhasdiscussedtheapp1.icationofim

6、ageCompressionbasedontheFourierIransfbnn.Atthesametime,Iheartic1.eputforwardanewa1.gorithmofFFT.KeyWords：FourierTransfbnniFFTiAIgorithnuIinageProcessingJmageCompression1引言傅立叶变换是信号处理中最重要，应用最广泛的变换。从某种意义上来说.傅立叶变换就是函数的其次种描述语言。傅里叶变换理论及其物理说明两者的结合，对图像处理领域诸多问题的解决供应了有利的思路，它让我们从事物的另侧面来考虑问题，这样在分析某问题时就会从空域和频域两个

7、角度来考虑问题并来回切换，可以在空域或频域中思索的问题，利用频域中特有的性防，可以使图像处理过程简沽，有效，对于迂回解决图像处理中的难题特别有帮助，被广泛应用于数字图像处理中。1.1本文的探讨背景图像信息是人类相识世界的重要源泉。数字图像的数据星尤其巨大，同时由于受到通讯带宽和存储空间的限制，所以图像处理技术在数字电视、网络多媒体通信、会议电视、可视电话、遥感图像传输、图像数据库、自动指纹识别系统的指纹存储等应用中起着重要的作用。假如图像不经过处理就进行存储或者在网络上进行传输，将占用特别大的存储空间和网络带宽，必将限制数字图像在众多领域中的广泛应用。因此，图像处理技术的发展，对现代科学探讨有

8、深远影响。1.2探讨现状和前景傅里叶变换在物理学、电子类学科、数论、组合数学、信号处理、概率论、统计学、密码学、声学、光学、海洋学、结构动力学等领域都有着广泛的应用。尤其在信号处理中，博里叶变换的典型用途是将信号分解成附值重星和频率重So随着傅里叶变换在不同筑域不同范用内的延长以及涉及的范用之广，其发展趋势也愈显“数字化”，更是与计算机技术密不行分，目前,在信号处理与通讯领域里，运用最活跃的当属MAT1.AB其在数学类科技应用软件中在数值计算方面数数二，而当前傅里叶变换在通信象域中的应用乂是基于这数学软件上，做快速便里叶变换，并I1.除了数字信号处理之外，精彩的图形处理功能使其在数字图像处理技

9、术上解决了傅里叶变换在这些应用领域内的特定类型的问题，使傅里叶变换在通信中得以更号的应用与发展。1.3本文探讨的思路及内容支配主要探讨傅立叶变换在边缘增加，图像压缩，去噪声，纹理分析等图像处理和分析中的重要作用。基于MAT1.AB数学分析工具环境下从工程和试验角度动身,直观地探讨傅立叶变换在图像压缩、边缘增加、图像去噪中的应用。同时,引用了种改进的快速傅立叶变换算法.为傅立叶变换在图像乐缩的实现供应了更为有利的条件。图像片缩：傅立叶变换会使图像信号能量在空间重新分布，其中低频成分占据能量的绝大部分，而高嫉成分所占比重很小，能量分布集中，这就是数字图像在频率域压缩编码的理论依据。图像增加与图像去

10、噪：绝大部分噪音都是图像的高频重星，通过低通滤波器来滤除高频一噪声：边绿也是图像的高频重员，可以通过添加高频重量来增加原始图像的边缘。本文先从傅立叶变换的理论动身，找到了图像傅立叶变换的优势所在，以他里叶变换在图像压缩中的原理及应用为例做详细探讨说明。利用MAT1.AB实现基于傅里叶变换的图像压缩技术。2傅里叶变换和图像处理技术傅立叶变换作为种强大的数学工具被广泛的应用于图像和运动识别等领域中。傅立叶变换与傅立叶级数技术用于分析连续信号，然而在很多应用场合，信号本身就己经是离散的，在这种状况下须要利用傅立叶变换的离散形式来分析离散信号，即离散傅立叶变换（DFT）。D卜T很重要，是因为其实质是有

11、限长序列傅立叶变换的仃限点离散采样，从而开拓了频域离散化的道路，使数字信号处理可以在领域采纳数字运算的方法进行，增加了数字信号处理的敏捷性。更重要的是DFr仃多种快速算法，从而使信号的实时处理和设备的简化得以实现，使图像处理技术成为可能，这章对傅立叶变换作简洁的描述，同时绐出离散傅立叶变换的定义，并引出傅立叶变换在图像处理中应用。2.1 傅里叶变换概述1804年,法国科学家JJ氏J博里叶由于当时工业上处理金凤的须要，起先从事热流淌的探讨。他在题为热的解析理论一文中，发展了热流淌方程，并且指出如何求解。在求解过程中，他提出了随意周期函数都可以用三角缎数来表示的想法。他的这种思想，虽然缺乏严格的论

12、证，但对近代数学以及物理、工程技术却都产生了深远影响，成为傅里叶变换的起源。傅立叶变换是十九世纪数学界和工程界最辉煌的成果之,它本质上提出了一种与空间思维不同的频域思维方法，始终是信号处理领域最先备，应用最广泛的种分析手段，它也是线性系统分析的有利工具，特殊是被广泛的应用于数字图像处理中。在传统的数字图像处理中，傅立叶变换能够定量的分析诸如数字化系统，采样点，电子放大器，卷积滤波器，噪声，显示点等的作用，它在图像平滑，边缘增加，图像片缩，去噪声，税理分析等图像处理和分析中有重要作用。随着图像处理和识别技术的发展，傅立叶变换乂被应用于数字水印和特征提取及运动状态识别中。所谓的傅立叶变换就是以时间

13、为自变量的“信号”和以频率为自变量的“嫉谱“函数之间的某种变换美系。这种变换同样可以用在其他有关数学和物理的各种问题之中，并可以采纳其他形式的变员。当自变量“时间”或“须率”取连续时间形式和离散时间形式的不同组合，就可以形成各种不同的傅立叶变换对。傅立叶变换家族中的变换很多，主要包括：连续傅立叶变换，拉普拉斯变换.离散傅立叶变换，序列傅立叶变换，Z变换和离散何立叶变换，连续何立叶变换，连续傅立叶级数变换，连续拉普拉斯变换适用于连续时间信号的情形。离散傅立叶缎数变换，序列傅立叶变换，Z变换和离散傅立叶变换适用于离散时间信号的情形。连续傅里叶变换函数f()的傅里叶变换存在的条件是满意狄里必莱条件,

14、ni1.：具有有限个间断点：具有有限个极值点：确定可积。维连续傅里叶变换及反变换：单变量连续函数f(x)的傅里叶变换F(U)定义为：F(u)=j1f(x)ej2adA:其中了=T.X称为时域变量，u为频率变量。当绐定F(U),通过傅里叶反变换可以得到f(x)/(x)=F(uei2audu二维连续傅里叶变换及反变换：二维连续函数f(xy)的傅里叶变换F(U.、，)定义为：F(ii,v)=,f(x,y)ei2avyydxdy其中x.y为时域变量，u.v为频域变量。当给定F(u.v),通过傅里叶反变换可以得到f(.y):f(x,y)=F(u,I，把3“i”4以I，离散傅里叶变换离散时间信号X(n)的

15、连续何立叶变换定义为X(et,)x(n)eiun2.1)其反变换为：=fX()eiwd(2.2)2J.在此，我们用数字域频率来表示变换对,并旦式(2.2)是在X()的个周期内求枳分的。取样频率工与取样周期T的关系是=1/T:取样的角频率为Q,=2用取样数字频率为吗=2.式中X(e)是一个连续函数，不能干脆在计算机上做数字运算。为了在计算机上实现频谱分析，必需对的频谱作离散近似。有限长离散信号VO,n=O.1.N/的离散傅立叶变换(DFT)定义为X(k)=DFTx(n)=x(m)W,k=0.1.2,.N-I=M.通常称式(2.3)和(2.4)为博立叶变换对，的离散何立叶变换与变换区间长度N的取值

16、有关。将DFT变换的定义式写成矩阵形式，得到X=4X其中DFT的变换矩阵A为1IIIM.Wr1.二维离散傅里叶变换假如二维函数/(x,y)是连续可积的，并且尸(“，)是可积的，则FoUrier变换对：1.(Ay)=F(w,v)=f(x,y)ep-j211(tx+y)dxty(2.6)和F1(F(u,V)=fx,y)=f(t,v)exp/2;T(MX+y)duiv(2.7)对二维连续俾立叶变换在二维坐标上进行采样，对空域的取样间隔为A1.-和曲，时频域的取样间隔&/为v,它们的关系为：AU=一一和Av=一NAxNAy式中N是在图像一个维上的取样总数。那么，二维离散傅立叶变换对由式(28)和(2.

17、9)给出：r(u,v)=X八工，.F)exp-小(麻+vy)N2,8)N,-0,-O和/(y)=F(z,v)exp(j211(ux+vy)/N(2.9)Nu.ov式中M,V=0.1,.,N-1.,x,y=0.1.,N-1。二维离散傅里叶变换的性质及其在图像中的表现离散傅立叶变换之所以在图像处理中被广泛运用，成为图像处理的有利工具，就是因为它有良好的性质。现在对离散f立叶变换的若干性质作一简洁阐述。(1)变换域的周期性F(U+tnN,V+nN)=F(u.v)(2.10)因此，一个有界图像函数必需是周期性的。在有些状况下，需对x.y或u,v进行延拓,使图像达到一个周期N。(2)可分性FOUria变

18、换核是可分的，对称的，即cxp-j2*(,r+、)/jV)=cp(-j2ru/n)cp(-j211vy/N)这特性质可使二维傅立叶变换依次进行两次一维傅立叶变换来实现。这样，对于任何可分别性函数/(x.M=/COZiU)，则有FMV)=工(幻小块力心力=J(x)e)UMdx,fi(y)e-j2nydy=F1(u)F2(v)2.1.1.)因此，假如一个二维图像函数可被分为两个一维里量函数，则它的频i曾可被分解为两个一重量函数。)对于图像处理来说，就是先对“行”进行变换，再对“列”进行变换(或者先对“列”进行变换，再对“行”进行变换)(3)缩放性傅立叶变换的缩放性表明，对于两个标量和，有尸化(2.

19、12)abIab)式中，。两边的函数为对应的变换函数。式(3.9)说明,空域比例尺度的绽开相应于频域尺度的压缩，其幅值也相应的削减为原来的一。特殊是当a.b=-1.I的时,有f(-x.-y)F(-m.-v)(2.13)上式表明，离散傅立叶变换具有符号变更对应性。(4)位移性傅立叶变换时的位移定理由下式给出/(x-,1.,y-0)oF(u.v)exp-72(jtt,+vy0)/N(2.14)F(u-u0,v-vv)通常,图像频谱中心在点(0,0),为了便于视察,多将频谱的中心移至频域的中心。为此，令1,=%=N2,于是exp2”(4/+%,)/M=er=(_广，得到(2.16)/(x,)M-1.

20、严OF(U-Nt2,v-N2),即将图像阵元/(sy)乘以因子(-1)”后进行停立叶变换，其频谱中心变移位到了(N2,N2).(5)180度旋转可以证明，只需对幅图像连续做两次傅立叶变换，图像就成倒置的了，即FU1(X,刈=(,-y)2.17)(6)平均值二维离散函数的平均值定义为7(x,y)=jW(x,y)，另外，在二维作立叶变换定义式中，令=0,%=0,得FM=fy)=NU,y)=Nf(,y).(2.18)八-ONA优点：处理精度高,处理内容丰富，可进行困难的非线性处理，有敏捷的变通实力，一般来说只要变更软件就可以变更处理内容。缺点：处理速度还是个问题，特殊是进行困难的处理更是如此。其次是

21、辨别率及精度尚有确定限制。数字图像处理的主要方法A、空域法：这种方法是把图像看作是平面中各个像素组成的集合，然后干脆对这二维函数进行相应的处理。空域处理法主要有两大类：B.变换域法：数字图像处理的变换域处理方法是首先对图像进行正交变换，得到变换域系数阵列，然后再施行各种处理，处理后再反变换到空间域，得到处理结果。这类处理包括：滤波、数据压缩、特征提取等处理2.3 图像傅里叶变换般来说,进行图像处理的目的在于提高图像质量,使模糊的图像变得清荒：提取图像的有效特征，以便进行模式识别：通过图像变换和有效编码来压缩其频带或数据，以便传输和存信。对图像进行傅里叶变换，是将图像信号变换到频域进行分析，它不

22、仅反映图像的灰度结构特征，而旦能使很多算法易于实现。这种变换域分析在图像处理中是种重要有效的分析手段，这可从下列两点看出：D仃些处理方法干脆和滤波概念相联系,因而就需借助傅里叶变换把空间域信号映射到频率域上来分析。2）借用傅里叶变换，可简化计算或作某种特殊应用（如特征提取、数据J长缩等）。图像傅里叶变换的物理意义图像的频率是表征图像中灰度变更猛烈程度的指标，是灰度在平面空间上的梯度。如最大面积的沙漠在片灰度变更辍慢的区域，对应的场域值很低：而对于地表属性变更猛烈的边缘区域在图像中是片灰度变更拓烈的区域，对应的频率值很高。傅立叶变更在实际中有特别明显的物理意义，设是个能量有限的模拟信号，则其傅立

23、叶变换就表示的谱。从纯粹的数学意义来看，傅立叶变换是将个函数转换为系列周期函数来处理的。从物理效果来看，傅立叶变换是将图像从空间域变换到频率域,其逆变换是将图像从须率域转换到空间域。换句话说,傅立叶变换的物理意义是将图像的灰度函数分布变换为频率分布函数，傅立叶逆变换是将图像的频率分布函数变换为灰度分布函数。傅立叶变换可以得出信号在各个频率点上的强度。傅里叶变换在图像处理中的作用1 .图像增加与图像去噪绝大部分噪音都是图像的高频重任，通过低通滤波器来波除高频噪声：边缘也是图像的高频重量，可以通过添加高频重量来增加原始图像的边缘：2 .图像分割之边缘检测提取图像高频重量：3 .图像特征提取形态特征

24、：博里叶描述了纹理特征：干脆通过傅里叶系数来计算纹理特征其他特征：将提取的特征值进行傅里叶变换来使特征具有平移、伸缩、旋转不变性：4 .图像压缩可以干脆通过傅里叶系数来压缩数据：常用的离散余弦变换是傅立叶变换的实变换。傅里叶变换在图像压缩中的原理傅立叶变换用于图像压缩技术和其它的变换图像压缩编码技术样也可以分为三个步骤.如图2/所示。原始图像首先经过傅立叶变换得到变换系数。变换系数经过显:化，输出量化区间的索引符号流。量化操作是不行逆的，因此会导致信息损失.事实上假如不考虑信道噪声等的影响，则全部的信息损失均发生在量化器。量:化得到的符号流经过炳编码得到更为紧凑的比特流。烯编码是种以信息论为基

25、础的无损片缩，如HUffman编码、1.ZW编码与算术编码。解压与压缩相像，只是执行相反的操作。2-1基于(立叶变换的图像压缩框架原始图像经俾立叶变换会使图像信号能量在空间重新分布，其中低频成分占据能破的绝大部分，而高濒成分所占比亚很小，依据统计编码的原理，能量分布集中，端值最小，可实现平均码长最短，这就为数字图像在绘率域的压缩编码供应了理论依据。这样，傅立叶变换用于图像压缩的基本原理不妨这样阐述：将原来在空域描述的图像信号，变换到另外一些正交空间-频域中去，用变换系数即傅立叶系数来表示原始图像，并对系数进行编码。一般来说在变换域里描述要比在空域简洁，因为图像的相关性明显下降。尽管变换本身并不

26、带来数据压缩，但由于变换图像的能量大部分只集中于少数几个变换系数上，采纳试化和燧编码则可以有效地压缩图像的编码比特率。变换后图像能量更加集中，在量化和编码时，结合人类视觉心理因素等，采纳“区域取样或“阈值取样等方法，保留俾立叶变换系数中幅值较大的元素，进行量化编码，而大多数幅值小或某些特定区域的傅立叶变换系数将全部当作零处理。傅里叶变换在图像压缩中的实现下面将要介绍的就是用离散傅立叶变换压缩信号的例子.考虑由以下函数产生的图像信号，如图2-2所示，y(t)=ensin(2r)+2cos(4)+0.4sinfsin(1.()其中0Y211,首先在0Y211上把信号离散化为2=256个等间隔的样值

27、点，然后对采样点晃作离散傅立叶变换得$（八）.k=0.1.,255,其中较小的K为0.若要对信号进行30%的压缩.则令30%个最小的儿为0.然后对新的熊进行快速傅立叶逆变换,最终得到压缩后的信号.图2-4中所给出的是用离散傅立叶变换JK缩80%后的信号.2-3用卜Fr压缩80%后的信号既然离散傅立叶变换能够用于,图像压缩，那么探讨它的快速算法探讨就特别有意义，在下一章招转入对其快速算法的探讨。3图像傅里叶变换快速算法数字图像的数据狂相当巨大，耍在有限的时间内完成图像的压缩无疑是一件浩大的工程,干脆用DrT算法进行图像信号的实时处理是不切实际的.直到1965年发觉离散傅里叶变换的快速算法后，状况

28、才发生根本性转变.3.1 离散傅里叶变换的物理意义在上节的探讨中我们知道离散傅里叶变换对满意以下关系式:X(幻=DFTx(n)=x(n)w!:,k=0,1.2,.N-IoO.v(M)=1.1.)FX(k)=,n=O,1.”N-I式中，W,=e懵。一般状况下时间序列x()及其离散傅里叶变换X(灯是用更数表示的，由此可见干脆计卯DFT及IDFT须要N?次复数乘法及MNT)次复数加法。由于一次复数乘法要作4次实数.乘法和两次实数加法，一次复数加法要作2次实数加法，所以做一次疡散卿里.叶变换须要做4炉次实数乘法及N(4N-2)次实数加法。随若序列长度N的增大、运党次数耨猛烈地增加。离散傅里叶变换的应用

29、特别广泛，有必要在计算方法上寻求改进，使其运算次数大大削减。3.2 离散傅里叶变换的快速算法60年头中期，Codey和TUkCy提出了一种离散傅里叶变换的快速算法，它所需的运算量大约为(NIOaN”2次复数乘法和NIOg,N次麓数加法。因此，这种算法的出现，大大推动了离散傅里叶变换在各方面的应用。目前比较普遍运用的匏法，是基于C1.cy和TUkCy提出的基二党法，继CooICy和TUkCy之后，又有很多人致力于进一步削减DFr的运算量，提出了一些改进算法。其中最闻名的算法是1975年IBM公司的Shmuc1.Winograd博士提出的WFTA兑法(WinogaK1.FourierTransfo

30、rmA1.gorithm.简称WFTA算法)。本节招先主要探讨FFT的基本思想，介绍基2FFT和WFTA算法，同时筒要介绍一下在基二算法基础上发展起来的基四算法以及素因子算法。3.3 FFT算法的基本思想前面提到，N点DFT的豆乘次数等于N，明显，把N点DFT分解成几个较短的DFT,可使乘法次数大大削减。另外，旋转因子具有明显的周期性和对称性，其周期性表现为WrW=e-Cf1.=e*=眩(3.1)其对称性表现为-IW或者IWJFr=w；(3.2)（3.3）%2=-限FFT算法就是不断的把长序列的DFT分解成几个短序列的DFT,并利用Wa的周期性和对称性来削减DFT的运算次序。3.4 FFT算法

31、的几种经典算法(1)按时域抽取的基2FFT算法DIT-FFT这种算法是将输入序列在时域上的次序按偶数和奇数来抽取，对于随意一个N=2点长序列的DFT运算，可以采纳M次分解，最终分解成2点的DFT运算的组合，从而降低了运算量。设序列*)的长度为N,且满意N=2v(m为自然数，第一次分解：按”的奇偶把*)分解为两个N/2点的子序列N,NX1(/)=.r(2r),r=0J,.t-I和卬r)=x(2,+1),r=0,1,3-1则的DFT为XOI)=；川e+W：xi(r)W-tf(3.4)r-0r-O由于个=W品4/2一1A/2.1所以XG1.)=X1(r)W-1.r+W.v,(r)Wv=X1.()+X

32、2(k).k=0.1.N-Ir=1.=0(3.5)其中X#)和X2(k)分别为耳和.的N/2点DFT,由于Xt(k)和X2(k)均以N/2为周期，且W；T=-M,所以X（八）又可以表示为X(J1.)=X1（八）+1.*X2(k)k=0.1,.N/2-1(3.6)X(k+N4)=Xi(k)-WyX2(k),k=0r2-1.(3.7)这样，就将N点的DFT分解为两个N/2点的DFT和式(3.6)以及式(3.7)的运算.其次次分解：与第一次分解相同，将Wr)按奇偶分解成两个N/4长的子序列Nv,()三,(2),=0,1-i-1.和%(/)=卬2/),/=0,1,.,丁-1,那么仿照第一次的结果,X,

33、()=XX:)+y*,XJk).A=().1.,NIA-I(3.8)X.(k+N/4)=X.(k)-W,2X1.(k).k=0.,r4-1(3.9)用同样的方法可以计算出Xi(k)=Xf1.(k)+W*,iX6(k),k=0,/V4-I(3.10)X2(k+N/4)=Xs(k)-W*,2X6(k).k=0.1.N/4-1(3.11)这样，经过其次次分解，又将N/2点DFT分解为两个N/4点DFT。依此类推，经过MI次分解，最终招N点的DFT分解成N/2个2点DFT.下文将利用一个长度为8的DFT例子说明兑法的思想.当N=8时，依据上面的分析可知，计算可以分解为三步.图3-1、图3-2和图3-3

34、分别显示了这三步计算的详细过程，图3-4展示了整个运算流程。图（34）8点DFr的第,次时域抽取分解图图3-3）8点DFT的第三次时域抽取分解图图（3-4）8点DFT的运算流图与D1.T-FFT算法相对应，按领域抽取的拢2FFT算法一D1.F-FFT是把频域输出X(k)按k是偶数或是奇数,逐级分解成2点的D卜T运算，其原理与D1-FF算法相对偶，运算量也与DIT-FFr算法的相同.这里不再赘述，(2)基4FFT算法基本原理与基2FFT,算法大致相同.设N=2，的长序列，先将这样一个长度为N的DFT转换成四个氏度为N/4的DbT来计算，所需乘法次数和加法次数各为3N和3N/4,每个新的D卜丁乂可

35、以分解为四个长度为N/16的DFT,直至个简洁的蝶形为止。事实上，基4算法须要访问内存的次数也可以削减半，这样也有利于提高运算速度.但是基4算法点数的取值种类应当是基2FFT算法的半,这样使得基升,卜T的应用受到限制，而口基4FFT的蝶型图也比基2FF.算法要困难得多.其实从理论上说，基数越高总的计算量就越少，所以采纳基8和基16算法应当可以使运算次数进步削战，但削诚量会越来越不显著，而基8、基16算法的蝶形图会更加困难，硬件和软件实现也特别不便，所以向以来对它们的探讨与利用并不多.(3)素因子算法(PFA)索因子算法无论是基2还是基4算法,都对DH的长度N有特别大的限制，它们必需是2或4的N

36、次方.但是在实际应用往往是不行能的.由于这个缘由，后来发展的D卜T算法很好地解决了这个问题.当复合数N可以依据GOOd映射分解为几个互素因子的乘积时，其FFT变换就可以避开旋转因子的影响。PFA算法就是采纳了GOOd映射,将长度为N=NJN2的潍DkT转换成尺寸为NiN1的二维DkT.然后以行列方式沿每维果纳最有效的算法计算这个二维的DFo1.1 WkTA算法WFTA算法是建立在下标映射和数论上的套新奇的算法.它的主要思想是把个长度为N(N=MXM)离散傅立叶变换分解为两个互素,的小N因子的离散傅立叶变换.首先计算出M长度变换的结果，再利用结果进行M长度的计算.在实际应用中，若N较大,我们还可

37、以将N划分成多个互索小N的乘积小N”因子的DhI是指234.5.7.8.9和16点的DET。3.5 几种算法的比较为了仃更加直观地比较各种算法，下表总结了前面介绍到的各种算法的。性能以及适用范国表几种算法的比较算法适用范IS运算量内存量基-2FFT基UFFTN为2的整数次募最多的乘法次数.最少的加法次数.理论上N越大次数越少鼓少PFAN不为2的整数次零乘法次数和加法次数几乎于基TFFT和WK1.A间.详细状况现N的组成因子而定较少WFTA特殊适合计算实数数据.最少的乘法次数.最多的加法次数最少除上表的总结以外，我们还将上表作以下两项说明:如采纳超大规模集成电路的实现作为目标，则基-2FFT,基

38、-4FFT是较好的选择，它具有简洁而规则的结构和便利的存储模式，运用T向量机处理：(2)对于乘法速度慢而加法速度快的运算器来说，采纳WFTA算法能得到明显的效果，而且WFTA特殊适合计兑实数输入的DFT。每一种算法都有各自不同的特点，在实际应用中我们可以依据详细状况选择适用的算法，甚至把算法结合起来运用，并且将之进行改进.3.6 算法的改进前面提到基2FFT,算法结构简洁而WFTA算法运兑量少,人们自然会问为了得到一种较好的FFT.算法，是否可以将FFT中的部分运算通过调用结构简洁的基2FFT.算法来完成而其它部分运算通过调用WFTA算法来完成呢?答案是确定的!下文将结合基2FFT兑法和WFT

39、A两种算法，对FFT进行了改进，从而使得新的FFT兑法运算量少，结构简洁.算法的改进原理首先回忆一下战2-FFT的方法，它是将一个长度较大的DFr逐步分解为长度小的DFT,每一次的迭代中，DFT的长度变为上一层的一半,迭代的结果是，把这个长度为N的DFT分解为N/2个计算两点的DFT这就是基2-FFT克法的思想方法,其分解过程有NIog,N步.然而，在实际计算中，我们的目标是得到长度为N的DFE因此在计算过程中就必需从思想方法的最底层起先,先计算最终层中N/2个计算两点的DkT:再依据思想方法的逆向过程把计算好的结果组合起来，得到长度为4的DFT.长度为4的DFT乂组合成长度为8的DkT.依此

40、类推，算法执行到最终步的时候，两个长度为N/2的D卜T就通过乘法和加法计算组合成长度为N的DFT这就是我们想要得到的结果。改进的算法就是把WFTA算法插入到基2-FFT算法的过程中，也就是说，让WETA算法代替其中部分的基2-FF算法.改进算法的基本思路为如下：基2-FFT算法分解的过程共有1.og2N步，当按基2小卜丁算法分解1.og,N-4步时，其计算有N/16个长度为16的DFT.由于在基-2卜卜T.算法中每次迭代分解出来的DFr在每组之间是相互独立的，所以我们可以引入WFA算法计算这些长度为16的DIT.鉴于计算过程与算法思想分析的过程刚好是互逆的，我们先调用16点的WFTA的算法把数

41、据先计算好,再将结果依据基2FFT算法进行计算组合，最终得到长度为N的DET.改进的算法实行这样的组合方式的缘由是，假如计算长度N较大,那么WFTA算法结构就会变得相当困难，所以在此仅采纳16点WFTA的算法与基-2FET结合.这样做既可以保持算法的简洁结构，也可以利用到WFIA的算法在乘法上的优势。下面以N=32为例子、说明改进算法。把32个数据按它们的下标分为奇、偶两组，两组分别先进行16点的WFTA计算，结果分别送回原址，再对结果再进行基2FFT,计算流程如图3-5中,右边的部分其实就是基2FFT最终层的蝶型图，而左边则为WFTA算法的调用.详细过程如图3-5所示.综上所述，整个算法可分

42、为以下几步：第步，输入数据到数组DATA中，推断数据的个数N是否为2的整数欢聚.假如不是则补零，使计算的长度为2的整数次案.其次步，依据N/16的频率抽出数据，组成N/I6个数组，每个数组有16个数字.第三步，分别对这些数组进行16点的AkTA计算，结果依次放回到DATA中.第四步，对数组DNrA进行基2FFT计算.第五步，输出结果图3-6为整个算法的流程图图（3-5）改进算法N=32的蝶形图图3-6改进后的算法潦程图改进的算法只适用于N=2，的状况,由丁克法是由基2FFT律法和WFTA结合的,所以运算员仍旧满意基2FFT算法的运算量，但是在最终的两步迭代过程中乘法次数有所削减.但当N很大时，

43、例如N=600,采纳以上算法，则需补零延长到1024,运算后再舍去后面的424个数据，这样一来就带来了大量的多余运算，使得运算过增加，另方面使得频谱在确定程度上有误差，补零个数楂多，误差相对越大。算法中有待探讨的问题从上面的分析可以看到，这种新的算法在确定程度上削诚了DET的运算量，但这种改进的算法却不能够很好的解决N不是2的整次器的状况。为了解决这个问题，我们不妨在算法中引入素因子算法（PFA）。对于个长度为N=2MWDFT.详细方法如下：利用PFA算法，先将N=2XN长度的D卜T分解，按M间隔抽取.得到2组数据进行计算，再按2间隔抽取，之后进行计算，计算结果分别送回原址;其次步，利用改进算法进行计算.假如M为几个互素因子的乘积，则可以按PFA算法接着分解计算.将基2FF.PFA和WFTA三者在机结合，使得卜卜T运算效率得到提高的同时，还增加了算法的运用范闱，但是假如将三者结合，算法结构会变得困难,增加了实现的难度。4基于MAT1.AB的图像离散傅里叶变换的探讨MAT1.AB是Mathworks公司推出的套功能强大的工程设计和系统仿真软件包。它具备强大的数值计算和分析实力，很多困难的问题只需短短的几行代码就可实现。本章先应用MAT1.AB分析图像，紧接着在此基础上说明图像压缩的基本问