一、概述

　　离散付立叶变换（Discrete Fourier Transform── 简称DFT）在数字信号处理和数字图像处理中应用十分广泛。它建立了离散时域和离散之间的联系。如果直接应用卷积和相关运算在时域中处理，计算量将随着取样点数 数学 的平方而增加，这使计算机的计算量大，很费时，很难达到实时处理的要求。因此，一般可采用 DFT方法，将输入的数字信号首先进行 DFT变换，在频域中进行各种有效的处理，然后进行 DFT反变换，恢复为时域信号。这样用计算机对变换后的信号进行频域处理。比在时域中直接处理更加方便，计算量也大大减少，提高了处理速度。因此，本节介绍的DFT在数字图像处理领域中有很大的实用价值。

　　DFT还有一个明显的优点是有快速算法，即FFT（Fast Fourier Transform）算法，它可大大减少计算次数，使计算量减少到只是直接用DFT所需计算量的一小部分。

　　二维离散付立叶变换很容易以一维的概念推广而得。在数字图像处理中，二维DFT被广泛地应用于图像增强，复原，编码个分类中。

　　本节重点介绍二维DFT及其重要的性质，对FFT算法只介绍最基本的 为2的整数幂的算法。

　　二、二维离散付立叶变换

　　（一）一维离散付立叶变换

　　如将一维连续函数 用取 个间隔 取样增量的方法进行离散化， 变为离散函数，可用图3-3-1所示的序列 表示。它可写为下式

图 3-3-1　一维连续函数f(x)的取样

　　 (3.3.1)

　　式中 为离散值。

　　式（3.3.1）也就是表示了离散函数 为相应连续函数取 个间隔 的取样值。

　　经取样后的一维离散函数 的离散付立叶变换对由下式表示

　　 (3.3.2)

　　 (3.3.3)

　　式中： ；

　　　　　

　　值得注意的是离散付立叶变换式（3.3.2）和(3.3.3)类似于式（3.2.16）和(3.2.17)表示的连续函数 付立叶变换积分的离散求和的近似值，但它本身对离散后函数 不是一个近似值，而是对离散函数的标准的离散付立叶变化．

　　另外， 也是一个取 个等量间隔 取样后的离散函数，它可表示为 ，若 的取样始于原点，则

　　 (3.3.4)

　　式中： 为离散值

　　可证明空间域和频率域取样间隔 和 之间的关系为：

　　 　 （3.3.5）

　　最后，应指出的离散付立叶变换总是存在的，它不必考虑连续付立叶变换所需的可积的条件要求．

　　（二）二维离散付立叶变换

　　只要考虑二个变量，就很容易将一维离散付立叶变换推广到二维．二维离散付立叶变换对由下式给出

　　 (3.3.6)

　　式中：

　　　　　

　　　　　 (3.3.7)

　　　　　式中：

　　　　　

　　二维连续函数的取样是在二维的取样间隔上进行的，对空域的取样间隔为 和 ，对频御的取样间隔为 和 ．它们的相互关系为：

　　 　　 （3.3.8）

　　 (3.3.9)

　　在数字图像处理中，图像一般被取样为方形阵列，即，那二维DFT可表示为：

　　 (3.3.10)

　　式中

　　 (3.3.11)

　　式中

　　值得指出的是方程（3.3.10）和（3.3.11）不是所有作者一致通用的表示式，常用的是正，反变换式中常数项的取 ，有的应用相反正负号的 项．项目

　　一维和二维离散函数的付立叶谱，相位和能量谱分别与连续付立叶变换时基本相同，它可由式(3.2.19)至(3.2.20)和（3.2.23）至(3.2.25)给出，所不同的地方在于变量是离散值．

　　三、二维离散付立叶变换的性质

　　二维离散付立叶变换有二维连续付立叶变换的相似性质，下面说明它的集中常用性质，证明请见（3.16， 3.17）．

　　（１） 线性

　　付立叶变换是一种线性算子。设 和 分别为二维离散函数 和 的离散复付立叶变换，则

　　 (3.3.12)

　　式中 是常数

　　（２）可分离性

　　由式（3.3.10）和(3.3.11)可看出，式中指数项可分成只含有 和 的二项乘积，其相应的二维离散付立叶变换对可分离成二部分只乘积

　　 (3.3.13)

　　

　　 (3.3.14)

　　其中：

　　　　　

　　可分离性的重用意义在于：一个二维付立叶变换或反变换都可分解为二步进行，其中每一步都是一个一维付立叶变换或反变换．为说明此问题，以二维付立叶正变换（式3.3.13）为例，例会设式(3.3.13)后面的指数项为 ，即

