第三章-图像变换-数字图像处理课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第三章-图像变换-数字图像处理课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 图像 变换 数字图像 处理 课件
- 资源描述:
-
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
展开阅读全文