FFT示意图

图像傅里叶变换冈萨雷斯版<图像处理>里面的解释非常形象：一个恰当的比喻是将傅里叶变换比作一个玻璃棱镜。

棱镜是可以将光分解为不同颜色的物理仪器，每个成分的颜色由波长（或频率）来决定。

傅里叶变换可以看作是数学上的棱镜，将函数基于频率分解为不同的成分。

当我们考虑光时,讨论它的光谱或频率谱。

同样, 傅立叶变换使我们能通过频率成分来分析一个函数。

Fourier theory讲的就是：任何信号（如图像信号）都可以表示成一系列正弦信号的叠加，在图像领域就是将图像brightness variation 作为正弦变量。

比如下图的正弦模式可在单傅里叶中由三个分量编码：频率f、幅值A、相位γ这三个value可以描述正弦图像中的所有信息。

1.frequencyfrequency在空间域上可由亮度调节，例如左图的frequency比右图的frequency 低……2.幅值magnitude（amplitude）sin函数的幅值用于描述对比度，或者说是图像中最明和最暗的峰值之间的差。

（一个负幅值表示一个对比逆转，即明暗交换。

）3.相位表示相对于原始波形，这个波形的偏移量（左or右）。

=================================================================一个傅里叶变换编码是一系列正弦曲线的编码，他们的频率从0开始（即没有调整，相位为0，平均亮度处），到尼奎斯特频率（即数字图像中可被编码的最高频率，它和像素大小、resolution有关）。

傅里叶变换同时将图像中所有频率进行编码：一个只包含一个频率f1的信号在频谱上横坐标f为f1的点处绘制一个单峰值，峰值高度等于对应的振幅amplitude，或者正弦曲线信号的高度。

如下图所示。

DC term直流信号对应于频率为0的点，表示整幅图像的平均亮度，如果直流信号DC=0就表示整幅图像平均亮度的像素点个数=0，可推出灰度图中，正弦曲线在正负值之间交替变化，但是由于灰度图中没有负值，所以所有的真实图像都有一个正的DC term，如上图所示。

