3.1.4 快速傅里叶变换(FFT)
随着计算机技术和数字电路的迅速发展，在信号处理中使用计算机和数字电路的趋势愈加明显。离散
傅里叶变换已成为数字信号处理的重要工具。然而，它的计算量较大，运算时间长，在某种程度上却限
制了它的使用范围。快速算法大大提高了运算速度，在某些应用场合已可能作到实时处理，并且开始应
用于控制系统。
快速傅里叶变换并不是一种新的变换，它是离散傅里叶变换的一种算法。这种方法是在分析
离散傅里叶变换中的多余运算的基础上，进而消除这些重复工作的思想指导下得到的，所以在运算中大大节省了工作量，达到了快速运算的目的。下面我们从基本定义入手，讨论其原理。
对于一个有限长序列{x(n)}(0?n?N?1)，它的傅里叶变换由下式表示
X(m)?N?1n?0?x(n)e?j2?mnNm?0,1,??N?1(3—47)
令
W?e2??jN,W?1?e2?jN,因此，傅里叶变换对可写成下式
X(m)?1x(n)?NN?1n?0N?1n?0?x(n)WX(m)Wmn(3—48)
??mn(3—49）
将正变换式（3—48）展开可得到如下算式
X(0)?x(0)W?x(1)W????x(N?1)WX(1)?x(0)W?x(1)W????x(N?1)W2021101100010(N?1)1(N?1)2(N?1)X(2)?x(0)W?x(1)W????x(N?1)W ? ? X(N?1)?x(0)W(N?1)0?x(1)W(N?1)1????x(N?1)W(N?1)(N?1)(3—50)
数字图像处理基础第3章图像处理中的正交变换（第一讲）第3章图像处理中的正交变换
数字图像处理的方法主要分为两大类：一个是空间域处理法(或称空域法)，一个是频域法(或称变换域法)。
在频域法处理中最为关键的预处理便是变换处理。
这种变换一般是线性变换，其基本线性运算式是严格可逆的，并且满足一定的正交条件，因此，也将其称作酉变换。目前，在图像处理技术中正交变换被广泛地运用于图像特征提取、图像增强、图像复原、图像识别以及图像编码等处理中。本章将对几种主要的正交变换进行较详细地讨论。
3.1 傅里叶变换
傅里叶变换是大家所熟知的正交变换。在一维信号处理中得到了广泛应用。把这种处理方法推广到图像处理中是很自然的事。这里将对傅里叶变换的基本概念及算法作一些简单的复习。
3.1.1 傅里叶变换的定义及基本概念
傅里叶变换在数学中的定义是严格的。设f(x)为x的函数，如果满足下面的狄里赫莱条件：
（１）具有有限个间断点；（２）具有有限个极值点；
（３）绝对可积。
（６）偶函数
如果
xe?n??xe??n?Xe(m)?N?1n?0则
?2?mnxe(n)cos()N（７）奇函数
如果
x0?n???x0??n?X0(m)??j?N?1n?0则
2?x0(n)?sin(mn)N（８）卷积定理
如果则反之
x(n)?X(m),y(n)?Y(m)x(n)?y(n)?X(m)?Y(m)x(n)?y(n)?X(m)?Y(m)也成立。
（９）相关定理
如果
x(n)?X(m)y(n)?Y(m)x(n)oy(n)?X(m)?Y(m)?则
（10）帕斯维尔定理
如果
x(n)?X(m)N?1则
n?0?1x(n)?N2N?1m?02?X(m)
（８）卷积定理
如果f(x)和g(x)是一维时域函数，f(x,y)和g(x,y)是二维空域函数，那么，定义以下二式为卷积函数，即
f(x)?g(x)??????f(?)g(x??)d?f(x,y)?g(x,y)????????f(?,?)g(x??,y??)d?d?由此，可得到傅里叶变换的卷积定理如下
f(x,y)?g(x,y)?F(u,v)?G(u,v)f(x,y)?g(x,y)?F(u,v)?G(u,v)式中F(u,v) 和G(u,v) 分别是f(x)和g(x)的傅里叶变换。
3.1.3 离散傅里叶变换
连续函数的傅里叶变换是波形分析的有力工具，这
在理论分析中无疑具有很大价值。离散傅里叶变换使得数学方法与计算机技术建立了联系，这就为傅里叶变换这样一个数学工具在实用中开辟了一条宽阔的道路。因此，它不仅仅有理论价值，而且在某种意义上说它也有了更重要的实用价值。
1.离散傅里叶变换的定义
如果x(n)为一数字序列，则其离散傅里叶正变换定义由下式来表示
2?mnNX(m)?N?1n?0?x(n)e?j(3—29)
傅里叶反变换定义由下式来表示
1x(n)??X(m)eNm?0N?12?mnjN(3—30)
由(3—29)和(3—30)式可见，离散傅里叶变换是直接处理离散时间信号的傅里叶变换。如果要对
一个连续信号进行计算机数字处理，那么就必须经过离散化处理。这样，对连续信号进行的傅里
叶变换的积分过程就会自然地蜕变为求和过程。
2.离散傅里叶变换的性质（１）线性
如果时间序列x(n)与y(n)各有傅里叶变换X(m)和
Y(m)，则
ax(n)?by(n)?aX(m)?bY(m)（２）对称性如果
x?n??X?m?1X(n)?x(?m)N则
（３）时间移位
如果序列向右（或向左）移动k位，则:
x?n?k??X?m??W则
kmx?n?k??X?m??Wkm（４）频率移位如果
(3—40)
x?n??X?m?x?n??W?kn则
?X?m?k?（５）周期性
如果
x?n??X?m?x(n?rN)?x(n)则