　　 (3.3.15)

　　此式表示对每一个 值， 先沿每一行进行一次一维付立叶变换。然后，将 ，即

　　 (3.3.16)

　　上述分离过程可用图3-3-2表示．

图 3-3-2　二维付立叶变换分离为二个一维变换

　　图3-3-2表示二维付立叶变换先沿行后沿列分离为二个一维变换的过程，显然改为先沿列后沿行分离为一个一维变换，其结果亦是一样，此时，式(3.3.15)和(3.3.16)改为下列形式即可

　　 (3.3.17)

　　 (3.3.18)

　　二维离散付立叶反变换的分离过程完全与上述相似，所不同的只是指数项为正，这里就不重复了。

　　（３）平移性

　　付立叶变换对的平移性由下式给出：

　　 (3.3.19)

　　和 (3.3.20)

　　上式表明，在空域中图像原点平移到 时，其对应的频谱 要乘上一个负的指数项 ] :而频域中原点平移到 时，其对应的 要乘上一个正的指数项 ，平移性告诉我们一个感兴趣的事实：当空域中 产生移动时，在频域中只发生相移，移动而付立叶变换的幅值不变，因为：

　　 (3.3.21)

　　反之，当频域中 产生移动时，相应的 在空域中也只发生相移，而幅值不变。

　　在数字图像处理中，常常需要将 的原点移到 频域方阵的中心，以便能清楚地分析付立叶变换谱的情况．要做到此点．只需令

　　

　　则　　 (3.3.22)

　　上式结果可用尤拉公式，即代入 而得

　　将式(3.3.22)代入(3.3.19)式可得

　　 (3.3.23)

　　式(3.3.23)说明：如果需要将图像频谱的原点从起始点 移到图像的中心点 ，只要 乘上 因子进行付立叶变换即可实现。

　　（４） 周期性和共轭对称性

　　离散付立叶变换和反变换具有周期性和共轭对称性．付立叶变换对的周期性表示为

　　 (3.3.24)

　　 (3.3.25)

　　式中

　　共轭对称性表示为：

　　 (3.3.26)

　　 (3.3.27)

　　离散付立叶变换对的周期性说明正变换后得到的 或反变换后得到的 都是具有周期为 的周期性重复离散函数．但是，为了完全确定 或 只需变换一个周期中每个变量的 个值．也就是说，为了在频域中安全地确定 ，只需要变换一个周期．在空域中，对 也有类似的性质．共轭对称性说明变换后的幅值是以原点为中心对称．利用此特性，在求一个周期内的值时，只要求出半个周期，另半个周期也就知道了，这大大地减少了计算量．

　　为说明此问题，以一维变量为例，例会如图3-3-4所示，周期性 表明 以长度为 的周期重复出现，而共轭对称性 说明变换的幅值 以原点为中心对称．此时离散付立叶谱 在 一个周期中是二个背对背的半周期的谱．如果在变换前将 乘上 ，就能将变换后的谱 的原点移至 处，这样在 个周期中，可显示出一个完整周期。

图 3-3-3　付立叶变换的周期性和共轭对称性的例子

　　（５） 旋转不变性

　　若引入极坐标

　　

　　则 和 分别为 。在极坐标系中，存在以下变换对：

　　 (3.3.28)

　　此式表明，如果 在空间域中旋转 角度后，相应的付立叶变换 在频域中也旋转同 角。反之， 在频域中旋转 角，其反变换 在空间域中也旋转 角。

　　（６）分配性和比例性

　　付立叶变换的分配性表明付立叶变换和反变换对于加法可以分配，而对乘法则不行。即

　　 　 （3.3.29）

　　 (3.3.30)

　　付立叶变换的比例性表明为对于二个标量 和 有

　　 (3.3.31)

　　 (3.3.32)

　　式(3.3.32)说明了在空间比例尺度的展宽，相应于频域比例尺度的压缩，其幅值也减少为原来的 。

　　（７）平均值

　　二维离散函数的平均值定义如下：

　　 (3.3.33)

　　将 代入二维离散付立叶定义(3.3.6)式可得

　　 (3.3.34)

　　比较式(3.3.33)和(3.3.34)可看出

　　 (3.3.35)

　　因此，要求二维离散信号 的平均值，只需算出相应的付立叶变换 在原点的值 。

　　（８）微分性质

　　二维变量函数 的拉普拉斯（Laplacian）算子的定义为：

　　 （3.3.36）

　　按二维付立叶变换的定义可得：

　　 　 （3.3.37）

　　拉普拉斯算子通常用于捡出图像轮廓的边缘。