离散时间信号的基2快速傅里叶变换FFT （时间抽取）蝶形算法实现一、一维连续信号的傅里叶变换连续函数f(x)满足Dirichlet （狄利克雷）条件下，存在积分变换：正变换：2()()()()j ux F u f x e dx R u jI u π+∞--∞==+⎰ 反变换：2()()j ux f x F u e du π+∞-∞=⎰其中()()cos(2)R u f t ut dt π+∞-∞=⎰，()()sin(2)I u f t ut dt π+∞-∞=-⎰定义幅值、相位和能量如下：幅度：1222()()()F u R u I u ⎡⎤⎡⎤=+⎣⎦⎣⎦ 相位：()arctan(()/())u I u R u ϕ= 能量：22()()(E u R u I u =+）二、一维离散信号的傅里叶变换将连续信号对自变量进行抽样得到离散信号（理想冲击抽样脉冲），利用连续信号的傅里叶变换公式得到离散时间傅里叶变换DTFT ；再利用周期性进行频域抽样，得离散傅里叶变换DFT （详情参考任何一本《数字信号处理》教材）。

DFT 变换如下：正变换：12/0()(),0,1,2,1N j ux Nx F u f x eu N π--===-∑。

反变换：12/01()(),0,1,2,1N j ux Nu f x F u ex N Nπ-===-∑。

DFT 是信号分析与处理中的一种重要变换，因为计算机等数字设备只能存储和处理离散数据（时域、频域）。

因直接计算DFT 的计算量大（与变换区间长度N 的平方成正比，当N 较大时，计算量太大），所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT 算法进行谱分析和信号的实时处理是不切实际的。

直到1965年发现了DFT 的一种快速算法（快速傅里叶变换，即FFT ）以后，情况才发生了根本的变化。

FFT 有时间抽取和频率抽取两种，下面介绍时间抽取FFT 。

三、时间抽取的基2快速傅里叶变换FFT令2j NN W eπ-=，则2jkm km NNWeπ-=称为旋转因子，把DFT 正变换改写为：1[][],0,1,1N km N k F m f k W m N -===-∑将函数记作x ，变换后为X ，则为：10[][],0,1,1N kmN k X m x k W m N -===-∑时间抽取的FFT 算法利用了旋转因子的三个性质：周期性、对称性和可约性。

图像处理1--傅⾥叶变换（FourierTransform）楼下⼀个男⼈病得要死，那间壁的⼀家唱着留声机；对⾯是弄孩⼦。

楼上有两⼈狂笑；还有打牌声。

河中的船上有⼥⼈哭着她死去的母亲。

⼈类的悲欢并不相通，我只觉得他们吵闹。

OpenCV是⼀个基于BSD许可（开源）发⾏的跨平台计算机视觉库，可以运⾏在Linux、Windows、Android和Mac OS操作系统上。

它轻量级⽽且⾼效——由⼀系列 C 函数和少量 C++ 类，同时提供了Python、Ruby、MATLAB等语⾔的接⼝，实现了和计算机视觉⽅⾯的很多通⽤算法。

OpenCV⽤C++语⾔编写，它的主要接⼝也是C++语⾔，但是依然保留了⼤量的C语⾔。

该库也有⼤量的Python、Java andMATLAB/OCTAVE（版本2.5）的接⼝。

这些语⾔的API接⼝函数可以通过在线获得。

如今也提供对于C#、Ch、Ruby,GO的⽀持。

所有新的开发和算法都是⽤C++接⼝。

⼀个使⽤CUDA的GPU接⼝也于2010年9⽉开始实现。

图像的空间域滤波：空间域滤波，空间域滤波就是⽤各种模板直接与图像进⾏卷积运算，实现对图像的处理，这种⽅法直接对图像空间操作，操作简单，所以也是空间域滤波。

频域滤波说到底最终可能是和空间域滤波实现相同的功能，⽐如实现图像的轮廓提取，在空间域滤波中我们使⽤⼀个拉普拉斯模板就可以提取，⽽在频域内，我们使⽤⼀个⾼通滤波模板（因为轮廓在频域内属于⾼频信号），可以实现轮廓的提取，后⾯也会把拉普拉斯模板频域化，会发现拉普拉斯其实在频域来讲就是⼀个⾼通滤波器。

既然是频域滤波就涉及到把图像⾸先变到频域内，那么把图像变到频域内的⽅法就是傅⾥叶变换。

关于傅⾥叶变换，感觉真是个伟⼤的发明，尤其是其在信号领域的应⽤。

⾼通滤波器，⼜称低截⽌滤波器、低阻滤波器，允许⾼于某⼀截频的频率通过，⽽⼤⼤衰减较低频率的⼀种滤波器。

它去掉了信号中不必要的低频成分或者说去掉了低频⼲扰。

实验一 FFT变换及其应用一、实验目的和要求1.在理论课学习的基础上，通过本次实验，加深对DFT原理的理解，懂得频域DFT与时域卷积的关系，进一步加深对DFT基本性质的理解；2.研究FFT算法的主要途径和编程思路，掌握FFT算法及其程序的编写过程，掌握最基本的时域基-2FFT算法原理及程序框图；3.熟悉应用FFT实现两个序列的线性卷积的方法，利用FFT进行卷积，通过实验比较出快速卷积优越性，掌握循环卷积和线性卷积两者之间的关系；4.熟悉应用FFT对典型信号进行频谱分析的方法，初步了解用周期图法作随机信号谱分析的方法，了解应用FFT进行信号频谱分析过程中可能出现的问题，以便在实际中正确应用FFT；5.掌握使用MATLAB等基本开发工具实现对FFT编程。

二、实验设备和分组1.每人一台PC机；2.Windows 2000/XP以上版本的操作环境；3.MatLab 6.5及以上版本的开发软件。

三、实验内容(一)实验准备1.用FFT进行谱分析涉及的基础知识如下：信号的谱分析就是计算信号的傅里叶变换。

若信号是模拟信号，用FFT进行谱分析时，首先必须对信号进行采样，使之变成离散信号，然后用FFT来对连续信号进行谱分析。

若信号本身是有限长的序列，计算序列的频谱就是直接对序列进行FFT运算求得X（k）,X(k)就代表了序列在[0,2]之间的频谱值。

幅度谱：相位谱：为避免产生混叠现象，采样频率fs 应大于2倍信号的最高频率fc ，为了满足采样定理，一般在采样之前要设置一个抗混叠低通滤波器。

用FFT 对模拟信号进行谱分析的方框图如下所示。

图1.1 FFT 对模拟信号进行谱分析的方框图2. 应用FFT 实现快速卷积涉及的基础知识如下： 一个信号序列x(n)与系统的卷积可表示为下式：Y(n)=x(n)*h(n)=∑+∞-∞=-m m n h m x )()(当是一个有限长序列，且0≤n ≤N-1时，有：Y(n)=∑-=-1)()(N n m n x m h此时就可以应用FFT 来快速计算有限长度序列的线性卷积。

fft 原理详解FFT 是离散傅立叶变换的快速算法，可以将一个信号变换到频域。

有些信号在时域上是很难看出什么特征的，但是如果变换到频域之后，就很容易看出特征了。

这就是很多信号分析采用FFT 变换的原因。

另外，FFT 可以将一个信号的频谱提取出来，这在频谱分析方面也是经常用的。

一个模拟信号，经过ADC 采样之后，就变成了数字信号。

采样定理告诉我们，采样频率要大于信号频率的两倍。

采样得到的数字信号，就可以做FFT 变换了。

N 个采样点，经过FFT 之后，就可以得到N 个点的FFT 结果。

为了方便进行FFT 运算，通常N 取2 的整数次方。

FFT的点数N：假设采样频率为Fs，信号频率F，采样点数为N。

那么FFT 之后结果就是一个为N 点的复数。

FFT后的幅度：每一个点就对应着一个频率点。

这个点的模值，就是该频率值下的幅度特性。

具体跟原始信号的幅度有什么关系呢？假设原始信号的峰值为A，那么FFT 的结果的每个点（除了第一个点直流分量之外）的模值就是A的N/2 倍。

而第一个点就是直流分量，它的模值就是直流分量的N 倍。

FFT后的频率分辨率：第一个点表示直流分量（即0Hz），而最后一个点N 的再下一个点（实际上这个点是不存在的，这里是假设的第N+1 个点，也可以看做是将第一个点分做两半分，另一半移到最后）则表示采样频率Fs，这中间被N-1 个点平均分成N 等份，每个点的频率依次增加。

例如某点n 所表示的频率为：Fn=(n-1)*Fs/N。

由上面的公式可以看出，Fn 所能分辨到频率为为Fs/N，如果采样频率Fs 为1024Hz，采样点数为1024 点，则可以分辨到1Hz。

1024Hz 的采样率采样1024 点，刚好是 1 秒，也就是说，采样1 秒时间的信号并做FFT，则结果可以分析到1Hz，如果采样 2 秒时间的信号并做FFT，则结果可以分析到0.5Hz。

如果要提高频率分辨力，则必须增加采样点数（必须增加有效的采样点数，通过在原来采样数据后补0的方法不能提高频率分辨率，只能使频谱图更加平滑而已），也即采样时间。

[实验2] 快速傅里叶变换 (FFT) 实现一、实验目的1、掌握FFT 算法和卷积运算的基本原理；2、掌握用C 语言编写DSP 程序的方法；3、了解利用FFT 算法在数字信号处理中的应用。

二、实验设备 1. 一台装有CCS 软件的计算机； 2. DSP 实验箱的TMS320C5410主控板； 3. DSP 硬件仿真器。

三、实验原理 （一）快速傅里叶变换傅里叶变换是一种将信号从时域变换到频域的变换形式，是信号处理的重要分析工具。

离散傅里叶变换（DFT ）是傅里叶变换在离散系统中的表示形式。

但是DFT 的计算量非常大， FFT 就是DFT 的一种快速算法, FFT 将DFT 的N 2步运算减少至 ( N/2 )log 2N 步。

离散信号x(n)的傅里叶变换可以表示为∑=-=10][)(N N nk N W n x k X ， Nj N e W /2π-=式中的W N 称为蝶形因子，利用它的对称性和周期性可以减少运算量。

一般而言，FFT 算法分为时间抽取（DIT ）和频率抽取（DIF ）两大类。

两者的区别是蝶形因子出现的位置不同，前者中蝶形因子出现在输入端，后者中出现在输出端。

本实验以时间抽取方法为例。

时间抽取FFT 是将N 点输入序列x(n) 按照偶数项和奇数项分解为偶序列和奇序列。

偶序列为：x(0), x(2), x(4),…, x(N-2)；奇序列为：x(1), x(3), x(5),…, x(N-1)。

这样x(n) 的N 点DFT 可写成：()()∑++∑=-=+-=12/0)12(12/02122)(N n kn NN n nkNW n x Wn x k X考虑到W N 的性质，即2/)2//(22/)2(2][N N j N j N W e e W ===--ππ因此有：()()∑++∑=-=-=12/02/12/02/122)(N n nkN k NN n nkN W n x WWn x k X或者写成：()()12()kN X k X k W X k =+由于X 1(k) 与X 2(k) 的周期为N/2，并且利用W N 的对称性和周期性，即：kNNkNWW-=+2/可得：()()12(/2)kNX k N X k W X k+=-对X1(k) 与X2(k)继续以同样的方式分解下去，就可以使一个N点的DFT最终用一组2点的DFT来计算。

