fft 图像_图像处理工具

数字图像处理傅立叶变换.ppt课件 　　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-1x=0,1,2,M-1；y=0,1,2,.N-13.3.1 可分离性可分离性成立的推导先对行（y变量）做变换： 然后对列（x变量）进行变换：3.3.1 可分 　　2、离性先对行做变换： 然后对列进行变换：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)expj2(u0 x/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)要乘上一个正的指数项： expj2(u0 x/M+v0y/N) ； 在空域中图像原点平移到(x0,y0)时，其对应的F(u 　　3、,v)要乘上一个负的指数项： exp-j2(ux0/M+vy0/N) 。3.3.2 平移性 对于M=N，则类似地有： f(x,y)expj2(u0 x+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)要乘上一个正的指数项expj2(u0 x+v0y)/N； 在空域中图像原点平移到(x0,y0)时，其对应的F(u,v)要乘上一个负的指数项exp-j2(ux0+vy0)/N 。3.3.2 平移性3.3.2 平移性 在数字图像处理中，常常需要将F(u,v)的原点移到NN频域 　　4、的中心（平移前空域、频域原点均在左上方），以便能清楚地分析傅立叶谱的情况。要做到此，只需令 u0=v0=N/2则expj2(u0 x+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因子进行傅立叶变换即可实现。3.3.2 平移性 平移性告诉我们一个感兴趣的事实：当空域中f(x,y)产生移动时，在频域中只发生相移，并不影响它的傅立叶变换的幅值，因为 反之，当频域中F(u,v)产生移动时，相应的f(x,y)在空域中也只发生相移，而幅值不变。3.3.3 　　5、 周期性和共轭对称性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.共轭对称性 傅立叶变换结果是以原点为中心的共轭对称函数。对于一维傅立叶变换有： F(u) = F*(kN-u) k=0,1,2,对于二维傅立叶变换有： F(u,v) = F*(kN-u ,lN- 　　6、v) k=0,1,2, l=0,1,2,周期性和共轭对称性举例3.3.3 周期性和共轭对称性3. 二维离散的傅立叶变换结果中频率的分布对应低频成分直流部分二维DFT二维IDFT图像对应高频成分对应低频成分对应高频成分1 42 3直流部分换位3421光学的二维DFT3.3.3 周期性和共轭对称性 存储DFT结果的二维数组中频率成分的分布，如上图所示，即数组的左上角相当于直流部分，左上、右上、左下、右下各角的周围对应低频成分，数组中央部分附近对应于高频成分。为了使直流成分出现在数组中央，在把画面分成四分的基础上，进行如图所示的换位也是可以的。 使中央对直流部分这样的二维傅立叶变换称作光学傅立叶变换 　　7、(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，则可以得到证明。3.3.5 线性与比例性1.线 　　8、性 线性的描述：傅立叶变换是线性系统、函数和的傅立叶变换是可分离的。设：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.卷积 卷积定理的描述：空域中的卷积等价于频域中的相乘f(x,y)*g(x,y) F( 　　9、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 = exp(-j2/N) 　　10、 是一个常数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-13.4 快速傅立叶变换得出FFT 的第一个递推公式：该公式说明F(u)可以通过偶部和奇部之和来计算。3.4 快速傅立叶变换另有：WMu+M = exp-2j(u+M)/M= exp-2ju/Mexp-2j= WMuej(-2) = W 　　11、Mu(-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 　　12、(u)W2Mu) 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个点的D 　　13、FT。3.4 快速傅立叶变换2.逆向FFT算法算法思想描述：用正向变换计算逆向变换。u = 0,1,2,.N-1x = 0,1,2,.N-13.4 快速傅立叶变换 在离散逆向变换表达式两边同取共轭，并除Nu = 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), 　　14、 f(7) 计算： F(0), F(1), F(2), 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 　　15、), F4(6) F4(1), F4(3), F4(5),F4(7) F8(0), F8(1), F8(2), F8(3), F8(4), 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 　　16、 快速傅立叶变换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(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)）。我们人为地把它对称地扩展到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。