傅立叶变换及其在信号处理中的应用

傅立叶变换是信号处理的理论基础，它建立了信号时域与频域的联系，在各种数字信号处理的算法中起着核心的作用，尤其是在一维信号处理中被广泛使用。这里我们将介绍它在数字图像处理中的使用方法。

（一）二维连续傅立叶变换的定义

傅立叶变换建立了以时间为自变量的“信号”与以频率为自变量的“频率函数（频谱）”之间的某种变换关系。根据时间或频率取连续还是离散值，就形成各种不同形式的傅立叶变换对：

1）傅立叶级数（FS）：针对连续周期信号，时间连续，频率离散。

2）傅立叶变换（FT）：针对连续非周期信号，时间连续，频率连续。

3）离散时间傅立叶变换（DTFT）：针对离散时间信号，时间离散，频率连续。

4）离散傅立叶变换（DFT）：针对离散时间信号，时间离散，频率离散。

设f（x）为实变量x的连续函数，如果f（x）满足绝对可积的条件：

则定义f（x）的傅立叶变换为

其逆变换为

式中，x为时域自变量，u为频域自变量，通常称为频率变量。显然，傅立叶变换的结果是一个复数表达式。

我们可以把傅立叶变换推广到二维情况。如果二维连续函数f（x，y）满足绝对可积的条件，则可导出下面的二维傅立叶变换：

如果F（u，ν）是可积的，则逆变换为

设F（u，ν）的实部为R（u，ν），虚部为I（u，ν），则二维傅立叶变换的幅度谱和相位谱分别为

和

能量谱为

例如，计算函数

的傅立叶变换表达式

因为∫exdx=ex且d（cx）=c·dx

则

由欧拉公式e-jX-e-jX=-2jsinX可知

其幅度谱为

（二）二维连续傅立叶变换的性质

傅立叶变换具有很多方便运算处理的性质。下面列出二维连续傅立叶变换的一些重要性质。

1.线性

傅立叶变换是一个线性变换，即

2.可分离性

一个二维傅立叶变换可以用二次一维傅立叶变换来实现。推导如下：

3.平移性

傅立叶变换具有平移特性，即

4.共轭性

如果函数f（x，y）的傅立叶变换为F（u，ν），F∗（-u，-ν）为f（-x，-y）傅立叶变换的共轭函数，那么

F(u，ν)=F∗(-u，-ν)(2-83)

5.尺度变换特性

如果函数f（x，y）的傅立叶变换为F（u，ν），a和b为两个标量，那么

6.旋转不变性

如果空间域函数旋转角度为θ0，则该函数的傅立叶变换函数也将旋转同样的角度。表达式如下：

式中，f（r，θ）和F（k，φ）为极坐标表达式，其中x=rcosθ，y=rsinθ，u=kcosθ，ν=ksinθ，f（r，θ）傅立叶变换为F（k，φ）。

7.对称性

如果函数f（x，y）的傅立叶变换为F（u，ν），那么

8.能量保持定理

能量保持定理也称Parseval定理，数学描述如下：

表明傅立叶变换前后信号的能量守恒。

9.相关定理

如果f（x，y）和g（x，y）为两个二维时域函数，那么可以定义相关运算“◦”如下：

则

式中，F（u，ν）为函数f（x，y）的傅立叶变换；G（u，ν）为函数g（x，y）的傅立叶变换；G∗（u，ν）为G（u，ν）的共轭；g∗（x，y）为g（x，y）的共轭。

10.卷积定理

如果f（x，y）和g（x，y）为两个二维时域函数，那么可以定义卷积运算“∗”如下：

则

式中，F（u，ν）为函数f（x，y）的傅立叶变换；G（u，ν）为函数g（x，y）的傅立叶变换。

（三）二维离散傅立叶变换的定义

连续函数的傅立叶变换是波形分析的有力工具，但是为了使之适用于计算机技术，必须将连续变换转变成离散变换，这样就必须引入离散傅立叶变换（DFT）。离散傅立叶变换在数字信号处理和数字图像处理中都得到了十分广泛的应用，它在离散时域和离散频域之间建立了联系。

如果f（x）为一长度为N的序列，则其离散傅立叶正变换由下式来表示：

逆变换为

式中，x=0，1，2，…，N-1

如果令WN=exp[-j2π/N]，那么上述公式变成

式（2-97）写成矩阵形式为

式（2-97）写成矩阵形式为

式（2-98）写成矩阵形式为

二维离散傅立叶变换很容易从一维的概念推广得到。二维离散函数f（x，y）的傅立叶变换为

逆变换为

式中，x=0，1，…，M-1，y=0，1，…，N-1。

在数字图像处理中，图像取样一般是方阵，即M=N，则二维离散傅立叶变换式为