fft采样正弦幅度一、傅里叶变换简介傅里叶变换是一种数学工具，可以将一个信号分解成一系列正弦和余弦函数的叠加。

它将信号从时域转换到频域，显示出信号的频率和幅度信息。

傅里叶变换在信号处理、图像处理、通信等领域有广泛应用。

二、正弦信号的特点正弦信号是一种周期性信号，具有固定的频率和幅度。

通过FFT采样正弦信号，可以得到其频率和幅度的准确数值。

三、FFT采样正弦信号为了演示FFT采样正弦幅度的过程，我们先构造一个频率为f的正弦信号，并设定采样率为Fs，采样点数为N。

然后对信号进行FFT 变换，得到频域的幅度谱。

1. 步骤一：生成正弦信号我们需要生成一个频率为f的正弦信号。

正弦信号的表达式为：y(t) = A * sin(2πft + φ)，其中A为幅度，f为频率，t为时间，φ为相位。

2. 步骤二：采样信号我们需要对生成的正弦信号进行采样，得到离散的信号序列。

采样率Fs表示每秒钟采集的样本数。

采样定理告诉我们，为了准确地重构信号，采样率至少要是信号最高频率的两倍。

3. 步骤三：FFT变换将采样得到的信号序列进行FFT变换，得到频域的幅度谱。

