第三章-图像变换-数字图像处理课件.ppt

1、1Digital Image Processing 数字图像处理数字图像处理http:/E-MAIL:姚姚 敏敏2第三章第三章 图像变换图像变换3453.2 一维离散傅里叶变换一维离散傅里叶变换 6离散傅里叶变换离散傅里叶变换有限长序列有限长序列)1,1,0)(Nxxf10)()()(NxuxWxfxfDFTuF1,1,0Nu10)(1)()(NuuxWuFNuFIDFTxf1,1,0NxNjeW2变换核变换核)()(uFxf7离散傅里叶变换离散傅里叶变换)1()1()0()1()1()0()1()1()1(2)1(101)1(121100000NfffWWWWWWWWWWWWNFFFNNNN

2、N)1()1()0(1)1()1()0()1()1(2)1(1)1(0)1(1121100000NFFFWWWWWWWWWWWWNNfffNNNNNux8离散傅里叶变换离散傅里叶变换其它0101)(Nxxf000 111 )()()()(22210210uuNeeeNeWxfxfDFTuFuNjuNNjuNjNxxuNjNxux其它9离散傅里叶变换离散傅里叶变换)(nf)(uFunN1001N2110离散傅里叶变换的性质离散傅里叶变换的性质)()(11uFxf)()(22uFxf)()()()(2121ubFuaFxbfxaf11离散傅里叶变换的性质离散傅里叶变换的性质)()(uFxf)()(

3、1ufxFN12离散傅里叶变换的性质离散傅里叶变换的性质)()(uFxfumWuFmxf)()(13离散傅里叶变换的性质离散傅里叶变换的性质)()(uFxf)()(kuFWxfkx14离散傅里叶变换的性质离散傅里叶变换的性质)()(uFxf)()(uGxg)()()()(uGuFxgxf10)()()()(Nhhxghfxgxf15离散傅里叶变换的性质离散傅里叶变换的性质)()(uFxf)()(uGxg)()()()(*uGuFxgxf10)()()()(Nhhxghfxgxf16离散傅里叶变换的性质离散傅里叶变换的性质)()(uFxf102102|)(|1)(NuNxuFNxf173.3 一

4、维快速傅里叶变换一维快速傅里叶变换 18基本思想基本思想)1()1()0()1()1()0(NfffNFFFuxW19基本思想基本思想uxW10lNWW12NWulNuWW)(xuNxuWW)2(对称性 周期性 不必乘20基本思想基本思想21当当n=4n=4时，变换矩阵的简化过程：时，变换矩阵的简化过程：111112322321963064203210000011111111111111111111WWWWWWWWWWWWWWWWWWWWWWWWWWWW运用性质运用性质3简化结果简化结果运用性质运用性质1和性质和性质2简化结果简化结果22例例1：令：令N=2n，下面以，下面以N=4(n=2)时

5、的傅立叶时的傅立叶变换为例来说明快速傅立叶变换的基本思想：变换为例来说明快速傅立叶变换的基本思想：)1()3()2()1()0()3()2()1()0(9630642032100000ffffWWWWWWWWWWWWWWWWFFFF)3()2()1()0(1111)3()2()1()0()3()1()2()0(5233212020009630321064200000ffffWWWWWWWWWWWWffffWWWWWWWWWWWWWWWWFFFF重新安排计算次序重新安排计算次序利用周期性简化利用周期性简化232121222003120)3()2()1()0(0100010100011001000

6、01001)3()1()2()0(ffWfWWffffWWWWWWWWFFFFW200002200111111)3()1()2()0()3()1()2()0()3()1()2()0()3()1()2()0()3()1()2()0(WffWffWffWffWffWffWffWfffwfffff分解成分解成n=2个矩阵，使每个矩阵中每一行中只有两个元素不为个矩阵，使每个矩阵中每一行中只有两个元素不为0W1f2次乘法次乘法4次加法次加法242121222003120)3()2()1()0(010001010001100100001001)3()1()2()0(ffWfWWffffWWWWWWWWFF

7、FFW21111110110111222222)3()2()3()2()1()0()1()0()3()2()1()0()3()1()2()0(WffWffWffWfffwffffFFFFf分解成分解成n=2个矩阵个矩阵：W1f2次乘法次乘法4次加法次加法252121222003120)3()2()1()0(010001010001100100001001)3()1()2()0(ffWfWWffffWWWWWWWWFFFFW2分解成分解成n=2个矩阵个矩阵：W1f)3()2()1()0()3()2()1()0(9630642032100000ffffWWWWWWWWWWWWWWWWFFFF共共4

8、次乘法运算，次乘法运算，8次加法运算次加法运算共共16次乘法运算，次乘法运算，12次加法运算次加法运算26例例2：以：以N=8(n=3)时的傅立叶变换在重新安排时的傅立叶变换在重新安排计算次序并将计算次序并将Wux分解成分解成n=3个矩阵：个矩阵：.;)7()6()5()4()3()2()1()0()7()6()5()4()3()2()1()0(23312211333333333323123123FfWffWffWffffffffffFFFFFFFFFffWfWWfWWWF44440000111111111wwwwwwwwW662244002010001010001010001010001ww

9、wwwwwwW27例例2：以：以N=8(n=3)时的傅立叶变换在重新安排时的傅立叶变换在重新安排计算次序并将计算次序并将Wux分解成分解成n=3个矩阵：个矩阵：73516240311111111wwwwwwwwW可见，可见，N=8=23时需要进行时需要进行3步不计算步不计算，4 4次乘法，次乘法，8 8次加法运算，一共需要次加法运算，一共需要1212次乘法，次乘法，2424次加法运算，而次加法运算，而直接计算直接计算DFTDFT是需要是需要6464次乘法运算，次乘法运算，5656次加法运算。次加法运算。空白处均为空白处均为028一维一维FFT29一维一维FFT设N=2n，经过n步计算后，其结果

10、为其中 的二进制表示为100011221120121)2222()(kkkkkkkkknnnnnn1,1,0 1,0niki101021120121210)2222(),(nnnnnnkkkkkkkkl30一维一维FFT 当，将变换矩阵分解成 个矩阵，使每个矩阵中每一行仅含有两个非零元素。有两种分解方法：一种是按时间分解一种是按频率分解31一维一维FFTu和x的二进制表示为 10)()()(NxuxWxfxfDFTuF1,1,0Nu100011221120111100011221120111)2222(),()2222(),(uuuuuuuuuxxxxxxxxxnnnnnnnnnnnn10)2

