数字图像处理学：第3章 图像处理中的正交变换（第3－3讲）.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数字图像处理学,第,3,章,图像处理中的正交变换,（第三讲）,3.3.4,沃尔什函数的性质,沃尔什函数有如下一些主要性质：,（）在区间,0,1,内有下式成立,(3119),(3120),(3121),这说明在,0,1,区间内除了 外，其他沃尔什函数取和的时间是相等的。,（）在区间,0,1,的第一小段时间内（通常称为时隙）沃尔什函数总是取。,（）沃尔什函数有如下乘法定理,(3122),并且，该定理服从结合律,(3123),证明：由定义式,但是,因此,以上便是乘法定理的证明。,（）沃尔什函数有归一化正交性,(3124),证明：由乘法定理有,其中,由于,所以当,l,=0,，即,i=j,时，则,而当 ，即 时，则,正交性得证。,3.3.5,沃尔什变换,离散沃尔什变换可由下二式表达,(3127),(3128),离散沃尔什变换解析式写成矩阵式可得到沃尔什变换,矩阵式,(3130),式中,代表,阶沃尔什矩阵。,另外，沃尔什函数可写成如下形式,式中,因此，可得到指数形式的沃尔什变换式,(3133),以上是离散沃尔什变换的三种定义，其中矩阵式最,为简洁。,(3132),3.3.6,离散沃尔什,-,哈达玛变换,由沃尔什函数的定义可知，按哈达玛排列的沃尔什函数与按沃尔什排列的沃尔什函数相比较只是排列顺序不同，其本质并没有什么不同。但是哈达玛矩阵具有简单的递推关系，也就是高阶矩阵可用低阶矩阵的直积得到，这就使得沃尔什一哈达玛变换有许多方便之处。因此，用得较多的是沃尔什哈达玛变换。,离散沃尔什哈达玛变换的定义可直接由沃尔什变换得到，只要用按哈达玛排列的沃尔什函数去代替沃尔什排列的沃尔什函数，就可以得其矩阵式如下：,(3-134),式中，是沃尔什哈达玛变换系数序列,，,是时间序列，,p,为正整数。式,(3134),的逆变换式如下,(3135),例：将时间序列,做沃尔什哈达玛变换及反变换。,反变换为,3.3.7,离散沃尔什变换的性质,离散沃尔什变换有许多性质。下面把主要性质列举于下。为叙述方便起见，用 表示时间序列，用 表示变换系数序列，以 表示沃尔什变换对应关系。,(3136),（）线性,如果,则,其中,为常数,。,（）模,2,移位性质,将时间序列 作,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,也取同样的值，只不过取值的顺序不同而已。于是可写成如下形式：,所以，证明,又因为 ，这说明 与,l,无关。也就是说，模,2,移位后的序列，作沃尔什变换后，所得到的第,n,个系数的平方 与模,2,移位的移位位数无关。仍然等于 。,因此，,模,2,移位定理（或称为并元移位定理）又可表达为输入序列 模,2,移位后的功率谱是不变的。,例如：设输入序列 ，对此序列作,l=3,的模,2,移位，得,作沃尔什变换得,根据,可得,从上面结果可知,可见,n,相同时，功率也相同，也就是说功率列率谱是不变的。,（）模,2,移位卷积定理（时间）,在讨论下面的定理之前，首先说明一下模,2,移位卷积与模,2,移位相关的概念。,令 和 是两个长度相同的周期性序列。用下式来定义两个序列的模,2,移位卷积,：,(3143),(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.3.8,快速沃尔什变换,离散付里哀变换有快速算法。同样，离散沃尔什变换也有快速算法。利用快速算法，完成一次变换只须 次加减法，运算速度可大大提高。当然快速算法只是一种运算方法，就变换本身来说快速变换与非快速变换是没有区别的。,由于沃尔什哈达玛变换有清晰的分解过程，而且快速沃尔什变换可由沃尔什哈达玛变换修改得到，所以下面着重讨论沃尔什哈达玛快速变换。,式中 为正整数。,(3152),由离散沃尔什哈达玛变换的定义可知,这里以,8,阶沃尔什哈达玛变换为例，讨论其分解过程及快速算法。由克罗内克积可知,：,(3153),其中,(3154),(3155),(3156),其中 均为么阵,由上面的分解有,(3157),令,则,下面是具体计算 的公式及流程图。,(3158),(3159),(3160),图,314,快速沃尔什,-,哈达玛变换信号流图（,N=8,）,因为,而 是对称矩阵，即：,(3161),由此可得到另一种蝶形运算流程图。,图,315,快速沃尔什,-,哈达玛变换信号流图（第二种算法）,对于一般情况，则矩阵,可分解成,P,个矩阵 之乘积，即：,所以，任意 阶快速沃尔什哈达玛变换蝶式流图不难用上述方法引伸。,(3162),流程图的画法：,1)、确定迭代次数；,N,是序列长度。,2）、,对偶节点的计算；,3）、对偶节点组数目为 个,离散沃尔什哈达玛变换的特点：,1）、,WHT,只有加减运算，没有乘除运算，运算速度快；,2）、,H,是对称矩阵，,H=H,所以，正反变换均用一样的公式，一样的运算程序，甚至用一样的硬件，给工程带来极大方便。,3.3.9,多维变换,图像处理多用二维变换，二维变换的定义,：,二维沃尔什哈达玛变换可用一维沃尔什哈达玛变换来计算，其步骤如下：,(1),、以 ，对 中 个列中的每一列做变换，得到 ；,(2),、以 对 中 行的每一行作变换，即可得到二维变换系数 。根据这一步骤，便可以利用一维快速沃尔什哈达玛变换来完成二维沃尔什哈达玛变换的计算。,另外一种计算方法是将二维沃尔什哈达玛变换当做一维来计算。这种方法是将数据矩阵的各列依次顺序排列，这样就形成由 个元素的列矩阵。然后再按照一维沃尔什哈达玛变换方法来计算。下面用实例说明一下两种计算方法。,例：设数据矩阵如下,求 的二维沃尔什哈达玛变换,。,首先对 的每一列作变换：,第一列,第三列,第二列,第四列,所以,第一行,对 每一行作变换,第二行,最后得到二维变换系数矩阵,以上是采用第一种算法得到的结果。,第二种算法如下：,将 改写成列矩阵,Y,，即,对,做一维变换,然后重排一下,显然，与第一种算法得到的结果一致。,