FFT变换后，信号的频率信息会分布在不同的频率点上，幅度信息则对应频率点的振幅。

四、分析FFT采样得到的幅度谱通过观察FFT采样得到的幅度谱，我们可以得到正弦信号的幅度信息。

幅度谱是一个关于频率的函数图像，横轴表示频率，纵轴表示幅度。

根据幅度谱的形状和数值，可以判断正弦信号的频率和幅度大小。

1. 幅度峰值幅度谱中最高的峰值对应着正弦信号的主频率，即信号的频率。

通过检测幅度峰值的位置和数值，可以准确地得到正弦信号的频率。

2. 幅度大小幅度谱中每个频率点对应的幅度大小反映了信号在该频率上的能量分布。

通过观察幅度大小的变化，可以判断信号的幅度大小。

五、实例分析假设我们采样了一个频率为100Hz，幅度为2的正弦信号，采样率为1000Hz，采样点数为1024。

经过FFT变换后，得到的幅度谱如下图所示：图1：幅度谱示意图根据图1，我们可以得到以下结论：1. 幅度峰值位于100Hz处，说明信号的频率为100Hz。

DIT-FFT 至简设计实现法1、 DIT-FFT 算法的基本原理有限长序列x n 的N 点DFT 定义为：X (k )=∑x (n )W N Kn N−1n=0,式中W N=e−j2πN。

DFT 在实际应用中很重要，但是如果直接按DFT 变换进行计算，当序列长度N 很大时，计算量会非常大，所需时间也很长，因此常用的是DFT 的一种快速计算算法，简称FFT 。

最常用的FFT 算法是基于时间抽取的基2-FFT 算法和基于频率抽取的基2-FFT 算法，这种算法的特点在于FFT 会把一次大的DFT 分割成几个小的DFT ，这样递归式地细分下去，例如有8个采样点的FFT ，首先会把最外层的8点运算分成两个4点FFT 的奇偶组合，第二层FFT 又分成四个两点FFT 的奇偶组合，并且由此计算出的频谱中很有趣的一点在于对于实数输出的数组，后面一半和前面一半正好对称相同，对于虚数输出的数组，后面一半是前面数组对称后乘上负1，因此，我们只需要算出FFT 的一半即可求出全部。

