《数字图像处理傅立叶变换.ppt》由会员分享，可在线阅读，更多相关《数字图像处理傅立叶变换.ppt（46页珍藏版）》请在三一办公上搜索。
1、,3.3 二维离散傅立叶变换(Discrete Fourier Transform：DFT)性质,二维离散傅立叶变换特性可分离性平移性周期性与共轭对称旋转特性,线性与比例性 均值性 卷积与相关,3.3.1 可分离性,二维离散傅立叶变换DFT可分离性的基本思想是：二维DFT可分离为两次一维DFT。应用：二维快速傅立叶算法FFT，是通过计算两次一维FFT实现的。,3.3.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,3.3.1 可分离性,可分离性成立的推导先对行（y变量）做变换：,然后对列（x变量）进行变换：,3.
2、3.1 可分离性,先对行做变换：,然后对列进行变换：,3.3.2 平移性,3.3.2 平移性,3.3.2 平移性,3.3.2 平移性,3.3.3 周期性和共轭对称性,1.周期性 离散傅立叶变换DFT和它的逆变换是以N为周期的。对于一维傅立叶变换有：F(u)=F(ukN)k=0,1,2,对于二维傅立叶变换有：F(u,v)=F(ukN,vlN)k=0,1,2,l=0,1,2,3.3.3 周期性和共轭对称性,类似有：f(xkN,ylN)=f(x,y)即从DFT的角度来看，反变换得到的图像阵列也是二维循环。,3.3.3 周期性和共轭对称性,2.共轭对称性 傅立叶变换结果是以原点为中心的共轭对称函数。对
3、于一维傅立叶变换有：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,周期性和共轭对称性,存储DFT结果的二维数组中频率成分的分布，如上图所示，即数组的左上角相当于直流部分，左上、右上、左下、右下各角的周围对应低频成分，数组中央部分附近对应于高频成分。为了使直流成分出现在数组中央，在把画面分成四分的基础上，进行如图所示的
4、换位也是可以的。使中央对直流部分这样的二维傅立叶变换称作光学傅立叶变换(optical Fourier transform)。,3.3.4 旋转特性,旋转特性描述：如果f(x,y)旋转了一个角度，那么f(x,y)旋转后的图像的傅立叶变换也旋转了相同的角度。结论：对图像的旋转变换和傅立叶变换的顺序是可交换的。FRf(x,y)RFf(x,y),3.3.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，
5、则可以得到证明。,3.3.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),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)点的值。,3.3.7 卷积与相关,卷积与相关:空域和频域之间的基本联系1.卷积 卷积定理的描述：空域中的卷积等价于频
6、域中的相乘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),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
7、=exp(-j2/N)是一个常数,3.4 快速傅立叶变换,递推公式推导 假设N为：N=2n 其中n是一个正整数，因此N可表示为：N=2M 这里M仍然是一个正整数。将N=2M代入前一页的式子，得到：,3.4 快速傅立叶变换,所以：,由于：WN=exp(-j2/N),代入前页式子有：,3.4 快速傅立叶变换,定义两个符号：,偶数部分u=0,1,2,M-1,奇数部分u=0,1,2,M-1,3.4 快速傅立叶变换,得出FFT 的第一个递推公式：,该公式说明F(u)可以通过偶部和奇部之和来计算。,3.4 快速傅立叶变换,另有：WMu+M=exp-2j(u+M)/M=exp-2ju/Mexp-2j=WMu
8、ej(-2)=WMu(-1)(-2)=WMu且：W2Mu+M=exp-2j(u+M)/2M=exp-2ju/2M ej(-1)=W2Mu(-1)(-1)=-W2Mu最后有：WMu+M=WMu；W2Mu+M=-W2Mu,得出u+M的DFT:,得出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),3
9、.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
10、快速傅立叶变换,2.逆向FFT算法算法思想描述：用正向变换计算逆向变换。,u=0,1,2,.N-1,x=0,1,2,.N-1,3.4 快速傅立叶变换,在离散逆向变换表达式两边同取共轭，并除N,u=0,1,2,.N-1,可以看出，上式的右端在形式上就是傅立叶正变换。因此，只要将F*(u)输入，用正向变换算法计算，得到1/Nf*(x)，取共轭并乘上N，即得到f(x)。,3.4 快速傅立叶变换,3.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
11、),F(3),F(4),F(5),F(6),F(7),3.4 快速傅立叶变换,首先分成奇偶两组，有：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),f(0),f(4)f(2),f(6)f(1),f(5)f(3),f(7)F2(0),F2(4)F2(2),F2(6)F2(1),F2(5)F2(3),F2(7)F4(0),F4(2),F4(4),F4(6)F4(1),F4(3),F4(5),F4(7)F8(0),F8(1),F8(2),F8(3),F8(4),
12、F8(5),F8(6),F8(7),3.4 快速傅立叶变换,算法实现的几个关键点1）地址的排序：按位倒序规则例如：N=23=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),3.4 快速傅立叶变换,2）计算顺序及地址增量 地址+1 地址+2 地址+4 f(0)F2(0)F4(0)f(4)F2(4)F4(4)f(2)F2(2)F4(2)f(6)F2(6)F4
13、(6)f(1)F4(1)F4(1)f(5)F2(5)F4(5)f(3)F2(3)F4(3)f(7)F2(7)F4(7),3.4 快速傅立叶变换,3）复系数的计算：尤拉公式 W2M=exp-j2/2M=exp-j/M=cos(/M)-jsin(/M),F(u)=1/2(Feven(u)+Fodd(u)W2Mu)F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu),3.5 离散余弦变换（Discrete Cosine Transform,DCT）,在傅立叶级数展开式中，如果被展开的函数是偶函数。据此特点可以推导出另一种变换离散余弦变换。假如已知函数并非偶函数（如一维函数f(x)(x0)
14、）。我们人为地把它对称地扩展到x0，构成偶函数（如fs(x)）。,3.5 离散余弦变换（Discrete Cosine Transform,DCT）,一维离散余弦变换的定义式：,式中C(u)是第u个余弦变换系数，u是广义频率变量，u=1,2,N-1；f(x)是时域N点序列，x=0,1,2,N-1。,3.5 离散余弦变换（Discrete Cosine Transform,DCT）,一维离散余弦反变换的定义式：,3.5 离散余弦变换（Discrete Cosine Transform,DCT）,二维离散余弦变换的定义式：,(4),其中f(x,y)是空间域二维向量之元素；u,v=1,2,N-1,x,y=0,1,2,N-1；C(u,v)是变换系数阵列之元素；式中表示的阵列为NN。,3.5 离散余弦变换（Discrete Cosine Transform,DCT）,
