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

国防科学技术大学教案课程名称：小波分析任课单位：理学院数学与系统科学系计算数学教研室授课对象：2011级数学专业本科生主讲教员：成礼智教授授课时间：2013年秋季学期小波提升格式国防科技大学理学院2013年秋季-2-教案首页课程名称Fourier分析与小波总计：40学时课程类别数学专业选修学分2讲课：40学时自主学习：6学时任课教师成礼智职称教授授课对象2011级数学专业本科生选修课程教材和基本参考资料1．成礼智，王红霞，罗永，小波理论与应用，北京：科学出版社，20042．G.Strang,TQNguyen,WaveletandFilterBanks,WellesleynCambridgePress,19963．S.Mallat,IntroductiontoWaveletsforSignalProcessing,SIAMPA,2002教学目的任务本课程是数学专业选修专业课。本课程以泛函分析与矩阵分析为基础，主要介绍Fourier变换与小波分析的基础理论,小波分析的典型应用.本课程的教学目的是在较短的学时内，提供数学专业本科生所需要的基本的小波分析基础知识知应用能力，使学生在掌握基本理论的基础上能够应用于解决实际问题。内容课时分配章内容学时数1傅里叶分析与预备知识82Haar小波分析63多分辨分析与小波构造124提升格式小波与整数变换85小波的典型应用6教研室意见教研室主任签名年月日案续页授课时间2013年秋季学期地点305-402课次授课方式理论课课时安排授课题目基于多项式分解与提升格式的小波构造教学目的、要求掌握对称双正交小波的多项式表示形式，理解提升格式原理，并掌握基于提升格式的双正交小波构造方法和有理化系数小波构造方法教学重点、难点：重点：提升格式与小波构造，难点：双正交小波的构造教学基本内容基于多项式分解的小波构造课程重点：1、基于多项式分解的对称双正交小波构造；2、提升格式的概念与提升格式小波分解难点：多项式分解的推导、提升格式小波分解一、基于提升格式的小波变换设计1995年，Sweldens利用提升格式研究了在时域内构造小波的问题，并得到基于提升格式小波的信号分解与重构的计算格式，得到称之为第二代小波的小波变换理论。与傅立叶分析框架下的小波变换理论相比，基于提升格式的小波变换具有下列特色：（1）小波的构造完全在时域内进行，无需傅立叶分析理论；（2）所用到的工具相当简单，主要为Laurent级数的Euclidean除法；（3）可以构造出所有已有的小波变换并且得到部分新的小波变换；（4）建立了与Mallat算法功能相同的提升格式算法，而运算量有一定减少（如9–7小波的提升格式比相应Mallat算法减少30%左右）；（5）运算过程简单，可以实行即位（in-place）运算。另外，可以实现整数到整数的变换，从而实现了基于小波的无损压缩技术，运算过程适宜于VLSI实现。下面通过一般的完全重构滤波器的提升格式分解，研究特殊完全重构滤波器小波的构造问题。1、提升格式的思想提升格式是在双正交小波基础上建立起来的，较早文献见[1]T.G.Marshall,Predictiveandladderrealizationofsubbandcoders.InProceedingsofIEEEWorkshoponVisualSignalProcessingandCommunication,Raleigh,NC,1992-4-[2]T.G.Marshall,AfastwavelettransformbasedontheEuclideanalgorithm.InProceedingsofConferenceonInformationScienceandSystems,JohanHopkinsUniversity,1993[3]A.A.A.C.KalkerandI.Shah.Ladderstructuresformultidimensionallinearphaseprefectreconstructionfilterandwavelets.InProceedingsofSPIEConfernce1818onVisualCommunicationsandImageProcceding,1992biorthogonalwavelets.J.Appl.andComput.HarmonicAnaly.,3(2):186-200,199696与97年，计算机视觉与图形学专业博士生Sweldens系统提出提升小波的概念，参见：[4]W.Sweldens.Theliftingscheme:acustom-designconstructionofWavelets.SIAM.Math.Analysis,29(2):511-546,1997下面看提升格式的思想。提升格式由分裂、预测与更新三步组成：1）分裂。将信号jS分裂成两个部分（通常为奇、偶划分），表示为11()(,)jjjsplitSSd2）预测。针对数据的相关性，利用1jS去预测1jd，预测算子设为P，利用子集1jd与预测值1()jPS的差代替1jd，即111:()jjjddPS经过n次分裂和预测后，可以得到如下的形式：11{,,,,}jjnjnjnjSSddd3）更新。利用分裂和预测2个步骤产生的子集11{,,,}jnjnjddd对数据1jS进行更新，即111:()jjjSSUd如果需要无损运算，分别对P与S取整即可，此时变为111:int(()),jjjddPS111:int(())jjjSSUd提升格式的分解与重构过程分别为分解（正变换）：11111111{,):():():()jjjjjjjjjSdsplitSddPSSSUd1111()()()()()()()()()()eeooeeooszhzxzhzxzdzgzxzgzxz重构（逆变换）：11111111:():():(,)jjjjjjjjjSSUdddPSSmergSd下面讨论如何实现上述的提升过程。完全重构滤波器与提升分解（复习）完全重构滤波器描述考虑两带完全重构滤波器结构。如下图1所示，整个过程按照输入、分析滤波器、下采样、信号的处理、上采样、综合滤波器、输出组成。完全重构的条件是指选择合适的1010,,,FFHH满足lnnxxˆ，其中称之为增益，l为延迟。而00,FH与11,FH分别为低通与高通滤波器。22)(0zH)(nx分解滤波器合成滤波器)(0zF22)(1zF)(1zH)(ˆnx图1两带完全重构滤波器分解过程：设}{},{kkgh为两个滤波器01(),()HzHz对应系数，即01(),(),kkikkkkHzhzHzgzze，滤波器第一步：输出（低频部分）0()()lkklkXzHzxxh；输出（高频部分）1()()lkklkXzHzdxg；第二步：“下采样”（2）滤波过程(0)(0)22,kkkkxxdd（即取出低、高通滤波器系数的偶数下表部分，保证输入等于输出，后面的理论表明可以实现信号重构），上述两步等价于下式：nnnknknknkxgdxhx)1(2)0()1(2)0(,（1）则式（1）的多项式表示为)]()()()([21)()]()()()([21)(2121121211)0(2121021210)0(zXzHzXzHzDzXzHzXzHzX（2）一般意义下，H对应于低频滤波，是一种平均算子；G对应于高频滤波，是一种差算子。直观上看，常数序列成立，否则对指NnxXn01(1)1()1(序列值为零）经过H后应仍然为1，而经过G后应变为零，即有1,0kkkkhg-6-重构过程：综合端所描述的重构过程通过“上采样”（)2完成。对式（2）得到的两个多项式)(),()0()0(zDzX，当)()0(zX“上采样”后作用到)(0zF得到低通输出，而)()0(zD“上采样”后作用到)(1zF得到高通输出，即低通输出)]()()()()[(21000zXzHzXzHzF高通输出)]()()()()[(21111zXzHzXzHzF将上两式相加得到重构序列ˆ()xn，z变换为)(ˆzX，即)()]()()()([21)()]()()()([21)(ˆ11001100zXzHzFzHzFzXzHzFzHzFzX由于完全重构要求)()(ˆzXzzXl，因此完全重构条件又可以表示为定理1设ize，则当00110011()()()()2,()()()()0lFzHzFzHzzFzHzFzHz（3）成立时，按照图4–11所示的滤波器结构构成完全重构滤波器。式（3）中的第二个等式称之为消除“混叠”，显然，消除“混叠”的方法多种多样。由（3）的第一式，)(0zH与)(1zH无公因式，因此，1001()()(),()()()FzHzpzFzHzpz对某个多项式)(zp成立。将上述两个表达式代入式（3）的第一式导出lzzFzHzFzHzp2)]()()()()[(1010由此推得mzzp)(对某个ZmC,成立。因此),()(01zHzzFm)()1()(011zFzzHmm成立。特别地，如果取)()(),()(0011zHzFzHzF，以及)()(01zHzH，则得到1976年由Croiser-Estaban-Galand提出的称之为二次镜像滤波器（QuadratureMirrorFilter）的正交滤波器，而设滤波器长度为N，取)()(01zHzzHN，则得到由Smith和Barnwell分别于1984与1985年独立提出的正交滤波器。在小波设计中，常取),()(01zHzzF)()(01zFzzH，此时，nnnnnnhghg11)1(~,~)1(。在小波设计中，设两个分解析滤波器为h~（低通）与g~（带通），作下采样得到2))(~)((,2))(~)((zgzXzhzX，而合成端滤波器则先做上采样，接着使用两个综合滤波器h（低通）和g（高通）。上述过程构成完全重构条件（3）为()()()()2,()()()()0.hzhzgzgzhzhzgzgz（4）将式（4）等价的表示为多项式矩阵形式。在双正交小波的设计中，输出系数对应的多项式分别为(),()szdz，则重构条件（4）可以表示为1/21/21/21/21/21/21/21/21()()()()()21()()()()()2szxzhzxzhzdzxzgzxzgz等价形式：（5）上述形式的矩阵描述：设212()()(),eoxzxzzxz其中，,eoxx分别为偶、奇系数多项式，即，221(),()kkekokkkxzxzxzxz，将该式代入（5），得到（6）即有定义矩阵()()()()()eeoohzgzPzhzgz，利用上式，基于Mallat算法的信号分解过程的矩阵表示为1()()()()()eToxzszPzxzdz(7)因此，Mallat算法过程可以通过矩阵向量乘积来实现。信号分解过程的流程图表示为再来看信号重构过程的矩阵表示方法。利用Mallat算法，双正交小波变换的重构过程为22()()()()()xzszhzdzgz因此有1/21/21/21/21/21/21/21/21()()()()()21()()()()()2szxzhzxzhzdzxzgzxzgz1/21/21/21/21/21/21/21/21/21/211()()()()()()()2211()()(