动画物理|二维离散付立叶变换及其性质动画物理|图像处理

一、概述
离散付立叶变换（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。

表 3-3-1　FFT与DFT算法的比较
例如，用DFT直接运算，对于一般小型计算机需要几十分钟，而用FFT算法，其速度可快100倍以上。秩序几十秒。如采用FFT硬件专用机只需要几十毫秒即可完成。
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的公式比任何其他基的运算次数要少，但它不易变成，一般不大采用。