十三2013年本科生Fourier分析之提升分解

1、国防科学技术大学教案课程名称：小波分析任课单位：理学院数学与系统科学系计算数学教研室授课对象：2011级数学专业本科生主讲教员：成礼智 教授授课时间：2013年秋季学期小波提升格式国防科技大学理学院2013年秋季教案首页课程名称Fourier分析与小波总计：40学时 课程类别数学专业选修学分2讲课：40 学时自主学习：6学时任课教师成礼智职称教授授课对象2011级数学专业本科生选修课程教材和基本参考资料1 成礼智，王红霞，罗永，小波理论与应用，北京：科学出版社，20042 G.Strang, T Q Nguyen, Wavelet and Filter Banks, Wellesleyn Ca

2、mbridge Press,19963 S.Mallat, Introduction to Wavelets for Signal Processing, SIAM PA,2002教学目的任务本课程是数学专业选修专业课。本课程以泛函分析与矩阵分析为基础，主要介绍Fourier变换与小波分析的基础理论,小波分析的典型应用.本课程的教学目的是在较短的学时内，提供数学专业本科生所需要的基本的小波分析基础知识知应用能力，使学生在掌握基本理论的基础上能够应用于解决实际问题。内容课时分配章内容学时数1傅里叶分析与预备知识82Haar小波分析63多分辨分析与小波构造124提升格式小波与整数变换85小波的典型

3、应用6教研室意见教研室主任签名年月日案续页授课时间2013年秋季学期地点305-402课次授课方式理论课课时安排授课题目 基于多项式分解与提升格式的小波构造教学目的、要求 掌握对称双正交小波的多项式表示形式，理解提升格式原理，并掌握基于提升格式的双正交小波构造方法和有理化系数小波构造方法教学重点、难点：重点：提升格式与小波构造，难点：双正交小波的构造教学基本内容基于多项式分解的小波构造 课程重点：1、基于多项式分解的对称双正交小波构造；2、提升格式的概念与提升格式小波分解 难点：多项式分解的推导、提升格式小波分解一、基于提升格式的小波变换设计1995年，Sweldens利用提升格式研究了在时域

4、内构造小波的问题，并得到基于提升格式小波的信号分解与重构的计算格式，得到称之为第二代小波的小波变换理论。与傅立叶分析框架下的小波变换理论相比，基于提升格式的小波变换具有下列特色：（1）小波的构造完全在时域内进行，无需傅立叶分析理论；（2）所用到的工具相当简单，主要为Laurent级数的Euclidean除法；（3）可以构造出所有已有的小波变换并且得到部分新的小波变换；（4）建立了与Mallat算法功能相同的提升格式算法，而运算量有一定减少（如97小波的提升格式比相应Mallat算法减少30%左右）；（5）运算过程简单，可以实行即位（ in-place）运算。另外，可以实现整数到整数的变换，从而

5、实现了基于小波的无损压缩技术，运算过程适宜于VLSI实现。下面通过一般的完全重构滤波器的提升格式分解，研究特殊完全重构滤波器小波的构造问题。1、 提升格式的思想 提升格式是在双正交小波基础上建立起来的，较早文献见 1 T.G.Marshall, Predictive and ladder realization of subband coders. In Proceedings of IEEE Workshop on Visual Signal Processing and Communication, Raleigh,NC,1992 2 T.G.Marshall, A fast wavele

6、t transform based on the Euclidean algorithm. In Proceedings of Conference on Information Science and Systems, Johan Hopkins University,1993 3 A.A.A.C.Kalker and I.Shah. Ladder structures for multidimensional linear phase prefect reconstruction filter and wavelets. In Proceedings of SPIE Confernce 1

7、818on Visual Communications and Image Procceding,1992 biorthogonal wavelets. J.Appl.and Comput.Harmonic Analy., 3(2): 186-200, 199696 与97年，计算机视觉与图形学专业博士生Sweldens系统提出提升小波的概念，参见： 4 W.Sweldens. The lifting scheme: a custom-design construction of Wavelets. SIAM.Math.Analysis,29(2):511-546,1997 下面看提升格式的思

8、想。提升格式由分裂、预测与更新三步组成：1） 分裂。将信号分裂成两个部分（通常为奇、偶划分），表示为 2） 预测。 针对数据的相关性，利用去预测，预测算子设为，利用子集与预测值的差代替，即 经过n次分裂和预测后，可以得到如下的形式： 3） 更新。利用分裂和预测2个步骤产生的子集对数据进行更新，即 如果需要无损运算，分别对P与S取整即可，此时变为提升格式的分解与重构过程分别为 分解（正变换）： 重构（逆变换）：下面讨论如何实现上述的提升过程。 完全重构滤波器与提升分解（复习）完全重构滤波器描述考虑两带完全重构滤波器结构。如下图1所示，整个过程按照输入、分析滤波器、下采样、信号的处理、上采样、综合