本设计讨论的是基于至简设计法实现按时间抽选的基2-FFT 算法（即DIF-FFT ）实现过程，支持N 由8到1024。

图 1按时间抽取的基2-FFT 算法蝶形运算流图（N=8）2、蝶形运算至简实现过程2、1 模块划分图 2蝶形运算模块框图本模块包括三个RAM模块（RAM1，RAM2，RAM3）与一个DFT模块，各模块功能如下：1）RAM1模块：在开始进行蝶形运算前，全部采样点（如图1所示的x(0)、x(4)、x(2)、x(6)、x(1)、x(5)、x(3)、x(7)）已经按照倒位序二进制的地址依次存储在RAM1模块中，即地址0保存了采样点x(0)，地址1保存了采样点x(4)。

选用双端口RAM1可以同时对两点采样数据(如图1的x（0）、x(4))进行读、写操作。

2）RAM2模块：RAM2模块也是采用双端口输入输出，可同时对两点数据进行读、写操作。

很多同学学习了数字信号处理之后，被里面的几个名词搞的晕头转向，比如DFT，DTFT，DFS，FFT，FT,FS等，FT和FS 属于信号与系统课程的内容，是对连续时间信号的处理，这里就不过多讨论，只解释一下前四者的关系。

首先说明一下，我不是数字信号处理专家，因此这里只站在学生的角度以最浅显易懂的性质来解释问题，而不涉及到任何公式运算。

学过卷积，我们都知道有时域卷积定理和频域卷积定理，在这里只需要记住两点：1.在一个域的相乘等于另一个域的卷积；2.与脉冲函数的卷积，在每个脉冲的位置上将产生一个波形的镜像。

(在任何一本信号与系统课本里，此两条性质有详细公式证明)下面，就用这两条性质来说明DFT，DTFT，DFS，FFT之间的联系：先看图片：首先来说图（1）和图（2），对于一个模拟信号，如图(1)所示，要分析它的频率成分，必须变换到频域，这是通过傅立叶变换即FT(Fourier Transform)得到的，于是有了模拟信号的频谱，如图(2)；注意1：时域和频域都是连续的！但是，计算机只能处理数字信号，首先需要将原模拟信号在时域离散化，即在时域对其进行采样，采样脉冲序列如图(3)所示，该采样序列的频谱如图(4)，可见它的频谱也是一系列的脉冲。

所谓时域采样，就是在时域对信号进行相乘，(1)×(3)后可以得到离散时间信号x[n]，如图(5)所示；由前面的性质1，时域的相乘相当于频域的卷积，那么，图(2)与图(4)进行卷积，根据前面的性质2知，会在各个脉冲点处出现镜像，于是得到图(6)，它就是图(5)所示离散时间信号x[n]的DTFT(Discrete time Fourier Transform)，即离散时间傅立叶变换，这里强调的是“离散时间”四个字。

注意2：此时时域是离散的，而频域依然是连续的。

经过上面两个步骤，我们得到的信号依然不能被计算机处理，因为频域既连续，又周期。

我们自然就想到，既然时域可以采样，为什么频域不能采样呢？这样不就时域与频域都离散化了吗？没错，接下来对频域在进行采样，频域采样信号的频谱如图(8)所示，它的时域波形如图(7)。

实验二ENVI图像增强与变换实验指导实验目的：通过上机操作，了解图像增强、图像变换几种遥感图象处理的过程和方法，加深对图象增强与变换处理的理解，熟悉ENVI软件中图像增强与变换的一些方法。

基础理论回顾与ENVI图像增强与变换预览：1.图像增强与变换的目的：图像增强的目的在于改善图像的显示质量，提高图像目视效果，突出所需要的信息，为进一步遥感目视判读做预处理工作。

