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

数字图像处理学数字图像处理学第第3章章 图像处理中的正交变换图像处理中的正交变换（第三讲）（第三讲）3.3.4 沃尔什函数的性质沃尔什函数的性质 沃尔什函数有如下一些主要性质：沃尔什函数有如下一些主要性质： （１）（１） 在区间在区间[0,1]内有下式成立内有下式成立 (3—119)(3—120)(3—121)这说明在这说明在[0,1]区间内除了区间内除了 外，其他沃外，其他沃尔什函数取＋１和－１的时间是相等的尔什函数取＋１和－１的时间是相等的 （２）（２） 在区间在区间[0,1]的第一小段时间内（通常称为的第一小段时间内（通常称为时隙）沃尔什函数总是取＋１时隙）沃尔什函数总是取＋１（３）（３） 沃尔什函数有如下乘法定理沃尔什函数有如下乘法定理 (3—122) 并且，该定理服从结合律并且，该定理服从结合律(3—123) 证明：由定义式证明：由定义式 但是但是因此因此以上便是乘法定理的证明以上便是乘法定理的证明（４）（４） 沃尔什函数有归一化正交性沃尔什函数有归一化正交性(3—124) 证明：由乘法定理有证明：由乘法定理有其中 由于由于 所以当所以当l=0，即，即i=j时，则时，则而当而当 ，即，即 时，则时，则正交性得证。

正交性得证 3.3.5 沃尔什变换沃尔什变换 离散沃尔什变换可由下二式表达离散沃尔什变换可由下二式表达 (3—127) (3—128)离散沃尔什变换解析式写成矩阵式可得到沃尔什变换离散沃尔什变换解析式写成矩阵式可得到沃尔什变换矩阵式矩阵式 (3—130)式中代表阶沃尔什矩阵另外，沃尔什函数可写成如下形式式中 因此，可得到指数形式的沃尔什变换式 (3—133)以上是离散沃以上是离散沃尔尔什什变换的三种定的三种定义，其中矩，其中矩阵式最式最为简洁 (3—132) 3.3.6 离散沃尔什离散沃尔什--哈达玛变换哈达玛变换 由沃尔什函数的定义可知，按哈达玛排列的沃尔什由沃尔什函数的定义可知，按哈达玛排列的沃尔什函数与按沃尔什排列的沃尔什函数相比较只是排列函数与按沃尔什排列的沃尔什函数相比较只是排列顺序不同，其本质并没有什么不同。

但是哈达玛矩顺序不同，其本质并没有什么不同但是哈达玛矩阵具有简单的递推关系，也就是高阶矩阵可用低阶阵具有简单的递推关系，也就是高阶矩阵可用低阶矩阵的直积得到，这就使得沃尔什一哈达玛变换有矩阵的直积得到，这就使得沃尔什一哈达玛变换有许多方便之处因此，用得较多的是沃尔什－哈达许多方便之处因此，用得较多的是沃尔什－哈达玛变换 离散沃尔什－哈达玛变换的定义可直接由沃尔什变离散沃尔什－哈达玛变换的定义可直接由沃尔什变换得到，只要用按哈达玛排列的沃尔什函数去代替换得到，只要用按哈达玛排列的沃尔什函数去代替沃尔什排列的沃尔什函数，就可以得其矩阵式如下：沃尔什排列的沃尔什函数，就可以得其矩阵式如下： (3-134)式中，式中， 是沃尔什哈是沃尔什哈达玛变换系数序列达玛变换系数序列，，是时间序列，是时间序列， ，，p为正整数。

式为正整数式(3—134)的逆的逆变换式如下变换式如下 (3—135) 例：将时间序列做沃尔什－哈达玛变换及反变换反变换为3.3.7 离散沃尔什变换的性质离散沃尔什变换的性质 离散沃尔什变换有许多性质下面把主要性质列举离散沃尔什变换有许多性质下面把主要性质列举于下为叙述方便起见，用于下为叙述方便起见，用 表示时间序表示时间序列，用列，用 表示变换系数序列，以表示变换系数序列，以 表示沃尔什变换对应关系表示沃尔什变换对应关系 (3—136) （１）线性（１）线性 如果如果 则则 其中其中为常数常数（２）（２） 模模2移位性质移位性质 将时间序列将时间序列 作作L位模位模2移位所得到的序列，移位所得到的序列，我们称为模我们称为模2移位序列移位序列模模2移位是这样实现的：移位是这样实现的： 设：设： 是周期长度为是周期长度为N的序列。

