第五章-基本图像变换

1、长安大学地测学院长安大学地测学院1/85第五章 基本图像变换v本章实质:频率域变换v重中之重:傅里叶变换长安大学地测学院长安大学地测学院2/85第5章 图象变换基础 为了有效和快速地对图象进行处理，常常 需要将原定义在图象空间的图象以某种形式转换到另外一些空间，并利用在这些空间的特有性质方便地进行一定的加工，最后再转换回图象空间以得到所需的效果。这些转换方法就是本章要着重介绍和讨论的图象变换技术 变换是双向的，或者说需要双向的变换。在图象处理中，一般将从图象空间向其他空间的变换称为正变换，而将从其他空间向图象空间的变换称为反变换或逆变换 长安大学地测学院长安大学地测学院3/85第5章 图象变换

2、基础5.1 可分离和正交图象变换5.2 傅里叶变换 5.3 沃尔什/哈达玛变换 5.4 离散余弦变换5.5 Radon变换长安大学地测学院长安大学地测学院4/855.1 可分离和正交图象变换v分离变换目的:简化计算,长安大学地测学院长安大学地测学院5/855.1 可分离和正交图象变换1-D可分离变换可分离变换正变换反变换 1 , , 1 , 0),()()(10NuuxhxfuTNx正向变换核1 , , 1 , 0),()()(10NxuxkuTxfNu反向变换核长安大学地测学院长安大学地测学院6/855.1 可分离和正交图象变换2-D可分离变换可分离变换（傅里叶变换是一个例子） 1010),

