一维FFT二维FFT.doc

摘要 本文介绍了一维FFT和二维FFT的产生背景及其计算方法，快速傅里叶变换与离散傅里叶变换相比，计算速度有了数量级上的提升，是信号与图像领域中，不可缺少的工具。文中还以对一幅二值图像的压缩为例，简单的体现了经傅里叶变换后的频域处理的应用。关键字：一维FFT 二维FFT 图像处理目录1 直接计算DFT算法存在的问题及改进途径31.1 DFT与IDFT的运算量32 快速傅里叶变换-FFT32.1 DFT中系数 的特性42.2基-2按时间抽取的FFT算法(DIT)(库利-图基算法)42.3蝶形信号流图52.4按时间抽取FFT算法的特点72.5二维FFT82.6 傅里叶变换的性质82.7 FFT与数字图像处理102.8应用11小结121 直接计算DFT算法存在的问题及改进途径1.1 DFT与IDFT的运算量设有限长序列,点数为N,即只在n=0N-1有值，其他n时，=0.我们把它看成周期为N的周期序列的一个周期，而把看成的以N为周期的周期延拓，即表示成 （1）离散傅里叶正变换（FFT）为 （2）反变换（IFFT）为 （3）其中为复数， 也为复数，所以DFT与IDFT二者计算量相同。由（2）和（3）可以看出，计算一个 (一个频率成分)值，假设则需要进行次复数乘法和(N-1)次复数加法，所以，要完成整个DFT运算，其计算量为：次复数乘法和次复数加法。一个复数乘法包括4个实数乘法和2个实数加法，如果换算成实数运算量，由(a+jb)(c+jd)=(ac-bd)+j(bc+ad)可以看出，每运算一个X(k)的值实数运算量为：4N次实数乘法和次实数加法，整个DFT实数运算量为：次实数相乘和次实数相加。由此看出：直接计算DFT时，乘法次数与加法次数都是和成比例的。当很大时，所需工作量是非常可观的。当N=1024点时，直接计算DFT需要1048576次的复乘运算，这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有十分苛刻的要求，因此迫切需要改进DFT的计算方法，以减少总的运算次数。2 快速傅里叶变换-FFT快速傅里叶变换起源于1965年，库利-图基在、Mathematic of Computation 杂志上发表了著名的“机器计算付里级数的一种算法”文章，提出一种快速计算DFT的方法和计算机程序-揭开了FFT发展史上的第一页。促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的条件,使DFT的运算大简化了。傅立叶变换在数字信号处理和数字图像处理中应用十分广泛。一般可采用DFT方法，将输入的数字信号首先进行DFT变换，在频域中进行各种有效的处理，然后进行DFT反变换，恢复为时域信号。FFT(fast Fourier transform)算法可大大减少计算次数，使计算量减少到只是直接用DFT所需计算量的一小部分。二维离散傅立叶变换很容易以一维的概念推广而得。在数字图像处理中，二维DFT被广泛地应用于图像增强、复原、编码各分类中。 FFT并不是一种新的变换形式,它只是DFT的一种快速算法.并且根据对序列分解与选取方法的不同而产生了FFT的多种算法.2.1 DFT中系数 的特性1)对称性 （4）(2)周期性 （5）(3)可约性 （6）由以上特性可得出： （7） （8） （9）利用这些特性，使DFT运算中有些项可以合并；利用对称性、周期性、可约性，可以将长序列的DFT分解为短序列的DFT。FFT正是基于这样的基本思路发展起来的。它的算法基本上可分为两类：按时间抽选(DIT)法和按频率抽选(DIF)法。2.2基-2按时间抽取的FFT算法(DIT)(库利-图基算法)算法原理：设输入序列长度为N=2M (M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。其中基数，为整数。若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到算法步骤：先将x(n)按n的奇偶分为两组，作变量置换:当为偶数时，令，当为奇数时，令，可得 r=0N/2-1; （10） r=0N/2-1; （11）则其DFT可化为两部分：前半部分： （12）后半部分： （13）代入DFT中 （14）可得 （15）同理可得后半部分： （16）这样，只要求出0到(N/2-1)区间的所有 和 值，即可求出0到(N-1)区间内所有 值，大大节省了运算。2.3蝶形信号流图上节所述内容可用蝶形流图表示为图1所示：X1(k)X2(k)图1将N=8点分解成2个4点的DFT的信号流图如图2：4点DFTx(0)x(2)x(4)x(6)4点DFTx(1)x(3)x(5)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶数序列奇数序列x1(r)x2(r)图2进一步分解可得x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)m=0m=1m=2图3由此可以将蝶形运算总结为图4所示：2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT两个2点DFT两个2点DFT两个2点DFT两个2点DFT两个4点DFT两个4点DFT两个N/2点DFTX1(k).X2(k)X(k)x(n)图4 由前面介绍的按时间抽取的FFT运算流图可见： 每级都由N/2个蝶形单元构成，因此每一级运算都需要N/2次复乘和N次复加（每个结加减各一次）。这样（N=2M)M级运算共需要： 复乘次数： （17） 复加次数： （18） 可以得出如下结论： 按时间抽取法所需的复乘数和复加数都是与 成正比。而直接计算DFT时所需的复乘数与复加数则都是与N2成正比.(复乘数md=N2,复加数ad=N(N-1)N2)2.4按时间抽取FFT算法的特点（1）原位运算 原位运算的结构，可以节省存储单元，降低设备成本。 定义：当数据输入到存储器以后，每一组运算的结果，仍然存放在这同一组存储器中直到最后输出。(2)码位倒读规则 以N=8为例，我们从输入序列的序号及整序规律得到码位倒读规则。由N=8蝶形图看出：原位计算时，FFT输出的X(k)的次序正好是顺序排列的，即X(0)X(7),但输入x(n)都不能按自然顺序存入到存储单元中，而是按x(0),x(4),x(2), x(6).的顺序存入存储单元即为乱序输入，顺序输出。这种顺序看起来相当杂乱，然而它是有规律的。即码位倒读规则。01234567000001010011100101110111自然顺序二进制码表示码位倒读码位倒置顺序00010001011000110101111104261537表一(3)整序重排子程序 具体执行时，只须将1与4对调送入，3与6对调送入，而0，2，5，7不变，仅需要一个中间存储单元。在实际运算时，先按自然顺序将输入序列存入存储单元，再通过变址运算将自然顺序变换成按时间抽取的FFT算法要求的顺序。变址的过程可以用程序安排加以实现-称为“整序”或“重排”（采用码位倒读）且注意： a.当n=n时，数据不必调换； b.当nn时，必须将原来存放数据x(n)送入暂存器R，再将x(n)送入x(n),R中内容送x(n).进行数据对调。 c.为了避免再次考虑前面已调换过的数据，保证调换只进行一次，否则又变回原状。nn时，调换。2.5二维FFT 容易将一维FFT变换为二维的情况： （19） 式中; 反变换： （20）2.6 傅里叶变换的性质（1）加法性质(对加法满足分配率，对乘法不满足)，时域或空域内的相加对应于频域内的相加。（2）位移性质(3）卷积性质，时域（或空域）中的卷积等价于频域的乘积。(4) 缩放性质,描述函数自变量尺度变化对其傅立叶变换的作用. 上式表明，尽管F(u,v)对无穷多个u,v重复出现，但只需根据一个周期里的N歌F（u,v）值，就可以得到f(x,y)。 如果f(x,y)是实函数，则它的傅里叶变换具有共轭对称性对于一维变换F(u)，周期性是指F(u)的周期长度为M，对称性是指频谱关于原点对称。 一幅二维图像的傅里叶频谱 中心化的傅里叶频谱 图5（6）旋转不变性（7）平均值，如果f(x,y)是一幅图像，在原点的傅里叶变换即等于图像的平均灰度级。（8）微分性质（9）分离性，如下图所示：图6（10）相关性理论 大小为MN的两个函数f(x,y)和h(x,y)的相关性定义为：f*表示f的复共轭。对于实函数，f*f相关定理 自相关理论 卷积和相关性理论总结：卷积是空间域过滤和频率域过滤之间的纽带，相关的重要应用在于匹配：确定是否有感兴趣的物体区域f(x,y)是原始图像h(x,y)作为感兴趣的物体或区域（模板）如果匹配，两个函数的相关值会在h找到f中相应点的位置上达到最大。2.7 FFT与数字图像处理图7 图7为两幅二值图像的傅里叶变换。2.8应用用MATLAB仿真实现对图8所示的二维离散数据的进行显示、傅里叶变换、能量谱的显示、频谱压缩、傅里叶反变换、还原显示等处理。 图8图9 经过对