作一个新的序列的序列作一个新的序列 (3—137) 其中其中 此时，称此时，称 是序列是序列f(t)的位模的位模2移位序列移位序列  例：例：L=2， 则：由于=(2)D =(3)D =(0)D =(1)D =(6)D =(7)D =(4)D =(5)D所以 同理 用矩阵表示为式中 (3—139) (3—140) 按照模按照模2和的性质，可知和的性质，可知这里这里[I]是么阵3—141) 模模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移位卷积：(3—143) (3—144) 式中 为模2卷积， 为模2减运算符，它的运算结果与模2加一样 模2移位相关的定义式如式(3—144)所示其中其中 表示模表示模2移位相关，移位相关， 是是 的模的模2移移位序列。

位序列 由式由式(3—143)和和(3—144)可见，模可见，模2移位卷积和模移位卷积和模2移位移位相关具有相同的结果相关具有相同的结果,即：即： 如果用如果用W 代表作沃尔什变换，则：代表作沃尔什变换，则：则(3—145) 下面讨论模下面讨论模2移位卷积定理移位卷积定理 如果如果所以证明 （４）（４） 模模2移位列率卷积定理移位列率卷积定理模2移位列率卷积由下式来表示(3—146) 依照模2时间卷积定理，模2移位列率卷积定理如下 如果 (3—147) 仿照模2移位时间卷积定理的证明方法可得到证明则（５）（５） 模模2移位自相关定理移位自相关定理 从模从模2 移位时间卷积移位时间卷积(相关相关)定理可以得到模定理可以得到模2移位移位自相关定理只要把定理中的自相关定理只要把定理中的 和和 换成换成 和和 便立即可以得到模便立即可以得到模2移位移位自相关定理自相关定理3—148) 其证明方法也与模其证明方法也与模2移位时间卷积定理的证明一样移位时间卷积定理的证明一样。

 从式从式(3—148)可以建立一个重要概念：可以建立一个重要概念：模模2移移位自相关序列的沃尔什变换等于序列的功率谱位自相关序列的沃尔什变换等于序列的功率谱也就是说，模也就是说，模2移位下的自相关序列的沃尔什移位下的自相关序列的沃尔什变换正好与序列的功率谱相符合变换正好与序列的功率谱相符合与傅里叶变与傅里叶变换相比较，模换相比较，模2 2移位下的自相关与沃尔什谱的移位下的自相关与沃尔什谱的关系相当于线性移位下的自相关序列的离散傅关系相当于线性移位下的自相关序列的离散傅里叶变换与其功率谱的关系里叶变换与其功率谱的关系 （６）帕斯维尔定理（６）帕斯维尔定理 如果 则 (3—149) 证明：设 因因为是自相关函数，所以是自相关函数，所以 则 又由于又由于 所以所以如果令如果令t=0，则由于由于 l 仅是求和运算的变量，因此将仅是求和运算的变量，因此将 l 换成换成 t ，，即可得：即可得：（７）循环移位定理（７）循环移位定理 把序列把序列 循环地向左移若干位，例如移循环地向左移若干位，例如移l位，位，l=1，，2，，……，，N-1，这样得到的序列叫循环移位，这样得到的序列叫循环移位序列。

如果用序列如果用 来表示循环移位序列，来表示循环移位序列，(3—150)  例如：有一个N=8的序列， 当l=5，l=3 的循环移位序列分别为循环移位定理的内容如下：循环移位定理的内容如下： 如果如果 和它的循环移位序列和它的循环移位序列 的沃尔的沃尔什－哈达玛变换分别是什－哈达玛变换分别是 和和 ，则，则 (3—151) 式中  这个定理把序列的沃尔什－哈达玛变换系数与这个定理把序列的沃尔什－哈达玛变换系数与循环移位序列的沃尔什哈达玛变换系数联系了循环移位序列的沃尔什哈达玛变换系数联系了起来即某些起来即某些 之和与之和与 之和是之和是相等的所以这个定理又称为相等的所以这个定理又称为沃尔什－哈达玛沃尔什－哈达玛变换的循环移位不变性变换的循环移位不变性下面用一个例子来说下面用一个例子来说明本定理的意义。

明本定理的意义 例如设 ，经沃尔什－哈达玛变换后的系数序列为 现将 做l=3的循环移位，则 此序列经沃尔什－哈达玛变换后的系数序列为从两个序列 与 可以看出当r=1时，则：  所以 当时，则： 所以 当r=3时，则：所以：所以： 显然，这些关系符合循环移位定理显然，这些关系符合循环移位定理 需要特别指出的是这个定理只适用于沃尔什－哈达需要特别指出的是这个定理只适用于沃尔什－哈达玛变换此定理的更加一般性的证明，请参阅有关书玛变换此定理的更加一般性的证明，请参阅有关书籍3.3.8 快速沃尔什变换快速沃尔什变换 离散付里哀变换有快速算法同样，离散沃尔什变离散付里哀变换有快速算法同样，离散沃尔什变换也有快速算法利用快速算法，完成一次变换只换也有快速算法利用快速算法，完成一次变换只须须 次加减法，运算速度可大大提高次加减法，运算速度可大大提高当然快速算法只是一种运算方法，就变换本身来说当然快速算法只是一种运算方法，就变换本身来说快速变换与非快速变换是没有区别的。

