数字图像处理傅立叶变换精品文稿.ppt

《数字图像处理傅立叶变换精品文稿.ppt》由会员分享，可在线阅读，更多相关《数字图像处理傅立叶变换精品文稿.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数字图像处理傅立叶变换第1页，本讲稿共46页3.3.1 可分离性可分离性 二维离散傅立叶变换二维离散傅立叶变换DFTDFT可分离性的基本可分离性的基本思想是：思想是：二维二维DFTDFT可分离为两次一维可分离为两次一维DFTDFT。应用：应用：二维快速傅立叶算法二维快速傅立叶算法FFT FFT，是通过计算两次，是通过计算两次一维一维FFTFFT实现的。实现的。第2页，本讲稿共46页3.3.1 可分离性可分离性可分离性的定义可分离性的定义u=0,1,2,u=0,1,2,M-1M-1；v=0,1,2,.N-1v=0,1,2,.N-1x=0,1,2,x=0,1,2,M-1M-1；y=0,1,2,.N

2、-1y=0,1,2,.N-1第3页，本讲稿共46页3.3.1 可分离性可分离性可分离性成立的推导可分离性成立的推导先对行（先对行（y y变量）做变换：变量）做变换：然后对列（然后对列（x x变量）进行变换：变量）进行变换：第4页，本讲稿共46页3.3.1 可分离性可分离性先对行做变换：先对行做变换：然后对列进行变换：然后对列进行变换：f(x,y)（0,0）（M-1，N-1）xyF(x,v)（0,0）（M-1，N-1）xvF(x,v)（0,0）（M-1，N-1）xvF(u,v)（0,0）（M-1，N-1）uv第5页，本讲稿共46页 傅立叶变换对有如下平移性质：傅立叶变换对有如下平移性质：f(x,

3、y)expj2(u0 x/M+v0y/N)F(u-u0,v-v0)和和 f(x-x0,y-y0)F(u,v)exp-j2(ux0/M+vy0/N)以上式子表明，以上式子表明，在频域中原点平移到在频域中原点平移到(u0,v0)时，时，其对应的其对应的f(x,y)要乘上一个正的指数项：要乘上一个正的指数项：expj2(u0 x/M+v0y/N)；在空域中图像原点平移到在空域中图像原点平移到(x0,y0)时，时，其其对应的对应的F(u,v)要乘上一个负的指数项：要乘上一个负的指数项：exp-j2(ux0/M+vy0/N)。3.3.2 平移性平移性第6页，本讲稿共46页 对于对于M=N，则类似地有：则

4、类似地有：f(x,y)expj2(u0 x+v0y)/N F(u-u0,v-v0)和和 f(x-x0,y-y0)F(u,v)exp-j2(ux0+vy0)/N 在频域中原点平移到在频域中原点平移到(u0,v0)时，其对应的时，其对应的f(x,y)要要乘上一个正的指数项乘上一个正的指数项expj2(u0 x+v0y)/N；在空域中图像原点平移到在空域中图像原点平移到(x0,y0)时，时，其其对应的对应的F(u,v)要乘上一个负的指数项要乘上一个负的指数项exp-j2(ux0+vy0)/N。3.3.2 平移性平移性第7页，本讲稿共46页3.3.2 平移性平移性 在数字图像处理中，常常需要将在数字图

5、像处理中，常常需要将F(u,v)的原点的原点移到移到NN频域的中心（平移前空域、频域原点均频域的中心（平移前空域、频域原点均在左上方），以便能清楚地分析傅立叶谱的情况。在左上方），以便能清楚地分析傅立叶谱的情况。要做到此，只需令要做到此，只需令 u0=v0=N/2则则expj2(u0 x+v0y)/N=所以所以f(x,y)(-1)x+y F(u-N/2,v-N/2)上式说明：如果需要将图像傅立叶谱的原点从上式说明：如果需要将图像傅立叶谱的原点从左上角左上角(0,0)移到中心点移到中心点(N/2,N/2)，只要，只要f(x,y)乘上乘上(-1)x+y因子进行傅立叶变换即可实现。因子进行傅立叶变换

