小波变换课件第4章小波变换的实现技术

1、第4章 小波变换的实现技术4.1 Mallat算法双正交小波变换的Mallat算法：设、为实系数双正交小波滤波器。，是小波分析滤波器，是小波综合滤波器。表示的逆序，即。若输入信号为，它的低频部分和高频部分以此为和，小波分解与重构的卷积算法： 先进行输入信号和分析滤波器的巻积，再隔点采样，以形成低频和高频信号。对于有限的数据量，经过多次小波变化后数据量大减，因此需对输入数据进行处理。4.1.1 边界延拓方法下面给出几种经验方法。1. 补零延拓是假定边界以外的信号全部为零，这种延拓方式的缺点是，如果输入信号在边界点的值与零相差很大，则零延拓意味着在边界处加入了高频成分，造成很大误差。实际应用中很少

2、采用。2.简单周期延拓将信号看作一个周期信号,即。简单周期延拓后的信号变为这种延拓方式的不足之处在于，当信号两端边界值相差很大时，延拓后的信号将存在周期性的突变，也就是说简单周期延拓可在边界引入大量高频成分，从而产生较大误差。3. 周期对称延拓这种方法是将原信号在边界上作对称折叠，一般分二1）当与之做卷积的滤波器为奇数时，周期延拓信号为2）当与之做卷积的滤波器为偶数时，周期延拓信号为 4. 光滑常数延拓在原信号两端添加与端点数据相同的常数。5. 平滑延拓在原信号两端用线性外插法补充采样值，即沿着信号两端包络线的一阶导数方向增加采样值。l 实际应用时，在变换前对输入信号进行边界进行延拓，使之变成

3、无限长的信号，变换后，、在尽可能不丢失信息的情况下，适当截取部分变换系数作为低频信号和高频信号，以保证小波分解后的数据总量保持不变。见下图。为实现完全重构，先对有限长序列进行延拓，然后再插值和滤波，对滤波后的信号相加，再适当截取，以恢复原信号。见下图。4.1.3 用小波处理函数信号的基本步骤1. 初始化l 对于时间的连续信号，选择适当的，使得大于信号的抽样频率(不同的应用决定了不同的抽样率)。l 设信号在最高初始分辨率级下的光滑逼近为，则有由式（322）, 既可得在实际应用中，由原信号确定的的范围是有限的，譬如信号的持续时间为，则的范围为。2. 小波分解应用Mallat 算法，得到离散信号的小

4、波变换，相应地，得到的分辨率表示：其中， 。具体地,实际应用中，可以根据需要控制分解的级数，不一定达到级。3. 小波系数处理针对不同的应用目标，对小波系数进行处理获得新的小波系数。譬如，在进行信号的数据压缩时，将绝对值小于某一阈值的系数置为零，保留剩余的系数，用于重构信号；而在去噪时，将绝对值小于某一阈值的系数置为零，用于重构去噪信号。4. 小波重构对处理后的小波系数，重构出分辨率时的离散信号。一般地，是的逼近信号。进而可以得到或的重构信号。对于离散信号的小波处理过程为 ，设（）是一个离散输入信号，采样间隔为，其中。可将与联系起来（是正交尺度函数），使为的均匀采样，即。根据式（322）可得。由

5、此可获得在最高分辨率下的初始系数序列。然后，利用Mallat算法对该序列进行小波分解、对小波系数处理以及处理后的系数进行小波重构等。4.1.4 应用举例例4.1对单位区间上一个连续信号，将信号离散化为个采样值，相应的逼近信号记为。用Haar小波对信号进行3级小波分解，写出信号的多分辨表示，并画出该信号在不同分辨率下的逼近信号、和的图形。 假设信号为，它在中的投影记为，则的图形见图42a。用Haar小波对信号进行3级小波分解，其多分辨表示为其中、波形如图42b、c、d所示。图4-2 一个函数的多分辨逼近函数 例4.2 对于例4-2中的信号及逼近信号。若用正交尺度函数和正交小波函数进行小波分析解，