11、222)(2222(012101210011221100112211),(),(NxuuuuxxxxnnnnnnnnnnnnWxxxxfuuuuF32一维一维FFTN=8=23 101010)222)(222(012012012001122001122),(),(xxxuuuxxxWxxxfuuuF000112210102000112210011222001122001122001122)222(2)2(4)222(2)222(4)222()222)(222(xuuuxuuuxxuuuxuuuxuuuuuuxxxuxWWWWWWWW1,1,12112228816uxuxuxWWW 101010

12、)222(2)2(4012012012000112210102),(),(xxxxuuuxuuuxWWWxxxfuuuF33一维一维FFTN=8=23 1040120101202),(),(xuxWxxxfxxuf040101),1(),0(uWxxfxxf10)24(010101021101),(),(xxuuWxxufxuuf)24(00100101),1,(),0,(uuWxufxuf10)24(0102210300012),(),(xxuuuWxuufuuuf01224102102)1,()0,(uuuWuufuuf),(),(2103012uuufuuuF34一维一维FFT)1,1,

13、1()0,1,1()1,0,1()0,0,1()1,1,0()0,1,0()1,0,0()0,0,0(11111111)1,1,1()0,1,1()1,0,1()0,0,1()1,1,0()0,1,0()1,0,0()0,0,0(4444000011111111ffffffffWWWWWWWWffffffff04ww35一维一维FFT)1,1,1()0,1,1()1,0,1()0,0,1()1,1,0()0,1,0()1,0,0()0,0,0(0100010100201010001010001)1,1,1()0,1,1()1,0,1()0,0,1()1,1,0()0,1,0()1,0,0()0

14、,0,0(11111111662440022222222ffffffffWWWWWWWWffffffff2604,wwww36一维一维FFT)1,1,1()0,1,1()1,0,1()0,0,1()1,1,0()0,1,0()1,0,0()0,0,0(11111111)1,1,1()0,1,1()1,0,1()0,0,1()1,1,0()0,1,0()1,0,0()0,0,0(222222227351624033333333ffffffffWWWWWWWWffffffff3715,wwww37一维一维FFT38一维一维FFT(1)整个流程需要的计算步数为n=log2N(N=2n)；(2)在第r

15、步计算中，要乘的因子为nrsWrsNr,1;12,1,0 12(3)第r步计算中有2r-1个组，每组有（N/2r-1）个元素，每组的W因子各不相同，且每组只有一种类型的W因子，此因子在组中上一半为正，下一半为负。例如:N=8、如r=3时，第三组第一个待求量x3(1,0,0),k=(1,0,0)，右移n-r=0位，得k=(1,0,0),再逆位得k0=(0,0,1)，故w因子为w1。39一维一维FFT(4)对比DFT与IDFT的定义式，只要将上述FFT算法中W因子用其共轭代替，并将最后结果乘以1/N，就是计算IDFT即离散傅里叶反变换的快速算法。(5)在每步计算中，需要的乘法次数N/2，加法次数为

16、N，因此FFT的总计算量为：乘法次数为 加法次数为 而直接计算DFT的计算量为：乘法次数为N2，加法次数为N(N-1)。当N=2048时，DFT需要4194304次乘法运算，而FFT只需要11264次乘法运算，二者之比为 NN2log2NN2log4.372)log2/(22NNN403.4 二维离散傅里叶变换二维离散傅里叶变换 41二维二维DFT)1,1,0;1,1,0)(,(NyMxyxf)(21010),(),(NvyMuxjMxNyeyxfvuF1,1,01,1,0NvMu)(21010),(1),(NvyMuxjMuNvevuFMNyxf1,1,01,1,0NyMx),(),(vuF

17、yxf42二维二维DFTF(u,v)=R(u,v)+jI(u,v),(|),(|),(vujevuFvuF2/122),(),(|),(|vuIvuRvuF),(),(tan),(1vuRvuIvu),(),(|),(|),(|222vuIvuRvuFvuP43二维二维DFT性质性质NuxjNvyjNxNyeeyxfvuF/2/21010),(),(1,1,0,NvuNuxjNvyjNuNveevuFNyxf/2/210102),(1),(1,1,0,Nyx44二维二维DFT性质性质),(),(),(),(2211vuFyxfvuFyxf),(),(),(),(2121vubFvuaFyxbf

18、yxaf45二维二维DFT性质性质),(),(vuFyxf),(),(nNvmNuFvuF),(),(*vuFyxf46二维二维DFT性质性质),(),(vuFyxfNvyuxjevuFyyxxf/)(20000),(),(),(),(00/)(200vvuuFeyxfNyvxuj47二维二维DFT性质性质),(),(vuFyxf),(|1),(bvauFabbyaxf48二维二维DFT性质性质),(),(wFrf),(),(00wFrf49二维二维DFT性质性质10102),(1),(NuNvyxfNyxf10102),(1)0,0(NuNvyxfNF)0,0(),(Fyxfu=v=050二

19、维二维DFT性质性质),(),(),(),(vuGyxgvuFyxf),(),(),(),(vuGvuFyxgyxf),(),(),(),(vuGvuFyxgyxf51二维二维FFTNvyjNyeyxfvxF/210),(),(1,1,0Nv10/2),(),(NxNuxjevxFvuF1,1,0Nu52二维二维FFT53Matlab实现实现54Matlab实现实现 55Matlab实现实现 563.5 离散余弦变换离散余弦变换 57一维一维DCT1002)12(cos)()()(NxNuxxfucuF1,1,0Nu1012)12(cos)()()(NuNuxuFucxf1,1,0NxN210

20、01021)(uuuc58一维一维FDCT59一维一维FDCT60一维一维FDCT61一维一维FDCT 不计不计83sin)2()1(83cos)3()0(821cos)3(815cos)2(89cos)1(83cos)0()3(4cos)2()1(4cos)3()0(814cos)3(810cos)2(86cos)1(82cos)0()2(8sin)2()1(8cos)3()0(87cos)3(85cos)2(83cos)1(8cos)0()1(4cos)2()1(4cos)3()0()3()2()1()0(21)0(ffffffffFffffffffFffffffffFffffffffF6

21、2一维一维FDCT8sin;8cosiSiiCi63一维一维FDCT16sin;16cosiSiiCi64二维二维DCTNvyNuxyxfvucvuFNxNy2)12(cos2)12(cos),(),(),(101001,1,0,NvuNvyNuxvuFvucyxfNuNv2)12(cos2)12(cos),(),(),(101011,1,0,Nyx2104N0102/102/1),(uvvuuvvuvuc且65Matlab实现实现66Matlab实现实现 67应应 用用例如，在JPEG图像压缩算法中，首先将输入图像划分为88的方块，然后对每一个方块执行二维离散余弦变换，最后将变换得到的量化的

22、DCT系数进行编码和传送，形成压缩后的图像格式。在接受端，将量化的DCT系数进行解码，并对每个88方块进行二维IDCT，最后将操作完成后的块组合成一幅完整的图像。68应应 用用88方块经正变换后得到的DCT矩阵F=F(u,v)的左上角代表图像的低频分量，右下角代表图像的高频分量，F(O,0)为直流分量(DC)。DCT改变了信号能量的分布方式，使信号能量的分中于低频区(即DC与DC附近)。换言之，DCT矩阵F中大多数的DCT系数的值非常接近于零，舍弃这些接近于零的DCT系数值，就可以节约大量的存储空间，而在重构图像时又不会使图像质量显著下降。6970离散沃尔什变换离散沃尔什变换 离散傅里叶变换和

23、离散余弦变换在快速算法中要用到复数乘离散傅里叶变换和离散余弦变换在快速算法中要用到复数乘法、三角函数乘法，运算占用时间较多。在某一些应用领域，法、三角函数乘法，运算占用时间较多。在某一些应用领域，需要更有效和便利的变换算法。离散沃尔什需要更有效和便利的变换算法。离散沃尔什(Walsh)(Walsh)变换就是其变换就是其中的一种。中的一种。1.1.一维一维离散沃尔什变换离散沃尔什变换 一维沃尔什变换核：一维沃尔什变换核：是沃尔什变换的阶数。有，如位。的二进制的第是其中n2102k10)()(2N1(z)b0,(z)b1,(z)b,(101)5z3nkz)z()1(1),(1bNuxgniubxb

24、ini71离散沃尔什变换离散沃尔什变换 一维离散沃尔什变换可写成一维离散沃尔什变换可写成：1N,1,0u)1(f(x)N1W(u)10)()(1-N0 x1niubxbini一维离散沃尔什逆变换核：一维离散沃尔什逆变换核：10)()(1)1(),(hniubxbiniux1N,1,0 x)1(W(u)f(x)10)()(1-N0u1niubxbini一维离散沃尔什逆变换可写成一维离散沃尔什逆变换可写成：72离散沃尔什变换离散沃尔什变换 一维离散沃尔什正变换与逆变换只差一个常数项1/N，所以正变换算法也可用于逆变换。由沃尔什变换核组成的矩阵是一个对称矩阵对称矩阵且其行和列正交行和列正交，即任意两

25、行相乘或两列相乘后的的各数之和必为零。例如当n=2,N=4时的变换核矩阵为G4：111111111111111141G473离散沃尔什变换离散沃尔什变换 而当而当n=3,N=8时的变换核矩阵为时的变换核矩阵为G8：111111111111111111111111111111111111111111111111111111111111111181G874离散沃尔什变换离散沃尔什变换 2.2.二维离散沃尔什变换二维离散沃尔什变换 二维沃尔什正变换核和逆变换核分别为：二维沃尔什正变换核和逆变换核分别为：10)v()y()()(10)v()y()()(21111)1()v,y,(h)1(1)v,y,(

26、nibbubxbnibbubxbiniiniiniiniuxNuxg由上式可见：由上式可见：v)(y,u)h(x,h)v,y,(hv)(y,u)g(x,g)v,y,(1111uxuxg 二维沃尔什正变换核和逆变换核是二维沃尔什正变换核和逆变换核是可分离可分离和和对称对称的。因的。因此二维沃尔什变换可以用两步一维离散沃尔什变换此二维沃尔什变换可以用两步一维离散沃尔什变换75离散沃尔什变换离散沃尔什变换 二维沃尔什正变换和逆变换分别为：二维沃尔什正变换和逆变换分别为：1N,1,0yx,)1(v)W(x,y)f(x,1N,1,0vu,)1(f(x)N1v)W(u,10)v()y()()(1-N0 x

27、10)v()y()()(1-N0 x21111nibbubxbnibbubxbiniiniiniini76离散哈达玛变换离散哈达玛变换 77离散哈达玛变换离散哈达玛变换 )()(1010)1()(1)(ubxbNxiNiixfNuB1,1,0Nu)()(1010)1()()(ubxbNuiNiiuBxf1,1,0Nx78快速哈达玛变换算法快速哈达玛变换算法 )(1:,)1()1()0()1()1()0(:N1B:单位矩阵具有重要性质阶哈达马矩阵是其中矩阵形式一维快速哈达马变换的IHHnnHNffffNBBBBfHnnnn79快速哈达玛变换算法快速哈达玛变换算法 1111111111111111

28、4N:21111:)1(21111211111HHHHHHHHHHNHnNnnnnnn阶哈达马矩阵为：例如阶哈达马矩阵为阶哈达马矩阵为80)7()6()5()4()3()2()1()0(81)7()6()5()4()3()2()1()0(N1B2222ffffffffHHHHBBBBBBBBfHn81)2.1(#)7()3()6()2()5()1()4()0(81)7()6()5()4(81)3()2()1()0(81)7()6()5()4()1.1(#)7()3()6()2()5()1()4()0(81)7()6()5()4(81)3()2()1()0(81)3()2()1()0(22222

29、2ffffffffHffffHffffHBBBBffffffffHffffHffffHBBBB快速哈达玛变换算法快速哈达玛变换算法 82)7()6()5()4(81)7()6()5()4()3()2()1()0(81)3()2()1()0(7,6,5,4)()4()(3,2,1,0)4()()(111111111111111111ffffHHHHBBBBffffHHHHBBBBllflflfllflflf引入记号：快速哈达玛变换算法快速哈达玛变换算法 83)4.2(#)7()6(81)7()5()6()4(81)7()6()3.2(#)5()4(81)7()5()6()4(81)5()4()2

30、.2(#)3()2(81)3()1()2()0(81)3()2()1.2(#)1()0(81)3()1()2()0(81)1()0(22111111221111112211111122111111ffHffffHBBffHffffHBBffHffffHBBffHffffHBB84)3(#)7()7()6()7(8)6()7()6()6(8)5()3()4()5(8)4()3()4()4(8)3()3()2()3(8)2()3()2()2(8)1()1(0)1(8)0()1()0()0(8322322322322322322322322fffBfffBfffBfffBfffBfffBfffBff

31、fB85离散哈达玛变换离散哈达玛变换 86一维快速哈达玛变换算法一维快速哈达玛变换算法 FHT(1)整个流程需要的计算步数为n=log2N(N=2n)，设r为计算序号，则r=1,2,.,n；(2)第r步计算中有2r-1个组，每组中包括（N/2r-1）加减法，在每组中这些基萨中有半数为加法，半数为减法。每一步共有N次加减法；(3)计算全部变换系数的总运算次数为Nlog2N，而直接运算则需要N2次加减法；(4)这种快速运算可以直接用于逆变换，因为正逆变换只差一个常数。87离散哈达玛变换离散哈达玛变换 )()()()(1010210)1(),(1),(vbybubxbNxNyiNiiiiyxfNvu

32、B1,1,0,Nvu)()()()(101010)1(),(),(vbybubxbNuNviNiiiivuByxf1,1,0,Nyx8889变换变换 霍特林（Hotelling）变换是一种基于图像统计特性的变换霍特林变换可直接用于对数字图像的变换它在连续域对应的变换是KL（Karhunen-Loeve）变换霍特林变换：特征值变换、主分量变换、离散KL变换 90变换变换 TNxxx),(21xxmEx)(TxxxEmxmxCNNijxc)(C91变换变换 xC),2,1(Nii)1,2,1(1Niii),2,1(NiiejijijTi01eeNiiiix,2,1 eeC92变换变换 )(21Ne

33、ee)()(2121xTNTTxTNyyymxeeemxy93变换变换 0 )(xTTxTyEEEmxmxymTxxTTxxTTyyyEEE)()()(mxmxmxmxmymyCxTCN21y的协方差矩阵除对角线以的协方差矩阵除对角线以外的元素均为零，即外的元素均为零，即y的各的各分量是彼此不相关的。因此分量是彼此不相关的。因此，霍特林变换消除了数据之，霍特林变换消除了数据之间的相关性，从而在信息压间的相关性，从而在信息压缩方面起着重要的作用缩方面起着重要的作用 94变换变换 )(1xTTTmxyI和NKjjKjjNjjmsxjkjjxkxexxNKmeymykexKxxmyx1111:,K)

34、(e,1),(,K)(e,KLx其均方误差为时近似当用即次部分展开式的为令展开式的称为得：95变换特性变换特性 NKjjKjjNjjmsexx111:,K)(e,其均方误差为时近似当用9697Radon变换变换 Radon变换是计算图像在某一指定角度射线方向上投影的变换方法在垂直方向上的二维线积分就是在x轴上的投影在水平方向上的二维线积分就是在y轴上的投影98Radon变换变换 99Radon变换变换 的Radon变换式 ),(yxf)cossin,sincos()(dyyxyxfxRyxyxcossinsincos100Radon变换变换 101Matlab实现实现 I表示需要变换的图像 Theta表示变换的角度 R的各行返回theta中各方向上的radon变换值 xp表示向量沿轴相应的坐标轴radon逆变换可以根据投影数据重建图像,在X射线断层摄影分析中常常使用102Matlab实现实现 103Matlab实现实现 104Matlab实现实现