图像傅里叶变换经典课件.ppt

图图像傅里叶像傅里叶变变换换第三章第三章 傅里叶变换傅里叶变换傅里叶变换傅里叶变换 为什么要在频率域研究图像增强为什么要在频率域研究图像增强 可以利用频率成分和图像外表之间的对应关系。一可以利用频率成分和图像外表之间的对应关系。一些在空间域表述困难的增强任务，在频率域中变得非些在空间域表述困难的增强任务，在频率域中变得非常普通常普通 滤波在频率域更为直观，它可以解释空间域滤波的滤波在频率域更为直观，它可以解释空间域滤波的某些性质某些性质 可以在频率域指定滤波器，做反变换，然后在空间可以在频率域指定滤波器，做反变换，然后在空间域使用结果滤波器作为空间域滤波器的指导域使用结果滤波器作为空间域滤波器的指导 一旦通过频率域试验选择了空间滤波，通常实施都在一旦通过频率域试验选择了空间滤波，通常实施都在空间域进行空间域进行傅里叶变换傅里叶变换定义定义 一维连续傅里叶变换及反变换一维连续傅里叶变换及反变换 单变量连续函数单变量连续函数f(x)的傅里叶变换的傅里叶变换F(u)定义定义为为 给定给定F(u),通过傅里叶反变换可以得到通过傅里叶反变换可以得到f(x)f(x)e j2 uxdxF(u)1其中，其中，j F(u)ej2 uxduf(x)傅里叶变换傅里叶变换定义定义傅里叶变换傅里叶变换定义定义从欧拉公式从欧拉公式 e cos jsin f x cos(2 ux)/M jsin(2 ux)/M f x cos2 ux/M jsin2 ux/M 一维离散傅里叶变换及反变换一维离散傅里叶变换及反变换 j M 1x 01MF(u)f x e j(2 ux)/M M 1x 0M 1x 01M1M傅里叶变换傅里叶变换 F u R u I u 2 2 u arctan 傅里叶变换的极坐标表示傅里叶变换的极坐标表示F u F u e j u 幅度或频率谱为幅度或频率谱为12R(u)和和I(u)分别是分别是F(u)的实部和虚部的实部和虚部相角或相位谱为相角或相位谱为 I u R u 傅里叶变换傅里叶变换P u F u R u I u 傅里叶变换的极坐标表示傅里叶变换的极坐标表示 功率谱为功率谱为 f(x)的离散表示的离散表示 F(u)的离散表示的离散表示2 2 2f x f x 0 x x x 0,1,2,.,M 1F u F u u u 0,1,2,.,M 1傅里叶变换傅里叶变换傅里叶变换傅里叶变换定义定义 F u,v R u,v I u,v 2 2 u,v arctan 二维二维DFT的极坐标表示的极坐标表示F u,v F u,v e j u,v 幅度或频率谱为幅度或频率谱为12R(u,v)和和I(u,v)分别是分别是F(u,v)的实部和虚部的实部和虚部相角或相位谱为相角或相位谱为 I u,v R u,v 傅里叶变换傅里叶变换P u,v F u,v R u,v I u,v f x,y 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-12 2 2F u M /2,v N /2 F(u,v)的原点变换的原点变换x y傅里叶变换傅里叶变换 f x,y F(0,0)表示表示这说明：假设这说明：假设f(x,y)是一幅图像，在原点的傅是一幅图像，在原点的傅里叶变换等于图像的平均灰度级里叶变换等于图像的平均灰度级M 1 N 1x 0 y 01MNF 0,0 傅里叶变换傅里叶变换如果f(x,y)是实函数，它的傅里叶变换是对称的，即Fu,v Fu,v傅里叶变换的频率谱是对称的Fu,v Fu,v傅里叶变换傅里叶变换傅里叶变换 二维傅里叶变换的性质二维傅里叶变换的性质1.2.3.4.5.6.7.8.9.平移性质平移性质分配律分配律尺度变换（缩放）尺度变换（缩放）旋转性旋转性周期性和共轭对称性周期性和共轭对称性平均值平均值可分性可分性卷积卷积相关性相关性傅里叶变换傅里叶变换1.傅里叶变换对的平移性质傅里叶变换对的平移性质(1)(2)公式（公式（1）表明将）表明将f(x,y)与一个指数项相乘就相当于与一个指数项相乘就相当于把其变换后的频域中心移动到新的位置把其变换后的频域中心移动到新的位置公式（公式（2）表明将）表明将F(u,v)与一个指数项相乘就相当于与一个指数项相乘就相当于把其变换后的空域中心移动到新的位置把其变换后的空域中心移动到新的位置公式（公式（2）表明对）表明对f(x,y)的平移不影响其傅里叶变换的平移不影响其傅里叶变换的幅值的幅值f x,y ej2 u0 x/M v0y/N F u u0,v v0 f x x0,y y0 F u,v e j2 ux0/M vy0/N 以以 表示函数和其傅里叶变换的对应性表示函数和其傅里叶变换的对应性傅里叶变换傅里叶变换 1 f x,y 1 1.傅里叶变换对的平移性质（续）傅里叶变换对的平移性质（续）当当u0=M/2且且v0=N/2,带入（带入（1）和（）和（2），得到），得到ex y ej(x y)j2 u0 x/M v0y/N F u M/2,v N/2 x yu v傅里叶变换傅里叶变换2.分配律分配律根据傅里叶变换的定义，可以得到根据傅里叶变换的定义，可以得到 f1 x,y f2 x,y f1 x,y f2 x,y f1 x,y f2 x,y f1 x,y f2 x,y 上述公式表明：傅里叶变换对加法满足分配上述公式表明：傅里叶变换对加法满足分配律，但对乘法则不满足律，但对乘法则不满足傅里叶变换傅里叶变换3.尺度变换（缩放）尺度变换（缩放）给定给定2个标量个标量a和和b，可以证明对傅里叶变换下列，可以证明对傅里叶变换下列2个公式成立个公式成立af x,y aF u,v F u/a,v/b 1abf ax,by 傅里叶变换傅里叶变换4.旋转性旋转性引入极坐标引入极坐标 x rcos,y rsin,u cos,v sin 将将f(x,y)和和F(u,v)转换为转换为 f r,和和F ,。将它。将它们带入傅里叶变换对得到们带入傅里叶变换对得到f r,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)在空域也成立在空域也成立F u,v F u M,v F u,v N F u M,v N f x,y f x M,y f x,y N f x M,y N 上述公式表明上述公式表明傅里叶变换傅里叶变换F u,v F u,v 5.周期性和共轭对称性周期性和共轭对称性如果如果f(x,y)是实函数，则它的傅里叶变换具有是实函数，则它的傅里叶变换具有共轭对称性共轭对称性 F u,v F u,v 其中，其中，F*(u,v)为为F(u,v)的复共轭。的复共轭。复习：当两个复数实部相等复习：当两个复数实部相等,虚部互为相反数时虚部互为相反数时,这两个这两个复数叫做互为共轭复数复数叫做互为共轭复数.傅里叶变换傅里叶变换对于一维变换F(u)，周期性是指F(u)的周期长度为M，对称性是指频谱关于原点对称周期性和共轭对称性举例周期性和共轭对称性举例半周期的傅里叶频谱一幅二维图像的傅里叶频谱全周期的傅里叶频谱中心化的傅里叶频谱fx,ye j2vy/N x 0 y 01 M 1 j2ux/M 1 N1Fx,v x 0e6.F(x,v)是沿着f(x,y)的一行所进行的傅里叶变换。当x=0,1,M-1，沿着f(x,y)的所有行计算傅里叶变换。分离性Fu,veM N1 M 1 j2ux/MM傅里叶变换6.分离性二维傅里叶变换的全过程先通过沿输入图像的每一行计算一维变换再沿中间结果的每一列计算一维变换可以改变上述顺序，即先列后行上述相似的过程也可以计算二维傅里叶反变换傅里叶变换 fx,yfx,y fx,y7.平均值由二维傅里叶变换的定义而M 1N1x0 y01MNFu,vfx,ye j2ux/M vy/NM 1N1x0 y01MN所以 F0,0M 1N1x0 y01MN傅里叶变换f x,y F 0,0 7.平均值平均值所以所以 上式说明：如果上式说明：如果f(x,y)是一幅图像，在是一幅图像，在原点的傅里叶变换即等于图像的平均灰度原点的傅里叶变换即等于图像的平均灰度级级傅里叶变换傅里叶变换 f m,n h x m,y n 8.卷积理论卷积理论大小为大小为MN的两个函数的两个函数f(x,y)和和h(x,y)的离散的离散卷积卷积1 M 1N 1MN m 0 n 0f x,y h x,y 卷积定理卷积定理f x,y h x,y F u,v H u,v f x,y h x,y F u,v H u,v 傅里叶变换傅里叶变换 f m,n h x m,y n f x,y h x,y F u,v H u,v 9.相关性理论相关性理论大小为大小为MN的两个函数的两个函数f(x,y)和和h(x,y)的相关的相关f*表示表示f的复共轭。对于实函数，的复共轭。对于实函数，f*f相关定理相关定理1 M 1N 1 *MN m 0 n 0性定义为性定义为f x,y h x,y f x,y h x,y F*u,v H u,v*傅里叶变换傅里叶变换f x,y f x,y F u,v R u,v I u,v f x,y F u,v F u,v 自相关理论自相关理论2 2 22注：复数和它的复共轭的乘积是复数模的平方注：复数和它的复共轭的乘积是复数模的平方傅里叶变换傅里叶变换 卷积和相关性理论总结卷积和相关性理论总结 卷积是空间域过滤和频率域过滤之间的纽带卷积是空间域过滤和频率域过滤之间的纽带相关的重要应用在于匹配：确定是否有感兴相关的重要应用在于匹配：确定是否有感兴趣的物体区域趣的物体区域 f(x,y)是原始图像是原始图像h(x,y)作为感兴趣的物体或区域（模板）作为感兴趣的物体或区域（模板）如果匹配，两个函数的相关值会在如果匹配，两个函数的相关值会在h找到找到f中相应点的位置上达到最大中相应点的位置上达到最大傅里叶变换傅里叶变换相关性匹配举例图像f(x,y)模板h(x,y)延拓图像f(x,y)相关函数图像延拓图像h(x,y)通过相关图像最大值的水平灰度剖面图傅里叶变换傅里叶变换傅里叶变换及其反变换傅里叶变换的性质快速傅里叶变换(FFT)只考虑一维的情况，根据傅里叶变换的分离性可知，二维傅里叶变换可由连续2次一维傅里叶变换得到快速傅里叶变换(FFT)为什么需要快速傅里叶变换？快速傅里叶变换(FFT)则只需要Mlog2M次运算 FFT算法与原始变换算法的计算量之比是log2M/M，如M=1024103,则原始变换算法需要106次计算，而FFT需要104次计算，FFT与原始变换算法之比是1：1001 M1M x0Fufxej2ux/Mu 0,1,2,.,M 1 对u的M个值中的每一个都需进行M次复数乘法(将f(x)与ej2ux/M相乘)和M-1次加法，即复数乘法和加法的次数都正比于M2 FFT算法基本思想算法基本思想FFT算法基于一个叫做逐次加倍的方法。通算法基于一个叫做逐次加倍的方法。通过推导将原始傅里叶转换成两个递推公式过推导将原始傅里叶转换成两个递推公式M 1x 01MF u 快速傅里叶变换快速傅里叶变换(FFT)12 Feven u Fodd u W2ukF u 12 Feven u Fodd u W2ukF u K f x e j2 ux/M u 0,1,2,.,M 1 FFT算法基本思想算法基本思想其中：其中：M =2KFeven(u)、Fodd(u)是是K个点的傅里叶值个点的傅里叶值u 0,1,2,.,M 1快速傅里叶变换快速傅里叶变换(FFT)12 Feven u Fodd u W2ukF u 12 Feven u Fodd u W2ukF u K FFT公式推导公式推导FFT算法基于一个叫做逐次加倍的方法。为算法基于一个叫做逐次加倍的方法。为方便起见用下式表达离散傅立叶变换公式方便起见用下式表达离散傅立叶变换公式这里这里是一个常数是一个常数1 M 1M x 0F u f x e j2 ux/M快速傅里叶变换快速傅里叶变换(FFT)M 1x 0f x WM ux1MWM e j2 /M 快速傅里叶变换快速傅里叶变换(FFT)假设假设M的形式是的形式是M 2nn为正整数。因此，为正整数。因此，M可以表示为可以表示为M 2K将将M=2K带入上式带入上式2K 1x 0f x W2uxK12KF u 1 1 K 1 u 2x 1 K 1 u 2x 1 2 K 2 1 2 K K W W x f u F 2 K W x f快速傅里叶变换(FFT)推导：因为所以带入上式有WM ej2/M11 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 ux1 K1KFevenuf2x1WK ux1 K1KF odduu0,1,2,.,K1Fevenu FodduW2K快速傅里叶变换(FFT)得到FFT的第一个公式该公式说明F(u)可以通过奇部和偶部之和来计算u12FuWK ue j2 WK u1WW2uKe j1 W2uK1快速傅里叶变换(FFT)推导：WK u2uK2K e j2uK/2Kej2u/2KejWK uK e j2(uK)/K e j2u/Ke j2W2uK1 f2xW2K x 0 f2x1W2Kf2xWKf2x1WK uKxW2K uKf2xWK x 0 f2x1WK ux W2uK 快速傅里叶变换(FFT)K1x0K1x0uKx1K1 12 KfxW2K uKx1 2K12K x0FuK1 K1 uK2x1K11 K1 uK2x2K x01 1 K1 ux 1 K12K x0 K12FevenuFodduW2uK快速傅里叶变换(FFT)得到FFT的第二个公式该公式说明F(uK)可以通过奇部和偶部之差来计算12Fevenu FodduW2uKFu KFevenu FodduW2K快速傅里叶变换(FFT)最后得到FFT的二个公式12Fevenu FodduW2uKFu Ku12Fu分析这些表达式得到如下一些有趣的特性：一个M个点的变换，能够通过将原始表达式分成两个部分来计算 通过计算两个（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 =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算法实现对输入数据的排序可根据一个简单的位对换规则进行如用x表示f(x)的1个自变量值，那么它排序后对应的值可通过把x表示成二进制数并对换各位得到 例如N=23,f(6)排序后为f(3),因为61102而01123把输入数据进行了重新排序，则输出结果是正确的次序。反之不把输入数据进行排序，则输出结果需要重新排序才能得到正确的次序FFT算法实现地址的排序：按位倒序规则例如：N =23=8原地址000001010011100101110111原顺序f(0)f(1)f(2)f(3)f(4)f(5)f(6)f(7)新地址000100010110001101011111新顺序f(0)f(4)f(2)f(6)f(1)f(5)f(3)f(7)快速傅里叶变换(FFT)FFT算法实现几个关键点2）计算顺序及地址增量：2nn =0,1,2地址+1f(0)f(4)f(2)f(6)f(1)f(5)f(3)f(7)地址+2F2(0)F2(4)F2(2)F2(6)F4(1)F2(5)F2(3)F2(7)地址+4F4(0)F4(4)F4(2)F4(6)F4(1)F4(5)F4(3)F4(7)快速傅里叶变换(FFT)