Abstract: 数字图像处理：第21天
Keywords: 离散傅里叶变换
本文最初发表于csdn，于2018年2月17日迁移至此
开篇废话
一如既往的开篇废话，今天介绍离散傅里叶变换（DFT），学习到这，不敢说对傅里叶有多了解，但起码把他家家谱算是捋顺了，这个家族不关系相当复杂，让多少人都迷糊了好久，估计上大学学明白的人不多，工作了用不到也就不会可以去学习了，不过很庆幸，感觉自己又学会了一点东西，也解决了之前心中的一个疑惑，后面希望能够将学到的傅里叶的数学知识用到解决实际问题的算法中。
离散傅里叶变换
首先说一下DFT的存在的意义，我们必须明确一点，计算机只能处理离散的有限的序列，不论是时域，还是频域如果计算得到的时连续的公式，那么计算机都无法实现，所以纵观前几篇的傅里叶，没有人满足这个条件，傅里叶级数虽然离散但是时域和频域都是无限的，傅里叶变换时域和频域都是无限的，而且是连续的，DTFT时域是离散有限的，但频域是连续的无限的；所以都不满足计算机对数据的要求，但通过观察我们可以发现，对DTFT稍加改造，或者对离散周期序列的傅里叶级数进行裁剪将能得到满足我们需求的数据类型，即有限的且离散的数据。
我们对DTFT的改造方式，根据其时域的采样方式，以等价的方式在频域进行等间隔采样，便得到频域离散的序列。
或者我们可以将原信号，即时域离散的有限信号，进行周期复制，周期要大于序列的长度，以保证信号形状不变，此离散周期序列存在傅里叶级数，但级数是周期离散的，也就是无限的，我们截取其中的一个完整的周期，便得到了频域离散有限的信号。
离散傅里叶变换公式上与离散周期傅里叶级数极其相似，对于序列 ${x[n]}$ 其中 $0\leq n<N$ ：
戴帽子的x就是频域序列；对应的从频域到时域的转换：
上面两个式子就是离散傅里叶变换。由公式可以看出，时域和频域的信号都是长度为N的离散序列。
数学推导
下面对DFT进行简要推导，假设 $x(t)$ 其中t在 $[0,L]$ 区间上，现在对时域进行取样，取样周期为 $T$ 即新序列
$$
x[n]=x(k\times T),k=0,1,2,3,\dots N-1
$$
共 $N$ 个采样点，其中 $N=\frac{L}{T}$ ，
为离散后的序列：
其傅里叶变换为:
这个式子其实就是前面所说的离散时间傅里叶变换。下面对其的频域进行采样，我们知道根据采样定律，采样频率必须大于原信号的最大频率的2倍，所以采样周期必须小于原信号最小周期的二分之一，所以，一个离散的有限的序列，其频率最大不超过其取样周期T的二倍的倒数，即频率域的最大频率 $w<\frac{(2\times\pi)}{(2\times T)}$ ,对应的负频率就应该是
$-w>-\frac{2\times\pi}{2\times T}$ ，所以离散序列对应的频率宽度为 $\frac{2\times\pi}{T}$ 。因为原序列的长度为L所以其最小频率间隔为 $\frac{2\times\pi}{L}$ 。那么频率域的离散序列长度为 $\frac{\frac{2\times\pi}{T}}{\frac{2\times\pi}{L}}=\frac{L}{T}=N$ ，与原序列对应，顾频率域的采样间隔为 $\frac{2\pi}{N}$ 。
顾采样序列为：
：
将上面式子归一化，令 $T=1$ ，便得到DFT公式。
所以，完整的DFT的过程是：对于连续非周期信号，现将其离散化，得到DTFT，然后将频率域进行再次离散化，得到DFT。
或者将有限离散序列进行复制，使原信号变成离散周期信号，求其傅里叶级数，求主值，也就是一个周期内的连续的点，就是对应的DFT。
性质
总结
总结下，DFT进行了粗略的介绍，因为其计算和离散周期信号的傅里叶级数计算相似，而且公式很易于接受，所以就只进行了简单的描述，之前后面一篇总结下所有的傅里叶的基础知识，然后介绍二维傅里叶，在外面绕了一圈就要回归图像了。
下面给出傅里叶家族的一些基本关系，灰色粗箭头表示可以由什么推导出什么，其他箭头表示连线：