（计算数学专业论文）基于a+trous小波变换的小波域运动估计和运动补偿.pdf

中文摘要 中山大学硕士学位论文 基于at r o u s 小波变换的小波域运动估计和 运动补偿 专业： 学位申请人 ： 导师及职称 ： 计算数学 夏颖 关履泰 李小福 教授 副教授 摘要： 传统的视频压缩方法广泛采取空域运动补偿预测方式，其缺点是容易产生 马赛克效应和运动分离现象。然而小波变换图像本身具有天然的塔式结构，充 分利用小波图像内在的多分辨率特性，在小波域中进行运动估计和运动补偿， 消除马赛克效应，成为视频压缩中的一大研究方向。但由于离散小波变换不具 备空间平移不变性，使得小波域上的运动参数难以得到精确的估计，这成为了 小波域运动估计和运动补偿研究的一大难点之一。 s h e n s a 提出的“a 昀u s ”离散小波变换，通过取消下采样，以冗余代价得 到了小波变换的空间平移不变性。本文结合“at r o u s ”小波变换的特点，提出 了基于“at r o u s ”离散小波变换的小波域上的块匹配运动估计和运动补偿算 法，以及基于规则三角网格基的运动估计和运动补偿算法。通过“at r o u s ”小 波变换获得精确的运动矢量估计，经过运动补偿后再对残差图像进行下采样， 得到没有冗余的小波图像，最后进行熵编码。实验结果表明，本文建议的两种 方法既很好的利用了小波内在的多分辨率分析特性，又克服了一般离散小波变 换不具有平移不变性的缺点，在主观图像质量和客观评价标准上都比传统的块 匹配算法和三角网格基算法在压缩质量上有了明显的提高。 关键词： 视频压缩，a 仰u s 小波，块匹配，三角形网格，运动估计，运动补偿 一 坠照壁垒! 坐堕 m o t i o ne s t i m a t i o na n dc o m p e n s a t i o ni nt h e w a v e l e td o m a i nu s l n g“a1 - r o u s ，w a v e l e t 1 _ r a n s f o r m m a j o r n a i n e s u p e r v i s o o c o m p u t a t i o n a lm a m e m a d c 8 x i a y i n g p r o f e s s o rg u a nl n t a i a s s o c i a t ep r o f c s s o r “x i a o f u a b s n a c t ： m 谢o ne s t i m a t i o na n dm 嘶o nc o m p e n s a t i o ni nm es p a t i a ld o m i ni sw i d e l ye m - p l o y e di nm o d e mv i d e oc 唧r e s s i o n b u tt h i ss i m p l ea p p m a c hu s u a u ys u 疵r sf r o m b 1 0 c k i n ga n i f a c t s b e c a u s eo ft 1 1 em u l d r c s o l u d o na n a l y s i sp r o p e n yo fw a v e k t 咖【i l s - f o 肌h a v i n gm o t i o ne s t i n l a t i o na n d m o t i o nc o m p e n s a t i o ni n 吐l ew a v e l e td o m i ni sa n a t 眦a c t i v ea l t c m a t i v e b u tt h ef a c tt l l a td i s c r e t ew a v e l e tt r a n s f o r r ni ss h j f tv a r i 锄tg r e a t l y l l i n d e r sm em o 矗o ne s t i n l a 6 0 na i l dm o t i o nc o n l p e n s a c i o np r o c e s s s h e n s a s a 伽s ”a l g 嘶m i nr e n d e r st l l es h i f ti n v a r i a n t 印d p e n yb yp e r f b i l i n g w a v e l e t 锄m s f b 咖w i t 董l o m 也ed o w n s a m p i i n g 卿t i o n i nt l l i sp a p e r b o 血b i o c k - b a s e d a n dr e g l l l 盯t r i a i l g u l a fm e s h - b a s e dm e m o da r c 印p l i e dw i mm e ”at r o u s ，廿a n s f o n n 沁g e t l ea c c u 豫t ei n o i o ne s t i 瑚t i o n a f t e r 出ei n o d o nc o m p e n s a l i o np f o c e s s ，出ee r r o ri m a g ei sd o w n s a i p l c dt oan o n r e d u n d 锄tf o mw m c hi st h e nc o d e du s i i l ga n y w a v e l e t _ b a s e ds t i l l - i m a g ec o d e l e x p e r i m e n t a lf e s u l t ss h o wt h 砒o u rp u 单o s e dm e t h o d s o u t p e r f o m sb o t ht i l et r a d m o n a lb l o c k - b a s e da n dt r i a n g u l a rm e s h 书a s e dm e t l l o d si nt h e s d a t i a ld o m a i n k e y w o r d s ： v i d e oc o m p r e s s i o n ；at r o u sw a v e l e t ；b 1 0 c km a t c l l i n g ；t r i a i l g l em e s h ；m o t i o ne s t i _ m a t i o n ；m o t i o nc o l p e n 阻t i o n n i 第一章绪论 第一章绪论 1 1 视频压缩的研究背景和意义 视频压缩，是在满足实际需求和运算复杂度可行的条件下，将表达视频图 像的信息量降低到一定程度的过程。图像和视频信息之所以可以被压缩，是由 于用以表达图像和视频的信息间通常具有较强的相关性，我们称之为冗余。 近年来，随着数据、语音、多媒体等业务的需求的不断增加，人们对这些业 务的服务质量要求越来越高。图像和视频信号由于数据量极大对数据存储和数 据传输带宽的需求超出了现有通信技术的能力。为了使通信成为可能并尽可能 地降低通信费用，必须对图像和视频信号进行压缩。视频会议、可视电话、高清 晰度电视、交互式电视和远程医疗的出现，i n t e m e t 、电信网和广播电视网的逐步 融合，使得图像和视频压缩问题越来越受到人们的关注和重视，成为图像通信的 研究的中心议题之一。 f 0 l l f i e r 变换是图像和视频压缩中应用最早和最广的工具。基于分块d c t 变 换的压缩编码技术是已有图像和视频压缩标准的核心技术。如我们熟 悉的j p e g 【“、h 2 6 3 2 1 和m p e g 3 】标准等。但随着应用和研究的不断深入，分 块d i 玎变换编码的缺点逐步暴露出来，尤其在低比特率环境下，压缩图像不可 避免地出现了方块效应和飞蚊噪声。 小波变换由于具有良好的时域频域局部化性质，对处理像图像和视频这 样的非平稳信号十分有效。而小波多分辨率分析的思想，与人类视觉系统的特 性相匹配，为开发出高效的图像视频压缩算法提供了可能。因此，基于小波 的图像视频压缩已成为当前视频压缩的研究热点。如今，j p e g 2 0 0 0 【4 l 和m p e g - 4 v t ( s u a lt e x t u r ec o d i n g ) 【5 】标准都采用小波变换编码算法，可见基于小波 的视频压缩技术将成为未来视频压缩标准的一项核心技术。 1 2 视频压缩技术原理 视频实际上是由静态图像的时间序列构成的，每一幅图像称之为一 帧( f r a m e ) 。对于视频的显示来说，帧速率就是时间序列的播放速率，通常帧 速率在2 5 3 0 f $ ( 帧，每秒) 之间。视频的数据量是庞大的，以公用的中间格 式c 1 ( c o 皿n o ni n t e m e d i a t ef 0 珊a t e ) 为例，每帧有2 8 8 + 3 6 0 个像素点，每个像素 第一章绪论 编码方法实例 雹夫曼编码 熵编码算术编码 游程编码 离教余弦变换 澡编码离散小波变换 运动补偿预测 分形图像压缩 h2 右3 棍合编码 j p e g m p e g 图i i图像，视频编码方法的分类 采用2 4 个比特数来存放亮度及色度分量，当帧速率为3 0 f p s 时，每秒c i f 视频的 比特数高达7 4 6 5 m b 。 虽然表示视频信息需要大量的数据，但这些数据往往是高度相关的，因此 可以通过去除冗余信息来实现对视频数据的压缩。视频除了存在静止图像的空 间冗余以外，还有由帧间数据的高度相关性带来的时间冗余。因此，对视频数 据的压缩目的就是去除空间冗余和时间冗余。 常用的图像，视频压缩方编码法如图1 1 所示，可分为嫡编码、源编码和混合 编码等。本文主要讨论的是小波变换加运动估计与补偿的混合压缩编码方式。 1 。3 基于小波变换的视频压缩研究回顾 基于小波变换的视频压缩研究包括以消除空间冗余为目的的小波静止图像 的压缩研究和以消除时间冗余为目的的压缩机制研究。 1 3 1 基于小波变换的图像压缩 基于小波变换的图像压缩是小波视频压缩的基础。根据小波变换的特征可 知，小波图像有如下几个显著的特点： ( 1 ) 各高频子带具有良好的空间方向选择性，这与人眼的视觉特性十分吻 合。 ( 2 ) 小波图像的多分辨率分析特性。小波图像的各个频带分别对应了原图像 在不同尺度和不同分辨率下的细节以及一个最小尺度、最小分辨率下对原始图 一一 第一章绪论 像的最佳逼近，且各高频带之间存在着一定的关系。 ( 3 ) 小波图像分解的系数间存在着天然的塔式数据结构。除最高分辨率下的 三个高频子带外，每个高频予带中的每个像素点在空间位置上都对应于其相邻 分辨率下高频子带的四个像素点。 根据小波变换和小波图像的特点，用小波技术对图像进行压缩编码时，需 要解决三个方面的关键技术： ( 1 ) 图像边界的扩展 对图像进行小波分解与合成的运算是卷积运算。由于一幅图像的范围总是 有限的，若直接进行卷积运算，合成时必定会导致信号边界的失真，影响恢复 图像的质量，因此要对图像信号进行边界扩展。常用的扩展方法主要有周期扩 展、边界补零扩展、重复边界点扩展、对称扩展、反对称扩展等。 ( 2 ) 小波基的选取 不同的小波基具有不同的时频局域性，对编码的复杂度、压缩比及恢 复图像质量均会产生影响。具有紧支集的正交小波基可以无冗余地表示图 像信号，但除h a r 堪外，这类小波基缺乏信号处理中所希望的对称性，对应 的滤波器不具有线性相位，对图像编码是不利的。而双正交小波基正好相 反，且构造容易，因此在实际应用中受到了广泛重视。常用的双正交小波基 有c o b e n - d a u b e c l l i e s 的3 ，5 、7 ，9 小波【6 】f 7 】【8 】【9 1 等。 ( 3 ) 编码方法 近年来，小波图像压缩编码研究取得了很大的成功。它们主要利用小波良 好的频率压缩特性和空间压缩特性，以及小波系数分布的相似性。得到高效的 阻像编码算法。经典的包括e z w 算法、s p h l l r 算法和e b c c r r 算法。 e z w ( e m b e d d e dz e r o t r e ew a v e l e t ) 1 0 1 喇算法是基于零树假设而提出的：如 果空间树的粗尺度的小波系数对t 门限是不重要的，则在这棵小波树的细尺 度的小波系数也极可能是不重要的。在这个假设下，e z w 用上一级的小 波系数预测下一级的小波系数，每次阈值的选取按递减方式来实现逐级量 化，这样使最后所产生的比特流可以按对应的幅值大小分层次地排列，从 而实现了对图像的逐次逼近。 s p h i 联s e t p a n i t i 锄i n g i n h i e r 8 r c l l i c a l l h 嚣) 【l l 】s p h i t 算法是存e z w 算法的基 础上改进得到的。s p 瑚t 利用空间树分层分割的方法，间接实现空间小波树 一1 一 第一章绪论 的比特面排序，从而有效地减小了比特面上编码符号集的规模。它成功构 造了两种不同类型的空间零树，从而可以更好的利用小波系数的幅值衰减 规律，因此性能比e z w 有了很大的提高。 e b c o t ( e m b e d d e db l o c kc 0 d i n gw i t ho p t i m 啦dn u n c a t i ) 【1 2 je b c o r r 算法 是一种具有对嵌入式码流进行优化截取的嵌入式分块编码方法。它先将每 个子带分成一个个相对独立的码块，然后使用优化的分层截断算法对这些 码块进行编码，产生压缩码流。结果图像的压缩码流不仅具有s n r 可扩展 而且具有分辨率可扩展，还可以支持图像的随机存储。因此，e b c 0 | r 特别 适用于大图像的远程浏览和图像数据库检索等应用领域。 1 3 1 2 基于小波变换的视频压缩 消除时间冗余的研究主要有两大方向，基于二维的运动估计和运动补偿和 把视频看作一个三维整体的三维方法。主要的算法有以下三种类型： 1 3 2 1 基于空域运动补偿的小波视频编码( m c d 厂r ) m c - d w t 是采取空域运动估计和运动补偿技术消除时间冗余，然后使用整域 小波变换消除空间冗余。它与传统的基于d ( 卫的混合编码的主要差别在于对补 偿帧差的处理，即使用整域小波变换代替分块d c t 变换。根据运动补偿残差使 用的小波变换编码不同，目前m c d w t 的算法主要有三种：z e 算法、p a c c 算 法、s l c c 算法。 z t e ( 零树熵编码) 算法【l 如z t e 是基于小波域空间分块的自适应系数单次量 化编码和优化算术熵编码。它是在e z w 算法基础上发展而来的，它假定当 前帧的编码比特数为前一帧编码比特数和平均目标比特数的平均值，然后 根据所分配的比特数作帧内自适应，其优点在于可以支持基于对象编码和 空间可扩展编，解码。 p a c c 算法【1 4 1p a c c 算法则是对e z w 和s p i h t 算法的综合优化，进一步优化信 源分离，改进零树映射，并使用局部自适应熵编码。其性能比z t e 视频编 码器的性能有了进一步的提高。 s l c c 算法1 1 习s l c c 算法是s l c c 图像压缩编码算法在视频压缩的推j “。它采 用了与零树编码类似的方法，对相邻频带间的重要系数进行父子连接以提 第一章绪论 高编码效率。s l c c 算法与e z w 和s 咖t 算法的最大区别在于，它利用的 是重要系数的父子相关性而不是e z w 和s p i h t 所利用的不重要系数的父子 相关性比较而言s l c c 算法可以更好地编码具有丰富纹理信息的图像。 1 3 2 2 基于变换域运动补偿的小波视频编码( d 、佴m c ) d w t - m c 是先使用整域小波变换消除空间冗余，再通过小波域的运动估计 和运动补偿技术消除时间冗余，最后对变换域的补偿残差进行小波压缩编码。 由于小波分解内在的多分辨结构，在小波域内很容易执行运动估计和运动补 偿。z h 柚一硒1 等首先提出了一种基于小波分解域的可变块大小多分辩率运动估 计，同传统的时域运动估计相比可以节省大量的搜索匹配时间，在中高比特率视频 压缩中有较好的应用，但在低码率条件下的压缩性能极差。这是因为小波变换 并不具有空间平移不变性，使得小波域内相邻帧间的平移运动难以精确界定。 因此小波域上的运动估计和运动补偿成为娜m c 研究中的一大难点。 h w p a r k 提出了一种改进的方法：基于低频子带平移方法的运动估计算 法( l b s m e ，m o d o ne s d m a t i o nu s i l l 窖l a w b a n d s h i f tm e t h o d ) h 7 1 ，扩大小波域估 计的搜索集，使小波域的运动估计等价于空域的全域搜索。由于小波基具有 紧支性，l b s m e 算法等价于对空域的重叠块估计，而且随小波基的不同而自适 应，其估计效果达到了最佳。这种算法的缺点是匹配搜索的时间较长，而且需要 较多的缓存。 1 3 2 3 含运动补偿的三维小波视频编码( m c 3 d w c ) ) 基于三维的小波视频压缩是将视频看成一个三维整体( 即两个空间维和一 个时间维) ，直接对二维小波图像压缩的思想进行推广。三维小波视频压缩需 要考虑视频序列在时间方向上存在的相关性。这种相关性不同于空间相关性， 它是指当前帧一般是由先前帧的部分区域变化的结果，引起这些变化有许多可能 因素，如摄像机的移动、镜头聚焦的变化、场景中物体的运动以及照明条件的变 化等等。 目前已有的i 维小波算法有多速率三维子带小波编码( 3 d s b c ) m l 、运动补 偿三维子带编码算法( m c 一3 d s b c ) 9 1 ，基于三维零数结构的高度可扩展三维小 波视频编码算法( t r i 拥t ) m 1 、基于三维空间八叉树的三维小波编码算法等 等。 目前关于m c d r 的研究是较为成熟的，这类编码算法存低比特条件下 的压缩性能，无论主观品质还是客观品质大都超出h 2 6 3 编码器性能。但是m c 一5 一 第一章绪论 d 、t 只是对传统混合视频编码算法的简单继承，缺乏针对性。没有完全运用到 小波图像的特点，因此在中高比特条件下图像质量得不到提高。m c 3 d w c 的 优势在于容错性强，支持高度扩展功能。但是目前研究中的这类算法编码效率 低，需要较多的帧存储器，造成较大的延迟。因此，本文的工作选择在d w t m c 方向进行。d w t - m c 方法的研究关键在于克服小波的平移可变性，提高小波 域运动估计的准确性和效率。 1 4 对视频压缩质量的客观评价标准 ( 1 ) p s n r ( 峰值信噪比) p s 兄= 1 0l 0 9 1 0 ( q 2 彳s e ) 其中q 为图像灰度值量化级数，m s e 为均方误差，其定义为： mn m _ s e 2 赤萋圣掣) 一，协胛 ( 1 2 ) 其中，( 。，! ，) 和，7 ( z ，) 分别表示原图像和重构图像。 p s n r 值越高。表明重构图像与原图均方误差越小。p s n r 的计算较为简 单，且在多数情况下能反映图像的逼真度，因此国内外文献均用其作为评估压 缩质量的主要标准。 ( 2 ) 每像素比特率( b i tp e rp i x e l ) b p p = 压缩后图像所含比特数，原始图像象素总数。 b p p 反映的是图像的压缩效率，b p p 越小，压缩比越高。在图像通信传输 中，b p p 常与帧速率结合用于控制比特传输速率。 1 5 本文的研究内容及组织结构 第一章绪论首先回顾了视频压缩的研究背景、特点和技术原理。针对基于 小波变换的视频压缩研究丰流方法进行了系统的整理和概述。 第二章回顾了运动估计和运动补偿技术的主要原理，对常用的空域运动补 偿技术作了详细介绍和分析，并对空域和小波域上的运动补偿优缺点做了深入 比较。 一6 一 第一章绪论 第三章介绍了常用的离散小波变换和本文研究工作中使用的a 昀u s 吲小波 变换，并针对”平移不变性”问题对两种小波变换进行深入分析和比较。本文提 出了以a u s 小波为基础的块匹配运动估计和运动补偿算法，实验证明，本文 提出的方法比一般空域块匹配方法在压缩性能和质量上有了较大的改善。 第四章介绍了规则和不规则三角网格在运动估计和运动补偿中的使用，并 提出了本文的另一项研究工作：基于规则三角形网格的at r o u s 小波域运动估计 和运动补偿算法。实验证明，本文建议的方法比一般空域三角形网格方法在压 缩质量上同样有一定的改善。 一7 一 第二章运动补偿预测技术 第二章运动补偿预测技术 2 1 运动补偿预测原理 根据图像的统计特性，视频图像的帧与帧之间在宏观上存在着很大的运动 相关性，即后一帧图像总是前一帧图像经过平移、旋转、缩放等各种运动得来 的，从而两帧图像之问会出现大部分像素不变动或者仅作有规律的变动的情 况。为了提高视频的压缩效率，充分利用图像序列阅的运动信息，消除冗余，采用 运动辛 偿技术，进行帧间预测编码，是目前视频图像压缩中最主流的方式。运 动补偿技术就是在动态序列图像实时编码中运用信息以及像素的位移向量进行 图像高效编码的一种方法。h 2 6 x 系列标准和m p e g 标准中都采用了运动补偿法 来作为帧间的编码方法。 运动补偿帧问预测编码分为如下四个部分： ( 1 ) 物体的划分，划分静止区域和运动区域： ( 2 ) 对运动目标进行位移估计，即对运动物体从参考帧到当前帧位移的方 向和像素数做出估计，也就是要求出运动矢量： ( 3 ) 利用位移估计进行补偿预测，即根据得到的运动矢量，将参考帧做位 移，求出对当前帧的估计： ( 4 ) 对预测残差信息进行编码。 由于实际的视频序列图像内容总是千差万别的，要把运动物体以整体形式 划分出来是极其困难的。而物体的运动实际上又是十分复杂的三维运动，既有平 移，又有转动；如果再考虑到物体的非刚性和运动中光照的变化，将使运动模型的 建立和运动参数的估计十分复杂。最简单的情况是只考虑物体的平移情况。经 典的方法有像素递归法、相位相关法、时空域约束法及块匹配法等。其中，块匹 配法是使用最广泛的一种方法，h 2 6 1 ，c c 璩7 2 3 ，m p e g 1 。m p e g 2 标准中都采用 块匹配法做运动估计。 块匹配法( b 1 0 c km a t c h i n ga k o r i t h m ) 是把一幅图像划分为若干m 的宏 块( m a c r o b l o c k ) ，并假设每一块内所有像素都具有同样的平移运动，故宏块的运 动矢量就是宏块内所有像素的运动矢量。对每一宏块估计其运动矢量，即可实现 运动补偿。 9 第二章运动补偿预测技术 一赋 2 1 1 帧的分类 图2 1帧组构成示意图 对一输入的视频图像序列，首先要判定是进行帧内编码还是帧间编 码。m p e g 【3 】标准中把视频图像序列分成若干个帧组，每个l 魄组包含3 种类型的 图象帧：i 帧、p 帧和b 帧。它们的关系如图21 所示。根据图像帧类型的不同，采 用不同的编码方法。 i 帧 【帧( i n t r a c o d e df r a m e s ) 又称为参考帧，对它只进行帧内编码，不做运动补偿 帧间预测。每一个帧组是从一个i 帧开始，i 帧提供随机接收的访问点，便于实现 随机接收和定时进行帧刷新。 p 帧 p 帧( f 0 朋a r dp r e d i c 【e df r a m e s ) 是前向预测帧，根据其前传输的i 帧或p 帧( 以 下称参考帧) 做运动补偿预测。 p 帧的运动补偿实现原理如图2 ，2 所示，设在第一l 帧里，中心点为( 茁1 ，掣1 ) 的运动物体在第帧里移动到中心点为( 茁l + 如，1 + 由) 的位置，则其位移 矢量为d = ( 出，咖) 。若此时直接求两帧间的差值，显然两帧之间相关性极 小，所得差值幅度很大。若首先对运动物体的位移量进行运动补偿，即将第帧 中( z 1 + 如，! ，1 + d ! ，) 点的运动物体移回 1 ，可1 ) 处，再与第一l 帧求差值，从而使 相关性增大，差值信号减小，压缩比得到明显提高。 b 帧 b 帧( b i d i r e c t i o n a u vp r e d i c t e df r a m e s ) 是双向预测帧，它使用显示顺序处于该 帧前和该帧后的两帧作为参考帧，分别做前向补偿预测和后向运动补偿预 测。b 帧适合解决景物中由于物体运动引起的遮挡区的预测难题。例如画砸背 景中的一个区域a 在上一帧中被前方物体。遮挡，在当前帧中，由于物体o 的运 动。区域a 不再被遮挡，而在画面中显示出来。在这种情况下，对区域a 我们用后 一l o 第二章运动补偿预测技术 筹n 2 图2 2p 帧的运动预测 图2 3b 帧的自适应帧内插 向预测代替前向预测。 b 帧常采用自适应帧内插法实现。其原理如图2 3 所示：图中第一2 帧和 第帧是参照帧，第一1 帧是内插帧。按照一般的线性内插法，第一1 帧内 位于( 。1 1 ) 的像素要由第一2 帧和第帧的同样处于( z 1 ，1 ) 的像素值内插获 得。这实际上是将运动物体上的像素值和静止背景上的像素值做混合平均，会 引起图像模糊。为了在内插帧中正确地恢复运动物体，必须考虑其位移情况，对其 进行运动补偿。如图所示，在第一2 帧中，中心位于( z 。，。) 的运动物体在第帧 一茎三兰垩垫塑堡塑型塾查 中运动到( z l + 如，掣1 + 咖) 处，即该帧中位于( z 1 + 如2 ，l + 白2 ) 处的像素值应 由第一2 帧中位于( z 1 ，可1 ) 的像素和第帧中位于( z 1 + 咖，1 + d ) 的像素内插 得到。 2 1 2 帧内帧问编码判定 对某一宏块是进行帧内还是帧间编码，可以根据图像的帧间相关性和图像 的空间细节的丰富程度判定。 设，( 。，) 为当前帧大小为b b 宏块的像素灰度值，9 ( z ，) 为参照帧对应宏 块的像素灰度值日b 。则两宏块像素之差的均方差为： b b m s e = 壶驴( 剐) 一旦( 啪) 2 ( 2 1 ) 当前帧宏块的亮度像素的方差为： 日b s e = 壶善；m 矧) 2 = lz = l ( 2 2 ) m s e 反映了图像帧间的相关性，而s e 则反映了图像空间细节的丰富程度。 一般来说，宏块运动位移量小，则帧闻相关性强。但是，若图像空间细节少， 即使运动量大帧间仍可保持较强的相关性；若图像空间细节丰富，即使运动量 很小，其相关性也会大大减弱。因此，对帧间相关性强，图像空间细节丰富的 宏块采取帧内编码，其他的采取帧间预测编码。 2 2 运动估计算法 块匹配法将当前帧划分尺寸为m 个像素的一个个宏块，并假设一个 宏块内所有的像素作速度相同的平移运动。对当前帧中的每块b ，在以前 一帧的对应位置为中心、上下左右四个方向偏离相等距离d m 的范围内，即 在( m + 2 d m ) ( + 2 d m ) 个像素的搜索区内进行搜索，寻求与其最匹配的宏 块b 。这一对宏块在水平和垂直方向的距离即是所求的运动位移向量( 出，却) 。 块匹配法要解决的问题主要有两个：最佳匹配准贝和搜索方法。 一1 2 一 曲他 且d 口归 三驴 第二章运动补偿预测技术 2 2 1 匹配准则 衡量块匹配法最佳匹配的常用匹配准则有三种： ( 1 ) 绝对帧间差均值( m a d ，m e a na b s 0 1 u t ed i f f e r e n c e ) ： mn m a d ( i ，j ) = 丽专面 ( n ，m ) 一瓯一，( m + i ，n + j ) i ( 2 3 ) 其巾，& ( m ，n ) 为第k 帧( m ，竹) 处的像素灰度值，瓯一l ( m + i ，n + j ) 为第k 1 帧( m + i ，n + j ) 处的像素灰度值。 ( 2 ) 均方误差( m s e ，m e a ns q u a r ce r r o r ) ； j i f m s e ( i ，j ) = 丽专丙【鼠( n ，m ) 一一1 ( m + i ，倪+ 删2 ( 2 4 ) ( 3 ) 归一化互相关函数( n c c f ，n o 肌“z e dc m s sc o r r e l a t i o nf u n c t i o n ) ) 一即) = 丽杂岛 其中，r 。m 一，( d ) 为第k 帧与第k 一1 帧惟一矢量为d 的互相关函数， 第k 帧的自相关函数，r 8 。，( 0 ) 为第k 一1 帧的自相关函数。 2 2 2 搜索算法 ( 2 5 ) r w 。( 0 ) 为 常用的运动估计的搜索算法有很多，如全搜索法、三步法、共轭方向法、 二维对数法、交叉搜索法等。在这里我们只介绍两种有代表性的搜索方法。 ( 1 ) 全搜索法( f u ns e a r c h ) 全搜索法是对整个搜索窗口的每一个点进行块匹配计算，根 据m a d 或m s e 最小的原则，得出最佳匹配宏块。全搜索法是性能最好，最 可靠的。但显然，当图像空间分辨率高、运动速度快、搜索范围极大时，其运算 量相当大( 匹配运算次数达( 2 d 。+ 1 ) 2 ) ，对系统处理速度要求极高，很难实现视 频图像的实时编码。 ( 2 ) 三步法( n e es 呻s e a r c h ) 一1 3 第二章运动补偿预测技术 i，、 3 ， 3232 33 3 it l2， lr 删， ， f， 222 p 。 lil r j l l ：千、 o 一。 l | ll 4西一 一2 图2 4 o246s 三步搜索法 三步法是通过三步搜索，每次以上一步的搜索结果为中心，逐步减小搜索 步长，最终得到最佳匹配点的方法。其实现过程可见图2 4 ： 三步法基本保持了全搜索法的效果，但其计算量只有全搜索法的1 0 左 右，是一种快速而高效的算法。 2 t 2 3 无限运动估计 通常情况下，图像边缘的宏块运动估计是受到边界限制的，这对某些沿图 像边缘运动的物体、背景运动的估计影响较大。采用无限制的运动估计模式， 即允许运动矢量指向图像边界以外的区域，超出图像边界的部分，使用边界像 素进行填充。 2 3 运动补偿预测【2 4 j f 2 5 l 设，( z ，) 为当前预测宏块的像素灰度值，前向预测参照帧为i 帧，参照 帧对应宏块的像素灰度值为m ( z ，) ，前向预测运动矢量为f m y ( z ，y ) ；后向预 测参照帧为p 帧，参照帧对应宏块的像素灰度值为跏( 。，可) ，后向预测运动矢量 为b m 矿( z ，) ，则有： 前向预测运动补偿： ，7 ( z ，可) = 娇( 茁+ f m k ，口+ f m w ) ( 2 6 ) 一1 4 6 4 2 0 o 一 4 第二章运动补偿预测技术 前向预测残差： 彳b ，) = ，扛，掣) 一，扛，9 ) = ，( z ，) 一仇扛+ f m k ，+ f m u ) ( 2 7 ) 后向预测运动补偿： 后向预测残差： ，( z ，可) = 鲂( z + b m k ，可+ b m k ) ( 2 8 ) m b 扛，口) = ，( 茁，可) 一，( z ，) = ，( z ，) 一卯( z + b m k ，可+ _ b m k ) ( 2 9 ) 双向预测运动补偿： 烈，筝) = ：b 缸+ f 肠磙，爹+ f m ) + 彩 + b m k ，f + b m k ) l ( 2 1 0 ) 双向预测残差： m 日( 。，) = ，( z ，掣) 一，( z ，) = ，( z ，掣) 一i h 扛+ f m k ，+ f m ) + 跏+ b m k ，+ b m u ) 】 ( 2 1 1 ) 对得到的预测残差m b ( z ，可) 进行混合编码，消除空间冗余度以后，与运 动矢量一起送到解码端，重构图像。 2 4 空域运动补偿压缩编码解码器 如图2 5 所示，对输入的视频序列，若为i 帧，则以静止图像压缩的方式，直 接进行小波变换，最化和熵编码。常用的熵编码算法有绪论中提到的z r e 算 法、p a c c 算法、s l c c 算法等。若为p 帧或b 帧，先对其进行运动估计和运动补 偿，然后再对残差图像进行小波变换、量化和熵编码，与运动矢量一起形成输 出序列。 解码的过程相当于编码的逆过程，其流程如图2 ，6 所示。对i 帧无需进行运 一1 5 第二章运动补偿预测技术 图2 ，5 基于小波的空域运动补偿压缩编码器 同2 6 基于小波的空域运动补偿压缩解码器 动补偿，直接进行解码、反量化和逆小波变换，然后存入帧贮存器作参照帧使 用。对p 帧或b 帧，由解码得到的残差图像和运动矢量，调出参照帧中的对应匹 配块相加即可得到重构的图像。 2 5 小波域运动补偿 小波金字塔结构每层之间存在着很高的相关性，故在金字塔不同层的运动 行为虽然不同，但同样具有很高的相关性。因为它们实际上是在不同的尺度空 间和频率范围内，刻画相同的运动结构。利用这一相关性进行运动估计，能大 大减小运动估计的计算复杂度，并能减少由于对分块图像作全局小波变换引入 的误差。 z h a n g 等首先提出了种基于小波分解域的可变块大小多分辩率运动估 计( m u l t i r e s o l u t i o ni n o t i o ne s t i m a t i o n ，m 蹦e ) 算法。这种方法是在最高层低频 子图中进行块匹配的运动估计，得到的运动矢量作为其它子图的运动估计初 矢量，然后做相应的修正。这种方法的优点是大大减小了基于块匹配算法运 动估计过程的计算复杂度，缺点是由于小波变换不具有空问平移不变性，使 得运动矢量的估计容易出现偏差。因此在低比率环境下应用效果较差。p a r k 1 6 第二章运动补偿预测技术 图2 7m r m e 算法编码流程 和k i m 【17 1 、李涛【、刘红梅f 2 7 】、娄东升( 2 8 】等都分别提出过对m 刚e 算法的改 进。 一个图像，( z ，) 经过三级小波分解，可以得到1 卟子带图 像 口3 ，蝣，孵，孵，七= 日，v d ；j = 1 ，2 ，3 ) 。b 3 是，在最低分辨率2 上 的低通近似图像，而- 咿，w y 和w 尹则分别代表分辨率2 一j 上的水平、垂直和对角 线方向高频部分。 m 蹦e 算法首先估值出子带岛上的运动矢量。若按块匹配法将原始图像 分解为大小为m 的一系列小方块，子带岛图像的大小是原始图像的2 - 3 2 3 倍，故该层相应的宏块尺寸也减小到2 3 m 2 - 3 。显然可见块匹配运动估 计的计算量大大减小。 得到子带j e 7 3 的运动矢量后，乘以一个缩放尺度因子，即可作为其他子带运 动矢量的初始估值，再在此基础上修正这些子带的运动矢量。需要注意的是各 层所对应的块大小不同。第七层上的块大小为2 m 2 “。 设在子带8 3 得到的运动矢量估计值为( 硼) ，则畔上的运动矢量( 喀) = 蠲 2 3 一+ ，其中；是按下述准则决定的修正值： ；= 哪俩q l 8 其中，臻( s ) 为时刻在孵中位于点s 的像素值，为孵的分块。 图2 7 为m r m e 算法的编码流程图： 2 6 现有运动补偿技术的优缺点比较 空域运动补偿方法是在使用离散余弦变换( d c t ) 进行视频压缩的基础上发 一1 7 第二章运动补偿预测技术 展起来的。d c t 编码器无论是在帧内还是帧间编码时都使用了分块的思想。实 际上分块技术很容易导致马赛克效应、飞蚊噪声等失真现象。 基于小波变换的空域运动补偿在编码上用d 、w 代替了d c t ，而在运动补偿 方面则继承了原有的思想和算法。这种编码方法实现较为简单并且在低比特 率传输条件下取得了极佳的性能。因此m p e g 4 将基于小波的视频编码方法纳 入为优选方案。但这种空域运动补偿没有利用到小波分解内在的多分辨率特 性，采用全局小波变换，变换后的系数分布比较松散，因此在中高比特压缩传输领 域内性能未有大的改善。 小波域运动估计和运动补偿，利用了小波多分辨率结构的相关性和适应人 视觉特性的优点，能消除马赛克效应。其中，m r m e 方法由于一般离散小波变 换不具有空间平移不变性，难以达到精确的估计，影响了运动补偿的效果和 性能。第三章中将介绍“at r o u s ”冗余离散小波，能克服小波变换的平移可变 性，使用本文提出的“a 伽s ”变换块匹配运动估计算法，使得小波域上的运 动估计得到较大改善。 另一方面，以上介绍的运动估计算法都是基于块匹配思想的。块匹配法是 基于同一块内像素只作同一平动运动的假设下进行的。但实际物体的运动除了 平移以外，还有旋转、缩放等。因此在处理旋转、尺度缩放、弹性形变时，传统 运动补偿技术效率极低。此外，运动矢量并不总是反映图像中物体的实际运动 状态，容易导致运动分离等现象的产生。第四章将介绍本文另一项工作重点， 将三角网格基运动估计和运动补偿与“a 叻u s ”小波变换相结合，是对块匹配 算法存在的这一问题的另一个改迸。 一1 8 一釜三至垒塑! ! ! 尘鎏壅塑兰堡受垦至垫i ! 垡 第三章at r o u s 小波变换与块匹配运动补偿 3 1 连续小波变换1 2 9 】【3 。剐 定义3 1 设妒( ) 为平方可积函数，若其满足小波可容许条件 耻z 掣虮。j r w 则称妒( t ) 为母小波，由妒( ) 通过平移和伸缩生成的一系列函数称为小波： ( 3 1 ) 饥删= 厕( 等) n o 妊r ( 3 2 ) 定义3 2 函数，( z ) p 的小波变换定义为： 嗽6 ) = 击肛m ( 等冲 ( 3 ，) 相应的逆变换为： 删= 去厶陬咖) 警 ( 3 4 ) 从小波变换的定义可知，髓厂作小波变换其实是将，分解为不同的尺度级， 随着尺度级的变化，频率也相应的变化。当尺度变小时，频率变大，分辨率 增强，得到，越来越局部的细节；反之当。变大时，频率减少，分辨率减弱， 得到广的整体性质。因此，小波交换起到了“数学显微镜”的作用。小波的这 种良好的时频局部化性质，能更精确的逼近原始数据；此外，小波系数之问存 在着相关性，利用这种相关性可以进一步提高压缩效果。因此，小波变换在图 像和视频压缩方面得到很好的应用。 一1 9 第三章a1 r o u s 小波变换与块匹配运动补偿 3 2 离散小波变换 3 2 1 多分辨率分析 则： 定义3 3 设码是l 2 ( r ) 上的闭子空问族，满足： ( 1 ) v 2 lc c ( 2 ) d 7 巧= l 2 ( r ) ，n 嵋= o ( 3 ) ，( ) k 营，( 2 t ) + 1 ( 4 ) ，( t ) k 营，0 一) ，v 七z ( 5 ) 存在妒，使得妒0 一七) k 构成的一个r i e s z 基 则称嵋为l 2 ( r ) 上的一个多分辨率分析，妒称为尺度函数。 定义3 4 设k 为三2 ( r ) 上的一个多分辨率分析，为k 在巧+ 1 上的正交补， k + = o 聊，上k 由多分辨率分析的性质可知 三2 ( r ) = o w j j z ( 3 5 ) ( 3 ，6 ) 即j z 构成l 2 ( r ) 空间的一组正交子空间。设讥 ( t ) 为的一组正交基， 且妒满足容许性条件，容易证明，咖，( t ) j 。z 构成l 2 ( r ) 的一组正交基，故称妒为 小波函数。 其中 对v ，l 2 ，对任意整数j o ，由u + 1 = ow j 得到： 坤) = 晰，一( t ) + 而，* 奶，t ( ) ( 3 7 ) k zj ，o 七z 勺，= ，由，k = ( 3 8 ) 一2 0 一 第三章a1 b u s 小波变换与块匹配运动补偿 3 2 2ma l l 甜快速算法 m a u a t 【3 2 】根据图像分解的金字塔算法的思想，结合多分辨率分析，提出了 塔式多分辨率分解和重构的快速算法： 引入低通滤波器h 和高通滤波器k ，它们满足双尺度方程： 则m a j l a t 分解算法为： 重构算法为 妒( t ) = 妒( 2 t 一七) 妒( ) = 鳜妒( 2 t 一) ( 3 9 ) ( 3 1 0 ) ( 3 1 1 ) ( 3 1 2 ) 哪2 去莓一嘶协一) ( 3 1 3 ) 图3 1 和3 2 是一维m a l m 算法分解与重构的示意图： 其中，i2 代表下采样，即每两个点抽样；t2 代表一卜采样，即隔一捅零。 型粤孚嚣 图3 1一维m a l k 算法分解结构 一2 l 一 昏积 磷t 小 a 弘| m i 1 孙 “ 瓯 丽 。 。 土以 土瓶 | i | | k k l a 0 第三章a1 b u s 小波变换与块匹配运动补偿 构 礤v 删 扎n i 图3 2一维m a l 蕊算法重构结构 二维m a l b t 算法是对一维情况的直接推广。若k ，。z 为工2 ( 固空间的一个多分 辨率分析，记吁= ko 嵋，则容易推证，垮。z 为一二维多分辨率分析： 呼= + l k + 1 = ( o 嵋) o ( k o 嵋) ( 3 1 4 ) = ( kok ) o ( k ) o ( ko ) o ( o ) 记： 马= k ，k = uo 嵋，功=