　　（９）卷积定理

　　卷积定理和相关定理都是研究二个函数的付立叶变换之间的关系。这也构成了空间域和频域之间的基本关系。

　　对于二个二维连续函数 和 的卷积定义为：

　　 (3.3.38)

　　其二维卷积定理可由下面关系表示：

　　设：

　　则： (3.3.39)

　　　　 (3.3.40)

　　它表明二个二维连续函数在空间域中的卷积可求其相应的二个付立叶变换乘积的反变换而得。反之，在频域中的卷积可用的在空间域中乘积的付立叶变换而得。应用卷积定理的明显好处是避免了直接计算卷积的麻烦，它只需先算出各自的频谱，然后相乘，再求其反变换，即可得卷积。

　　对于离散的二维函数 和 ，同样可应用上述卷积定理。其差别仅仅是与取样间隔对应的离散增量出发生位移，以及用求和代替积分，另外，由于离散付立叶变换个反变换都是周期函数，为了防止卷积后产生交叠误差，（wraparound error）需对离散的二维函数的定义域加以扩展。

　　设 和 是大小分别为 和 的离散数组，也就是说 定义域为 ， 的定义域为 。根据[3·18]证明，必须假定这些数组在 和 方向延伸为某个周期是 和 的周期函数，其 和 的大小为：

　　 （3.3.41）

　　 （3.3.42）

　　这样各个卷积周期才能避免交叠误差。为此将 和 用增补零的方法扩充为以下的二维周期序列：

　　

　　

　　其二维离散卷积形成为：

　　 　　（３.3.43）

　　其中；

　　　　　

　　这个方程给出的 阵列，是离散的二维卷积的一个周期。

　　二维离散卷积定理可用下式表示

　　 　　　　　（3.3.44）

　　 (3.3.45)

　　此形式与连续的基本一样，所不同的是所有变量 都是离散量，其运算都是对于扩充函数 和 进行的。

　　（10）相关定理

　　对于二个二维连续函数 和 的相关定义为：

　　 (3.3.46)

　　在离散情况下，于离散卷积一样，需用增补零的方法扩充 和 为 和 ，并按式（3.3.41）和（3.3.42）选取 和 ，以避免在相关函数周期内产生交叠误差。那么离散和力学那许情况的相关定理都可表示为

　　 （3.3.47）

　　和 （3.3.48）

　　式中“ ”表示共扼。显然对离散变量来说，其函数都是扩充函数，用 表示。

　　四、应用付立叶变换需注意的问题

　　尽管付立叶变换有很多游泳的性质，获得了广泛的应用，但它也有两个缺点：一是需计算负数而不是实数，进行复数运算比较费时。如采用其他合适的正交函数系来代替付立叶变换所用的正、余弦函数构成正交的正交函数系，就可避免这种复数运算。如下面介绍的沃尔什（Walsh）函数系，每个函数只取＋1与－1两个值，组成二值正交函数。因此，以沃尔什函数为基础所构成的变换，什实数加减运算，其运算速度要比付立叶变换快。

　　此外，在图像处理中，常以光强度函数显示付立叶谱。但许多图像的谱随着频率的增加衰减得很快，因此他们的高频项变得越来越不清楚。为解决此问题，常用下面函数变换代替 ，该函数定义为

　　 (3.3.49)

　　注意： 为非负函数

　　五、快速付立叶变换(Fast Fourier Transform-FFT)

　　离散付立叶变换还有一个有点是有快速算法（FFT算法）。由式（3.3.2）可看出，求一维DFT时，对 的 个值中的每一个，需要做 次复数乘法和 次复数加法。那么对 个 值，全部DFT运算则需进行 次复数乘法与 （当N很大时）次复数加法。很显然，当N很大时，计算是很费时的。

　　1965年由库里（Cooley）和图基（Tukey）首先提出一种FFT算法，其复数乘法和加法的次数正比于 ，这在 大时，计算量的节省很显著，见表3-3-1。

　　FFT算法基本上可分为二大类：按时间抽取算法和按频率抽取算法。“库利－图基”算法属于前者，而后者是前者的改进形式，称“桑德（Sande）-图基”算法。FFT算法包括了以下三种情况：

　　（１） 为2的整数幂的算法；

　　（２） 为高复合数时的算法；

　　（３） 为素数时的算法。

　　本节只介绍最基本的 为2的整数幂的算法，而且只介绍按时间抽取算法。

　　最后，值得一提的是1976年维诺格兰（WINOGRAD）发表了FFT的新算法（称为WFTA算法－Winograd Fourier Transform Algorithm），它要求的复数乘法次数仅为FFT乘法次数的1/3，复数加法次数与FFT基本相同。

