图像傅里叶变换.ppt

《图像傅里叶变换.ppt》由会员分享，可在线阅读，更多相关《图像傅里叶变换.ppt（75页珍藏版）》请在三一文库上搜索。

1、研究生课程,数字图像处理和分析,Digital Image Processing and Analysis,杜红,E_mail:,第三章 傅里叶变换,傅里叶变换,为什么要在频率域研究图像增强 可以利用频率成分和图像外表之间的对应关系。一 些在空间域表述困难的增强任务，在频率域中变得非 常普通,滤波在频率域更为直观，它可以解释空间域滤波的,某些性质,可以在频率域指定滤波器，做反变换，然后在空间,域使用结果滤波器作为空间域滤波器的指导 一旦通过频率域试验选择了空间滤波，通常实施都在 空间域进行,傅里叶变换定义,一维连续傅里叶变换及反变换,单变量连续函数f(x)的傅里叶变换F(u)定义为,给定F(u

2、),通过傅里叶反变换可以得到f(x), ,f(x)ej2uxdx,F(u) 1,其中，j , ,F(u)ej2uxdu,f(x),傅里叶变换定义,傅里叶变换定义,从欧拉公式 e cos jsin, fxcos(2ux)/M jsin(2ux)/M, fxcos2ux/M jsin2ux/M,一维离散傅里叶变换及反变换,j,M1 x0,1 M,F(u) ,fxe j(2ux)/M, ,M 1 x0 M 1 x0,1 M 1 M,傅里叶变换, ,Fu Ru Iu,2 2,u arctan, ,傅里叶变换的极坐标表示 Fu Fue ju,幅度或频率谱为 1 2 R(u)和I(u)分别是F(u)的实部

3、和虚部 相角或相位谱为 Iu Ru,傅里叶变换,Pu Fu Ru Iu,傅里叶变换的极坐标表示,功率谱为,f(x)的离散表示,F(u)的离散表示,2 2 2,f x f x 0 x x,x 0,1,2,., M 1,F u F u u ,u 0,1,2,., M 1,傅里叶变换,傅里叶变换定义, ,Fu,v Ru,v Iu,v,2 2,u,varctan, ,二维DFT的极坐标表示 Fu,v Fu,ve ju,v,幅度或频率谱为 1 2 R(u,v)和I(u,v)分别是F(u,v)的实部和虚部 相角或相位谱为 Iu,v Ru,v,傅里叶变换,Pu,v Fu,v Ru,v Iu,v,f x, y

4、 1 ,二维DFT的极坐标表示,功率谱为,用(-1)x+y乘以f(x,y),将F(u,v)原点变换到频,率坐标下的(M/2，N/2)，它是MN区域的中心,u=0,1,2,M-1,v=0,1,2,N-1,2 2 2,F u M / 2, v N / 2,F(u,v)的原点变换 x y,傅里叶变换, f x, y,F(0,0)表示,这说明：假设f(x,y)是一幅图像，在原点的傅 里叶变换等于图像的平均灰度级,M 1 N 1 x0 y0,1 MN,F0,0,傅里叶变换,如果f(x,y)是实函数，它的傅里叶变换是,对称的，即,Fu,v Fu,v,傅里叶变换的频率谱是对称的 Fu,v Fu,v,傅里叶变

5、换,傅里叶变换,傅里叶变换,二维傅里叶变换的性质,1. 2. 3. 4. 5. 6. 7. 8. 9.,平移性质 分配律 尺度变换（缩放） 旋转性 周期性和共轭对称性 平均值 可分性 卷积 相关性,傅里叶变换,1.,傅里叶变换对的平移性质,(1) (2), ,公式（1）表明将f(x,y)与一个指数项相乘就相当于 把其变换后的频域中心移动到新的位置 公式（2）表明将F(u,v)与一个指数项相乘就相当于 把其变换后的空域中心移动到新的位置 公式（2）表明对f(x,y)的平移不影响其傅里叶变换 的幅值,fx,yej2u0 x/Mv0y/N Fuu0,vv0 fxx0,yy0Fu,vej2ux0/Mv

