正交变换第二组

正交变换第二组第一页，共六十页，编辑于2023年，星期三主要内容

第一章沃尔什变换第二章小波变换第二页，共六十页，编辑于2023年，星期三第一章沃尔什变换1.1沃尔什函数1.2沃尔什变换1.3算法1.4应用第三页，共六十页，编辑于2023年，星期三1.1沃尔什函数※※※函数值仅取“+1”、“-1”两值的非正弦型的标准正交完备函数系。任何一个时间函数完全可以用多个沃尔什函数来表示。只定义在有限时间T内，具有两个自变量，时间变量t和序数n。函数通常表示为Wal(n,t)。第四页，共六十页，编辑于2023年，星期三

三种定义方法：按照沃尔什排列来定义（按列率排序）；按照佩利排列来定义（按自然排序）；按照哈达玛排列来定义。第五页，共六十页，编辑于2023年，星期三拉德梅克函数集是一个不完备的正交函数集，由它可以构成完备的沃尔什函数。把一个正弦函数进行无限限幅就可以得到拉得梅克函数。拉得梅克函数包括n和t两个自变量,用R(n,t)表示。它可以用下式来表示：

当x=0时，sgn（x）无定义。拉德梅克函数第六页，共六十页，编辑于2023年，星期三按沃尔什排列定义的沃尔什函数是按列率排列的。通常把正交区间内波形变号次数的二分之一称为列率（按照函数的序数由正交区间内过零点平均数来定义的）。函数的列率由下式决定：按沃尔什排列的沃尔什函数可由拉德梅克函数构成，表达式如下：g(i)是i的格雷码，g(i)k是此格雷码的第K位数字，m为正整数。（1）按沃尔什排列的沃尔什函数第七页，共六十页，编辑于2023年，星期三按佩利排列的沃尔什函数也可由拉德梅克函数构成，定义是如下：ik是将函数序号写成自然二进制码的第K位数字，即

。（2）按佩利排列的沃尔什函数第八页，共六十页，编辑于2023年，星期三按哈达玛排列的沃尔什函数也可由拉德梅克函数构成，解析式如下：式中是把i的自然二进码反写后的第k位数字,并且 也就是反写后：（3）按哈达玛排列的沃尔什函数第九页，共六十页，编辑于2023年，星期三由于哈达玛排序的沃尔什函数是由2n（n=0,1,…）阶哈达玛矩阵(HadamardMatrix)得到的，而哈达玛矩阵的最大优点在于它具有简单的递推关系，即高阶矩阵可用两个低阶矩阵的克罗内克积求得，因此我们重点介绍哈达玛排列定义的沃尔什变换。2n阶哈达玛矩阵：递推关系：第十页，共六十页，编辑于2023年，星期三三种定义下的沃尔什函数，尽管它们的排列顺序各不相同，但三种排序方法得到的沃尔什函数有一定的关系。沃尔什函数三种定义之间的关系：WALp(i，t)WALw(i，t)WALH(i，t)比特倒置二进码写，格雷码读格雷码写，二进码读比特倒置格雷码写，倒置，二进码读二进码写，倒置，格雷码读图1-1沃尔什函数关系图第十一页，共六十页，编辑于2023年，星期三以沃尔什函数为基础，将一个函数变换为取值为+1或-1为基向量构成的级数。与傅里叶变换相比，沃尔什变换的主要优点在于存储空间少和运算速度快，这一点对于图像处理来说是至关重要的。

一维离散沃尔什变换

离散沃尔什-哈达玛变换

二维离散沃尔什变换

快速沃尔什变换（FWHT）1.2沃尔什变换第十二页，共六十页，编辑于2023年，星期三 一维离散沃尔什变换定义：

一维离散沃尔什逆变换定义：1.2.1一维离散沃尔什变换第十三页，共六十页，编辑于2023年，星期三

式中，代表N阶沃尔什矩阵。是沃尔什变换系数序列；是时间序列。沃尔什变换矩阵式第十四页，共六十页，编辑于2023年，星期三若将用哈达玛矩阵表示，并将变换表达式写成矩阵形式：

式中，为N阶哈达玛矩阵。1.2.2离散沃尔什-哈达玛变换第十五页，共六十页，编辑于2023年，星期三由哈达玛矩阵的特点可知，沃尔什-哈达玛变换的本质上是将离散序列f(x)的各项值的符号按一定规律改变后，进行加减运算，因此，它比采用复数运算的DFT和采用余弦运算的DCT要简单得多。第十六页，共六十页，编辑于2023年，星期三将一维WHT的定义推广到二维WHT。二维沃尔什-哈达玛变换的指数式如下：二维沃尔什-哈达玛变换的的逆变换式为：式中代表图像的像素，是该像素在空间中的位置坐标；代表变换系数；为正整数；是x，u的二进制码的第r位数字，