6、则可得到：其中，1）用Haar尺度函数和Haar小波函数分解信号，令绝对值最小的80%和90%的系数为0，对信号进行小波压缩。画出相应的重构信号波形，并求出相应的相对误差。2）用Daubechice尺度函数和Daubechice小波 (如db2)分解信号，令绝对值最小的80%和90%的系数为0，对信号进行小波压缩。画出相应的重构信号波形，并求出相应的相对差。3）比较1）和2）的压缩效果。4）用FFT在相同条件下压缩信号，所得的相对误差如何。求解过程如下：1） 用Haar小波函数分解信号，令绝对值最小的80%和90%的系数为0，得到重构信号图形如图4-3a所示。所得的均方差为0.7991；相对误

7、差为0.0050。如果令绝对值最小的90%的系数为0，得到重构信号图形如图4-3b所示。在这种情况下，得到均方误差为2.9559，相对误差为0.0185。图4-3 用Haar小波压缩后的重构信号2） 用Daubechice小波函数(如Db2)分解信号，令绝对值最小的80%的系数为0，得到的重构信号波形如图4-4a所示，得到均方误差为0.0277，相对误差为0.00017。如果令绝对值最小的90%的系数为0，得到重构信号图形如图4-4b所示，这时得到均方误差为0.2159，相对误差为0.0014。图4-4 用Daubechice小波压缩后的重构信号3） 比较1）和2）的压缩效果可以看出，对于同一

8、种小波，保留更多的变换后的系数可以得到更好的重构信号。对于相同比例的保留系数，用Daubechice小波分解信号，再重构，得到的效果好于Haar小波。这是因为Daubechice小波的连续性较好，更适合处理连续性较好的信号。4) 用FFT对信号进行处理。令绝对值最小的80%的系数为0，则重构信号的图形如图4-5a所示。得到均方误差为0.0025，相对误差为1.59。图4-5 用FFT压缩后的重构信号注释：上两例是说明用小波处理信号的基本过程和在压缩中的应用，并不是想与FFT比较谁的效果好。实际上，这里采用的信号周期性很好（正弦波的叠加），用傅立叶变换处理更有优势。一般地，小波更适合处理突变信号

9、，而傅立叶变换更适合处理周期信号。4.2 多孔算法l Mallat算法存在的问题是数据逐级减少问题。原因是逐级二抽样，每经过一级小波分解，数据减少一半，因此，随着分辨率减少，低频分量的数据越来越少。l 多孔算法（非抽样小波变换或平稳小波变换）两通道Mallat算法等价的z变换如图47表示。记，l 二分树算法Mallat算法的小波分解迭代过程如图4-8所示。其中，l z变换的等效易位性质：因为左边 右边 图4-9 Mallat 算法的一种等效形式如果不考虑每个分支的最后的抽样环节，则，相当于中各点的小波变换全部计算出来，这叫非抽样小波变换。如图4-9所示。表示在滤波器的任意两点间插入个零所得到的

10、滤波器Z变换，所以，非抽样小波变换就是把滤波器，个相邻点之间插入个零再与低频信号做卷积，故称多孔算法。是将每两个点之间插入三个零得到的新滤波器，是将每两个点之间插入一个零得到的新滤波器，这样就把每一级的抽取移到了最后，保证了总数据不会逐级减少，有效地实现了Mallat算法。由于和是使，中补零 ，增加了空隙，故称多孔算法。设原始信号的长度为，记，根据下面的分解算法： （4-1）计算各抽样点处的小波变换，（）的伪码程序：从多孔算法的分解过程（式（4-1）可知，于是，由完全重构条件（式（3-34）可得 （4-2）4.3 小波变换的提升实现优点（1）可以实现更快速的小波变换算法，一般比Mallat算法