6、即可实现。第8页，本讲稿共46页3.3.2 平移性平移性 平移性告诉我们一个感兴趣的事实：当空域中平移性告诉我们一个感兴趣的事实：当空域中f(x,y)产生产生移动时，在频域中只发生相移，并不影响移动时，在频域中只发生相移，并不影响它的傅立叶变换的幅值，因为它的傅立叶变换的幅值，因为 反之，当频域中反之，当频域中F(u,v)产生产生移动时，相应的移动时，相应的f(x,y)在空域中也只发生相移，而幅值不变。在空域中也只发生相移，而幅值不变。第9页，本讲稿共46页3.3.3 周期性和共轭对称性周期性和共轭对称性1.1.周期性周期性 离散傅立叶变换离散傅立叶变换DFTDFT和它的逆变换是以和它的逆变换

7、是以N N为周期的。为周期的。对于一维傅立叶变换有：对于一维傅立叶变换有：F(u)=F(ukN)F(u)=F(ukN)k=0,1,2,k=0,1,2,对于二维傅立叶变换有：对于二维傅立叶变换有：F(u,v)=F(ukN,vlN)F(u,v)=F(ukN,vlN)k=0,1,2,k=0,1,2,l=0,1,2,l=0,1,2,第10页，本讲稿共46页3.3.3 周期性和共轭对称性周期性和共轭对称性类似有：类似有：f(xkN,ylN)=f(x,y)即从即从DFT的角度来看，反变换得到的图像阵的角度来看，反变换得到的图像阵列也是二维循环。列也是二维循环。第11页，本讲稿共46页3.3.3 周期性和共

8、轭对称性周期性和共轭对称性2.2.共轭对称性共轭对称性 傅立叶变换结果是以原点为中心的共轭对称傅立叶变换结果是以原点为中心的共轭对称函数。函数。对于一维傅立叶变换有：对于一维傅立叶变换有：F(u)=FF(u)=F*(kN-u)(kN-u)k=0,1,2,k=0,1,2,对于二维傅立叶变换有：对于二维傅立叶变换有：F(u,v)=FF(u,v)=F*(kN-u,lN-v)(kN-u,lN-v)k=0,1,2,k=0,1,2,l=0,1,2,l=0,1,2,第12页，本讲稿共46页周期性和共轭对称性举例周期性和共轭对称性举例3.3.3 周期性和共轭对称性周期性和共轭对称性第13页，本讲稿共46页3.

9、二维离散的傅立叶变换结果中频率的分布二维离散的傅立叶变换结果中频率的分布对应低频成分对应低频成分直流部分直流部分二维二维DFT二维二维IDFT图像图像对应高频成分对应高频成分对应低频成分对应低频成分对应高频成分对应高频成分1 42 3直流部分直流部分换位换位3421光学的二维光学的二维DFT第14页，本讲稿共46页3.3.3 周期性和共轭对称性周期性和共轭对称性 存储存储DFT结果的二维数组中频率成分的分布，如结果的二维数组中频率成分的分布，如上图所示，即数组的左上角相当于直流部分，左上、上图所示，即数组的左上角相当于直流部分，左上、右上、左下、右下各角的周围对应低频成分，数组中右上、左下、右

10、下各角的周围对应低频成分，数组中央部分附近对应于高频成分。为了使直流成分出现在央部分附近对应于高频成分。为了使直流成分出现在数组中央，在把画面分成四分的基础上，进行如图所数组中央，在把画面分成四分的基础上，进行如图所示的换位也是可以的。示的换位也是可以的。使中央对直流部分这样的二维傅立叶变换称作使中央对直流部分这样的二维傅立叶变换称作光学光学傅立叶变换傅立叶变换(optical Fourier transform)。第15页，本讲稿共46页3.3.4 旋转特性旋转特性旋转特性描述：旋转特性描述：如果如果f(x,y)f(x,y)旋转了一个角度旋转了一个角度 ，那么，那么f(x,y)f(x,y)旋

