数字图像处理应用-傅里叶变换

研究生课程数字图像处理DigitalImageProcessing彭宇新北京大学计算机科学技术研究所E_mail:[e-mail]傅里叶变换z傅里叶变换9傅里叶变换及其反变换9傅里叶变换的性质9快速傅里叶变换（FFT）z为什么要在频率域研究图像增强9可以利用频率成分和图像外表之间的对应关系。一些在空间域表述困难的增强任务，在频率域中变得非常普通9滤波在频率域更为直观，它可以解释空间域滤波的某些性质9可以在频率域指定滤波器，做反变换，然后在空间域使用结果滤波器作为空间域滤波器的指导9一旦通过频率域试验选择了空间滤波，通常实施都在空间域进行傅里叶变换z一维连续傅里叶变换及反变换9单变量连续函数f(x)的傅里叶变换F(u)定义为其中，9给定F(u),通过傅里叶反变换可以得到f(x)∫∞∞−−=dxexfuFuxjπ2)()(1−=j∫∞∞−=dueuFxfuxjπ2)()(傅里叶变换z二维连续傅里叶变换及反变换9二维连续函数f(x,y)的傅里叶变换F(u,v)定义为9给定F(u,v),通过傅里叶反变换可以得到f(x,y)()dydxeyxfvuFvyuxj∫∫∞∞−∞∞−+−=π2),(),(()dvduevuFyxfvyuxj∫∫∞∞−∞∞−+=π2),(),(傅里叶变换z一维离散傅里叶变换(DFT)及反变换9单变量离散函数f(x)(x=0,1,2,..,M-1)的傅里叶变换F(u)定义为u=0,1,2,…,M-19给定F(u),通过傅里叶反变换可以得到f(x)x=0,1,2,…,M-1()∑−=−=10/21)(MxMuxjexfMuFπ()∑−==10/2)(MuMuxjeuFxfπ傅里叶变换z一维离散傅里叶变换及反变换9从欧拉公式()()∑−=−+−=10/)2sin(/)2cos(1MxMuxjMuxxfMππθθθsincosjej+=()∑−=−=10/)2(1)(MxMuxjexfMuFπ()()∑−=−=10/2sin/2cos1MxMuxjMuxxfMππ傅里叶变换z傅里叶变换的极坐标表示9幅度或频率谱为R(u)和I(u)分别是F(u)的实部和虚部9相角或相位谱为()()()ujeuFuFφ−=()()()[]2122uIuRuF+=()()()⎥⎦⎤⎢⎣⎡=uRuIuarctanφ傅里叶变换z傅里叶变换的极坐标表示9功率谱为zf(x)的离散表示zF(u)的离散表示()()()()222uIuRuFuP+==()()xxxfxfΔ+≅01,...,2,1,0−=Mx()()uuFuFΔ≅1,...,2,1,0−=Mu傅里叶变换z二维离散傅里叶变换及反变换9图像尺寸为M×N的函数f(x,y)的DFT为u=0,1,2,…,M-1,v=0,1,2,…,N-19给出F(u,v),可通过反DFT得到f(x,y),x=0,1,2,…,M-1,y=0,1,2,…,N-1注：u和v是频率变量，x和y是空间或图像变量()()∑∑−=−=+−=1010//2,1),(MxNyNvyMuxjeyxfMNvuFπ()()∑∑−=−=+=1010//2,),(MuNvNvyMuxjevuFyxfπ傅里叶变换z二维DFT的极坐标表示9幅度或频率谱为R(u,v)和I(u,v)分别是F(u,v)的实部和虚部9相角或相位谱为()()()vujevuFvuF,,,φ−=()()()[]2122,,,vuIvuRvuF+=()()()⎥⎦⎤⎢⎣⎡=vuRvuIvu,,arctan,φ傅里叶变换z二维DFT的极坐标表示9功率谱为zF(u,v)的原点变换9用(-1)x+y乘以f(x,y),将F(u,v)原点变换到频率坐标下的(M/2，N/2)，它是M×N区域的中心9u=0,1,2,…,M-1,v=0,1,2,…,N-1()()()()222,,,,vuIvuRvuFvuP+==()()[]()2/,2/1,NvMuFyxfyx−−=−ℑ+傅里叶变换zF(0,0)表示这说明：假设f(x,y)是一幅图像，在原点的傅里叶变换等于图像的平均灰度级()()∑∑−=−==1010,10,0MxNyyxfMNF傅里叶变换z如果f(x,y)是实函数，它的傅里叶变换是对称的，即z傅里叶变换的频率谱是对称的()()vuFvuF−−=,,()()vuFvuF−−=,,傅里叶变换z傅里叶变换9傅里叶变换及其反变换9傅里叶变换的性质9快速傅里叶变换（FFT）傅里叶变换z二维傅里叶变换的性质1.平移性质2.分配律3.尺度变换（缩放）4.旋转性5.周期性和共轭对称性6.平均值7.可分性8.卷积9.相关性傅里叶变换1.傅里叶变换对的平移性质以表示函数和其傅里叶变换的对应性(1)(2)9公式（1）表明将f(x,y)与一个指数项相乘就相当于把其变换后的频域中心移动到新的位置9公式（2）表明将F(u,v)与一个指数项相乘就相当于把其变换后的空域中心移动到新的位置9公式（2）表明对f(x,y)的平移不影响其傅里叶变换的幅值()()()00//2,,00vvuuFeyxfNyvMxuj−−⇔+π()()()NvyMuxjevuFyyxxf//20000,,+−⇔−−π⇔傅里叶变换1.傅里叶变换对的平移性质（续）当u0=M/2且v0=N/2,带入（1）和（2），得到()()yxyxjNyvMxujee+++−==1)(//200ππ()()()2/,2/1,NvMuFyxfyx−−⇔−+()()()vuvuFNyMxf+−⇔−−1,2/,2/傅里叶变换2.分配律根据傅里叶变换的定义，可以得到上述公式表明：傅里叶变换对加法满足分配律，但对乘法则不满足()()[]()[]()[]yxfyxfyxfyxf,,,,2121ℑ+ℑ=+ℑ()()[]()[]()[]yxfyxfyxfyxf,,,,2121ℑ•ℑ≠•ℑ傅里叶变换3.尺度变换（缩放）给定2个标量a和b，可以证明对傅里叶变换下列2个公式成立()()vuaFyxaf,,⇔()()bvauFabbyaxf/,/1,⇔傅里叶变换4.旋转性引入极坐标将f(x,y)和F(u,v)转换为和。将它们带入傅里叶变换对得到9f(x,y)旋转角度，F(u,v)也将转过相同的角度9F(u,v)旋转角度，f(x,y)也将转过相同的角度()()00,,θϕωθθ+⇔+Frfϕωϕωθθsin,cos,sin,cos====vuryrx0θ()θ,rf()ϕω,F0θ傅里叶变换5.周期性和共轭对称性上述公式表明9尽管F(u,v)对无穷多个u和v的值重复出现，但只需根据在任一个周期里的N个值就可以从F(u,v)得到f(x,y)9只需一个周期里的变换就可将F(u,v)在频域里完全确定9同样的结论对f(x,y)在空域也成立()()()()NvMuFNvuFvMuFvuF++=+=+=,,,,()()()()NyMxfNyxfyMxfyxf++=+=+=,,,,傅里叶变换5.周期性和共轭对称性如果f(x,y)是实函数，则它的傅里叶变换具有共轭对称性其中，F*(u,v)为F(u,v)的复共轭。z复习：当两个复数实部相等,虚部互为相反数时,这两个复数叫做互为共轭复数.()()vuFvuF−−=∗,,()()vuFvuF−−=,,傅里叶变换z对于一维变换F(u)，周期性是指F(u)的周期长度为M，对称性是指频谱关于原点对称周期性和共轭对称性举例半周期的傅里叶频谱全周期的傅里叶频谱一幅二维图像的傅里叶频谱中心化的傅里叶频谱6.分离性F(x,v)是沿着f(x,y)的一行所进行的傅里叶变换。当x=0,1,…,M-1，沿着f(x,y)的所有行计算傅里叶变换。()()∑∑−=−−=−=10/210/2,11,NyNvyjMxMuxjeyxfNeMvuFππ()vxFeMMxMuxj,110/2∑−=−=π傅里叶变换6.分离性——二维傅里叶变换的全过程9先通过沿输入图像的每一行计算一维变换9再沿中间结果的每一列计算一维变换9可以改变上述顺序，即先列后行9上述相似的过程也可以计算二维傅里叶反变换傅里叶变换7.平均值由二维傅里叶变换的定义所以而()()()∑∑−=−=+−=1010//2,1,MxNyNvyMuxjeyxfMNvuFπ()()∑∑−=−==1010,10,0MxNyyxfMNF()()∑∑−=−=−=1010,1,MxNyyxfMNyxf傅里叶变换7.平均值所以上式说明：如果f(x,y)是一幅图像，在原点的傅里叶变换即等于图像的平均灰度级()()0,0,Fyxf=−傅里叶变换8.卷积理论大小为M×N的两个函数f(x,y)和h(x,y)的离散卷积卷积定理()()()()∑∑−=−=−−=∗1010,,1,,MmNnnymxhnmfMNyxhyxf()()()()vuHvuFyxhyxf,,,,⇔∗()()()()vuHvuFyxhyxf,,,,∗⇔傅里叶变换9.相关性理论大小为M×N的两个函数f(x,y)和h(x,y)的相关性定义为f*表示f的复共轭。对于实函数，f*＝f相关定理()()()()∑∑−=−=++=1010*,,1,,MmNnnymxhnmfMNyxhyxfo()()()()vuHvuFyxhyxf,,,,*⇔o()()()()vuHvuFyxhyxf,,,,*o⇔傅里叶变换z自相关理论注：复数和它的复共轭的乘积是复数模的平方()()()()()222,,,,,vuIvuRvuFyxfyxf+=⇔o()()()vuFvuFyxf,,,2o⇔傅里叶变换z卷积和相关性理论总结9卷积是空间域过滤和频率域过滤之间的纽带9相关的重要应用在于匹配：确定是否有感兴趣的物体区域¾f(x,y)是原始图像¾h(x,y)作为感兴趣的物体或区域（模板）¾如果匹配，两个函数的相关值会在h找到f中相应点的位置上达到最大傅里叶变换相关性匹配举例图像f(x,y)模板h(x,y)延拓图像f(x,y)延拓图像h(x,y)相关函数图像通过相关图像最大值的水平灰度剖面图傅里叶变换z傅里叶变换9傅里叶变换及其反变换9傅里叶变换的性质9快速傅里叶变换(FFT)¾只考虑一维的情况，根据傅里叶变换的分离性可知，二维傅里叶变换可由连续2次一维傅里叶变换得到快速傅里叶变换(FFT)z为什么需要快速傅里叶变换？9对u的M个值中的每一个都需进行M次复数乘法(将f(x)与相乘)和M-1次加法，即复数乘法和加法的次数都正比于M29快速傅里叶变换(FFT)则只需要Mlog2M次运算9FFT算法与原始变换算法的计算量之比是log2M/M，如M=1024≈103,则原始变换算法需要106次计算，而FFT需要104次计算，FFT与原始变换算法之比是1：100()()∑−=−=10/21MxMuxjexfMuFπ1,...,2,1,0−=MuMuxje/2π−zFFT算法基本思想FFT算法基于一个叫做逐次加倍的方法。通过推导将原始傅里叶转换成两个递推公式()()∑−=−=10/21MxMuxjexfMuFπ快速傅里叶变换(FFT)()()()[]ukoddevenWuFuFuF221+=()()()[]ukoddevenWuFuFKuF221−=+1,...,2,1,0−=MuzFFT算法基本思想其中：M=2KFeven(u)、Fodd(u)是K个点的傅里叶值1,...,2,1,0−=Mu快速傅里叶变换(FFT)()()()[]ukoddevenWuFuFuF221+=()()()[]ukoddevenWuFuFKuF221−=+zFFT公式推导FFT算法基于一个叫做逐次加倍的方法。为方便起见用下式表达离散傅立叶变换公式这里是一个常数()()∑−=−=10/21MxMuxjexfMuFπ快速傅里叶变换(FFT)()∑−==101MxuxMWxfMMjMeW/2π−=快速傅里叶变换(FFT)假设M的形式是n为正整数。因此，M可以表示为将M=2K带入上式nM2=KM2=()()∑−==120221KxuxKWxfKuF()()()()⎥⎦⎤⎢⎣⎡++=∑∑−=−=+1010122221212121K