逆变换为

图像的频率是表征图像中灰度变化剧烈程度的指标，是灰度在平面空间上的梯度。如大面积的沙漠在图像中是一片灰度变化缓慢的区域，对应的频率值很低；而对于地表属性变换剧烈的边缘区域在图像中是一片灰度变化剧烈的区域，对应的频率值较高。

从物理效果看，傅立叶变换是将图像从空间域转换到频率域，其逆变换是将图像从频率域转换到空间域。实际上对图像进行二维傅立叶变换得到的频谱图就是图像梯度的分布图，当然频谱图上的各点与图像上各点并不存在一一对应的关系。我们在傅立叶频谱图上看到的明暗不一的亮点，就是图像上某一点与其邻域点差异的强弱，即灰度梯度的大小，也即该点的频率的大小。经过傅立叶变换后的图像，四角对应于低频成分，中央部位对应于高频部分，如图2-13～图2-15所示。

图2-13　对雷娜（Lena）图像进行傅立叶变换前后的结果

a）原始图像　b）离散傅立叶变换后的频谱图

图2-14　对维维安（Vivien）图像进行傅立叶变换前后的结果

a）原始图像　b）离散傅立叶变换后的频谱图(www.xing528.com)

图2-15　对二值图像进行傅立叶变换前后的结果

a）原始图像　b）频谱图

（四）二维离散傅立叶变换的性质

二维离散傅立叶变换与二维连续傅立叶变换有相似的性质，下面列出它的几种常用性质。

1.线性

设F1（u，ν）和F2（u，ν）分别为二维离散函数f1（x，y）和f2（x，y）的离散傅立叶变换，则

式中，a和b是常数。

2.可分离性

由式（2-101）和式（2-102）可以看出，式中的指数项可分成只含有x，u和y，ν的二项乘积，其相应的二维离散傅立叶变换对可分离成两部分的乘积

式中，u，ν，x和y均取0，1，2，…，N-1。

可分离性的重要意义在于：一个二维傅立叶变换或反变换都可分解为两步进行，其中每一步都是一个一维傅立叶变换或反变换。为说明问题，以二维傅立叶正变换式（2-50）为例，设式（2-107）的求和项为F（x，ν），即

表示对每一个x值，f（x，y）先沿每一行进行一次一维傅立叶变换，再将F（x，ν）沿每一列进行一次一维傅立叶变换，就可得二维傅立叶变换F（u，ν），即

显然，改为先沿列后沿行分离为二个一维变换，其结果是一样的。此时，式（2-108）和式（2-109）改为下列形式：

二维离散傅立叶逆变换的分离过程与正变换相似，不同的只是指数项为正，这里就不再赘述了。

3.平移性

和

上式表明，在空域中图像原点平移到（x0，y0）时，其对应的频谱F（u，ν）要乘上指数项exp[-j2π（ux0+νy0）/N]；而频域中原点平移到（u0，νo）时，其对应的f（x，y）要乘上指数项exp[j2π（ux0+νy0）/N]。当空域中f（x，y）产生移动时，在频域中只发生相移，而频谱的幅值不变，因为

反之，当频域中F（u，ν）产生移动时，相应的f（x，y）在空域中也产生相移，而幅值不变。

在数字图像处理中，常常需要将F（u，ν）的原点移到N×N频域方阵的中心，以便可以清楚地分析其频谱的情况。要做到这一点，只需要令u0=ν0=N/2，则

将式（2-115）代入式（2-112）可得

上式说明如果需要将图像频谱的原点从起始点（0，0）移到图像的中心点（N/2，N/2），只要f（x，y）乘上（-1）x+y因子进行傅立叶变换即可实现。图2-16为图像平移前后其频谱图的变化情况。

图2-16　傅立叶变换的平移性

a）平移前的频谱图b）平移后的频谱图

4.周期性和共轭性

离散傅立叶变换和反变换具有周期性和共辄对称性。其中周期性表示为

式中，a，b=0，±1，±2，…。

共轭对称性表示为

离散傅立叶变换对的周期性，说明正变换后得到的F（u，ν）或反变换后得到的f（x，y）都是周期为N的离散函数。但是，为了确定F（u，ν）或f（x，y）只需得到一个周期中的N个值。就是说，为了在频域中完全地确定F（u，ν），只需要变换一个周期。在空域中，对f（x，y）也有类似的性质。共轭对称性说明变换后的幅值是以原点为中心对称的。利用此特性，在求一个周期内的值时，只需求出半个周期，另半个周期也就知道了，如此可大大减少计算量。

5.旋转不变性

若引入极坐标，则f（x，y）和F（u，ν）分别变为f（r，θ）和F（ω，φ）。在极坐标系中，存在以下变换对：

