傅立叶变换

傅里叶变换傅里叶变换傅里叶变换及其反变换傅里叶变换的性质快速傅里叶变换（FFT）为什么要在频率域研究图像增强可以利用频率成分和图像外表之间的对应关系。一些在空间域表述困难的增强任务，在频率域中变得非常普通滤波在频率域更为直观，它可以解释空间域滤波的某些性质可以在频率域指定滤波器，做反变换，然后在空间域使用结果滤波器作为空间域滤波器的指导一旦通过频率域试验选择了空间滤波，通常实施都在空间域进行傅里叶变换一维连续傅里叶变换及反变换单变量连续函数f(x)的傅里叶变换F(u)定义为其中，给定F(u),通过傅里叶反变换可以得到f(x)dxexfuFuxj2)()(1jdueuFxfuxj2)()(傅里叶变换二维连续傅里叶变换及反变换二维连续函数f(x,y)的傅里叶变换F(u,v)定义为给定F(u,v),通过傅里叶反变换可以得到f(x,y)dydxeyxfvuFvyuxj2),(),(dvduevuFyxfvyuxj2),(),(傅里叶变换一维离散傅里叶变换(DFT)及反变换单变量离散函数f(x)(x=0,1,2,..,M-1)的傅里叶变换F(u)定义为u=0,1,2,…,M-1给定F(u),通过傅里叶反变换可以得到f(x)x=0,1,2,…,M-110/21)(MxMuxjexfMuF10/2)(MuMuxjeuFxf傅里叶变换一维离散傅里叶变换及反变换从欧拉公式10/)2sin(/)2cos(1MxMuxjMuxxfMsincosjej10/)2(1)(MxMuxjexfMuF10/2sin/2cos1MxMuxjMuxxfM傅里叶变换傅里叶变换的极坐标表示幅度或频率谱为R(u)和I(u)分别是F(u)的实部和虚部相角或相位谱为ujeuFuF2122uIuRuFuRuIuarctan傅里叶变换傅里叶变换的极坐标表示功率谱为f(x)的离散表示F(u)的离散表示222uIuRuFuPxxxfxf01,...,2,1,0MxuuFuF1,...,2,1,0Mu傅里叶变换二维离散傅里叶变换及反变换图像尺寸为M×N的函数f(x,y)的DFT为u=0,1,2,…,M-1,v=0,1,2,…,N-1给出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傅里叶变换二维DFT的极坐标表示幅度或频率谱为R(u,v)和I(u,v)分别是F(u,v)的实部和虚部相角或相位谱为vujevuFvuF,,,2122,,,vuIvuRvuFvuRvuIvu,,arctan,傅里叶变换二维DFT的极坐标表示功率谱为F(u,v)的原点变换用(-1)x+y乘以f(x,y),将F(u,v)原点变换到频率坐标下的(M/2，N/2)，它是M×N区域的中心u=0,1,2,…,M-1,v=0,1,2,…,N-1222,,,,vuIvuRvuFvuP2/,2/1,NvMuFyxfyx傅里叶变换F(0,0)表示这说明：假设f(x,y)是一幅图像，在原点的傅里叶变换等于图像的平均灰度级1010,10,0MxNyyxfMNF傅里叶变换如果f(x,y)是实函数，它的傅里叶变换是对称的，即傅里叶变换的频率谱是对称的vuFvuF,,vuFvuF,,傅里叶变换傅里叶变换傅里叶变换及其反变换傅里叶变换的性质快速傅里叶变换（FFT）傅里叶变换二维傅里叶变换的性质1.平移性质2.分配律3.尺度变换（缩放）4.旋转性5.周期性和共轭对称性6.平均值7.可分性8.卷积9.相关性傅里叶变换1.傅里叶变换对的平移性质以表示函数和其傅里叶变换的对应性(1)(2)公式（1）表明将f(x,y)与一个指数项相乘就相当于把其变换后的频域中心移动到新的位置公式（2）表明将F(u,v)与一个指数项相乘就相当于把其变换后的空域中心移动到新的位置公式（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)转换为和。将它们带入傅里叶变换对得到f(x,y)旋转角度，F(u,v)也将转过相同的角度F(u,v)旋转角度，f(x,y)也将转过相同的角度00,,Frfsin,cos,sin,cosvuryrx0,rf,F0傅里叶变换5.周期性和共轭对称性上述公式表明尽管F(u,v)对无穷多个u和v的值重复出现，但只需根据在任一个周期里的N个值就可以从F(u,v)得到f(x,y)只需一个周期里的变换就可将F(u,v)在频域里完全确定同样的结论对f(x,y)在空域也成立NvMuFNvuFvMuFvuF,,,,NyMxfNyxfyMxfyxf,,,,傅里叶变换5.周期性和共轭对称性如果f(x,y)是实函数，则它的傅里叶变换具有共轭对称性其中，F*(u,v)为F(u,v)的复共轭。复习：当两个复数实部相等,虚部互为相反数时,这两个复数叫做互为共轭复数.vuFvuF,,vuFvuF,,傅里叶变换对于一维变换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.分离性——二维傅里叶变换的全过程先通过沿输入图像的每一行计算一维变换再沿中间结果的每一列计算一维变换可以改变上述顺序，即先列后行上述相似的过程也可以计算二维傅里叶反变换傅里叶变换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,,MmNnnymxhnmfMNyxhyxfvuHvuFyxhyxf,,,,*vuHvuFyxhyxf,,,,*傅里叶变换自相关理论注：复数和它的复共轭的乘积是复数模的平方222,,,,,vuIvuRvuFyxfyxfvuFvuFyxf,,,2傅里叶变换卷积和相关性理论总结卷积是空间域过滤和频率域过滤之间的纽带相关的重要应用在于匹配：确定是否有感兴趣的物体区域f(x,y)是原始图像h(x,y)作为感兴趣的物体或区域（模板）如果匹配，两个函数的相关值会在h找到f中相应点的位置上达到最大傅里叶变换相关性匹配举例图像f(x,y)模板h(x,y)延拓图像f(x,y)延拓图像h(x,y)相关函数图像通过相关图像最大值的水平灰度剖面图傅里叶变换傅里叶变换傅里叶变换及其反变换傅里叶变换的性质快速傅里叶变换(FFT)只考虑一维的情况，根据傅里叶变换的分离性可知，二维傅里叶变换可由连续2次一维傅里叶变换得到快速傅里叶变换(FFT)为什么需要快速傅里叶变换？对u的M个值中的每一个都需进行M次复数乘法(将f(x)与相乘)和M-1次加法，即复数乘法和加法的次数都正比于M2快速傅里叶变换(FFT)则只需要Mlog2M次运算FFT算法与原始变换算法的计算量之比是log2M/M，如M=1024≈103,则原始变换算法需要106次计算，而FFT需要104次计算，FFT与原始变换算法之比是1：10010/21MxMuxjexfMuF1,...,2,1,0MuMuxje/2FFT算法基本思想FFT算法基于一个叫做逐次加倍的方法。通过推导将原始傅里叶转换成两个递推公式10/21MxMuxjexfMuF快速傅里叶变换(FFT)ukoddevenWuFuFuF221ukoddevenWuFuFKuF2211,...,2,1,0MuFFT算法基本思想其中：M=2KFeven(u)、Fodd(u)是K个点的傅里叶值1,...,2,1,0Mu快速傅里叶变换(FFT)ukoddevenWuFuFuF221ukoddevenWuFuFKuF221FFT公式推导FFT算法基于一个叫做逐次加倍的方法。为方便起见用下式表达离散傅立叶变换公式这里是一个常数10/21MxMuxjexfMuF快速傅里叶变换(FFT)101MxuxMWxfMMjMeW/2快速傅里叶变换(FFT)假设M的形式是n为正整数。因此，M可以表示为将M=2K带入上式nM2KM2120221KxuxKWxfKuF1010122221212121KxKxxuKxuKWxfKWxfK快速傅里叶变换(FFT)推导：因为所以带入上式有MjMeW/21010212121