6、y0/N,以 表示函数和其傅里叶变换的对应性,傅里叶变换,1,fx,y1,1.,傅里叶变换对的平移性质（续） 当u0=M/2且v0=N/2,带入（1）和（2），得到,e,xy,e,j(xy),j2u0 x/Mv0y/N,FuM/2,vN/2,xy,uv,傅里叶变换,2.,分配律 根据傅里叶变换的定义，可以得到 f1x, y f2x, y f1x, y f2x, y f1x, y f2x, y f1x, yf2x, y 上述公式表明：傅里叶变换对加法满足分配 律，但对乘法则不满足,傅里叶变换,3.,尺度变换（缩放） 给定2个标量a和b，可以证明对傅里叶变换下列 2个公式成立 af x, y aF

7、u,v,Fu /a,v/b,1 ab,fax,by,傅里叶变换,4., ,旋转性 引入极坐标 xrcos,yrsin,ucos,vsin 将f(x,y)和F(u,v)转换为 fr,和F,。将它 们带入傅里叶变换对得到 fr, 0 F, 0,f(x,y)旋转角度0，F(u,v)也将转过相同 的角度 F(u,v)旋转角度0，f(x,y)也将转过相同 的角度,傅里叶变换,5.,周期性和共轭对称性, ,尽管F(u,v)对无穷多个u和v的值重复出现，但只需 根据在任一个周期里的N个值就可以从F(u,v)得到 f(x,y) 只需一个周期里的变换就可将F(u,v)在频域里完全 确定 同样的结论对f(x,y)

8、在空域也成立,Fu,v Fu M,v Fu,v N Fu M,v N fx, y fx M, y fx, y N fx M, y N 上述公式表明,傅里叶变换,Fu,v F u,v,5. ,周期性和共轭对称性 如果f(x,y)是实函数，则它的傅里叶变换具有 共轭对称性 Fu,v Fu,v 其中，F*(u,v)为F(u,v)的复共轭。 复习：当两个复数实部相等,虚部互为相反数时,这两个 复数叫做互为共轭复数.,傅里叶变换,对于一维变换F(u)，周期性是指F(u)的周期长,度为M，对称性是指频谱关于原点对称,周期性和共轭对称性举例,半周期的傅里叶频谱 一幅二维图像的傅里叶频谱,全周期的傅里叶频谱

9、中心化的傅里叶频谱,fx, ye j2vy/ N, x 0, y 0,1 M 1 j2ux/M 1 N1,Fx,v, x 0e,6.,F(x,v)是沿着f(x,y)的一行所进行的傅里叶变 换。当x=0,1,M-1，沿着f(x,y)的所有行计 算傅里叶变换。,分离性 Fu,v ,e M N 1 M 1 j2ux/M M,傅里叶变换,6.,分离性二维傅里叶变换的全过程, ,先通过沿输入图像的每一行计算一维变换 再沿中间结果的每一列计算一维变换 可以改变上述顺序，即先列后行 上述相似的过程也可以计算二维傅里叶反变换,傅里叶变换, fx, y,fx, y, fx, y,7.,平均值 由二维傅里叶变换的

10、定义,而,M 1N1 x0 y0,1 MN,Fu,v,fx, ye j2ux/M vy/ N,M 1N1 x0 y0,1 MN,所以 F0,0,M 1N1 x0 y0,1 MN,傅里叶变换,fx, y F0,0,7.,平均值 所以 上式说明：如果f(x,y)是一幅图像，在 原点的傅里叶变换即等于图像的平均灰度 级,傅里叶变换, fm,nhxm, yn,8.,卷积理论 大小为MN的两个函数f(x,y)和h(x,y)的离散,卷积,1 M1N1 MN m0 n0,fx, yhx, y,卷积定理 fx,yhx,yFu,vHu,v fx,yhx,yFu,vHu,v,傅里叶变换, f m,nhxm, yn

