第7章-频域处理

多媒体通信北京科技大学杨扬第7章频域处理频域世界与频域变换傅立叶变换频域变换的一般表达式离散余弦变换离散沃尔什哈达玛变换小波变换简介1、频域世界与频域变换频域变换的理论基础是：“任意波形都可以用单纯的正弦波的和来表示”因此图像的频域变换为：（1）将图像看成是线性叠加系统；（2）图像在空域上相关性很强；（3）图像变换是将图像从空域变换到其它域如频域的数学变换。常用的变换有：傅立叶变换、离散余弦变换、小波变换、离散K-L变换(a)(b)(c)(d)1、频域世界与频域变换正弦波的振幅A和相位φ初相位振幅A基本正弦波(A＝1,＝0)角频率OA1、频域世界与频域变换时域和频域之间的变换可用数学公式表示如下：)(),()(ffAff正变换逆变换为能同时表示信号的振幅和相位，通常采用复数表示法，因此上式可用复数表示为)()(fFff正变换逆变换完成这种变换，一般采用的方法是线性正交变换。2、傅立叶变换傅立叶变换是一种常用的正交变换，它的理论完善,应用程序多。在图像处理应用领域，傅立叶变换起着非常重要的作用，可用它完成图像分析、图像增强以及图像压缩等工作。当一个一维信号f(x)满足狄里赫莱条件，即f(x)（1）具有有限个间断点；（2）具有有限个极值点；（3）绝对可积。则其傅立叶变换对（傅立叶变换和逆变换）一定存在。2.1连续函数的傅立叶变换一维傅立叶变换对的定义为：dueuFxfuFFdxexfuFxfFuxjuxj212)()()]([)()()]([式中：，x称为时域变量，u1j2.1连续函数的傅立叶变换以上一维傅立叶变换可以很容易地推广到二维，如果二维函数f(x,y)满足狄里赫莱条件，则它的二维傅立叶变换对为dudvevuFyxfvuFFdxdyeyxfvuFyxfFvyuxjvyuxj)(21)(2),(),()],([),(),()],([式中：x,y为时域变量；u,v为频域变量。2.1连续函数的傅立叶变换若把一个一维输入信号作一维傅立叶变换，该信号就被变换到频域上的一个信号，即得到了构成该输入信号的频谱，频谱反映了该输入信号由哪些频率构成。一维傅立叶变换对的定义为：212[()]()()[()]()()juxjuxFfxFufxedxFFufxFuedu式中：，x称为时域变量，u称为频域变量。1j2.2离散傅立叶变换设{f(x)|f(0),f(1),f(2),…,f(N-1)}为一维信号f(x)的N个抽样，其离散傅立叶变换（DiscreteFourierTransform，DFT)对为：式中：x，u=0，1，2，…，N－1。NuxjNxNuxjNxeuFNxfuFFexfuFxfF/2101/210)(1)()]([)()()]([2.3离散傅立叶变换的性质2.3离散傅立叶变换的性质2.3离散傅立叶变换的性质-平移性质由可分离性可知，一个二维傅立叶变换可分解为两步进行，其中每一步都是一个一维傅立叶变换。先对f(x,y)按行进行傅立叶变换得到F(x,v)，再对F(x,v)按列进行傅立叶变换，便可得到f(x,y)的傅立叶变换结果，如下图所示。显然对f(x,y)先按列进行离散傅立叶变换，再按行进行离散傅立叶变换也是可行的。用两次一维DFT计算二维DFTf(x,y)F(x,)F(u,)按行进行一维DFT按列进行一维DFT2.3离散傅立叶变换的性质-可分离性平移性质表明，只要将f(x,y)乘以因子(－1)x+y，再进行离散傅立叶变换，即可将图像的频谱原点（0，0）移动到图像中心（M/2,N/2）处。下图是简单方块图像平移的结果。(a)原图像；(b)无平移的傅立叶频谱；(c)平移后的傅立叶频谱(a)(b)(c)2.3离散傅立叶变换的性质-旋转不变性由旋转不变性可知，如果时域中离散函数旋转θ0角度，则在变换域中该离散傅立叶变换函数也将旋转同样的角度。离散傅立叶变换的旋转不变性如右图所示。（a）原始图像；（b）原始图像的傅立叶频谱；（c）旋转45°后的图像；（d）图像旋转后的傅立叶频谱(a)(b)(d)(c)2.4快速离散傅立叶变换离散傅立叶变换计算量非常大，运算时间长。可以证明其运算次数正比于N2，特别是当N较大时，其运算时间将迅速增长，以至于无法容忍。为此，研究离散傅立叶变换的快速算法(FastFourierTransform，FFT)是非常有必要的。2.4快速离散傅立叶变换一维离散傅立叶变换的快速算法如下式：式中，W=e-j2π/N，称为旋转因子。10)()(NxuxWxfuF2.4快速离散傅立叶变换前面所示的一维离散傅立叶变换（DFT）用矩阵的形式表示为：式中，由Wux构成的矩阵称为W阵或系数矩阵。001020(1)0011121(1)10(1)1(1)2(1)(1)(1)(0)(0)(1)(1)............................................................(1)(1)NNNNNNN2.4快速离散傅立叶变换从上式中的W阵，并结合W的定义，可以发现W是以N为周期的。这样，W阵中很多系数就是相同的，不必进行多次重复计算。同时从下面关系可以看出W的对称性：对于N=4，W阵为：xuNxuNxuNNjN22222,19630642032100000快速离散傅立叶变换由W的周期性得：W4＝W0，W6＝W2，W9＝W1；再由W的对称性可得：W3＝－W1，W2＝－W0。于是上式可变为：1010000010100000快速离散傅立叶变换可见N=4的W阵中只需计算W0和W1两个系数即可。这说明W阵的系数有许多计算工作是重复的，如果把一个离散序列分解成若干短序列，并充分利用旋转因子W的周期性和对称性来计算离散傅立叶变换，便可以简化运算过程，这就是FFT的基本思想。设N为2的正整数次幂，即：,2,12nnn如令M为正整数，且N=2M2.4快速离散傅立叶变换uxMuxMWW22将上式代入F(u)式，离散傅立叶变换可改写成如下形式：10)12(2)2(2101202)12()2()()(MxxuMxuMMxMxuxMWxfWxfWxfuF由旋转因子W的定义可知因此上式变为：uMuxMMxMxuxMWWxfWxfuF21010)12()2()(现定义：1,,1,0,)12()(1,,1,0,)2()(1010MxuWxfuFMxuWxfuFMxuxMoMxuxMe)()()(2uFWuFuFouMe则可得：2.4快速离散傅立叶变换进一步考虑W的对称性和周期性可知，于是：uMMuMWWuMMuMWW22)()()(2uFWuFMuFouMe由此，可将一个N点的离散傅立叶变换分解成两个N／2短序列的离散傅立叶变换，即分解为偶数和奇数序列的离散傅立叶变换Fe(u)和Fo(u)。2.4快速离散傅立叶变换在此，以计算N=8的DFT为例，此时n=3，M=4。)3()3()7()2()2()6()1()1()5()0()0()4()3()3()3()2()2()2()1()1()1()0()0()0(3828180838281808oeoeoeoeoeoeoeoeFWFFFWFFFWFFFWFFFWFFFWFFFWFFFWFF2.4快速离散傅立叶变换前式中，u取0～7时的F(u)、Fe(u)和Fo(u)的关系可用右图描述。左方的两个节点为输入节点，代表输入数值；右方两个节点为输出节点，表示输入数值的叠加，运算由左向右进行。线旁的W18和－W18为加权系数，定义由F(1)、F(5)、Fe(1)和Fo(1)所构成的结构为蝶形运算单元,其表示的运算为：)1()1()5()1()1()1(1818oeoeFWFFFWFF蝶形运算单元Fe(1)F(1)F(5)Fo(1)18W18W－2.4快速离散傅立叶变换由于Fe(u)和Fo(u)都是4点的DFT，因此，如果对它们)1()1()3()0()0()2()1()1()1()0()0()0(28082808eoeeeeoeeeeoeeeeoeeeFWFFFWFFFWFFFWFF)1()1()3()0()0()2()1()1()1()0()0()0(28082808oooeooooeooooeooooeoFWFFFWFFFWFFFWFF2.4快速离散傅立叶变换4点DFT分解为2点DFT的蝶形流程图Fee(0)Feo(1)08W28W－Fee(1)Feo(0)Fe(0)Fe(1)Fe(2)Fe(3)28W08W－Foe(0)Foo(1)08W28W－Foe(1)Foo(0)Fo(0)Fo(1)Fo(2)Fo(3)28W08W－2.4快速离散傅立叶变换8点DFT的蝶形流程图Fee(0)Feo(1)08W28W－Fee(1)Feo(0)Fe(0)Fe(1)Fe(2)Fe(3)28W08W－Foe(0)Foo(1)08W28W－Foe(1)Foo(0)Fo(0)Fo(1)Fo(2)Fo(3)28W08W－f(0)f(4)08W08W－f(2)f(6)08W08W－f(1)f(5)08W08W－f(3)f(7)08W08W－08W18W28W38W08W－18W－28W－38W－F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)2.4快速离散傅立叶变换8点DFT逐级分解框图第一级N/4点DFTf(0)f(4)N/4点DFTf(2)f(6)N/2点DFTN/4点DFTf(1)f(5)N/4点DFTf(3)f(7)N/2点DFT第二级N点DFT第三级F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)3、频域变换的一般表达式--可分离变换二维傅立叶变换可以利用变换核的可分离性，用两次一维变换来实现，即可先对f(x,y)的每一行进行一维变换得到F(x,v)，再沿F(x,v)每一列取一维变换得到变换结果F(u,v)。对于其他的图像变换，只要其变换核如果先对f(x,y)的每一列进行一维变换得到F(y,u)，再沿F(y,u)每一行取一维变换得到F(u,v)，其最终结果是一样的。该结论对反变换核也适用。3、频域变换的一般表达式--图像变换的矩阵表示数字图像都是实数矩阵，设f(x,y)为M×N的图像灰度矩阵，通常为了分析、推导方便，可将可分离变换写成矩阵的形式：F=PfQF=P-1FQ-1其中，F、f是二维M×N的矩阵；P是M×M矩阵；Q是N×N矩阵。4、离散余弦变换（DCT）离散余弦变换（DiscreteCosineTransform，DCT）的变换核为余弦函数。DCT除了具有一般的正交变换性质外，它的变换阵的基向量能很好地描述人类语音信号和图像信号的相关特征。因此，在对语音信号、图像信号的变换中，DCT变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国际标准建议中，都把DCT作为其中的一个基本处理模块。除此之外，DCT还是一种可分离的变换。4.1一维离散余弦变换一维DCT的变换定义为：归一化后为：矩阵形式为：F=Gf1010)(2)0()12(2cos)(2)(NNxxfNFu