（计算机科学与技术专业论文）h264中基于视频序列特征的块匹配运动估计研究.pdf

：! ：；j 、：， b l o c k m a t c h i n gm o t i o ne s t i m a t i o nf o rh 2 6 4 b a s e do nv i d e os e q u e n c e sf e a t u r e s p e c i a l t y ： c o m p u t e rs c i e n c ea n dt e c h n o l o g y _ m a s t e r d e g r e ec a n d i d a t e ： c h e ny u a n s u p e r v i s o r ：a s s o c i a t ep r o f r e ns h e n g - b i n g s c h o o lo fi n f o r m a t i o ns c i e n c ea n d e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h a ，h u n a n ，p r c 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：j 叁垂日期：丛年三月丑日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：受l 旦导师签名么娼期：丝! ! 年羔月型日 摘要 块匹配运动估计在h 2 6 4 视频编码中占一半以上的计算量，其匹 配速度和精度直接影响到编码的速度和质量。通常，搜索模板和搜索 策略对块匹配运动估计起着决定作用。然而以往的块匹配算法没有充 分利用视频序列自身的特征，大多数采用固定的搜索模板或单一的搜 索策略，对具有不同运动程度的块无法进行分开处理，使块匹配运动 估计缺乏适应性，一定程度上限制了编码效率的提升。 针对以往算法的缺陷，为进一步提高块匹配运动估计的整体性 能，本文在研究视频序列内部特征的基础上，提出了一种基于混合模 板的搜索算法( m i x e dp a t t e r nb a s e ds e a r c h ，m p b s ) ，并在研究了选 取初始搜索中心的基础上，对m p b s 做了进一步的改进。 论文首先对块匹配运动估计的经典搜索算法进行了详细的讨论 和深入的分析，总结了各种算法的优缺点。然后，论文通过研究视频 序列自身的特征，详细分析了视频序列中运动矢量的中心偏置特征和 相邻块之间的空间相关性。同时通过实验进行统计分析，得出了在初 始搜索模板以外的运动矢量分布模型，发现有约5 6 8 的运动矢量分 布在初始搜索模板的最小块误差点和次小块误差点之间的区域，利用 这些特征和实验结果设计出了一种混合搜索模板以及相应的搜索策 略，包括十字模型的初始搜索模板、直线型的后续搜索模板和两种模 板混合搜索的策略。并由此在研究视频序列特征的基础上提出了快速 块匹配算法m p b s 。最后，论文进一步研究了预测初始搜索中心在 m p b s 算法中的应用及其影响，使m p b s 算法得到进一步的改进。 实验结果表明，在保持图像质量基本不变的情况下，本文提出的 算法比几种典型的块匹配运动估计算法平均减少约5 0 的搜索点数。 而应用了预测初始搜索中心的m p b s 算法在原来基础上进一步减少 约1 7 5 的搜索点数，同时，图像峰值信噪比提高了0 3 4 d b 。 关键词：块匹配运动估计，中心偏置，混合搜索，预测中心 a bs t r a c t b l o c k - m a t c h i n gm o t i o ne s t i m a t i o n ( b m e ) t a k e sm o r et h a nh a l fo f c o m p u t a t i o ni nh 2 6 4v i d e oc o d i n g t h em a t c h i n gs p e e da n da c c u r a c yo f b m ed i r e c t l ya f f e c tt h e c o d i n gs p e e da n dq u a l i t y g e n e r a l l y , s e a r c h p a r e ma n ds e a r c hs t r a t e g yp l a ya ni m p o r t a n tr o l ei nb n m h o w e v e gt h e p r e v i o u sb m 匣a l g o r i t h m sd o n tm a k eu s eo ft h ev i d e os e q u e n c e sf e a t u r e f u l l y m o s to ft h e ma d o p tr e g u l a rs e a r c hp a t t e mo rs i n g l es e a r c hs t r a t e g y a n dc a nn o td e a lw i t ht h eb l o c k sw h i c hh a v ed i f f e r e n tm o t i o nd e g r e e r e s p e c t i v e l y s o i tm a k e st h eb m eb ed e f i c i e n ti na d a p t a b i l i t ya n d r e s t r i c t st h ee f f i c i e n c yo fc o d i n gt os o m ee x t e n t d u et ot h ed e f e c t so f p r e v i o u sb n 匝a l g o r i t h m sa n df o rt h ep u r p o s e o fi m p r o v i n gt h ep e r f o r m a n c eo fb m e ，t h i st h e s i sp r o p o s e sam i x e d p a t t e r nb a s e ds e a r c h ( m p b s ) a l g o r i t h m ，b a s e do nt h er e s e a r c ho fv i d e o s e q u e n c e sf e a t u r e ，a n da f t e rt h er e s e a r c ho fh o wt oc h o o s et h ei n i t i a l s e a r c hp o i n t ，t h et h e s i sm a k e saf u r t h e ri m p r o v ef o rm p b s t h et h e s i sf i r s t l ym a k e sad e t a i l e dd i s c u s s i o na n dad e e p l ya n a l y s i s f o rc l a s s i cb m 匣a l g o r i t h m s a n ds u m m a r i z e st h e a d v a n t a g e sa n d s h o r t c o m i n g so ft h o s ea l g o r i t h m s t h e nt h r o u g ht h er e s e a r c ho fv i d e o s e q u e n c e sf e a t u r e ，t h et h e s i sa n a l y z e st 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 f t h em o t i o nv e c t o r ( m v ) a n dt h es p a t i a lc o r r e l a t i o no f n e i g h b o r i n gb l o c k s a tt h es a m et i m e ，t h r o u g he x p e r i m e n t a la n a l y s i s ，t h i st h e s i so b t a i n st h e d i s t r i b u t e dm o d e lo fm vo u t s i d et h ei n i t i a ls e a r c hp a t t e m a n df i n d st h a t t h e r ea r ea b o u t5 6 8 o fm o t i o nv e c t o r sl o c a t e db e t w e e nm i n i m u m b l o c kd i s t o r t i o n ( m b d ) p o i n ta n ds e c o n d a r ym i n i m u mb l o c kd i s t o r t i o n ( s m b d ) p o i n t t a k i n ga d v a n t a g eo ft h o s ef e a t u r e sa n dt h ee x p e r i m e n t a l r e s u l t s ，t h i st h e s i sd e s i g n sam i x e ds e a r c hp a t t e ma n di t ss e a r c hs t r a t e g y c o r r e s p o n d i n g l y , i n c l u d i n g t h ei n i t i a l c r o s s e d - p a t t e m ，t h ef o l l o w i n g l i n e p a t t e m ，a n dt h em i x e ds e a r c h i n gs t r a t e g yo ft w op a t t e m s t h e nt h e t h e s i sp r o p o s e st h ef a s tb 匝a l g o r i t h m 【p bsb a s e do nt h er e s e a r c ho f v i d e os e q u e n c e sf e a t u r e l a s t l y , t h et h e s i sm a k e saf u r t h e rr e s e a r c ho nt h e a p p l i c a t i o nt op r e d i c ti n i t i a ls e a r c hc e n t e rf o r m b s a n di m p r o v e st h e bsb vu s i n gt h i st e c h n i q u e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mc a nr e d u c e m o r et h a n5o o fs e a r c hp o i n t s c o m p a r e dw i t ht h o s ec l a s s i cb 匝 i i a l g o r i t h m s ，w h i l em a i n t a i n i n gt h eq u a l i t yo fp i c t u r e s w h e nt h em b p s u s e st h ei n i t i a ls e a r c hc e n t e rp r e d i c t i o n ，i tc a nr e d u c e 17 5 o fs e a r c h p o i n t sm o r et h a no r i g i n a l ，a n da l s oi m p r o v et h ep s n r b y0 3 4 d b k e y w o r d s ：b l o c k - m a t c h i n gm o t i o ne s t i m a t i o n ，c e n t e r - b i a s e d ，m i x e d s e a r c h ，p r e d i c t e dc e n t e r i i i 目录 摘要i a b s t r a c t i i 第一章绪论一l 1 1 课题背景和意义1 1 2 国内外研究现状1 1 3 论文研究内容及组织结构4 1 3 1 论文的研究内容4 1 3 2 论文的组织结构4 第二章块匹配运动估计研究6 2 1 运动估计6 2 1 1 运动估计原理6 2 1 2 块匹配运动估计6 2 1 3 块匹配准则7 2 2 块匹配运动估计算法分析8 2 2 1 全搜索算法8 2 2 2 三步搜索法9 2 2 3 四步搜索法9 2 2 4 菱形搜索法1 1 2 2 5 六边形搜索法。1 2 2 3 块匹配运动估计在h 2 6 4 中的应用1 4 2 3 1h 2 6 4 标准1 4 2 3 2h 2 6 4 基本原理1 4 2 3 3h 2 6 4 中运动估计的新特征1 6 2 4 本章小结1 7 笫三章视频序列特征与运动矢量分布分析18 3 1 视频序列内部特征18 3 1 1 运动矢量的中心偏置特性1 8 3 1 2 相邻块的空间相关性1 9 3 2 初始搜索模板外运动矢量的分布2 l 3 2 1 运动矢量分布分析一2 1 3 2 2 运动矢量分布分析实验2 2 3 3 本章小结2 5 第四章基于视频序列特征的快速块匹配算法2 6 4 1 搜索模板2 6 4 1 1 初始搜索模板2 6 4 1 2 混合模板：2 7 4 2 搜索策略2 8 4 2 1m b d 点在中心2 9 i v 4 2 2m b d 点和s m b d 点在相邻的边界2 9 4 2 3s m b d 点在中心3 0 4 2 4m b d 点和s m b d 点距中心相背3 0 4 3 基于混合模板的块匹配算法m p b s 31 4 4 实验结果与分析3 2 4 4 1 实验平台与参数设置3 2 4 4 2 实验结果与分析3 4 4 5 基于选取初始搜索中心的m p b s 算法改进3 7 4 5 1 预测初始搜索中心在m p b s 算法中的应用3 7 4 5 2 改进算法的实验结果与分析3 9 4 6 本章小结4 2 第五章总结与展望：。4 3 5 1 论文总结4 3 5 2 研究展望4 4 参考文献4 5 致谢5l 攻读学位期间主要的研究成果5 2 v 硕士学位论文 第一章绪论 第一章绪论 1 1 课题背景和意义 随着网络和通信技术的飞速发展，信息交流的内容越来越丰富，已经从简单 的文字信息交流逐步发展到声音、图像以及视频信息的交流。在这些信息当中， 图像和视频信息最能给人以直观、确切的感受。由于原始的视频信息数据量比较 庞大，要实现视频信息的存储和传递，则需对这些信息进行必要的规整化。基于 此，人们在视频编码领域经过多年的努力探索，已经形成一系列标准，包括 m p e g - x 、h 2 6 x 等标准，一般来说越到后面的标准越高级。h 2 6 4 t l 】于2 0 0 3 年 颁布以来就一直倍受关注，更高的压缩效率以及网络传输中更强的抗抖动能力是 其受青睐的主要原因，预计将成为未来流行通用的视频编码格式。然而，由于新 标准的复杂性，导致其编码复杂度、编码时间都普遍增大，并且对硬件的要求也 提高了，所以，人们正努力通过各种方法对其改进和优化，使其能更有效的应用 于实际当中。 h 2 6 4 的编码过程主要包括预测、变换和量化、熵编码等一系列步骤。其中， 块匹配运动估计是整个编码过程中最为复杂，最耗时间的一个关键步骤，在h 2 6 4 中占用5 0 以上的计算量，由此可见块匹配运动估计在整个h 2 6 4 编码标准中占 有重要地位。而以往大多数块匹配运动估计算法的改进是以降低视频质量或者增 大系统资源开销为代价，存在着一定的缺陷：固定的搜索模板和单一的搜索策略 不能根据不同特征的块和物体运动的方向以及运动的剧烈程度自适应的改变搜 索半径和搜索范围；没有充分挖掘和利用视频序列自身的特征，包括运动矢量的 特征以及块之间的关联特征等等。本文通过对视频序列自身特征的深入研究，以 及在改进块匹配运动估计算法中所做的工作将为运动估计快速、精确的实现块匹 配搜索提供一条新的有效途径，从而进一步丰富视频编码领域中块匹配运动估计 的研究内容。不仅在视频压缩编码的研究与发展方面具有重要的理论意义，而且 在工业、商业等领域也有着广泛的实际应用价值。 1 2 国内外研究现状 由于h 2 6 4 采用了许多新技术，使其在压缩效果和对网络的适应性方面都有 了很大程度的提高。但是，h 2 6 4 性能的改善是对很多新技术改进的结果，而这 些新技术的采用产生了巨大的计算量( 尤其是运动估计) ，还不能达到实时应用 硕士学位论文 第一章绪论 的要求。所以人们一直将运动估计的研究视为视频编码的研究重点，不断有人提 出新的算法或者对已有算法进行优化和改进。 按照匹配对象的大小进行分类，运动估计算法可分为下面三类： ( 1 ) 基于像素匹配的运动估计 e f s i r a t i a d i ss n 等人提出了基于像素递归的算法( p e l r e c u r s i v em o t i o n e s t i m a t i o n a l g o r i t h m ) 【2 1 。该类型的运动估计算法1 2 4 】以像素为基本搜索单位，能 体现出各个像素点不同的运动状态，所以具有较高的精确度，但是随之而来的是 加大了计算复杂度，用硬件实现代价大，总的来说，其实用性较差。 ( 2 ) 基于对象匹配的运动估计 基于对象匹配的运动估计算法【5 7 】通常将视频图像进行分割，形成若干个对 象，然后对这些对象进行匹配。这类算法大多要进行视频对象的分割，而目前的 分割算法【8 。1 0 】发展比较缓慢，所以在一定程度上影响了该类运动估计算法的研究 进展。同时，由于分割出来的对象可能大小不一，无任何规则与共同点，导致算 法的设计复杂性与计算复杂度增加，所以该类算法还不能达到实用的目的，近年 来发展相对缓慢。 ( 3 ) 基于块匹配的运动估计 块匹配运动估计算法以块为基本搜索单位，而每个块包含若干个像素点，并 假设每个块内的所有像素点具有一致的运动状态。由于其以规格尺寸的块为单 位，使得运动估计的计算复杂度大大降低，得到了广泛的应用。目前，国内外研 究人员提出了一系列的块匹配算法。 k o g at 等人提出了三步搜索法( t h r e es t e ps e a r c h ，t s s ) 【l l 】，通过正方形 模板，采用由粗到细的搜索模式进行块匹配。由于初始搜索模板覆盖的范围较大， 使其对小运动的块进行匹配的效率降低。但是整体上是一种快速匹配算法，促进 了快速搜索算法的发展，后来提出了一些改进的三步搜索法【1 2 。1 3 1 。 l ir 等人提出的新三步搜索法( n e wt h r e es t e ps e a r c h ，n t s s ) 【1 2 】在t s s 的基础上做了改进。针对t s s 中对于小运动块的匹配效率低这一缺陷，n t s s 改 进了初始搜索模板，包括一个外围的大正方形和一个内置的小正方形，n t s s 降 低了陷入局部最优的可能，提高了搜索效率。 p ol m 等人提出的四步搜索法( f o u rs t e ps e a r c h ，f s s ) 1 4 l 同样使用正方形 初始搜索模板，但是缩小了模板覆盖的范围，对大运动的块和小运动的块做了个 折中，提高了运动估计的整体效率。 z h us 等人提出的菱形搜索法( d i a m o n ds e a r c h ，d s ) 【1 5 j 首次采用了两种搜 索模板：大菱形模板和小菱形模板，进一步调整了搜索模板的大小和适应性。 d s 算法先由大菱形模板进行粗匹配，再有小菱形进行细匹配，提高了运动估计 2 硕士学位论文 第一章绪论 的匹配速度和精度，并被m p e g - 4 标准纳入其验证模型。d s 算法是一种性能优 异的块匹配算法，后来又有人提出了基于d s 算法的改进算法，c h e u n gch 等人 提出了十字菱形搜索算法( c r o s s d i a m o n ds e a r c h ，c d s ) b 6 ，还有其他改进的 d s 算法【1 1 7 。2 1 】等等，他们在一定程度上获得了性能的提高。 h o s u rpi 等人提出的运动矢量场自适应搜索算法( m o t i o nv e c t o rf i e l d a d a p t i v es e a r c ht e c h n o l o g y ，m v f a s t ) 【2 2 j 采用了终止判决的方法，通过事先设 定一个阈值，在进行搜索匹配时，如果( 0 ，o ) 点的误差值小于这个阈值，则停 止搜索，否则再根据当前块的运动类型使用菱形模板进行匹配搜索。该算法通过 提前终止的准则加快了运动估计的速度。 z h uc 等人提出的六边形搜索算法( h e x a g o n - b a s e ds e a r c h ，h e x b s ) 2 3 】， 在延续菱形算法两个模板的基础上，将大菱形模板替换为六边形模板，使初始模 板覆盖的范围更为均匀，从而在一定程度上提高了匹配速度。但是由于搜索点 数的减少，其搜索精度有所下降，后来有人提出了几种改进的六边形搜索算法 2 4 - 2 6 ) o 近年来，仍有不少人相继提出了一些新的块匹配算法，包括基于内容自适应 性的块匹配算法【2 7 2 9 】、基于预测起点的块匹配算法【3 0 。2 1 、基于正方形模板的搜索 算法【3 3 。3 5 1 、基于八边形搜索模板的块匹配算法 3 6 - - 3 8 1 、多种模板进行搜索的块匹配 算法【3 9 4 3 1 、以及其他算法 4 4 - 5 川等等。当前的块匹配运动估计正向图像内容自适应 性、混合模板、预测起点等方向发展。 除以上类型的运动估计外，还有部分研究人员从其他领域研究运动估计，主 要提出了以下几个方面的运动估计算法： 多分辨率搜索的算法【5 1 5 3 】，该类型的算法先将当前待编码的图像进行抽样， 得到一个粗分辨率的图像样本，运动估计从这个分辨率较粗的样本开始搜索，找 到样本中的最佳匹配点后，再以该匹配点为起点，逐步提高图像分辨率继续搜索， 直至在图像达到正常的分辨率的基础上搜索到最佳匹配点。 基于小波域的运动估计算法【5 4 弓6 j ，该类型的算法主要在小波域中对图像残差 的变换系数进行搜索匹配，由于其实现难度大，没有得到广泛的应用。 还有诸如基于相位相关的算法【5 7 - 5 9 1 、遗传算法【6 0 石2 1 等等，皆因实现难度大、 计算复杂度高，并且精度不够等原因而没有得到实际应用。 综合上述，块匹配算法以块为基本匹配单位，虽然使得运动估计在精度上会 比基于像素匹配的运动估计低，但是大大降低了计算复杂度，易于硬件实现， h 2 6 4 正是采用的块匹配运动估计。然而以往的块匹配运动估计的算法如t s s 、 n t s s 、f s s 等，大多使用固定的搜索模板或者单一的搜索策略，没有根据视频 序列自身的特征设计出能适应不同运动程度的搜索模板和策略，一定程度上限制 3 硕士学位论文第一章绪论 了运动估计整体性能的提升。为此，本文将着重研究基于视频序列特征的快速块 匹配运动估计。 1 3 论文研究内容及组织结构 1 3 1 论文的研究内容 为进一步提高块匹配运动估计算法的性能，使视频序列自身的特征得到充分 的利用，本论文主要对以下三个方面着手研究： ( 1 ) 运动矢量的中心偏置特征 通常，视频序列中存在大量的背景内容，这些背景内容被划分成块后，就形 成许多静止块或者小运动的块，而这些块的运动矢量都很小，大部分集中在原点 附近。本文在研究这个特点的基础上将对块匹配运动估计的初始搜索模板的选取 一、 进行详细的分析与讨论。 ( 2 ) 初始搜索模板外的运动矢量分布 前一个研究点的研究内容解决了静止块和小运动块的快速搜索问题，对于运 动矢量分布在初始搜索模板外的块，本文通过研究运动矢量在初始搜索模板外的 分布状态，设计出有针对性的混合搜索模板，并提出基于混合模板的快速块匹配 算法，进一步提高块匹配运动估计的速度。 ( 3 ) 相邻块运动矢量的空间相关性 视频序列内同一个图像中，相邻块通常具有相似的运动趋势，他们的运动矢 量也具有相似性。本文详细阐述了运动矢量的空间相关性，在第一个研究点的基 础上，利用这个特点为运动程度较大的块预测运动矢量，根据匹配误差最小的原 则，在原点和预测运动矢量对应点之间选择一个初始搜索点，减少初始搜索模板 陷入局部最优的可能，对提出的算法进行改进，提高了算法的速度和精度。 同时，本文还将通过实验对提出的算法与一系列典型的块匹配运动估计算法 进行测试对比，并对实验结果进行分析讨论。 1 3 2 论文的组织结构 本论文共有五章，各章的主要研究内容如下： 第一章绪论，通过查阅和调研国内外文献资料，首先介绍了本论文的课题背 景和研究意义，其次总结出了运动估计的国内外研究现状，最后阐述了本论文的 主要研究内容并列出了本文内容的组织结构。 第二章首先阐述了视频编码中运动估计的基本原理，重点讲述了块匹配运动 4 硕士学位论文第一章绪论 估计。其次详细分析了几种典型的块匹配运动估计算法，概括了各个算法的性能 和优缺点。最后叙述了块匹配运动估计在h 2 6 4 中的应用，并对h 2 6 4 中块匹配 运动估计的新技术做了说明。 第三章主要通过分析视频序列内部特征，详细阐述了运动矢量的中心偏置特 征和相邻块的空间相关性。同时，通过实验分析了初始搜索模板以外运动矢量的 分布情况，为本文算法的设计做铺垫。 第四章为算法设计，首先利用视频序列自身的两个特征设计出了一种混合搜 索模板，其次提出了相应的搜索策略，概括出算法的具体步骤，然后通过实验测 试了算法的性能，最后提出了一种选取初始搜索中心的方法，将其应用到算法中， 并通过实验测试了对算法性能的影响。 第五章为总结与展望，首先总结了本论文所作的研究工作，然后指出了以后 的研究展望。 5 硕士学位论文 第二章块匹配运动估计研究 2 1 运动估计 2 1 1 运动估计原理 第二章块匹配运动估计研究 在帧间预测编码中，相邻图像往往存在较强的相似性，两个相邻图像之间的 差别很可能只是其中某一个物体移动了。因此，可以把一个图像分成若干个有运 动的对象，再设法搜索出该图像的每个对象在邻近图像中的位置，并求出二者之 间的相对位移量，就得到了通常所说的运动矢量。而搜索这个位置并求运动矢量 的过程在视频编码技术中被称为运动估计。 当然，运动估计并不能保证完全精确。因为在普遍的视频序列中，一个图像 中的某个对象并不一定能在相邻图像中找到与其完全匹配的对象，两者之间在亮 度或者色度方面或多或少都存在一些差别。虽然如此，通过运动估计仍然可以大 量去除视频序列的时间冗余，降低编码后传输的比特数。可以说，帧间预测是视 频编码里实现压缩的一个非常重要的技术手段。 帧间预测除了要求得运动矢量外，还要计算出残差图像即预测产生的误差， 并在编码后与运动矢量一起发送到解码端。解码器就根据运动矢量在已确定的邻 近参考图像中找到对应的位置，和残差图像相加，在不考虑量化等过程带来的其 他误差时，就能还原原始的图像。 2 1 2 块匹配运动估计 在运动估计中，如果图像被划分得到的对象无任何规则，就很难进行处理。 因为很难对任意轮廓的物体形成一种统一的计算公式或标准。目前，科研人员正 在对基于对象的运动估计进行研究。块匹配运动估计解决了上述难题，使得运算 更简单高效。图2 1 为块匹配运动估计的示意图，图中箭头所指的方向和距离就 是对当前块进行块匹配搜索得到的运动矢量。 6 硕士学位论文第二章块匹配运动估计研究 当前图像 图2 1 块匹配运动估计图示 块匹配运动估计的基本思想是把视频序列的每个图像都划分成一定规格大 小( 如1 6 1 6 、8 木1 6 、4 * 4 等) 、互不重叠的子块，并且假设各个子块内的所有 像素具有相同的运动趋势，只做平移运动，不包括旋转、伸缩等，然后在参考图 像的一定范围( 称为匹配窗口) 内按照预先确定好的匹配准则搜索与之最相似的 块，如图2 1 所示，称找到的最相似的块为( 当前块的) 预测块。当前块与预测 块之间的位移就是当前块的运动矢量，当前块与预测块图像内容的差值被称为残 差图像。此时，在知道参考图像、运动矢量以及残差图像的基础上，就能重构原 始图像了。 2 1 3 块匹配准则 在视频编码中，块匹配运动估计依据某种计算规则进行匹配，我们称之为匹 配准则，匹配准则在一定程度上影响了计算的复杂度，常见的块匹配准则有如下 3 种： ( 1 ) 最小绝对差准则( m a d ) 心。o ，歹) = 面1 万刍m 善nl 以，甩) 一 一。+ z ，刀+ 歹) l 公式( 1 1 ) 公式( 1 - 1 ) 中，i 、j 为参考图像内欲拿来进行匹配的某个块内部各个像素 点的位置，m 、n 为块的大小尺寸，五为当前图像的灰度值，以一，为参考图像的 灰度值。公式得到的结果即当前块与参考图像内各个块的像素灰度值求绝对差的 和再除以块的大小。通常选取结果最小的点作为最佳匹配点。 7 硕士学位论文第二章块匹配运动估计研究 ( 2 ) 最小均方误差准则( m s e ) m s e ( i ，) = 击蚤m 荟1 阮，力) 一以一t + 咖+ ) 】2 公式( 1 - 2 ) 1 ，t 同样，在公式( 1 2 ) 中，m s e 准则选取m s e 值最小的点作为最佳匹配点。 ( 3 ) 绝对误差和准则( s a d ) mn s a d ( i ，歹) = i 以( m ，n ) - a 一。+ f ，n + j ) m = ln = l 公式( 1 - 3 ) 在实际的编码系统中，考虑到硬件实现的条件，为降低计算复杂度，一般选 取m a d 作为匹配准则。同时，考虑到m a d 中存在乘法，增加了一定的复杂度， 通常使用公式( 1 3 ) 中的绝对误差和( s a d ) 作为实际的匹配准则。s a d 只在 m a d 的基础上去掉了乘法运算，对运动估计的精度影响很小，但是降低了计算 复杂度，易于软件和硬件的实现。 2 2 块匹配运动估计算法分析 块匹配运动估计具有简单高效、额外开销小、易于硬件实现等优点而被包括 h 2 6 4 在内的大多数视频编码标准采用。为了提高运动估计的速度和效率，进一 步提高视频编码的效率，国内外研究人员经过努力钻研，提出了一系列的快速块 匹配运动估计算法。大多数提出的算法虽然在精度上略有下降，但是在速度上得 到了明显的体现。下面将介绍并分析一些典型的块匹配运动估计算法。 2 2 1 全搜索算法 全搜索( f u l ls e a r c h ，f s ) 算法又称穷尽搜索法，是对匹配窗口内所有的点 进行搜索匹配。该算法简单可靠，能得到精度最高的运动矢量，也即全局最优点， 是块匹配运动估计中精度最高的算法。但因其计算量较大，不利于进行实时处理， 实际工程项目中较少应用。一般都用来对新算法进行比较，衡量其他算法的速度 与精度。 8 硕士学位论文第二章块匹配运动估计研究 2 2 2 三步搜索法 三步搜索( t h r e es t e ps e a r c h ，t s s ) 算法【】使用了由大到小的搜索模式，首 先以原点为搜索中心，取搜索半径的一半为步长，将原点及周围距离步长的8 个点都进行匹配计算，得到一个差值最小的点，称为最小块误差( m i n i m u mb l o c k d i s t o r t i o n ，m b d ) 点。然后将中心移到m b d 点，对距离m b d 半个步长的8 个 点进行匹配计算，得到一个新的m b d 点。如果此时步长已为1 ，则该m b d 点 所在的位置就是对应的运动矢量，否则继续将步长减半搜索新的m b d 点。 图2 2 表示的是一个t s s 的搜索方式和过程，圆圈内的数字表示搜索进行到 第几步。可以看到，第一步搜索从原点( o ，o ) 开始，对其围绕8 个点以及自身 均进行匹配计算得到m b d 点的位置为( 4 ，4 ) ；第二步将步长减半，以( 4 ，4 ) 为中心进行同样的匹配得到新m b d 点的位置为( 4 ，6 ) ：第三步再将步长减半， 以( 4 ，6 ) 为中心继续匹配计算，得到最终的m b d 点( 4 ，7 ) 。 一、 厂一、 厂、 丫丫丫 小 小厶 v一一， 丫 入 丫 令 八 弋! 广 小 小一岔) _仓 丫丫i 厂、，；、八i 一 厶累球狲 丫累高累y 图2 2 三步搜索法举例 t s s 的初始搜索窗步长较大，而且采用的是固定的搜索模板，效率不是很高。 如果搜索范围扩大，可能最终会超过3 步，但是相对于全搜索法，它还是有明显 的优势。为快速运动估计的研究与继续改进打下了基础。 2 2 3 四步搜索法 四步搜索法( f o u rs t e ps e a r c h ，f s s ) 算法【1 4 】与t s s 选用9 串9 的初始搜索窗口 不同的是，f s s 算法选用的是5 幸5 的初始搜索窗口，如图2 3 ( a ) ，同样是匹配计算9 个点，但是f s s 缩小了搜索范围。 9 硕士学位论文第二章块匹配运动估计研究 士拉+ 拉护。_ 扛。_卜_ lj l t - + 厂l 丫 # 人 丫 占 上 丫 土 上 丫 上 卜_1 ( a ) 初始模板( b ) 新增5 点( c ) 新增3 点 图2 3 四步搜索法模板 f s s 的基本步骤为： ， ( 1 )以原点为中心，计算5 * 5 窗口内的9 个点，如果m b d 点就在中心，则 跳到第4 步，否则，执行下一步。 ( 2 )如果m b d 点位于5 * 5 窗口的四个角上，则只需新增5 个点就能构成一 个新的5 * 5 窗口，如图2 3 ( b ) 所示，而t s s 每步都需要新增8 个点。如果m b d 点位 于5 * 5 窗口的其他位置，则只需要新增3 个点就能构成新的搜索窗口，如图2 3 ( c ) 所示。计算完后，如果m b d 点位于新窗口中心，则跳到第4 步执行，否则，执行 下一步。 ( 3 )搜索方式同上，但搜索完后要执行第4 步。 ( 4 )减小步长，将搜索窗口缩小为3 * 3 ，此次计算出的m b d 点所在的位置 就是对应的运动矢量。 图2 4 给出了一个f s s 的例子，第一步从原点开始搜索5 * 5 窗口里的9 个点，找 到第一个m b d 点位于( 2 ，o ) ；第二步以( 2 ，o ) 为中心组成新的5 * 5 窗口，经 计算得到新的m b d 点( 4 ，2 ) ；第三步以( 4 ，2 ) 为中心组成新的5 * 5 窗口，经 计算得到新的m b d 点( 6 ，2 ) ；第四步则以( 6 ，2 ) 为中心，将搜索窗缩小为3 * 3 ， 计算得到最终的m b d 点为( 6 ，1 ) ，即要求的运动矢量。 、一、一 、一h 妙弋! _ 卜弋! 广k 纠 、 ) _ 卜 厂h - 、! 广 v h h 厂 小小 小累累茏 vy 一 v厂 郴搽 小厶k 弋厂ki 厂弋i 厂 图2 4f s s 搜索举例 1 0 硕士学位论文第二章块匹配运动估计研究 f s s 的提出又一次改进了运动估计，它的初始搜索窗为5 * 5 大小，l 卜, t s s d ， 所以总的计算复杂度会降低，提高了运动估计的效率。但由于仍采用了固定的搜 索模板，使得块匹配速度不能进一步提高。 2 2 4 菱形搜索法 菱形搜索( d i a m o n ds e a r c h ，d s ) i s l 算法采用了大菱形和小菱形两种模板搜 索，是快速块匹配算法中性能比较优异的算法之一，曾被国际标准纳入到验证模 型里。图2 5 为d s 算法的初始搜索模板，该模板包含了9 个搜索点，各个点距离中 心的位置有可能不相等。 图2 5d s 算法的初始搜索模板 d s 算法的基本步骤是： ( 1 ) 用大菱形模板匹配计算其9 个点的误差值，如果m b d 点位于菱形中 心，则跳到第3 步执行，否则进入下一步。 ( 2 )以上一步得到的m b d 点为中心，组成一个新的大菱形模板再进行匹 配计算，如果新m b d 点位于中心，则跳到第3 步，否则，重复当前步骤。 ( 3 )以上一步最后的m b d 点作为中心，采用小菱形模板进行匹配计算， 此时得到的m b d 点所在的位置即为对应的运动矢量。 图2 6 为d s 算法的一个例子，首先计算大菱形模板的9 个点，得到m b d 点的 位置( 2 ，o ) ，然后以( 2 ，o ) 为中心组成新的大菱形进行计算，得到新的m b d 点( 3 ，1 ) ；再以( 3 ，1 ) 为中心组成新的大菱形进行计算，发现m b d 点不变， 仍停留在大菱形中心，此时，将大菱形模板替换成小菱形模板，计算得到最终的 运动矢量为( 4 ，1 ) 。 硕士学位论文第二章块匹配运动估计研究 一、 八 h 匕裂八 l象澄算港一 八一旷 瞪努一户 v 一门弋o k 八冷黔墨八： y v 、 l厂 ky 图2 6 菱形搜索算法举例 d s 算法首次采用了混合模板，大菱形模板搜索范围广，用它来进行粗定位， 有利于降低运动估计陷入局部最优的可能性；在粗定位的基础上，小菱形模板能 更快速的搜索出最优的m b d 点，从而得到运动矢量。两种模板的混合使用，能 形成优势互补，提高了运动估计的速度和效率。由此可见采用混合模板的算法更 有利于块匹配运动估计性能的提高。 2 2 5 六边形搜索法 六边形搜索( h e x a g o n b a s e ds e a r c h ，h e x b s ) 1 2 3 算i 主i z h uc 等人提出。大 菱形模板的中心与周围各个点的距离不一定相等，搜索的范围非均匀，可能会引 起各个方向搜索速度的不一致，使整体速度下降。而h e x b s 采用了六边形的搜 索模板，使各个方向的搜索速度相同。图2 7 为h e x b s 的初始模板，h e