数字图像处理傅立叶变换.ppt

单击此处编辑母版标题样式0,单击此处编辑母版文本样式1,第二级2,第三级3,第四级4,第五级5,2021/3/2,*,第三章 图像变换,数字图像处理,傅立叶变换原理,2021/3/2,1,1.1,二维离散傅立叶变换,(Discrete Fourier Transform,：,DFT),性质,二维离散傅立叶变换特性,可分离性,平移性,周期性与共轭对称,旋转特性,线性与比例性,均值性,卷积与相关,2021/3/2,2,1.1.1,可分离性,二维离散傅立叶变换,DFT,可分离性的基本思想是：,二维,DFT,可分离为两次一维,DFT,。,应用：,二维快速傅立叶算法,FFT,，是通过计算两次一维,FFT,实现的。,2021/3/2,3,1.1.1,可分离性,可分离性的定义,u=0,1,2,M-1,；,v=0,1,2,.N-1,x=0,1,2,M-1,；,y=0,1,2,.N-1,2021/3/2,4,1.1.1,可分离性,可分离性成立的推导,先对行（,y,变量）做变换：,然后对列（,x,变量）进行变换：,2021/3/2,5,1.1.1,可分离性,先对行做变换：,然后对列进行变换：,f(x,y),（,0,0,）,（,M-1,，,N-1,）,x,y,F(x,v),（,0,0,）,（,M-1,，,N-1,）,x,v,F(x,v),（,0,0,）,（,M-1,，,N-1,）,x,v,F(u,v),（,0,0,）,（,M-1,，,N-1,）,u,v,2021/3/2,6,傅立叶变换对有如下平移性质：,f(x,y)expj2,(,u,0,x/M+v,0,y/N),F(u-u,0,v-v,0,),和,f(x-x,0,y-y,0,),F(u,v)exp-j2,(ux,0,/M,+vy,0,/N),以上式子表明，,在,频域中,原点,平移到,(,u,0,v,0,),时,，,其对应的,f(,x,y),要,乘,上一个正的指数项：,expj2,(u,0,x/M+v,0,y/N),；,在空域中图像原点平移到,(x,0,y,0,),时，,其,对应的,F(u,v),要乘上一个负的指数项：,exp-j2,(ux,0,/M,+vy,0,/N),。,1.1.2,平移性,2021/3/2,7,对于,M=N,，,则类似地有：,f(x,y)expj2,(u,0,x+v,0,y)/N,F(u-u,0,v-v,0,),和,f(x-x,0,y-y,0,),F(u,v)exp-j2,(ux,0,+vy,0,)/N,在,频域中,原点,平移到,(,u,0,v,0,),时,，,其对应的,f(,x,y),要,乘,上一个正的指数项,expj2,(u,0,x+v,0,y)/N,；,在空域中图像原点平移到,(x,0,y,0,),时，,其,对应的,F(u,v),要乘上一个负的指数项,exp-j2,(ux,0,+vy,0,)/N,。,1.1.2,平移性,2021/3/2,8,3.3.2,平移性,在数字图像处理中，常常需要将,F(u,v),的原点移到,N,N,频域的中心（平移前空域、频域原点均在左上方），以便能清楚地分析傅立叶谱的情况。要做到此，只需令,u,0,=v,0,=N/2,则,expj2,(u,0,x+v,0,y)/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,因子进行傅立叶变换即可实现。,2021/3/2,9,1.1.2,平移性,平移性告诉我们一个感兴趣的事实：当空域中,f(,x,y),产生,移动,时，在频域中只发生相移，,并不影响它的傅立叶变换的幅,值,，因为,反之，当频域中,F(u,v),产生,移动,时，相应的,f(x,y),在空域中也只发生相移，而,幅,值不变。,2021/3/2,10,1.1.3,周期性和共轭对称性,1.,周期性,离散傅立叶变换,DFT,和它的逆变换是以,N,为周期的。,对于一维傅立叶变换有：,F(u)=F(u,kN),k=0,1,2,对于二维傅立叶变换有：,F(u,v)=F(u,kN,v,l,N),k=0,1,2,l=0,1,2,2021/3/2,11,1.1.3,周期性和共轭对称性,类似有：,f(,x,kN,y,l,N)=,f(,x,y),即从,DFT,的角度来看，反变换得到的图像阵列也是二维循环。,2021/3/2,12,1.1.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,2021/3/2,13,周期性和共轭对称性举例,1.1.3,周期性和共轭对称性,2021/3/2,14,3.,二维离散的傅立叶变换结果中频率的分布,对应低频成分,直流部分,二维,DFT,二维,IDFT,图像,对应高频成分,对应低频成分,对应高频成分,1 4,2 3,直流部分,换位,3,4,2,1,光学的二维,DFT,2021/3/2,15,1.1.3,周期性和共轭对称性,存储,DFT,结果的二维数组中频率成分的分布，如上图所示，即数组的左上角相当于直流部分，左上、右上、左下、右下各角的周围对应低频成分，数组中央部分附近对应于高频成分。为了使直流成分出现在数组中央，在把画面分成四分的基础上，进行如图所示的换位也是可以的。,使中央对直流部分这样的二维傅立叶变换称作,光学傅立叶变换,(,optical Fourier transform),。,2021/3/2,16,1.1.4,旋转特性,旋转特性描述：,如果,f(x,y),旋转了一个角度,，那么,f(x,y),旋转后的图像的傅立叶变换也旋转了相同的角度,。,结论：,对图像的旋转变换和傅立叶变换的顺序是可交换的。,FRf(x,y),RFf(x,y),2021/3/2,17,1.1.4,旋转特性,反之，如果,F(u,v),旋转某一角度，则,f(x,y),在空间域也旋转同样的角度。,若引入极坐标,则,f(x,y),和,F(u,v),分别变为,f(r,),和,F(,),。在极坐标中存在以下变换对：,f(r,+,0,),F(,+,0,),这条性质以极坐标代以,x,y,u,v,，则可以得到证明。,2021/3/2,18,1.1.5,线性与比例性,1.,线性,线性的描述：傅立叶变换是线性系统、函数和的傅立叶变换是可分离的。,设：,f(x,y),的傅立叶变换为,Ff(x,y),g(x,y),的傅立叶变换为,Fg(x,y),有：,Ff(x,y)+g(x,y)=Ff(x,y)+Fg(x,y),2021/3/2,19,1.1.5,线性与比例性,2.,比例性,比例性的描述：,af(x,y),aF(u,v),且有：,f(ax,by),1/|ab|F(u/a,v/b),2021/3/2,20,1.1.6,均值性,均值性的描述：,离散函数的均值等于该函数傅立叶变换在,(0,0),点的值。,2021/3/2,21,1.1.7,卷积与相关,卷积与相关,:,空域和频域之间的基本联系,1.,卷积,卷积定理的描述：,空域中的卷积等价于频域中的相乘,f(x,y)*g(x,y),F(u,v)G(u,v),Ff(x,y)*g(x,y)=F(u,v)G(u,v),同时有：,f(x,y)g(x,y),F(u,v)*G(u,v),2021/3/2,22,1.1.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),2021/3/2,23,1.2,快速傅立叶变换,FFT,算法基于一个叫做,递推加倍,的方法，通过推导将,DFT,转换成两个递推公式。为方便起见我们用下式表达离散傅立叶变换公式：,1.FFT,算法,基本思想,这里,W,N,=exp(-j2,/N),是一个常数,2021/3/2,24,1.2,快速傅立叶变换,递推公式推导,假设,N,为：,N=2,n,其中,n,是一个正整数，因此,N,可表示为：,N=2M,这里,M,仍然是一个正整数。将,N=2M,代入前一页的式子，得到：,2021/3/2,25,1.2,快速傅立叶变换,所以：,由于：,W,N,=exp(-j2,/N),代入前页式子有：,2021/3/2,26,1.2,快速傅立叶变换,定义两个符号：,偶数部分,u=0,1,2,M-1,奇数部分,u=0,1,2,M-1,2021/3/2,27,1.2,快速傅立叶变换,得出,FFT,的第一个递推公式：,该公式说明,F(u),可以通过偶部和奇部之和来计算。,2021/3/2,28,1.2,快速傅立叶变换,另有：,W,M,u+M,=,exp,-2j,(u+M)/M,=exp-2ju/Mexp-2j,=,W,M,u,e,j,(-2),=,W,M,u,(-1),(-2),=,W,M,u,且：,W,2M,u+M,=,exp,-2j,(u+M)/2M,=,exp-2ju/2M,e,j,(-1),=,W,2M,u,(-1),(-1),=-,W,2M,u,最后有：,W,M,u+M,=,W,M,u,；,W,2M,u+M,=,-,W,2M,u,2021/3/2,29,得出,u+M,的,DFT:,2021/3/2,30,得出,FFT,的第二个递推公式：,1.2,快速傅立叶变换,该公式说明,F(u+M),可以通过,F(u),偶部和奇部之差来计算。,F(u+M)=1/2(F,even,(u)-F,odd,(u)W,2M,u,),2021/3/2,31,1.2,快速傅立叶变换,得出,FFT,的两个递推公式：,F(u)=1/2(F,even,(u),+,F,odd,(u)W,2M,u,),F(u+M)=1/2(F,even,(u),-,F,odd,(u)W,2M,u,),2021/3/2,32,1.2,快速傅立叶变换,分析这些表达式得到如下一些有趣的特性：,（,1,）一个,N,个点的变换，能够通过将原始表达,式分成两个部分来计算。,（,2,）通过计算两个（,N/2,）个点的变换。得到,F,even,(u),和,F,odd,(u),。,（,3,）偶部与奇部之和得到,F(u),的前,(N/2),个值。,（,4,）偶部与奇部之差得到,F(u),的后,(N/2),个值。,且不需要额外的变换计算。,2021/3/2,33,1.2,快速傅立叶变换,归纳快速傅立叶变换的思想：,1,）通过计算两个单点的,DFT,，来计算两个点的,DFT,。,2,）通过计算两个双点的,DFT,，来计算四个点的,DFT,，,，以此类推。,3,）对于任何,N=2,n,的,DFT,的计算，,通过计算两个,N/2,点的,DFT,，来计算,N,个点的,DFT,。,2021/3/2,34,1.2,快速傅立叶变换,2.,逆向,FFT,算法,算法思想描述：用正向变换计算逆向变换。,u=0,1,2,.N-1,x=0,1,2,.N-1,2021/3/2,35,1.2,快速傅立叶变换,在离散逆向变换表达式两边同取共轭，并除,N,u=0,1,2,.N-1,可以看出，上式的右端在形式上就是傅立叶正变换。因此，只要将,F,*,(u),输入，用正向变换算法计算，得到,1/Nf*(x),，,取共轭并乘上,N,，即得到,f(x),。,2021/3/2,36,1.2,快速傅立叶变换,3.,FFT,算法实现举例,通过一个实例来体会一下,FFT,算法：,设：有函数,f(x),，其,N=2,3,=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),2021/3/2,37,1.2,快速傅立叶变换,首先分成奇偶两组，有：,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),2021/3/2,38,f(0),f(4)f(2),f(6)f(1),f(5)f(3),f(7),F,2,(0),F,2,(4)F,2,(2),F,2,(6)F,2,(1),F,2,(5)F,2,(3),F,2,(7),F,4,(0),F,4,(2),F,4,(4),F,4,(6)F,4,(1),F,4,(3),F,4,(5),F,4,(7),F,8,(0),F,8,(1),F,8,(2),F,8,(3),F,8,(4),F,8,(5),F,8,(6),F,8,(7),2021/3/2,39,1.2,快速傅立叶变换,算法实现的几个关键点,1,）地址的排序：,按位倒序规则,例如：,N=2,3,=8,原地址 原顺序 新地址 新顺序,000 f(0)000 f(0),001 f(1)100 f(4),010 f(2)010 f(2),011 f(3)110 f(6),100 f(4)001 f(1),101 f(5)101 f(5),110 f(6)011 f(3),111 f(7)111 f(7),2021/3/2,40,1.2,快速傅立叶变换,2,）计算顺序及地址增量,地址,+1,地址,+2,地址,+4,f(0)F,2,(0)F,4,(0),f(4)F,2,(4)F,4,(4),f(2)F,2,(2)F,4,(2),f(6)F,2,(6)F,4,(6),f(1)F,4,(1)F,4,(1),f(5)F,2,(5)F,4,(5),f(3)F,2,(3)F,4,(3),f(7)F,2,(7)F,4,(7),2021/3/2,41,1.2,快速傅立叶变换,3,）,复系数的计算：,尤拉公式,W,2M,=exp-j2,/2M,=exp-j,/M,=cos(,/M)-jsin(,/M),F(u)=1/2(F,even,(u)+F,odd,(u),W,2M,u,),F(u+M)=1/2(F,even,(u)-F,odd,(u),W,2M,u,),2021/3/2,42,数字图像处理,傅立叶变换程序实现,2021/3/2,43,离散傅立叶变换MATLAB程序,1.图像的二维离散傅立叶频谱。,I=imread(lena.bmp);,Imshow(I);,J=fftfhift(fft2(I);,figure;,imshow(log(abs(J),8,10);,2021/3/2,44,离散傅立叶变换,MATLAB,程序,2.二维离散傅立叶变换的旋转性,I=zeros(256,256);,I(28:228,108:148)=1;,Imshow(I);,J=fft2(I);,F=abs(J);,K=fftshift(F);,Figure;imshow(K,5,50);,2021/3/2,45,离散傅立叶变换,MATLAB,程序,L=imrotate(I,315,bilinear,crop);%对图像进行旋转,figure;imsow(L);,N=fft2(L);,S=abs(N);,M=fftshift(S);,Figure;imshow(M);,2021/3/2,46,傅立叶变换的应用,1.对连续信号（模拟信号）处理,2.对离散信号（数字信号）处理,3.求解激励信号的响应（卷积或者卷积和）,2021/3/2,47,