双正交小波变换提升格式的简化算法

分类号密级UDC编号桂林电子科技大学硕士学位论文题目基于提升小波变换的图像压缩方法研究（英文）TheStudyofImagecompressionarithmeticbasedonLiftingWaveletTransform研究生姓名：李辉指导教师姓名、职务：朱芳来教授申请学位：工学硕士学科、专业：控制理论与控制工程提交论文日期：2006年4月论文答辩日期：2006年6月 年月日独创性（或创新性）声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得桂林电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名： 日期：关于论文使用授权的说明本人完全了解桂林电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属桂林电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为桂林电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。（保密的论文在解密后遵守此规定）本学位论文属于保密在____年解密后适用本授权书。本人签名： 日期：导师签名： 日期：基于提升小波变换的图像压缩方法研究i摘要提升算法以其通用性和灵活性及高效的实现方法，成为目前小波领域研究的热点问题。图像信息是人们认识世界的主要信息来源，如何用较少的数据来表示图像信号，是许多研究领域需要解决的问题。本文主要对提升格式的小波变换算法，及提升小波变换后如何进行小波系数的有效压缩进行研究。研究结果具体如下：1)在用传统的Euclidean算法对第一代小波滤波器进行提升时，发现并不是所有小波滤波器的提升格式都很简单。有时经过提升之后算法虽较之原来的第一代小波的卷积运算有所简化，但仍然要进行效率不高的卷积运算。为了使每一步的提升或对偶提升更加简洁，本文通过重新定义多项式带余除法，提出了一种改进的Euclidean算法并在此基础之上给出了一种提升格式的简化算法。在该提升实现算法中，用简单的数乘运算代替了原来小波变换提升实现算法中的卷积运算，使得算法中的核心部分——提升及对偶提升步骤的计算更加简单直接，更加易于硬件实现。2)通过分析提升小波变换后各个子块的小波系数与整个图像变换后的小波系数之间的关系，发现每个子块的子带在整个图像的相同子带内的空间位置，与子块在原始图像中的空间位置相同。利用该结论，很容易的实现小波变换及其编码的并行处理以及ROI特殊区域编码。3)通过引入EBCOT的子带分块编码的思想，提出了一种基于提升小波变换的改进SPIHT算法。该算法不但具有传统SPIHT算法的优点，而且能实现码流多分辨率表示和ROI区域编码。试验结果表明，该算法是综合性能比较好的一种小波系数压缩算法。4)基于前面的工作，给出了一种有效的基于提升小波变换的图像压缩系统。该系统把图像分割成小块后，单独进行提升小波变换及编码处理，并在解码端恢复后进行重新组合。试验结果表明该系统在码流的多分辨表示和ROI区域编码情况下的压缩压缩效果都比较好。关键字：图像压缩；简化的提升格式；小波变换；SPIHT压缩算法；Euclidean算法PAGE1AbstractBecauseofitsgenerality,flexibilityandhighimplementationefficiency,atpresent,theliftingschemehasbeenahotquestioninthefieldsofwavelet.Theimagesignalsarethemainsourceofinformationthroughwhichpeoplecanknowtheworld.Sohowtoexpresstheimagesignalsbyusinglessdatahasbeenakeyquestionmanyfieldsneedtosolve.Inthispaper,themainjobistostudythealgorithmofliftingwavelettransformandhowtocompressthewaveletcoefficientseffectively.Thestudyresultscanbesaidasfollow:1)AtthetimeofliftingthefirstgenerationwaveletfiltersbyusingthetraditionalEuclideanalgorithm,wefindnotallliftingschemeofthefiltersareverysimple.Sometimesitmustemployconvolutionoperationswithverylowimplementationefficiency,thoughthealgorithmhasbeenalittlesimplerthanbeforeafterlifting.Tomakeeachliftingordual-liftingstepsimpler,inthispaperasimplifiedliftingschemeforwavelettransformisproposedbyredefiningtheEuclideanalgorithmwithanewdivisionforLaurentpolynomials.Inthesimplifiedalgorithmtheconvolutionoperationisreplacedbysimplenumericdivisionoperation.Itmakesthekernelpartofthealgorithm(liftingandduallifting)andhardwarerealizationeasier.2)Afterliftingwavelettransform,byanalyzingtherelationsofthecoefficientsbetweeneachsonblockandthewholeimage,wecanfindtheindexpositionofthesub-bandofeachsonblockinthesamesub-bandofthewholeimageissameasthatofthesonblockintheoriginimage.Usingtheconclusion,theparallelprocessingofwavelettransformandcoding,andROIcodingcanberealizedveryeasily.3)ByintroducingtheideaoftheblockcodinginEBCOT,amodifiedSPIHTalgorithmisproposed.ThealgorithmnotonlyhasalltheadvantagesofconventionalSPIHT,butalsocanrealizebit-streamwithmulti-resolutionandROIcoding.Theexperimentresultsshowitisagoodalgorithmforwaveletcoefficientscompression.4)Onthebasisoftheworkabove,amoreefficientimagecompressionsystembasedonliftingwavelettransformisgiven.Afterdividingtheimageintoblocks,eachblockisliftingwavelettransformedandencodedlonely,andthenatthetimeofdecoding,allthedataisrecombined.Theexperimentresultsshowthesystemhasverygoodperformancetothemulti-resolutionexpressionofthebit-streamandROIcoding.Keywords:Imagecompression;CompactLiftingScheme;WaveletTransform;SPIHT;EuclideanAlgorithm.目录摘要 iAbstract ii目录 iii第一章绪论 1§1.1图像压缩编码的必要性 1§1.2图像压缩编码的可能性 2§1.3小波图像压缩技术研究进展 3§1.3.1小波提升技术的研究进展 3§1.3.2图像压缩编码技术的研究进展 4§1.4本文研究的内容 6第二章小波变换 8§2.1连续小波变换 8§2.2离散小波变换 9§2.3多分辨分析及Mallat算法 9§2.3.1一维正交多分辨分析及Mallat算法 10§2.3.2二维张量积多分辨分析及Mallat算法 15§2.4紧支撑双正交小波基的构造 20§2.5本章小结 24第三章提升小波变换的简化实现 25§3.1小波分解与重构的多相位表示 25§3.2Laurent多项式的Euclidean算法 27§3.3改进的Laurent多项式Euclidean算法 28§3.4多相位矩阵的因子分解 32§3.5小波变换的提升实现的传统算法 36§3.6小波变换的提升实现的简化算法 37§3.7提升算法举例 39§3.8整数小波变换 43§3.9本章小结 44第四章基于提升小波变换的图像压缩编码 45§4.1常用的小波编码算法简析 45§4.2新小波编码算法的一些必要准备 47§4.2.1 嵌入式编码 47§4.2.2 一维信号分段下的提升小波变换 47§4.2.3 二维图像信号分块下的提升小波变换 48§4.2.4 边界问题处理 51§4.2.5 细节树组块重要性的概念 52§4.3一种改进的SPIHT算法 53§4.3.1SPIHT编码算法 54§4.3.2改进SPIHT编码算法 56§4.4ROI特殊区域编码 58§4.5一种基于提升的小波编码系统 59§4.6新系统性能分析 63§4.7本章小结 63第五章试验及结果分析 64第六章结论 69参考文献 70发表论文目录 73致谢 74第一章绪论§1.1图像压缩编码的必要性随着经济全球化进程的不断推进，世界各国之间的联系更加紧密，人们之间的交流更加的广泛和频繁。对信息的需求量大大的增加。人们不仅要和周围的人进行面对面的交流，还需要与远方的人们进行远距离交流。这就要求我们要对信息进行远距离的传输。而据分析，人类感知的所有外部信息当中，声音和图像占据了其中的主要部分。其中，通过听觉接收的信息约占接收到总信息量的20％，通过视觉接收的信息则占到60％以上[38]。因此，人们要了解远处的信息，就必然要对声音和图像信号进行存储和远距离传输。而对其中图像信号的存储和传输尤为重要。然而，由于图像信息（包括静止图像和活动图像）是高维信息，图像信号的内容非常复杂，其数据量非常庞大。从而给图像信息的存储、处理和传输都带来许多问题。给信息的远距离交流带来不便。例如，对于真彩色活动图像，其分辨率为，每个分量的精度为，则每分钟的数据量为存储1分钟这样的视频需要近的存储空间。如果要进行实时传输，需要同时占用路数字电话线（每路）。如果不进行压缩处理，存储和传输如此海量的数据，所消耗的资源是难以接受的。为此，人们想尽各种方法去寻找新的图像替代表示方法以减少表示一幅图像所需的数据量，这就是图像编码所要解决的主要问题，在这个意义上图像编码也可以称作图像压缩。图像压缩的主要目的就是：在有限的存储空间内，存放更多的图像信息。减少数据量，以便于在有限的信道容量内传输更多的图像信息。若不经过压缩就直接进行传输或存储，将消耗大量的通信和存储资源，给图像信息传输与存储带来困难，增加了信息保持的成本。显然，压缩比例越大，有限存储空间和有限的信道容量就可以存放和传输的图像信息就越多。在图像压缩领域进行研究的目的就是寻找到一种有效压缩编码方法使得图像压缩比例尽可能的大，同时要或者保持图像的内容不变；或者把内容的差别控制在一定的范围内；或者保证一定观察效果的主观质量。第一种情况称为无失真或无损编码，后两种情况为有限失真或有损编码。根据不同的需求，应用在不同的场合。在一些医学诊断和航天探测图像就需要无损压缩编码，而对于一般的日常图像多采用有损压缩编码。有损压缩要比无损压缩的效率要高，且压缩比更大，同时图像质量没有明显的损伤。§1.2图像压缩编码的可能性图像信号之所以能够压缩，是因为图像中存在着大量的冗余信息。研究图像压缩，就是要研究如何减少或者消除这些冗余。在数字图像中，有3中最基本的数据冗余[39]：1.编码冗余图像编码中，用码本表示数据图像，如图1.1所示码本由一系列码字组成，每个码字是一个符号序列，其中的符号个数称为码长。图1.1图像编码数据的一般结构设离散随机变量表示图像的灰度值，，出现的概率近似为其中，表示灰度总级数；表示第个灰度级出现的次数；表示象素总数。编码中若用个比特表示的值，则每个象素所需的平均比特数为：不同的编码方法将得到不同的。如果编码所用的码本不能使达到最小，则说明存在编码冗余。产生编码冗余是没有充分利用编码对象的概率特性所致。例如对每个象素灰度采用自然二进制码编码（如均匀量化的PCM码），不论灰度级出现的概率大小，一律赋予同样码长的比特数，就会产生编码冗余。而统计编码（如Huffman编码）就是利用图像的统计特性减少编码冗余的编码方法。2.象素间冗余象素间冗余是一种与象素间相关性有关的数据冗余，也称作空间冗余或几何冗余。对于一幅随机图像样本，帧内存在象素间冗余；对连续序列图像，则表现为帧间冗余。存在象素间冗余的图像，其每个象素值都可用与它邻近的若干象素值的线性组合来表示，或者说可由邻近象素值进行预测。减少象素间冗余的典型编码方法就是预测编码法。3.心理视觉冗余心理视觉冗余是与视觉信息及人的视觉特性密切相关的一种数据冗余。人眼是图像最终的接受者，而由于人眼对各种视觉信息有着不同的视觉灵敏度，因此，去除那些对于人眼并不敏感的信息（冗余信息），人眼并不会感觉到图像质量的变化。从而达到压缩数据的目的。量化就是去除心理视觉冗余的过程。其将导致视觉信息的损失，因而是不可逆的。量化是造成图像信息损失的主要根源，也是图像高效压缩编码的关键。充分利用人眼的视觉特性，就可以得到高效的图像压缩编码方法。§1.3小波图像压缩技术研究进展§1.3.1小波小波变换的概念是由法国从事石油信号处理的工程师J.Morlet在1974年首先提出的。它与Fourier变换、窗口Fourier变换（Gabor变换）相比，这是一个时间和频率的局域变换，因而能有效的从信号中提取信息，通过伸缩和平移等运算功能对函数或信号进行多尺度细化分析（MultiscaleAnalysis），解决了Fourier变换不能解决的许多困难问题，小波变化被誉为“数学显微镜”，它是调和分析发展史上里程碑式的进展。小波分析的应用是与小波分析的理论研究紧密地结合在一起地。现在，它已经在科技信息产业领域取得了令人瞩目的成就。电子信息技术是六大高新技术中重要的一个领域，它的重要方面是图像和信号处理。现今，信号处理已经成为当代科学技术工作的重要部分，信号处理的目的就是：准确的分析、诊断、编码压缩和量化、快速传递或存储、精确地重构（或恢复）。从数学的角度来看，信号与图像处理可以统一看作是信号处理（图像可以看作是二维信号），在小波分析地许多分析的许多应用中，都可以归结为信号处理问题。现在，对于其性质随实践是稳定不变的信号，处理的理想工具仍然是傅立叶分析。但是在实际应用中的绝大多数信号是非稳定的，而特别适用于非稳定信号的工具就是小波分析。小波分析用于信号与图像压缩是小波分析应用的一个重要方面。它的特点是压缩比高，压缩速度快，压缩后能保持信号与图像的特征不变，且在传递中可以抗干扰。基于小波分析的压缩方法很多，比较成功的有小波包最好基方法，小波域纹理模型方法，小波变换零树压缩，小波变换向量压缩等。小波变换理论是近几年兴起的时（空）频域分析理论，通过对原始图像进行小波变换，可以将图像信号由时间域（空间域）表示变换到小波域表示。利用小波变换的正交或双正交变换特性，解除图像像素间的相关性，消除图像信号在空间的冗余，并集中图像信号的能量，为后面的系数量化、系数位建模、算术编码等提供前提，为高效的图像编码奠定基础。传统的卷积小波（第一代小波）变换，由于采用卷积运算方法，过程复杂，运算量大，实时性较差，不利于硬件的实现。1995年Sweldens提出了一种不依赖于傅立叶变换的新的小波构造方法——提升格式（Liftingscheme）[1-5]，称之为第二代小波变换。这种提升格式不但保持了第一代小波的特性，同时又克服了其平移和伸缩的不变性。许多中外学者对提升格式小波变换进行了广泛研究，取得了丰硕的成果[1-12,19,20]。小波提升方案为第一代小波变换提供了一种新的更快速的实现方法。第一代小波变换都可以通过Euclidean算法得到其等效的提升结构[1,6]。提升方法不但是构造第二代小波的基本工具[5]，还使得第一代小波的构造不再依赖于Fourier变换构造，大大降低了构造第一代小波的难度，并且已经证明提升可以实现所有的第一代小波变换[1,6]。利用提升方案可以构造出不同的小波，如Daubechies双正交小波[7]和差值双正交小波[8]。提升方法提供了一个有效的构造非线性小波的方法,构造出的非线性小波同传统小波变换相比,计算简单快速,而且适合于自适应、非线性、非奇异采样和整数到整数的变换。双正交小波变换因为具有线形性而广泛应用于图像压缩领域，目前研究证明任何具有FIR结构的双正交小波变换都可以由惰性变换经过有限步交替的提升和对偶提升过程得到[1]。小波提升方案的复杂度只有原来卷积方法的一半左右，而且实时性好，运算简单，因此成为计算离散小波变换的主流方法。离散小波变换提升实现的快速算法是最近研究的热点。新一代静止图像压缩标准JPEG2000也将离散小波变换纳入标准之中，成为其编码系统的核心算法。§1.3.2图像压缩编码技术的研究进展 上个世纪40年代末脉冲编码调制技术（PCM）出现不久，人们就开始了对电视信号的数字化研究。经典的图像编码方法是基于Shannon信息论，其中最基本的Huffman编码（熵编码）、预测编码和变换编码理论就产生并发展于上个世纪五六十年代，并影响至今，在目前已知的图像压缩编码的国际标准中，仍然被普遍使用。之后，人们在探索一些新的高效编码方法方面不断取得进展。例如，算术编码已经被许多编码标准所采用，其最大的优点就是可以在编码过程中调整信号的概率模型，是一类高效、普遍适用的无失真编码；其他还有矢量量化、方块截断编码、比特面编码、亚抽样与内插、子带编码和小波变换编码等。另外，随着人们对视觉特征的认识不断提高，出现了许多结合人类视觉系统特性（HVS）和多种编码算法的综合算法，编码效率不断改善。这些基于Shannon信息理论发展起来的经典图像编码方法，也称为第一代编码方法。上个世纪90年代以来，Kunt等人提出了第二代编码的概念。他们认为传统的编码方法是基于信号波形的方法，衡量编码方法的效果主要以重建信号与原始信号的波形一致性程度为评价准则；而新一代编码方法则是基于对象模型的描述方法，可获得比经典算法要高的压缩效率。但第二代编码方法实现起来大都比较复杂，而且在对一般的自然图像进行处理时，所获得的编码增益也没有理论上预期的好。因此，第二代编码方法尚处于理论研究阶段。有待进一步研究出复杂度较低，较实用的编码方法。近年来，一种新的变换编码技术——小波变换编码，日益受到人们的重视，特别是1993年J.M.Shapiro提出嵌入式零树小波编码（EmbeddedZerotreeWaveletsEncoding，EZW）算法[13]，该算法不但具有优良的压缩性能，还提供了天然的多尺度、多分辨率的图像描述方法。是一种有效且计算简单的图像压缩技术，受到这一方法的启发，人们后来开发出了更加有效的SPIHT算法(Setpartitioninginhierarchicaltrees)[14]，CREW[15](Compressionwithreversibleembeddedwavelets)，集合分裂嵌入块编码器SPECK[30]算法以及最佳截断嵌入码块编码（Embeddedblockcodingwithoptimizedtruncation，EBCOT)[17]算法等。由于小波提升算法和EBCOT小波系数编码算法的优越性能，国际标准化组织（ISO）和国际电联电信委员会（ITU-T）于2000年底制定出JPEG2000新的图像压缩标准。该标准具有以下6个部分[27,28,38,40]：⑴JPEG2000图像编码系统（核心部分）⑵应用扩展（在核心上扩展更多特性）⑶运动JPEG2000⑷兼容性（即包容性与继承性）⑸参考软件（目前主要为JAVA与C程序）⑹复合图像文件格式（如传真式的服务等）与以前的JPEG标准小比，JPEG2000具有优越的压缩性能。这是因为它采用了先进的EBCOT编码技术。其优越性能可以分下面六个方面来说[27,28,38,40]：⑴可以实现渐进式传输，这是JPEG2000的重要特征之一。它先传输图像的大体轮廓，然后逐步传输其他数据，不断地提高图像质量。这样图像就由朦胧到清晰显示出来，从而充分利用有限的带宽。而传统的JPEG只能从上到下逐行显示，无法做实现渐进式传输。⑵同时支持有损、无损两种压缩方式。而JPEG只支持有损压缩。⑶支持感兴趣区域（Regionofinteresting，ROI）进行特别的压缩编码。不但可以指定图像上任意区域的压缩质量，还可以指定哪个部分先进行解压处理。这在大大降低图像尺寸方面起到很大作用。⑷可达到较高的压缩比。在具有和传统JPEG类似质量的前提下，其压缩率要比JPEG高20%-40%左右。⑸在颜色处理上，具有更优秀的内涵。与JPEG相比，JPEG2000同样可以用来处理多达256个通道的信息。而JPEG仅局限于RGB数据。也就是说，JPEG2000可以用单一的文件格式来描述另外一种色彩模式，比如CMYK模式。⑹能使基于WEB方式多用途图像简单化。由于JPEG2000图像文件在它从服务器下载到用户的WEB页面时，能平滑地提供一定数量的分辨率基准，WEB设计师们处理图像的任务就简单。例如我们经常会看到一些提供图片欣赏的站点，在一个页面上用缩略图来代理较大的图像。浏览者只需点击该图像，就可以看到较大分辨率的图像。不过这样WEB设计师们的任务就在无形中加重了。因为缩略图与它链接的图像并不是同一个图像，需要另外制作与存储。而JPEG2000只需要一个图像就可以了。用户可以自由地缩放、平移、剪切该图像并能得到他们所需要的分辨率与细节。§1.4本文研究的内容文献[1]中指出，第一代小波变换都可以通过Euclidean算法得到其等效的提升结构。提升算法为第一代小波变换提供了快速的实现方法。但是在一些情况下，这种优势并不是很明显。例如，若两个Laurent多项式的商，仍是一个比较复杂的Laurent多项式，这样该提升步骤就较为复杂，仍然要进行卷积运算。虽比原来稍有简化但仍然很复杂。本文就针对第一代小波提升实现算法中存在的这些问题进行研究，提出了一种使得每一步提升都很简单的提升实现算法。另外，本文还在第二代提升小波变换的基础上，对变换后的小波系数如何进行有效的压缩编码进行研究。目前比较流行的小波系数编码方法有EZW算法、SPIHT算法及被JPEG2000采用的EBCOT算法等。这些算法特别是EBCOT算法，都具有优越的性能。但是它们仍然有不足之处。本文针对这些问题进行了分析，并对这些算法进行改进和创新，提出了一种更为有效的小波编码方案。本文的主要创新点具体如下：1)在传统的Laurent多项式Euclidean算法的基础上，通过重新定义Laurent多项式除法，给出了一种改进的Laurent多项式的Euclidean算法，并在该算法的基础上提出了一种小波变换提升实现的简化算法。在该提升实现算法中，用简单的数乘运算代替了原来小波变换提升实现算法中的卷积运算，使得提升算法中的核心部分——提升及对偶提升步骤的计算更加简单直接，更加易于软件和硬件的实现。如果利用该算法对具有线形相位的小波滤波器（如JPEG2000有损压缩时推荐使用的(9-7)小波滤波器）进行提升实现，就可以使每一步提升都是简单的单项式，完全摆脱了复杂的卷积运算。2)研究原始图像分割后各个子块的提升小波变换结果与整个图像的提升小波变换结果之间的关系后发现，变换后，每个子块的子带在整个图像的相同子带内的空间位置，与该子块在原始图像中的空间位置相同。利用这个结论，可以在编码端把原始图像分块并进行提升小波变换后，进行单独编码传输；而在解码端每接收完一个子块的编码数据并解码后，按照空间位置关系，安放到整个图像的相应子带的相应空间位置上。把解码的数据安放好之后，进行提升小波逆变换，就可以恢复原始图像。另外，利用该结论还可以很容易的实现小波变换及其编码的并行处理和ROI编码。3)通过引入EBCOT的子带分块编码的思想，对传统的SPIHT压缩编码算法进行改进，提出了一种基于提升小波变换的改进SPIHT算法。该算法不但具有传统SPIHT算法的优点，而且能实现码流的分辨率可伸缩性和ROI区域编码。试验结果表明，该算法是综合性能比较好的一种小波系数压缩算法。4)给出了一种有效的基于提升小波变换的图像压缩系统。该系统利用分块理论，把图像分割成小块后，单独进行提升小波变换，对各个图像块单独利用带有自适应二进制算术编码器的改进SPIHT算法进行编码，并在解码端恢复后进行重新整合。正文§4.6中分析并给出了该系统的各种优越性能，第五章的测试结果表明该系统在分辨率可伸缩性和ROI区域编码情况下的压缩压缩效果都比较好。第二章小波变换§2.1连续小波变换在小波分析中，主要讨论的函数空间为。指上平方可积函数构成的函数空间，即若，则称为能量有限的信号。也常称为能量有限的信号空间。如果，其傅立叶变换为满足容许性条件（AdmissibleCondition）：(2-1)即有界，则称为一个基小波或母小波（MotherWavelet）。将母小波经过伸缩和平移后，就可以得到一个小波序列：(2-2)其中，，且。称为伸缩因子，为平移因子。定义下式为关于基小波的连续小波变换（或积分小波变换）。其中，表示对的共扼运算。显然，变换后的函数是二维的，即小波变换把原来的一维信号变换为二维信号。以便分析信号（或函数）的时－频特性。而下面的变换为关于基小波的逆小波变换。小波逆变换把二维信号重构回原来的一维信号。 从小波的容许性条件（2-1）可以知道，母小波是一个振荡且能量有限的函数。并且在时域上是快速衰减的。从容许性条件，容易推出(2-3)即。这是因为，若，则当时，，即无界。 小波变换的实质在于将空间中的任意函数表示成为其在具有不同伸缩因子和平移因子的之上的投影的叠加。与傅立叶变换（仅将投影到频率域）不同的是，小波变换将一维时域函数映射到二维“时间－尺度”域上，因此在小波基上的展开具有多分辨率的特性。通过调整伸缩因子和平移因子，可以得到具有不同时－频宽度的小波以匹配原始信号的任意位置，达到对信号的时－频局部化分析的目的。§2.2离散小波变换连续小波变换中的尺度因子和平移因子都是连续变化的实数，在应用中需要计算连续积分，在处理数字信号时很不方便。主要用于理论分析与论证。在实际问题的数值计算中常采用离散形式，即离散小波变换（DWT）。DWT可以通过离散化CWT中的尺度因子和平移因子得到。通常取把其带入式（2-2）可以得到这时的小波函数就是离散小波。相应的离散小波变换为特殊的，取，可以得到二进小波（DyadicWavelet）： 在实际应用中，为了使小波变换的计算更加有效，通常构造的小波函数都具有正交性，即 从理论上可以证明将连续小波变换离散成离散小波变换，信号的基本信息并不会丢失，相反由于小波基函数的正交性，使得小波空间中两点之间因冗余度造成的关联得以消除；同时，因为正交性，使得计算的误差更小，使得变换结果时－频函数更能反映信号本身的性质。§2.3多分辨分析及Mallat算法多分辨分析（Multi-resolutionAnalysis，MRA）是由S.Mallat引入的，他从空间概念上，形象地说明了小波的多分辨特性，将在此之前所有小波变换理论统一起来。1989年，Mallat在小波变换多分辨分析理论与图像处理的应用研究中受到塔式算法的启发，提出了信号的塔式多分辨分析分解与重构的快速算法，即著名的Mallat算法。Mallat算法在小波分析中的地位相当于快速傅立叶变换（FFT）在经典傅立叶分析中的地位。本节就介绍一维和二维张量积情况下的多分辨分析及相应的Mallat算法。至于三维及三维以上情况下的多分辨分析，由于在二维离散的数字图像的处理中不涉及，在此不作介绍(可参见文献[12，P138-144])。§2.3.1一维正交多分辨分析多分辨分析是用小波函数的二进伸缩和平移表示函数这一思想的更加抽象复杂的表现形式，它重点处理整个函数集，而非侧重处理作为个体的函数。MRA形成了构造正交小波基的一个框架，常用的B-样条正交小波基和Daubechies紧支撑正交小波基都可看作是该框架下的产物。下面就给出多分辨分析的严格定义：定义2.1称中的闭子空间序列为一个（二进）多分辨分析，如果满足下列条件：单调性：逼近性：伸缩性：平移不变性：Riesz基存在性：存在函数，使得构成的一个Riesz基。即函数序列线性无关，且存在常数和，满足，使得对任意的，总存在序列使得且，。则称为尺度函数，并称生成的一个多分辨分析。特别的，若构成的一个标准正交基，则称为正交尺度函数，相应的，称生成的一个正交多分辨分析。MRA本质上给出了人类视觉系统对物体认识的数学描述。当人眼观察某一物体时，如果设为人眼在尺度下所感知的物体信息（如物体的一个侧面），而当尺度增加到时，所摄取的信息量为（如物体的全貌）。尺度的增加可以看作是观察距离的较少，因而，能更深入的认识物体，即有，。在多分辨分析中，称为逼近空间。一般的，不同的逼近空间对应着不同的尺度函数，从而对应不同的多分辨分析。在实际中，比较有用的是一类具有紧支撑特性的尺度函数。若为尺度函数生成的中的多分辨分析，则必然存在系数序列，使得以下尺度关系，即两尺度方程成立：（2-4）这是因为，，且构成的一个Riesz基，故存在系数，使得。尺度方程（2-4）在频域的表达式为（2-5）其中为系数序列的傅立叶变换。假设是数字滤波器的脉冲响应，则该式将离散滤波器和多尺度分析联系起来。根据文献[12]中的定理2.34，可以知道，若，则是标准（规范）正交系，等价于恒等式对于几乎所有的成立。 利用这个定理，可以通过将尺度函数正交化的方法，得到一个正交尺度函数。若令(2-6)则，且构成的一个标准正交基，而对于任意的，构成一个标准正交基。从而生成一个正交多分辨分析。事实上，对任意，由多分辨分析的定义可知，。则存在系数序列使得用代替，可得。因此，构成的一个基。此外，对于任意，有则可以知道，对于任意的，是标准正交的。 但是，通常情况下不是的标准正交基。通过正交多分辨分析，我们可以得到的一个标准正交基。 由于，则存在在中的正交补空间，使得上述空间正交分解过程可对逼近空间递归进行下去，可用下图表示。则，。令，可得到的正交和分解：(2-7)函数称为小波，如果。如果构成的一个标准正交基，则由可以推出构成的标准正交基，从而构成的标准正交基。这时称为小波空间，为正交小波。 定理2.1设正交尺度函数生成了正交多分辨分析，是满足两尺度方程的滤波器，令(2-8)其中，满足，则为小波，且它的平移系构成的标准正交基，其中是在中的正交补。从而，构成的一个标准正交基。 上述定理等价为以下几点： 1）是标准正交的。 2）对任意。 3）中的每个函数都可表示为的线性组合。 4）是一个小波，即。 定理2.1是一个非常重要的定理，它给出了一种根据正交尺度函数来构造正交小波的一般方法。具体推导过程如下：利用式（2-6）由计算利用式（2-5）计算由，计算相应的傅立叶变换式根据小波方程的频域表示式计算上述构造正交小波基的整个过程可总结为， 根据上面的过程，得到小波基之后，我们就可以用其来表示中的任意函数，等式两边同时对取内积，并注意到是的一个标准正交基，可以得到，则有特别的，对于中的任意子空间，有从而，可以得到中的任意函数都存在如下多分辨分析表示，其中表示函数的低频部分，而表示在不同分辨率下的高频成分。在式(2-9)两边同时与做内积，并利用及其二进伸缩和平移的正交特性，可得到类似的有同时对等式（2-9）两边与做内积，有其中，是由正交尺度函数的两尺度方程对应的滤波器系数序列，可看作是低通滤波器；由式给出，可看作是高通滤波器。由此，可以得到一维情况下，离散小波变换的Mallat算法。其卷积表达形式为其中，表示滤波器的共轭反转；表示与的卷积；表示对卷积的二元下抽样；表示对序列的二元上抽样；为二元上、下抽样算子。小波分解与重构的迭代过程如图2.1所示。相应二通道滤波器组表示见图2.2。a）小波分解过程b）小波重构过程图2.1一维信号小波分解与重构的迭代过程示意图图2.2一维信号小波分解与重构的二通道滤波器组表示（括号中选项表示双正交滤波器） 由于除了Haar小波外，没有同时具有对称性和紧支撑性的正交小波。紧支撑性，意味着小波滤波器的长度是有限长的，以便于计算（如果长度无限，将难以处理）。对称性，意味着小波滤波器的线性相位，线性相位可以保持原信号的相位不变。紧支撑性和对称性在信号处理中具有重要的意义。为了同时具有这两种性质，就必须放弃小波的正交性，而采用双正交小波。下面就来介绍双正交多分辨分析的概念、双正交小波基在函数多分辨表示中的作用及双正交小波分解与重构的滤波器组算法。定义2.2设函数，称是的一个Reisz基，如果它是线性无关的，且存在常数和，满足，使得对任意的，总存在序列满足：且，。 设和是的两个多分辨分析，它们的尺度函数分别为和，如果下述条件成立：和满足如下正交性条件：(2-10)这时称和为对偶尺度函数。令是在中的补空间，是在中的补空间，使得其中，为直和运算。如果存在中的函数和序列满足：使得且是的一个Reisz基，是的一个Reisz基，从而和都构成的Reisz基。则称是的一个双正交多分辨分析。这时称和为对偶双正交小波。 在双正交多分辨分析的定义中，如果，则由式（2-10）可知，为正交尺度函数，它生成的一个正交多分辨分析。这说明正交多分辨分析是双正交多分辨分析的特殊情况。类似正交小波分解和重构过程的推导，可以得到双正交小波变换的Mallat算法如下：选取图2.2中括号中的滤波器，可以得到双正交小波分解与重构对应的二通道滤波器组表示。§2.3.2二维张量积多分辨分析及Mallat算法前面介绍的是一维小波及其变换，为了能够处理二维函数或信号（如图像信号），就必须引入二维小波和二维小波变换及相应的快速算法。二维多分辨分析有两种，一种是可分离的，一种是不可分离的。前一种情况简单且应用广泛。因此本节就介绍可由一维多分辨分析的张量积空间构造的二维多分辨分析。而不可分离的情况也比较常见，但在图像处理领域应用不多，故这里不作介绍（可参见文献[11]，P113-118）。用表示平面上平方可积函数空间，即（2-11）容易证明，平面上有限区域中的一幅图像的能量是有限的。如设是一幅图像，它的定义域围成的区域的面积为，设最大的亮度值为M，即，则 引入空间的内积相应的范数定义为在不发生混淆的情况下，范数也常记为。的Fourier变换定义为， 设和是两个有限维或可数无限维线性空间。和的基底分别为，及。定义以形如的元素为基底的空间，为与的张量积空间，表示为如果和都是函数空间，和分别是和中的自变量，则张量积空间中的元素称为二维张量积函数或张量积曲面。 现在，设和是由尺度函数和生成的两个多分辨分析。则可以得到和的张量积空间，由于的基底为，的基底为，所以的基底为。 对于二元函数，引入记号记则是的基底。这样就形成中的一个多分辨分析，就是相应的尺度函数。 设关于的补空间，关于的补空间，即 现在，设生成，生成，即这时（2-12）其中，,同样，由于的基底为，的基底为，则的基底为。记则的基底为。类似的，记则的基底为，的基底为。 可以看到，与一维只有一个尺度函数和一个小波函数不同的是，二维情形有一个尺度函数和三个小波函数。 与一维情况类似，由式（2-12），我们有直和分解则对于都有唯一分解其中。 若及都是半正交尺度函数与半正交小波函数，则上面的直和分解就可以变为正交和分解此时，即，其中。 设，则其中对于任何。这样对于还可以进一步分解为其中。则有。 利用一维情况下的两尺度方程和小波方程可以得到二维张量积两尺度关系为其中现在，设则由再利用尺度函数和小波函数及其二进伸缩和平移的正交性，可以得到二维Mallat算法如下：（1）分解算法：（2）重构算法：类似的，利用一维双正交多分辨分析，可以获得二维双正交多分辨分析。只要将相应的分解和重构滤波器置换，就可以得到二维双正交多分辨分析的Mallat算法。我们称序列为的一级二维小波变换。 则对应于二维Mallat算法的滤波器组表示如图2.3所示。二维小波分解（括号中表示双正交滤波器）二维小波重构图2.3二维二通道Mallat算法的滤波器组表示 有了上面的分析，现在就可以分析二维离散图像信号的处理方法。设是一幅输入图像，其象素点之间的距离为，其中。我们可以将与尺度下的一个逼近函数联系起来，其中，是两个对偶尺度函数。使得为的均匀采样，即。另外，根据，有。由于，故从而，是在的一个小邻域上的加权平均。因此有 若将看成是一幅二维图像信号，和分别为行下标和列下标，则二维小波变换过程可以如下解释：先利用分析滤波器，对图像的每一行做小波变换，得到低频部分和高频部分；然后对得到的数据的每一列用分析滤波器，做小波变换；对的各列做小波变换得到低频系数，即；得到高频系数，即。对的各列做小波变换得到低频系数，即，及高频系数，即。一级小波分解后图像由四部分构成：其中，每个子图像都是原始图像尺寸大小的。这样每一级变换得到的低频信号递归的进行分解。同样重构过程也可类似进行。这样就形成了二维小波变换的塔式结构。§2.4紧支撑双正交小波基的构造 由于除了Haar小波外，没有同时具有对称性和紧支撑性的正交小波。而Haar小波不能很好的表示和分析连续信号或函数。因而，在数字图像处理中，常常采用同时具有对称性和紧支撑性的双正交小波。故本节只介绍具有紧支撑性的双正交小波基的构造方法。正交小波基的构造方法可以参见文献[8,11,12]相关部分的介绍。设是对偶的双正交尺度函数，是对偶双正交小波，则有与其相应的两尺度方程和小波方程（2-13）（2-14）在式（2-13）和式（2-14）中的每个方程两边同时取积分，可得（2-15）及（2-16）容易推出，式（2-13）和式（2-14）等价的频域表示形式分别为（2-17）（2-18）对式（2-17）和式（2-18）中的各方程进行反复迭代，可得各式的无穷积表示，（2-19），（2-20）这说明以上四个式子在中都是收敛的。 另外，滤波器组还要满足完全重构条件（2-21） 由式（2-15）、式（2-16）和式（2-21）容易推出此外，由式（2-15）和式（2-21）可以推出式（2-16）；由式（2-19）和式（2-13）可以推出式（2-20）。因此，综上可以得到，有限滤波器，使得尺度函数和对偶小波函数存在的必要条件为（2-22）及（2-23）式（2-22）被称为双正交滤波器的约束条件。 下面的定理给出了对完全重构的有限长滤波器给出了生成的一个双正交基的充分条件。 定理2.2若有限长滤波器满足式（3-21）,满足下式其中，时，。并且则无穷积，依次收敛于中的函数，。满足双正交关系。两个小波族都是的双正交Riesz基，其中满足式（3-13）。且相应的尺度函数和小波函数也都有紧支集。具体的，如果对于，；对于，，使得的支撑依次为和，则的支撑分别为和。因而，相应的小波的支撑分别为和。所以两个小波的支撑长度相同，都等于。设和是关于0对称的对偶低通滤波器，即满足（2-24）并且的长度分别为和，则有下面的结论成立：小波有阶消失矩等价于满足如下关系（2-25）2）小波有阶消失矩等价于满足如下关系（2-26）综上所述可知，构造具有阶消失矩并关于0对称的双正交小波和的约束条件为式（2-22）、式（2-24）、式（2-25）及式（2-26）下面用例子来说明双正交小波基的构造方法。 例2.1构造(5-3)小波滤波器。其被广泛应用于图像压缩，而且为JPEG2000中无损图像压缩的缺省滤波器。的滤波器长度分别为5和3，即。。并且是关于0对称的双正交小波。则可以得到(5-3)小波滤波器的约束条件为整理并求解该方程组可得到 例2.2构造(9-7)小波滤波器。其被JPEG2000用于有损图像压缩的缺省滤波器。的滤波器长度分别为9和7，即。。并且是关于0对称的双正交小波。则可以得到(9-7)小波滤波器的约束条件为整理并求解该方程组可得到的值如表2.1所示。表2.1小波与对偶小波都具有4阶消失矩的(9-7)小波滤波器系数01，－12，－23，－34，－40.788485616405580.41809227322162-0.04068941760916-0.0645388826287000.852698679008890.37740285561283-0.11062440441844-0.023849465019560.03782845550726§2.5本章小结本章主要介绍传统小波（或第一代小波）变换理论的基本知识。首先介绍了连续小波变换和离散小波变换的基本原理。接着讨论了离散小波变换在一维和二维张量积情况下的多分辨分析及相应的Mallat算法。Mallat算法在小波分析中具有非常重要的地位，相当于快速傅立叶变换（FFT）在经典傅立叶分析中的地位。最后给出了紧支撑双正交小波基的构造方法。本章所介绍的内容是为下一章介绍提升小波变换（或第二代小波）理论做必要准备。第三章提升小波变换的简化实现 经典小波分析是从傅立叶分析的基础上发展出来的，因而它在一定程度上受到傅立叶分析的限制。小波分析中的两个核心的概念——小波分析和多分辨分析都是建立在二进平移和伸缩思想基础之上的，这种思想直接来源于信号处理领域。我们称这种经典多分辨分析框架构造的小波为第一代小波。 1995年Sweldens提出了一种不依赖于傅立叶变换的新的小波构造方法——提升格式(liftingscheme)，称之为第二代小波变换。提升格式保持了第一代小波的特性，同时又克服了其平移和伸缩的不变性，并具有许多优点，具体表现在： 1）能够用于构造第一代小波，可根据需要来设计小波基。例如，可以先选择一个具有特殊尺度函数的一般多分辨分析，然后利用提升技术来修正该多分辨分析，直到满足设计者所希望性质。这种方法常用于提升小波的消失矩、构造具有插值性质的小波等。应用提升方法构造第一代小波，虽然不能构造全新的小波，但是它使我们认识到小波的构造能够完全在空间域完成。 2）能够改进第一代小波变换算法。它提供了一种快速实现方式，与经典的Mallat算法相比，运算量减少一半。能够实现小波变换的原位（in-place）计算。换言之，整个计算过程不需要申请辅助存储空间，可节省存储单元。逆小波变换的实现非常简单、快速直接，而且意义非常明确。可以简单的通过逆序正变换，同时交换加减符号得到。很容易实现整数小波变换，可以使小波变换用于信号的无损压缩。能够很容易的处理边界问题。 3）可用于第二代小波的构造。这种小波构造方法完全摆脱了Fourlier变换，放弃了二进平移和伸缩的条件，但获得的小波具有第一代小波的所有优点，如时频局部化性质和快速变换算法。基于此，我们可以在非平移不变区域（如有界区域或曲面）上构造小波基。§3.1小波分解与重构的多相位表示 由于正交小波变换是双正交小波变换的特殊情况，因此，下面仅介绍具有有限脉冲响应（FiniteInpulseresponse，FIR）的双正交小波滤波器的情况。设、、、是双正交小波滤波器组，它们对应的二通道Mallat算法等价的变换表示如图3.1所示。图3.1二通道Mallat算法等价的变换表示 滤波器的多相位表示为其中，包含了的偶系数，而包含了的奇系数，即或者 在二通道双正交小波滤波器组的完全重构（PerfectReconstruction,PR）条件下，取，从而有， 定义和的多相位矩阵（polyphasematrix）为从而有，类似的，可以定义和的多相位矩阵，亦即和的对偶多相位矩阵为同样，因此，小波滤波器的完全重构条件可以写成，（3-1）其中表示矩阵的转置矩阵，为的单位矩阵。根据上式可以给出小波分解与重构的多相位表示，如图所示。z-1z-1z图3.2小波分解与重构的多相位表示 下面来说明图3.1和图3.2在效果上的等价性。设输入序列的变换为，则图3-2中虚线框部分的作用相当于对序列进行懒小波变换，即抽取序列的偶序列和奇序列。偶序列和奇序列的变换分别为，，。设这两个变换经过作用后的低频部分和高频部分分别为和，则有计算上式可以得到这与根据图2.1所得到的结果完全相同。这就说明两图在效果上是完全等价的。 由于、、、都是有限长的小波滤波器，所以和的行列式和都是Laurent多项式。由式（3-1）可知，及其倒数都是Laurent多项式，故其必定为关于的单项式。这里设。下面的章节将根据小波分解和重构的多相位表示，通过对多相位矩阵进行因子分解，给出小波变换的提升实现算法。§3.2Laurent多项式的Euclidean算法 考虑一个具有紧支集的有限脉冲响应（FiniteInpulseresponse，FIR）滤波器，其中对于有限范围以外的均为零。有限滤波器的变换是一个Laurent多项式，即(3-2)于是，的次数为，比滤波器的长度少1。当是单项式时，定义其次数为[1]。 定义3.1两个Laurent多项式的带余除法： 对任何两个Laurent多项式和，其中，，一定存在Laurent多项式（称为商）和（称为余数），使成立，其中，或。称该过程为两个Laurent多项式的带余除法。简称带余除法。 两个Laurent多项式的商和余数不是唯一的。例如，对于，，对于以下几种情况： 1）。 2）。 3）。都满足，且。 利用带余除法，可以给出Laurent多项式的Euclidean算法如下： 对于任何两个Laurent多项式和，其中。设，从开始进行如下的递归运算：其中，“％”表示取余运算。则，且是一个Laurent多项式，其中为使的最小数，“gcd()”表示取最大公因子（greatestcommondivisor）。 假设，则存在使得，因此算法在步结束，其中。若记，其中，“/”表示取“商”运算，则有这等价于(3-3)显然，同时整除和。如果是一个单项式，则和是互素的。§3.3改进的Laurent多项式Euclidean算法 根据上面的两个Laurent多项式的带余除法的定义，给出了商为单项式的带余除法的定义，如下： 定义3.2商为单项式的两个Laurent多项式的带余除法： 对任何两个Laurent多项式，，其中，（即），一定存在Laurent单项式(3-4)称为单项商，其和多项式（称为余数），使成立。称该过程为商为单项式的两个Laurent多项式的带余除法。简称为，单项商带余除法。 从上面的定义可以看出，单项商带余除法的定义少了一个约束条件。这是因为，在要求商为单项式的条件下，就不能保证所求得的余数的次数一定比除数的小。另外，在我们的定义中也可以不要求，为与上面所述的Euclidean算法相一致特意增加了该条件。 由于对于给定的两个Laurent多项式和，以及都是确定的数，因此在该定义下，显然有下面的定理成立。 定理3.1两个Laurent多项式的单项商和余数是唯一的。例如，对于上面的例子，，由于，故，，且。 利用单项商带余除法，我们可以给出Laurent多项式的改进的Euclidean算法如下： 对于任何两个Laurent多项式和，其中。初始化，令，；计算；计算单项商其中，，和，分别表示和中的最大指数项及最小指数项的系数；计算余数其中，“％”表示单项商带余除法定义下的取余运算；5）;6）如果退出循环。否则，跳转到2)继续循环。和上面的定义一样，，且是一个Laurent多项式，其中为使的最小数。假设，则存在使得，因此算法在步结束。其中。同样我们可以得到与式（3-3）相同的结果，显然，同时整除和。如果是一个单项式，则和是互素的。比较改进前后的Laurent多项式Euclidean算法，我们可以发现，虽然前后两种算法都可以得到式（3-3）相同的结构。但是其中的是完全不同的。前者中为一个Laurent多项式，而后者中所有的都是单项式。使得各个矩阵之间的乘积变得简单，计算复杂度大大减少。下面还是用上面的例子，来说明。 例3.1用基于带余除法的Laurent多项式Euclidean算法进行计算。 计算过程（由于结果不止一种，这里只取下面一种）1）令，2），，3），，所以，和是互素的，且辗转除法的步数为。 例3.2用基于单项商带余除法的Laurent多项式Euclidean算法进行计算。 计算过程，1）令， 2），， 3），， 4)，， 5)，，所以，和是互素的，且辗转除法的步数为。 下面用，来说明。 例3.3用基于带余除法的Laurent多项式Euclidean算法进行计算。 计算过程，1）令， 2），， 3），，所以，和是互素的，且辗转除法的步数为。 例3.4用基于单项商带余除法的Laurent多项式Euclidean算法进行计算。 计算过程，1）令， 2），， 3），， 4)，， 5)，， 6)，， 7)，， 8)，， 9)，，所以，和是互素的，且辗转除法的步数为。§3.4多相位矩阵的因子分解 Daubechies和Swedens在其文献[1]中研究并给出了多相位矩阵因子分解的定理，该定理构成了小波变换提升实现的基础。下面在的行列式等于1的前提下，讨论完全重构滤波器的提升分解格式。并给出多相位矩阵的因子分解定理。 定义3.3若多相位矩阵的行列式等于1，则相应的滤波器对称之为补。 显然，当构成补时，也构成补。 定理3.2（提升）设构成补，则任何其他的补都可以表示为其中为Laurent多项式。 证明：直接计算知道的多相位分量对于偶数部分为，而对于奇数部分为。做一次提升分解后，新的多相位分解矩阵定义为 此时行列式的值没有发生变化，而。类似可以得到对偶多相位分解矩阵的表示为，此时的提升格式得到新的滤波器。类似的，我们也可以通过对偶提升格式来建立分解与重构端的提升结构。 定理3.3（对偶提升）设构成补，则任何其他的补都可以表示为其中为Laurent多项式。做一次对偶提升分解后，新的多相位分解矩阵定义为而对应于产生新的滤波器满足。 根据前面所述的改进的Euclidean算法对多项式向量（3-5）进行分解，可以得到。经过处理，我们总能保证为偶数。当为奇数时，经过下面的处理过程可以使得变为偶数。 假设为奇数，并令则， 现在，如果令则，由于为单项式，所以仍为单项式。则此时有，（3-6）其中，。给定一个滤波器，通常可以用下面的式子得到与其构成补的滤波器。 根据前面的论述，上面的式子构成了一种完全重构滤波器多相位矩阵的提升分解。但是，对于一般给定的特殊长度（包括分解和重构）的完全重构滤波器，上述分解不一定满足。因此，我们需要根据定理3.2对该结果进行提升。存在Laurent多项式使得，则滤波器对的多相位矩阵可以表示为，（3-7）另外，注意到，当为偶数时，利用上式可以得到，（3-8）根据上面的讨论，我们可以给出下面的定理。 定理3.4若的行列式等于1，即，则总存在Laurent多项式和及非零常数，使得其中，，。 在式（3-8）中，令，，，并结合式（3-7）可以知道该定理成立。 下面给出提升因子和的计算方法。 首先，对多项式矩阵（3-5）应用欧几里德算法，可得到令，注意到，则由式（3-7）可得，，其中。 若记，则则有，因此有，，综上，我们可以得到有限滤波器多相位矩阵的提升分解算法：使用欧几里德算法得到计算最后计算出另外，对多项式矩阵（3-5）应用欧几里德算法，可得到其中，为偶数。若为奇数，可以根据式（3-6）处理，最终可以使得为偶数。令，则，化简上面的式子，可以得到，。则根据式（3-7）可以得到，用该式进行计算，比上述算法少做一次矩阵乘法。根据二通道小波滤波器的完全重构（PerfectReconstruction）条件的多相位表示，（3-9）其中，为的单位矩阵，可以得到，（3-10）由此，我们可给出基于提升的正向小波变换和逆向小波变换的流程图如图3.3和图3.4所示。图3.3基于提升的正向小波变换流程图图3.4基于提升的逆向小波变换流程图图3.3和图3.4中和分别表示输入序列的偶序列和奇序列的变换，和表示经过一级小波变换后得到的低频部分和高频部分的变换。§3.5小波变换的提升实现的传统算法 根据上一节的讨论，下面给出小波变换的提升实现算法。根据是否为零分为两种情况。当时，预测步骤的起始步由奇序列预测偶序列。时，预测步骤的起始步由偶序列预测奇序列。限于篇幅，这里只给出的情况。设是长度为（这里设为偶数）的一个信号，和表示它的偶序列和奇序列。由于和都是单项式，故可以记，若记，分别表示，的变换，且则用序列卷积可表示为，故可以写出正向小波变换提升实现的简化算法如下：1）懒小波变换（Lazywavelettransform）2）步提升及对偶提升（liftinganddualliftingsteps）3）比例缩放变换（scaling）最后得到的和分别为小波分解的低频分量和高频分量。其中，。 通过对正向小波变换按照相反的步骤操作，同时改变正负号，即可得到相应的逆变换如下。1）比例缩放变换（scaling）2）步提升及对偶提升（liftinganddualliftingsteps）3）逆懒小波变换（InverseLazywavelettransform）另外，参照上面的介绍，时的算法步骤可以类似给出。这里不再列出。§3.6小波变换的提升实现的简化算法 利用上面给出的改进的Laurent多项式的Euclidean算法，我们提出了一种小波变换的提升实现的简化算法。该算法与前面的算法类似，只是提升与对偶提升步骤稍有差别，其他过程都基本一致。同样该算法也按是否为零，分为两种情况。时的算法过程如下。设是长度为（这里设为偶数）的一个信号，和表示它的偶序列和奇序列。由于和都是单项式，故可以记，，若记，分别表示，的变换，且则用序列卷积可表示为，故可以写出正向小波变换提升实现的简化算法如下：1）懒小波变换（Lazywavelet）；2）步提升及对偶提升（liftinganddualliftingsteps）；3）比例缩放变换（scaling）。最后得到的和分别为小波分解的低频分量和高频分量。其中，。 通过对正向小波变换按照相反的步骤操作，同时改变正负号，即可得到相应的逆变换。另外，当的情况与时情况稍有不同，但是可以参照传统算法时的情况类似给出算法步骤。这里不再列出。§3.7提升算法举例 下面以几种常用的小波变换的提升实现为例来说明本文算法与传统算法的不同。由于传统的多相位矩阵的分解不唯一，所以小波变换的提升分解也不是唯一的。以下用传统小波变换提升分解算法实现的例子中只给出一种常用的分解形式。 例3.5用传统提升小波算法实现(5-3)小波变换的提升。 (5-3)小波滤波器如下：可以求出(5-3)小波滤波器的多相位矩阵在传统的提升小波算法下存在如下一种因子分解，其中，。由此可以给出(5-3)正向小波变换的提升实现为， 例3.6用本文提升小波算法实现(5-3)小波变换的提升。可以求出，因子分解为：其中，。由可以得到，由此可以给出(5-3)正向小波变换的提升实现为，简单的变更计算次序和加减号就可以给出(5-3)逆向小波变换的提升实现为，然后根据图3.3和图3.4就可以给出相应的基于提升的正向及逆向小波变换的流程图。以下各例都可通过做类似的操作，得到相应的流程图。 例3.7用传统提升小波算法实现(9-7)小波变换的提升。，这里选用小波与对偶小波都具有4阶消失矩的(9-7)小波滤波器，滤波器系数见表2.1。可以求出，存在以下因子分解：令，则，于是我们可以得到(9-7)正向小波变换的提升实现算法为： 例3.8用本文提升小波算法实现(9-7)小波变换的提升。可以求出，因子分解为：（3-11）其中，由可以得到，于是我们可以得到(9-7)正向小波变换的提升实现算法为：(9-7)逆向小波变换的提升实现仿照例3.6中的形式，可以很容易给出。这里不再给出。 例3.9用传统提升小波算法实现D4小波变换的提升。D4小波滤波器的变换为其中可以求出D4小波滤波器的多相位矩阵在传统的提升小波算法下有如下一种因子分解，由此，可以给出D4小波变换的传统提升实现算法为， 例3.10用本文提升小波算法实现D4小波变换的提升。 用改进的Laurent多项式Euclidean算法计算出 由此，可以给出D4小波变换的本文提升实现算法为， 从上面的例子，可以看到，对于具有线性相位的(9-7)和(5-3)小波滤波器，它们的为常数，而对于对称性不好的D4小波滤波器而言，为多项式。 从例子可以看出，除了最后一步提升外，其他的提升和对偶提升步骤都是用奇序列中的一项来预测偶序列中的一项，或用偶序列中的一项来更新奇序列中的一项。计算过程只是用简单的乘法运算和加减运算得到，计算复杂度非常低。对于具有线性相位的小波滤波器，所有的提升步骤都是通过简单单项乘法及加法得到，完全去除了传统提升运算中的卷积运算，更加有利于软硬件的实现。 另外，当(9-7)和(5-3)这些具有线性相位的滤波器用于处理信号时，采用对称周期延拓的信号边界处理方法则不仅可实现小波变换的完全重构，同时又不增加变换后的数据量。§3.8整数小波变换 数字图像都是用整数来表示其象素值的，而小波滤波器表示却具有浮点数系数。对数字图像进行小波变换处理后数据，即得到的小波系数不再为整数。由于用二进制来表示浮点数的精度有限，因而经过小波变换后得到的小波系数重构时，就会有能量损失。因此，当人们想对数字图像进行无损压缩时，就希望变换后的小波系数仍为整数。提升算法可以十分方便的构造整数到整数的小波变换。将整数小波变换应用于图像压缩就可以实现无失真的图像压缩。该算法是通过在忽略归一化因子的情况下，将算子作用于每一个提升步骤中的算子和实现的。而向下取整算子“”是非线性的，因此，整数小波变换是非线性变换。利用例3.8中结果，给出(9-7)小波变换基于本文算法的整数提升形式为 通过上面的讨论我们可以知道，从多分辨分析的尺度函数或直接从滤波器出发可以构造出具有紧支撑性的双正交小波基；并在传统小波变换的提升算法的基础上，给出了一种新的提升算法。该算法在计算复杂度上较传统算法略微下降，但在软硬件实现方面更加简单。§3.9本章小结本章介绍了小波变换的提升理论，通过分析传统小波提升变换的不足，提出了一种小波变换的简化提升格式。具体就是在传统的Laurent多项式Euclidean算法的基础上，通过重新定义Laurent多项式除法，给出了一种改进的Laurent多项式的Euclidean算法，并在该算法的基础上提出了一种小波变换提升格式实现的简化算法。在该提升实现算法中，用简单的数乘运算代替了原来小波变换提升实现算法中的卷积运算，使得算法中的核心部分——提升及对偶提升步骤的计算更加简单直接，更加易于硬件实现。本章的最后，给出了传统提升小波变换算法与本文的简化提升算法的实例。通过实例对比可以看出，对于一般的小波滤波器，简化算法中的卷积运算除了最后一步提升或对偶提升之外，其他提升和对偶步骤中都没有卷积运算；而对于具有线形相位的小波滤波器（如常用于图像有损压缩的(9-7)滤波器），简化提升算法的每一提升和对偶提升步骤都是通过简单的一次加法和一次乘法运算完成，完全去除了复杂的