第四章图像的频域变换

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)

3、)，则：，则：112200( , )yxuNMMNjjxyf x yee , )fTfTf x y列行（, )fTfTf x y列行（ 二维Fourier变换可以转化为两次一维Fourier变换。二维离散Fourier变换 反变换1010)(21),(),(MNjMNNyMxeFyxf111, )MNfTfTf x y行列（111, )MNfTfTf x y列行（注：逆变换的系数不为注：逆变换的系数不为1 1。二维离散Fourier变换 变换公式系数说明n 因为因为FourierFourier变换是一种正交变换，所以其正、变换是一种正交变换，所以其正、反变换的系数可以有几种表示形式。反变换的系

4、数可以有几种表示形式。n 按照严格意义上的正交变换，正、反变换的系按照严格意义上的正交变换，正、反变换的系数相等，为：数相等，为：1MNn 按照计算方便的角度，正、反变换的系数可以按照计算方便的角度，正、反变换的系数可以按照前面的方式给出，并且正、反变换的系数可按照前面的方式给出，并且正、反变换的系数可以互换。以互换。二维离散Fourier变换 作用1 1）可以得出）可以得出信号在各个频率点信号在各个频率点上的强度。上的强度。2 2）可以将卷积运算化为乘积运算。）可以将卷积运算化为乘积运算。快速Fourier变换（FFT）n 快速快速FourierFourier变换的提出，是为了减少计算量。变

5、换的提出，是为了减少计算量。n基本思想是，找出基本思想是，找出FourierFourier变换中的数据变化规变换中的数据变化规 律，按照其规律整理出律，按照其规律整理出 适合计算机运算适合计算机运算 的逻辑的逻辑 结构。结构。FFT的推导 n 因为二维傅立叶变换可以转换成两次的一维傅立叶变换，所以，在这里我们只对一维快速傅立叶变换进行推导。FFT的推导 )exp(2NxxNj令：xNNxxfF10)()( ：则（分成奇数项和偶数项之和）（分成奇数项和偶数项之和）M0)12(212/0212/0) 12()2(xNNxxNNxxfxfNxMMxxMMxNMxfxf10102) 12()2()()

6、(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的数据变换规律之一是：1)可以不断分成奇数项与偶数项之加权和。2)奇数项、偶数项可分层分类。FFT的推导)()()(MFwMFMFoMNe)()(oMNeFwF)exp(2NMNMNNMNjwwwwNNwjw)exp