9、滤波器、输出组成。完全重构的条件是指选择合适的满足，其中称之为增益，l为延迟。而与分别为低通与高通滤波器。图 1 两带完全重构滤波器分解过程：设为两个滤波器对应系数，即，滤波器第一步：输出（低频部分）；输出（高频部分）；第二步：“下采样”（）滤波过程 （即取出低、高通滤波器系数的偶数下表部分，保证输入等于输出，后面的理论表明可以实现信号重构），上述两步等价于下式： （1）则式（1）的多项式表示为 （2）一般意义下，H对应于低频滤波，是一种平均算子；G对应于高频滤波，是一种差算子。直观上看，常数序列序列值为零）经过H后应仍然为1，而经过G后应变为零，即有 重构过程：综合端所描述的重构过程通过“上

10、采样”（完成。对式（2）得到的两个多项式，当“上采样”后作用到得到低通输出，而“上采样”后作用到得到高通输出，即低通输出高通输出将上两式相加得到重构序列，变换为，即由于完全重构要求，因此完全重构条件又可以表示为定理1 设，则当 （3）成立时，按照图411所示的滤波器结构构成完全重构滤波器。式（3）中的第二个等式称之为消除“混叠”，显然，消除“混叠”的方法多种多样。由（3）的第一式，与无公因式，因此，对某个多项式成立。将上述两个表达式代入式（3）的第一式导出 由此推得 对某个成立。因此成立。特别地，如果取，以及，则得到1976年由Croiser-Estaban-Galand提出的称之为二次镜像滤

11、波器（Quadrature Mirror Filter）的正交滤波器，而设滤波器长度为，取，则得到由Smith和Barnwell分别于1984与1985年独立提出的正交滤波器。在小波设计中，常取，此时，。 在小波设计中，设两个分解析滤波器为（低通）与（带通），作下采样得到，而合成端滤波器则先做上采样，接着使用两个综合滤波器（低通）和 g（高通）。上述过程构成完全重构条件（3）为 （4）将式（4）等价的表示为多项式矩阵形式。在双正交小波的设计中，输出系数对应的多项式分别为，则重构条件（4）可以表示为等价形式： （5）上述形式的矩阵描述：设其中，分别为偶、奇系数多项式，即，将该式代入（5），得到

12、（6）即有定义矩阵，利用上式，基于Mallat算法的信号分解过程的矩阵表示为 (7)因此，Mallat算法过程可以通过矩阵向量乘积来实现。信号分解过程的流程图表示为再来看信号重构过程的矩阵表示方法。利用Mallat算法，双正交小波变换的重构过程为因此有即从而矩阵表示：信号重构过程的流程图为 完全重构条件表示为.其流程图为 双正交小波可以通过构造特殊完全重构滤波器得到。下面讨论提升分解构造方法。二、提升分解方法描述1、laurent多项式与多项式欧几里德除法定义Laurent多项式h(z)为 其中表示该多项式的次数。设两个Laurent多项式与，其中。则存在Laurent多项式（称之为剩余式）使

13、得商与剩余分别记为 。对于Laurent多项式，存在下面的Euclidean算法。Euclidean算法：设Laurent多项式与，满足。取，对于递推地做 则存在使得为Laurent多项式的公因式。 在上述过程中，商取为，则有，因此Euclidean算法过程可以等价地表示为或者等价地 （8）利用上面的两个式子得到 （9）下面讨论完全重构滤波器的类似（9）式的表示方法。为了使得与仅含有Laurent多项式，由前面的矩阵等式知道detP(z)以及其逆也为Laurent多项式，选取，其中c称之为增益，称之为延迟因子。不失一般性，选取detP(z)=1。直接利用线性方程组求解的Gramer法则得到综合

14、端滤波器与分析端滤波器的关系满足,或者等价地，有.下面在行列式的值取1的前提下讨论完全重构滤波器的提升分解格式。定义1 若多相位矩阵P(z)的行列式为1，则相应的滤波器对（）称之为补。显然，当（）构成补时，类似定义下，也构成补。定理1（提升）设（）构成补，则的任何其它补都可以表示为 （10）其中s(z)为Laurent多项式。 证明 设（）与（）均构成补，则由定义多相位矩阵P(z)的行列式为1，即有，这表明，即两个多项式互素，但是两式相减得到，由，知存在多项式满足，从而有，相应新的多相位矩阵形式为类似得到对偶多相位分解矩阵的表示为 此时的提升格式得到新的滤波器。另外还可以通过对偶提升格式来建立