为正整数；是y，v的二进制码的第s位数字。1.2.3二维离散沃尔什变换第十七页，共六十页，编辑于2023年，星期三二维沃尔什-哈达玛变换的矩阵式定义如下：式中，和分别为和阶哈达玛矩阵第十八页，共六十页，编辑于2023年，星期三类似于FFT，WHT也有快速算法FWHT。利用快速算法，完成一次变换只需

次加减法，预算速度可大大提高。快速沃尔什变换可由沃尔什-哈达玛变换修改得到，所以下面着重讨论一下沃尔什-哈达玛快速变换。由离散沃尔什-哈达玛变换的定义可知：

式中，，P为正整数。

1.2.4快速沃尔什变换（FWHT）第十九页，共六十页，编辑于2023年，星期三以8阶沃尔什-哈达玛变换为例，讨论分解过程及快速算法： 其中，均为酉阵。第二十页，共六十页，编辑于2023年，星期三对于一般情况，则矩阵可以分解成P个矩阵之乘积，即第二十一页，共六十页，编辑于2023年，星期三由上面的分解有

令则

因为而是对称矩阵，则

由此可得到两种形式的蝶形运算流程图。所以任意2r阶快速沃尔什-哈达玛变换的碟式流程图不难用上述方法引伸。第二十二页，共六十页，编辑于2023年，星期三法一：二维沃尔什-哈达玛变换可以用一维沃尔什-哈达玛变换来计算，其步骤如下：（1）以，对中个列中的每一列做变换，得到；（2）以，对中行中每一行做变换，即可得到二维变换系数。法二：将二维沃尔什-哈达玛变换当做一维来计算。这种方法是将数据矩阵的各列依次顺序排列，这样就形成由

个元素的列矩阵。然后再按一维沃尔什-哈达玛变换方法来计算。

下面用事例说明一下两种计算方法。1.3二维沃尔什-哈达玛变换的计算第二十三页，共六十页，编辑于2023年，星期三

例：设数据矩阵如下，

求的二维沃尔什-哈达玛变换。法一：首先对的每一列做变换：

第一列

第二列

第三列

第四列

所以

第二十四页，共六十页，编辑于2023年，星期三

对每一行做变换 第一行 第二行最后得到二维系数变换矩阵

第二十五页，共六十页，编辑于2023年，星期三法二： 将改写成矩阵Y，即

对Y做以下变换

然后重排一下

显然，与第一种算法的到的结果一致。第二十六页，共六十页，编辑于2023年，星期三下图是一幅数字图像及对其进行二维WHT变换的结果。

图1-2二维WHT结果（a）原图像；（b）WHT结果从以上例子可看出，二维WHT具有能量集中的特性，而且原始数据中数字越是均匀分布，经变换后的数据越集中于矩阵的边角上。因此，二维WHT可用于压缩图像信息。1.4应用第二十七页，共六十页，编辑于2023年，星期三 综上所述，WHT是将一个函数变换成取值为＋1或－1的基本函数构成的级数，用它来逼近数字脉冲信号时要比FFT有利。同时，WHT只需要进行实数运算，存储量比FFT要少得多，运算速度也快得多。因此，WHT在图像传输、通信技术和数据压缩中被广泛使用。第二十八页，共六十页，编辑于2023年，星期三第二章小波变换2.2离散小波变换2.4应用2.3算法2.1连续小波变换第二十九页，共六十页，编辑于2023年，星期三背景知识傅立叶变换：提供了频率域的信息，但丢失了时间域的局部化信息。小波变换:是对一个函数在时间和频率上进行局部化分析的一种数学变换。通过平移母小波(motherwavelet)获得信号的时间信息。通过缩放母小波的宽度(或称尺度)获得信号的频率特性。对母小波的平移和缩放操作是为计算小波的系数，这些系数代表局部信号和小波之间的相关程度。从而达到变换目的：获得时间和频率域之间的相互关系。第三十页，共六十页，编辑于2023年，星期三2.1连续小波变换连续小波变换（ContinuousWaveletTransform，CWT）用下式表示：