11、转后的旋转后的图像的傅立叶变换也旋转了相同的角度图像的傅立叶变换也旋转了相同的角度 。结论：结论：对对图图像像的的旋旋转转变变换换和和傅傅立立叶叶变变换换的的顺顺序序是是可可交换的。交换的。FRf(x,y)FRf(x,y)RFf(x,y)RFf(x,y)第16页，本讲稿共46页3.3.4 旋转特性旋转特性 反之，如果反之，如果F(u,v)旋转某一角度，则旋转某一角度，则f(x,y)在空间在空间域也旋转同样的角度。域也旋转同样的角度。若引入极坐标若引入极坐标 则则f(x,y)和和F(u,v)分别变为分别变为f(r,)和和F(,)。在极坐标中存。在极坐标中存在以下变换对：在以下变换对：f(r,+0

12、)F(,+0)这条性质以极坐标代以这条性质以极坐标代以x,y,u,v，则可以得到证明。，则可以得到证明。第17页，本讲稿共46页3.3.5 线性与比例性线性与比例性1.1.线性线性 线性的描述：傅立叶变换是线性系统、函数线性的描述：傅立叶变换是线性系统、函数和的傅立叶变换是可分离的。和的傅立叶变换是可分离的。设：设：f(x,y)f(x,y)的傅立叶变换为的傅立叶变换为Ff(x,y)Ff(x,y)g(x,y)g(x,y)的傅立叶变换为的傅立叶变换为Fg(x,y)Fg(x,y)有：有：Ff(x,y)+g(x,y)=Ff(x,y)+Fg(x,y)Ff(x,y)+g(x,y)=Ff(x,y)+Fg(x

13、,y)第18页，本讲稿共46页3.3.5 线性与比例性线性与比例性2.2.比例性比例性 比例性的描述：比例性的描述：af(x,y)af(x,y)aF(u,v)aF(u,v)且有：且有：f(ax,by)f(ax,by)1/|ab|F(u/a,v/b)1/|ab|F(u/a,v/b)第19页，本讲稿共46页3.3.6 均值性均值性均值性的描述：均值性的描述：离散函数的均值等于该函数傅立叶变换在离散函数的均值等于该函数傅立叶变换在(0,0)(0,0)点的值。点的值。第20页，本讲稿共46页3.3.7 卷积与相关卷积与相关卷积与相关卷积与相关:空域和频域之间的基本联系空域和频域之间的基本联系1.1.卷

14、积卷积 卷积定理的描述：卷积定理的描述：空域中的卷积等价于频域中的相乘空域中的卷积等价于频域中的相乘f(x,y)*g(x,y)f(x,y)*g(x,y)F(u,v)G(u,v)F(u,v)G(u,v)Ff(x,y)*g(x,y)=F(u,v)G(u,v)Ff(x,y)*g(x,y)=F(u,v)G(u,v)同时有：同时有：f(x,y)g(x,y)f(x,y)g(x,y)F(u,v)*G(u,v)F(u,v)*G(u,v)第21页，本讲稿共46页3.3.7 卷积与相关卷积与相关2.相关相关 相关定理的描述：相关定理的描述：空域中空域中f(x,y)f(x,y)与与g(x,y)g(x,y)的相关等价

15、于频域的相关等价于频域中中F(u,v)F(u,v)的共轭与的共轭与G(u,v)G(u,v)相乘相乘 f(x,y)f(x,y)g(x,y)g(x,y)F F*(u,v)G(u,v)(u,v)G(u,v)同时有：同时有：f f*(x,y)g(x,y)(x,y)g(x,y)F(u,v)F(u,v)G(u,v)G(u,v)第22页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换 FFT FFT算法基于一个叫做算法基于一个叫做递推加倍递推加倍的方法，通的方法，通过推导将过推导将DFTDFT转换成两个递推公式。为方便起见转换成两个递推公式。为方便起见我们用下式表达离散傅立叶变换公式：我们用下式表达离散

16、傅立叶变换公式：1.FFT1.FFT算法算法基本思想基本思想 这里这里 WN=exp(-j2/N)是一个常数是一个常数第23页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换递推公式推导递推公式推导 假设假设N N为：为：N=2N=2n n 其中其中n n是一个正整数，因此是一个正整数，因此N N可表示为：可表示为：N=2MN=2M 这这里里M M仍仍然然是是一一个个正正整整数数。将将N N=2M2M代代入入前前一一页页的的式式子子，得到：得到：第24页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换所以：所以：由于：由于：W WN N=exp(-j2=exp(-j2/N)/N)代入前

17、页式子有：代入前页式子有：第25页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换定义两个符号：定义两个符号：偶数部分偶数部分u=0,1,2,u=0,1,2,M-1M-1奇数部分奇数部分u=0,1,2,u=0,1,2,M-1M-1第26页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换得出得出FFT FFT 的第一个递推公式：的第一个递推公式：该公式说明该公式说明F(u)F(u)可以通过偶部和奇部之和来计算。可以通过偶部和奇部之和来计算。第27页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换另有：另有：W WM Mu+M u+M=expexp-2j-2j(u+M)/M(u+M)/