快速变换与非快速变换是没有区别的 由于沃尔什－哈达玛变换有清晰的分解过程，由于沃尔什－哈达玛变换有清晰的分解过程，而且快速沃尔什变换可由沃尔什－哈达玛变换而且快速沃尔什变换可由沃尔什－哈达玛变换修改得到，所以下面着重讨论沃尔什－哈达玛修改得到，所以下面着重讨论沃尔什－哈达玛快速变换快速变换式中式中 为正整数为正整数3—152) 由离散沃尔什－哈达玛变换的定义可知由离散沃尔什－哈达玛变换的定义可知 这里以这里以8阶沃尔什－哈达玛变换为例，讨论其分解阶沃尔什－哈达玛变换为例，讨论其分解过程及快速算法由克罗内克积可知过程及快速算法由克罗内克积可知：：  (3—153) 其中(3—154) (3—155) (3—156) 其中 均为么阵由上面的分解有 (3—157) 令 则 下面是具体计算 的公式及流程图(3—158) (3—159)(3—160)  图 3—14 快速沃快速沃尔尔什什-哈达哈达玛变换信号流信号流图（（N=8））因为 而 是对称矩阵，即： (3—161) 由此可得到另一种蝶形运算流程图。

由此可得到另一种蝶形运算流程图图 3—15 快速沃尔什-哈达玛变换信号流图 （第二种算法）对于一般情况，对于一般情况， ，则矩阵，则矩阵 可分解成可分解成P个矩阵个矩阵 之乘积，即：之乘积，即：所以，任意所以，任意 阶快速沃尔什－哈达玛变换蝶阶快速沃尔什－哈达玛变换蝶式流图不难用上述方法引伸式流图不难用上述方法引伸 (3—162) 流程图的画法：流程图的画法：1)、确定迭代次数；、确定迭代次数； N是序列长度是序列长度2）、）、对偶节点的计算；对偶节点的计算；3）、对偶节点组数目为）、对偶节点组数目为 个个 离散沃尔什－哈达玛变换的特点：离散沃尔什－哈达玛变换的特点： 1）、）、WHT只有加减运算，没有乘除运算，运只有加减运算，没有乘除运算，运算速度快；算速度快； 2）、）、[H]是对称矩阵，是对称矩阵，[H]=[H] ′,所以，正反变所以，正反变换均用一样的公式，一样的运算程序，甚至用换均用一样的公式，一样的运算程序，甚至用一样的硬件，给工程带来极大方便。

一样的硬件，给工程带来极大方便3.3.9 多维变换多维变换图像处理多用二维变换，二维变换的定义图像处理多用二维变换，二维变换的定义： 二维沃尔什－哈达玛变换可用一维沃尔什－哈达玛变换来计二维沃尔什－哈达玛变换可用一维沃尔什－哈达玛变换来计算，其步骤如下：算，其步骤如下： (1)、以、以 ，对，对 中中 个列中的每一列做变换，个列中的每一列做变换，得到得到 ；； (2)、以、以 对对 中中 行的每一行作变换，行的每一行作变换，即可得到二维变换系数即可得到二维变换系数 根据这一步骤，便可以根据这一步骤，便可以利用一维快速沃尔什－哈达玛变换来完成二维沃尔什－哈利用一维快速沃尔什－哈达玛变换来完成二维沃尔什－哈达玛变换的计算达玛变换的计算另外一种计算方法是将二维沃尔什－哈达玛变换当做另外一种计算方法是将二维沃尔什－哈达玛变换当做一维来计算。

这种方法是将数据矩阵的各列依次顺序一维来计算这种方法是将数据矩阵的各列依次顺序排列，这样就形成由排列，这样就形成由 个元素的列矩阵然后再个元素的列矩阵然后再按照一维沃尔什－哈达玛变换方法来计算下面用实按照一维沃尔什－哈达玛变换方法来计算下面用实例说明一下两种计算方法例说明一下两种计算方法 例：设数据矩阵如下例：设数据矩阵如下 求求 的二维沃尔什－哈达玛变换的二维沃尔什－哈达玛变换 首先对首先对 的每一列作变换：的每一列作变换： 第一列 第三列第三列 第二列第二列 第四列第四列 所以所以 第一行第一行 对对 每一行作变换每一行作变换 第二行第二行 最后得到二维变换系数矩阵最后得到二维变换系数矩阵 以上是采用第一种算法得到的结果以上是采用第一种算法得到的结果 第二种算法如下：第二种算法如下： 将将 改写成列矩阵改写成列矩阵[Y]，即，即 对对做一维变换做一维变换 然后重排一下然后重排一下 显然，与第一种算法得到的结果一致。

显然，与第一种算法得到的结果一致。