上式表示小波变换是信号f(t)与被缩放和平移的小波函数ψ()之积在信号存在的整个期间里求和的结果。CWT的变换结果是许多小波系数C，这些系数是缩放因子（scale）和平移（positon）的函数。第三十一页，共六十页，编辑于2023年，星期三2.1.1小波小波的选择既不是唯一的也不是任意的：这里是归一化地具有单位能量的解析函数，他应满足以下条件：（1）具有有限的持续时间和突变的频率和振幅。（2）在有限的时间范围内，它的平均值等于零，即（高阶矩也为0）. 第三十二页，共六十页，编辑于2023年，星期三图2-1（a）正弦波曲线（b）小波曲线

上图表示了正弦波和小波的区别，由此可以看出，正弦波从负无穷一直延续到正无穷，正弦波是平滑而且是可预测的，而小波是一类在有限区间内快速衰减到0的函数，其平均值为0，小波趋于不规则、不对称。综上，可以概括为：小波应是具有震荡性和迅速衰减的波。第三十三页，共六十页，编辑于2023年，星期三

基本小波函数ψ()的缩放和平移操作含义如下：(1)缩放。简单地讲，缩放就是压缩或伸展基本小波，缩放系数越小，则小波越窄，如图2-2所示。（2）平移。简单地讲，平移就是小波的延迟或超前。在数学上，函数f(t)延迟k的表达式为f(t-k)，如图2-3所示。图2-3小波的平移操作(a)小波函数ψ(t)；(b)位移后的小波函数ψ(t-k)

图2-2小波的缩放操作第三十四页，共六十页，编辑于2023年，星期三例：设函数具有有限能量，即，则小波变换的定义如下：

积分核为。a为尺度参数，b为位置参数，为小波。若，函数具有伸展作用；，函数具有收缩作用。小波随伸缩参数a，平移参数b而变化。随参数a的减小，的支撑区也就变大（支撑区或支集就是函数定义域的闭子集），而

频谱随之向高频端展宽，反之亦然。这就有可能实现窗口大小自适应变化，当信号频率增高时，时窗宽度变窄，而频窗宽度增大，有利于提高时频分辨率，反之也一样。第三十五页，共六十页，编辑于2023年，星期三 小波的缩放因子与信号频率之间的关系是：缩放因子scale越小，表示小波越窄，度量的是信号的细节变化，表示信号频率越高；缩放因子scale越大，表示小波越宽，度量的是信号的粗糙程度，表示信号频率越低。第三十六页，共六十页，编辑于2023年，星期三2.1.2二维连续小波变换定义：逆变换为：第三十七页，共六十页，编辑于2023年，星期三2.1.3小波变换傅立叶分析用一系列不同频率的正弦波表示一个信号。一系列不同频率的正弦波是傅立叶变换的基函数。小波变换用母小波通过移位和缩放后得到的一系列小波表示一个信号。一系列小波可用作表示一些函数的基函数。凡能用傅立叶分析的函数都可用小波分析小波变换可理解为用经过缩放和平移的一系列函数代替傅立叶变换用的正弦波。用不规则的小波分析变化激烈的信号比用平滑的正弦波更有效，或者说对信号的基本特性描述得更好。第三十八页，共六十页，编辑于2023年，星期三2.2离散小波变换（DWT）在连续小波变换中，伸缩参数a和平移参数b连续取值，在每个可能的缩放因子和平移参数下计算小波系数，其计算量相当大，将产生惊人的数据量，而且有许多数据是无用的。实际应用中离散小波变换更适合于计算机处理。离散小波：

离散小波变换（DiscreteWaveletTransform，DWT）：第三十九页，共六十页，编辑于2023年，星期三2.2.1双尺度小波变换（DyadicWaveletTransform） 缩放因子和平移参数都选择为2j（j>0且为整数）的倍数，使用这样的缩放因子和平移参数的小波变换称为双尺度小波变换，它是离散小波变换的一种形式。通常离散小波变换就是指双尺度小波变换。第四十页，共六十页，编辑于2023年，星期三2.2.2快速小波变换（Mallat算法） 执行离散小波变换的有效方法是使用滤波器，该方法是Mallat于1988年提出的，称为Mallat算法。Mallat算法本质上不需要知道尺度函数和小波函数的具体结构，只由系数就可以实现的分解与重构，因此称为快速小波变换。第四十一页，共六十页，编辑于2023年，星期三