　　（一）FFT的基本原理

　　此处只介绍按时间抽取， 为2的整数幂 的FFT算法。

　　一维离散付立叶变换对为

　　 (3.3.50)

　　 （3.3.51）

　　式中

　　 (3.3.53)

　　FFT是利用 的二个特点来提高计算效率的

　　（1） 的对称性

　　 (3.3.53)

　　（2） 的周期性

　　 (3.3.54)

　　因为 为2的整数幂，即 ，故可以将 分解成二部分；一是偶数部分 ，一是奇数部分 ，此处 。那么，离散函数 的DFT可以用二个 采样点的DFT计算，即由偶数部分 的DFT和奇数部分 的DFT求出。因此，式（3.3.50）可以写成：

　　 （3.3.55）

　　从式（3.3.52）可得 ，那么式（3.3.55）可改写为

　　 （3.3.56）

　　如定义：

　　 （3.3.57）

　　 （3.3.58）

　　其中 .

　　由此，式（3.3.56）变为：

　　 （3.3.59）

　　因为

　　所以

　　那由（3.3.57）至（3.3.59）可得

　　 （3.3.60）

　　由式（3.3.59）和(3.3.60)可见，一个 点的DFT可以从二个 点的DFT求出。 的前一半的计算由式（3.3.57）和（3.3.58）求出分别为 点的DFT，即求出 和 ，然后带入式（3.3.59）可得 的 .另一半可直接从式（3.3.59）。如依次类推，每次将 用2除，就可以分成越来越小的子序列上执行DFT，直到执行2点的DFT为止，最后再合成 点的DFT。

　　（二）信号流图

　　FFT运算可用信号流图表示。式（3.3.59）和式（3.3.60）运算一般称为蝶形运算，因子Wun称为旋转因素。蝶行信号流图如图3-3-4所示，图3-3-4中（a）和（b）是等效的二种蝶行运算表示形式。很显然，计算一个蝶形需1次乘法和2次加（减）法。

图 3-3-4　蝶形运算

　　下面以 为说明式（3.359）和式（3.3.60）的FFT算法，其蝶形信号流图如图3-3-5所示。

图 3-3-5　N=8的按时间抽取FFT信号流图

　　上述方法的每一步分解都是按输入序列在时域上的次序是偶数还是奇数来抽取，故称为为按时间抽取法，同样也可按 在频域上的顺序是偶数还是奇数抽取，这时按频率抽取法。按频率取样法FFT可参阅『3.14』。

　　从图3-3-5还可以看出：

　　（1）对于 点DFT的整个运算全由蝶形运算组成，需要 轮递推，每轮由 个蝶形，总共有 个蝶形。考虑倒每个蝶形包括1次乘法和2次加法，因此，总的计算量为 次乘法及 次加法。采用这种形式的FFT算法，最少可以节省计算时间的倍数为：

　　

　　（2）从图3-3-5中可以看出FFT变换的结果是 是自然顺序排列，而输入 才可以进行FFT运算。此“码位倒置”是因为在时间抽取算法过程中，把偶数点放在上面，把奇数点放在下面。奇数点与偶数点可以从二进制数码的最后一位码 先着手区分开来。如果 为0，则 是偶数，应放在上面。反之，如果 为1，则 是奇数，应放在下面。然后再依此由左到右逐位检验下去。最后合起来就是倒置了码位的二进制反序数。由表3-3-2表示了 共有三个码位 的倒置过程和结果。

自然顺序	二进制码表示	码位倒置	码位倒置顺序
0	000	000	0
1	001	100	4
2	010	010	2
3	011	110	6
4	100	001	1
5	101	101	5
6	110	011	3
7	111	111	7

表 3-3-2　码位倒置顺序

　　（三）逆FFT

　　FFT的逆变换都可用正变换FFT作适当的修改即可求得。为说明此点，将式（3.3.50）和（3.3.51）重写如下：

　　 （3.3.61）

　　 （3.3.62）

　　求式（3.3.62）的共扼并用 除二边可得到。

　　 （3.3.63）

　　将式（3.3.63）和式（3.3.61）比较，可看出式（3.3.63）的右端在形式上就是付立叶正变换。因此，只要将 输入到计算正变换算法，结果将式 ，取它的复共扼的运算没有必要，因为对实函数有 。

　　最后要指出的是FFT算法通常是以基－2格式公式化的，因它易于用汇编语言实现。对于其他大于2的整数基也有 FFT算法，如基为3的公式比任何其他基的运算次数要少，但它不易变成，一般不大采用。