数字图像处理傅立叶变换

1、3.3二维离散傅立叶变换（DiscreteFourier Transform: DFT）性质第三章图像变换二维离散傅立叶变换特性可分离性平移性周期性与共轨对称线性与比例性均值性卷积与相关旋转特性3.3.1可分离性二维离散傅立叶变换DFT可分离性的基本思想是:二维DFT可分离为两次一维DFT。应用:二维快速傅立叶算法FFT ,是通过计算两次一维FFT实现的。可分离性的定义M-1F(u,v)=l/MNx=0N-lf(x,y)exp(-j2%vy/N)y=0exp(-j27cux/M)u=0,1, 2,MT； v=0,1,2,. NT3.3.1可分离性3.3.1可分离性M-1N-l3.3.1可分离性

2、f(x，y) =F(u,v)exp(j2兀vy/N)exp(j27uux/M)u=0v=0x=0,1, 2,MT； y=0,1,2,. NT可分离性成立的推导-先对行（y变量）做变换:N1F（兀 v）二 1/N 丫 /（I）expQ2 刻 y/N）y=0-然后对列（X变量）进行变换:M-1F（u, v） = 1/M E F（x, v） exp（- j2 兀 ux/M）x=03.3.1可分离性-先对行做变换：(0,0)；f(x,y) _(M-l, N-l)-然后对列进行变换:(o,o)；F(x,v)(M-l, N-l)(0,0)；4 F(x,v)v(M-l, N-l)、/ X(0,0)；4 F(

3、u,v)(M-l, N-l)第三章图像变换3.3.2平移性傅立叶变换对有如下平移性质： f(x,y)expj27c(uox/M+voy/N) F(u-u0,v-v0)和 f(x-x0,y-y0) oF(u,v)exp-j2兀(iiXo/M+vyo/N) 以上式子表明，在频域中原点平移到(11,V。)时, 其对应的f(x,y)要乘上一个正的指数项：expj2K(u0x/M+v0y/N)；在空域中图像原点平移到(,yo)时，其对应的 F(u,v)要乘上一个负的指数项：exp -j 27c(uXo/M+vyq/N)。3.3.2平移性对M=N,则类似地有：f(x,y)exp j 27t(uox+voy

4、)/N F(u-u0,v-v0) 和 f(x-x0,y-y0) oF(u,v)exp卜j2兀(iiXo+vyo)/N 在频域中原点平移到( ,Vo)时，其对应的f(x,y)要 乘上一个正的指数项expj27c(u0x+v0y)/N； 在空域中图像原点平移到(x,yo)时，其对应的 F(u,v)要乘上一个负的指数项exp-j2K(ux0+vy0)/N。在数字图像处理中，常常需要将F(u,v)的原点 移到NXN频域的中心(平移前空域、频域原点均在左上方),以便能清楚地分析傅立叶谱的情况O要做到此，只需令UqVq=N/2 则 expj2 兀(iioX+Voy)/N=所以 f(x,y)(l)w oF(

5、u-N/2,v-N/2)上式说明：如果需要将图像傅立叶谱的原点从 左上角(0,0)移到中心点(N/2,N/2),只要f(x,y)乘上 ( 1严y因子进行傅立叶变换即可实现。3.3.2平移性平移性告诉我们一个感兴趣的事实：当空域中 f(x,y)产生移动时，在频域中只发生柑移，并不影响 它的傅立叶变换的幅值，因为T亍(U补叽)b (m,v)e n反之，当频域中F(u,v)产生移动时，相应的 f(x,y)在空域中也只发生相移，而幅值不变。3.3.3周期性和共轨对称性1-周期性离散傅立叶变换DFT和它的逆变换是以N 为周期商。对于一维傅立叶变换有：F (u) =F (u 土 kN)k=0, 1, 2,

6、 对于二维傅立叶变换有：F (u, v) =F (u 土kN, v 土 IN)k二0, 1, 2, 1=0, 1, 2,-类似有：f(x kN,y lN)=f(x,y)即从DFT的角度来看，反变换得到的图像 阵列也是二维循环。2. 对、傅立叶变换结果是以原点为中心的共轨对称函数。对于一维傅立叶变换有：F(u)二 F* (kN-u) k=0, 1, 2, 对于二维傅立叶变换有：F (u, v)二 F* (kN-u , lN-v)k=0, 1, 2, 1=0, 1, 2,a bc dFIGURE 4.34(a) Fourier spectrum showing back-to-back half

7、periods in the interval OuW - 1.(b) Shifted spectrum showing a full period in the same interval.(c) Fourier spectrum of an image, showing the same back-to-back properties as (a but in two dimensions.心)1f(“)lCentered Fourier spectrum.3.二维离散的傅立叶变换结果中频率的分布 F（0,0）表不图像第三章图像变换F（0,0）=1MN；V/-1 N_工工心尹）x=o r=

8、o这说明:假设f(x,y)是一幅图像,在原点的傅 里叶变换等于图像的平均灰度级3.3.3周期性和共轨对称性存储DFT结果的二维数组中频率成分的分布, 如上图所示，即数组的左上角相当于直流部分，左 上、右上、左下、右下各角的周围对应低频成分， 数组中央部分附近对应于高频成分。为了使直流成 分出现在数组中央，在把画面分成四分的基础上， 进行如图所示的换位也是可以的。使中央对直流部分这样的二维傅立叶变换称作 光学傅立叶变换(optical Fourier transform) o第三章图像变换3.3.4旋转特性旋转特性描述：如果f (x, y)旋转了一个角度a ,那么f (x, y)旋 转后的图像的

9、傅立叶变换也旋转了相同的角度a o结论：对图像的旋转变换和傅立叶变换的顺序是可 交换的。FRf(x,y) o RFf(x,y)3.3.4旋转特性第三章图像变换反之，如果F(u，v)旋转某一角度，贝Uf(x，y)在空间 若引入极坐标fx =厂 COS0(U = CCOS0二厂 sin0v = sin0贝!jf(x,y)和F(u,v)分知变为f(叩)和F(o)，9 )o在极坐 标中存在以下变换对：f(r, 0+00) oF(o,(p+ 00)这条性质以极坐标代以x,y,u,v,则可以得到证明。3.3.5线性与比例性1 线性线性的描述：傅立叶变换是线性系统、函数和的傅立叶变换是可分离的。设：f (x

10、, 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) o aF (u, v)且有：f (ax, by) o 1/1 ab | F (u/a, v/b)3.3.6均值性均值性的描述:离散函数的均值等于该函数傅立叶变换在(o, o)点的值。_M-l N-1F(x,y)=l/MNf(x,yHx=0 y=0f(x,y)二 F(0,0)3.3.7卷积与相关卷积与相关:空域和频域之间的基本联系1.

11、卷积卷积定理的描述:空域中的卷积等价于频域中的相乘f(X, y) *g (x, y) o 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) o 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) Og (x, y) o F* (u, v) G (u, v)同时有：f* (x, y)g (x, y) o F (u, v) oG (u, v)3

12、.4快速傅立叶变换1. FFT算法基本思想FFT算法基于一个叫做递推加倍的方法，通过推导将DFT转换成两个递推公式。为方便起见我们用下式表达离散傅立叶变换公式:N-1F(u) = 1/N f(x)exp(-j27tux / N)x=0N-1F(u)=l/N2；f(xXWN)uxx=0这里WN = exp (-j27t/N)是一个常数34快速傅立叶变换递推公式推导假设N为：N = 2n其中n是一个正整数，因此N可表示为：N = 2M这里M仍然是一个正整数。将N = 2M代入前一页的 式子，得到：I2M-1F（u） = l/（2M）Jf（xXW2M）uxIx=0I M1M1二 1/2 1/M f（

13、2x ）w 貯）+ 1/M f（2x + l）w x+1）x 二0x 二03.4快速傅立叶变换第三章图像变换由于：WN = exp (-j27t/N)W2M=exp-j27r2ux/2M =exp-j2 7tux /M = WyX 所以：W=W代入前页式子有：3.4快速傅立叶变换偶数部分u=0, 1, 2,.M-l奇数部分u=0, 1, 2,.M-lAf-1MAF（吩 1/2 1/M X /（2x）船）+ 1/M 工 /（2x +1 岡严）A-0Y-0代=畤M-lM-1F（u） = 1/2 1/M（2x）Wx + 1/M（2x + 1）WX WMx=0x=0定义两个符号:M-lFeve（u）=

14、l/MXf（2X）W-x=0M-lFodd（u）=l/Mf（2x+1Kx=03.4快速傅立叶变换第三章图像变换得出FFT的第一个递推公式：F(u)=l/2(Feven(u)+Fodd(u)WM)该公式说明F (u)可以通过偶部和奇部之和来计算。3-4快速傅立叶变换另有：Wm+m 二 exp-2j;c(u+M)/M=exp -2 j7tu/M exp -2 j7c二 W/eJ71 = WMU(-1) (_2)二 WMU且： W2Mu+m 二 exp -2 j;i (u+M) /2M=exp -2j7tu/2M eM(T)=W2MU(一1)(T)= -W2MU最后有:Wm”m 二 WMU ； W2

15、mm = -W2M-2M-I=|方（2兀）*2络”+M）（2x）工二oM-V三工/（2训帶心+三工/（2x + l）WF（u）=l/（2M）f（xXW2M）uxx=0M-l= 1/2 1/Mf（2x）w得出ii+M的DFT:12M-1F（W + M）/（x）W2（r）x2M塔1 M-1M-lM-1眇）+ l/Mf（2x + l）w 谿Z x=0x=0W畀=叱;；W-M = -W扣1 M-l+丄/（2兀+ 1网嘗3）M *02M-Ix=0M-4 三/（2讪囂 +三工/（2x + 1）W,（-W2：）2_Mlrx=0二 Veven（%） - 臨（弘阿；3.4快速傅立叶变换得出FFT的第二个递推公式

16、:F(u+M)= l/2(Feven(u)-Fodd(u)W2/)UJ该公式说明F(u+M)可以通过F(u)偶部和奇部之差来计算。3.4快速傅立叶变换M-1Fewn(u)=l/Mf(2x)W-x=0M-1Fdd(u)=l/Mf(2x + l)W席x=0得出FFT的两个递推公式：F (u)二 1/2 (Feven (u) +Fdd (u) W2MU)F(u+M)二 l/2(Feven(u)-Fodd(u)W2/)3.4快速傅立叶变换3.4快速傅立叶变换分析这些表达式得到如下一些有趣的特性:（1） 一个N个点的变换，能够通过将原始表达式分成两个部分来计算。(2)通过计算两个（N/2）个点的变换。得

17、到Feven（U）和 Fodd ）。（3）偶部与奇部之和得到F（U）的前（N/2）个值。（4）偶部与奇部之差得到F（u）的后（N/2）个值。 且不需要额外的变换计算。归纳快速傅立叶变换的思想：1）通过计算两个单点的DFT, DFTo2）通过计算两个双点的DFT, DFT,，以此类推。来计算两个点的来计算四个点的通过计算两个N/23）对于任何N=2的DFT的计算， 点的DFT,来计算N个点的DFT。2 逆向FFT算法-算法思想描述：用正向变换计算逆向变换。N-1F（%）二 1/2V 工/*（x）cxp-）2 加 x/Wx=0u = 0,1, 2,. N-lN于（兀）二工 F（u）cxpj2加x/

18、wu=0x = 0,1, 2,. NT3.4快速傅立叶变换第三章图像变换在离散逆向变换表达式两边同取共轨，并除NN-1F(w)= l/A/(x)exp - j2ma/Nx=0N-l/M= Z F)expj2 加优/NM = 0N-1l/Nf *(x)二 l/NF*(u)exp|-j27mx/Nu=0u = 0,1, 2,. NT可以看出，上式的右端在形式上就是傅立叶正 变换。因此，只要将F*(u)输入，用正向变换算法 计算，得到1/Nf*(x),取共轨并乘上N,即得到 f(x) O3.4快速傅立叶变换3. FFT算法实现举例通过一个实例来体会_Tfft算法：设：有函数f(X),其N二23二8,

19、有：f(0), f(l), f(2), f(3), f(4), f, f(6), f(7)计算：F(0), F(l), F(2), F(3), F(4), F(5),F(6),F(7)首先分成奇偶两组，有: f(0), f(2), f(4), f(6) f(l), f(3), f(5), f(7) 为了利用递推特性，再分成两组，有： f(0), f(4) , f(2), f(6) f(l), f(5) , f(3), f(7) 第三章图像变换算法实现的几个关键点1）地址的排序： 按位倒序规则序17 7 17 17 )/ 17 17 17 M 04261537 z( /( /( z( /l /(

20、X /( zt 新 ffffffff址地 o o o 1A IX 1A 1A o o 1 1 o o 1 1 亲 ololololIK 7 7 )/ 17 7 17 J/ 阳 01234567 原 ffffffff地 如原N址o o IX oAu o IX IX Av Av 1A IX ov Av IX IX IX IX 例第三章图像变换3-4快速傅立叶变换地址+4计算顺序及地址增量地址+2地址+12)7 |7 17 |7 |7 7 17 04261537 /( z( /( /( /( z( Z(N z( ffffffff17 7 7 7 7 / 7 704261537/( z(x z(x 7( z( /( /( 7(ffffffff第三章图像变换F(u) = l/2(Feven(u)+Fodd(u)W2Mu)F(u+M)= l/2(Feven(u)-Fodd(u)VV2Mu)3.4快速傅立叶变换3)复系数的计算： 尤拉公式W2M=exp-j2K/2M=exp-j7t/M=cos(k/M) - jsin(7t/M)3.5离散余弦变换(Discrete CosineTransform, DCT)在傅立叶级数展开式中，如果被展开Fl的函数是偶函数。据此特点可以推导出另 一种变换一离散余弦变换。假如已知函数并非偶函数(如一维函 数f(x)(