2.图像增强的方法：3.实验内容：●影像融合：HSV变换融合、主成分变换融合●裁剪影像（以下实验的影像数据）●NDVI指数的计算●纹理分析●快速傅立叶滤波实验数据：影像融合：SPOT5全色影像（2_5_SPOT5）和多光谱影像(10_SPOT5）：表1 SPOT5 XI卫星有关参数介绍空间分辨率全色：2.5m（星下点）多光谱：10m（星下点）光谱响应范围全色：480-710nm1：790-890nm 近红外2：610-680nm 红波段3：500-590nm 绿波段4：1580-1750nm 短波红外其他实验：实验一几何配准后影像。

ETM+多波段数据：图 1实验方法与步骤：一、影像融合1.HSV融合ENVI中的融合方法：图2使用HSV融合可以进行RGB图像到HSV色度空间的变换，用高分辨率的图像代替颜色亮度值波段，并自动将色度和饱和度重采样到高分辨率像元尺寸，然后再将图像变换回RGB色度空间。

输出的RGB图像的像元将与高分辨率数据的像元大小相同。

1.从ENVI主菜单中，选择File →Open Image File 把SPOT5全色影像（2_5_SPOT5）和多光谱影像(10_SPOT5）都加载到可用波段列表中：图 32.从ENVI主菜单中，选择Transform → Image Sharpening → HSV，开始进行多光谱影像和全色影像的HSV 变换融合。

3.在Select Input RGB Input Bands对话框中，分别选择多光谱影像（10_SPOT5）影像的波段1、波段2和波段3，然后点击OK：图 44.打开High Resolution Input File（输入高分辨率数据）对话框，在Select Input Band列表中选择SPOT5全色影像（2_5_SPOT5），点击OK：图 5至此，完成了HSV变换融合的数据输入工作。

⼩学⽣都能看懂的FFT⼩学⽣都能看懂的FFT前⾔在创新实践中⼼偷偷看了⼀天FFT资料后，我终于看懂了⼀点。

为了给⼤家提供⼀份简单易懂的学习资料，同时也⽅便⾃⼰以后复习，我决定动⼿写这份学习笔记。

⾷⽤指南：本篇受众：如标题所⽰，另外也⾯向同我⼀样⾼中起步且⾮常菜的OIer。

真正的dalao请⽆视。

本篇⽬标：让⼤家（和不知道什么时候把FFT忘了的我）在没有数学基础的情况下，以最快的速度了解并会写 FFT。

因此本篇将采⽤尽可能通俗易懂的语⾔，且略过⼤部分数学证明，在严谨性上可能有⽋缺。

但如果您发现了较⼤的逻辑漏洞，欢迎在评论⾥指正！你⼀定听说过FFT，它的⾼逼格名字让⼈望⽽却步——“快速傅⾥叶变换”。

你可能知道它可以O(n log n)求⾼精度乘法，你想学，可是⾯对⼀堆公式，你⽆从下⼿。

那么欢迎阅读这篇教程！[Warning] 本⽂涉及复数（虚数）的⼀⼩部分内容，这可能是最难的部分，但只要看下去也不是⾮常难，请不要看到它就中途退出啊QAQ。

什么是FFT？快速傅⾥叶变换（FFT）是⼀种能在O(n log n)的时间内将⼀个多项式转换成它的点值表⽰的算法。

补充资料：什么是点值表⽰设A(x)是⼀个n−1次多项式，那么把n个不同的x代⼊，会得到n个y。

这n对(x,y)唯⼀确定了该多项式，即只有⼀个多项式能同时满⾜“代⼊这些x，得到的分别是这些y”。

由多项式可以求出其点值表⽰，⽽由点值表⽰也可以求出多项式。

（并不想证明，⼗分想看证明的同学请前往“参考资料”部分）。

注：下⽂如果不加特殊说明，默认所有n为2的整数次幂。

如果⼀个多项式次数不是2的整数次幂，可以在后⾯补0。

为什么要使⽤FFT？FFT可以⽤来加速多项式乘法（平时⾮常常⽤的⾼精度⼤整数乘法就是最终把x=10代⼊的多项式乘法）。

假设有两个n−1次多项式A(x)和B(x)，我们的⽬标是——把它们乘起来。

普通的多项式乘法是O(n2)的——我们要枚举A(x)中的每⼀项，分别与B(x)中的每⼀项相乘，来得到⼀个新的多项式C(x)。