（模式识别与智能系统专业论文）视频压缩编码运动估计算法研究.pdf

摘要 摘要 运动估计是视频压缩编码中的核心技术之一，采用运动估计和运动补偿技术 可以消除视频信号的时间冗余以提高编码效率。如何提高运动估计的效率，使运 动估计算法的搜索过程更健壮、更快速、更高效成为目前研究的热点。 本文重点研究了基于块匹配的运动估计算法，总结了提高运动估计算法效率 的三个主要技术，分析了一些较为典型的基于块匹配的运动估计算法。在此基础 上提出了一种效率更高的运动估计算法：基于起点预测的快速运动估计算法 ( p c p ) 。该算法充分利用了序列图像的运动矢量时间、空间分布特性中心偏 移性和相关性，设计了菱形和正方形两种模板，在搜索过程中根据图像的内容( 运 动类型) 采用组合模板进行灵活处理，提高了块匹配的搜索速度。实验结果表明， 该算法在速度和准确性方面都有了很大的提高。本文还对多分辨率运动估计算法 在空域和小波域分别进行了研究和探讨，并针对现有多分辨率运动估计算法普遍 存在的问题，提出一种基于内容的多分辨率运动估计算法( c b m r ) ，该算法应用阈 值中止判别技术，对满足运动补偿效果的运动矢量不再进一步处理，这样大大节 省了计算量。本文最后研究了最新视频压缩国际标准h 2 6 l 的高精度运动估计算 法，对可变块大小、不同精度和多参考帧运动估计算法分别作了实验仿真和性能 比较。 关键词：视频编码运动估计块匹配多分辨率h 2 6 l a b s t r a c t a b s t r a c t m o t i o ne s t i m a t i o ni so n eo f t h ec o r e t e c h n i q u e so f v i d e o c o d i n g m o t i o ne s t i m a t i o n a n dm o t i o nc o m p e n s a t i o nc a nr e d u c et h el a r g ea m o u n to ft e m p o r a lr e d u n d a n c yt h a t e x i s t sb e t w e e nf l a m e so fv i d e o s e q u e n c e s ，w h i c hl e a d st oh i g hc o m p r e s s i o n t h e r e s e a r c ho nl o o k i n gf o ram o t i o ne s t i m a t i o na l g o r i t h mt h a tc a l l g e ta ne f f e c t i v ea n d a c c u r a t em o r i o nv e c t o r q u i c k l y b e c o m e sah o t t o p i ca tp r e s e n t i nt h i s t h e s i s ，t h ea u t h o re m p h a t i c a l l yd i s c u s s e st h eb l o c k - m a t c h i n ga l g o r i t h m l a m a ) ，a n dm a k e sas u m m a r yo ft h em a i nt e c h n i q u e su s e df o ri m p r o v i n gm o t i o n e s t i m a t i o n t h e ns o m et y p i c a ls e a r c ha l g o r i t h m sb a s e do nb l o c km a t c h i n go fm o t i o n e s t i m a t i o ni sd e s c r i b e da n da n a l y s e dr e s p e c t i v e l y t h r o u g ht h er e s e a r c h ，t h ea u t h o r p r o p o s e sa b e t t e rm o t i o ne s t i m a t i o na l g o r i t h mc a l l e d p r e d i c t i o na n dc o m b i n a t i v ep a t t e r n a l g o r i t h m ( p c p ) ，i nw h i c h t h eh i 曲c o r r e l a t i o n o f a d j a e e n f l yb l o c k s m o t i o n v e c t o r sa n d t h ec e n t e r - b i a s e dc h a r a c t e r i s t i co fm o t i o nv e c t o r si ni m a g es e q u e n c e sa r eu s e d t w o k i n d so f p a t t e r n sa r ed e s i g n e d ，o n ei sd i a m o n d ，a n dt h eo t h e ri ss q u a r e t h e p a t t e r n sa r e c o m b i n e dt o p r o c e s s t h e i m a g ea c c o r d i n g t oi t s c o n t e n t ( m o t i o nk i n d ) ，w h i c h s i g n i f i c a n t l ys p e e d su p t h eb l o c k m a t c h i n g e x p e r i m e n t a l r e s u l t ss h o wt h a tt h ep r o p o s e d a l g o r i t h me x c e l so t h e rt r a d i t i o n a la l g o r i t h m si na s p e c t so fs p e e da n dv e r a c i t y t h e m u l t i r e s o l u t i o nm o t i o ne s t i m a t i o na l g o r i t h m sb o t hi n s p a t i a ld o m a i na n di nw a v e l e t d o m a i na r ed i s c u s s e d a i m e da tt h eq u e s t i o ne x i s t i n gi nt h e s ea l g o r i t h m s ，t h ea u t h o r p r e s e n t s ac o n t e n t - b a s e dm u l t i - r e s o l u t i o nm o t i o ne s t i m a t i o n a l g o r i t h m ( c b m r ) i n w b a c hat h r e s h o l d i n gt e c h n i q u ei sa p p l i e dt ow i t h h o l dt h o s eb l o c k sw h o s ee s t i m a t e d m o t i o nv e c t o r sg i v eas a t i s f a c t o r ym o t i o nc o m p e n s a t i o nf r o mf u r t h e rp r o c e s s i n g ，t h u s s a v i n gal o to fc o m p u t a t i o n i nt h el a s tp a r to f t h et h e s i s ，t h eh i g h e ra c c u r a c ym o t i o n e s t i m a t i o na l g o r i t h mo ft h ei t u th 2 6 lv i d e oc o d i n gs t a n d a r di sd e s c r i b e d t h e e x p e r i m e n t r e s u l t sa n d p e r f o r m a n c ec o m p a r i s o n s o fv a r i o u sb l o c ks i z e sm o t i o n c o m p e n s a t i o n , d i f f e r e n tp i x e lm o t i o nc o m p e n s a t i o na n dm u l t i p l er e f e r e n c ef r a m e s p r e d i c t i o na r eg i v e nr e s p e c t i v e l y k e y w o r d ：v i d e oc o d i n g , m o t i o ne s t i m a t i o n , b l o c km a t c h i n g ，m u l t i - r e s o l u t i o n ， h 2 6 l 创新性声明 y s 3 s 7 2 6 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：! 自查整 日期：；，g 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论支的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在互年解密后适用本授权书。 本人签名： 导师签名：秀审宝面导师签名：铆玉。砷日期：弼f 占 第一章绪论 第一章绪论 1 1 引言 随着信息技术的飞速发展，人们对多媒体通信业务的需求与日俱增。尽管人 们在努力增加信道带宽和提高信道传输效率，但数字化信息带来的“信息爆炸”， 使其成为多媒体技术发展中的一个非常棘手的瓶颈问题。比如，n t s c 制式的电视 图像以6 4 0 x 4 8 0 的分辨率、2 4 b i t s 象素、每秒3 0 帧的质量传输时。其数据传输 率达2 8 m b i t s ，2 0 秒的未压缩视频图像将占用5 6 0 m b i t 的存储空间，换句话说， 当数据不作压缩处理时，一张c d - - r o m 光盘只能储存2 0 秒钟的电视节目。要解 决多媒体信息存储容量大、数据传输率高的难题，就需要采用压缩技术。 压缩数据量的重要方法是消除冗余数据。原始图像中存在着大量的信息冗余， 如时间冗余、空间冗余、信息熵冗余、谱间冗余、几何结构冗余、视觉冗余和知 识冗余等等。一般情况下画面的大部分区域信号变化缓慢，尤其是背景部分几乎 不变，因此，视频图像在相邻象素间、相邻行间、相邻帧间存在强相关性，这种 相关性就表现为空间冗余和时问冗余。视频图像的空间冗余一般通过离散余弦变 换( d i s c r e t ec o s i n et r a n s f o i t l l ，d c t ) 、离散小波变换( d i s c r e t ew a v e l e tt r a n s f o i t n ， d w t ) 等变换来去除，而视频图像的时间冗余则通常使用运动估计和运动补偿来 完成。 运动估计和运动补偿技术已广泛用于视频压缩的一些国际标准中，如i t u t h 2 6 1 1 ”，h 2 6 3 n ，m p e o 1 1 3 1 ，m p e o _ 2 1 4 1 ，m p e o 一4 嘲和h 2 6 l 1 6 1 。在这些视频压缩国际 标准中，运动估计是最关键的技术之一，它直接或间接地影响着后面的编码效率和 图像恢复质量。运动估计得越准确，补偿的残差就越小，编码的效率就越高，解 码出来的图像质量越好。并且，运动估计在整个系统中的计算复杂度最大，占了 整个系统的5 0 以上。要想提高视频编码的效率，必须提高运动估计的效率。所 以，研究并提出一种精确而又快速的运动估计算法具有十分重要的实际价值。 1 2 视频压缩编码技术的发展概况及国际标准 1 2 1 视频压缩编码技术的发展概况 1 9 4 8 年，o l i v e r 提出了第一个编码理论脉冲编码调制( p u l s ec o d i n g m o d u l a t i o n ，简称p c m ) ；同年，s h a n n o n 的经典论文“通信的数学原理”首次 提出并建立了信息率失真函数概念：1 9 5 9 年，s h a n n o n 进一步确立了码率失真理 论，以上工作奠定了信息编码的理论基础。主要编码方法有预测编码、变换编码 和统计编码，也称为三大经典编码方法。这些经典编码技术也被称为“第一代” 视频压缩编码运动估计算法研究 视频压缩编码技术。它们都是非常优秀的纹理编码方案，能够在中等压缩率的情 况下，提供非常好的图像质量，但在非常低的压缩率情况下，无法为一般的序列 提供令人满意的质量。八十年代初期，“第一代”编码技术已经达到了顶峰，这类 技术去除客观和视觉冗余信息的能力已接近极限。究其原因是由于这些技术都没 有利用图像的结构特点，因此它们也就只能以象素或块作为编码的对象，另外， 这些技术在设计编码器时也没有考虑人类视觉系统的特性。 为了克服“第一代”视频压缩编码技术的局限性，k u n t 等人于1 9 8 5 年提出了 “第二代”视频压缩编码技术。他们认为，“第一代”编码技术只是以信息论和数 字信号处理技术为理论基础，旨在去除图像数据中的线性相关性的一类编码技术。 其压缩比不高，大约在1 0 ：1 左右。而“第二代”编码技术不局限于信息论的框架， 要充分利用人的视觉生理、心理和图像信源的各种特征，实现从“波形”编码到 “模型”编码的转变，以便获得更高压缩比。其压缩比多在3 0 ：1 至7 0 ：1 之间，有 的甚至高达1 0 0 ：i 。“第二代”编码方法主要有：基于分形的编码、基于模型的编 码、基于区域分割的编码和基于神经网络的编码等。“第二代”编码方法充分利用 了计算机图形学、计算机视觉、人工智能与模式识别等相关学科的研究成果，为 视频图像压缩编码开拓出了广阔的前景。但是由于“第二代”编码方法增加了分 析的难度，所以大大增加了实现的复杂性。从当前发展情况来看，“第二代”编码 方法仍处于深入研究的阶段。例如，分形法由于图像分割、迭代函数系统代码的 获得是非常困难的，因而实现起来时间长，算法非常复杂。模型法则仅限于人头 肩像等基本的视频图像上，进一步的发展有赖于新的数学方法和其它相关学科的 发展。神经网络的工作机理至今仍不清楚，硬件研制不成功，所以在视频压缩编 码中的应用研究进展缓慢，目前多与其他方法结合使用。但由于巨大压缩性能的 潜力，人们都在致力于这些新方法的研究之中。 近年来，出现了一类充分利用人类视觉特性的“多分辨率编码”方法，如子 带编码、塔形编码和基于小波变换的编码。这类方法使用不同类型的一维或二维 线性数字滤波器，对视频图像进行整体的分解，然后根据人类视觉特性对不同频 段的数据进行粗细不同的量化处理，以达到更好的压缩效果。这类方法原理上仍 属于线性处理，属于“波形”编码，可归入经典编码方法，但它们又充分利用了 人类视觉系统的特性，因此可以被看作是“第一代”编码技术向“第二代”编码 技术过渡的桥梁。 1 2 2 视频压缩国际标准 为了在全世界范围内促进压缩技术的应用，由国际标准化组织( i n t e r n a t i o n a l s t a n d a r d i z a t i o no r g a n i z a t i o n ，简称i s o ) 和国际电信联盟( i n t e r n a t i o n a l 第一章绪论 t e l e c o m m u n i c a t i o nu n i o n ，简称i t u ) 制定了一系列视频压缩国际标准。由i t u 组 织制定的标准主要是针对实时视频通讯的应用，如视频会议和可视电话等，它们 以h 2 6 x 命名( 如h 2 6 1 ，h 2 6 2 ，h 2 6 3 和h 2 6 l ) ；而由i s o 和i e c ( i n t e r n a t i o n a l e l e c t r o t e c h n i c a lc o m m i s s i o n ，国际电工委员会) 的共同委员会中的m p e g 组织 ( m o v i n g p i c t u r e e x p e r t g r o u p ) 制定的标准主要针对视频数据的存储( 如d v d ) ， 广播电视和视频流的网络传输等应用，它们以m e p g - x 命名( 如m p e g i ，m p e g 2 ， m p e g 4 ，m p e g - 7 等) 。 标准的具体介绍见附录a 。 1 3 问题的提出背景 1 3 1 运动估计研究现状 要想提高视频压缩编码的效率，关键是要有准确的运动估计，因此运动估计 算法的研究成了多年来视频压缩编码的研究重点。运动估计算法多种多样，大体 上可以把它们分成四类：块匹配法、递归估计法、贝叶斯估计法和光流法。块匹 配运动估计算法因其具有算法简单、便于v l s i 实现等优点得到广泛应用。所以本 文重点研究块匹配运动估计算法。 目前，块匹配运动估计算法中搜索精度最高的是全搜索法( f s 8 1 ) ，它对搜索 范围内的每一个象素点进行匹配运算以得到一个最优的运动矢量。但它的计算复 杂度太高，不适合实时应用。为此人们提出了许多快速运动估计算法。早期的三 步法( t s s 9 1 ) ，二维对数法( t d l 1 0 b ，交叉法( c s 【1 1 1 ) 等，主要是通过限制搜索 位置的数目来减少计算量。但它们在第一步中搜索步长较大，不利于估计小的运 动块。动态搜索窗调整法( d s w a f l 2 】) 根据当前结果动态调整下一步搜索步长的 大小，算法性能在一定程度上有了改进。新三步法( n t s s t l 3 1 ) ，新四步法( n f s s t l 4 1 ) ， 基于块的梯度下降法( b b g d s ”】) 等利用运动矢量具有中心偏移的分布特性，提 高了匹配速度，减少了陷入局部极小的可能性，但它们都是以原点作为初始搜索 中心，没有充分利用相邻块之间的运动相关性。预测搜索法( p s a t l 6 j ) ，自适应运 动跟踪法( a m t s l l 7 】) 等利用相邻块的运动相关性选择一个反映当前运动块趋势的 预测点作为初始搜索点，以提高搜索速度和预测的准确性。1 9 9 9 年1 0 月，菱形法 ( d s 【1 8 】) 被m p e g 4 国际标准采纳并收入验证模型( v m 【1 9 1 ) 。经过研究发现，虽然 它的综合性能较其它算法优越，但它不能根据图像的内容( 运动类型) 作出灵活 处理。 尽管块匹配运动估计算法已成为目前许多压缩标准采用的主要方法，但由于 小波理论的发展和m p e g - 4 标准的提出，国际上已经开始将注意力投向多分辨率 的运动估计算法和基于视频对象的运动估计算法研究领域。多分辨率运动估计算 视频压缩编码运动估计算法研究 法不仅效率高，而且运动矢量场一致性好，从而具有较高的实用价值。b i e r l i n g 等 口叫提出分层运动搜索算法在运动矢量逼近真实运动和计算量降低方面都取得了一 定效益。在b i e r l i n g 基础上，李劲【2 i 】提出了更加系统化的多分辨率运动估计算法。 张旭东等【2 2 j 充分利用运动矢量场空域、时域和分层父子块之间的相关性自适应确 定搜索范围，构成空时相关多分辨运动估计算法( s t m e ) 。j a eh u nl e e 等1 2 3 j 为了 获得低功率高性能的运动估计器，提出了一种新的分层运动估计算法，并实现了 它的v l s i 结构设计，可以广泛应用于无线视频通信所需的低功率视频编码器。以 上都是基于空域进行运动估计，z h a n g 等【2 4 】将小波理论应用于视频编码时，提出 一种基于小波分解域的可变块大小多分辨率运动估计( m u l t i r e s o l u t i o nm o t i o n e s t i m a t i o n ，m 蹦e ) 算法，它利用小波金字塔结构每层间的相关性，来降低运动 估计过程的运算复杂度。而后，针对这一问题，s e o n g m a n k t 25 1 、许洁斌【2 6 】、刘红 梅1 27 j 等先后提出了自己的改进算法。 1 3 2 运动估计的基本原理 运动图像多数情况下只是其中的很少一部分图像在运动，同一场景相邻的两 幅图像之间在内容上的差异不会太大，或者说后一帧的内容与前一帧重复的部分很 多，如图1 1 所示。用数学术语来讲，二者是相关的。 ( a ) f o r m a n 序列第8 8 帧( b ) f o r m a n 序列第8 9 帧 图1 1 f o r m a n 序列中相邻帧图像 对于相关的视频图像，发送端不一定必须把每帧图像上所有的象素都传给接 收端，而只要将物体( 或摄像机) 的运动信息告知接收端，接收端就可以根据运 动信息和前一帧图像的内容来更新当前帧图像，这比全部传送每帧图像的具体细 节所需的数据量要小得多。 要这样做，首先要解决的问题是如何从序列图像中提取有关物体运动的信息， 这个过程称为运动估计( m o t i o ne s i t m a t i o n ，m e ) ，其表达方式是运动矢量( m o t i o n v e c t o r ，m v ) ，运动估计研究的主要内容就是如何快速、有效的获得有足够精度的 运动矢量；而把前一帧相应的运动部分信息根据运动矢量补偿过来的过程称为运 动补偿( m o t i o nc o m p e n s a t i o n ，m c ) 。 第一章绪论 如图1 2 所示，运动估计的基本思想是将图像序列的每一帧分成许多互不重叠 的宏块，并认为宏块内所有象素的位移量都相同，然后对于当前帧中的每一块到 前一帧或后一帧某一给定搜索范围内根据一定的匹配准则找出与当前块最相似的 块，即匹配块，由匹配块与当前块的相对位置计算出运动位移，所得运动位移即 为当前块的运动矢量( m o t i o nv e c t o r ) 。利用搜索到的运动矢量在参考帧上进行运 动补偿，补偿残差( d i f f e r e n c e ) 经d c t 变换、量化、行程编码后与运动矢量共同经 熵编码，然后以比特流形式传出去。 c u r r e r l t u i 捆u l l q 图1 2 运动估计的基本思想 1 3 3 提高运动估计效率的主要研究技术 运动估计算法的效率主要体现在图像质量、压缩码率和搜索速度( 复杂度) 三个方面。运动估计越准确，预测补偿的图像质量越高，补偿的残差就越小，补 偿编码所需位数也就越少，且比特率也就越小；运动估计速度越快，越有利于实 时应用。提高图像质量，加快估计速度，减小比特率是运动估计算法研究的目标。 通过研究初始搜索点的选择、匹配准则、运动搜索策略可以有效提高算法效率。 本文将在第三章对初始搜索点的选择、匹配准则、运动搜索策略这三个主要 研究技术进行详细介绍。 1 4 研究工作概要和章节安排 1 4 1 主要工作 本文主要对视频压缩编码系统和块匹配运动估计算法进行了研究，在此基础 上，提出一种基于起点预测的快速运动估计算法，论文后期，对多分辨率运动估 计算法在空域和小波域分别进行了探讨和研究，并提出一种改进算法。 研究工作分为以下五个阶段进行： 视频压缩编码运动估计算法研究 1 前期工作中，涉足数字图像研究领域，熟悉视频压缩编码系统，学习j p e g 系列、m p e g x 系列和h 2 6 x 系列的国际视频压缩的标准，熟悉其算法原理，获得 总体上的认识。 2 重点研究了运动估计和与之紧密相关的运动补偿技术，对目前国际上先进 的运动估计算法进行分析和研究。通过查阅和整理相关领域的文献，建立运动估 计算法的实验平台，对一些经典算法进行了模拟仿真，并进行性能比较。 3 提出一种基于起点预测的快速运动估计算法( p r e d i c t i o na n dc o m b i n a t i v e p a t t e ma l g o r i t h m ，简称p c p ) ，并进行了算法仿真和与其它算法的性能比较。 4 后期工作中，对多分辨率运动估计算法在空域和小波域分别进行了研究和 探讨，模拟仿真了一些经典算法：针对现有多分辨率运动估计算法存在的问题， 提出一种基于内容的多分辨率运动估计算法( c o n t e n t - b a s e dm u l t i r e s o l u t i o n ，简称 c b m r ) 。 、 5 深入研究了最新视频压缩国际标准h 2 6 l 的高精度运动估计算法，对其进 行实验仿真和性能比较。 本文的主要成果： 1 深入学习和研究了视频压缩编码系统和现行的各种视频压缩标准，总结了 各类压缩标准所用到的主要技术；重点研究了块匹配运动估计算法，总结了提高 运动估计效率的主要研究技术：初始搜索点的选择、匹配准则、运动搜索策略； 归纳了目前国际上先进的运动估计算法。 2 结合初始搜索点的选择和模板组合，提出一种效率更高的运动估计算法： 基于起点预测的快速运动估计算法( p c p ) ，它充分利用了序列图像的运动矢量时 间、空间分布特性中心偏移性和相关性，设计了菱形和正方形两种模板，这 两种模板的组合一定程度上体现了人类视觉中视网膜感受野分布的特点，也体现 了基于内容搜索的特点。p c p 算法在搜索过程中，能根据图像的内容( 运动类型) 采用组合模板进行灵活处理，提高了块匹配的搜索速度。该算法具有基于内容搜 索的特点。实验结果表明，该算法在速度和准确性方面都优于传统的快速运动估 计算法。 3 对多分辨率运动估计算法在空域和小波域分别进行了研究和探讨，并针对 现有多分辨率运动估计算法普遍存在的问题：直接将上一级的运动矢量传递给下 一级进行更精细的运动估计，而不管该级估计得到的运动矢量是否已经满足或就 是全局最优运动矢量，提出一种基于内容的多分辨率运动估计算法( c b m r ) 。实 际中绝大多数图像序列的运动都很小，它们的运动矢量通常总是高度集中分布在 搜索窗的中心位置附近，对于这样的运动块，在父层能够满足一定精度的运动矢 量也没有必要传递到下一层作更精细的处理。c b m r 就利用了这一点，在搜索过 第一章绪论 程中根据图像的内容( 运动类型) 设置阙值对得到的运动矢量进行灵活处理，大 大减少了计算量。 4 为了能够很好的模拟、验证、比较和演示运动估计算法，作者在v i s u a lc + + 6 0 环境下开发了运动估计算法软件模拟平台，采用模块化编程思想，对各种算法 提供了统一的接口，为后续的研究奠定了基础。 1 4 2 论文章节安排 论文全文共分五章。第一章是绪论，简单介绍了视频编码技术的发展、视频 编码国际标准，并分析总结了运动估计算法研究现状、算法原理和主要研究技术； 第二章介绍了视频压缩编解码系统及其关键技术，详细研究了有效提高运动估计 算法效率的三个主要技术，并分析了一些较为典型的基于块匹配的运动估计算法； 第三章结合初始搜索点的选择和模板组合，提出了一种效率更高的运动估计算法： 基于起点预测的快速运动估计算法( p c p ) ，并作了详细的描述和性能分析：第四 章对多分辨率运动估计算法在空域和小波域分别进行了研究和探讨，提出一种基 于内容的多分辨率运动估计算法( c b m r ) ，并作了详细的描述和性能分析：第五章 深入研究了最新视频压缩国际标准h 2 6 l 的高精度运动估计算法，对其进行实验 仿真和性能比较；最后是对本文工作的总结和运动估计算法的研究展望。 视频压缩编码运动估计算法研究 第二章视频压缩编码与运动估计算珐研究 视频压缩编码的研究工作已经有5 0 多年的历史了，特别是8 0 年代中后期， 相关学科的迅速发展和新兴学科的不断出现为视频压缩编码的发展注入了新的活 力。人们对图像信息需求的巨增也有力地促进了视频压缩编码技术的进步。同时， 运动估计作为视频压缩编码的核心技术，也取得了很大的发展。本章将首先介绍 视频压缩编解码系统及其关键技术，然后重点介绍运动估计算法。 、 2 1 视频疰缩编解码系统与关键技术 2 1 1 视频压缩编解码系统 目前的视频编码国际标准的基本方法都是采用了基于d c t 变换的混合编码方 法，不同的标准针对不同的应用，采取了不同的编码策略来改进编码效率和获得 更好的图像质量。 典型的视频压缩编解码系统如图2 1 所示，它分两种编码模式；帧内( m 船舶m e ) 编码和帧n 叫e r - f r a m e ) 编码。框图显示了视频压缩编解码过程：如果进行帧内编 码，视频图像数据经过d c t 变换、量化、变长编码形成压缩码流放在缓冲区里， 同时量化后的数据又经过反量化、d c t 反变换重建图像并保存在帧存器里作为下 一帧的参考帧；在解码端，压缩码流经过逆过程重构视频图像。如果是进行帧间 编码，当前帧与帧存器里的参考帧先进行运动估计，得到当前帧的运动矢量，运 动矢量与参考帧又补偿出当前帧的预测帧，预测帧与当前帧相减得到预测误差， 然后对预测误差进行d c t 变换和量化，最后，把运动矢量和量化后的d c t 信息 一起进行变长编码，同时，量化后的d c t 信息又经过反量化、i d c t 变换得到预 测误差，预测误差与先前的预测帧相加得当前帧，存入帧存器作为下一帧的参考 帧。在解码端，压缩码流经过变长解码分成两部分：运动矢量和预测误差的逆信 息。将预测误差的逆信息经过反量化、i d c t 变换得到预测误差；将运动矢量与帧 存器里的前一帧进行运动补偿得到预测帧，再将预测帧与预测误差相加就得到了 当前帧的重构图像，同时保存到帧存器里作为下一帧的参考帧。图中的“控制” 是针对位速率的，编码器的输出应该与给定的位速率匹配，当缓冲区的信息快要 占满时，量化步长就要增加，以减少编码的信息，当然会导致图像质量下降；反 之，减小步长，改善图像质量。 第二章视频压缩编码与运动估计算法研究 ( a ) 编码器 视频输出 ( b ) 解码器 图2 1 典型的视频压缩编解码系统框图 2 1 2 视频压缩关键技术 由视频压缩编解码系统框图可以看出，它包括d c t 变换、量化、变长编码、 缓存控制、运动估计、运动补偿等部分。下面对这些关键技术进行简单说明。 1 、离散余弦变换d c t d c t 是一种空间变换，一般以8 x 8 的象素块为单位进行，生成的是8 x8 的 d c t 系数数据块。d c t 变换的最大特点是对于一般的图像都能够将象素块的能量 集中于少数低频d c t 系数上，即生成8 8 d c t 系数块中，仅左上角的少量低频 系数数值较大，其余系数的数值很小，这样就可以只编码和传输少数系数而不严 重影响图像质量。d c t 不能直接对图像产生压缩作用，但对图像的能量具有很好 的集中效果，为压缩打下了基础。 2 、量化器 量化是针对d c t 变换系数进行的，量化过程就是以某个量化步长去除d c t 系数。量化步长的大小称为量化精度，量化步长越小，量化精度就越细，包含的 信息越多，但所需的传输频带越高。不同的d c t 变换系数对人类视觉感应的重要 性是不同的，因此编码器根据视觉感应准则，对一个8 8 的d c t 变换块中的6 4 个d c t 变换系数采用不同的量化精度，以保证尽可能多地包含特定的d c t 空间 频率信息，又使量化精度不超过需要。d c t 变换系数中，低频系数对视觉感应的 1 0 视频压缩编码运动估计算法研究 重要性较高，因此分配的量化精度较细；高频系数对视觉感应的重要性较低，分 配的量化精度较粗，通常情况下，一个d c t 变换块中的大多数高频系数量化后都 会变为零。 3 、之字型扫描与游程编码 d c t 变换产生的是一8 8 的二维数组，为进行传输，还须将其转换为一维排 列方式。有两种二维到一维的转换方式，或称扫描方式：之字型扫描( z i gz a g ) 和 交替扫描，其中之字型扫描是最常用的一种，扫描过程如图2 2 所示。由于经量化 后，大多数非零d c t 系数集中于8 x 8 二维矩阵的左上角，即低频分量区，之字 型扫描后，这些非零d c t 系数就集中于一维排列数组的前部，后面跟着长串的量 化为零的d c t 系数，这些就为游程编码创造了条件。 图2 2 之孚型扫描 游程编码中，只有非零系数被编码。一个非零系数的编码由两部分组成：前 一部分表示非零系数前的连续零系数的数量( 称为游程) ，后一部分是那个非零系 数。这样就把之字型扫描的优点体现出来了，因为之字型扫描在大多数情况下出 现连零的机会比较多，游程编码的效率就比较高。当一维序列中的后部剩余的d c t 系数都为零时，只要用一个“块结束”标志0 1 0 b ) 来指示，就可结束这一8 8 变 换块的编码，产生的压缩效果是非常明显的。 4 、熵编码( 变长编码) 量化仅生成了d c t 系数的一种有效的离散表示，实际传输前，还须对其进行 比特流编码，产生用于传输的数字比特流。简单的编码方法是采用定长码，即每 个量化值以同样数目的比特表示，但这种方法的效率较低。而采用熵编码可以提 高编码效率。熵编码是基于编码信号的统计特性，使得平均比特率下降。游程和 非零系数既可独立的。也可联合的作熵编码。熵编码中使用较多的一种是霍夫曼 编码。霍夫曼编码中，在确定了所有编码信号的概率后生产一个码表，对经常发 生的大概率信号分配较少的比特表示，对不常发生的小概率信号分配较多的比特 表示，使得整个码流的平均长度趋于最短。 5 、信道缓存 第二章视频压缩编码与运动估计算法研究 1 1 由于采用了熵编码，产生的比特流的速率是变化的，随着视频图像的统计特 性变化。但大多数情况下传输系统分配的频带都是恒定的，因此在编码比特流进 入信道前需设置信道缓存。信道缓存是一缓存器，以变比特率从熵编码器向里写 入数据，以传输系统标称的恒定比特率向外读出，送入信道。缓存器的大小，或 称容量是设定好的，但编码器的瞬时输出比特率常明显高于或低于传输系统的频 带，这就有可能造成缓存器的上溢出或下溢出。因此缓存器须带有控制机制，通 过反馈控制压缩算法，调整编码器的比特率，使得缓存器的写入数据速率与读出 数据速率趋于平衡。缓存器对压缩算法的控制是通过控制量化器的量化步长实现 的，当编码器的瞬时输出速率过高，缓存器将要上溢时，就使量化步长增大以降 低编码数据速率，当然也相应增大了图像的损失；当编码器的瞬时输出速率过低， 缓存器将要下溢出时，就使量化步长减小以提高编码数据速率。 6 、运动估计 运动估计使用于帧间编码方式时，通过参考帧图像产生对被压缩图像的估计。 运动估计的准确程度对帧间编码的压缩效果非常重要。如果估计做的好，那么被 压缩图像与预测图像相减后只留下很小的值用于传输。运动估计以宏块为单位进 行，计算被压缩图像与参考图像的对应位置上的宏块间的位置偏移。这种位置偏 移是以运动矢量来描述的，一个运动矢量代表水平和垂直两个方向上的位移。 运动估计涉及三种帧结构：i 帧、p 帧、b 帧。只包含帧内编码的帧称为i 帧， 对i 帧或p 帧前向预测得到的帧称为p 帧，对i 帧或p 帧双向预测得到的帧称为b 帧。图2 3 显示了含有这三种帧结构的一个序列。运动估计时，p 帧图像使用前面 最近解码的i 帧或p 帧作参考图像，称为前向预测；而b 帧图像使用两帧图像作 为预测参考，称为双向( b i d i r e c t i o n a l l y ) 预测，其中一个参考帧在显示顺序上先 于编码帧( 前向预测) ，另一帧在显示顺序上晚于编码帧( 后向预测) ，b 帧的参考帧 在任何情况下都是i 帧或p 帧。b 帧图像不仅压缩比最高，而且误差不会传递，这 是因为b 帧本身不会被用作预测的基准。此外，对利用两幅图像进行双向预测的 结果加以平均，有助于平滑噪声的影响。 图2 3 包含i 帧、p 帧和b 帧的图像序列 视频压缩编码运动估计算法研究 7 、运动补偿 利用运动估计算出的运动矢量，将参考帧图像中的宏块移至水平和垂直方向 上的相对应位置，即可生成对被压缩图像的预测。运动补偿假设当前帧是前面帧 的某种平移，这就为使用预测和内插提供了机会。当某帧图片被作为参考时，后 序帧只是由于摄像机或图片中物体的移动与前面稍有不同。运动补偿试图在压缩 时补偿物体或摄像机的这一运动。对于帧中每个要被编码的块( 即正被处理的当 前帧) ，参考帧中的最佳匹配块都是在许多候选块中搜索得到的。得到的运动矢量 被看作是一种分析指示，从参考帧中已有块的位置指向正被编码帧中它的新位置。 在某种意义上说，这是试图与运动物体的新位置保持一致。这种保持一致的过程 可基于预测或内插。预测只需要当前帧和参考帧。基于产生的运动矢量值，预测 方法试图发现物体新的相对位置并通过详尽比较某些块来确认它。在内插中，运 动矢量的产生与两个参考帧相关，一个来自前面的帧，另一个是后面的预测帧。 在两个参考帧中搜索最佳匹配块，取平均值作为块在当前帧的位置。 2 2 运动估计算法研究 从视频压缩编码技术可以看出，运动估计在整个编码系统中起了关键作用， 它直接和间接影响着编码的效率和图像恢复质量。因此，运动估计算法的研究也 就成了视频压缩算法的研究重点。运动估计研究的主要内容是如何快速、有效的 获得有足够精度的运动矢量。这方面的一种有效方法是块匹配运动估计b m m e ( b l o c k - m a t c h i n gm o t i o ne s t i m 砒i o n ) ，它目前已被许多视频编码标准所采纳，例如 i t u th 2 6 1 ，h 2 6 3 ，m p e g 1 ，m p e g - 2 ，m p e g - 4 ，h 2 6 l 等。但现有的块匹配运动 估计算法速度较慢，不利于实时应用。因此，必须寻找更加快速、准确的高效的 运动估计算法。 2 2 1 块匹配运动估计算法简介 顾名思义，块匹配运动估计就是将图像划分成许多互不重叠的子块，并认为 子块内的所有象素具有运动一致性，且只作平移运动，然后对当前帧图像的每一 子块( 也即宏块) ，在参考帧的一定范围内按照一定的匹配准则进行匹配，搜索与 当前子块最相似的块，即匹配块，该匹配块在参考帧所处的位置就认为是当前子 块位移前的位置，由匹配块与当前子块的相对位置所得的运动位移即为当前子块 的运动矢量。图2 4 显示了块匹配中宏块、搜索区域和运动矢量的关系睇。 第二章视频压缩编码与运动估计算法研究1 3 图2 4 块匹配中宏块、搜索区域和运动矢量的关系 宏块大小为m x n ，般取1 6 1 6 。这是一个折衷的选择，因为在宏块大小 的选择上存在矛盾：1 ) 宏块必须足够大，如果太小，很可能发生匹配到有相同灰 度值但与场景无关的块，并且块小增加运算量，所需传输的附加信息也增加了。2 ) 宏块必须足够小，因为如果在一个块里存在不同运动矢量，匹配块就不能提供准 确的估计。 搜索范围一般由最大偏移矢量来决定，而偏移矢量又是基于帧间图像的时间 分辨率和块内图像的空间分辨率，以及帧序列图像的性质而选定的。设可能的最 大偏移矢量为( d x m 。，d y j 。) ，则搜索范围为( m + 2 d x 。) x ( n + 2 d y m 。) 。如 最大偏移矢量取( 7 ，7 ) ，则搜索范围为( 3 0 3 0 ) 。这是对于整个宏块而言，对 于宏块中的每一个象素其实搜索范围是1 5 1 5 。 常用的匹配准则有最小绝对差( m a d ) 、最小均方误差( m s e ) 和归一化互相关 函数( n c c f ) 。 2 2 2 提高运动估计效率的主要研究技术 由图2 1 视频压缩编解码系统框图可以看出，变长编码处理的数据一是运动估 计产生的运动矢量，二是运动补偿后的预测残差的变换系数，它们都来自于运动 估计的结果。这就要求运动估计具有足够的准确性。同时，运动估计占据了整个 系统的5 0 以上运算量，要提高系统的性能，必须降低运动估计算法复杂度，提 高运动估计的速度。总之，提高运动估计的效率是视频压缩算法的研究重点。 运动估计算法的效率主要体现在图像质量、压缩码率和搜索速度( 复杂度) 三个方面。运动估计越准确，预测补偿的图像质量越高，补偿的残差就越小，补 偿编码所需位数越少，比特率越小；运动估计速度越快，越有利于实时应用。提 1 4 视频压缩编码运动估计算法研究 高图像质量，加快估计速度，减小比特率是运动估计算法研究的目标。通常通过 研究初始搜索点的选择、匹配准则、运动搜索策略来提高算法效率。 一、初始搜索点的选择 1 直接选择参考帧对应的( 0 ，o ) 位置 这种方法简单，但易陷入局部最优点。如果采用的算法初始步长太大，而原 点又不是最优点，有可能使快速搜索跳出原点周围可能性比较大的区域而去搜索 远距离的点，导致搜索方向的不确定性，故有可能陷入局部最优。 2 选择预测的起点 、 由于相邻块之闻和相邻帧之间具有很强