第七章频域处理7.1 频域世界与频域变换7.2 傅立叶变换7.3 频域变换的一般表达式7.4 离散余弦变换7.5 离散沃尔什哈达玛变换7.6 用Matrix<LIB>C++库实现图像变换的VC++编程7.7 小波变换简介7.1 频域世界与频域变换图7-1 任意波形可分解为正弦波的加权和(a)(b)(c)(d)图7-2 正弦波的振幅A 和相位φ初相位ϕ振幅A基本 正弦波(A ＝1, ϕ＝0)角频率O A图7-3 图7-1（a ）波形的频域表示(a) 幅频特性；(b) 相频特性AOf O f(a)(b)时域和频域之间的变换可用数学公式表示如下：)(),()(f f A f f Φ⇔正变换逆变换为能同时表示信号的振幅和相位，通常采用复数表示法，因此式（7-1）可用复数表示为)()(f F f f 正变换逆变换⇔完成这种变换，一般采用的方法是线性正交变换。
(7-1) (7-2)7.2 傅立叶变换7.2.1连续函数的傅立叶变换若把一个一维输入信号作一维傅立叶变换，该信号就被变换到频域上的一个信号，即得到了构成该输入信号的频谱，频谱反映了该输入信号由哪些频率构成。
这是一种分析与处理一维信号的重要手段。
当一个一维信号f(x)满足狄里赫莱条件，即f(x)（1）具有有限个间断点；（2）具有有限个极值点；则其傅立叶变换对（傅立叶变换和逆变换）一定存在。
在实际应用中，这些条件一般总是可以满足的。
一维傅立叶变换对的定义为du e u F x f u F F dx e x f u F x f F uxj ux j ππ212)()()]([)()()]([⎰⎰∞+∞--+∞∞-====(7-3) (7-4) 式中：，x 称为时域变量，u 称为频域变量。
1--=j以上一维傅立叶变换可以很容易地推广到二维，如果二维函数f (x ,y )满足狄里赫莱条件，则它的二维傅立叶变换对为dudv e v u F y x f v u F F dxdy e y x f v u F y x f F vy ux j vy ux j )(21)(2),(),()],([),(),()],([+∞+∞-∞+∞--+-+∞∞-+∞∞-⎰⎰⎰⎰====ππ(7-5) (7-6)式中：x, y 为时域变量；u, v 为频域变量。
7.2.2离散傅立叶变换要在数字图像处理中应用傅立叶变换，还需要解决两个问题：一是在数学中进行傅立叶变换的f(x)为连续（模拟）信号，而计算机处理的是数字信号（图像数据）；二是数学上采用无穷大概念，而计算机只能进行有限次计算。
通常，将受这种限制的傅立叶变换称为离散傅立叶变换（Discrete Fourier Transform，DFT)。
设{f(x)|f(0), f(1), f(2), …, f(N-1)}为一维信号f(x)的N个抽样，其离散傅立叶变换对为N ux j N x N ux j N x eu F N x f u F F ex f u F x f F /2101/210)(1)()]([)()()]([ππ∑∑-=---=====(7-7)(7-8)式中：x ，u =0，1，2，…, N －1。
注：式（7-8）中的系数1/N 也可以放在式（7-7）中，有时也可在傅立叶正变换和逆变换前分别乘以，这是无关紧要的，只要正变换和逆变换前系数乘积等于1/N 即可。
N /1由欧拉公式可知θθθsin cos j e j +=(7-9)将式（7-9）代入式（7-7），并利用cos(－θ)=cos(θ)，可得∑-=⎪⎭⎫ ⎝⎛-=102sin 2cos )()(N x N ux j N ux x f u F ππ(7-10)可见，离散序列的傅立叶变换仍是一个离散的序列，每一个u 对应的傅立叶变换结果是所有输入序列f (x )的加权和（每一个f (x )都乘以不同频率的正弦和余弦值），u 决定了每个傅立叶变换结果的频率。
通常傅立叶变换为复数形式，即)()()(u jI u R u F +=(7-11)式中，R (u )和I (u )分别是F (u )的实部和虚部。
式(7-11)也可表示成指数形式：F (u )=|F (u ) |e j φ(u )(7-12) 其中)()(arctan )()()(|)(|22u R u I u u I u R u F =+=ϕ(7-13) (7-14)通常称|F (u )|为f (x )的频谱或傅立叶幅度谱，φ(u )为f (x )的相位谱。
频谱的平方称为能量谱或功率谱，它表示为)()(|)(|)(222u I u R u F u E +==(7-15) 考虑到两个变量，就很容易将一维离散傅立叶变换推广到二维。
二维离散傅立叶变换对定义为)(210101)(21010),(1),()],([),(),()],([N vy M ux j N v M u N vy M ux j M x N y e v u F MN y x f v u F F ey x f v u F y x f F +-=-=-+--=-=∑∑∑∑====ππ(7-16) (7-17)式中：u ,x =0,1,2,…,M -1；v ,y =0,1,2,…,N -1；x ,y 为时域变量，u ,v 为频域变量。
像一维离散傅立叶变换一样，系数1/MN 可以在正变换或逆变换中，也可以在正变换和逆变换前分别乘以系数，只要两式系数的乘积等于1／MN 即可。
二维离散函数的傅立叶频谱、相位谱和能量谱分别为MN /1),(),(),(),(),(arctan ),(),(),(|),(|2222v u I v u R v u E v u R v u I v u v u I v u R v u F +==+=ϕ(7-18) (7-19) (7-20)式中，R (u , v )和I (u , v )分别是F (u , v )的实部和虚部。
7.2.3 离散傅立叶变换的性质表7-1 二维离散傅立叶变换的性质1.可分离性由可分离性可知，一个二维傅立叶变换可分解为两步进行，其中每一步都是一个一维傅立叶变换。
先对f(x,y)按行进行傅立叶变换得到F(x,v)，再对F(x,v)按列进行傅立叶变换，便可得到f(x,y)的傅立叶变换结果，如图7-4所示。
显然对f(x,y)先按列进行离散傅立叶变换，再按行进行离散傅立叶变换也是可行的。
f (x, y) F (x, ) F (u, )按行进行一维DFT按列进行一维DFT图7-4 用两次一维DFT计算二维DFT2.平移性质平移性质表明，只要将f (x ,y )乘以因子(－1)x+y ，再进行离散傅立叶变换，即可将图像的频谱原点（0，0）移动到图像中心（M ／2,N ／2）处。
图7-5是简单方块图像平移的结果。
图7-5 傅立叶频谱平移示意图(a) 原图像；（b ）无平移的傅立叶频谱；（c）平移后的傅立叶频谱(a) (b) (c)3.旋转不变性由旋转不变性可知，如果时域中离散函数旋转θ0角度，则在变换域中该离散傅立叶变换函数也将旋转同样的角度。
离散傅立叶变换的旋转不变性如图7-6所示。
图7-6 离散傅立叶变换的旋转不变性(a)(b)(d)(c)7.2.4快速离散傅立叶变换离散傅立叶变换计算量非常大，运算时间长。
可以证明其运算次数正比于N2，特别是当N较大时，其运算时间将迅速增长，以至于无法容忍。
为此，研究离散傅立叶变换的快速算法 （Fast Fourier Transform，FFT）是非常有必要的。
下面介绍一种称为逐次加倍法的快速傅立叶变换算法 （FFT），它是1965年Cooley和Tukey首先提出的。
采用该FFT 算法，其运算次数正比于N lb N，当N很大时计算量可以大大减少。
例如，FFT的运算次数和DFT的运算次数之比，当N=1024时，比值为1／102.4；当N=4096时，比值可达1／341.3。
由于二维离散傅立叶变换具有可分离性，即它可由两次一维离散傅立叶变换计算得到，因此，仅研究一维离散傅立叶变换的快速算法即可。
先将式（7-7）写成∑-==1)()(N x uxWx f u F (7-21)式中，W =e -j2π／N ，称为旋转因子。
这样，可将式(7-21)所示的一维离散傅立叶变换（DFT ）用矩阵的形式表示为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡-⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡--⨯--⨯-⨯-⨯⨯-⨯⨯⨯-⨯⨯⨯⨯-⨯⨯⨯)1()1()0()1()1()0()1()1()1(2)1(1)1(00)1(02010)1(0201100)1(020100N f f f W W W WWW W W W W W WWWW N F F F N N N N N N N N 式中，由W ux 构成的矩阵称为W 阵或系数矩阵。
(7-22)观察DFT 的W 阵，并结合W 的定义表达式W =e -j2π／N ，可以发现系数W 是以N 为周期的。
这样，W 阵中很多系数就是相同的，不必进行多次重复计算，且由于W 的对称性，即xu N xu N x u N N jN WW WW e W ⨯⨯+⨯--=⨯=-==22222,1π因此可进一步减少计算工作量。
例如，对于N =4，W 阵为⎥⎥⎥⎥⎥⎥⎥⎤⎢⎢⎢⎢⎢⎢⎢⎡642032100000W W W W W W W W W WWW (7-23)由W 的周期性得：W 4＝W 0，W 6＝W 2，W 9＝W 1；再由W 的对称性可得：W 3＝－W 1，W 2＝－W 0。
于是式(7-23)可变为⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡------1010000010100000W W W W W W W W W W W W W W W W (7-24)可见N=4的W阵中只需计算W0和W1两个系数即可。
这说明W 阵的系数有许多计算工作是重复的，如果把一个离散序列分解成若干短序列，并充分利用旋转因子W的周期性和对称性来计算离散傅立叶变换，便可以简化运算过程，这就是FFT的基本思想。
设N为2的正整数次幂，即,2,12==nn n如令M为正整数，且N=2M (7-25) (7-26)将式（7-26）代入式（7-21），离散傅立叶变换可改写成如下形式：∑∑∑-=+-=-=++==1)12(2)2(211202)12()2()()(M x x u Mx u MM x M x ux MWx f Wx f Wx f u F 由旋转因子W 的定义可知，因此式(7-27)变为uxMux MWW=22u Mux MM x M x ux MWW x f Wx f u F 2101)12()2()(∑∑-=-=++=现定义1,,1,0,)12()(1,,1,0,)2()(110-=+=-==∑∑-=-=M x u Wx f u F M x u Wx f u F M x ux Mo M x ux Me (7-27)(7-28)(7-29)(7-30)于是式(7-28)变为)()()(2u F W u F u F o u Me +=(7-31)进一步考虑W 的对称性和周期性可知和，于是u MM u MWW=+u MM u MWW22-=+)()()(2u F W u F M u F o u Me -=+(7-32)由此，可将一个N 点的离散傅立叶变换分解成两个N ／2短序列的离散傅立叶变换，即分解为偶数和奇数序列的离散傅立叶变换F e (u )和F o (u )。