此式表明，如果f（x，y）在时间域中旋转θ0角后，相应的F（u，ν）在频域中也旋转θ0角；反之，如果F（u，ν）在频域中旋转θ0角，其反变换f（x，y）在空间域中也旋转θ0角。

6.分配性和比例性

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

傅立叶变换的比例性表明对于两个常数a和b，有

式（2-125）说明在空间尺度的展宽，相应于频域尺度的压缩，其幅值也减少为原来的1/|ab|。

7.平均值

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

将u=ν=0代入二维离散傅立叶变换定义式，可得

比较式（2-126）和式（2-127），可看出

因此，若要求二维离散信号f（x，y）的平均值，只需计算其傅立叶变换F（u，ν）在原点的值F（0，0）。

8.微分性质

二维函数f（x，y）的拉普拉斯算子的定义为

按二维傅立叶变换的定义，可得

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

9.卷积定理

卷积定理和相关定理都是研究两个函数的傅立叶变换之间的关系。这也构成了空间域和频域之间的基本关系。两个二维连续函数f（x，y）和g（x，y）的卷积定义为

设

则

上式表明两个二维连续函数在空间域中的卷积可用求其相应的两个傅立叶变换乘积的反变换得到。

对于离散的二维函数，上述性质也成立，但需注意与取样间隔对应的离散增量处发生位移，以及用求和代替积分。另外，由于离散傅立叶变换和反变换都是周期函数，为了防止卷积后产生混叠误差，需对离散二维函数的定义域加以扩展。设f（x，y）和g（x，y）是大小分别为A×B和C×D的离散数组，也就是说f（x，y）定义域为（0≤x≤A-1，0≤y≤B-1），g（x，y）的定义域为（0≤x≤C-1，0≤y≤D-1），则可以证明，必须假定这些数组在x和y方向延伸为某个周期是M和N的周期函数，其中M≥A+C-1，N≥B+D-1。这样各个卷积周期才能避免混叠误差，为此将f（x，y）和g（x，y）用补零的方法扩充成二维周期序列

其二维离散卷积形式为

式中，x=0，1，…，M-1，y=0，1，…，N-1。这个方程给出的M×N阵列，是离散二维卷积的一个周期。

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

此形式与连续的基本一样，所不同的是所有变量x、y、u和ν都是离散量，其运算都是对于扩充函数fe（x，y）和ge（x，y）进行的。

10.相关定理

两个二维连续函数f（x，y）和g（x，y）的相关运算定义为

在离散情况下，与离散卷积一样，需用补零的方法扩充f（x，y）和g（x，y）为fe（x，y）和ge（x，y）。那么，离散和连续情况的相关定理都可表示为

和

式中，“∗”表示共轭。显然，对离散变量来说，其函数都是扩充函数，用fe（x，y）和ge（x，y）表示。

（五）二维离散傅立叶变换的具体操作步骤

一般来说，对一幅图像进行傅立叶变换运算量很大，不直接利用以上公式计算，而是采用快速傅立叶变换（FFT）算法，可大大减少计算量。如前所述，可以将二维离散傅立叶变换的运算分解为水平和垂直两个方向上的一维离散傅立叶变换运算，而一维离散傅立叶变换可用快速傅立叶变换来实现。下面给出二维离散快速傅立叶变换的操作步骤：

1）获取原图像数据存储区的首地址、图像的高度和宽度。

2）计算进行傅立叶变换的宽度和高度，这两个值必须是2的整数次幂；计算变换时所用的迭代次数，包括水平方向和垂直方向。

3）逐行或逐列顺序读取数据区的值，存储到新开辟的复数存储区。

4）调用一维FFT函数进行垂直方向的变换。

5）转换变换结果，将垂直方向的变换结果转存回时域存储区。

6）调用一维FFT函数，在水平方向上进行傅立叶变换，步骤同1）～4）。

7）将计算结果转换成可显示的图像，并将坐标原点移至图像中心位置，使得可以显示整个周期频谱。

（六）应用傅立叶变换时应当注意的问题

尽管傅立叶变换提供了很多有用的属性，在数字图像处理领域中得到广泛的应用，但是它也有自身的不足，主要表现在两个方面：一是复数计算时，相对比较费时。如采用其他合适的完备正交函数来代替傅立叶变换所用的正、余弦函数构成完备的正交函数系，就可避免这种复数运算。如后面介绍的沃尔什（Walsh）函数系，每个函数只取“+1”和“-1”两个值，组成二值正交函数。因此，以沃尔什函数为基础所构成的变换是实数加减运算，其运算速度要比傅立叶变换快。另一个缺点是收敛慢，在图像编码中尤为突出。