数字图像处理及应用：第三章沃尔什变换.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,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,年将这种矩阵加以普遍化，建立了所谓哈达玛矩阵。,利用克罗内克乘积算子,(,Kronecker,Product Operator),不难把沃尔什函数表示为哈达玛矩阵形式。利用这种形式定义的沃尔什函数称为克罗内克序数。这就是沃尔什函数的,第三种定序法,。,由上述历史可见，沃尔什函数及其有关函数的数学基础早已奠定了。但是，这些函数在工程中得到应用却是近几十年的事情。主要原因是由于半导体器件和计算机在近几十年得到迅速发展，它们的发展为沃尔什函数的实用解决了手段问题，因此，也使沃尔什函数得到了进一步发展。,与傅里叶变换相比，沃尔什变换的主要优点在于存储空间少和运算速度高，这一点对图像处理来说是至关重要的，特别是在大量数据需要进行实时处理时，沃尔什函数就更加显示出它的优越性。,3.,3.1,拉德梅克函数,拉德梅克,(,Rademacher,),函数集是一个不完备的正交函数集，由它可以构成完备的沃尔什函数。在这里首先介绍一下拉德梅克函数。拉德梅克函数包括,n,和,t,两个自变量，用,R(n,t),来表示拉德梅克函数。它可用下式来表示,(3100),当,x,=0,时，,sgn,(,x,),无定义。,(3101),由,sin,函数的周期性知道,R(n,t),也是周期性函数。由式,(3100),可见，,当,n,=1,时，,R,(1,t,),的周期为,1,；,当,n,=2,时,R,(2,t,),的周期为,1/2,；,当,n,=3,时，,R,(3,t,),的周期为 ；,一般情况下可用下式表示,(3102),拉德梅克函数的波形如图,39,所示。,R(0,t),1,0,t,R(1,t),t,t,R(2,t),t,R(3,t),t,R(4,t),图,39,拉德梅克函数,1,0,-1,1,0,-1,1,0,-1,1,0,-1,由图,39,可见，拉德梅克函数有如下一些规律：,（）,R,(,n,t,),的取值只有,+1,和,-1,。,（）,R,(,n,t,),是,R,(,n-1,t,),的二倍频。因此，如果已知最高次数,m,=,n,，则其他拉德梅克函数可由脉冲分频器来产生。,（）如果已知,n,，那么,R,(,n,t,),有 个周期，其中,0,t,1；,（4）如果在 处作取样，则可得到一数据序列,R,(,n,k,)，,。每一取样序列将与下述矩阵相对应。,这里我们取,n,=3,，,k,=0,1,2,.7,。,(3103),采用上述离散矩阵形式就可以用计算机,进行灵活处理。,3.3.,2,沃尔什函数,沃尔什函数系是完备的正交函数系，其值也是只取,1,和,1,。从排列次序来定义不外乎三种：,第一种是按沃尔什排列或称按列率排列来定义；,第二种是按佩利排列定义；(自然序数）,第三种是按哈达玛排列来定义。（第三定序法）,还可用其它方式来定义，但沃尔什函数的定义至今尚未统一，下面分别讨论上述三种排列方法定义的沃尔什函数。,3,3,1,按沃尔什排列的沃尔什函数,按沃尔什排列的沃尔什函数用 来表示。,函数波形如图,310,所示。,按沃尔什排列的沃尔什函数实际上就是按列率排列的沃尔什函数。,1,0,t,1,0,-1,t,1,1,1,0,-1,t,1,1,0,-1,t,1,1,0,-1,t,1,1,0,-1,t,1,1,0,-1,t,1,1,0,-1,t,1,图,310,按沃尔什排列的沃尔什函数,从波形上可总结出如下规律：,（1）在 中，,i,就是波形在正交区间的变号次数；,如：变号次数为0；,变号次数为1；,变号次数为2；,（2）,列率,：通常把正交区间内波形变号次数的二分之一称为列率,(,sequency,),。如果令,i,为波形在正交区间内的变号次数，那么，按照,i,为奇数或偶数，函数,的列率将分别由下式来决定,（3）按沃尔什排列的沃尔什函数可由拉德梅克函数构成，它的表达式如下,(3105),式中,R,(,k,+1,t,),是拉德梅克函数，,g,(,i,),是为,i,的格雷码，,g,(,i,),k,是此格雷码的第,k,位数字，,p,为正整数。,一个正整数可以编成自然二进码，但也可以编成格雷码。格雷码也称为反射码。格雷码的特点是：两个相邻数的格雷码只有一个码位的值不同。例如：,2,的格雷码是,(0 0 1 1),，,3,的格雷码为,(0 0 1 0),。,这两个相邻的数字的格雷码只有第四个码位的值不同。,在脉冲编码技术中，常常采用这种码，以便得到较好的误差特性。一个正整数的自然二进码和格雷码之间是可以互相转换的。从自然二进码转成格雷码的方法如下：,设一个十进制数的自然二进码为：,并设该数的格雷码,为：,其中 和 分别为自然二进码和格雷码内的码位数字，并且 、。它们之间的关系可用式,(3106),表示,(3106),式中 代表模加。,模2加的规律：,1,10,101,0 11,0 00,例：,P=4,试求（,2,）的格雷码。,解：,其中：,其格雷码,同理 若,则其格雷码为,在格雷码中，有如下关系存在：,(3107),例：设：,则,而,所以：,从正整数的格雷码也可以求出该十进数的自然二进码。其转换方法如下：,设正整数的格雷码为：,又设其自然二进码为：,则,(3108),例：,n,的格雷码为,1011,，求其自然二进码表示。,由给定的格雷码可知：,其中：,以上便是格雷码的定义及格雷码与自然二进码之间的转换方法。,即：自然二进码为,所以：,例：用公式,(3105),求,p,=4,时的,。,解：因为,i,=5,，所以,5,的自然二进码为,(0101),。由前面所述的转换规则可得到格雷码为,(0111),。因此，有下面的对应关系,即,(0 1 1 1),第,3,位 第,2,位 第,1,位 第,0,位,代入式,(3105),得,3,3,2,按佩利排列的沃尔什函数,用 来表示按佩利排列的沃尔什函数，其波形如图,311,所示。,1,0,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,图,311,按佩利排列的沃尔什函数,t,按佩利排列的沃尔什函数也可以由拉德梅克函数产生。其定义由下式表示,(3111),式中 是拉德梅克函数，是将函数序号写成自然二进码的第,k,位数字 。即：,例：,p,=3,时，求,因为,i,=1,，所以自然二进码为：,第,2,位 第,1,位 第,0,位,代入式,(3111),得：,例：,p=3,，求,。,因为,i,=5,，所以，自然二进码为,(101),，代入式,(3111),，则,当,p,=3,时的,8,个沃尔什函数经取样后可得矩阵,如式,(3112),(3112),由按佩利排列的沃尔什函数前,8,个波形的规律：,(1),、函数序号,i,与正交区间内取值符号变化次数有表,31,所列之关系。,表,3.1,按佩利排列的沃尔什函数序号与变号次数的关系,i,0,1,2,3,4,5,6,7,变 号 数,0,1,3,2,7,6,4,5,(2),、,i,与变号次数的关系是自然二进码与格雷码的关系。,如,i,=6=(110),B,，这个自然二进制码按格雷码读出是,4,，也就是说，把十进制数变成自然二进码，然后按格雷码的规律反变回十进制数，这个数就是这个序号的沃尔什函数的变号次数。,3,3,3,按哈达玛排列的沃尔什函数,按哈达玛排列的沃尔什函数是从,2,n,阶哈达玛矩阵得来的。,2,n,阶哈达玛矩阵每一行的符号变化规律，对应某个沃尔什函数在正交区间内符号变化的规律，也就是说，,2,n,阶哈达玛矩阵的每一行就对应着一个离散沃尔什函数。,2,n,阶哈达玛矩阵有如下形式,(3,114),(3,115),(3,113),一般情况,(3116),式,(3,116),是哈达玛矩阵的递推关系式。利用这个关系式可以产生任意,2,n,阶哈达玛矩阵。这个关系也叫做克罗内克积,(,Kronecker,Product),关系，或叫直积关系。,按哈达玛排列的沃尔什函数用,wal,h,(,i,t,),来表示。它的前八个函数波形如图,312,所示。按哈达玛排列的沃尔什函数也可以写成矩阵式,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,1,0,-1,1,t,1,0,-1,1,t,图,312,按哈达玛排列,的沃尔什函数,t,(3117),按哈达玛排列的沃尔什函数有如下一些特点,：,(1),、从,2,阶哈达玛矩阵可得到,2,个沃尔什函数，从,4,阶哈达玛矩阵可得到,4,个沃尔什函数，一般地说，,2,n,阶哈达玛矩阵可得到,2,n,个沃尔什函数。,(2),、由不同阶数的哈达玛矩阵得到的沃尔什函数排列顺序是不同的。例如，从,H,h,(4),得到的沃尔什函数,wal,h,(2,t,),并不是从,H,h,(8),得到的,wal,h,(2,t,),，而是从,H,h,(8),得到的,wal,h,(4,t,),。,(3),、,由于哈达玛矩阵的简单的递推关系，使得按 哈达玛排列的沃尔什函数特别容易记忆。,(4),、按哈达玛排列的沃尔什函数也可以由拉德梅克,函数产生，解析式如式,(3118),所示。,(3118),式中 仍然是拉德梅克函数，,是把,i,的自然二进码反写后的第,k,位数字，并且 ，也就是,反写后,第,1,位第,0,位,例如：求,p,=3,时，的波形。,第一种方法可用比较简单的方法是写出,阶哈达玛矩阵 ，并自上而下从,0,数起至第,6,行就是 。,第二种方法是应用数学解析式。因为,，,所以：,三种定义下的沃尔什函数，尽管它们的排列顺序各不相同，但三种排序方法得到的沃尔什函数是有一定关系的。它们之间的关系如表,32,和图,313,所示。,代入式,(3118),得,表,3 2,三种排列的前个沃尔什函数之间的关系表,例如,Wal,p,(,2,t,),的,wal,w,(,i,t,),和,wal,H,(,i,t,),间的关系如下：,2=(010),B,，按格雷码读，即,(010),G,=3,，所以 就是,wal,w,(3,t,),，,(010),比特倒置后为,(010),，按二进码读仍为,2,，则,wal,p,(2,t,),就是,wal,H,(2,t,),。其他以次类推。以上就是沃尔什函数三种定义之间的关系。,图,3 13,三种定义的沃尔什函数序号间的关系,3,4,沃尔什函数的性质,沃尔什函数有如下一些主要性质：,（）在区间,0,1,内有下式成立,(3119),(3120),(3121),这说明在,0,1,区间内除了,wal,(0,t,),外，其他沃尔什函数取和的时间是相等的。,（）在区间,0,1,的第一小段时间内（通常称为时隙）沃尔什函数总是取。,1,0,t,1,0,-1,t,1,1,1,0,-1,t,1,1,0,-1,t,1,1,0,-1,t,1,1,0,-1,t,1,1,0,-1,t,1,1,0,-1,t,1,图,310,按沃尔什排列的沃尔什函数,1,0,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,图,311,按佩利排列的沃尔什函数,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,1,0,-1,1,t,1,0,-1,1,t,图,312,按哈达玛排列,的沃尔什函数,t,（）沃尔什函数有如下乘法定理,(3122),并且，该定理服从结合律,(3123),证明：由定义式,但是,因此,以上便是乘法定理的证明。,（）沃尔什函数有归一化正交性,(3124),证明：由乘法定理有,其中,由于,所以当,l,=0,，即,i=j,时，则,而当 ，即 时，则,正交性得证。,3,5,沃尔什变换,离散沃尔什变换可由下二式表达,(3127),(3128),离散沃尔什变换解析式写成矩阵式可得到沃尔什变换,矩阵式,(3130),式中,代表,阶沃尔什矩阵。,另外，沃尔什函数可写成如下形式,式中,因此，可得到指数形式的沃尔什变换式,(3133),以上是离散沃尔什变换的三种定义，其中矩阵式最,为简洁。,(3132),3,6,离散沃尔什哈达玛变换,由沃尔什函数的定义可知，按哈达玛排列的沃尔什函数与按沃尔什排列的沃尔什函数相比较只是排列顺序不同，其本质并没有什么不同。,但是哈达玛矩阵具有简单的递推关系，也就是高阶矩阵可用低阶矩阵的直积得到，这就使得沃尔什一哈达玛变换有许多方便之处。因此，用得较多的是沃尔什哈达玛变换。,离散沃尔什哈达玛变换的定义可直接由沃尔什变换得到，只要用按哈达玛排列的沃尔什函数去代替沃尔什排列的沃尔什函数，就可以得其矩阵式如下：,(3-134),式中，是沃尔什哈达玛变换系数序列,是时间序列，,p,为正整数。,式,(3134),的逆变换式如下,(3135),例：将时间序列,做沃尔什哈达玛变换及反变换。,反变换为,3,7,离散沃尔什变换的性质,离散沃尔什变换有许多性质。下面把主要性质列举于下。为叙述方便起见，用,f,(,t,),表示时间序列，用,W,(,n,),表示变换系数序列，,以 表示沃尔什变换对应关系。,（）线性,如果,则,其中,为常数,。,（）模,2,移位性质,将时间序列,f,(,t,),作,L,位模,2,移位所得到的序列，我们称为模,2,移位序列。模,2,移位是这样实现的：,设：,是周期长度为,N,的序列。,作一个新的序列,(3137),其中 。此时，称 是序列,f,(,t,),的位模,2,移位序列。,例：,L=2，,则：,由于,=(2),D,=(3),D,=(0),D,=(1),D,=(6),D,=(7),D,=(4),D,=(5),D,所以,同理,用矩阵表示为,式中,(3139),(3140),按照模,2,和的性质，可知,这里,I,是么阵。,(3141),模,2,移位性质是指下面的关系，如果 ，并且 是 的模,2,移位序列，,则,式中：，是矩阵 中的第,n,行第,l,列的元素；,n,=0,，,1,，,2,，,(,N,-1),；,t,=0,，,1,，,2,，,，,(,N,-1),；，,p,是正整数。,此定理可证明如下：,令 为 的元素，是 的模,2,移位序列，则,令 ，则有 ，并且当,t,取值由,0,到,N,-1,时，,r,也取同样的值，只不过取值的顺序不同而已。于是可写成如下形式：,又因为,，这说明,W,z,(,n,),2,与,l,无关。,所以，证明,也就是说，模,2,移位后的序列，作沃尔什变换后，所得到的第,n,个系数的平方,W,z,(,n,),2,与模,2,移位的移位位数无关。,W,z,(,n,),2,仍然等于,W,(,n,),2,。,因此，模,2,移位定理（或称为并元移位定理）又可表达为输入序列 模,2,移位后的功率谱是不变的。,例如：设输入序列 ，对此序列作,l,=3,的模,2,移位，得,作沃尔什变换得,根据,可得,从上面结果可知,可见,n,相同时，功率也相同，也就是说功率列率谱是不变的。,（）模,2,卷积定理（时间）,在讨论下面的定理之前，首先说明一下模,2,移位卷积与模,2,移位相关的概念。,令 和 是两个长度相同的周期性序列。,(3143),用下面两式来定义两个序列的模,2,移位卷积和,模,2,移位相关,(3144),式中 为模,2,卷积，为模,2,减运算符，它的运算结果与模,2,加一样。模,2,移位相关的定义式如式,(3144),所示,其中 表示模,2,移位相关，是 的模,2,移位序列。,由式,(3143),和,(3144),可见，模,2,移位卷积和模,2,移位相关具有相同的结果,即：,如果用,W,代表作沃尔什变换，则：,则,(3145),下面讨论模,2,移位卷积定理,如果,所以证明,（）模,2,移位列率卷积定理,模,2,移位列率卷积由下式来表示,(3146),依照模,2,时间卷积定理，模,2,移位列率卷积定理如下,(3147),仿照模,2,移位时间卷积定理的证明方法可得到证明。,则,如果,（）模,2,移位自相关定理,从模,2,移位时间卷积,(,相关,),定理可以得到模,2,移位自相关定理。只要把定理中的 和 换成 和 便立即可以得到模,2,移位自相关定理。,(3148),其证明方法也与模,2,移位时间卷积定理的证明一样。,从式,(3148),可以建立一个重要概念：,模,2,移位自相关序列的沃尔什变换等于序列的功率谱。,也就是说，模,2,移位下的自相关序列的沃尔什变换正好与序列的功率谱相符合。,与傅里叶变换相比较，模,2,移位下的自相关与沃尔什谱的关系相当于线性移位下的自相关序列的离散傅里叶变换与其功率谱的关系。,（）帕斯维尔定理,如果,则,(3149),证明：设,因为,是自相关函数，所以,则,又由于,所以,如果令,t,=0,，则,由于,l,仅是求和运算的变量，因此将,l,换成,t,，即可得：,（）循环移位定理,把序列 循环地向左移若干位，例如移,l,位，,l=1,，,2,，,，,N-1,，这样得到的序列叫循环移位序列。如果用 来表示循环移位序列，则,(3150),例如：有一个,N=8,的序列，,当,l=5,，,l=3,的循环移位序列分别为,循环移位定理的内容如下：,如果 和它的循环移位序列 的沃尔什哈达玛变换分别是 和 ，则,(3151),式中,这个定理把序列的沃尔什哈达玛变换系数与循环移位序列的沃尔什哈达玛变换系数联系了起来。即某些 之和与 之和是相等的。所以这个定理又称为沃尔什哈达玛变换的循环移位不变性。下面用一个例子来说明本定理的意义。,例如设 ，经沃尔什哈达玛变换后的系数序列为,现将 做,l=3,的循环移位，则,此序列经沃尔什哈达玛变换后的系数序列为,从两个序列 与 可以看出,当,r=1,时，则：,所以,当,时，则：,所以,当,r,=3,时，则：,所以：,显然，这些关系符合循环移位定理。,需要特别指出的是这个定理只适用于沃尔什哈达玛变换。此定理的更加一般性的证明，请参阅有关书籍。,3,8,快速沃尔什变换,离散傅里叶变换有快速算法。同样，离散沃尔什变换也有快速算法。利用快速算法，完成一次变换只须 次加减法，运算速度可大大提高。当然快速算法只是一种运算方法，就变换本身来说快速变换与非快速变换是没有区别的。,由于沃尔什哈达玛变换有清晰的分解过程，而且快速沃尔什变换可由沃尔什哈达玛变换修改得到，所以下面着重讨论沃尔什哈达玛快速变换。,式中 为正整数。,(3152),由离散沃尔什哈达玛变换的定义可知,这里以,8,阶沃尔什哈达玛变换为例，讨论其分解过程及快速算法。由克罗内克积可知,(3153),其中,(3154),(3155),(3156),其中 均为么阵,由上面的分解有,(3157),令,则,下面是具体计算 的公式及流程图。,(3158),(3159,),(3160),图,314,快速沃尔什,-,哈达玛变换信号流图（,N=8,）,因为,而 是对称矩阵，即：,(3161),由此可得到另一种蝶形运算流程图。,对于一般情况，则矩阵 可分解成,P,个矩阵 之乘积，即：,所以，任意 阶快速沃尔什哈达玛变换蝶式流图不难用上述方法引伸。,(3162),图,315,快速沃尔什,-,哈达玛变换信号流图（第二种算法）,3,9,多维变换,在图像处理中广泛运用的是二维变换，因此，下面对二维沃尔什哈达玛变换作一介绍。,二维沃尔什哈达玛变换可用一维沃尔什哈达玛变换来计算，其步骤如下：,(1),、以,N,=,N,x,，对,f,(,x,y,),中,N,y,个列中的每一,列做变换，得到,W,x,(,u,y,),；,(2),、以,N=,N,y,对,W,x,(,u,y,),中,N,x,行的每一行作变,换，即可得到二维变换系数,W,xy,(,u,v,),。,另外一种计算方法是将二维沃尔什哈达玛变换当做一维来计算。这种方法是将数据矩阵的各列依次顺序排列，这样就形成由,N,x,N,y,个元素的列矩阵。然后再按照一维沃尔什哈达玛变换方法来计算。下面用实例说明一下两种计算方法。,求 的二维沃尔什哈达玛变换。,首先对 的每一列作变换：,例：设数据矩阵如下,第一列,第二列,第三列,第四列,所以,对 每一行作变换,第一行,第二行,最后得到二维变换系数矩阵,以上是采用第一种算法得到的结果。,第二种算法如下：,将,f,(,x,y,),改写成列矩阵,Y,，即,对,Y,做一维变换,然后重排一下,显然，与第一种算法得到的结果一致。,二维沃尔什哈达玛变换的矩阵式定义如下,(3,171),(3,172),式中 和 分别为 阶和 阶哈达玛矩阵。,作业：,P175,第,4,题,P176,第,12,14,20,23,25,29,题,