用滤波器执行离散小波变换的概念如图2-4所示。S表示原始的输入信号，通过两个互补的滤波器组，其中一个滤波器为低通滤波器，通过该滤波器可得到信号的近似值A（Approximations），另一个为高通滤波器，通过该滤波器可得到信号的细节值D（Detail）。图2-4小波分解示意图2.2.3小波分解第四十二页，共六十页，编辑于2023年，星期三对于一个信号，如采用图2-4所示的方法，理论上产生的数据量将是原始数据的两倍。于是，根据奈奎斯特（Nyquist）采样定理，可用下采样的方法来减少数据量，即在每个通道内（高通和低通通道）每两个样本数据取一个，便可得到离散小波变换的系数（Coefficient），分别用cA和cD表示，如图2-5所示。图中表示下采样。图2-5小波分解下采样示意图第四十三页，共六十页，编辑于2023年，星期三2.2.4小波重构定义：利用信号的小波分解的系数还原出原始信号，这一过程称为小波重构（WaveletReconstruction）或叫做小波合成（WaveletSynthesis）。这一合成过程的数学运算叫做逆离散小波变换（InverseDiscreteWaveletTransform，IDWT）。图2-6

小波重构算法示意图第四十四页，共六十页，编辑于2023年，星期三1）重构近似信号与细节信号由上图可知，由小波分解的近似系数和细节系数可以重构出原始信号。同样，可由近似系数和细节系数分别重构出信号的近似值或细节值，这时只要近似系数或细节系数置为零即可。图2-7是对第一层近似信号或细节信号进行重构的示意图。图2-7

重构近似和细节信号示意（a）重构近似信号；(b)重构细节信号第四十五页，共六十页，编辑于2023年，星期三2）多层重构在图2-6中，重构出信号的近似值A1与细节值D1之后，则原信号可用A1＋D1＝S重构出来。对应于信号的多层小波分解，小波的多层重构如图2-8，可见重构过程为：A3＋D3＝A2；A2＋D2＝A1；A1+D1＝S。图2-8

多层小波重构示意图第四十六页，共六十页，编辑于2023年，星期三2.2.5二维离散小波变换二维离散小波变换是一维离散小波变换的推广，其实质上是将二维信号在不同尺度上的分解，得到原始信号的近似值和细节值。由于信号是二维的，因此分解也是二维的。分解的结果为：近似分量cA、水平细节分量cH、垂直细节分量cV和对角细节分量cD。同样也可以利用二维小波分解的结果在不同尺度上重构信号。二维小波分解和重构过程如图2-9所示。第四十七页，共六十页，编辑于2023年，星期三图2-9

二维小波分解和重构过程示意图（a）二维DWT；(b)二维IDWT第四十八页，共六十页，编辑于2023年，星期三2.3Mallat算法尺度函数由尺度函数构造小波是小波变换的必经之路。尺度函数应满足下列条件：它是一个平均函数。即尺度函数是范数为1的规范化函数。

即尺度函数对所有的小波是正交的。即尺度函数对于平移是正交的。

即某一尺度上的尺度函数可以由下一尺度的线性组合得到，hn是尺度系数。尺度函数与小波是有关联的。式中，是归一化因子，是有尺度系数导出的系数。这说明小波可以由尺度函数的伸缩和平移的线性组合获得，这就是构造小波正交基的途径。第四十九页，共六十页，编辑于2023年，星期三（2）由离散小波的定义，如果把t也离散化，并选择，则可得到二进制小波：Mallat算法描述设V0是给定的多分辨率尺度空间，尺度因子m=0，相应的尺度函数为:第五十页，共六十页，编辑于2023年，星期三小波函数为：若，则正交小波分解为：当m=1时，则令当尺度因子m=1转到m=2时，相应于第五十一页，共六十页，编辑于2023年，星期三需补充细节信息d1，则类似的则。因此可得：

为建立和的系数之间的关系，代换角标n用k代之，j用n代之则有：第五十二页，共六十页，编辑于2023年，星期三由此可得：由此推广至系数表达的一般式：该式就是由小波系数和重构函数f（t）的正交展开式系数的公式。函数f(t)的小波展开系数和

用双尺度差分公式表示可按下式计算：第五十三页，共六十页，编辑于2023年，星期三同理：第五十四页，共六十页，编辑于2023年，星期三计算步骤可按下列方法进行：由计算和，再由计算和，直至尺度到m为止。上述的分析从信息处理的观点来看，可认为是一种滤波运算。Mallat算法本质上不需要知道尺度函数和小波函数的具体结构，只由系数就可以实现