15、分解与重构端的提升结构。定理2（对偶提升）. 设（）构成补，则g的任何其它补都可以表示为 （11）其中为Laurent多项式。做一次对偶提升后，新的多相位分解矩阵表示为，同样的做法对应于产生新的滤波器满足。从上面的讨论可以看出，对（对应低频）与（对应高频）加长滤波器长度分别对应于在多相位矩阵左端乘上下、上三角矩阵。根据上面的讨论，现在开始研究完全重构滤波器的提升分解问题。首先通过一个例子说明Euclidean算法实现提升分解的过程。例1 设，求的提升分解。解 进行一次Euclidean除法得到。第二次Euclidean除法得到 .上述两步的矩阵表示为所需要的除法步数满足。现在讨论多项式向量按照

16、的Euclidean算法过程 （12）事实上，由Euclidean算法，矩阵形式为 ，一直辗转相除得到相应的矩阵形式即为（12）式，因此又有 （13）利用上式构造一个2阶多项式矩阵如下： (14)当为偶数或奇数时，上述矩阵的行列式分别为1和-1。根据前面的讨论上式构成一种完全重构滤波器多相位矩阵的提升分解。相应的多项式构成多项式的补，而多项式也构成多项式的补，因此根据定理1，存在多项式满足 （15）而如果利用实施Euclidean算法，则上面的（15）式变为 （16）（15）与（16）的进一步讨论。 需要两个等式： （17）因此，（15）与（16）两式可以统一表示成 与 另外，又由于，因此上面

17、的两式进一步表示为 (18)或者 (19)反复使用利用（17）实施对角矩阵与单位三角矩阵的顺序交换，多项式表示仍然沿用原来的记号，则（18）与（19）还可以等价地表示为或者上面讨论的都是完全重构滤波器的提升分解问题，小波作为一种完全重构滤波器，同样存在提升分解格式，下面举例说明小波的提升分解过程。 例2 Haar小波的提升分解解 分析和综合端各种滤波器函数为使用Euclidean算法得到多相位矩阵满足， （20）按照式（20）作向前的提升变换格式得到 （21）而逆变换为 （22）再来看行列式为整数的对角矩阵提升分解，事实上 (23)或者 （24）二、 9-7小波的多相位提升格式分解在提升格式的

18、小波变换出现之前，小波分解都是通过Mallat算法来完成的，而提升格式的小波变换的显著特点之一是：相比于 Mallat算法，提升格式分解算法运算量由一定减少，不同的小波运算量减少的程度不一样，一般减少的幅度在25%到50%之间。由于CDF 97小波已经作为标准压缩用小波变换，因此下面主要以97小波为例来进行讨论。对于97双正交对称小波而言，提升格式分解的过程可以描述为： （12）（12）的实现过程为： (13)容易看出，上述过程需要6次法，8次加法，一共需要14次浮点运算。而Mallat算法需要23次浮点运算，因此利用提升格式可以获得46%的减少。三、 基于提升格式分解的完全重构滤波器设计例1

19、、首先讨论4-4带双正交完全重构滤波器的提升分解解 此时多相位矩阵为 取利用Euclidean 算法，得到；于是因此若定义可以直接求解得到根据上述讨论得到 （14）或者 （15）讨论：从上面的过程可以看出，只要系数则按照（14）或（15）得到完全重构滤波器，又如果还添加上消失矩与Daubechies不等式条件，则得到小波滤波器。例如，取在第四章曾经得到过的2带双正交有理小波，分解与重构端的滤波器系数分别为，相应的提升分解为 (16) 例2、双正交对称97完全重构滤波器的提升分解。设多相位多项式分别为以及.为了建立一般得97双正交对称完全重构滤波器的提升分解，考虑两种情况（1） 此时利用Eucl

20、idean 算法，设 则有 其中 ，以及; ，则 其中 ，; ，则 其中，; ，则 其中 上述过程的提升分解为 (17) ( 2) 此时 97滤波器表示为添加消失矩条件：消失矩，得到相应提升分解可以表示为 (18)或者，等价地 (19)此时滤波器系数满足 (20)以及,式（17）为一般97双正交完全重构滤波器的提升分解格式，为了得到相应的小波必须对其系数添加一定的限制，如组成的滤波器函数需要满足消失矩条件，Daubechies不等式成立等。而（18）与（19）则是在添加消失矩以及满足Daubechies条件下得到的。下面进一步讨论式（17）构成97小波系数的条件。将式（17）表示为下面的形式 （21）展开（21）得到 (22)设分解与重构端97双正交小波的消失矩分别为2和4，并利用归一化条件 ，得到下列线性方程组 (23)求解上述方程组得到含一个自由变量的解 （24）式(24)给出了满足消失矩条件与一种归一化条件下的97对称双正交完全重构滤波器系数。换句话说，对于任意实数，式(20) 与式（24）在用于图像处理时经过非线性处理后都能