本章主要内容离散傅立叶变换DFT快速傅立叶变换FFT.pdf

1第三章 图像变换 本章主要内容： ? 离散傅立叶变换DFT ? 快速傅立叶变换FFT ? 离散余弦变换DCT 21. DFT(离散傅立叶变换) 1.1 一维离散傅立叶变换 对一个连续函数等间隔采样可得到一个 离散序列。假设：共有N个采样点，则这个 离散序列可以表示为： 这时，可将该序列的傅立叶变换对定义为： ){ )1(,),2(),1(),0( ???? Nffff 31.1 一维离散傅立叶变换 正变换: u=0,1,…,N-1 逆变换： x=0,1,…,N-1 [ ]Nuxjxf N uF N x /2exp)(1)( 1 0 π?= ∑ ? = [ ] /2exp)()( 1 0 NuxjuFxf N u π∑ ? = = 41.1 一维离散傅立叶变换 在DFT变换中，f(x) 总是实函数，而F(u)是 复函数，我们可以把它写成： )()()( ujIuRuF += 51.1 一维离散傅立叶变换 或者写成极坐标的形式： 其中：幅度函数 称为f(x)的傅立叶频谱 称为相位角。 频谱的平方称为f(x)的功率谱或频谱密度，记为 P(u): ( )]ujuFuF Φ= exp[)()( ( ) ( )[ ]2122)( uIuRuF += ])( )(arctan[)( uR uIu =Φ )()()()( 222 uIuRuFuP +== 61.2 二维离散傅立叶变换 正方形网格采样得到的图像的2维傅立叶变换 为： u,v=0,1,…,N-1 x,y=0,1,…,N-1 ∑∑ ? = ? = +?= 1 0 1 0 )/)(2exp[),(1),( N x N y Nvyuxjyxf N vuF π ∑∑ ? = ? = += 1 0 1 0 )/)(2exp[),(1),( N u N v NvyuxjvuF N yxf π 71.2 二维离散傅立叶变换 f(x,y)与F(u,v)形成傅立叶变换对，即： 频谱： 相位角： ),(),( vuFyxf ? ( ) ( )[ ]21,,),( 22 ννν uIuRuF += ]),( ),(arctan[),( ν νν uR uIu =Φ 81.3 二维傅立叶变换的性质 1) 可分离的性质： 可以写成如下分离形式： ∑∑ ? = ? = +?= 1 0 1 0 )/)(2exp[),(1),( N x N y Nvyuxjyxf N vuF π ∑ ∑ ? = ? = ?? ? ?? ?? ?? ? ?? ??= 1 0 1 0 )2exp),(2exp1),( N x N y N vyjyxf N uxj N vuF ππ 91) 可分离的性质： 可以看出，2－D傅立叶变换可由连续两次 1－D傅立叶变换来实现。 令 v=0,1,…,N-1 u=0,1,…,N-1 ? ? ? ? ? ? ?= ∑ ? = 1 0 ]/2exp[),(1),( N y Nvyjyxf N NvxF π ∑ ?= ]/2exp[),(1),( NuxjvxFNvuF π 10 1) 可分离的性质： x y N-1 N-1 f(x,y) (0,0) x y N-1 N-1 F(x,v) (0,0) x y N-1 N-1 F(u,v) (0,0) 列变换 行变换 乘以N 11 2) 平移性质 傅立叶变换对的平移性质可表示为： 若： 则有： ),(),( vuFyxf ? ),(]/)(2exp[),( 0000 vvuuFNyvxujyxf ???+π ]/),(2exp[),(),( 0000 NvyuxjvuFyyxxf π???? 12 2) 平移性质 上式表明： （1）将f(x,y)与一个指数项相乘相当于把其变换 后的频域中心移动到新的位置； （2）将F(u,v)与一个指数项相乘相当于把其反变 换后的空域中心移动到新的位置； （3）f(x,y)的平移不影响其傅立叶变换的幅值。 13 3) 周期性 傅立叶变换和反变换均以N为周期，即： 尽管F(u,v)对无穷多个u和v的值重复出现，但 只需要根据一个周期的N个值就可以从F(u,v)得 到f(x,y)。 ),(),(),(),( NvNuFNvuFvNuFvuF ++=+=+= 14 4) 旋转性质 首先借助极坐标变换 x=rcosθ, y=rsinθ, u=wcosφ, v=wsinφ, 将f(x,y)和F(u,v)转换为f(r, θ)和F(w,φ)，将它们带入傅立叶变换可得： 上式表明，对f(x,y)旋转 θ0对应于将其傅 立叶变换F(u,v)也旋转θ0；类似对F(u,v)旋转 θ0对应于将其傅立叶反变换f(x,y)也旋转θ0。 ),(),( 00 θφθθ +?+ wFrf 15 5) 分配率 根据傅立叶变换对的定义可以得