图像检测-10频域变换.

第十章图像的频域变换本章要点:二维离散Fourier变换快速Fourier变换（FFT）二维Fourier变换的应用•人类视觉所感受到的是在空间域和时间域的信号。•但是，往往许多问题在频域中讨论时，有其非常方便分析的一面。例如，空间位置上的变化不改变信号的频域特性。问题的提出：10.1二维离散Fourier变换1010)(2),(),(MxNyjNyvMxueyxfvuF正变换：,)))fTfTfxy列行（（（,)))fTfTfxy列行（（（注：这里给出的一维正变换的系数为1。•二维Fourier变换可以转化为两次一维Fourier变换。101022}),({MxNyjjMxuNyveeyxf1010)(2),(1),(MuNvjNyvMxuevuFMNyxf反变换：注：逆变换的系数不为1。))),(((111vuFfTfTMN列行))),(((111vuFfTfTMN行列•因为Fourier变换是一种正交变换，所以其正、反变换的系数可以有几种表示形式。•按照严格意义上的正交变换，正、反变换的系数相等，为：1MN•按照计算方便的角度，正、反变换的系数可以按照前面的方式给出，并且正、反变换的系数可以互换。Fourier变换有两个好处：1）可以得出信号在各个频率点上的强度。2）可以将卷积运算化为乘积运算。10.2快速Fourier变换（FFT）•快速Fourier变换的提出，是为了减少计算量。•基本思想是，找出Fourier变换中的数据变化规律，按照其规律整理出适合计算机运算的逻辑结构。10.2.1FFT的推导M0)exp(2NxxNjw令：xNNxwxfF10)()(：则/21/212(21)00[(2)(21)]NNxxNNxxfxwfxw11200[(2)(21)]MMxxNMMNxxMfxwfxww)]()([)(oNeFwFF（分成奇数项和偶数项之和）xMMxNxNxxNwjjjw)exp()exp()exp(2/22222（又可分成奇数项和偶数项之和）()eF10(2)MxMxfxw11200[(2(2))(2(21))]LLxxMLLMxxLfxwfxww)]()([)()2()2(oMeeFwFF()F[()()]eNoFwF==(2)(2)[()()]eeeMoFwF==(2)(2)[()()]ooeMoFwF=…………•FFT的数据变换规律之一是：1)可以不断分成奇数项与偶数项之加权和。2)奇数项、偶数项可分层分类。)()()(MFwMFMFoMNe)()(oMNeFwF)exp(2NMNMNNMNjNNwjw)exp()()()(oNeFwFMF•至此，计算量可减少近一半。1)2exp()2exp()2()(10jxMMxj其中：10.2.2FFT的设计思想•首先，将原函数分为奇数项和偶数项，通过不断的一个奇数一个偶数的相加（减），最终得到需要的结果。•也就是说FFT是将复杂的运算变成两个数相加（减）的简单运算的重复。10.2.3FFT算法1.先将数据进行奇、偶分组。01234567,,,,,,,,ffffffff89101112131415,,,,,,,ffffffff例：02468101214,,,,,,,,ffffffff13579111315,,,,,,,ffffffff下标为2x下标为2x+1偶数部分：奇数部分：0000，0010，0100，0110，1000，1010，1100，11100001，0011，0101，0111，1001，1011，1101，111102468101214,,,,,,,,ffffffff13579111315,,,,,,,ffffffff下标用二进制数表示为：下标用二进制数表示为：二进制数为：0000，0010，0100，0110，1000，1010，1100，1110第一层下标为：0246810121402461357/2*2第一层下标分组为：0，4，8，12；2，6，10，142.对偶数部分进行分层分组排序移位：000，001，010，011，100，101，110，111偶数组：000，010，100，110奇数组：001，011，101，111二进制数为：0000，0100，1000，1100第二层下标为：048120213/4*4第二层下标分组为：0，8；4，12；移位：00，01，10，11偶数组：00，10奇数组：01，113.根据每层偶数组的排序方式，获得奇数组的排序方式。因为偶数项的系数为f(2x)，奇数项的系数为f(2x+1)所以由第二层偶数排序：0，8，4，12；可以得到第一层偶数排序为：0，8，4，12，2，10，6，14；再根据第一层的偶数排序，获得原始数据的排序为：0，8，4，12，2，10，6，14，1，9，5，13，3，11，7，1519513311715,,,,,,,ffffffff14610212480,,,,,,,ffffffff4.进行分层的奇、偶项相加。对第二层偶数排序：0，8，4，12；对上面的结果再进行相加运算：………8020)2()0(fwfFe8020)2()1(fwfFe12024)2()1(fwfFo12024)2()0(fwfFo)0()0()0()2(04)2()(oeeFwFF)1()1()1()2(14)2()(oeeFwFF)0()0()2()2(04)2()(oeeFwFF)1()1()3()2(14)2()(oeeFwFF10.2.4FFT算法图示0f8f(0)(3)0(1)(3)1FF(0)(2)(0)(2)01(0)(2)(0)(2)23,,FFFF(0)(1)(0)(1)(0)(1)(0)(1)0123(0)(1)(0)(1)(0)(1)(0)(1)4567,,,,,,,FFFFFFFF(4)(3)0(4)(3)1FF4f12f(2)(3)0(2)(3)1FF2f6f10f14f(6)(3)0(6)(3)1FF1f9f(1)(3)0(1)(3)1FF5f13f(5)(3)0(5)(3)1FF3f7f(3)(3)0(3)(3)1FF11f15f(7)(3)0(7)(3)1FF(2)(2)(2)(2)01(2)(2)(2)(2)23,,FFFF(1)(2)(1)(2)01(1)(2)(1)(2)23,,FFFF(3)(2)(3)(2)01(3)(2)(3)(2)23,,FFFF(1)(1)(1)(1)(1)(1)(1)(1)0123(1)(1)(1)(1)(1)(1)(1)(1)4567,,,,,,,FFFFFFFF01234567,,,,,,,FFFFFFFF89101112131415(,,,,,,,)FFFFFFFF10.2.5FFT计算例设对一个函数进行快速Fourier变换，函数在采样点上的值设为：76543210,,,,,,,ffffffff偶数项部分：76543210,,,,,,,ffffffff0246,,,ffff下标值分别为：000，010，100，110排序为：000,100,010,110奇数项部分：1357,,,ffff下标值分别为：001，011，101，111排序为：001,101,011,111分成偶数、奇数为（偶数在左，奇数在右）：6420,,,ffff7531,,,ffff40,ff62,ff51,ff73,ff0f4f2f6f1f5f3f7f(0)(1)0(0)(1)1FF(2)(1)0(2)(1)1FF(1)(1)0(1)(1)1FF(3)(1)0(3)(1)1FF(0)(2)(0)(2)01(0)(2)(0)(2)23,,FFFF(1)(2)(1)(2)01(1)(2)(1)(2)23,,FFFF),,,(,,,,76543210FFFFFFFF按照前面叙述的FFT方法,第1层(4组2个点的运算)：(0)(1)0002404Ffwfff(0)(1)0102404Ffwfff同理：(2)(1)026Fff(2)(1)126Fff(1)(1)015Fff(1)(1)115Fff(3)(1)037Fff(3)(1)137Fff第2层（2组4个点的运算）：(0)(2)(0)(0(2)(1)00400426FFwFffff1)(0)(2)(0)(1)1(2)(1)1114104426()FFwFffwff同理：(0)(2)(0)(1)0(2)(1)22420426FFwFffff(0)(2)(0)(1)1(2)(1)1314104426()FFwFffwff(1)(2)(1)(1)0(3)(1)00401537FFwFffff(1)(2)(1)(1)0(3)(1)20401537FFwFffff(1)(2)(1)(1)1(3)(1)1114115437()FFwFffwff(1)(2)(1)(1)1(3)(1)1314115437()FFwFffwff第3层（1组8个点的运算）：(0)(2)0(1)(2)008004261357FFwFffffffff(0)(2)1(1)(2)111118104426815437[()][()]FFwFffwffwffwff(0)(2)2(1)(2)22282042681537)FFwFffffwffff（）（(0)(2)3(1)(2)131338304426815437[(][()]FFwFffwffwffwff）(0)(2)0(1)(2)408004261357FFwFffffffff(0)(2)1(1)(2)111518104426815437[()][()]FFwFffwffwffwff(0)(2)2(1)(2)26282042681537)FFwFffffwffff（）（(0)(2)3(1)(2)131738304426815437[(][()]FFwFffwffwffwff）10.3二维Fourier变换的应用•前面已经提到了Fourier变换有两个好处，即：可以获得信号的频域特性；可以将卷积运算转换为乘积运算。•因此二维Fourier变换的应用也是根据这两个特点来进行的。10.3.1在图像滤波中的应用•首先，我们来看Fourier变换后的图像，中间部分为低频部分，越靠外边频率越高。•因此，我们可以在Fourier变换图中，选择所需要的高频或是低频滤波。10.3.2在图像压缩中的应用•变换系数刚好表现的是各个频率点上的幅值。在小波变换没有提出时，用来进行压缩编码。•考虑到高频反映细节、低频反映景物概貌的特性。往往认为可将高频系数置为0，骗过人眼。10.3.3在卷积运算中的应用•从前面的图像处理算法中知道，如果抽象来看，其实都可以认为是图像信息经过了滤波器的滤波（如：平滑滤波、锐化滤波等）。•如果滤波器的结构比较复杂时，直接进行时域中的卷积运算是不可思议的。•Fourier变换可以卷积运算转换为点乘运算，由此简化运算，提高计算速度。)(SG)j,i(f)j,i(fgfgfg),(F),(G),(Fg)F(FFTfg1g10.3.4在图像分割中的应用相当于滤波,选择不同的频率段),v,u(F0)v,u(Fˆ其它或)0