3、(),( ),(NxNyvuyxhyxfvuT 1010),(),( ),(NuNvvuyxkvuTyxf反向变换核正向变换核变换核与原始函数及变换后函数无关长安大学地测学院长安大学地测学院7/85可分离可分离1个2-D变换分成2个1-D变换对称对称 (h1与h2的函数形式一样),(),(),(21vyhuxhvuyxh),(),(),(11vyhuxhvuyxh102),(),(),(NyvyhyxfvxT101),(),(),(NxuxhvxTvuT5.1 可分离和正交图象变换长安大学地测学院长安大学地测学院8/85可分离且对称可分离且对称 AFAT BAFABBTB 图象矩阵对称变换矩阵

4、反变换矩阵变换结果BTBF BAFABF 1 AB1 AB5.1 可分离和正交图象变换反变换反变换完全恢复不完全恢复长安大学地测学院长安大学地测学院9/85正交正交考虑变换矩阵： 酉矩阵（*代表共轭 ）：如果A为实矩阵，且： 则A为正交矩阵，式(5.1.3)和式(5.1.4)构成正交变换对 BTBF 1 AB5.1 可分离和正交图象变换*1AAT1AA长安大学地测学院长安大学地测学院10/855.2傅里叶变换5.2.1 2-D傅里叶变换 5.2.2 傅里叶变换定理 5.2.3 快速傅里叶变换长安大学地测学院长安大学地测学院11/855.2傅里叶变换周期为 的周期函数用一系列三角函数 的和来表示

5、为:2)sin(0tnAn10)sin()(nnntnAAtf这种展开称为谐波分析。其中， 为直流分量， 为一次谐波（又做基波），而 依次称为二次谐波，三次谐波等等。0A)sin(11tA)2sin(22tA)3sin(33tA傅里叶级数（三角级数）傅里叶级数（三角级数）长安大学地测学院长安大学地测学院12/855.2 傅里叶变换若函数若函数 ( )f x以以2l为周期的光滑或分段光滑函数，即为为周期的光滑或分段光滑函数，即为(2 )( )f xlf x( )f x将将展开为傅里叶级数展开为傅里叶级数01( )(cossin)2kkkak xk xf xabll1( )cos()lnln xa

6、f xdxll1( )sin()lnln xbf xdxll0,1,2n 1,2,3n 长安大学地测学院长安大学地测学院13/855.2傅里叶变换欧拉公式欧拉公式:cossinixexix长安大学地测学院长安大学地测学院14/855.2 傅里叶变换01( )(cossin)kkkk xk xf xaablliiii1cos()21sin()2ixxxxxeexeei( )k xlkkf xC eii*11( ) d( )d22k xk xllllkllCf x exf x exll+复数形式的傅里叶级数长安大学地测学院长安大学地测学院15/855.2 傅里叶变换傅里叶展开的复数形式上式的物理意

7、义为上式的物理意义为: 一个周期为一个周期为2l 的函数的函数 ( )f x可以分解可以分解为频率为为频率为nl，复振幅为，复振幅为 nc的复简谐波的叠加的复简谐波的叠加 nl称为谱点，称为谱点，所有谱点的集合称为谱对于周期函数所有谱点的集合称为谱对于周期函数 ( )f x而言，谱是离散的而言，谱是离散的i( )k xlkkf xC e1( )2n xillklCf x edxl长安大学地测学院长安大学地测学院16/855.2 傅里叶变换傅里叶变换对(三种):ii1111( )( )d , ( )( )d22xxFf x exf xFeii221( )( )d , ( )( )d2xxFf x

8、 exf xFei2i233( )( )d , ( )( )dxxFf t exf xFe(1)(1)(2)(2)(3)(3)12311( )( )()222FFF三者之间的关系:长安大学地测学院长安大学地测学院17/855.2傅里叶变换傅里叶谱（频谱，幅度）傅里叶相位角傅里叶功率谱22 1/2|(*)| FRIarctanIR222(*) |(*)|PFRI长安大学地测学院长安大学地测学院18/855.2 傅里叶变换v傅立正反变换对是怎么确立的？假设非周期函数假设非周期函数 ( )f x是一个周期函数是一个周期函数 ( )g x的周期的周期 2l 时的极限情况。由此，时的极限情况。由此， (

9、 )g x的傅里叶级数展开式的傅里叶级数展开式01( )(cossin)kkkk xk xg xaabll在在 l 时的极限形式就是所要寻找的非周期函数时的极限形式就是所要寻找的非周期函数 ( )f x的傅里叶展开的傅里叶展开长安大学地测学院长安大学地测学院19/855.2傅里叶变换 设不连续的参量设不连续的参量 1 (0,1,2,), kkkkkkll则傅立叶级数写为：则傅立叶级数写为： 01( )(cossin)kkkkkg xaaxbx傅里叶系数为傅里叶系数为1( )cosd1( )sind lkklklkklaf xxxlbf xxxl2 (0)1 (0)kkk长安大学地测学院长安大学

10、地测学院20/855.2傅里叶变换 对于系数对于系数 0a，若，若 lim( )dlllf xx有限，则有限，则 01limlim( )d02llllaf xxl对于余弦部分：对于余弦部分：当当 ,0kll ，不连续参变量，不连续参变量 k变为变为 连续参量，以符号连续参量，以符号 代替对代替对 k的求和变为对连续参量的求和变为对连续参量 的积分。的积分。长安大学地测学院长安大学地测学院21/855.2傅里叶变换11001(cos)( )cosdcos1( )cosd cosd1( )cosd cosdlkklkkk xk xaf xxxlllk xf xxxkllf xxxx同理可得正弦部分

11、同理可得正弦部分01( )sind sindf xxxx长安大学地测学院长安大学地测学院22/855.2傅里叶变换若令若令1( )( )cosd1( )( )sindAf xxxBf xxx00( )( )cosd( )sindf xAxBx则傅里叶变换可表示为：长安大学地测学院长安大学地测学院23/855.2 傅里叶变换iiii1cos(), sin()22xxxxixeexee 由欧拉公式得：00( )( )cosd( )sindf xAxBxii0011( ) ( )i ( )d ( )i ( )d22xxf xABeABe0ii011( ) ( )i ( )d (|)i (|)d22x

12、xf xABeABei( )( )dxf xFe反变换反变换长安大学地测学院长安大学地测学院24/855.2.1 2-D傅里叶变换傅里叶变换 1-D正变换对1个连续函数 f (x) 等间隔采样20( )f x13101525450575685790 x10/j2exp)(1)()(NxNuxxfNuFxfF长安大学地测学院长安大学地测学院25/855.2.1 2-D傅里叶变换傅里叶变换 1-D反变换 变换表达频谱（幅度）相位角101/j2exp)()()(NuNuxuFxfuFF)( j exp )( )(j)()(uuFuIuRuF21 22)()( )( uIuRuF)()(arctan)

13、( uRuIu 长安大学地测学院长安大学地测学院26/855.2.1 2-D傅里叶变换傅里叶变换 二维傅里叶变换频谱（幅度）相位角功率谱 1010/ )(j2exp),( 1),(NuNvNvyuxvuFNyxf21 22 ),(),( ),( vuIvuRvuF),(),(arctan),(vuRvuIvu 1010/ )(j2exp),( 1),(NxNyNvyuxyxfNvuF),(),( ),( ),(222 vuIvuRvuFvuP长安大学地测学院长安大学地测学院27/855.2.1 2-D傅里叶变换傅里叶变换傅里叶频谱图，就是图像梯度的分布图。（实际上图像上某一点与邻域点差异的强弱

14、，即梯度的大小，也即该点的频率的大小 长安大学地测学院长安大学地测学院28/855.2.1 2-D傅里叶变换傅里叶变换v 频率域 由傅立叶变换和频率变量( u, v)定义的空间 基本性质（1）变化最慢的频率成分(u=0, v=0)对应一幅图像的平均灰度（2）低频（原点附近）对应图像灰度变化慢的像素（3）高频（远离原点）对应图像灰度变化快的像素长安大学地测学院长安大学地测学院29/855.2.1 2-D傅里叶变换傅里叶变换长安大学地测学院长安大学地测学院30/855.2.2 傅里叶变换定理傅里叶变换定理 0 0、分离性质、分离性质 1次2-D 2次1-D O(N 4)减为O(N 2) (0,0)

15、XV(0,0)XY(0,0)UV列变换乘以行变换f (x, y)F(x, v)F(u, v)N(N 1)(N 1)-(N 1)-(N 1)-(N 1)-(N 1)-10/xj2exp),(1),(NxNuvxFNvuF/exp),(=),(=101NyNvyj2yxfNNvxF长安大学地测学院长安大学地测学院31/851 1、平移定理、平移定理 ),(/ )(j2exp),(dvcuFNdycxyxf5.2.2 傅里叶变换定理傅里叶变换定理 )( ),(/ )()(j2exp),( 1/ )(j2exp/ )(j2exp),( 1/ )(j2exp),(10101010dvcuFNydvxcu

16、yxfNNvyuxNdycxyxfNNdycxyxfNxNyNxNy F),(),(vuFyxf长安大学地测学院长安大学地测学院32/855.2.2 傅里叶变换定理傅里叶变换定理2、旋转定理、旋转定理借助极坐标：cossinxryr00( ,)( ,)f rF 表明：表明：对 旋转 对应于将其傅里叶变换 也旋转。反之亦然。( , )f x y00( , )F x y长安大学地测学院长安大学地测学院33/855.2.2 傅里叶变换定理傅里叶变换定理v旋转定理示例旋转定理示例例5.2.3长安大学地测学院长安大学地测学院34/855.2.2 傅里叶变换定理傅里叶变换定理3、尺度定理(相似定理)( ,

17、 )( , )af x yaF u1(,)(,)|uf ax byFaba bu原函数在幅度方面变化导致对其傅里叶变换在幅度方面产生对应的尺度变化。u原函数在空间尺度方面的缩放导致对其傅立叶变换在频域方面的相反缩放。长安大学地测学院长安大学地测学院35/855.2.2 傅里叶变换定理傅里叶变换定理v尺度定理例5.2.4长安大学地测学院长安大学地测学院36/854 4、剪切定理、剪切定理（水平方向）纯剪切 （垂直方向）纯剪切 5.2.2 傅里叶变换定理傅里叶变换定理 byxxyy ),(),(buvuFybyxfxx ydxy),(),(vduuFydxxf图5.2.5 (a)与(b)长安大学地

18、测学院长安大学地测学院37/855 5、组合剪切定理、组合剪切定理平移旋转尺度 水平剪切 垂直剪切 5.2.2 傅里叶变换定理傅里叶变换定理 bdvbubddvuFbdydxbyxf1,111),(xx11db101b101d图5.2.5长安大学地测学院长安大学地测学院38/856 6、仿射定理、仿射定理u = (eu dv)/ 和和v = ( bu + av)/ 5.2.2 傅里叶变换定理傅里叶变换定理 bdaeedbavuebdavu长安大学地测学院长安大学地测学院39/857 7、卷积定理、卷积定理 2-D2-D ( , )( , )( , ) ( , )f x yg x yF u v

19、G u v( , ) ( , )( , )( , )f x y g x yF u vG u v5.2.2 傅里叶变换定理傅里叶变换定理 ( )( )( ) ( )f xg xF u G u( ) ( )( )( )f x g xF uG u-( , )( , ) ( , ) (,)d df x yg x yf p q g xp yqp q u两函数在空间的卷积与其傅立叶变换在频率域的乘积构成一对变换u两函数在空间的乘积与其傅里叶变换在频率域的卷积构成一对变换长安大学地测学院长安大学地测学院40/858 8、相关定理、相关定理互相关：f (x) 与g(x)不是同一个函数 自相关：f (x) =

20、g(x)2-D2-D5.2.2 傅里叶变换定理傅里叶变换定理 *( )( )( ) ()df xg xfz g xzz),(),(*),(),(vuGvuFyxgyxf),(),(),(),(*vuGvuFyxgyxf qpqypxgqpfyxgyxfdd),(),(),(),(长安大学地测学院长安大学地测学院41/855.2.3 快速傅里叶变换快速傅里叶变换直接进行一个N N的2-D傅里叶变换需要N4次复数乘法运算和N2(N2 1) 次复数加法运算1-D：复数乘法和加法的次数都正比于N2 快速傅里叶变换（FFT）： 将复数乘法和加法的次数减少为正比于N log2N 逐次加倍法：复数乘法次数由

21、N2减少为(N log2 N)/2 复数加法次数由N2减少为N log2 N 1 , , 1 , 0/j2exp)(1)()(10NuNuxxfNuFxfNxF长安大学地测学院长安大学地测学院42/855.2.3 快速傅里叶变换快速傅里叶变换 考察一维有限长序列x(n)(0=n=N-1)的傅立叶变换： 1, 1 ,0e1210NmnxNmXNmnjNn其中：10*110*010212)()1()()0()()(e,eNnnNnnNnmnNjNjWnxXWnxXWnxmXWW即有：则令或记为或记为Wn，Wn -1长安大学地测学院长安大学地测学院43/855.2.3 快速傅里叶变换快速傅里叶变换)

22、 1(.) 1 () 0 (.) 1(.) 1 () 0 () 1() 1(1) 1(0) 1() 1(11101) 1(01000NxxxWWWWWWWWWNXXXNNNNNN计算复杂性：一个频率分量需计算复杂性：一个频率分量需N次乘法次乘法，N-1-1次加法次加法 整个变换需整个变换需N2 2次乘法次乘法，N( (N-1)-1)次加法次加法矩阵表示矩阵表示：10)()(NnmnWnxmX长安大学地测学院长安大学地测学院44/855.2.3 快速傅里叶变换快速傅里叶变换为为周周期期是是以以，知知由由 2NWeWnmNj 结论：系数多数相同，且具有对称性结论：系数多数相同，且具有对称性mnNm

23、nmnNNNjNWWWWeW 222221 9630642032100000WWWWWWWWWWWWWWWW例：例：N=40213192604;WWWWWWWWWW ；对对称称性性：；周周期期性性： 1010000010100000WWWWWWWWWWWWWWWW最小无重最小无重复运算复运算0W2W3W1WN=4长安大学地测学院长安大学地测学院45/855.2.3 快速傅里叶变换快速傅里叶变换12/0212/011021)()()()()12, 1 ,0()12()()2()(:)(2NnmnNNnmnNNnmnNWnxWnxWnxmXNnnxnxnxnxnxN划分为为整数），现将序列（设)(

24、)()12()2()12()2(2112/02/12/02/12/0)12(12/0)2(mXWmXWWnxWnxWnxWnxmNmNNnmnNNnmnNNnnmNNnnmNmnNmNmnNjmNjmmnNjnmNmnNmnNjmnNjnmNWWeeeWWeeW2/2/22)2(2)12(2/2/222)2(N点的点的DFT转化转化为两个求为两个求N/2点的点的DFT 1965 1965年年，库利，库利- -图图基提出把基提出把原始的原始的N N点点序列依次序列依次分解成一分解成一系列短序系列短序列，减少列，减少乘法运算乘法运算长安大学地测学院长安大学地测学院46/85)3,2,1 ,0()(

25、)4();()4(4)()()7()7()7()6()6()6()5()5()5()4()4()4()3()3()3()2()2()2()1()1()1()0()0()0(8848822112127812681258124812381228121812081mWWWmXmXmXmXDFTmXmXXWXXXWXXXWXXXWXXXWXXXWXXXWXXXWXXNmmm的对称性有：的是周期为和又例子：)()()(21mXWmXmXmN5.2.3 快速傅里叶变换快速傅里叶变换长安大学地测学院长安大学地测学院47/85)3()3()7()2()2()6() 1 () 1 ()5()0()0()4()3

26、()3()3()2()2()2() 1 () 1 () 1 ()0()0()0(23812281218120812381228121812081XWXXXWXXXWXXXWXXXWXXXWXXXWXXXWXX则则有有： X1(0) X(0) 08W 08W X2(0) X(4) 蝶蝶形形运运算算单单元元 5.2.3 快速傅里叶变换快速傅里叶变换长安大学地测学院长安大学地测学院48/85X2(0)X2(1)X2(2)X2(3)08W18W28W38W-1-1-1-11111X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(

27、7)N/2点点DFTN/2点点DFTX1(0)X1(1)X1(3)X1(2) 3 () 3 () 7 () 2 () 2 () 6 () 1 () 1 () 5 () 0 () 0 () 4 () 3 () 3 () 3 () 2 () 2 () 2 () 1 () 1 () 1 () 0 () 0 () 0 (23812281218120812381228121812081XWXXXWXXXWXXXWXXXWXXXWXXXWXXXWXX5.2.3 快速傅里叶变换快速傅里叶变换长安大学地测学院长安大学地测学院49/85DFTMXmXmXmXmXWmXmXmXWmXmXNnnxnxnxnxNnn

28、xnxnxnxDFTmHmGmNmN点的点的都是都是、而而，同样奇偶分组，同样奇偶分组点的点的都是都是和和又又2)()()()()()()()()()() 14/,.,1 , 0() 12()()2()() 14/,.,1 , 0() 12()()2()(4)()(654362524231262514135.2.3 快速傅里叶变换快速傅里叶变换长安大学地测学院长安大学地测学院50/85 X5(0) X2 (0) X5 (1) X2 (1) X6 (0) X2 (2) X6 (1) X2 (3) X3(0) X1 (0) X3 (1) X1 (1) X4 (0) X1 (2) X4 (1) X1

29、 (3) ) 1 () 1 () 3 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0() 1 () 1 () 3 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(2)()()()(62852608526285260852428314083142831408316543XWXXXWXXXWXXXWXXXWXXXWXXXWXXXWXXDFTMXmXmXmX点点的的都都是是、而而5.2.3 快速傅里叶变换快速傅里叶变换长安大学地测学院长安大学地测学院51/85)6()2()1 ()6()2()0()4()0()1 ()4()0()0(2

30、84284083083xWxXxWxXxWxXxWxX)7()3()1 ()7()3()0()5()1 ()1 ()5()1 ()0(386386185185xWxXxWxXxWxXxWxX完整的蝶形图如下页：完整的蝶形图如下页：5.2.3 快速傅里叶变换快速傅里叶变换长安大学地测学院长安大学地测学院52/85)7()3()5() 1 ()6()2()4()0(xxxxxxxx ) 1 ()0() 1 ()0() 1 ()0() 1 ()0(66554433XXXXXXXX )3()2() 1 ()0()3()2() 1 ()0(22221111XXXXXXXX )7()6()5()4()3(

31、)2() 1 ()0(XXXXXXXX 5.2.3 快速傅里叶变换快速傅里叶变换长安大学地测学院长安大学地测学院53/85时间复杂性：Nlog2N注意：输出X(m)是以m从小到大排列，而输入序列x(n)不是以n从小到大排列。采用码位倒序法排序：将自然顺序数转换成二进制数，然后首尾位倒序，再转换成十进制数，那么十进制数就是输入序列中的位置。如：N=8X(3)的位置是：011110(6)5.2.3 快速傅里叶变换快速傅里叶变换长安大学地测学院长安大学地测学院54/85二维FFT 101021010210/210/2e ),(*1),(*e ),(1),(e )(*1)(*1e )()(NuNvNv

32、yuxjNuNvNvyuxjNuNuxjNuNuxjvuFNyxfvuFNyxfuFNxfNuFxf 逆逆FFT112 ()001122001( , )( , )e1( , )e( , )eux vyNNjNxyuxvyNNjjNNxyF u vf x yNF u vf x yNFFT根据可分离性有：二维变换用两次一维实现5.2.3 快速傅里叶变换快速傅里叶变换长安大学地测学院长安大学地测学院55/85v傅立叶变换注意的问题 两个缺点： (1)要进行复数运算，计算比较费时 实用中还采用如沃尔什(Walsh)变换等。 (2)很多图像的高频项衰减的很快，在频域不清楚。 解决方法：vuFvuD,1l

33、g,5.2.3 快速傅里叶变换快速傅里叶变换长安大学地测学院长安大学地测学院56/855.3沃尔什/哈达玛变换5.3.1 沃尔什变换 5.3.2 哈达玛变换 5.3.3 关于两种变换的讨论沃尔什和哈达码变换都是可分离和正交变换 长安大学地测学院长安大学地测学院57/855.3.1 沃尔什沃尔什变换变换正变换核正变换核N = 2nbk(z)： z 的二进制表达中的第 k 位如 n = 3对 z = 6（1102）有 b0(z) = 0，b1(z) = 1，b2(z) = 1对 z = 2（102）有 b0(z) = ?，b1(z) = ?，b2(z) = ? 10)( )(1) 1( 1),(n

34、iubxbiniNuxh长安大学地测学院长安大学地测学院58/855.3.1 沃尔什沃尔什变换变换N=4N=4和和8 8时的沃尔什变换核时的沃尔什变换核长安大学地测学院长安大学地测学院59/855.3.1 沃尔什沃尔什变换变换正变换正变换变换核组成的矩阵是一个对称矩阵 并且其行和列正交（反变换核与 正变换核只差1个常数1/N）反变换核反变换核反变换反变换1010)( )(1) 1( )(1)(NxniubxbinixfNuW10)( )(1) 1(),(niubxbiniuxk1010)( )(1) 1( )()(NuniubxbiniuWxf长安大学地测学院长安大学地测学院60/852-D沃

35、尔什变换正反 10)( )()( )(11) 1(1),(nivbybubxbiniiniNvuyxh 101010)( )()( )(11) 1( ),( 1),(NxNynivbybubxbiniiniyxfNvuW 101010)( )()( )(11) 1( ),( 1),(NuNvnivbybubxbiniinivuWNyxf5.3.1 沃尔什沃尔什变换变换10)( )()( )(11) 1(1),(nivbybubxbiniiniNvuyxk长安大学地测学院长安大学地测学院61/852-D沃尔什变换核：可分离且对称都可分成两步计算,每步计算用1D变换实现10)( )(10)( )(

36、111111) 1(1) 1(1),(),(),(),(),(nivbybniubxbiniiniNNvykuxkvyhuxhvuyxh5.3.1 沃尔什沃尔什变换变换111( )( )( )( )01( , , , )( 1)iniininb x buby bvik x y u vN 正变换核反变换核长安大学地测学院长安大学地测学院62/855.3.1 沃尔什沃尔什变换变换v沃尔什变换中,正向变换核与反向变换核只依赖于x,y,u,v，而与f(x,y)或W(u,v)的值无关。这些核可看一组基本函数，一旦图像尺寸确定，这些函数也就完全确定。N=4时的二维沃尔什变换图5.3.1长安大学地测学院长安

37、大学地测学院63/855.3.1 沃尔什沃尔什变换变换长安大学地测学院长安大学地测学院64/855.3.1 沃尔什沃尔什变换变换v离散傅里叶变换是浮点数的运算，因此计算量会比较大，而且浮点数运算产生的误差会比较大；v沃尔什变换矩阵的系数是1或是1，只需要使用加法即可实现，计算复杂度小；v离散傅立叶转换相当于把信号拆解成在不同频率的正弦函数与余弦函数的分量，而使用沃尔什转换相当于把信号拆解成在许多不同震荡频率的方波上，因此，除非所要分析的信号拥有类似方波组合的特性，否则沃尔什转换作频谱分析的效果会比使用离散傅立叶转换分析的效果要差，这是降低运算复杂度所要付出的代价。长安大学地测学院长安大学地测学

38、院65/855.3.1 沃尔什沃尔什变换变换沃尔什变换具有某种能量集中。而且沃尔什变换具有某种能量集中。而且原始数据中数字越是均匀分布，经变换后原始数据中数字越是均匀分布，经变换后的数据越集中于矩阵的边角上。因此沃尔的数据越集中于矩阵的边角上。因此沃尔什变换可以压缩图像信息。且变换比傅立什变换可以压缩图像信息。且变换比傅立叶变换快。叶变换快。长安大学地测学院长安大学地测学院66/85正变换核正变换核bk(z)：z 的二进制表达中的第 k 位指数上的求和以2为模正变换正变换10)( )( ) 1(1),(niiiubxbNuxh5.3.2 哈达玛哈达玛变换变换10)()( 10) 1)(1)(N

39、xubxbniiixfNuHN=8时，哈达玛变换核表5.3.2长安大学地测学院长安大学地测学院67/85反变换核反变换核反变换核与正变换核只差1个常数1/N反变换反变换用于正变换的算法也可用于反变换5.3.2 哈达玛哈达玛变换变换10)( )( ) 1(1),(niiiubxbNuxh10)( )( ) 1(),(niiiubxbuxk10)( )( 10) 1)()(NuubxbniiiuHxf长安大学地测学院长安大学地测学院68/852-D变换核变换核2-D变换对变换对5.3.2 哈达玛哈达玛变换变换10 )( )()( )( ) 1(1),(niiiiivbybubxbNvuyxh10

40、)( )()( )( ) 1(1),(niiiiivbybubxbNvuyxk 1010 )( )()( )( 10) 1)(,( 1),(NxNyvbybubxbniiiiiyxfNvuH 1010 )( )()( )( 10) 1)(,( 1),(NuNvvbybubxbniiiiivuHNyxf长安大学地测学院长安大学地测学院69/855.3.2 哈达玛哈达玛变换变换v二维哈达玛变换（正变换和反变换）都可分成两个步骤计算，每个步骤用一个1维变换实现。长安大学地测学院长安大学地测学院70/855.3.3 关于两种变换的讨论关于两种变换的讨论v两种变换核里的数值都是1和-1，但是在行列的秩序

41、上两者有所不同。（下页说明）v在绝大多数图像变换应用中，常混合使用沃尔什变换和哈达玛变换，所以被统称为“沃尔什哈达玛”变换，通常用来指两者中的任意一个。长安大学地测学院长安大学地测学院71/85 阶（序）阶（序）列中符号变换的次数表5.3.2中8列的序依次为0，7，3，4，1，6，2，5随 u 增加而序也增加 的哈达玛变换核10)( )( ) 1(1),(niiiupxbNuxg5.3.3 关于两种变换的讨论关于两种变换的讨论 )()()()()()()()(01121110ububupububupubupnnnn对比表5.3.2与表5.3.3长安大学地测学院长安大学地测学院72/85N =

42、8 时经过排序的1-D哈达玛变换核的值行和列都满足序单增的条件 ux012345670+1+2+3+4+5+6+7+5.3.3 关于两种变换的讨论关于两种变换的讨论长安大学地测学院长安大学地测学院73/85哈达玛矩阵的迭代方便地获得变换矩阵11112HNNNNNHHHHH2NNHA1AFAT 11111111111111114H5.3.3 关于两种变换的讨论关于两种变换的讨论同样适合于哈达玛反变换长安大学地测学院长安大学地测学院74/85沃尔什变换和哈达玛变换比较可分离且对称，正反变换核相同行列正交（即各行向量与各列向量的内积为0）沃尔什变换特点有快速算法（类似快速傅里叶变换）哈达玛变换特点有迭代性质5.3.3 关于两种变