11、快2倍。（2）可以实现完全的同址运算。（3）能很好地克服小波变换的边界问题。（4）提升算法小波变换的描述简单，可以避免使用傅里叶变换。（5）在时域或空域直接实现小波构造，既工程师可以按着自己的要求来构造不同的小波，不再紧紧依赖数学家。4.3.0小波变换的提升实现l 回顾 Haar小波变换按着Haar小波滤波器组，两个数a,b的平均与细节分别为于是，的小波变换为。如果，高度相关，则很小。由恢复的计算公式如下：对于长度为的信号，将求平均与细节运算应用到每对数据，上，记 （1-45）这里是将信号序列的偶序号点和奇序号点相加取平均得平均值；将奇序号点减去偶序号点得到差值。和各有个样本，看作是信号的概貌

12、和细节。当遍历0到之间的所有整数时，组成序列，可以对进行类似的分解，得到和，它们各有个样本，组成了序列。这样的分解可以进行次，最后的概貌信号只有一个点，它是信号的均值或直流分量。最后的概貌信号加上各级细节信号，正好是个。上述变换正是Haar小波变换。多级Haar小波变换的分解过程和重构过程如下图。图1-21 多级小波变换过程示意图l （1.8.2） Haar小波变换的提升实现小波变换的原位实现（in-lplace）-不增加额外空间（1） d=b-a （先将d 存于原来b的位置） （2） s =a+d/2 (s=a+d/2=a+b/2- a/2= (a+b)/2) （再计算s 存于原来a 的位置

13、）l 提升算法中的信号分解提升过程分为三步：分裂、预测和更新。考虑信号，提升算法分三步完成（1）Split(分裂)将信号简单地分为两部分，有多种方法，这里将信号序列按奇、偶分为两个子集： 只将完整信号序列分成二部分，不做其他处理，故称懒小波变换。这里Split是分裂算子。这种分解方法可表示为 注释：将信号分解为成两个序列的方法有很多，将信号序列按奇、偶分为两个子集是一种方法；或将前一半和后一半分成两个子集也是一种方法；或将相邻两个数之和分给一个子集，而相邻两个数之差分给另一个子集又是一种方法。总之，不同的分裂方法，相当于采用不同的小波基。实际应用中，最常用的是懒小波最为第一级分解。（2）Pre

14、dict(预测) 若原信号具有局部相关性，则子集和也具有相关性。因此，只要知道其中任一个，就可以以合理地精度预测另一个，通常用偶子集预测奇子集。在Haar小波变换的情况下，预测误差为，特别地，如果原信号是一个常量，则所有预测误差均为零。一般情况，定义预测算子P，且表示用值的某种运算或某种组合来预测的值。在Haar小波变换的情况下，简单地选择偶次项，去减奇次项，得差值。预测误差表示信号的细节信息。这一步骤在提升算法中被成为“对偶提升”。当信号的相关性较大时，预测是非常有效的，若信号为常数时，恒为零。（3）Update（更新） 低频概貌信号的一个关键性质是，它与原信号应具有相同的平均值，即，并且不

15、随变化。这能确保最后的变换系数是原信号的总平均。Update操作可保证该性质成立，既用细节信息子集来更新偶序号子集，既式中U为更新算子，表示对的某种运算或某种组合。对于Haar小波，可以简单地用预测误差信号更新偶子集信号，既。在提升算法中，更新称为“原始提升”，故才有“提升算法”一词。容易验证，以上三步操作相当于对信号进行一级小波变换，将它分解为低频信号和细节信号。一般地，对于提升算法存在分裂算子Split、预测算子P和更新算子U，使上述所有操作可以实现原位实现，即偶数位置用平均值重写，奇数位置用细节重写。伪码实现：提升方案实现小波分解的最大优点在于将小波分解成了几个简单的基本步骤，且每个步骤