7、()()()(oNeFwFMFu 至此，计算量可减少近一半。FFT的算法原理n首先，将原函数分为奇数项和偶数项，通过不首先，将原函数分为奇数项和偶数项，通过不断的一个奇数一个偶数的相加（减），最终得断的一个奇数一个偶数的相加（减），最终得到需要的结果。到需要的结果。n也就是说也就是说FFTFFT是是将复杂的运算将复杂的运算变成变成两个数相加两个数相加（减）的简单运算（减）的简单运算的重复。这恰好符合计算机的重复。这恰好符合计算机计算所擅长的计算规律。计算所擅长的计算规律。FFT的算法步骤1. 1. 先将数据进行奇、偶分组先将数据进行奇、偶分组。01234567, ,ff ffffff89101

8、112131415,ffffffff例：02468101214,ffffffff f f fffff下标为下标为2x2x下标为下标为2x+12x+1FFT算法步骤分析偶数部分的数据项：分析偶数部分的数据项：0000，0010，0100，0110，1000，1010，1100，1110024681 01 21 4,ffffffff如果下标用二进制数表示为：如果下标用二进制数表示为：末尾一位是末尾一位是0 0。FFT算法步骤分析奇数部分的数据项：分析奇数部分的数据项：00010001，00110011，01010101，01110111，10011001，10111011

9、，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 4 6 8 10 12 142. 2. 对偶数部分进行分层分组排序对偶数部分进行分层分组排序l 因为奇数部分的数据项排列规律为2x+1，所以只需要给出偶数项部分，奇数项部分则可以类推。FFT算法步

10、骤二进制数为：二进制数为：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，11110 0，111111偶数组：偶数组：00000 0，01010 0，10100 0，11110 0奇数组：奇数组：001001，011011，101101，111111FFT算法步

11、骤二进制数为：二进制数为： 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. 根据每层偶数组的排序方式，获得奇数组的排根据每层偶数组的排序方式，获得奇数组的排序方式。序方式。因为偶数项的系数为因为偶数项的系数为f(2x)f(2x)，奇数项的系数为，奇数项的系数为f(2x+1)f(2x+1)

12、，所以由第二层偶数排序：所以由第二层偶数排序：可以得到第一层偶数排序为：可以得到第一层偶数排序为：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，1414；最后，获得原始数据的排序为：最后，获得原始数据的排序为fffffffffffffffFFT算法步骤

13、4. 4. 进行分层的奇、偶项相加。进行分层的奇、偶项相加。对排好序的数据项，进行第一层计算有：对排好序的数据项，进行第一层计算有： 19513311715,f ffffffffffffff8020)0()0(ffFe8020)0() 1 (ffFe12024)1()0(ffFe12024)1() 1 (ffFe10022)2()0(ffFe10022)2() 1 (ffFe14026)3()0(ffFe14026)3() 1 (ffFe9021)0()0(ffFo9021)0() 1 (ffFo13025)1()0(ffFo13025)1() 1 (ffFo1102

14、3)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()2(eeeFFF)0()0()2()1(04)0()2(eeeFFF) 1 () 1 ()3(

15、)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(ooooFFFF)0()0()0()1(04)0()(oooeFF

16、F) 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()0()(

17、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算法步骤对得到的奇数数据项，进行第三层计算有：对得到的奇数数据

18、项，进行第三层计算有： )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(ooeoFF

19、F两个数一组FFT算法步骤最后，将获得的所有数据项进行合并：最后，将获得的所有数据项进行合并： ) 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(21

20、6)3(oeFF)10(F)3()3()3(316)3(oeFF)11(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(e

21、F)0()0(oF) 1 ()0(oF)0()1(oF) 1 ()1(oF)0()2(oF) 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

22、(ooFF)7(),6()3()3(ooFF) 1 (),0()2()2(ooFF)3(),2()2()2(ooFFFFT计算例 设对一个函数进行快速设对一个函数进行快速FourierFourier变换，函数在采变换，函数在采样点上的值设为：样点上的值设为：76543210,ffffffff偶数项部分：偶数项部分：76543210,ffffffff0246,ffff下标值分别为：下标值分别为：000000，010010，100100，110110排序为：排序为： 000, 100,000, 100, 010, 110010, 110奇数项部分：奇数项部分：1357,f fff下标值分别为：下标

23、值分别为：001001，011011，101101，111111排序为：排序为： 001, 101,001, 101, 011, 111011, 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(

24、)0(ffffFo515021)0() 1 (ffffFo737023)1()0(ffffFo737023)1() 1 (ffffFo偶数项部分奇数项部分第第2 2层偶数部分：层偶数部分：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(ffffFFFooo

25、7351)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(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(731451386214

26、40)2(38)2(3ffffffffFFFoe73516240)2(08)2(4)0()0(ffffffffFFFoe)()() 1 () 1 (73145118621440)2(18)2(5ffffffffFFFoe)()2()2(7351146240)2(28)2(6ffffffffFFFoe)()()3()3(73145138621440)2(38)2(3ffffffffFFFoe对函数：对函数：76543210,ffffffff按照定义，可得其按照定义，可得其FourierFourier变换为：变换为：708)()(xxwxfF下面，我们以下面，我们以F F3 3为例验证结果是否正确

27、：为例验证结果是否正确：75835853813862822840ffffffff58168758483384888531812816862848288484080ffffffff)()()3()3(73145138621440)2(38)2(3ffffffffFFFoe70383)()3(xxxfFF37873686358534843383328231813080ffffffff37873686358534843383328231813080ffffffff二维Fourier变换的应用n 前面已经提到了前面已经提到了FourierFourier变换有两个好处，即：变换有两个好处，即：可以获得信

28、号的频域特性；可以将卷积运算可以获得信号的频域特性；可以将卷积运算转换为乘积运算。转换为乘积运算。n 因此二维因此二维FourierFourier变换的应用也是根据这两个变换的应用也是根据这两个特点来进行的。特点来进行的。二维Fourier变换的应用 用于图像滤波用于图像滤波n 首先，我们来看首先，我们来看FourierFourier变换变换后的图像，中后的图像，中间部分为低频部分，越靠外边频率越高。间部分为低频部分，越靠外边频率越高。n 因此，我们可以在因此，我们可以在FourierFourier变换图中，选择变换图中，选择所需要的所需要的高频高频或是或是低频低频滤波。滤波。二维Fourier变换的应用 用于图像压缩用于图像压缩n 变换系数刚好表现的是各个频率点上的幅变换系数刚好表现的是各个频率点上的幅值。在小波变换没有提出时，用来进行压值。在小波变换没有提出时，用来进行压缩编码。缩编码。n 考虑到高频反映细节、低频反映景物概貌考虑到高频反映细节、低频反映景物概貌的特性。往往认为可将高频系数置为的特性。往往认为可将高频系数置为0 0，骗过人眼骗过人眼。二维Fourier变换的应用 用于计算卷积n 从前面的图像处理算法中知道，如果抽象来看，从前面的图像处理算法中知道，如果抽象来看，其实都可以认为是图像信息经过了滤波器的滤其实都可以认为是图像信息经过了滤波