11、,f x,yhx,yFu,vHu,v,9.,相关性理论 大小为MN的两个函数f(x,y)和h(x,y)的相关,f*表示f的复共轭。对于实函数， f*f,相关定理,1 M1N1 * MN m0 n0,性定义为 fx, yhx, y,fx,yhx,yF*u,vHu,v *,傅里叶变换,fx,y fx,yFu,v Ru,v Iu,v,fx,y Fu,vFu,v,自相关理论 2 2 2 2 注：复数和它的复共轭的乘积是复数模的平方,傅里叶变换,卷积和相关性理论总结, ,卷积是空间域过滤和频率域过滤之间的纽带 相关的重要应用在于匹配：确定是否有感兴,趣的物体区域, ,f(x,y)是原始图像 h(x,y)

12、作为感兴趣的物体或区域（模板） 如果匹配，两个函数的相关值会在h找到f,中相应点的位置上达到最大,傅里叶变换,相关性匹配举例,图像f(x,y),模板h(x,y),延拓图像f(x,y) 相关函数图像,延拓图像h(x,y) 通过相关图像最大 值的水平灰度剖面图,傅里叶变换,傅里叶变换, ,傅里叶变换及其反变换 傅里叶变换的性质 快速傅里叶变换(FFT),只考虑一维的情况，根据傅里叶变,换的分离性可知，二维傅里叶变换可 由连续2次一维傅里叶变换得到,快速傅里叶变换(FFT),为什么需要快速傅里叶变换？,快速傅里叶变换(FFT)则只需要Mlog2M次运算, FFT算法与原始变换算法的计算量之比是log

13、2M/M，如 M=1024103,则原始变换算法需要106次计算，而FFT需 要104次计算，FFT与原始变换算法之比是1：100,1 M1 M x0,Fu,fxej2ux/M,u 0,1,2,.,M 1, 对u的M个值中的每一个都需进行M次复数乘法(将f(x) 与ej2ux/M相乘)和M-1次加法，即复数乘法和加法的次 数都正比于M2,FFT算法基本思想 FFT算法基于一个叫做逐次加倍的方法。通 过推导将原始傅里叶转换成两个递推公式,M 1 x0,1 M,Fu,快速傅里叶变换(FFT),1 2,Fevenu FodduW2uk,Fu,1 2,FevenuFodduW2uk,Fu K,f xe

14、 j2ux /M u 0,1,2,.,M 1,FFT算法基本思想,其中：M = 2K Feven(u)、Fodd(u)是K个点的傅里叶值,u 0,1,2,.,M 1,快速傅里叶变换(FFT),1 2,Fevenu FodduW2uk,Fu,1 2,FevenuFodduW2uk,Fu K,FFT公式推导 FFT算法基于一个叫做逐次加倍的方法。为 方便起见用下式表达离散傅立叶变换公式,这里,是一个常数,1 M1 M x0,Fu,fxej2ux/M,快速傅里叶变换(FFT),M 1 x0,fxWM ux,1 M,WM e j2 /M,快速傅里叶变换(FFT) 假设M的形式是 M 2n n为正整数。

15、因此，M可以表示为 M2K 将M=2K带入上式,2K 1 x0,f xW2uxK,1 2K,Fu,1 1 K1 u2x 1 K1 u2x1 2K, 2 1 2 K K W W x f u F, 2 K W x f,快速傅里叶变换(FFT),推导：因为,所以,带入上式有,WM ej2/M,11 K1 ux 1 K1 ux u 2K x0 K x0 ,W22 K ux e j2 (2ux)/2K e j2 (ux)/K WK ux, x 0, x 0,快速傅里叶变换(FFT) 定义两个符号,f2xWK ux,1 K1 K,Fevenu,f2x1WK ux,1 K1 K,F oddu,u0,1,2,