16、都非常容易找到它的逆变换。l 提升算法中信号的重构过程（三个过程）相反地，从低频信号和细节信号恢复原信号的提升算法为(1)反更新给定和，可由下式恢复出偶序号序列 （2）反预测用反更新计算出的偶序号序列和给定的细节，可通过下式预测出奇序号序列 （3）合并通过反更新和反预测步骤，分别获得偶序号序列和奇序号序列，将它们合并即可恢复原信号。这一步骤称为 ，记作 逆懒小波变换对于Haar小波，恢复4.3.1小波分解与重构的多相位表示讨论有限冲激响应的双正交滤波器的情况。设、为双正交小波滤波器组，对应二通道Mallat算法的等价Z变换如图4-7所示。从图3-2到图3-3，是将时域表示成z域，图中与时域中时

17、序反转相对应。l 两通道分析滤波器和综合滤波器在理想重构条件下，、的约束条件设是一个信号序列， z变换为。当是一个有限序列时，称是一个Laurent多项式（将实数下的泰勒公式推广到复数）。 设小波滤波器的Z变换为。可推出。同理，。另外，由于与的巻积的Z变换等于它们Z变换的乘积，既于是，图3-2的滤波器组的等价的Z变换形式如图3-3。令，则根据二元下采样的定义，有从而（和表示了二元下采样） （图3-3）的结果又，故（反映了两个元素之间插入一个零）类似地，有因此，之前第1个求和项应等于1，是确保的一个条件；必须消除由引起的混叠，既第2个求和项应消除。于是，滤波器组对任何输入信号实现精确重构，下式是

18、二通道滤波器组完全重构条件，既PR (Perfect Reconstruction)条件。 （3-34）l PR条件的矩阵形式：当矩阵的行列式时，综合滤波器、完全由分析滤波器、确定。于是，所以， （3-35）将式（3-35）代入式（3-34），并注意到，可得 （3-36）表明，当时，完全重构条件等价于重构条件式（3-35）和式（3-36）同时成立。l 有限长度滤波器的完全重构条件：对于有限长滤波器，根据定义，是Z的Laurent多项式，而由式（3-35）知，也是Z的Laurent多项式，因此，必是一个单项式。又因为，故是一个奇数次的单项式，既代入式（3-35），整理得， （3-37）¨

19、; 一种取法是，于是式（3-37）变为， （3-38）¨ 另一种取法是，于是式（3-37）变为， （3-39）按式（3-38），有限长度滤波器的完全重构条件为 （3-40） l 多相表示的基本思想：¨ 一个多相表示的例子对于多项式 =取M=2，可写成=用替换，得这就是多项式的两相表示。¨ 设滤波器，将其分裂成的偶次幂和奇次幂二部分： 定义，和则 ， （4-4）从而有 （4-3）其中，包含了的所有偶系数，而包含了的所有奇系数。更进一步，任一给定整数，可将分解成模不同余数次幂的部分。即： +可简洁地写为：-第一类多相表示；式中，是第一类多相表示的元素，对于因果序列，求

20、和下限可从0开始。定义和的多相位矩阵为 （4-7）于是，类似地，和的多相位矩阵为 （4-8）同理， 因此，小波重构的完全条件式（3-34）可以写成 （4-9）其中，表示矩阵的转置矩阵，为单位阵。l 小波分解与重构的多相位表示解释图4-11和图3-3的等价性。设输入序列的Z变换为,则流程图(图4-12)的作用相当于对进行懒小波变换 , 即抽取的偶序列和奇序列,Z变换分别为设这两个Z变换经作用后的低频和高频部分分别为和，则=可以验证与图3-3的结果一样。也可作此验证。4.3.2 Laurent多项式的Euclidean算法l 由于、都是有限长的小波滤波器，所以和的行列式和都是Laurent多项式。