18、M=exp-2j=exp-2j u/Mexp-2ju/Mexp-2j =W WM Mu ue ej j(-2)(-2)=W WM Mu u(-1)(-1)(-2)(-2)=W WM Mu u且：且：W W2M2Mu+M u+M=expexp-2j-2j(u+M)/2M(u+M)/2M =exp-2jexp-2j u/2M u/2M e ej j(-1)(-1)=W W2M2Mu u(-1)(-1)(-1)(-1)=-=-W W2M2Mu u最后有：最后有：W WM Mu+M u+M=W WM Mu u ；W W2M2Mu+M u+M=-W W2M2Mu u第28页，本讲稿共46页得出得出u+M

19、的的DFT:第29页，本讲稿共46页得出得出FFTFFT的第二个递推公式：的第二个递推公式：3.4 快速傅立叶变换快速傅立叶变换该公式说明该公式说明F(u+M)F(u+M)可以通过可以通过F(u)F(u)偶部和奇部之差来计偶部和奇部之差来计算。算。F(u+M)=1/2(FF(u+M)=1/2(Feveneven(u)-F(u)-Foddodd(u)W(u)W2M2Mu u)第30页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换得出得出FFTFFT的两个递推公式：的两个递推公式：F(u)=1/2(F F(u)=1/2(Feveneven(u)(u)+F Foddodd(u)W(u)W2M2

20、Mu u)F(u+M)=1/2(F F(u+M)=1/2(Feveneven(u)(u)-F Foddodd(u)W(u)W2M2Mu u)第31页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换分析这些表达式得到如下一些有趣的特性：分析这些表达式得到如下一些有趣的特性：（1 1）一个）一个N N个点的变换，能够通过将原始表达个点的变换，能够通过将原始表达 式分成两个部分来计算。式分成两个部分来计算。（2 2）通过计算两个（）通过计算两个（N/2N/2）个点的变换。得到）个点的变换。得到 F Feveneven(u)(u)和和 F Foddodd(u)(u)。（3 3）偶部与奇部之和得到）

21、偶部与奇部之和得到F(u)F(u)的前的前(N/2)(N/2)个值。个值。（4 4）偶部与奇部之差得到）偶部与奇部之差得到F(u)F(u)的后的后(N/2)(N/2)个值。个值。且不需要额外的变换计算。且不需要额外的变换计算。第32页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换归纳快速傅立叶变换的思想：归纳快速傅立叶变换的思想：1 1）通过计算两个单点的）通过计算两个单点的DFTDFT，来计算两个点的，来计算两个点的DFTDFT。2 2）通通过过计计算算两两个个双双点点的的DFTDFT，来来计计算算四四个个点点的的DFTDFT，以此类推。，以此类推。3 3）对对于于任任何何N=2N=2

22、n n的的DFTDFT的的计计算算，通通过过计计算算两两个个N/2N/2点点的的DFTDFT，来计算，来计算N N个点的个点的DFTDFT。第33页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换2.逆向逆向FFT算法算法算法思想描述：用正向变换计算逆向变换。算法思想描述：用正向变换计算逆向变换。u=0,1,2,.N-1u=0,1,2,.N-1x=0,1,2,.N-1x=0,1,2,.N-1第34页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换 在离散逆向变换表达式两边同取共轭，并除在离散逆向变换表达式两边同取共轭，并除N Nu=0,1,2,.N-1u=0,1,2,.N-1 可以看出

23、，上式的右端在形式上就是傅立叶正变换。可以看出，上式的右端在形式上就是傅立叶正变换。因此，只要将因此，只要将F*(u)输入，用正向变换算法计算，得到输入，用正向变换算法计算，得到1/Nf*(x)，取共轭并乘上取共轭并乘上N，即得到，即得到f(x)。第35页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换3.FFTFFT算法实现举例算法实现举例通过一个实例来体会一下通过一个实例来体会一下FFTFFT算法：算法：设：有函数设：有函数f(x)f(x)，其，其 N=2N=23 3=8=8，有：有：f(0),f(1),f(2),f(3),f(4),f(5),f(0),f(1),f(2),f(3),f

24、(4),f(5),f(6),f(7)f(6),f(7)计算：计算：F(0),F(1),F(2),F(3),F(4),F(5),F(0),F(1),F(2),F(3),F(4),F(5),F(6),F(7)F(6),F(7)第36页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换首先分成奇偶两组，有：首先分成奇偶两组，有：f(0),f(2),f(4),f(6)f(0),f(2),f(4),f(6)f(1),f(3),f(5),f(7)f(1),f(3),f(5),f(7)为了利用递推特性，再分成两组，有：为了利用递推特性，再分成两组，有：f(0),f(4)f(0),f(4)，f(2),f(6

25、)f(2),f(6)f(1),f(5)f(1),f(5)，f(3),f(7)f(3),f(7)第37页，本讲稿共46页 f(0),f(4)f(2),f(6)f(1),f(5)f(3),f(7)F2(0),F2(4)F2(2),F2(6)F2(1),F2(5)F2(3),F2(7)F4(0),F4(2),F4(4),F4(6)F4(1),F4(3),F4(5),F4(7)F8(0),F8(1),F8(2),F8(3),F8(4),F8(5),F8(6),F8(7)第38页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换算法实现的几个关键点算法实现的几个关键点1 1）地址的排序：）地址的排序：

26、按位倒序规则按位倒序规则例如：例如：N=2N=23 3=8=8原地址原地址 原顺序原顺序 新地址新地址 新顺序新顺序 000 000 f(0)f(0)000 000 f(0)f(0)001 001 f(1)f(1)100 100 f(4)f(4)010 010 f(2)f(2)010 010 f(2)f(2)011 011 f(3)f(3)110 110 f(6)f(6)100 100 f(4)f(4)001 001 f(1)f(1)101 101 f(5)f(5)101 101 f(5)f(5)110 110 f(6)f(6)011 011 f(3)f(3)111 111 f(7)f(7)1

27、11 111 f(7)f(7)第39页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换2 2）计算顺序及地址增量）计算顺序及地址增量 地址地址+1+1 地址地址+2 +2 地址地址+4+4 f(0)f(0)F F2 2(0)(0)F F4 4(0)(0)f(4)f(4)F F2 2(4)(4)F F4 4(4)(4)f(2)f(2)F F2 2(2)(2)F F4 4(2)(2)f(6)f(6)F F2 2(6)(6)F F4 4(6)(6)f(1)f(1)F F4 4(1)(1)F F4 4(1)(1)f(5)f(5)F F2 2(5)(5)F F4 4(5)(5)f(3)f(3)F F

28、2 2(3)(3)F F4 4(3)(3)f(7)f(7)F F2 2(7)(7)F F4 4(7)(7)第40页，本讲稿共46页3.4 快速傅立叶变换快速傅立叶变换3 3）复系数的计算：复系数的计算：尤拉公式尤拉公式 W2M=exp-j2/2M =exp-j/M =cos(/M)-jsin(/M)F(u)=1/2(Feven(u)+Fodd(u)W2Mu)F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu)第41页，本讲稿共46页3.5 离散余弦变换离散余弦变换（Discrete Cosine Transform,DCT）在傅立叶级数展开式中，如果被展开在傅立叶级数展开式中，如果

29、被展开的函数是偶函数。据此特点可以推导出另的函数是偶函数。据此特点可以推导出另一种变换一种变换离散余弦变换离散余弦变换。假如已知函数并非偶函数（如一维函假如已知函数并非偶函数（如一维函数数f(x)(x 0)）。我们人为地把它对称地）。我们人为地把它对称地扩展到扩展到x0，构成偶函数（如，构成偶函数（如fs(x)）。）。第42页，本讲稿共46页3.5 离散余弦变换离散余弦变换（Discrete Cosine Transform,DCT）一维离散余弦变换的定义式：一维离散余弦变换的定义式：式中式中C(u)是第是第u个余弦变换系数，个余弦变换系数，u是广义频率变量，是广义频率变量，u=1,2,N-1

30、；f(x)是时域是时域N点序列，点序列，x=0,1,2,N-1。第43页，本讲稿共46页3.5 离散余弦变换离散余弦变换（Discrete Cosine Transform,DCT）一维离散余弦反变换的定义式：一维离散余弦反变换的定义式：第44页，本讲稿共46页3.5 离散余弦变换离散余弦变换（Discrete Cosine Transform,DCT）二维离散余弦变换的定义式：二维离散余弦变换的定义式：(4)其中其中f(x,y)是空间域二维向量之元素；是空间域二维向量之元素；u,v=1,2,N-1,x,y=0,1,2,N-1；C(u,v)是变换系数阵列之元素；式中表示的阵列为是变换系数阵列之元素；式中表示的阵列为NN。第45页，本讲稿共46页3.5 离散余弦变换离散余弦变换（Discrete Cosine Transform,DCT）二维离散余弦反变换的定义式：二维离散余弦反变换的定义式：(5)式中符号意义同正变换一样。式中符号意义同正变换一样。第46页，本讲稿共46页