自-快速傅里叶变换的通俗解释
2012-7:5 上传下载附件 (585 KB） 一、傅立叶变换的由来关于傅立叶变换,无论是书本还是在网上可以很容易找到关于傅立叶变换的描述,但是大都是些故弄玄虚的文章，太过抽象,尽是一些让人看了就望而生畏的公式的罗列，让人很难能够从感性上得到理解，最近,我偶尔从网上看到一个关于数字信号处理的电子书籍，是一个叫Seen W. Smth, Ph.D.外国人写的，写得非常浅显,里面有七章由浅入深地专门讲述关于离散信号的傅立叶变换，虽然是英文文档,我还是硬着头皮看完了有关傅立叶变换的有关内容，看了有茅塞顿开的感觉,在此把我从中得到的理解拿出来跟大家分享,希望很多被傅立叶变换迷惑的朋友能够得到一点启发.要理解傅立叶变换，确实需要一定的耐心,别一下子想着傅立叶变换是怎么变换的，当然,也需要一定的高等数学基础,最基本的是级数变换,其中傅立叶级数变换是傅立叶变换的基础公式。二、傅立叶变换的提出让我们先看看为什么会有傅立叶变换?傅立叶是一位法国数学家和物理学家的名字,英语原名是Jean Bapist Jseph Fourir（1768-180)，Forir对热传递很感兴趣，于1807年在法国科学学会上发表了一篇论文，运用正弦曲线来描述温度分布，论文里有个在当时具有争议性的决断:任何连续周期信号可以由一组适当的正弦曲线组合而成。当时审查这个论文的人，其中有两位是历史上著名的数学家拉格朗日(Josep Lou Lgn, 1736-181）和拉普拉斯（PrrSon e Lapace, 4-82)，当拉普拉斯和其它审查者投票通过并要发表这个论文时,拉格朗日坚决反对，在近50年的时间里，拉格朗日坚持认为傅立叶的方法无法表示带有棱角的信号,如在方波中出现非连续变化斜率。法国科学学会屈服于拉格朗日的威望,拒绝了傅立叶的工作，幸运的是，傅立叶还有其它事情可忙,他参加了政治运动，随拿破仑远征埃及，法国大革命后因会被推上断头台而一直在逃避。直到拉格朗日死后15年这个论文才被发表出来。谁是对的呢？拉格朗日是对的:正弦曲线无法组合成一个带有棱角的信号。但是,我们可以用正弦曲线来非常逼近地表示它,逼近到两种表示方法不存在能量差别,基于此,傅立叶是对的。为什么我们要用正弦曲线来代替原来的曲线呢？如我们也还可以用方波或三角波来代替呀,分解信号的方法是无穷的，但分解信号的目的是为了更加简单地处理原来的信号。用正余弦来表示原信号会更加简单，因为正余弦拥有原信号所不具有的性质：正弦曲线保真度。一个正弦曲线信号输入后，输出的仍是正弦曲线，只有幅度和相位可能发生变化，但是频率和波的形状仍是一样的。且只有正弦曲线才拥有这样的性质,正因如此我们才不用方波或三角波来表示。三、傅立叶变换分类根据原信号的不同类型，我们可以把傅立叶变换分为四种类别:1非周期性连续信号傅立叶变换(orier Trsorm)2周期性连续信号傅立叶级数(Fouie Series)3非周期性离散信号离散时域傅立叶变换(Dirte Tme FourierTransfom）4周期性离散信号离散傅立叶变换(DisreteFuie Trsfor)下图是四种原信号图例这四种傅立叶变换都是针对正无穷大和负无穷大的信号，即信号的的长度是无穷大的，我们知道这对于计算机处理来说是不可能的，那么有没有针对长度有限的傅立叶变换呢？没有。因为正余弦波被定义成从负无穷小到正无穷大,我们无法把一个长度无限的信号组合成长度有限的信号。面对这种困难，方法是把长度有限的信号表示成长度无限的信号，可以把信号无限地从左右进行延伸，延伸的部分用零来表示,这样，这个信号就可以被看成是非周期性离解信号，我们就可以用到离散时域傅立叶变换的方法。还有，也可以把信号用复制的方法进行延伸,这样信号就变成了周期性离解信号,这时我们就可以用离散傅立叶变换方法进行变换。这里我们要学的是离散信号，对于连续信号我们不作讨论,因为计算机只能处理离散的数值信号,我们的最终目的是运用计算机来处理信号的。但是对于非周期性的信号，我们需要用无穷多不同频率的正弦曲线来表示,这对于计算机来说是不可能实现的。所以对于离散信号的变换只有离散傅立叶变换（DT）才能被适用，对于计算机来说只有离散的和有限长度的数据才能被处理，对于其它的变换类型只有在数学演算中才能用到，在计算机面前我们只能用F方法，后面我们要理解的也正是T方法。这里要理解的是我们使用周期性的信号目的是为了能够用数学方法来解决问题,至于考虑周期性信号是从哪里得到或怎样得到是无意义的。每种傅立叶变换都分成实数和复数两种方法，对于实数方法是最好理解的，但是复数方法就相对复杂许多了,需要懂得有关复数的理论知识，不过，如果理解了实数离散傅立叶变换(real DT）,再去理解复数傅立叶就更容易了,所以我们先把复数的傅立叶放到一边去，先来理解实数傅立叶变换，在后面我们会先讲讲关于复数的基本理论,然后在理解了实数傅立叶变换的基础上再来理解复数傅立叶变换。还有,这里我们所要说的变换(transor)虽然是数学意义上的变换，但跟函数变换是不同的,函数变换是符合一一映射准则的，对于离散数字信号处理(P),有许多的变换：傅立叶变换、拉普拉斯变换、变换、希尔伯特变换、离散余弦变换等，这些都扩展了函数变换的定义，允许输入和输出有多种的值,简单地说变换就是把一堆的数据变成另一堆的数据的方法。四、傅立叶变换的物理意义傅立叶变换是数字信号处理领域一种很重要的算法。要知道傅立叶变换算法的意义，首先要了解傅立叶原理的意义。傅立叶原理表明:任何连续测量的时序或信号,都可以表示为不同频率的正弦波信号的无限叠加。而根据该原理创立的傅立叶变换算法利用直接测量到的原始信号,以累加方式来计算该信号中不同正弦波信号的频率、振幅和相位。和傅立叶变换算法对应的是反傅立叶变换算法。该反变换从本质上说也是一种累加处理,这样就可以将单独改变的正弦波信号转换成一个信号。因此，可以说,傅立叶变换将原来难以处理的时域信号转换成了易于分析的频域信号(信号的频谱），可以利用一些工具对这些频域信号进行处理、加工。最后还可以利用傅立叶反变换将这些频域信号转换成时域信号。从现代数学的眼光来看,傅里叶变换是一种特殊的积分变换。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分。在不同的研究领域,傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。在数学领域，尽管最初傅立叶分析是作为热过程的解析分析的工具，但是其思想方法仍然具有典型的还原论和分析主义的特征。"任意"的函数通过一定的分解,都能够表示为正弦函数的线性组合的形式,而正弦函数在物理上是被充分研究而相对简单的函数类:1 傅立叶变换是线性算子,若赋予适当的范数，它还是酉算子;2 傅立叶变换的逆变换容易求出,而且形式与正变换非常类似;3.正弦基函数是微分运算的本征函数,从而使得线性微分方程的求解可以转化为常系数的代数方程的求解.在线性时不变杂的卷积运算为简单的乘积运算,从而提供了计算卷积的一种简单手段;. 离散形式的傅立叶的物理系统内，频率是个不变的性质,从而系统对于复杂激励的响应可以通过组合其对不同频率正弦信号的响应来获取;5. 著名的卷积定理指出：傅立叶变换可以化复变换可以利用数字计算机快速的算出（其算法称为快速傅立叶变换算法（FT)。正是由于上述的良好性质，傅里叶变换在物理学、数论、组合数学、信号处理、概率、统计、密码学、声学、光学等领域都有着广泛的应用。五、图像傅立叶变换的物理意义图像的频率是表征图像中灰度变化剧烈程度的指标，是灰度在平面空间上的梯度。如:大面积的沙漠在图像中是一片灰度变化缓慢的区域,对应的频率值很低；而对于地表属性变换剧烈的边缘区域在图像中是一片灰度变化剧烈的区域，对应的频率值较高。傅立叶变换在实际中有非常明显的物理意义，设f是一个能量有限的模拟信号，则其傅立叶变换就表示f的谱。从纯粹的数学意义上看,傅立叶变换是将一个函数转换为一系列周期函数来处理的。从物理效果看,傅立叶变换是将图像从空间域转换到频率域，其逆变换是将图像从频率域转换到空间域。换句话说，傅立叶变换的物理意义是将图像的灰度分布函数变换为图像的频率分布函数,傅立叶逆变换是将图像的频率分布函数变换为灰度分布函数。傅立叶变换以前,图像(未压缩的位图）是由对在连续空间(现实空间)上的采样得到一系列点的集合，我们习惯用一个二维矩阵表示空间上各点,则图像可由=f(x，)来表示。由于空间是三维的，图像是二维的，因此空间中物体在另一个维度上的关系就由梯度来表示，这样我们可以通过观察图像得知物体在三维空间中的对应关系。为什么要提梯度?因为实际上对图像进行二维傅立叶变换得到频谱图,就是图像梯度的分布图，当然频谱图上的各点与图像上各点并不存在一一对应的关系，即使在不移频的情况下也是没有。傅立叶频谱图上我们看到的明暗不一的亮点,实际上图像上某一点与邻域点差异的强弱，即梯度的大小,也即该点的频率的大小(可以这么理解，图像中的低频部分指低梯度的点，高频部分相反）。一般来讲，梯度大则该点的亮度强,否则该点亮度弱。这样通过观察傅立叶变换后的频谱图，也叫功率图,我们首先就可以看出,图像的能量分布,如果频谱图中暗的点数更多,那么实际图像是比较柔和的（因为各点与邻域差异都不大,梯度相对较小），反之，如果频谱图中亮的点数多，那么实际图像一定是尖锐的，边界分明且边界两边像素差异较大的。对频谱移频到原点以后,可以看出图像的频率分布是以原点为圆心,对称分布的。将频谱移频到圆心除了可以清晰地看出图像频率分布以外,还有一个好处，它可以分离出有周期性规律的干扰信号,比如正弦干扰，一副带有正弦干扰,移频到原点的频谱图上可以看出除了中心以外还存在以某一点为中心,对称分布的亮点集合，这个集合就是干扰噪音产生的，这时可以很直观的通过在该位置放置带阻滤波器消除干扰。另外我还想说明以下几点：1、图像经过二维傅立叶变换后，其变换系数矩阵表明：若变换矩阵n原点设在中心，其频谱能量集中分布在变换系数短阵的中心附近（图中阴影区)。若所用的二维傅立叶变换矩阵的原点设在左上角,那么图像信号能量将集中在系数矩阵的四个角上。这是由二维傅立叶变换本身性质决定的。同时也表明一股图像能量集中低频区域。2、变换之后的图像在原点平移之前四角是低频,最亮，平移之后中间部分是低频,最亮，亮度大说明低频的能量大（幅角比较大）。六、一个关于实数离散傅立叶变换（Real FT）的例子先来看一个变换实例，一个原始信号的长度是6，于是可以把这个信号分解个余弦波和9个正弦波（一个长度为N的信号可以分解成/21个正余弦信号，这是为什么呢?结合下面的1个正余弦图,我想从计算机处理精度上就不难理解，一个长度为N的信号,最多只能有/2+个不同频率，再多的频率就超过了计算机所能所处理的精度范围）,如下图:个正弦信号：把以上所有信号相加即可得到原始信号，至于是怎么分别变换出种不同频率信号的,我们先不急，先看看对于以上的变换结果,在程序中又是该怎么表示的，我们可以看看下面这个示例图：上图中左边表示时域中的信号，右边是频域信号表示方法，从左向右表示正向转换(Fad DT)，从右向左表示逆向转换(Invese DFT),用小写表示信号在每个时间点上的幅度值数组,用大写X表示每种频率的副度值数组, 因为有/2+种频率，所以该数组长度为N2+，数组又分两种，一种是表示余弦波的不同频率幅度值: ,另一种是表示正弦波的不同频率幅度值：m X，是实数(Ral)的意思，I
