05_第四章_傅立叶

第四章 图象变换,4.1 积分变换 4.2 连续傅立叶变换 4.3 离散傅立叶变换 4.4 快速傅立叶变换 4.5 二维离散傅立叶变换 4.6 正交变换的一般表示形式 4.7 其它离散正交变换 4.8 小波变换,傅立叶变换,4.1、积分变换 4.2、连续傅立叶变换 4.3、二维离散傅立叶变换 4.4、快速傅立叶变换,一维离散傅立叶变换(DFT),一维离散傅立叶变换公式为：,逆变换为：,二维离散傅立叶变换,对于二维离散傅立叶变换，其形式为：,逆变换为：,幅谱(频谱)、相谱：,傅立叶谱： |F(u,v)|= R2(u,v)+I2(u,v)1/2,相位: (u,v)= arctan(I(u,v)/R(u,v),图像矩阵 实数,频域矩阵 复数,幅度谱的屏幕显示,原图像,频域中的高频和低频与空间域的对应关系,二维离散傅立叶变换的性质,1. 线性性质：,2. 比例性质：,3. 可分离性：,4. 空间位移：,5. 频率位移：,图像中心化：,当u0=v0=N/2时，,平均值,平均值定义：,由傅立叶变换定义：,因此，f(x,y)的平均值与傅立叶变换系数的关系为：,频率位移性质,当图像在频率域时移动时需要用到频率位移性质：,图像中心化,把图像进行傅立叶变换后，往往要把中心移到u0=v0=N/2的位置上,平移性,FT,则：,即：,同理：,未移中的变换：,移中的变换：,能量集中于中心（示意图）,原图像f（x，y）,6. 周期性： F(u,v)=F(u+aN,v+bN), f(x,y)=f(x+aN,y+bN),7. 共轭对称性：,8. 旋转不变性：,9. 平均值：,旋转不变性,10. 卷积定理： f(x,y)*h(x,y) F(u,v)H(u,v) f(x,y)h(x,y) F(u,v)*H(u,v),11. 相关定理： 互相关：f(x,y)Og(x,y) F(u,v)G*(u,v) f(x,y)g*(x,y) F(u,v) OG(u,v) 自相关：f(x,y)Of(x,y) |F(u,v)|2 |f(x,y)|2 F(u,v) OF(u,v),12. 帕塞瓦定理（能量定理）：,若f1(x,y)=f2(x,y)=f(x,y)，则有：,可分离性,需要N 次复数乘法，N-1次复数加法。,因此总共需要N 2 次复数乘法，N(N-1)次复数加法。,1965年，Cooley和Tukey提出快速算法，算法时间复杂度为 N log2 N。,4.4 快速傅立叶变换,记,则有：,单位园表示：,设N=2m，f(x)的定义域分为偶数部分和奇数部分， 即f(2x)和f(2x+1),记为：,u = 0, 1, 2, , N/2-1,对于N=N/2, N/2, , N-1,由Fe(u)和Fo(u)的原式，它们以N/2为周期：,而由W的性质：,所以：,WNux的性质：,(1) 对称性：,(2) 周期性：,(3) 可分性：,FFT的核心思想是：,N=2M，M为正整数。基数2。若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2M,例 子,设一序列x(n)的长度为L=9,应加零补长为 N=24=16， 应补7个零值。,例子：求 N=23=8点FFT变换,将N=8DFT分解成2个4点DFT： 可知：时域上：x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上：X(0)X(3)，由X(k)给出 X(4)X(7),由X(k+N/2)给出,（1）先将8点的DFT分成4点DFT：,x1(r),x2(r),将N=8点分解成2个4点的DFT的信号流图,X(4)X(7) 同学们自已写,(a)N=8点的直接DFT运算量,N=8点的直接DFT的计算量为：N2次(64次）复数相乘,N(N-1)次(8(8-1)=56次)复数相加.共计120次。,比较直接计算N=8点DFT 与分解2个4点DFT的FFT运算量,求 一个蝶形结 需要的运算量,要运算一个蝶形结，需要一次乘法 ， 两次加法。,(b)用2个4点DFT来求N=8点的FFT所需的运算量,分解为两个N/2=4点的DFT的运算量,分解2个N/2点（4点）的DFT：,偶数 其复数相乘为 复数相加为,奇数 其复数相乘为 复数相加为,再将N/2点（4点）合成N点(8点)DFT时，需要进行N/2个蝶形运算,还需N/2次（4次）乘法及 次(8次）加法运算。,如何提高FFT