随着科学技术的不断发展，许多用于加快计算速度的算法应运而生，快速傅里叶变换就是其中之一，快速傅里叶变换是傅里叶变换的一种快速计算方式。傅里叶变换在科学研究中运用非常广泛，刚开始出现时，主要用于信号分析与处理，通过将信号从时域转换到频域，可以很好的表示复杂的信号。此外，它还可以用于图像处理中，将一张图片进行傅里叶变换后将表示这张图片各个像素的梯度大小。还可用于目标跟踪，快速傅里叶变换可以高效的进行卷积运算和相关操作，其中基于相关滤波的目标跟踪已经成为计算机视觉跟踪领域的一大模块，具有举足轻重的作用，本文将首先论述傅里叶变换在科学研究中的意义，然后具体介绍一下傅里叶变换的概念以及表达式，接着重点论述了下快速傅里叶变换的推导及实现过程，
最后由于我的研究方向的目标跟踪，所以具体讲解了下快速傅里叶变换在目标跟踪领域中的具体运用。通过快速傅里叶变换，我们可以将一个O(
)的计算规模，减少为O(nlogn)。并且计算量越大，效果越明显。
，傅里叶变换的意义
人们想让计算机能处理信号 但由于信号都是连续的、无限的，计算机不能处理，于是就有了傅里叶级数、傅里叶变换，将信号由时域变到频域，把一个信号变为有很多个不同频率不同幅度的正弦信号组成，这样计算机就能处理了，但又由于傅里叶变换中要用到卷积计算，计算量很大，计算机也算不过来，于是就有了快速傅里叶变换，大大降低了运算量，使得让计算机处理信号成为可能。快速傅里叶变换是傅里叶变换的快速算法而已，主要是能减少运算量和存储开销，对于硬件实现特别有利。
傅里叶变换是一种分析信号的方法，它可分析信号的成分，也可用这些成分合成信号。它的实质是将一个信号分离为无穷多多正弦/复指数信号的加成，也就是说，把信号变成正弦信号相加的形式——既然是无穷多个信号相加，那对于非周期信号来说，每个信号的加权应该都是零——但有密度上的差别，你可以对比概率论中的概率密度来思考一下——落到每一个点的概率都是无限小，但这些无限小是有差别的所以，傅里叶变换之后，横坐标即为分离出的正弦信号的频率，纵坐标对应的是加权密度。
傅里叶变换也可用于图像处理中，频域反应了图像在空域灰度变化剧烈程度，也就是图像灰度的变化速度，也就是图像的梯度大小。对图像而言，图像的边缘部分是突变部分，变化较 快，因此反应在频域上是高频分量；图像的噪声大部分情况下是高频部分；图像平缓变化部分则为低频分量。也就是说，傅立叶变换提供另外一个角度来观察图像， 可以将图像从灰度分布转化到频率分布上来观察图像的特征。书面一点说就是，傅里叶变换提供了一条从空域到频率自由转换的途径。
，傅里叶变换
，傅里叶变换的概念
傅里叶变换。简称DFT，表示能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。在不同的研究领域，傅立叶变换具有多种不同的变体形式，如连续傅立叶变换和离散傅立叶变换，本文主要探究离散傅里叶变换。
傅里叶变换可以实现时间域到频率域的转换，很多实际问题在时间域内很难求解，但在频率域内就很简单，下面给出时域和频域的概念。
时域：描述数学函数或物理信号对时间的关系，可以理解为是一种以时间为自变量的函数。
频域：主要针对的是三角函数，主要分析三角函数的频率，也可理解为是一种以频率为自变量的函数。
其实，在现实中，频域里的结果，我们人类是理解不了的，毕竟我们是生活在一个时域的世界，所以这就要求我们还要实现从频域到时域的转换，这个过程称为傅里叶逆变换。
，傅里叶变换的表达式
离散傅里叶变换的数学表达式式如下（一维形式）：
从定义我们可以得出，傅里叶变换是将一般函数转化为三角函数，但是依照上面的表达式并没有三角函数，这里引进一个特别伟大的公式-欧拉公式：
之所以说它伟大，是因为它将复数、三角函数以及指数三者联系起来，现在令 θ =-2 π jk/N，将(2)式代入(1)式得：
同理，傅里叶逆变换表达式为：
，快速傅里叶变换
，快速傅里叶变换的概念
快速傅里叶变换 (fast Fourier transform),即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。DFT需要O(N2
)的计算时间，而FFT仅需要O(NlogN)的计算时间。
，快速傅里叶变换的推导
但是当N很大的话，计算量那是无法承受的，所以我们引入了快速傅里叶变换。
观察(4)式，想要简化这种计算的话，只能从 w Njk
下功夫，因为它既可以表示成复数型指数 ，又可以表示成三角型复数，接下来我们先简单介绍一下它的性质。
我们假设N是2的整次幂
(5)式说明，对于一个点的傅里叶变换来说，如果需要求的W的值有2k个，则最多只有k个w的值不同。
(6)式说明，对于求N个点的傅里叶变换来说，将N个点二等分后，前后部分的W值大小相等，方向相反
下面我们从一种非常简单明了的推理去理解FFT是如何进行快熟运算的。
我们把(4)式展开，这里先把
取掉，它只起均分的作用，最后再加上就可以了，
通过观察(10)和(11)式，我们会发现，这两个式子只有正负号不同，其他的都相同，也就是说通过求A(
)和B( )，可以同时求出 和 的值。
通过以上分析，我们就可以利用递归分治策略去求N个点的傅里叶变换，这样计算速度就可以达到O(nlogn)，FFT也有一个很明显的缺陷，它只可以计算2的N次幂的傅里叶变换。至于傅里叶逆变换，它的过程和上面推导的类似，只不过
和 换下位置而已。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。具体流程如下图所示
但是这里也有一个问题，递归会占用计算机很多的内存，且消耗的时间也多，所以需要对它进行改进。下面介绍一种迭代版FFT。
，迭代版快速傅里叶变换
我们在分治的过程中，可以对原序列进行重新分配排序，如上图所示，将原序列重新排为0，4，2，6，1，5，3，7等序列后，直接将0、4，2、6，1、5，3、7等两两合并，变为0、4、2、6和1、5、3、7两个组，再将他们进行合并，即可求出原序列的傅里叶变换，这样就可以跳过递归这一过程，节省了大量空间。我们还可以将序列用二进制表示，这样可以在计算机中直接按地址号存放序列。
图2，迭代版FFT
，快速傅里叶变换代码
下面是FFT算法的C++代码
void fft(E *g,int type)
{
for(int i=0;i
Original: https://blog.csdn.net/weixin_53306805/article/details/123052116
Author: 阳光杨
Title: （FFT）快速傅里叶变换在目标跟踪中的运用
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/641190/
转载文章受原作者版权保护。转载请注明原作者出处！