《数字图像处理-傅里叶变换.ppt》由会员分享，可在线阅读，更多相关《数字图像处理-傅里叶变换.ppt（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机学院计算机学院马殿富马殿富数字图像处理数字图像处理傅里叶变换傅里叶变换1768-1830 1计算机学院计算机学院变换问题的引入变换问题的引入 频率域 幅值与频率 空间域 灰度2计算机学院计算机学院数字图像正交变换数字图像正交变换傅里叶变换傅里叶变换沃尔什变换沃尔什变换哈达玛变换哈达玛变换离散余弦变换离散余弦变换K-LK-L变换变换小波变换小波变换3计算机学院计算机学院傅里叶变换傅里叶变换傅里叶变换是线性系统分析的一个有力傅里叶变换是线性系统分析的一个有力工具，它能够定量地分析诸如数字图像工具，它能够定量地分析诸如数字图像之类的数字化系统，把傅里叶变换的理之类的数字化系统，把傅里叶变换的理
2、论与物理解释相结合，将有利于解决大论与物理解释相结合，将有利于解决大多数图像处理问题。多数图像处理问题。4计算机学院计算机学院幅值幅值频率频率波形波形如何表示？如何表示？5计算机学院计算机学院一维基函数一维基函数二维基函数二维基函数欧拉公式欧拉公式6计算机学院计算机学院一维傅立叶变换定义一维傅立叶变换定义设设 x(n):x(0),x(1),x(N-1);x(n):x(0),x(1),x(N-1);X(m):X(0),X(1),X(N-1)X(m):X(0),X(1),X(N-1)是数字序列，是数字序列，则序列则序列x(n)x(n)的傅立叶变换生成序列的傅立叶变换生成序列X(m)X(m)表示如下
3、：表示如下：正变换正变换反变换反变换缩写缩写函数函数W W的周期为的周期为N N7计算机学院计算机学院x(n)x(n)是输入函数，是输入函数，X(m)X(m)是输出函是输出函数，数，N=8N=8函数函数W W周期为周期为N=8N=88计算机学院计算机学院二维傅立叶变换定义二维傅立叶变换定义图像矩阵图像矩阵实数实数频域矩阵频域矩阵复数复数9计算机学院计算机学院二维傅立叶变换定义二维傅立叶变换定义设设 f(x,y):f(0,0),f(0,1),f(0,N-1),f(x,y):f(0,0),f(0,1),f(0,N-1),f(1,0),f(1,1),f(1,N-1),f(1,0),f(1,1),f(
4、1,N-1),.f(N-1,0),f(N-1,1),f(N-1,N-1),f(N-1,0),f(N-1,1),f(N-1,N-1),是数字矩阵是数字矩阵1.1.F(u,v):F(u,v):1.1.f(x,y):f(0,0),f(0,1),f(0,N-1),f(x,y):f(0,0),f(0,1),f(0,N-1),2.2.f(1,0),f(1,1),f(1,N-1),f(1,0),f(1,1),f(1,N-1),3.3.4.4.f(N-1,0),f(N-1,1),f(N-1,N-1),f(N-1,0),f(N-1,1),f(N-1,N-1),是数字矩阵是数字矩阵2.2.则则f(x,y)f(x,
5、y)的傅立叶变换生成的傅立叶变换生成F(u,v)F(u,v)表示如下：表示如下：正变换正变换反变换反变换变换对变换对10计算机学院计算机学院二维傅立叶变换二维傅立叶变换傅立叶变换：傅立叶变换：F(u,v)=|F(u,v)|eF(u,v)=|F(u,v)|ej j(u,v)(u,v)傅立叶谱：傅立叶谱：|F(u,v)|=RF(u,v)|=R2 2(u,v)+I(u,v)+I2 2(u,v)(u,v)1/21/2相位相位 (u,v)=arctan(I(u,v)/R(u,v)u,v)=arctan(I(u,v)/R(u,v)能量谱能量谱:E=|F(u,v)|E=|F(u,v)|2 211计算机学院计
6、算机学院12计算机学院计算机学院二维傅立叶变换二维傅立叶变换傅立叶谱：傅立叶谱：|F(u,v)|=F(u,v)|=RR2 2(u,v)+I(u,v)+I2 2(u,v)(u,v)1/21/2相位相位:(u,v)=u,v)=arctanarctan(I(u,v)/R(u,v)(I(u,v)/R(u,v)13计算机学院计算机学院14计算机学院计算机学院15计算机学院计算机学院二维傅立叶变换示例二维傅立叶变换示例(1)(1)16计算机学院计算机学院二维傅立叶变换示例二维傅立叶变换示例(2)(2)17计算机学院计算机学院 18计算机学院计算机学院19计算机学院计算机学院20计算机学院计算机学院21计算
7、机学院计算机学院傅傅里里叶变换示例叶变换示例 22计算机学院计算机学院傅立叶变换示例傅立叶变换示例(1)(1)图像中的周期性噪声产生了变换中的尖峰信号图像中的周期性噪声产生了变换中的尖峰信号23计算机学院计算机学院幅值与相位幅值与相位24计算机学院计算机学院傅立叶变换示例傅立叶变换示例(2.1)(2.1)幅值谱幅值重构图像相位重构图像相位谱25计算机学院计算机学院傅里叶变换性质傅里叶变换性质1 1 可分离性可分离性二维傅里叶变换可二维傅里叶变换可以分离为一维傅里以分离为一维傅里叶变换处理叶变换处理26计算机学院计算机学院傅里叶变换性质傅里叶变换性质1 1 可分离性可分离性图像图像横向横向纵向纵
8、向27计算机学院计算机学院傅立叶变换性质傅立叶变换性质2 2 周期性周期性如果如果f(x,y)f(x,y)F(u,v),F(u,v),则则28计算机学院计算机学院傅立叶变换性质傅立叶变换性质3 3 平移性平移性29计算机学院计算机学院傅立叶变换性质傅立叶变换性质3 3 平移性平移性如果如果f(x,y)f(x,y)F(u,v),F(u,v),则则 f(x,y)expj2f(x,y)expj2(u(u0 0 x+vx+v0 0y)/Ny)/NF(u-uF(u-u0 0,v-v,v-v0 0)f(x-xf(x-x0 0,y-y,y-y0 0)F(u,v)exp-j2F(u,v)exp-j2(ux(u
9、x0 0+vy+vy0 0)/N)/Nu0=N/2 v0=N/2 expj2(u0 x+v0y)/N=expj2(N*x+N*y)/2*N=expj(x+y)=(-1)(x+y)f(x,y)*(-1)(x+y)F(u-u0,v-v0)30计算机学院计算机学院傅立叶变换性质傅立叶变换性质4 4 共轭对称性共轭对称性如果如果f(x,y)f(x,y)F(u,v),F*(-u,-v)F(u,v),F*(-u,-v)是共轭复数，则是共轭复数，则F(u,v)=FF(u,v)=F*(-u,-v)(-u,-v)|F(u,v)|=|F|F(u,v)|=|F*(-u,-v)|(-u,-v)|31计算机学院计算机学
10、院傅立叶变换性质傅立叶变换性质5 5 旋转旋转32计算机学院计算机学院33计算机学院计算机学院傅立叶变换性质傅立叶变换性质5 5 旋转旋转设设f(x,y)f(x,y)F(u,v),F(u,v),34计算机学院计算机学院傅立叶变换性质傅立叶变换性质6 6 线性线性如果如果f f1 1(x,y)(x,y)F F1 1(u,v),(u,v),f f2 2(x,y)(x,y)F F2 2(u,v),(u,v),则则 af1(x,y)+bf2(x,y)aF1(u,v)+bF2(u,v)35计算机学院计算机学院傅立叶变换性质傅立叶变换性质7 7 比例性比例性如果如果f(x,y)f(x,y)F(u,v),F
11、(u,v),则则36计算机学院计算机学院傅立叶变换性质傅立叶变换性质7 7 平均值平均值37计算机学院计算机学院傅立叶变换性质傅立叶变换性质拉普拉斯算子拉普拉斯算子如果如果f(x,y)f(x,y)F(u,v),F(u,v),并且并且 2 2f f(x,y)=(x,y)=2 2f(x,y)/f(x,y)/x x2 2+2 2f(x,y)/f(x,y)/y y2 2,则则 2 2f f(x,y)=-(2(x,y)=-(2)2 2(u(u2 2+v+v2 2)F(u,v)F(u,v)38计算机学院计算机学院卷积定义卷积定义一维卷积定义：一维卷积定义：二维卷积定义二维卷积定义：39计算机学院计算机学院
12、卷积示例卷积示例(1.1)(1.1)f(x)f(x)和和g(x)g(x)作卷积作卷积折叠折叠平移平移形成函数形成函数g(x-g(x-)40计算机学院计算机学院卷积示例卷积示例(1.2)(1.2)f(f()和和 g(x-g(x-)乘积乘积结果结果41计算机学院计算机学院卷积示例卷积示例(2)(2)函数函数f(x)f(x)冲激函数冲激函数g(x)g(x)f(x)*g(x)f(x)*g(x)，原样复制原样复制42计算机学院计算机学院卷积示例卷积示例(3)(3)折叠折叠平移平移乘积乘积43计算机学院计算机学院卷积定理卷积定理如果如果f(x,y)f(x,y)F(u,v),g(x,y)F(u,v),g(x
13、,y)G(u,v)G(u,v)则则f(x,y)*g(x,y)f(x,y)*g(x,y)F(u,v)G(u,v)F(u,v)G(u,v)许多图像变换是卷积运算许多图像变换是卷积运算在频域的乘积运算比在空域的卷积运算快，特别是在频域的乘积运算比在空域的卷积运算快，特别是有了快速傅立叶变换以后，效果更加明显。有了快速傅立叶变换以后，效果更加明显。44计算机学院计算机学院相关定义相关定义一维相关定义：一维相关定义：二维相关定义：二维相关定义：45计算机学院计算机学院相关定理相关定理如果如果f(x,y)f(x,y)F(u,v),g(x,y)F(u,v),g(x,y)G(u,v)G(u,v)则则f(x,y
14、)f(x,y)g(x,y)g(x,y)F(u,v)G F(u,v)G*(u,v)(u,v)相关主要应用于模板和原型匹配相关主要应用于模板和原型匹配给定一个未知图像和已知图像集之间求最紧密的匹给定一个未知图像和已知图像集之间求最紧密的匹配。其基本途径是求相关，然后取相关函数最大值。配。其基本途径是求相关，然后取相关函数最大值。46计算机学院计算机学院能量能量(Rayleigh)(Rayleigh)定理定理能量定义能量定义能量定理能量定理47计算机学院计算机学院快速傅立叶变换快速傅立叶变换(1)(1)18501850年，高斯给出了年，高斯给出了DFTDFT有效算法有效算法19421942年，丹尼尔
15、森证明了一个界长为年，丹尼尔森证明了一个界长为N N的傅立叶变换可以由两个界长为的傅立叶变换可以由两个界长为N/2N/2的的傅立叶变换表示。傅立叶变换表示。19641964年，库利年，库利-图基给出了快速傅立叶图基给出了快速傅立叶变换算法变换算法48计算机学院计算机学院快速傅立叶变换快速傅立叶变换(1)(1)计算复杂性：计算复杂性：N N乘法，乘法，N(N-1)N(N-1)加法加法49计算机学院计算机学院快速傅立叶变换快速傅立叶变换(2)(2)W W是周期为是周期为N N的周期函数的周期函数 W=cos(2W=cos(2/N)-j sin(2/N)-j sin(2/N)/N)W W(m+kN)
16、(n+lN)(m+kN)(n+lN)=W=Wmnmn50计算机学院计算机学院快速傅立叶变换快速傅立叶变换(3)(3)库利库利-图基给出了快速傅立叶变换算法图基给出了快速傅立叶变换算法x x1 1(n)=x(2n)n=0,1,(n)=x(2n)n=0,1,(N-1)/2(N-1)/2 x x2 2(n)=x(2n+1)n=0,1,(n)=x(2n+1)n=0,1,(N-1)/2(N-1)/251计算机学院计算机学院快速傅立叶变换快速傅立叶变换(4.1)(4.1)由傅立叶变换定义由傅立叶变换定义52计算机学院计算机学院快速傅立叶变换快速傅立叶变换(4.2)(4.2)因为因为因为周期性，所以对于所有
17、的m，有53计算机学院计算机学院快速傅立叶变换快速傅立叶变换(4.3)(4.3)乘法乘法经过一系列的分解2,4,8.N/2计算复杂性：N log2 N54计算机学院计算机学院快速傅立叶变换快速傅立叶变换5 5FFTFFT碟式流程图算法碟式流程图算法55计算机学院计算机学院快速傅立叶变换快速傅立叶变换6 6 FFT FFT碟式流程图算法碟式流程图算法迭代次数迭代次数r r确定确定对偶节点的计算对偶节点的计算加权系数加权系数 的计算的计算重新排序重新排序56计算机学院计算机学院FFTFFT碟式流程图算法碟式流程图算法(1)(1)迭代次数迭代次数r r确定确定 r=logr=log2 2 N N 注
18、意：数据类型转换注意：数据类型转换 57计算机学院计算机学院FFTFFT碟式流程图算法碟式流程图算法(2)(2)对偶节点的计算对偶节点的计算节点节点l l是迭代次数，是迭代次数，k k是流程图的行数是流程图的行数 的对偶节点是的对偶节点是58FFTFFT碟式流程图算法碟式流程图算法(3)(3)59计算机学院计算机学院FFTFFT碟式流程图算法碟式流程图算法(4)(4)加权系数加权系数 的计算：确定的计算：确定p p(1)(1)把把k k值写成值写成r r位二进制数位二进制数(2)(2)把这个二进制数右移把这个二进制数右移r-lr-l位位(3)(3)二进制数按比特位倒转二进制数按比特位倒转(4)
19、(4)倒转后的二进制数变为十进制数倒转后的二进制数变为十进制数60计算机学院计算机学院FFTFFT碟式流程图算法碟式流程图算法(5)(5)求求k=2,l=2,N=8k=2,l=2,N=8的加权系数的加权系数 的计算：的计算：确定确定p p(1)(1)把把k k值写成值写成r r位二进制数：位二进制数：010010(2)(2)把这个二进制数右移把这个二进制数右移r-l=1r-l=1位：位：001001(3)(3)二进制数按比特位倒转：二进制数按比特位倒转：100100(4)(4)倒转后的二进制数变为十进制数：倒转后的二进制数变为十进制数：4 461计算机学院计算机学院FFTFFT碟式流程图算法碟
20、式流程图算法(6)(6)如果节点如果节点x xl l(k)(k)的的 ，则则x xl l(k)(k)的的对对偶节点为偶节点为 。x xl l(k)=x(k)=xl-1l-1(k)+(k)+62计算机学院计算机学院FFTFFT碟式流程图算法碟式流程图算法(7)(7)重新排序重新排序(1)(1)将节点将节点x xl l(k)(k)的的k k变为二进制数变为二进制数 x xl l(k)=x(k)=xl l(k(kr-1r-1k kr-2r-2kk0 0)(2)(2)将将二进制数按比特位倒转二进制数按比特位倒转 x xl l(k)=x(k)=xl l(k(k0 0k k1 1kkr-1r-1)(3)(
21、3)将二进制数变为十进制数，即为重将二进制数变为十进制数，即为重新新 排序位置排序位置63计算机学院计算机学院FFTFFT碟式流程图算法碟式流程图算法(8)(8)x x3 3(0)(0)x x3 3(000)(000)x x3 3(000)(000)x x3 3(0)(0)x x3 3(1)(1)x x3 3(001)(001)x x3 3(100)(100)x x3 3(4)(4)x x3 3(2)(2)x x3 3(010)(010)x x3 3(010)(010)x x3 3(2)(2)x x3 3(3)(3)x x3 3(011)(011)x x3 3(110)(110)x x3 3(6)(6)x x3 3(5)(5)x x3 3(101)(101)x x3 3(101)(101)x x3 3(5)(5)x x3 3(6)(6)x x3 3(110)(110)x x3 3(011)(011)x x3 3(3)(3)x x3 3(7)(7)x x3 3(111)(111)x x3 3(111)(111)x x3 3(7)(7)64计算机学院计算机学院65