1、图像的频域变换图像的频域变换n 人类视觉所感受到的是在空间域和时间域的人类视觉所感受到的是在空间域和时间域的信号。信号。n 但是，往往许多问题在频域中讨论时，有其但是，往往许多问题在频域中讨论时，有其非常方便分析的一面。例如，空间位置上的非常方便分析的一面。例如，空间位置上的变化不改变信号的频域特性。变化不改变信号的频域特性。问题的提出n 首先，提出的变换必须是有好处的，换句话首先，提出的变换必须是有好处的，换句话说，可以解决时域中解决不了的问题。说，可以解决时域中解决不了的问题。n 其次，变换必须是可逆的，可以通过逆变换其次，变换必须是可逆的，可以通过逆变换还原回原时域中。还原回原时域中。图
2、像变换的前提条件n二维离散傅立叶变换二维离散傅立叶变换n快速傅立叶变换快速傅立叶变换n二维离散傅立叶变换的应用二维离散傅立叶变换的应用n离散余弦变换离散余弦变换本章讨论的内容n 因为数字图像信号是二维的数字信号，所以因为数字图像信号是二维的数字信号，所以必须采用二维傅立叶变换才能够实现对图像必须采用二维傅立叶变换才能够实现对图像的频域变换。的频域变换。二维离散傅立叶变换二维离散Fourier变换 正变换1010)(2),(),(MxNyjNyMxeyxfF设图像大小为设图像大小为MM*N N，原图为，原图为f(x,yf(x,y)，其频谱，其频谱为为F(u,vF(u,v)，则：，则：112200
3、(,)yxuNMMNjjxyf x yee,)fTfTf x y列行（,)fTfTf x y列行（二维Fourier变换可以转化为两次一维Fourier变换。二维离散Fourier变换 反变换1010)(21),(),(MNjMNNyMxeFyxf111,)MNfTfTf x y行列（111,)MNfTfTf x y列行（f(x,yf(x,y)可以看成是一系列周期函数可以看成是一系列周期函数的线性组合的线性组合,F(u,v)可以看成是加权系数。可见可以看成是加权系数。可见u,v越大的部分越大的部分,影响影响f(x,y)细节部分细节部分)(2NyMxje二维离散Fourier变换 作用1 1）可
4、以得出）可以得出信号在各个频率点信号在各个频率点上的强度。上的强度。2 2）可以将卷积运算化为乘积运算。）可以将卷积运算化为乘积运算。快速Fourier变换（FFT）n 快速快速FourierFourier变换的提出，是为了减少计算量。变换的提出，是为了减少计算量。n基本思想是，找出基本思想是，找出FourierFourier变换中的数据变化规变换中的数据变化规 律，按照其规律整理出律，按照其规律整理出 适合计算机运算适合计算机运算 的逻辑的逻辑 结构。结构。FFT的推导 n 因为二维傅立叶变换可以转换成两次的一维傅立叶变换，所以，在这里我们只对一维快速傅立叶变换进行推导。FFT的推导 )ex
5、p(2NxxNj令：xNNxxfF10)()(：则（分成奇数项和偶数项之和）（分成奇数项和偶数项之和）M0)12(212/0212/0)12()2(xNNxxNNxxfxfNxMMxxMMxNMxfxf10102)12()2()()(oNeFFFFT的推导 （又可分成奇数项和偶数项之和）（又可分成奇数项和偶数项之和）(2)(2)()()eMoFw F10)2()(MxxMexfF单看偶数项:MxLLxxLLxMLxfxf10102)12(2()2(2(FFT的推导 ()F()()eNoFw F=(2)(2)()()eeeMoFw F=(2)(2)()()ooeMoFw F=u FFT的数据变换
6、规律之一是：1)可以不断分成奇数项与偶数项之加权和。2)奇数项、偶数项可分层分类。FFT的推导)()()(MFwMFMFoMNe)()(oMNeFwF)exp(2NMNMNNMNjwwwwNNwjw)exp()()()(oNeFwFMFu 至此，计算量可减少近一半。FFT的算法原理n首先，将原函数分为奇数项和偶数项，通过不首先，将原函数分为奇数项和偶数项，通过不断的一个奇数一个偶数的相加（减），最终得断的一个奇数一个偶数的相加（减），最终得到需要的结果。到需要的结果。n也就是说也就是说FFTFFT是是将复杂的运算将复杂的运算变成变成两个数相加两个数相加（减）的简单运算（减）的简单运算的重复。这
7、恰好符合计算机的重复。这恰好符合计算机计算所擅长的计算规律。计算所擅长的计算规律。FFT的算法步骤1.1.先将数据进行奇、偶分组先将数据进行奇、偶分组。01234567,ff ffffff89101112131415,ffffffff例：02468101214,ffffffff13579111315,f f f fffff下标为下标为2x2x下标为下标为2x+12x+1FFT算法步骤分析偶数部分的数据项：分析偶数部分的数据项：0000，0010，0100，0110，1000，1010，1100，1110024681 01 21 4,ffffffff如果下标用二进制数表示为：如果下标用二进制数表
8、示为：末尾一位是末尾一位是0 0。FFT算法步骤分析奇数部分的数据项：分析奇数部分的数据项：00010001，00110011，01010101，01110111，10011001，10111011，11011101，11111111135791 11 31 5,ffffffff如果下标用二进制数表示为：如果下标用二进制数表示为：末尾一位是末尾一位是1 1。FFT算法步骤二进制数为：二进制数为：00000 00 0，0010010 0，01010 00 0，0110110 0，10100 00 0，1011010 0，11110 00 0，1111110 0第一层下标为：第一层下标为：0 2
9、4 6 8 10 12 142.2.对偶数部分进行分层分组排序对偶数部分进行分层分组排序l 因为奇数部分的数据项排列规律为2x+1，所以只需要给出偶数项部分，奇数项部分则可以类推。FFT算法步骤二进制数为：二进制数为：00000 00 0，0010010 0，01010 00 0，0110110 0，10100 00 0，1011010 0，11110 00 0，1111110 00 2 4 6 1 3 5 7 /2*2第一层下标分组为：第一层下标分组为：0，4，8，12；2，6，10，14移位：移位：00000 0，001001，01010 0，011011，10100 0，101101，1
10、1110 0，111111偶数组：偶数组：00000 0，01010 0，10100 0，11110 0奇数组：奇数组：001001，011011，101101，111111FFT算法步骤二进制数为：二进制数为：00000 00 0，01010 00 0，10100 00 0，11110 00 0第二层下标为第二层下标为：0 4 8 120 21 3/4*4第二层下标分组为：第二层下标分组为：0，8；4，12；移位：移位：0000，0101，1010，1111偶数组：偶数组：0000，1010奇数组：奇数组：0101，1111FFT算法步骤3.3.根据每层偶数组的排序方式，获得奇数组的排根据每
11、层偶数组的排序方式，获得奇数组的排序方式。序方式。因为偶数项的系数为因为偶数项的系数为f(2x)f(2x)，奇数项的系数为，奇数项的系数为f(2x+1)f(2x+1)，所以由第二层偶数排序：所以由第二层偶数排序：可以得到第一层偶数排序为：可以得到第一层偶数排序为：0 0，8 8，4 4，1212；0 0，8 8，4 4，1212，2 2，6 6，1010，1414；FFT算法步骤再根据第一层的偶数排序：再根据第一层的偶数排序：获得奇数项的排序为：获得奇数项的排序为：1 1，9 9，5 5，1313，3 3，7 7，1111，15150 0，8 8，4 4，1212，2 2，6 6，1010，1
12、414；最后，获得原始数据的排序为：最后，获得原始数据的排序为：14106212480,ffffffff15117313591,ffffffffFFT算法步骤4.4.进行分层的奇、偶项相加。进行分层的奇、偶项相加。对排好序的数据项，进行第一层计算有：对排好序的数据项，进行第一层计算有：19513311715,f fffffff14610212480,ffffffff8020)0()0(ffFe8020)0()1(ffFe12024)1()0(ffFe12024)1()1(ffFe10022)2()0(ffFe10022)2()1(ffFe14026)3()0(ffFe14026)3()1(ff
13、Fe9021)0()0(ffFo9021)0()1(ffFo13025)1()0(ffFo13025)1()1(ffFo11023)2()0(ffFo11023)2()1(ffFo15027)3()0(ffFo15027)3()1(ffFo8 8个数一组个数一组8 8个数一组个数一组FFT算法步骤对得到的偶数数据项，进行第二层计算有：对得到的偶数数据项，进行第二层计算有：)0(),0(),0(),0()3()2()1()0(eeeeFFFF)1(),1(),1(),1()3()2()1()0(eeeeFFFF)0()0()0()1(04)0()2(eeeFFF)1()1()1()1(14)0(
14、)2(eeeFFF)0()0()2()1(04)0()2(eeeFFF)1()1()3()1(14)0()2(eeeFFF)0()0()0()2(04)2()(eeeoFFF)1()1()1()3(14)2()(eeeoFFF)0()0()2()3(04)2()(eeeoFFF)1()1()3()3(14)2()(eeeoFFF4 4个数一组个数一组4 4个数一组个数一组FFT算法步骤对得到的奇数数据项，进行第二层计算有：对得到的奇数数据项，进行第二层计算有：)0(),0(),0(),0()3()2()1()0(ooooFFFF)1(),1(),1(),1()3()2()1()0(ooooFF
15、FF)0()0()0()1(04)0()(oooeFFF)1()1()1()1(14)0()(oooeFFF)0()0()2()1(04)0()(oooeFFF)1()1()3()1(14)0()(oooeFFF)0()0()0()3(04)2()2(oooFFF)1()1()1()3(14)2()2(oooFFF)0()0()2()3(04)2()2(oooFFF)1()1()3()3(14)2()2(oooFFF4 4个数一组个数一组4 4个数一组个数一组FFT算法步骤对得到的偶数数据项，进行第三层计算有：对得到的偶数数据项，进行第三层计算有：)0(),0()()2(eoeFF)0()0(
16、)0()(08)2()3(eoeeFFF)0()0()4()(08)2()3(eoeeFFF)1(),1()()2(eoeFF)1()1()1()(18)2()3(eoeeFFF)1()1()5()(18)2()3(eoeeFFF)2(),2()()2(eoeFF)2()2()2()(28)2()3(eoeeFFF)2()2()6()(28)2()3(eoeeFFF)3(),3()()2(eoeFF)3()3()3()(38)2()3(eoeeFFF)3()3()7()(38)2()3(eoeeFFF两个数一组FFT算法步骤对得到的奇数数据项，进行第三层计算有：对得到的奇数数据项，进行第三层计
17、算有：)0(),0()2()(ooeFF)0()0()0()2(08)()3(ooeoFFF)0()0()4()2(08)()3(ooeoFFF)1(),1()2()(ooeFF)1()1()1()2(18)()3(ooeoFFF)1()1()5()2(18)()3(ooeoFFF)2(),2()2()(ooeFF)2()2()2()2(28)()3(ooeoFFF)2()2()6()2(28)()3(ooeoFFF)3(),3()2()(ooeFF)3()3()3()2(38)()3(ooeoFFF)3()3()7()2(38)()3(ooeoFFF两个数一组FFT算法步骤最后，将获得的所有
18、数据项进行合并：最后，将获得的所有数据项进行合并：)1()1()3(116)3(oeFF)0()0()3(016)3(oeFF)0(F)1(F)3()3()3(316)3(oeFF)2()2()3(216)3(oeFF)2(F)3(F)5()5()3(516)3(oeFF)4()4()3(416)3(oeFF)4(F)5(F)7()7()3(716)3(oeFF)6()6()3(616)3(oeFF)6(F)7(F)0()0()3(016)3(oeFF)8(F)1()1()3(116)3(oeFF)9(F)2()2()3(216)3(oeFF)10(F)3()3()3(316)3(oeFF)1
19、1(F)4()4()3(416)3(oeFF)12(F)5()5()3(516)3(oeFF)13(F)6()6()3(616)3(oeFF)14(F)7()7()3(716)3(oeFF)15(FFFT算法图示0f8f4f12f2f6f10f14f1f9f5f13f3f7f11f15f01234567,F F F F F F F F89101112131415(,)F F FFFFFF)0()0(eF)1()0(eF)0()1(eF)1()1(eF)0()2(eF)1()2(eF)0()3(eF)1()3(eF)0()0(oF)1()0(oF)0()1(oF)1()1(oF)0()2(oF)
20、1()2(oF)0()3(oF)1()3(oF)1(),0()3()3(eeFF)3(),2()3()3(eeFF)5(),4()3()3(eeFF)7(),6()3()3(eeFF)1(),0()2()2(eeFF)3(),2()2()2(eeFF)1(),0()()(oeoeFF)3(),2()()(oeoeFF)1(),0()()(eoeoFF)3(),2()()(eoeoFF),1(),0()3()3(ooFF)3(),2()3()3(ooFF),5(),4()3()3(ooFF)7(),6()3()3(ooFF)1(),0()2()2(ooFF)3(),2()2()2(ooFFFFT
21、计算例 设对一个函数进行快速设对一个函数进行快速FourierFourier变换，函数在采变换，函数在采样点上的值设为：样点上的值设为：76543210,ffffffff偶数项部分：偶数项部分：76543210,ffffffff0246,ffff下标值分别为：下标值分别为：000000，010010，100100，110110排序为：排序为：000,100,000,100,010,110010,110奇数项部分：奇数项部分：1357,f fff下标值分别为：下标值分别为：001001，011011，101101，111111排序为：排序为：001,101,001,101,011,111011,
22、111分成偶数、奇数为（偶数在左，奇数在右）：分成偶数、奇数为（偶数在左，奇数在右）：6420,ffff7531,ffff40,ff62,ff51,ff73,ff按照前面叙述的按照前面叙述的FFTFFT方法方法,第第1 1层层(4(4组组2 2个点的运算个点的运算)：404020)0()0(ffffFe404020)0()1(ffffFe626022)1()0(ffffFe626022)1()1(ffffFe515021)0()0(ffffFo515021)0()1(ffffFo737023)1()0(ffffFo737023)1()1(ffffFo偶数项部分奇数项部分第第2 2层偶数部分：层
23、偶数部分：6240)1(04)0()2()0()0()0(ffffFFFeee6240)1(04)0()2()0()0()2(ffffFFFeee)()1()1()1(621440)1(14)0()2(ffffFFFeee)()1()1()3(621440)1(14)0()2(ffffFFFeee第第2 2层奇数部分：层奇数部分：7351)1(04)0()2()0()0()0(ffffFFFooo7351)1(04)0()2()0()0()2(ffffFFFooo)()1()1()1(731451)1(14)0()2(ffffFFFooo)()1()1()3(731451)1(14)0()2(
24、ffffFFFeeo第第3 3层（层（1 1组组8 8个点的运算）：个点的运算）：73516240)2(08)2(0)0()0(ffffffffFFFoe)()()1()1(73145118621440)2(18)2(1ffffffffFFFoe)()2()2(7351146240)2(28)2(2ffffffffFFFoe)()()3()3(73145138621440)2(38)2(3ffffffffFFFoe73516240)2(08)2(4)0()0(ffffffffFFFoe)()()1()1(73145118621440)2(18)2(5ffffffffFFFoe)()2()2(7
25、351146240)2(28)2(6ffffffffFFFoe)()()3()3(73145138621440)2(38)2(3ffffffffFFFoe对函数：对函数：76543210,ffffffff按照定义，可得其按照定义，可得其FourierFourier变换为：变换为：708)()(xxwxfF下面，我们以下面，我们以F F3 3为例验证结果是否正确：为例验证结果是否正确：75835853813862822840ffffffff58168758483384888531812816862848288484080ffffffff)()()3()3(73145138621440)2(38)
26、2(3ffffffffFFFoe70383)()3(xxxfFF37873686358534843383328231813080ffffffff37873686358534843383328231813080ffffffff二维Fourier变换的应用n 前面已经提到了前面已经提到了FourierFourier变换有两个好处，即：变换有两个好处，即：可以获得信号的频域特性；可以将卷积运算可以获得信号的频域特性；可以将卷积运算转换为乘积运算。转换为乘积运算。n 因此二维因此二维FourierFourier变换的应用也是根据这两个变换的应用也是根据这两个特点来进行的。特点来进行的。二维Fourie
27、r变换的应用 用于图像滤波用于图像滤波n 图象图象 f f(x,yx,y)通过通过FourierFourier变换后得到变换后得到 F F(u,vu,v)=R=R(u,vu,v)+i I+i I(u,vu,v)n 图象图象f f(x,yx,y)的频谱的频谱,功率谱功率谱(功率密度功率密度),),相位谱相位谱:),(),(|),(|22vuIvuRvuF),(),(),(222vuIvuRvuF),(),(tan),(1vuRvuIvu二维Fourier变换的应用 用于图像滤波用于图像滤波n 首先，我们来看首先，我们来看FourierFourier变换变换后的图像，中间后的图像，中间部分为低频部
28、分，越靠外边频率越高。部分为低频部分，越靠外边频率越高。n 因此，我们可以在因此，我们可以在FourierFourier变换图中，选择所变换图中，选择所需要的需要的高频高频或是或是低频低频滤波。滤波。二维Fourier变换的应用 用于图像压缩用于图像压缩n 变换系数刚好表现的是各个频率点上的幅变换系数刚好表现的是各个频率点上的幅值。在小波变换没有提出时，用来进行压值。在小波变换没有提出时，用来进行压缩编码。缩编码。n 考虑到高频反映细节、低频反映景物概貌考虑到高频反映细节、低频反映景物概貌的特性。往往认为可将高频系数置为的特性。往往认为可将高频系数置为0 0，骗过人眼骗过人眼。二维Fourie
29、r变换的应用 用于计算卷积n 从前面的图像处理算法中知道，如果抽象来看，从前面的图像处理算法中知道，如果抽象来看，其实都可以认为是图像信息经过了滤波器的滤其实都可以认为是图像信息经过了滤波器的滤波（如：平滑滤波、锐化滤波等波（如：平滑滤波、锐化滤波等 ）。）。n 如果滤波器的结构比较复杂时，直接进行时域如果滤波器的结构比较复杂时，直接进行时域中的卷积运算是不可思议的。中的卷积运算是不可思议的。n FourierFourier变换可以卷积运算转换为点乘运算，由变换可以卷积运算转换为点乘运算，由此简化运算，提高计算速度。此简化运算，提高计算速度。)(SG),(jif),(jifgfgfg),(),
30、(),(FGFg)(1ggFFFTf离散余弦变换（DCT）问题的提出n FourierFourier变换的一个最大的问题是：它的参数都变换的一个最大的问题是：它的参数都是复数，在数据的描述上相当于实数的两倍。是复数，在数据的描述上相当于实数的两倍。n 为此，我们希望有一种能够达到相同功能但数为此，我们希望有一种能够达到相同功能但数据量又不大的变换。在此期望下，产生了据量又不大的变换。在此期望下，产生了DCTDCT变换。变换。离散余弦变换（DCT）正变换：1010222)1(2(cos)12(cos),()()(),(MxNyMNMNcyxyxfccF1010222)1(2(cos)12(cos
31、),()()(),(MNMNcMNyxFccyxf1)(21xc0 x1,.,2,1Nx逆变换：其中：其中：离散余弦变换（DCT）应用n 余弦变换实际上是利用了余弦变换实际上是利用了FourierFourier变换的实数变换的实数部分构成的变换。部分构成的变换。n 余弦变换主要用于图像的压缩，如目前的国余弦变换主要用于图像的压缩，如目前的国际压缩标准的际压缩标准的JPEGJPEG格式中就用到了格式中就用到了DCTDCT变变换。换。n 具体的做法与具体的做法与DFTDFT相似。即高频部分压缩多相似。即高频部分压缩多一些，低频部分压缩少一些。一些，低频部分压缩少一些。Fourier 变换示例图像的频率特性 Fourier变换的低通滤波示例Fourier变换的高通滤波示例基于Fourier变换的压缩示例另一幅图像效果另一幅图像效果压缩率为：1.7：1压缩率为：2.24：1压缩率为：3.3：1基于Fourier变换的压缩示例压缩率为：8.1：1压缩率为：10.77：1压缩率为：16.1：1
