傅立叶级数和傅立叶变换

由于傅立叶变换在科学领域计算机领域，关键是在实时渲染的时候经常会碰到，这里给自己普及一下相关的知识。

 

 

傅立叶级数：

它主要的价值在于对一些特殊的方程的一种特殊求解方式，我们解方程都喜欢算出一个数字来，但是人家解出来的结果用三角级数(傅立叶级数)来表示。这是不是预示着世界的基本组成元素为正弦波呢？

公式：

如果说方程是一条线的话，那么三角级数，就相当于用各种不同层次的波来描述一个特定的方程的线。还有一些高深的看不懂的理论和公式，不去管它理解其作用就行。

（拉格朗日坚持认为傅立叶的方法无法表示带有棱角的信号，拉格朗日是对的：正弦曲线无法组合成一个带有棱角的信号。但是，我们可以用正弦曲线来非常逼近地表示它，逼近到两种表示方法不存在能量差别，基于此，傅立叶是对的。拉格朗日好厉害，死后15年傅里叶的论文才被发表，但是人家说的确实是对的，所以拉格朗日厉害。傅里叶也厉害，虽然不对，但是很有用）

为什么我们要用正弦曲线来代替原来的曲线呢？如我们也还可以用方波或三角波来代替呀，分解信号的方法是无穷的，但分解信号的目的是为了更加简单地处理原来的信号。用正余弦来表示原信号会更加简单，因为正余弦拥有原信号所不具有的性质：正弦曲线保真度。一个正弦曲线信号输入后，输出的仍是正弦曲线，只有幅度和相位可能发生变化，但是频率和波的形状仍是一样的。且只有正弦曲线才拥有这样的性质，正因如此我们才不用方波或三角波来表示。三角级数就是正弦级数就是傅里叶级数。

 

傅里叶变换 ：

傅里叶变换能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。如果说傅里叶级数就是让三角级数成为函数的解的话，傅里叶变换就是求解的变换过程，所以傅里叶变换不止一种。

根据原信号的不同类型，我们可以把傅立叶变换分为四种类别：

1.非周期性连续信号傅立叶变换（Fourier Transform）：

2.周期性连续信号傅立叶级数(Fourier Series) ：

3.非周期性离散信号离散时域傅立叶变换（Discrete Time Fourier Transform）：

4.周期性离散信号离散傅立叶变换(Discrete Fourier Transform) ：

 

第四种就是咱们要用的DFT，FFT是在这个基础上进行对称性研究提升其计算效率的。

这四种傅立叶变换都是针对正无穷大和负无穷大的信号，即信号的的长度是无穷大的，但是我们要处理有限的信号怎么办呢？可以把有限信号的左右无限延伸用0表示，这样就跟第三种非周期性离散信号一样了。如果把有限信号进行周期性复制，将就跟第四种周期性离散信号一样了。

又由于非周期性的信号，我们需要用无穷多不同频率的正弦曲线来表示，其实这里有一个相对概念，就是周期性。什么是周期性？就是隔一段时间重复一次被，但是隔一秒和隔1一个世纪的概念是也是不一样的，而理论上的非周期性就是它要无穷多时间才能被重复，或者说仍旧不能重复。所以，我们计算机能够处理的就只有第四种了DFT，由于计算能力的要求，即便是周期性我们也要控制周期长度。其它类型只能人算，不适用。

 

傅立叶变换的物理意义：

傅里叶级数的本质咱已经很清楚了，就是用正弦表示其它的函数。而根据该原理创立的傅立叶变换算法利用直接测量到的原始信号，以累加方式来计算该信号中不同正弦波信号的频率、振幅和相位。试出一组解来，这就叫傅里叶变换。与此相反的是傅立叶变换算法的逆运算，该反变换从本质上说也是一种累加处理，这样就可以将单独改变的正弦波信号转换成一个信号。立叶变换将原来难以处理的时域信号转换成了易于分析的频域信号（信号的频谱），可以利用一些工具对这些频域信号进行处理、加工。最后还可以利用傅立叶反变换将这些频域信号转换成时域信号。

 

图像傅立叶变换的物理意义：

灰度也可认为是亮度，简单的说就是色彩的深浅程度。图像的频率是表征图像中灰度变化剧烈程度的指标，是灰度在平面空间上的梯度。灰度是描述图像中色彩的程度，而图像频率是描述当前像素点的灰度与旁边的比较。从物理效果看，傅立叶变换是将图像从空间域转换到频率域，其逆变换是将图像从频率域转换到空间域。换句话说，傅立叶变换的物理意义是将图像的灰度分布函数变换为图像的频率分布函数，傅立叶逆变换是将图像的频率分布函数变换为灰度分布函数。

图像是对三维世界的描述，其描述的过程会损失一个维度Z轴，那为了使信息不失真，我们如何保存Z轴呢？就是用上面图像进行二维傅立叶变换得到频谱图来保存，就是图像梯度的分布图。频谱图上的各点与图像上各点并不存在一一对应的关系，因为它描述的是像素点之间的亮度关系，而不是某个点的亮度值。

通过观察傅立叶变换后的频谱图，也叫功率图。可以从图像的能量分布看出，如果频谱图中暗的点数更多，那么实际图像是比较柔和的（因为各点与邻域差异都不大，梯度相对较小），反之，如果频谱图中亮的点数多，那么实际图像一定是尖锐的，边界分明且边界两边像素差异较大的。

对频谱移频到原点以后，可以看出图像的频率分布是以原点为圆心，对称分布的。将频谱移频到圆心除了可以清晰地看出图像频率分布以外，还有一个好处，它可以分离出有周期性规律的干扰信号，比如正弦干扰，一副带有正弦干扰，移频到原点的频谱图上可以看出除了中心以外还存在以某一点为中心，对称分布的亮点集合，这个集合就是干扰噪音产生的，这时可以很直观的通过在该位置放置带阻滤波器消除干扰。（这里除了消除干扰以外，还可以增加干扰，完全取决于你的目的）。

 

快速傅里叶（FFT）：

x(n）为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实快速傅里叶变换数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m），即N点DFT变换大约就需要N^2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算。

在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列。每个N/2点DFT变换需要（N/2）^2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2*(N/2）^2=N+N^2/2。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。

虽然没看懂里面的值的变化，但是计算的对称性貌似是有的，先0跟4一组，然后0跟2一组，最后0跟1一组，是这样么？