（信号与信息处理专业论文）基于小波变换和可变形块运动估计的视频编码算法研究.pdf

中文摘要 随着社会和经济的不断发展，视频信息已经成为人们日常交流沟通最重要的 手段之一，广泛应用于各个领域。由于视频信息具有信息量巨大的特点，视频压 缩一直是人们研究的热点，新技术层出不穷。本论文首先对传统视频编码技术进 行了研究，针对分块d c t 变换会引起块效应和传统运动估计模型不能有效表示 非平移运动的问题，提出了一种基于小波变换和可变形块运动估计技术的视频压 缩算法。 本文首先介绍了小波变换的原理、实现方法和二维m a l l a t 算法及小波变换在 视频压缩领域的应用现状，并针对不同特点图像的小波变换系数，分别介绍了分 层小波树集合分割算法( s p i h t ) 和零树熵编码算法( z t e ) 。其中根据z t e 算法中 量化的特点探索了相应的码率控制方法。随后本文在分析了传统快速块搜索算法 的影响因素和优缺点的基础上，引入双线性运动模型和基于节点搜索的1 4 精度 可变形块运动估计算法，并给出了两种1 4 精度内插的实现过程。 由于视频编码中i 帧编码无残差补偿，且对后续p 帧编码效果影响较大，所 以对i 帧的编码至关重要。本文采用小波变换技术和s p i h t 算法编码i 帧，使得 i 帧在低码率下获得了较高的重建质量、码率可控且无块效应。对于p 帧编码， 本文采用自适应快速块搜索和可变形块运动估计相结合的方法，在不明显增加运 算量和传输数据的情况下，更有效的表示了实际中物体的非平移运动，显著提高 了运动估计精度。同时针对运动估计后预测残差较小的特点，本文采用小波变换 和z t e 编码算法，并结合码率控制方法，高效的组织了残差数据。 本文采用的所有算法均在v c 6 0 环境下用c 语言实现，并对i 帧对p 帧的 影响、运动估计和补偿算法的效果以及不同内插方法对运动估计的影响等进行了 实验，最后对实验结果进行了分析和总结。实验证明，本文算法对复杂运动和包 含大量细节的视频序列均有良好的压缩效果。虽然运算量有所增加，但明显减轻 了块效应，克服了块运动估计不能很好表示非平移运动的缺陷，在相同码率下有 效提高了视频质量，而码率控制技术和对剧烈运动物体的运动估计方法仍需改 进。 关键词：视频编码；小波变换：可变形块运动估计；s p i h t 算法：z t e 算法 a b s t r a c t w i t ht h ed e v e l o p m e n to fs o c i e t ya n de c o n o m y , d i g i t a lv i d e oh a sb e e no n eo f t h e m o s ti m p o r t a n tt o o l sf o rc o m m u n i c a t i o ni nd a i l yl i f e f o rt h ep r o p e r t yo fm a g n i t u d e a b o u t v i d e oi n f o r m a t i o n ，p e o p l ea l w a y sf o c u so nv i d e oc o m p r e s s i o nw i t hn e w t e c h n i q u e s a f t e rr e s e a r c h i n gt r a d i t i o n a lv i d e oc o d e r , t h i sp a p e rd e s i g n e dan o v e l a l g o r i t h mb a s e do nw a v e l e tt r a n s f o r ma n dd e f o r m a b l eb l o c km a t c h i n ga l g o r i t h m ( d b m a ) ，w h i c hr e d u c e sb l o c k i n ge f f e c t s a n dr e p r e s e n t sn o n t r a n s l a t i o n a lm o t i o n e f f e c t i v e l y i n t h i sp a p e r , t h et h e o r y , i m p l e m e n t a t i o nm e t h o d ，t w o - d i m e n s i o n a lm a l l a t a l g o r i t h ma n da p p l i c a t i o ns t a t u sa b o u tw a v e l e tt r a n s f o r mw e r e i n t r o d u c e da tf i r s t , t h e n t h es p i h ta l g o r i t h ma n d ( z e r o t r e ee n t r o p y ) z t ea l g o r i t h mw e r ed e s c r i b e d r e s p e c t i v e l yf o rd i f f e r e n ti m a g ec o e f f i c i e n t s a f t e rw a v e l e tt r a n s f o r m i nt h ez t e a l g o r i t h m ，t h i sp a p e rh a de x p l o r e dam e t h o df o rr a t e c o n t r o li nq u a n t i z a t i o ns t e p t h r o u g ht h ea n a l y s i s o nb l o c km a t c h i n ga l g o r i t h m ( b m a ) ，n o d a l d i s p l a c e m e n t b a s e dd e f o r m a b l em o d e la n dn o d a ls e a r c ha l g o r i t h mw e r ea d o p t e d ，w h i c hh a d1 4 p i x e lp r e c i s i o n m e a n w h i l e t w oi n t e r p o l a t i o nm e t h o d sh a db e e ns h o w n i nv i d e oc o d i n g ，if r a m ew i t h o u tr e s i d u a lc o m p e n s a t i o nh a di m p o r t a n ti n f l u e n c e o nt h ef o l l o w i n gpf l a m e s t h i sp a p e ru s e dw a v e l e tt r a n s f o r ma n ds p i h ta l g o r i t h mt o c o d eif r a m e ，w h i c hw o u l dg e tt h eh i g h e rr e c o n s t r u c t i o nq u a l i t ya n dn ob l o c k i n g e f f e c t se s p e c i a l l yi nl o wb i tr a t e f o rpf l a m e ，t h i sp a p e ra d o p t e dt h em e t h o do f c o m b i n i n ga na d a p t i v ef a s tb l o c ks e a r c ha l g o r i t h ma n dd b m a ，w h i c hi m p r o v et h e p r e c i s i o no fm o t i o ne s t i m a t i o nu n d e rt h ec o n d i t i o no fc a l c u l a t i o na n do u t p u td a t a i n c r e a s e di n s i g n i f i c a n t l y a tt h es a m et i m e ，w a v e l e tt r a n s f o 丌n ，z t ea l g o r i t h ma n d r a t ec o n t r o lw e r ea p p l i e df o rr e s i d u a li m a g e ，w h i c ho r g a n i z e dr e s i d u a ld a t ae f f i c i e n t l y a c c o r d i n gt or e s i d u a lf e a t u r e a l lt h ea l g o r i t h m sd i s c u s s e di nt h i sp a p e rh a v eb e e nr e a l i z e dw i t hcp r o g r a mi n t h ec o n s o l eo fv c 6 0 d i f f e r e n te x p e r i m e n t sf o rif r a m e sc o d i n g ，m o t i o ne s t i m a t i o n ， r e s i d u a lc o m p e n s a t i o na n di n t e r p o l a t i o na r ec a r r i e do u t a tl a s t ，t h er e s u l t sw h i c ha r e a n a l y z e da n ds u m m a r i z e ds h o wt h a tt h ep r o p o s e da l g o r i t h mt a k eg o o dp e r f o r m a n c e f o rc o m p l e xm o t i o nv i d e oa n dm o r ed e t a i l sv i d e o ，r e d u c eb l o c k i n ge f f e c t so b v i o u s l y , a n dr e p r e s e n tn o n t r a n s l a t i o n a lo b j e c tm o r ee f f e c t i v e l y b u ts o m ed e t a i l ss h o u l db e i m p r o v e de s p e c i a l l yi nr a t ec o n t r o la n dd r a s t i cm o t i o ne s t i m a t i o n k e yw o r d s ：v i d e oc o d i n g ；w a v e l e tt r a n s f o r m ；d e f o r m a b l eb l o c km a t c h i n ga l g o r i t h m ( d b m a ) ；s e tp a r t i t i o n i n gi nh i e r a r c h i c a lt r e e s ( s p i h t ) ；z e r o t r e ee n t r o p y ( z t e ) 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫注基堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：喇f ；| f ；岛 签字日期：1 驴口7 年多月) 弓日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规定。 特授权墨鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：孝字鹇 签字日期：沙口7 年歹月) 弓日 导师签名： 主矽信 月t ) 日 第一章绪论 第一章绪论 随着社会的发展，人们对信息的需求量快速增长，特别是网络和多媒体技术 的广泛应用，大大提高了人们的生活质量，与此同时人们对信息的要求也越来越 高。视频信息直观、易懂且信息量大，已经成为人们日常沟通交流的重要手段， 然而视频信息的数据量是巨大的，因此视频压缩技术一直吸引着众多相关领域的 研究人员和工程师进行不断深入地探索。 1 1 视频压缩原理 视频可以看作是由静止图像逐帧变化而组成的运动序列，由于运动不会太 快，所以短时间内每帧图像并不是孤立的存在，而与其在时间轴上的相邻帧有着 密切的联系，同理每帧图像内部的像素也与其周围的像素有着密切的联系，这些 相关性都会引起信息的冗余。而去除这些相关性就可以减少表示该视频所用的数 据量，从而达到压缩的效果。视频信息的主要冗余包括以下几个方面： ( 1 ) 结构冗余。结构上的冗余表现为很强的空间( 帧内) 和时间( 帧间) 相关性。 统计实验证实了电视信号在相邻像素间、相邻行间、相邻帧间存在这种强相关。 一般情况下电视画面中的大部分区域信号变化缓慢，尤其是背景部分几乎不变， 所以冗余很大，因此可以被压缩。 ( 2 ) 统计冗余。信号统计上的冗余来自于被编码信号概率密度分布的不均 匀。这种极不均匀的概率分布对采用变字长编码方法压缩码率极为有利，即对出 现概率高的信号用短码，对出现概率低的信号用长码，这种编码称为统计编码或 熵编码。 ( 3 ) 心理视觉冗余。心理视觉冗余是针对人眼的视觉特性而言的，如人眼对 亮度信号比对色度信号敏感，对低频信号比对高频信号敏感，对静止对象比对运 动对象敏感等。因此减少对不敏感因素的表示，并不会对人的主观感觉造成大的 影响，所以可以在必要时去除这些不太重要的数据。 由上述原因可知，视频压缩是可行的，视频编码的目的就是利用各种方法去 除各种信息冗余，在低失真度的前提下，尽可能的提高压缩比率，做到低码率传 输，高压缩比存储，高质量还原视频序列。 第一章绪论 1 2 视频压缩的现状 自上世纪5 0 年代起，部分学者开始系统的研究数据压缩理论，到8 0 年代后 期，以预测编码、变换编码和统计编码三大经典编码技术为核心的视频压缩编码 体系已经形成，并达到实用阶段。经过国际标准化组织0 s o ) 、国际电信联盟( 1 1 r i j ) 等组织的推动，先后形成了多个系列的视频压缩编码国际标准，包括h 2 6 1 、 m p e g 2 、h 2 6 3 、h 2 6 4 和m p e g - 4 等。 传统的视频编码技术以m p e g 2 标准为代表，主要采用帧间运动估计结合离 散余弦变换( d c t ) 运动补偿的混合编码方案，目前这一技术已经相当成熟，在数 字电视等领域得到广泛应用，其它标准则是在这一基础上对各个技术细节的不断 改进，m p e g 2 视频编码标准框图如图1 1 所示。 视 图1 - 1m p e g 2 视频编码标准框图 码流 m p e g 2 标准将视频序列分为长度相同的若干个组，每组第一帧为i 帧，其 余各帧为p 帧，分别采用帧内模式和帧间模式编码。在帧内模式中，对当前帧直 接进行d c t 变换以减少帧内结构冗余，然后经过量化减少心理视觉冗余，最后 通过熵编码减少统计冗余得到码流，并通过反量化，反d c t 变换重构当前帧， 作为下一帧( 第一个p 帧) 的参考帧；对于帧间模式，根据已知参考帧对待编码帧 进行运动估计得到预测帧，减少帧间结构冗余，对通过原始帧减去预测帧得到的 残差图像进行d c t 变换，量化和熵编码得到输出码流，并通过反量化，反d c t 变换重构残差，与预测帧相加得到待编码帧的重构帧，并作为下一帧的参考帧。 编码器的运动补偿和变换编码都是以正方形的宏块( m a c r ob l o c k ) 或块( b l o c k ) 为单 2 第一章绪论 位的。量化是理论上引入失真的唯一环节，为了更好的控制解码端图像质量，参 考帧采用重构帧而不是原始帧。 随后发展的视频压缩国际标准在上述技术基础上进行了多种改进，最新的 h 2 6 4 标准压缩效率比m p e g 2 提高了一倍，其采用的主要技术有： ( 1 ) 4 4 亮度帧内预测模式：i 帧编码时，对每个4 x 4 亮度块都单独进行预 测，针对8 个方向和直流，共有9 种预测模式，经过计算后采用最优的一种进行 预测，它对图像细节区域的描述效果很好。 ( 2 ) 多参考帧帧间预测模式：p 帧编码时，允许编码器用多参考帧进行运动 估计，而且支持1 4 像素精度和帧边界外运动矢量等技术，每个宏块可以分解为 1 个1 6 1 6 块、2 个8 1 6 块、2 个1 6 8 块或4 个8 8 块，更适应运动剧烈 的视频序列，提高了预测质量。 此外，h 2 6 4 标准还采用了整数d c t 变换、钻石形运动搜索、基于上下文 的算术编码( c a b a c ) 等技术，但其总的指导思想和编码框架相对于m p e g 2 标 准没有大的改变。 1 3 当前视频压缩标准中的主要问题 随着研究和应用的不断深入，传统视频压缩体系中的问题不断暴露，主要表 现在以下两个方面： ( 1 ) 基于分块离散余弦变换编码的缺点明显，尤其在低比特率环境下，图像 不可避免的出现方块效应和飞蚊噪声。这是因为图像信号整体是高度平稳的，但 图像中的一些突变结构如边缘信息是非平稳的，用余弦基作为非平稳信号的逼 近，其结果不是最优的，在图像运动剧烈区域表现尤为明显。虽然采用将块的尺 寸减小、重叠块运动补偿估计( o b m c ) 【2 】等技术可以减小方块效应，但大大增加 了算法复杂度和运算量。 ( 2 ) 传统视频压缩体系所建立的物体运动模型中，假设块内像素的运动是一 致的，且做的是刚性平移运动，由于其简单、易实现所以应用广泛，在平移运动 情况下效果较好，但它不能适应运动物体发生旋转、缩放或弹性形变等非平移运 动情况。在实际中，很可能有少部分图像发生了诸如旋转、缩放等变形，在这种 情况下采用平移模型即块匹配运动估计算法( b l o c km a t c h i n ga l g o r i t h m ，b m a ) 不 能准确的表示物体的运动，必然产生较大误差，只能通过大量的运动补偿数据来 弥补，这是平移模型所固有的缺陷。所以现有视频压缩标准对包含非平移运动对 象在低码率条件下的编码效果还不够理想。 第章绪论 1 4 本论文研究内容和组织结构 本文对d c t 和b m a 算法的优缺点进行了深入研究，针对1 3 节中提到的问 题进行了大胆探索，提出了一种新的视频编码方法，经实验表明，对包含非平移 运动对象的复杂运动视频序列在低码率条件下的编码效果改进较明显。 本文主要采用了小波变换和可变形块运动估计两种技术。为了获得更大的压 缩效果，尽可能减小现有视频编码框架导致的块效应问题，根据人眼的视觉特性， 本文算法将图像编码中广泛应用的小波变换技术引入i 帧，并用分层小波树集合 分割算法( s e tp a r t i t i o n i n gi nh i e r a r c h i c a lt r e e s ，s p i h t ) 对其编码，在低码率下主观 效果良好，且无块效应。对于p 帧，针对b m a 不能表示非平移运动的缺陷，采 用一种快速自适应块搜索算法进行平移物体运动估计，在不能满足精度的情况下 引入基于节点位移的可变形块运动模型，并给出预测精度高、运算量低且易于实 现的节点位移搜索算法即基于节点位移的可变形块运动估计算法( n o d a l s e a r c h b a s e dd e f o r m a b l eb l o c km a t c h i n ga l g o r i t h m ，n s d b m a ) ，有效提高预测精 度，减小预测误差。在运动补偿环节，本文采用小波变换技术，为了有效适应经 n s d b m a 后残差图像的小波变换系数煦分布统计概率，采用零树熵编码 ( z e r o t r e ee n t r o p y , z t e ) 方法对残差进行编码。甥外，在分数精度运动估计中采用 了基于全相位的d c t 内插技术，并且在z t e 算法的量化过程中设置了码率控制 环节。本文的视频编码框图如图1 2 所示。 视 图1 - 2 本文编码方法框图 码流 除此之外，本文就i 帧编码质量对p 帧的影响进行了实验，对快速块搜索匹 4 第一章绪论 配算法、全搜索算法和可变形块运动估计算法进行了比较和分析，对可变形块运 动估计算法中用到的两种1 4 精度内插方法也进行了介绍和对比，还对码率控制 后的图像质量波动给出了分析。 本论文第一章绪论部分主要介绍了视频压缩的基本原理，现状和其主要缺 陷，并介绍本论文的主要研究内容；第二章介绍小波变换的原理，实现步骤并介 绍s p i h t 和z t e 编码方法及相关量化和码率控制环节；第三章主要介绍影响运 动估计的主要因素和常见的快速块运动估计算法及可变形块运动估计的原理和 实现；第四章是实验结果、数据分析和结论部分：最后第五章为本论文的总结和 展望。 第二章小波变换及其编码方法 第二章小波变换及其编码方法 从2 0 世纪5 0 年代末开始，傅立叶( f o u r i e r ) 变换就一直是变换域图像处理的 主角，然而近二十年左右，一种称作小波变换的技术使得压缩、传输和分析图像 变得更为便捷。傅立叶变换用正弦函数作为其基函数，能提供信号的频率信息， 但失去了时域信息，而小波变换则基于一些基本小波，其具有变化的频率和有限 的持续时间。 小波的发展可以追溯到2 0 世纪初。1 9 1 0 年，h a a r 提出了规范正交基，尽管 在那时没有“小波”这个概念，但它是最早的小波基。随后经过众多科学家的大 量工作，小波分析于1 9 8 8 年有了突破性的进展数学家d a u b e c h i e s 构造出了 具有紧支撑的光滑小波【3 】，后来m a l l a t 提出了多分辨率分析( m u l t i r e s o l u t i o n a n a l y s i s ，m r a ) 概念和快速小波变换算法1 4 捌，到现在其发展时间虽仅二十年左 右，但速度很快，不断取得重大突破。小波分析目前已经成为最受关注的热点之 一，其应用范围几乎涉及信息领域的全部内容。 本章主要介绍小波变换的原理和实现步骤及在视频压缩领域的应用现状，并 根据后文需要介绍两种针对小波系数的编码方法：分层小波树集合分割算法和零 树熵编码算法。 2 1 一维小波变换 2 1 1 连续小波变换 设y ( f ) r ( r ) ，若满足容许性条件： q = e 肾 ( 2 - 1 ) 则称妙( f ) 为基本小波或母小波函数，其中v ( c o ) 是沙( f ) 的傅立叶变换。对母小波 函数进行伸缩和平移可以得到小波函数族： ( f ) f ) i 口r ( 孚) ( 2 - 2 ) 其中口r + ，b r 。( f ) 称为小波函数，此时口决定了虬。( f ) 的宽度和幅度，b 决定了。( f ) 在t 轴上的位置。 连续的平方可积函数厂( f ) 的连续小波变换( c o n t i n u o u sw a v e l e tt r a n s f o r m ， 6 第二章小波变换及其编码方法 c w t ) 定义为： 睨( 口，6 ) = lf ( t 妒a ， ( f ) 西口 o , b r ( 2 - 3 ) 给定睨( 口，b ) 可以通过反连续小波变换求得厂( f ) ： f ( t ) = 了1re 睨( 口b ) g o “f 如亨( 2 - 4 ) 由式( 2 - 3 ) 可见，既( 口，6 ) 是函数( ，) 在小波函数。( f ) 上的投影，并将厂( f ) 变换 为一个二维函数。 虽然在分析信号时，时间和频率通常被作为不同的域来处理，但它们之间却 存在着不可分割的关系。根据海森堡( h e i s e n b e r g ) 沏, o 不准原理，如果想要关于时 域的有价值信息，就要忍受频域的含糊，反之亦然。 傅立叶变换即正弦基给出了时间发生的频率但没有时间分辨率，而小波变换 的时间和频率分辨率是变化的。小波变换对信号的处理可以想象为在时域和频域 开的两扇相互关联的窗口，假定沙( f ) 的时域窗函数中心与半径分别为( f 0 ，西) ，其 傅立叶变换痧( 缈) 的频域中心与半径分别为( ，d t o ) ，经小波变换后，既( 口，b ) 可 解释为通过中心为( a t o + 6 ，堕) ，边长分别为2 a d t 和2 丝的矩形时间一频率窗 【口气+ 6 一a d t ，a t o + 6 + 础】l 詈一警，i o ) o + 警i 对信号进行观察。可见小波变换本 质是对信号的时间一频率联合分析。当口减小时，时宽减小，频宽增大，频域中 心向高频方向移动，当口变大时情况正好相反。这种“变焦距特性”在频率随时 间变化而变化的非平稳信号分析中很重要。 实际上，时间一频率窗可以看作是一个适配带通滤波器，这一滤波器的品质 因数为： q = 訾= 丢= 彘= 常数 ( 2 - 5 ) 2 1 2 离散小波变换 小波函数族。( f ) 当参数口，b 取离散值时，可得到离散小波定义： y 雎( f ) = a o 2 y ( a 0 7 t 一纸) ，k z ( 2 - 6 ) 其中a = a o ，b = k b o a o ，应用中通常选取a o = 2 ，b o = 1 时的二进制离散小波， 则式( 2 - 6 ) 可写为： y ( f ) = 2 2 沙( 2 t - k ) ，k z ( 2 - 7 ) 对任意连续的平方可积函数f ( t ) 的离散小波变换( d i s c r e t ew a v e l e tt r a n s f o r m ， 7 第二章小波变换及其编码方法 d w t ) 定义为： 睨( ，七) = ( ( f ) ，( f ) ) = 2 2l ( f ) 少( 2 。t k ) a t ，k z ( 2 - 8 ) ，t t 。一 若 沙m ( ，) ) 是r ( r ) 的一组基，即满足稳定性条件，则任意厂( f ) r ( r ) 都可重构： m ) = 们) ，。( f ) 鹕。( f ) ，k z ( 2 9 ) 式( 2 9 ) 中的 眈。( f ) ) 称为 ，。( f ) ) 的对偶。 一般情况下，重构公式( 2 9 ) 中的 汐肪( f ) 是很难求得的，除非具有某些对偶 的先验知识。所以，往往要对小波给出很多的限制，以确定其对偶。例如，当小 波是半正交或正交时，就比较容易确定它们的对偶，因为正交小波= 旷，是自 对偶的；半正交小波| l f ，r ( r ) 的对偶眵，通过它的f o u r i e r 变换定义： 痧：一坐! 竺2 一一( 2 1 0 ) l f ，2 _ - 二二一 u l w i 汐( 国+ 2 七万) | 2 其中，正交小波和半正交小波的定义如下： ( 1 ) 若 ，。 满足正交条件 = t ，4 _ ，k ，m ，砟z ，则称缈为正交 小波， tl 。z 为正交小波基； ( 2 ) 若满足条件 = 0 ，j m ，k ，聊，刀z ，则称为半正交小波， ，t ) m 。z 为半正交小波基。 2 2 多分辨率分析和一维m a l l a t 算法 1 9 8 7 年，在一种全新而有效的信号处理与分析方法一多分辨率理论中，小 波首次作为分析基础出现了。多分辨率理论将多种学科的技术有效地统一在一 起，如子带编码，积分镜像过滤以及金字塔图像处理等。1 9 8 9 年，m a l l a t 受多分 辨率理论启发，提出了小波分解与重构的快速算法一m a l l a t 算法1 6 ，为小波理论 的实际应用开辟了道路。 2 2 1 多分辨率分析 多分辨率分析是建立在函数空间概念上的理论，其基本思想就是用一簇具有 不同分辨率的近似函数来对给定函数厂( f ) r ( 酞) 进行逼近。用于建立某一函数 一系列近似值的函数被称为尺度函数( s c a l i n gf u n c t i o n ) ，它可通过对( f ) 使用选 定的滤波函数进行平滑滤波得到，相邻两近似值之间的近似度一般相差2 倍，而 小波函数则用来表示相邻近似值之间的差异。 第二章小波变换及其编码方法 尺度函数( f ) 应遵循多分辨率分析的几个基本要求，定义r ( 袋) 空间中的一 闭子空间 ，若满足： 、j ，毫正 ( 1 ) 由低尺度的尺度函数跨越的子空间在低尺度处嵌套在由高尺度函数跨 越的子空间内，即单调性：c _ 一lc _ c 一+ lc 7 ，v j z ； ( 2 ) 唯一包含在所有中的函数是f ( t ) = 0 ，任何函数都可以任意精度表示， 即完备性：q _ - - o ) ，圪= r ( 酞) ； ( 3 ) 具有伸缩性和平移不变性，即厂( f ) _ f ( 2 t ) 一+ pw z ， 厂( f ) l 厂( f + 音) 巧，v k z ： ( 4 ) r i e s z 基存在性：存在矽( f ) v o ，使得 烈f 一七) lk z ) 是v o 的一个r i e s z 基。 定义闭子空间 髟 础，且彬是屹在一+ t 空间中的补空间，由于小波函数用 来表示相邻近似值之间的差异，所以满足构成的r i e s z 基条件的 杪肚( f ) = 2 j 2 ( 2 。t - k ) ，j ，七z 就是尺度函数( f ) 对应的小波。且子空间之间满 足下列关系： _ + 。= 巧+ ，z ( 2 1 1 ) 亭( 豫) = = + 矽。+ + + ( 2 1 2 ) 由于存在c 一一。c c 一卅c ，w z 的关系，o ) = 死，。( f ) v ock 可以 由其在更高尺度的表达式表示，展开式系数设为 n ) ，露z ，则有： = 压见o ( 2 t 一七) ( 2 1 3 ) 同理，由于( ，) = 。( f ) 甄ck ，所以缈( f ) 也可以由更高分辨率下的尺度函数 表示，其展开系数设为 吼) ，k z ，则有： 缈( f ) = 2 吼( 2 f 一七) ( 2 1 4 ) 七毫z 式( 2 一1 3 ) 和式( 2 - 1 4 ) 分别称为尺度函数和小波函数的两尺度关系( t w o s c a l e r e l a t i o n ) ，其中 见) ， 吼) 眦z 2 称为两尺度序列( 铆o - s c a l es e q u e n c e ) 。 2 2 2 一维m a l l a t 分解与重构算法 m a l l a t 算法也称作快速小波变换【7 9 ( f a s tw a v e l e tt r a n s f o r m ，f w t ) 是一种实 现d w t 的高效计算方法，该变换找到了相邻尺度d w t 系数间的一种令人惊喜的 关系，使小波分析从理论分析真正走向实用。 根据旦_ 。r ( r ) ，任意函数厂r ( 瓞) ，能够对某个z ，用 非常 接近地逼近，其中厶为f 在空间上的投影，对于图像信息可以认为 是真实 9 第二章小波变换及其编码方法 图像厂在一定分辨率空间上的投影。因为巧= 匕，。+ 形一，对任何j z 成立，厶 具有唯一的分解 = 一。+ 踟_ l 其中， 一。小g ，一l 。将其推广到m 个 相邻尺度空间，即m 层小波分解可得： = 一l + 一l = = 一l + 一2 + + 州+ k 州 ( 2 1 5 ) 厶( f ) = g ，一l ( f ) + g _ 一2 ( f ) 4 - + g m o ) - i - f - m ( t ) ( 2 1 6 ) 下面将讨论如何把厶分解为它的各个分量g n - j , , g 州和厶州，并根据 m a l l a t 算法，由这些分量重构 。 因为o ( 2 t ) ，( 2 t - 1 ) k ，且k = 圪+ 甄，所以存在两个序列 a 。) ， 坟) e 1 2 , k z 使 矽( 2 t - 1 ) = a l - 2 k q k ( t - k ) + b i 诎杪( 卜吼1e z ( 2 1 7 ) k = - * o 式( 2 一1 7 ) 称为( f ) 与少( f ) 的分解关系。 现在已经有两对序列( 吼) ， 饥) ) 与( 既) ， 吼) ) ，它们全部是唯一的，其中 a k ) 与 巩) 称为分解序列， p 。) 与 吼) 称为重构序列。 1 分解算法 乃( f ) _ 和g ) 形都具有唯一的级数表示 f l f t ) = c ( 2 t - k ) ig j ( f ) = d j ，妙( 2 t - k ) 、 其中， c j k ) ， d 肚) z 2 ，代表小波分解的级。在此本文隐藏了规范化系数2 m ， 用( 2 f - k ) ，w ( 2 f 一七) 代替方。女( f ) ，m ( ，) 。 z 荆= c j + l , l 彬“t - 1 ) = 铀lz a 埘彬t - k ) + b ，埘5 f ，( 2 t - k ) ) l f， l j 广1厂1 = l a i 一：。c ，+ i fi 矽( 2 f 一七) + l 6 一：。c ，+ ，i 少( 2 t j | ) ( 2 - 1 9 ) 又乃+ l ( f ) = f ( t ) + g j ( f ) = c 似( 2 t - k ) + 少( 2 7 t - k ) ( 2 - 2 0 ) 于是，分解算法可描述为：用分解序列 q ) ， 钆) 与被分解序列 c 川，。) 先进行滑动 内积，然后向下二采样得到 c ) ， d 小) 。这里的向下二采样是指隔一取一，仅保 留偶数点。 对于有限带宽信号厂( f ) ， l o 乏 q 艚 掳 t l 十 + 岫 咕 q 岛 ， = = f ， 刊 + c ， c ， 也 也 钆 札 ， = = t j 气 嘭 第二章小波变换及其编码方法 ( f ) = f s ( t ) = g 一。( f ) + 厶一。( f ) = i 哆。沙( 2 f 一七) + c 州，。( 2 - m t - - k ) l 从以上公式可以看出，先由 c n 。) 计算 c 州，。) 和 氏吨。) ，再由 c n - j ) 计算 c n - 2 , k ) 和 九- 2 。) ，这样就构成了小波多分辨分析的分解算法a 2 重构算法 乃+ ，( f ) = 乃( f ) + 毋( f ) = f ( 2 7 t - 1 ) + 嘭，g ( 2 t - 1 ) 型圣塑鱼巳，肌( 2 川t - 2 l - k ) + 嘭。，“( 2 川t - 2 l - k 。) 广1 全! 三坠墨! i ( p k 矾，+ 缸：，p ( 2 p 1 卜七) 另一方面，乃+ ，( f ) = c 川，。矽( 2 川t - k ) c j + 1 k = zip 心m c j 圯叫d j ， = z i p 。之，c j ，+ g 。一：，d ， + p ；一：，+ 。o + q k 一：，+ 。0 】 = in ，c 。+ 纠 ( 2 - 2 2 ) 其中，p a ) ， d 0 是 c ， ) ， d m ) 奇数点补零得到的序列。 于是重构算法可描述为：将尺度序列 c j 。) ， t 。) 先进行向上二采样( 奇数点 补零) ，再与重构序列 见) ， 吼) 卷积运算，得到 c 川，。 。 m a l l a t 算法的本质是通过一组分解滤波器 q ) 和 以) 对信号进行滤波，然后 将输出结果进行下二采样实现小波分解，分解的结果是产生长度减半的两部分： 一部分是经低通滤波器产生原始信号的近似，另一部分则是经高通滤波器产生原 始信号的细节：重构时则先对小波分解的结果进行上二采样，然后使用一组合成 滤波器 见) 和 吼) 进行滤波来重构信号。多级小波变换可以通过级联的方式进 行，每一级的小波变换都在前一级分解产生的低频分量上进行，合成是分解的逆 运算。因为在上述m a l l a t 算法中，不需要知道尺度函数矽( f ) 与小波函数妙( f ) 的具 体结构，由滤波器系数就可以实t q - 见f ( t ) 的分解与重构，因此它被誉为快速小波变 换，可以与怏速f o u r i e r 变换相媲美。 2 2 3m a l l a t 算法中的边界延拓 m a t t l a t 算法是在信号为双向无限长序列的前提下推导的，但实际中待处理 的信号一般是有限区间上的序列，因而在用分解和重构公式计算时就要对数据延 拓，对于不同的数据和精度要求可以采取不同的延拓，设已知数据a o ，口l ，一a n 。， 常用的延拓方法有如下几种： 第：章小波变换及其编码方法 ( 1 ) 零延拓：即边界点之外数据都取零，如，0 ，a o ，口1 ，口州，0 ，； ( 2 ) 重复边界点延拓：即边界点之外数据都取边界点的值，如， 口o ，q ，- l ，一，； ( 3 ) 周期延拓：将已知数据看成是周期数据，如，印i p 口o ，q ，一2 ，q n - i , a o ，口1 ，； ( 4 ) 对称延拓：在边界点用对称的方法将数据延拓，如，口：，a i ， 口0 ，口l ，一2 ，一i ，一2 ，3 ， 从信号完全重构角度考虑，周期延拓方法最好，其它几种延拓方法不能满足 重构条件，会在信号边界引入失真。但由于图像信号长度较大，做周期延拓时信 号的起始和结尾处相关性不大，反而容易产生高频干扰，所以本文采用对称延拓。 2 3 可分离二维小波变换及m a l l a t 算法 由于图像是二维信号，要想使小波技术应用到图像领域就必须将小波变换、 多分辨率分析、m a l l a t 算法推广到二维情况。 设 矿1 ，是r ( 碾) 中的一个多分辨分析，其尺度函数与小波函数分别为矽和 y ，则张量积空间 v ，2 衄构成r ( r 2 ) 中的一个多分辨分析，其中，哆= 巧 ， 则其尺度函数为 ( x ，y ) = ( z ) 痧( y )( 2 2 3 ) 令二维小波空间形? 为y j 空间的补空间，即哆+ 形2 = 囔，三个基小波函数为： iu ( 工，j ，) = ( z ) 5 c ，( y ) l | f ，h ( x ，y ) = y ( x ) 痧( y ) ( 2 2 4 ) iy “( 工，y ) = y ( x ) ( y ) 这些小波函数是方向敏感的，v 响应沿行的变化( 如垂直边缘) ，沙h 响应沿列的 变化( 如水平边缘) ，d 对应于对角线方向的变化。 对于二维信号实现二维小波多分辨率分析与一维情况类似，分别用 c ，。 和 以。，i = 1 ，2 ，3 表示信号f ( x ，少) 在分辨率为j 时二维小波的离散逼近和离散细 节，如果把原始数据看作是一幅图像采样后的二维离散数据，则二维离散小波变 换对图像的分解和重构可看成是如图2 1 所示的滤波过程。 首先对 c ，。 进行水平方向滤波，然后再进行垂直方向滤波，获得四个不同 的频带 巳吐七) 、 矽“。) 、 呼l , k ) 和 啄。) ，若对低频分量 勺吐。) 继续进行上述 滤波过程，就可得到如图2 2 所示的塔形分解，而重构过程则与分解过程相反。 图2 3 是对l e n a 图像做3 层小波分解的结果。 1 2 第二章小波变换及其编码方法 行游* 亚卜一 c j 。 r 匝卜p i 夏卜乜卜 ，) 一 l 亘卜炬卜) l 固书斗j l 厘习乜卜 n 。) 0 ) 小渡分解：h a r t ) 和岛( ) 分别为分解时对应的低通和高道滤波器 列滤波 q 。 + j j j 口 * 滤被 争b 珍砸p h 0 弋砂+ 匝一 争 争呕互卜- 争卜珍岖型9 十叱) _ 1 坐一 叫9 1 巫卜 ( 小被重构； ，( ”) 和g ( 目) 分别为重构时对应的低通和高通滤泣嚣 圈工l 二维离散小渡变换对图像的分解和重柯示意图 二划) 略) 屯。l ( 峨。) 靠) 站) 幽l i - 3 图2 - 2 二鲣信号的多赶小波分解示意图图2 3k n _ 圈像3 层小波分解结果 第二章小波变换及其编码方法 2 4 小波变换在视频编码中的应用 2 0 世纪8 0 年代后期发展起来的小波变换由于具有良好的空间频率局部 化特性，在信号处理中非常适合于非平稳信号的分析。小波基的无条件基特性， 使它成为一大类信号非线性逼近的最优基，许多信号在经小波变换后，都可获得 稀疏的表示，这对数据压缩非常有利。 一幅典型的自然图像通常是均匀区域和纹理区域的典型组合，同时拥有小部 分边缘信息作为对象边界。一致均匀区域像素点的幅值变化小