21、由式知，及其倒数都是Laurent多项式，故为Z的单项式。设=1，我们根据小波分解和重构的多相位表示，通过对多相位矩阵进行因子分解，给出小波变换的实现算法。l 有限冲激响应滤波器FIR可以描述为一系数集，范围为。FIR滤波器的Z变换是一个Laurent多项式，既于是，的次数为因此，滤波器的长度等于其相应Laurent多项式的次数加1。l 两个Laurent多项式的带余数除法对于任何两个Laurent多项式和，其中，一定存在Laurent多项式的（商）和（余数），使成立。其中，或。两个Laurent多项式的商和余数不是唯一的。例如，对于，则对于以下几种情况：1），。2），3），都满足，且。l E

22、uclidean算法如下：利用带余数除法，可以给出Laurent多项式的Euclidean算法。对于任何两个Laurent多项式和，其中，且。设=，=，从开始进行如下的递归运算：其中，%是表示取“余数”运算。则，且是一个Laurent多项式，下标是使的最小数，“”表示取最大公因子。假设，则存在m使得=0，因此，算法在步骤结束，其中，。若记，其中，“/“表示取商运算，则有=这等价于=显然，同时整除和。如果是一个单项式，则和是互为素数的。 例4.3 ，则由第一步带余除法，可得下一步带余数除法，给出所以，和是互为素数的，且辗转除法的步数为。4.3.3 多相位矩阵的因子分解下面的定理奠定了小波提升实现

23、的基础。l 定理 4.1 若的行列式等于1，既，则总存在Laurent多项式和及非零常数，使得 （4-10）其中，=0.定理证明略。主要介绍提升因子和的计算方法。首先，对和应用Euclidean算法，可得到记注意到=则由式（4-10）可得，其中。若记=，则=于是，有=所以，于是，有l 算法4.1 有限冲激响应滤波器FIR多相位矩阵的提升分解算法第1步 ，使用Euclidean算法得到第2步，计算第3步，计算例4.4 Haar小波滤波器的多相位矩阵分解。由=，可得，所以，Haar小波滤波器的多相位矩阵为，且=1令，由，得，因故，故=其中，。得： =所以， =0故 4.3.4 提升算法由（4-10

24、）及式（4-9）可推出， （4-11） (4-12)根据式（4-12）修改图4-11中小波分解部分，可得到基于提升的正向小波变换的流程图（4-13）.类似地，利用式（4-10）修改图4-11中小波重构部分，可得到基于提升的逆向小波变换的流程图（4-14）l 提升算法的实现1. 时提升算法的实现设是长度为为偶数N的一个输入信号，和表示它们的偶序列和奇序列信号。记若，分别表示序列，（）的Z变换，且则 用序列卷积可表示为其中，。l 算法4.2 正向小波变换的提升实现算法设预测步骤由奇序列预测偶序列开始。步骤1 懒小波变换 ，步骤2 提升与对偶提升¨ For i=to m，步骤3比例变换&#

25、168; For to N/2-1最后得到的和分别为小波分解的低频分量和高频分量。其中，。在算法4.2中，懒小波变换对应原信号的分裂；提升公式的意义在于用奇序列预测偶序列，而对偶提升公式的含义是用偶序列的预测误差更新。通过若干次预测和更新过程，经过比例变换，最后实现了信号的一级小波变换。 只要对正向小波变换按相反的次序进行操作，并改变正负号，立即得到逆变换。l 算法4.2*逆向小波变换的提升实现算法步骤1. 比例变换For l=0 to N/2-1步骤2 提升与对偶提升For i=m to 1，步骤3 逆懒小波变换，算法分析表明，当输入数据量很大时，提升算法比Mallat算法的设计量减少一半。2. 时提升算法的实现当时，式（410），即变为其中，记，于是，可表示为其中，从而，设是长度为的一个输入信号，和表示它的偶序列和奇序列信号。若分别表示序列的Z变换，而记则由，则 （415）l 算法4.3正向小波变换的提升算法（预测步骤由偶序列预测奇序列开始）步