数字图像处理傅立叶变换

第三章图像变换3.3二维离散傅立叶变换(DiscreteFourierTransform：DFT)性质二维离散傅立叶变换特性•可分离性•平移性•周期性与共轭对称•旋转特性•线性与比例性•均值性•卷积与相关第三章图像变换3.3.1可分离性•二维离散傅立叶变换DFT可分离性的基本思想是：二维DFT可分离为两次一维DFT。•应用：二维快速傅立叶算法FFT，是通过计算两次一维FFT实现的。第三章图像变换3.3.1可分离性•可分离性的定义1M0x1N0yMux2jexpNvy2jexpy,xfMN1v,uFu=0,1,2,…M-1；v=0,1,2,...N-11M0u1N0vMux2jexpNvy2jexpv,uFy,xfx=0,1,2,…M-1；y=0,1,2,...N-1第三章图像变换3.3.1可分离性•可分离性成立的推导–先对行（y变量）做变换：102exp),(1,NyNvyjyxfNvxF–然后对列（x变量）进行变换：1M0xMux2jexp)v,x(FM1v,uF第三章图像变换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第三章图像变换•傅立叶变换对有如下平移性质：f(x,y)exp[j2(u0x/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)要乘上一个正的指数项：exp[j2(u0x/M+v0y/N)]；在空域中图像原点平移到(x0,y0)时，其对应的F(u,v)要乘上一个负的指数项：exp[-j2(ux0/M+vy0/N)]。3.3.2平移性第三章图像变换•对于M=N，则类似地有：f(x,y)exp[j2(u0x+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)要乘上一个正的指数项exp[j2(u0x+v0y)/N]；在空域中图像原点平移到(x0,y0)时，其对应的F(u,v)要乘上一个负的指数项exp[-j2(ux0+vy0)/N]。3.3.2平移性第三章图像变换3.3.2平移性在数字图像处理中，常常需要将F(u,v)的原点移到N×N频域的中心（平移前空域、频域原点均在左上方），以便能清楚地分析傅立叶谱的情况。要做到此，只需令u0=v0=N/2则exp[j2π(u0x+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因子进行傅立叶变换即可实现。)()(22)1(yxyxNNje第三章图像变换3.3.2平移性平移性告诉我们一个感兴趣的事实：当空域中f(x,y)产生移动时，在频域中只发生相移，并不影响它的傅立叶变换的幅值，因为),(),()(200vuFevuFvyuxNj反之，当频域中F(u,v)产生移动时，相应的f(x,y)在空域中也只发生相移，而幅值不变。第三章图像变换3.3.3周期性和共轭对称性1.周期性离散傅立叶变换DFT和它的逆变换是以N为周期的。对于一维傅立叶变换有：F(u)=F(u±kN)k=0,1,2,···对于二维傅立叶变换有：F(u,v)=F(u±kN,v±lN)k=0,1,2,···l=0,1,2,···第三章图像变换3.3.3周期性和共轭对称性类似有：f(x±kN,y±lN)=f(x,y)即从DFT的角度来看，反变换得到的图像阵列也是二维循环。第三章图像变换3.3.3周期性和共轭对称性2.共轭对称性傅立叶变换结果是以原点为中心的共轭对称函数。对于一维傅立叶变换有：F(u)=F*(kN-u)k=0,1,2,···对于二维傅立叶变换有：F(u,v)=F*(kN-u,lN-v)k=0,1,2,···l=0,1,2,···第三章图像变换周期性和共轭对称性举例3.3.3周期性和共轭对称性第三章图像变换3.二维离散的傅立叶变换结果中频率的分布对应低频成分直流部分二维DFT二维IDFT图像对应高频成分对应低频成分对应高频成分1423直流部分换位3421光学的二维DFT第三章图像变换3.3.3周期性和共轭对称性存储DFT结果的二维数组中频率成分的分布，如上图所示，即数组的左上角相当于直流部分，左上、右上、左下、右下各角的周围对应低频成分，数组中央部分附近对应于高频成分。为了使直流成分出现在数组中央，在把画面分成四分的基础上，进行如图所示的换位也是可以的。使中央对直流部分这样的二维傅立叶变换称作光学傅立叶变换(opticalFouriertransform)。第三章图像变换3.3.4旋转特性•旋转特性描述：如果f(x,y)旋转了一个角度，那么f(x,y)旋转后的图像的傅立叶变换也旋转了相同的角度。•结论：对图像的旋转变换和傅立叶变换的顺序是可交换的。F{R{f(x,y)}}R{F{f(x,y)}}第三章图像变换3.3.4旋转特性反之，如果F(u,v)旋转某一角度，则f(x,y)在空间域也旋转同样的角度。若引入极坐标sincosryrxsincosvu则f(x,y)和F(u,v)分别变为f(r,)和F(ω,φ)。在极坐标中存在以下变换对：f(r,+0)F(ω,φ+0)这条性质以极坐标代以x,y,u,v，则可以得到证明。第三章图像变换3.3.5线性与比例性1.线性•线性的描述：傅立叶变换是线性系统、函数和的傅立叶变换是可分离的。设：f(x,y)的傅立叶变换为F{f(x,y)}g(x,y)的傅立叶变换为F{g(x,y)}有：F{f(x,y)+g(x,y)}=F{f(x,y)}+F{g(x,y)}第三章图像变换3.3.5线性与比例性2.比例性•比例性的描述：af(x,y)aF(u,v)且有：f(ax,by)1/|ab|F(u/a,v/b)第三章图像变换3.3.6均值性•均值性的描述：离散函数的均值等于该函数傅立叶变换在(0,0)点的值。01M0x1N0yey,xfMN1y,xf0,0Fy,xf第三章图像变换3.3.7卷积与相关•卷积与相关:空域和频域之间的基本联系1.卷积•卷积定理的描述：空域中的卷积等价于频域中的相乘f(x,y)*g(x,y)F(u,v)G(u,v)F{f(x,y)*g(x,y)}=F(u,v)G(u,v)同时有：f(x,y)g(x,y)F(u,v)*G(u,v)第三章图像变换3.3.7卷积与相关2.相关•相关定理的描述：空域中f(x,y)与g(x,y)的相关等价于频域中F(u,v)的共轭与G(u,v)相乘f(x,y)g(x,y)F*(u,v)G(u,v)同时有：f*(x,y)g(x,y)F(u,v)G(u,v)第三章图像变换3.4快速傅立叶变换FFT算法基于一个叫做递推加倍的方法，通过推导将DFT转换成两个递推公式。为方便起见我们用下式表达离散傅立叶变换公式：1.FFT算法——基本思想这里WN=exp(-j2/N)是一个常数1N0xuxNWxfN1uF1N0x)N/ux2jexp()x(fN1uF第三章图像变换3.4快速傅立叶变换递推公式推导假设N为：N=2n其中n是一个正整数，因此N可表示为：N=2M这里M仍然是一个正整数。将N=2M代入前一页的式子，得到：1M20xuxM2WxfM21uF1M0x1x2uM21M0xx2uM2w1x2fM1wx2fM121第三章图像变换3.4快速傅立叶变换所以：由于：WN=exp(-j2/N)uxMux2M2WMux2jexpM2ux22jexpW代入前页式子有：xuMxu2M2WW第三章图像变换3.4快速傅立叶变换定义两个符号：uM2uxM1M0xuxM1M0xWW1x2fM1Wx2fM121)u(FuxM1M0xevenWx2fM1uF偶数部分u=0,1,2,…M-1uxM1M0xoddW1x2fM1uF奇数部分u=0,1,2,…M-11012210221212121)(MxxuMMxxuMwxfMwxfMuFxuMxu2M2WW第三章图像变换3.4快速傅立叶变换得出FFT的第一个递推公式：该公式说明F(u)可以通过偶部和奇部之和来计算。uM2oddevenWuFuF21uF第三章图像变换3.4快速傅立叶变换另有：WMu+M=exp[-2j(u+M)/M]=exp[-2ju/M]exp[-2j]=WMuej(-2)=WMu(-1)(-2)=WMu且：W2Mu+M=exp[-2j(u+M)/2M]=exp[-2ju/2M]ej(-1)=W2Mu(-1)(-1)=-W2Mu最后有：WMu+M=WMu；W2Mu+M=-W2Mu第三章图像变换uModdevenMxMxuMuxMuxMMxMxMuMxMuMxMuMMxMxxMuMxMuMMxxMuMWuFuFWWxfMWxfMWWxfMWxfMWxfMWxfMWxfMMuF2101021010210101222212022112121211212121121212121)()()()()()()()()()()()()())(())(()(得出u+M的DFT:uMMuMuMMuMxuMxuM1M20xuxM2WxfM21uF1M0x1x2uM21M0xx2uM2w1x2fM1wx2fM121第三章图像变换得出FFT的第二个递推公式：3.4快速傅立叶变换该公式说明F(u+M)可以通过F(u)偶部和奇部之差来计算。F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu)第三章图像变换3.4快速傅立叶变换得出FFT的两个递推公式：F(u)=1/2(Feven(u)+Fodd(u)W2Mu)F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu)uxM1M0xevenWx2fM1uFuxM1M0xoddW1x2fM1uF第三章图像变换3.4快速傅立叶变换分析这些表达式得到如下一些有趣的特性：（1）一个N个点的变换，能够通过将原始表达式分成两个部分来计算。（2）通过计算两个（N/2）个点的变换。得到Feven(u)和Fodd(u)。（3）偶部与奇部之和得到F(u)的前(N/2)个值。（4）偶部与奇部之差得到F(u)的后(N/2)个值。且不需要额外的变换计算。第三章图像变换3.4快速傅立叶变换归纳快速傅立叶变换的思想：1）通过计算两个单点的DFT，来计算两个点的DFT。2）通过计算两个双点的DFT，来计算四个点的DFT，…，以此类推。3）对于任何N=2n的DFT的计算，通过计算两个N/2点的DFT，来计算N个点的DFT。第三章图像变换3.4快速傅立叶变换2.逆向FFT算法–算法思想描述：用正向变换计算逆向变换。NuxjxfNuFNx2exp110u=0,1,2,...N-