数字图像处理傅立叶变换

数字图像处理傅立叶变换第1页，共46页，2023年，2月20日，星期六3.3.1可分离性•二维离散傅立叶变换DFT可分离性的基本思想是：

二维DFT可分离为两次一维DFT。•应用：

二维快速傅立叶算法FFT，是通过计算两次一维FFT实现的。第2页，共46页，2023年，2月20日，星期六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-1第3页，共46页，2023年，2月20日，星期六3.3.1可分离性可分离性成立的推导先对行（y变量）做变换：然后对列（x变量）进行变换：第4页，共46页，2023年，2月20日，星期六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第5页，共46页，2023年，2月20日，星期六•

傅立叶变换对有如下平移性质：

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平移性第6页，共46页，2023年，2月20日，星期六•对于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平移性第7页，共46页，2023年，2月20日，星期六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因子进行傅立叶变换即可实现。第8页，共46页，2023年，2月20日，星期六3.3.2平移性

平移性告诉我们一个感兴趣的事实：当空域中f(x,y)产生移动时，在频域中只发生相移，并不影响它的傅立叶变换的幅值，因为

反之，当频域中F(u,v)产生移动时，相应的f(x,y)在空域中也只发生相移，而幅值不变。第9页，共46页，2023年，2月20日，星期六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,···

第10页，共46页，2023年，2月20日，星期六3.3.3周期性和共轭对称性类似有：f(x±kN,y±lN)=f(x,y)即从DFT的角度来看，反变换得到的图像阵列也是二维循环。

第11页，共46页，2023年，2月20日，星期六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,···第12页，共46页，2023年，2月20日，星期六周期性和共轭对称性举例3.3.3周期性和共轭对称性第13页，共46页，2023年，2月20日，星期六3.二维离散的傅立叶变换结果中频率的分布对应低频成分直流部分二维DFT二维IDFT图像对应高频成分对应低频成分对应高频成分1423直流部分换位3421光学的二维DFT第14页，共46页，2023年，2月20日，星期六3.3.3

周期性和共轭对称性

存储DFT结果的二维数组中频率成分的分布，如上图所示，即数组的左上角相当于直流部分，左上、右上、左下、右下各角的周围对应低频成分，数组中央部分附近对应于高频成分。为了使直流成分出现在数组中央，在把画面分成四分的基础上，进行如图所示的换位也是可以的。使中央对直流部分这样的二维傅立叶变换称作光学傅立叶变换(opticalFouriertransform)。第15页，共46页，2023年，2月20日，星期六3.3.4旋转特性旋转特性描述：

如果f(x,y)旋转了一个角度，那么f(x,y)旋转后的图像的傅立叶变换也旋转了相同的角度。

•结论： 对图像的旋转变换和傅立叶变换的顺序是可交换的。

F{R{f(x,y)}}R{F{f(x,y)}}第16页，共46页，2023年，2月20日，星期六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，则可以得到证明。第17页，共46页，2023年，2月20日，星期六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)}第18页，共46页，2023年，2月20日，星期六3.3.5线性与比例性2.比例性•比例性的描述： af(x,y)aF(u,v)

且有：

f(ax,by)1/|ab|F(u/a,v/b)第19页，共46页，2023年，2月20日，星期六3.3.6均值性均值性的描述：

离散函数的均值等于该函数傅立叶变换在(0,0)点的值。

第20页，共46页，2023年，2月20日，星期六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)第21页，共46页，2023年，2月20日，星期六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)第22页，共46页，2023年，2月20日，星期六3.4快速傅立叶变换FFT算法基于一个叫做递推加倍的方法，通过推导将DFT转换成两个递推公式。为方便起见我们用下式表达离散傅立叶变换公式：

1.FFT算法——基本思想

这里

WN

=exp(-j2/N)

是一个常数第23页，共46页，2023年，2月20日，星期六3.4快速傅立叶变换递推公式推导假设N为： N=2n

其中n是一个正整数，因此N可表示为：

N=2M这里M仍然是一个正整数。将N=2M代入前一页的式子，得到： 第24页，共46页，2023年，2月20日，星期六3.4快速傅立叶变换所以：由于：WN=exp(-j2/N)代入前页式子有：第25页，共46页，2023年，2月20日，星期六3.4快速傅立叶变换定义两个符号：偶数部分u=0,1,2,…M-1奇数部分u=0,1,2,…M-1第26页，共46页，2023年，2月20日，星期六3.4快速傅立叶变换得出FFT的第一个递推公式：

该公式说明F(u)可以通过偶部和奇部之和来计算。第27页，共46页，2023年，2月20日，星期六3.4快速傅立叶变换另有：WMu+M=

exp[-2j(u+M)/M] =exp[-2ju/M]exp[-2j] =WMuej(-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第28页，共46页，2023年，2月20日，星期六得出u+M的DFT:第29页，共46页，2023年，2月20日，星期六得出FFT的第二个递推公式：3.4快速傅立叶变换该公式说明F(u+M)可以通过F(u)偶部和奇部之差来计算。F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu)第30页，共46页，2023年，2月20日，星期六3.4快速傅立叶变换得出FFT的两个递推公式：

F(u)=1/2(Feven(u)+Fodd(u)W2Mu)F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu)

第31页，共46页，2023年，2月20日，星期六3.4快速傅立叶变换分析这些表达式得到如下一些有趣的特性：（1）一个N个点的变换，能够通过将原始表达 式分成两个部分来计算。（2）通过计算两个（N/2）个点的变换。得到 Feven(u)和Fodd(u)。（3）偶部与奇部之和得到F(u)的前(N/2)个值。（4）偶部与奇部之差得到F(u)的后(N/2)个值。且不需要额外的变换计算。第32页，共46页，2023年，2月20日，星期六3.4快速傅立叶变换归纳快速傅立叶变换的思想：1）通过计算两个单点的DFT，来计算两个点的DFT。2）通过计算两个双点的DFT，来计算四个点的DFT，…，以此类推。3）对于任何N=2n的DFT的计算，通过计算两个N/2点的DFT，来计算N个点的DFT。第33页，共46页，2023年，2月20日，星期六3.4快速傅立叶变换2.逆向FFT算法算法思想描述：用正向变换计算逆向变换。u=0,1,2,...N-1

x=0,1,2,...N-1

第34页，共46页，2023年，2月20日，星期六3.4快速傅立叶变换在离散逆向变换表达式两边同取共轭，并除Nu=0,1,2,...N-1

可以看出，上式的右端在形式上就是傅立叶正变换。因此，只要将F*(u)输入，用正向变换算法计算，得到1/Nf*(x)，取共轭并乘上N，即得到f(x)。

第35页，共46页，2023年，2月20日，星期六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),F(3),F(4),F(5),F(6),F(7)}

第36页，共46页，2023年，2月20日，星期六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)}

第37页，共46页，2023年，2月20日，星期六

{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),F8(5),F8(6),F8(7)}

第38页，共46页，2023年，2月20日，星期六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)第39页，共46页，2023年，2月20日，星期六3.4快速傅立叶变换2）计算顺序及地址增量地址+1 地址+2 地址+4f(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)

第40页，共46页，2023年，2月20日，星期六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(