16、.,K1,Fevenu FodduW2K,快速傅里叶变换(FFT) 得到FFT的第一个公式,该公式说明F(u)可以通过奇部和偶部之和 来计算,u,1 2,Fu,WK ue j2 WK u1,W,W2uKe j1 W2uK1,快速傅里叶变换(FFT),推导：,WK u,2,uK 2K, e, j2uK/2K,ej2u/2Kej,WK uK e j2 (uK)/K e j2u/Ke j2,W2uK,1, f2xW2K, x 0 f2x1W2K,f2xWK,f2x1WK uKxW2K uK,f2xWK , x 0, ,f2x1WK ux W2uK ,快速傅里叶变换(FFT), ,K1 x0,K1 x

17、0,uKx,1 K,1 1 2 K,fxW2K uKx,1 2K1 2K x0,FuK,1 K1 uK2x1,K,11 K1 uK2x 2K x0, ,1 1 K1 ux 1 K1 2K x0 K,1 2,FevenuFodduW2uK,快速傅里叶变换(FFT) 得到FFT的第二个公式,该公式说明F(uK)可以通过奇部和偶部之 差来计算,1 2,Fevenu FodduW2uK,Fu K,Fevenu FodduW2K,快速傅里叶变换(FFT),最后得到FFT的二个公式,1 2,Fevenu FodduW2uK,Fu K,u,1 2,Fu,分析这些表达式得到如下一些有趣的特性： 一个M个点的变

18、换，能够通过将原始表达 式分成两个部分来计算 通过计算两个（M/2）个点的变换。得 Feven(u)和 Fodd(u) 奇部与偶部之和得到F(u)的前(M/2)个值 奇部与偶部之差得到F(u)的后(M/2)个 值。且不需要额外的变换计算,快速傅里叶变换(FFT),归纳快速傅立叶变换的思想：,（1）通过计算两个单点的DFT，来计算两个 点的DFT， （2）通过计算两个双点的DFT，来计算四个 点的DFT，以此类推 （3）对于任何N=2m的DFT的计算，通过计算 两个N/2点的DFT，来计算N个点的DFT,快速傅里叶变换(FFT),FFT算法基本思想 FFT算法举例： 设：有函数f(x)，其N =

19、 23 = 8,有： f(0),f(1),f(2),f(3),f(4),f(5),f(6),f(7) 计算： F(0),F(1),F(2),F(3),F(4),F(5),F(6),F(7),快速傅里叶变换(FFT),FFT算法举例,首先分成奇偶两组： 有： f(0), f(2), f(4), f(6) f(1), f(3), f(5), f(7) 为了利用递推特性，再分成两组： 有： f(0), f(4) ， f(2), f(6) f(1), f(5) ， f(3), f(7) ,快速傅里叶变换(FFT),快速傅里叶变换(FFT),FFT算法实现,对输入数据的排序可根据一个简单的位对换,规则进

20、行 如用x表示f(x)的1个自变量值，那么它排序后对应 的值可通过把x表示成二进制数并对换各位得到 例如N=23,f(6)排序后为f(3),因为61102而0112 3,把输入数据进行了重新排序，则输出结果是,正确的次序。反之不把输入数据进行排序，则 输出结果需要重新排序才能得到正确的次序,FFT算法实现 地址的排序：按位倒序规则 例如：N = 23 = 8,原地址 000 001 010 011 100 101 110 111,原顺序 f(0) f(1) f(2) f(3) f(4) f(5) f(6) f(7),新地址 000 100 010 110 001 101 011 111,新顺序 f(0) f(4) f(2) f(6) f(1) f(5) f(3) f(7),快速傅里叶变换(FFT),FFT算法实现几个关键点,2）计算顺序及地址增量：2n,n = 0,1,2,地址+1 f(0) f(4) f(2) f(6) f(1) f(5) f(3) f(7),地址+2 F2(0) F2(4) F2(2) F2(6) F4(1) F2(5) F2(3) F2(7),地址+4 F4(0) F4(4) F4(2) F4(6) F4(1) F4(5) F4(3) F4(7),快速傅里叶变换(FFT),