姚敏-数字图像处理-第三章-图像变换

1DigitalImageProcessing数字图像处理@zj.com姚敏2第三章图像变换33.1概述4空间域表示法变换域表示法空间域处理法（或称空域法）频域法（或称变换域法）图像表示法图像处理法53.2一维离散傅里叶变换6离散傅里叶变换有限长序列)1,,1,0)((Nxxf10)()]([)(NxuxWxfxfDFTuF1,,1,0Nu10)(1)]([)(NuuxWuFNuFIDFTxf1,,1,0NxNjeW2变换核)()(uFxf定义7离散傅里叶变换)1()1()0()1()1()0()1()1()1(2)1(101)1(121100000Nfff)1()1()0(1)1()1()0()1()1(2)1(1)1(0)1(1121100000NFFF矩阵形式8离散傅里叶变换例其它0101)(Nxxf000111)()()]([)(22210210uuNeeeNeWxfxfDFTuFuNjuNNjuNjNxxuNjNxux其它9离散傅里叶变换例)(nf)(uFunN1001N21…10离散傅里叶变换的性质线性)()(11uFxf)()(22uFxf)()()()(2121ubFuaFxbfxaf如果则11离散傅里叶变换的性质对称性如果则)()(uFxf)()(1ufxFN12离散傅里叶变换的性质时移性如果则)()(uFxfumWuFmxf)()(13离散傅里叶变换的性质频移性如果则)()(uFxf)()(kuFWxfkx14离散傅里叶变换的性质卷积定理如果则)()(uFxf)()(uGxg)()()()(uGuFxgxf15离散傅里叶变换的性质相关定理如果则)()(uFxf)()(uGxg)()()()(*uGuFxgxf16离散傅里叶变换的性质帕斯瓦尔定理如果则)()(uFxf102102|)(|1)(NuNxuFNxf173.3一维快速傅里叶变换18基本思想)1()1()0()1()1()0(NfffNFFFuxW变换矩阵19基本思想变换矩阵元素uxW10lNWW12NWulNuWW)(xuNxuWW)2(③对称性②周期性①不必乘20基本思想由变换矩阵元素可见，利用矩阵元素的周期性与对称性之后，变换矩阵中许多元素相同。换言之，变换矩阵与输入信号相乘过程中存在着不必要的重复计算。利用变换矩阵元素的周期性与对称性，合理安排（即避免）重复出现的相乘运算，就能显著减少计算工作量。改进DFT的关键21一维FFTFFT重要环节重新安排计算次序矩阵分解22一维FFT重新安排计算次序设N=2n，经过n步计算后，其结果为fn(k)=F(l)其中k的二进制表示为100011221120121)2222()(kkkkkkkkknnnnnn1,,1,0}1,0{niki101021120121210)2222(),,,(nnnnnnkkkkkkkkl23一维FFT矩阵分解当N=2n，将变换矩阵分解成n个矩阵，使每个矩阵中每一行仅含有两个非零元素。有两种分解方法：一种是按时间分解一种是按频率分解下面仅介绍按时间分解的FFT算法24一维FFT矩阵分解u和x的二进制表示为10)()]([)(NxuxWxfxfDFTuF1,,1,0Nu100011221120111100011221120111)2222(),,,,()2222(),,,,(uuuuuuuuuxxxxxxxxxnnnnnnnnnnnn10)2222)(2222(012101210011221100112211),,,,(),,,,(NxuuuuxxxxnnnnnnnnnnnnWxxxxfuuuuF25一维FFT矩阵分解N=8=23101010)222)(222(012012012001122001122),,(),,(xxxuuuxxxWxxxfuuuF000112210102000112210011222001122001122001122)222(2)2(4)222(2)222(4)222()222)(222(xuuuxuuuxxuuuxuuuxuuuuuuxxxux1,1,12112228816uxuxux101010)222(2)2(4012012012000112210102}]),,([{),,(xxxxuuuxuuux=8=231040120101202),,(),,(xuxWxxxfxxuf040101),,1(),,0(uWxxfxxf10)24(010101021101),,(),,(xxuuWxxufxuuf)24(00100101),1,(),0,(uuWxufxuf10)24(0102210300012),,(),,(xxuuuWxuufuuuf01224102102)1,,()0,,(uuuWuufuuf),,(),,(2103012uuufuuuF27一维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(4444000011111111ffffffff矩阵分解矩阵表示)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,0,0(11111111662440022222222ffffffff矩阵分解矩阵表示)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(222222227351624033333333ffffffff=8时FFT流程图31一维FFTFFT流程图(1)整个流程需要的计算步数为n=log2N(N=2n)；(2)在第r步计算中，要乘的因子为nrsWrsNr,,1;12,,1,012(3)第r步计算中有2r-1个组，每组有（N/2r-1）个元素，每组的W因子各不相同，且每组只有一种类型的W因子，此因子在组中上一半为正，下一半为负。32一维FFTFFT流程图(4)对比DFT与IDFT的定义式，只要将上述FFT算法中W因子用其共轭代替，并将最后结果乘以1/N，就是计算IDFT即离散傅里叶反变换的快速算法。(5)在每步计算中，需要的乘法次数N/2，加法次数为N，因此FFT的总计算量为：乘法次数为加法次数为而直接计算DFT的计算量为：乘法次数为N2，加法次数为N(N-1)。当N=2048时，DFT需要4194304次乘法运算，而FFT只需要11264次乘法运算，二者之比为NN2log2NN2log4.372)log2/(22NNN333.4二维离散傅里叶变换34二维DFTMN图像)1,,1,0;1,,1,0)(,(NyMxyxf)(21010),(),(NvyMuxjMxNyeyxfvuF1,,1,01,,1,0NvMu)(21010),(1),(NvyMuxjMuNvevuFMNyxf1,,1,01,,1,0NyMx),(),(vuFyxf正变换核反变换核35二维DFTF(u,v)=R(u,v)+jI(u,v)),(|),(|),(vujevuFvuF2/122)],(),([|),(|vuIvuRvuF]),(),([tan),(1vuRvuIvu),(),(|),(||),(|222vuIvuRvuFvuP幅度谱相位谱功率谱36二维DFT性质分离性NuxjNvyjNxNyeeyxfvuF/2/21010]),([),(1,,1,0,NvuNuxjNvyjNuNveevuFNyxf/2/210102]),([1),(1,,1,0,Nyx37二维DFT性质线性如果则),(),(),,(),(2211vuFyxfvuFyxf),(),(),(),(2121vubFvuaFyxbfyxaf38二维DFT性质周期性与共轭对称性如果则),(),(vuFyxf),(),(nNvmNuFvuF),(),(**vuFyxf39二维DFT性质位移性如果则),(),(vuFyxfNvyuxjevuFyyxxf/)(20000),(),(),(),(00/)(200vvuuFeyxfNyvxuj40二维DFT性质尺度变换如果则),(),(vuFyxf),(||1),(bvauFabbyaxf41二维DFT性质旋转性如果则),(),(wFrf),(),(00wFrf42二维DFT性质平均值10102),(1),(NuNvyxfNyxf10102),(1)0,0(NuNvyxfNF)0,0(),(Fyxfu=v=043二维DFT性质卷积如果则),(),(),,(),(vuGyxgvuFyxf),(),(),(),(vuGvuFyxgyxf),(),(),(),(vuGvuFyxgyxf44二维FFT基于二维离散傅里叶变换的分离性，二维离散FFT算法可以用两个一维FFT算法来实现NvyjNyeyxfvxF/210),(),(1,,1,0Nv10/2),(),(NxNuxjevxFvuF1,,1,0Nu45二维FFT46Matlab实现fft函数一维DFTfft2函数二维DFTfftn函数N维DFTifft函数一维IDFTifft2函数二维IDF