第3章_图像处理中的正交变换第三讲

数字图像处理第2章图像处理中的正交变换（第三讲）3.3沃尔什变换离散傅里叶变换和余弦变换在快速算法中都要用到复数乘法，占用的时间仍然比较多。在某些应用领域中，需要更为便利更为有效的变换方法。沃尔什变换就是其中的一种。沃尔什函数是在1923年由美国数学家沃尔什(J.L.Walsh)提出来的。在沃尔什的原始论文中，给出了沃尔什函数的递推公式，这个公式是按照函数的序数由正交区间内过零点平均数来定义的。这种规定函数序数的方法也被波兰数学家卡兹马兹(S.Kaczmarz)采用了，所以，通常将这种规定函数序数的方法称为：沃尔什－卡兹马兹(Walshi-Kaczmarz)定序法。1931年美国数学家佩利(R.E.A.C.Paley)又给沃尔什函数提出了一个新的定义。他指出，沃尔什函数可以用有限个拉德梅克(Rademacher)函数的乘积来表示。这样得到的函数的序数与沃尔什得到的函数的序数完全不同。这种定序方法是用二进制来定序的，所以称为：二进制序数或自然序数。利用只包含＋1和－1阵元的正交矩阵可以将沃尔什函数表示为矩阵形式。早在1867年，英国数学家希尔威斯特(J.J.Sylvester)已经研究过这种矩阵。后来，法国数学家哈达玛(M.Hadamard)在1893年将这种矩阵加以普遍化，建立了所谓哈达玛矩阵。利用克罗内克乘积算子(KroneckerProductOperator)不难把沃尔什函数表示为哈达玛矩阵形式。利用这种形式定义的沃尔什函数称为克罗内克序数。这就是沃尔什函数的第三种定序法。由上述历史可见，沃尔什函数及其有关函数的数学基础早已奠定了。但是，这些函数在工程中得到应用却是近几十年的事情。主要原因是由于半导体器件和计算机在近几十年得到迅速发展，它们的发展为沃尔什函数的实用解决了手段问题，因此，也使沃尔什函数得到了进一步发展。与傅里叶变换相比，沃尔什变换的主要优点在于存储空间少和运算速度高，这一点对图像处理来说是至关重要的，特别是在大量数据需要进行实时处理时，沃尔什函数就更加显示出它的优越性。3.3.1拉德梅克函数拉德梅克(Rademacher)函数集是一个不完备的正交函数集，由它可以构成完备的沃尔什函数。拉德梅克函数包括n和t两个自变量，用R(n,t)来表示拉德梅克函数。它可用下式来表示)2sgn(sin),(ttnRn(3—100)0011)sgn(xxx当x=0时，sgn(x)无定义。(3—101)由sin函数的周期性知道R(n,t)也是周期性函数。由式(3—100)可见，当n=1时，R(n,t)的周期为1；当n=2时，R(2,t)的周期为1/2；当n=3时，R(3,t)的周期为；221一般情况下可用下式表示,2,121,),(1ntnRtnRn(3—102)拉德梅克函数的波形如图3—9所示。R(0,t)10tR(1,t)ttR(2,t)tR(3,t)tR(4,t)图3—9拉德梅克函数10-110-110-110-1由图3—9可见，拉德梅克函数有如下一些规律：（１）R(n,t)的取值只有+1和-1。（２）R(n,t)是R(n-1,t)的二倍频。因此，如果已知最高次数m=n，则其他拉德梅克函数可由脉冲分频器来产生。（３）如果已知n，那么,R(n,t)有个周期，其中0t1；（4）如果在处作取样，则可得到一数据序列R(n,k)，。每一取样序列将与下述矩阵相对应。这里我们取n=3，k=0,1,2,......7。12nnkt22112,,2,1,0kn11111111111111111111111111111111),3(),2(),1(),0(kRkRkRkR(3—103)采用上述离散矩阵形式就可以用计算机进行灵活处理。3.3.2沃尔什函数沃尔什函数系是完备的正交函数系，其值也是只取＋1和－1。从排列次序来定义不外乎三种：第一种是按沃尔什排列或称按列率排列来定义；第二种是按佩利排列定义；(自然序数）第三种是按哈达玛排列来定义。（第三定序法）3．3．1按沃尔什排列的沃尔什函数按沃尔什排列的沃尔什函数用来表示。函数波形如图3—10所示。按沃尔什排列的沃尔什函数实际上就是按列率排列的沃尔什函数。walitW(,)10),0(tWalwt10-1t),1(tWalw1110-1t1),2(tWalw10-1t1),3(tWalw10-1t1),4(tWalw10-1t1),5(tWalw10-1t1),6(tWalw10-1t1),7(tWalw图3—10按沃尔什排列的沃尔什函数从波形上可总结出如下规律：（1）在中，i就是波形在正交区间的变号次数；如：变号次数为0；变号次数为1；变号次数为2；walitW(,)),0(twalW),1(twalW),2(twalW（2）列率：通常把正交区间内波形变号次数的二分之一称为列率(sequency)。如果令i为波形在正交区间内的变号次数，那么，按照i为奇数或偶数，函数的列率将分别由下式来决定walitW(,)eveniioddiiiSi22100（3）按沃尔什排列的沃尔什函数可由拉德梅克函数构成，它的表达式如下}1,0{)(),1(),()(10kigpkWigtkRtiwalk(3—105)式中R(k+1,t)是拉德梅克函数，g(i)是为i的格雷码，是此格雷码的第k位数字，p为正整数。gik()一个正整数可以编成自然二进码，但也可以编成格雷码。格雷码也称为反射码。格雷码的特点是：两个相邻数的格雷码只有一个码位的值不同。例如：2的格雷码是(0011)，3的格雷码为(0010)。这两个相邻的数字的格雷码只有第四个码位的值不同。在脉冲编码技术中，常常采用这种码，以便得到较好的误差特性。一个正整数的自然二进码和格雷码之间是可以互相转换的。从自然二进码转成格雷码的方法如下：设一个十进制数的自然二进码为：Bkppnnnnnnn01221并设该数的格雷为：Gkppggggggg01221其中和分别为自然二进码和格雷码内的码位数字，并且、。它们之间的关系可用式(3—106)表示nkgkgk{,}01nk010121k1kk3p2p3p2p1p2p1p1pnngnngnngnngnngng(3—106)式中代表模２加。模2加的规律：1⊕1＝01⊕0＝10⊕1＝10⊕0＝0例：试求（2）的格雷码，P=4。解：Bn)0010()2(其中：01000123nnnngn330gnn232000gnn121011gnn010101其格雷码(2)(0011)Gg同理，若Bn)0011()3(则其格雷码为gg)0010()3(在格雷码中，有如下关系存在：gmgngmn()()()(3—107)例：设：2(0010)3(0011)(2)(0011)(3)(0010)BBGGmngg则gg()()()230001而)0001()3()2(BB所以：ggg()()()2323从正整数的格雷码也可以求出该十进数的自然二进码。其转换方法如下：设正整数的格雷码为：123210()()pppkGnggggggg又设其自然二进码为：)()(012321nnnnnnnnBkppp012321012321123212321321321211ggggggngggggnggggnggggngggnggngnpppppppppkpppkppppppppp则(3—108)例：n的格雷码为1011，求其自然二进码表示。由给定的格雷码可知：)1011()(gn其中：gggg32101011以上便是格雷码的定义及格雷码与自然二进码之间的转换方法。即：自然二进码为B)1101(ngnggngggngggg332321321032101101101010111所以：例：用公式(3—105)求p=4时的。waltw(,)5解：因为i=5，所以5的自然二进码为(0101)。由前面所述的转换规则可得到格雷码为(0111)。因此，有下面的对应关系(0111)↑↑↑↑第3位第2位第1位第0位g()53g()52g()51g()50即gggg(),()(),()515151500123代入式(3—105)得kigpkWtkRtiwal)(10),1(),(),3(),2(),1(),4(),3(),2(),1(),5(0111tRtRtRtRtRtRtRtwalw3．3．2按佩利排列的沃尔什函数用来表示按佩利排列的沃尔什函数，其波形如图3—11所示。),(tiwalp),0(tWalp1010-11t),1(tWalp),2(tWalp10-11t10-11t),3(tWalp10-11t),4(tWalp10-11t),5(tWalp10-11t),6(tWalp10-11t),7(tWalp图3—11按佩利排列的沃尔什函数t按佩利排列的沃尔什函数也可以由拉德梅克函数产生。其定义由式(3—111)表示kipkPtkRtiwal),1(),(10(3—111)式中是拉德梅克函数，),1(tkRBnniiiiii)()(01221ki是将函数序号写成自然二进码的第k位数字，。即：}1,0{ki例：p=3时，求),1(twalp因为i=1，所以自然二进码为：100第2位第1位第0位代入式(3—111)得：),1()],3([)],2([)],1([),1(),1(00120tRtRtRtRtkRtwalkikP例：p=3，求。waltp(,)5因为i=5，所以，自然二进码为(101)，代入式(3—111)，则),3(),1(]0),3([)],2([)],1([),1(),5(10120tRtRtRtRtRtkRtwalkikP1111111111111111111111111111111111111111111111111111111111111111)3(pH当p=3时的8个沃尔什函数经取样后可得矩阵如式(3—112)Hp()3由按佩利排列的沃尔什函数前8个波形可以看出有如下一些规律：(1)、函数序号i与正交区间内取值符号变化次数有表3—1所列之关系。表3.1按佩利排列的沃尔什函数序号与变号次数的关系i01234567变号数01327645(2)、i与变号次数的关系是自然二进码与格雷码的关系。如i=6=(110)B，这个自然二进制码按格雷码读出是4，也就是说，把十进制数编成自然二进码，然后按格雷码的规律反变回十进制数，这个数就是这个序号的沃尔什函数的变号次数。3．3．3按哈达玛排列的沃尔什函数按哈达玛排列的沃尔什函数是从阶哈达玛矩阵得来的。阶哈达玛矩阵每一行的符号变化规律，对应某个沃尔什函数在正交区间内符号变化的规律，n2n2也就是说，阶哈达玛矩阵的每一行就对应着一个离散沃尔什函数。阶哈达玛矩阵有如下形式:n2n2H()011111)1(H1111111111111111)2(H(3—113)(3—114)(3—115)一般情况)1()1()1()1()1()1()(HmHmHmHmHmHmH(3—116)式(3—116)是哈达玛矩阵的递推