（信号与信息处理专业论文）视频编码中运动估计算法研究.pdf

摘要 摘要 随着近年来多媒体技术的飞速发展，许多视频应用如视频点播、视频会议、 手机视频等都要求视频压缩系统具有实时性，快速、高效的压缩算法是解决这一 问题的关键。运动估计作为视频压缩的关键技术，也是压缩编码中运算最复杂、 最耗时的环节，有研究结果显示，对于新一代视频编码标准h 2 6 4 ，单帧参考， 运动估计占总运算量的7 0 ；多参考帧参考，这个比例能达到9 0 。因此快速而 高效的运动估计算法一直是工业界和学术界研究的热点。在各种运动估计方法中， 块匹配法由于其简单、易于硬件实现等优点，其相关快速算法得到了广泛的研究 和应用。本文重点研究了基于单参考帧帧和多参考帧帧的块匹配运动估计快速算 法。主要内容为： 在详细分析了各种经典运动估计算法的基础上，针对单参考帧的情形，根据 运动矢量的分布特性，综合采用多参考运动矢量预测、自适应的终止准则、多搜 索模板等一系列技术，提出了一种改进的自适应十字方形运动估计快速算法。通 过在h 2 6 4 验证模型j m l 0 2 上测试发现，与其他算法相比，本算法在保持相似的 峰值信噪比和码率的前提下，计算复杂度最低，表明了本算法的高效性。 针对h 2 6 4 支持多参考帧和多模式的特点，根据运动矢量的统计特性以及各 个参考帧和各个模式对编码效率的提升作用不同的特点，提出了一种改进的基于 h 2 6 4 的多参考帧运动估计快速算法。本算法形式简单、易于实现，充分考虑了 图像序列的时空相关性，将运动矢量复用和多种终止条件的结合在一起。实验证 明，在低码率序列图像传输中，此多参考帧搜索算法在匹配精度和运算速度方面 都有一定的优越性。 关键词：h 2 6 4 标准，视频编码，运动估计，块匹配 a b s t r a c t a b s t r a c t w 池t h er a p i dd e v e l o p m e n to fm u l t i m e d i at e c h n i q u e s ，m a n yv i d e oa p p l i c a t i o n s s u c ha sv i d e oo nd e m a n d ，v i d e oc o n f e r e n c e ，m o b i l ev i d e on e e dt h ev i d e o c o m p r e s s i o ns y s t e mt ob ear e a l t i m eo n e t h ek e yp o i n tt os o l v et h i sp r o b l e mi st h e f a s ta n de f f i c i e n tc o m p r e s s i o na l g o r i t h m a sav i t a lt e c h n i q u eo fv i d e oc o m p r e s s i o n ， m o t i o ne s t i m a t i o n ( m e ) i sa l s ot h em o s tc o m p l e xa n dt i m e c o n s u m i n gm o d u l e s o m e r e s e a r c h e ss h o wt h a tm o t i o ne s t i m a t i o nt a k e s7 0 o ft h et o t a lc o m p u t a t i o nf o ro n e r e f e r e n c ef l a m ec a s e ，a n dy e tf o rm u l t i - r e f e r e n c ef l a m e st h ep r o p o r t i o nc a nr i s eu pt o 9 0 t h e r e f o r ef a s ta n de f f e c t i v em o t i o ne s t i m a t i o na l g o r i t h m sa r et h em o s tc o m m o n s e a r c ha r e af o ri n d u s t r i a la n da c a d e m i cr e s e a r c h e r s i na v a r i e t yo fm o t i o ne s t i m a t i o n m e t h o d s ，d u et ot h ee x c e l l e n c eo fs i m p l e n e s sa n dh a r d w a r ei m p l e m e n t a t i o no fb l o c k m a t c h i n ga l g o r i t h m ( b m a ) t h er e l a t i v ef a s ta l g o r i t h m sh a v ee x t e n s i v er e s e a r c h e sa n d a p p l i c a t i o n s t h et h e s i s f o c u s e so nr e s e a r c h e sa b o u tf a s tb l o c km a t c h i n gm o t i o n e s t i m a t i o na l g o r i t h m sb a s e do n s i n g l e a n dm u l t i - r e f e r e n c ef r a m e t h em a i n a c h i e v e m e n t sa r ea sf o l l o w s f o ro n er e f e r e n c ef r a m ec a s e ，a c c o r d i n gt ot h ed i s t r i b u t i o n a lc h a r a c t e r i s t i c so f m o t i o nv e c t o r s ，an e wf a s tb l o c km a t c h i n ga l g o r i t h mn a m e da c s si sp r o p o s e dw h i c h i sb a s e do nt h ed e t a i l e da n a l y s i so fv a r i o u sc l a s s i c a lm o t i o ne s t i m a t i o na l g o r i t h m t h e n e wa l g o r i t h me x p l o i t sas e r i e so ft e c h n i q u e ss u c ha sm u l t i p l er e f e r e n c em o t i o nv e c t o r p r e d i c t i o n , a d a p t i v et e r m i n a t i o nc r i t e r i aa n dm u l t i p l es e a r c ht e m p l a t e s a c c o r d i n gt o t e s to nh 2 6 4v e r i f i c a t i o nm o d e lj m10 2 ，w i t ht h es i m i l a rp e a ks i g n a lt on o i s e r a t i o ( p s n r ) a n db i t r a t et h en e wa l g o r i t h mh a st h em i n i m u mc o m p u t a t i o n a l c o m p l e x i t y t h a td e m o n s t r a t e st h en e wa l g o r i t h mi sm o s te f f e c t i v ec o m p a r e dw i t h o 也e r s w i t hr e g a r dt ot h ec h a r a c t e r i s t i c st h a th 2 6 4t a i l s u p p o r tf o rm u l t i r e f e r e n c e f l a m ea n dm u l t i - m o d e lm o t i o ne s t i m a t i o n , af a s tm u l t i r e f e r e n c ef r a m em o t i o n e s t i m a t i o na l g o r i t h mf o rh 2 6 4i sp r o p o s e da c c o r d i n gt ot h es t a t i s t i c a lc h a r a c t e r i s t i c s o f m o t i o nv e c t o ra n dd i f f e r e n te f f e c t sf o rc o d i n ge f f i c i e n c ye n h a n c e m e n to fv a r i o u s r e f e r e n c ef r a m e sa n db l o c kp a t t e r n s t h ea l g o r i t h mi ss i m p l ea n de a s yt oi m p l e m e n t l i a b s t r a c t a n dm e a n w h i l ei tt a k e sf u l l yi n t oa c c o u n tt h es p a t i o - t e m p o r a lc o r r e l a t i o no fi m a g e s e q u e n c e sa n dc o m b i n e sm o t i o nv e c t o rr e u s ew i t l lav a r i e t yo ft e r m i n a t i o nc o n d i t i o n s e x p e r i m e n t ss h o wt h a t a tl o wb i t - r a t eo f i n l a g es e q u e n c et r a n s m i s s i o n , t h u s m u l t i - r e f e r e n c ef l a m es e a r c ha l g o r i t h mh a ss o m ea d v a n t a g e si nm a t c h i n ga c c u r a c ya n d s p e e d o f o p e r a t i o n k e y w o r d s ：h 2 6 4s t a n d a 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 i i i 主要符号表 n t s c d c t i d c t c 正 q c i f p 帧 b d m m s e i a d m 【p c m m e n c c f s a d b m a f s t s s n t s s d s m v f a s t u m h e x a g o n s e p z s m b d l d s p s d s p p s n r 主要符号表 一种电视标准，主要应用于美、日等国家和地区 离散余弦变换 离散余弦逆变换 视频信号的亮度分量分辨率为3 5 2 x 2 8 8 的公用中间格式 视频信号的亮度分量分辨率为1 7 6 x1 4 4 的公用中间格式 使用前向参考帧作运动补偿预测的编码图像 块失真度 均方误差函数 绝对平均误差函数 最大匹配像素数 最大误差最小函数 归一化相关函数 绝对误差和 块匹配算法 全搜索算法 三步搜索算法 新三步搜索算法 菱形搜索算法 运动矢量场自适应搜索算法 混合非对称交叉多六边形网格搜索算法 加强预测区域搜索算法 最小块失真 大菱形模板 小菱形模板 峰值信噪比 v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 魏一通n ，吼少。歹年阖 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 躲出导师躲卑 日期：j - 川年够月砂怕 第一章绪论 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 f f s ，2 0 秒的未压缩视频图像将占用5 6 0 m b i t 的存储空间，换句话说，当数据 不作压缩处理时，一张c d r o m 光盘只能储存2 0 秒钟的电视节目。要解决多媒 体信息存储容量大、数据传输率高的难题，就需要采用压缩技术。 经研究发现，图像数据表示中存在着大量的信息冗余，如时间冗余、空间冗 余、信息熵冗余、谱间冗余、几何结构冗余、视觉冗余和知识冗余等等。通过去 除这些冗余数据可以使原始图像数据极大的减少，从而解决图像数据量巨大的问 题。对于静态图像，最主要的数据冗余是空间冗余，而对于图像序列，除空间冗 余外，还存在着很大时间冗余。这是由于序列图像一般是位于同一时间轴区间内 的一组连续画面，其相邻帧间变化量一般很小，只是表现为移动物体所在的空间 位置略微不同。运动估计和运动补偿技术就是解决图像帧间时间冗余的很好方法。 运动估计与运动补偿是现阶段视频压缩编码的关键技术。它是一种实现帧间 编码的方法，利用前后两帧或若干帧之间的时间相关性，去除时间冗余度。帧间 编码之所以能减少冗余度，是因为在一般视频序列的两帧之间有很大的空间结构 相似性，如图1 1 ( a ) 和( b ) 所示，前后两帧的差帧可以用比帧内编码所需少 很多的比特数来进行编码，而帧间预测的方法基本上是以基于块匹配的运动估计 ( 补偿) 算法为主。 电子科技大学硕士学位论文 ( a 1 第3 3 帧第3 4 帧 图】- 】m o t h e ra n dd a u g h t e r 序列第”和3 4 帧 近年来，快速的块匹配运动估计算法在理论研究和实践应用中都得到了不断 的发展和完善。从全搜索法n - - 步搜索法f l 】、菱形搜索法闭、以及六边形搜索法口j 到自适应运动矢量场搜索算法h ( m v f a s t ) 、增强预测区域搜索算法口j ( e p z s ) 、 u m h e x a g o n s 算法【6 ) 等都提高了基于块匹配的运动估计算法的性能，也体现了运 动估计快速算法的不断发展。尽管通过这几年的研究，这些新算法已经达到了一 个很高的水平，但是运动估计模块作为视频编码中占用资源最多、耗对最长的部 分这一现实并未改变，它仍然是实现高质量实时编码器的瓶颈。如在h 2 6 1 【7 1 的编 码过程中，在采用著名的三步快速搜索法的情况下，运动估计仍要占用整个编码 过程的6 3 的计算量；而在h2 6 3 i s 编码器中，运动估计也还占用了4 2 的计算 量：对于新一代视频编码标准h2 6 4 唧，单帧参考，运动估计占总运算量的7 0 ， 5 帧参考，这个比例能达到9 0 【1 0 1 。各个视频压缩标准给出了视频压缩编码的框 架，对运动估计部分没有规定具体的实现算法。就运动估计而言，具体的算法和 控制策略，对设计者来说是开放的所以对运动估计算法的研究有着十分重要的 理论和现实意义。 基于块匹配的运动估计作为视频编码的关键技术，需要解决的问题是在保持 搜索精度的前提下如何提高它的估算速度。而鱼和熊掌不能兼得，这两个指标在 实际计算过程中往往无法同时达到最优，如何达到这两个指标的折衷具有很高的 理论和实际意义，是图像处理领域一个极其重要的研究课题。它的研究和应用必 第一章绪论 将促进计算机通信、图像通信和多媒体技术的发展。 本课题的创新点在于，通过研究已有的各种快速搜索算法的优缺点，在已有 算法的基础上，分别针对单参考帧和多参考帧提出了优化和改进块匹配运动估计 的快速搜索算法。 1 2 运动估计算法的发展及研究动态 运动估计是减少视频图像序列中帧间冗余的关键技术，所以国内外在这方面 的研究都比较多。m p e g - x 和h 2 6 x 等标准也都采用了运动估计算法。本节将介 绍一下目前运动估计技术的分类，为了提高编码效率运动估计所采用的主要技术 和当前快速运动估计算法的进展。 1 2 1 运动估计技术分类 运动估计是视频编码系统的一个重要的组成部分。运动估计的作用是消除连 续帧之间的时域冗余。人们提出了多类运动估计技术，以消除各种帧间冗余： ( 1 ) 块匹配运动估计( b m a )每个块中的运动被假定是恒定的，即整个 块进行平移，这称为块平移模型。运动估计问题是为每一个块在参考帧中寻找一 个运动矢量。块的形状一般采用正方形( 有时也使用三角形，适合仿射模型) 。这 种模型简单高效，被各种视频压缩标准所采用。 ( 2 ) 可变形块运动估计( d b m a ) 1 1 】块平移模型不适用于块的旋转、变 焦等复杂运动情形，一种改进的方式是将方形块映射到非正方的四边形，即每个 顶点均有一个运动矢量，这种使用高阶模型的基于块的运动估计方法称为可变形 块匹配算法( d b m a ) 。d b m a 得到的残差帧能量更小，但需要编码更多的运动 矢量，计算复杂度也很高。 ( 3 ) 基于网格的运动估计【1 2 】当前帧被一个网格所覆盖，运动估计的问题是 寻找每一个节点的运动，使得当前帧每个元素内的图案与参考帧中相应的变形元 素很好的匹配。每一个元素内的运动是由节点m v 内插得到的，从而不会有与块 匹配相关联的块失真，文献 1 3 】【1 4 】就使用网格运动估计结合三维小波编码，取得 了较好的压缩效果。 ( 4 ) 全局运动估计f 1 5 】全局运动估计是指估计视频序列中背景运动规律， 这是由摄像机作缩放、旋转、平移等运动引起的，m p e g - 4 t 1 6 】中采用的s p r i t e 1 7 】 编码就是一种全局运动估计编码方法，它通过预测当前帧在由整个图像序列生成 电子科技大学硕士学位论文 的s p r i t e 图像( 背景图像) 中的位置来实现运动图像压缩。 1 2 2 提高编码效率的运动估计技术 运动估计的作用是消除连续帧之间的时域冗余。如果运动估计的越准确，所 得到的残差图像能量就越小，也就能更有效的改善编码效率。为此，人们提出了 多种先进的运动估计技术： ( 1 ) 双向预测同时使用前后两帧作为参考，使用双向预测可以获得更高的 编码效率。在h 2 6 4 标准中，还可以给两个参考帧的匹配块赋以不同权值，为视 频编码提供了更大的灵活性。 ( 2 ) 多模式运动估计h 2 6 3 、m p e g - 4 标准引入了两种用于帧间预测的块 模式：1 6 x 1 6 和8 x $ ，h 2 6 4 标准则引入了7 种块模式：1 6 x 1 6 、1 6 x g 、8 x 1 6 、8 x 8 、 8 x 4 、4 x g 、4 x 4 。多模式运动估计解决了以往单一模式无法准确描述同一宏块内 多物体、多速度、多方向运动的困难，并且还可以精确表示具有不同像素精度的 纹理，更切合图像中实际运动物体的形状，大大提高了运动估计的精确程度。 ( 3 ) 亚像素运动估计自从h 2 6 3 和m p e g 2 【18 】等国际标准中相继采用半像 素精度的运动估计和运动补偿算法后，m p e g - 4 和h 2 6 4 中更引入1 4 像素精度 的运动估计技术来提高运动补偿的精度，因为精确的运动描述可以得到更小的预 测误差，从而获得更好的视觉质量。最新的研究【1 9 】表明，1 8 精度的运动矢量能 迸一步提高编码效率。 ( 4 ) 多参考帧运动估计传统的编码器只进行单参考帧运动估计，但是在镜 头抖动、光照变换、物体遮挡等情况下，仅仅参考前面一帧，往往不能找到最佳 的匹配块。h 2 6 4 为了提高运动估计的匹配准确度，采用多参考帧运动估计技术 增加搜索范围，这样做的结果是提高了搜索精度，更加有利于提高压缩比和信噪 比。 ( 5 ) 重叠块运动补偿( o b m c )o b m c 2 0 1 用来提高匹配图像的预测性能， 并显著减少了块失真。预测块中每个像素是由三个运动矢量计算得到的三个预测 值的加权和。这三个运动矢量分别是t 当前块、左边块和上边块的运动矢量。 ( 6 ) 无限定运动矢量允许运动矢量指向图像边界外，这能够使得编码性能 得到提高，特别是在摄像机运动或物体运动进出图像时。对指向图像外面的运动 矢量的预测信号是由重复图像的边界像素生成的。 4 第章绪论 1 2 3 块匹配运动估计快速算法 运动估计算法中预测精度最高的是全搜索法( f s ) ，即穷尽参考帧搜索窗内 所有可能的点进行比较，始终能找到失真最小的匹配块。但其计算复杂度太高， 不适合于v l s i 的设计，因而如何快速有效地进行运动估计就成了视频编码的主 要问题。 三步法【1 1 、对数搜索法【2 1 1 、交叉搜索法【划等首先被提出以加快搜索速度，它 们第一步都从搜索区域的中心开始，搜索步长等于或略大于最大搜索范围的一半。 然后以当前步的最佳匹配点为中心，不断使用减半的搜索步长( 模板尺寸) ，直到 步长为1 时结束。它们的不同仅在于搜索模板的样式。 由于真实视频序列中的运动矢量满足中心偏置特性，即绝大多数块的运动幅 度都很小，超过9 0 的运动矢量都在 2 ，2 】的范围内，于是出现了众多利用中心 偏置特性提高搜索效率的快速算法。新三步法【2 3 j 在三步法的基础上修改了第一步 的搜索模式，通过额外的中心8 个点加速了静止块的判别过程；梯度下降法【2 4 】从 原点开始使用3 x 3 模板，然后以最小块误差( m b d ) 点为新的中心进行搜索，这 个过程重复直到最小点位于模板中心为止：梯度下降法的模板尺寸较小，对于运 动剧烈的物体，需要较多的搜索步骤，因而四步法【2 5 1 、菱形法 2 1 、六边形法【3 1 从 原点开始使用较大尺寸的模板反复搜索，大模板结束后再检测4 个搜索点，提高 算法的速度和精度，它们的差异仅在于大模板的形状和搜索点数不同。 由于相邻块间的运动矢量有很强的相关性，可以从时空相邻的块中选择几个 候选运动矢量，取其中最好的一个作为后续步骤的搜索起点。m v f a s t 【4 j 、 p m v f a s t t 2 6 1 、a p d z s 2 7 1 、e p z s1 5 】等算法都是基于该类思想，u m h e x a g o n s 6 1 还 根据邻块的绝对误差和( s a d ) 和量化步长使用自适应的终止准则，当预测精度 满足预定要求时，就提前结束搜索过程，在保证搜索精度的基础上进一步提高了 搜索速度。此外，c d h s 2 引、a r p s 2 9 】等利用真实序列中水平和垂直方向的运动矢 量占较大比例的特点，设计了不同的十字模板、方向模板来跳过局部最优，从而 快速检测到最佳匹配点。 在多参考帧搜索方面，文献 3 0 】首先在各帧进行小范围的粗搜索选择最佳参 考帧，然后在该帧上进行更精确的搜索；文献 31 3 2 】充分利用物体在相邻帧中的 运动连续性，使用复合运动矢量预测各帧中的起始位置，极大的提高了搜索速度， 但需要存储较多的运动矢量；文献 3 3 】综合考虑了匹配精度和运动矢量精度的影 响，研究了多参考帧下的终止准则。文献 3 4 】则将多参考帧搜索和多模式块搜索 电子科技大学硕士学位论文 相结合，对于较大尺寸的模式，由于其编码中所占的比例较大，搜索相对较多的 参考帧，可以获得更高的编码效率。而小尺寸模式使用较为宽松的终止准则，对 编码效率影响不是很大。 在亚像素搜索方面，可以根据统计规律选取部分点进行搜索，如文献 3 5 】只 搜索整像素精度下最优和次优匹配点之间的亚像素位置；也可以假设搜索代价函 数在一定区域内呈某种规律分布，缩小搜索范围以减少搜索块数，最常见的是基 于抛物面模型【3 6 1 ，只需搜索抛物面最低处附近的几个亚像素位置和额外的s a d 曲面模型即可。文献【3 7 假定抛物面模型是分离的二次方程，x 和y 方向分别使 用一维的二次方程来预测出最佳运动矢量，进一步减少了模型计算量；文献 3 8 】 将抛物线模型推广到1 4 精度等情形，更适合h 2 6 4 标准的情形。 1 3 本论文的主要研究工作 本论文的主要工作是在基于块匹配的视频图像运动估计技术研究的基础上， 深入分析、全面总结现有的经典块匹配运动估计算法，比较了它们的性能的优劣。 在此基础上，分别针对单参考帧和多参考帧，提出了优化和改进后的运动估计快 速算法，同时对新算法的性能与经典算法作对比实验以证明其有效性。 本论文的主要工作体现在： ( 1 ) 在分析和研究了运动估计原理的基础上，对几种经典的块匹配运动估计 搜索算法如全搜索法、m v f a s t 、u m h e x a g o n s 、e p z s 等算法进行了详细的分析， 并总结了各种算法的特点； ( 2 ) 通过对视频序列运动矢量的分布特性进行统计发现，水平和垂直方向的 运动矢量居多，因此对大菱形模板进行了改进，分解成十字模板和方形模板，可 以对运动较剧烈的序列进行快速的方向跟踪和粗定位，有效的减少了搜索的点数， 加快了搜索速度： ( 3 ) 通过对各种快速运动估计算法阈值的选择方法进行了分析，发现 m v f a s t 采用固定的阈值( t = 5 1 2 ) 不具有普遍性，u m h e x a g o n s 算法引入了q p 对阈值的影响因子，计算过程复杂。考虑到算法的鲁棒性和计算方便，充分利用 了邻块的相关性，本文提出了三种门限值t l 、t 2 、t 3 ，分别用于不同搜索阶段的 终止判断，进一步提高了算法的性能； ( 4 ) 提出了一种改进的基于起始点预测的自适应十字方形搜索算法。此算 法充分利用了运动矢量的中心偏置特性，趋向于实际序列运动方向的方向模板， 6 第一章绪论 灵活有效的终止准则。对于静止块运用终止准则可以直接得到最终的运动矢量； 对于小运动序列，运用终止准则利用小模板进行小范围的搜索；对于运动较为剧 烈的块先采用大模板进行搜索，避免结果陷入局部最优： ( 5 ) 对自适应十字方形运动估计算法进行了仿真实验。通过平均峰值信噪 比( p 咖t ) 、码率、标准化的计算复杂度( n c c ) 来判断算法的性能。仿真实验 的结果表明，从p s n r 和码率两个指标来看，对于各种序列各种算法的运行结果 都非常接近，在计算复杂度方面，此算法在各种序列中的都是最小的，分别约为 u m h c x a g o n s 算法的2 0 3 0 、e p z s 算法的3 5 5 0 ，说明a c s s 算法是其中搜 索速度最快的算法； ( 6 ) 针对h 2 6 4 标准的多参考帧和多模式运动估计，在分析了多参考帧特征 的基础上，在参考大量的文献资料后，综合采用了运动矢量复用、终止准则、不 同模式间多参考帧选择的相关性判断、运动矢量精度检测、结合编码模式的终止 准则提出了一种基于h 2 6 4 的多参考帧快速运动估计算法； ( 7 ) 对基于h 2 6 4 的多参考帧快速运动估计算法进行仿真实验。仿真实验采 用5 种标准测试序列的前1 0 0 帧，与全搜索法、混合非对称交叉多边形网格搜索 算法( u m e h x a g o n s ) 进行了对比。对比发现此算法的p s n r 和平均码率跟f s 、 u m h e x a g o n s 算法非常接近，损失几乎可以忽略。同时，此算法每种模式平均每 帧只需要搜索3 7 个点即可，计算复杂度约为f s 的1 2 0 0 ，约为u m h e x a g o n s 算 法的1 6 ，适合硬件实现，有较大的实用价值。 1 4 本论文的组织 本论文共分五章，组织如下： 第一章绪论。阐述了本论文的研究背景与意义，运动估计算法的发展与研究 动态以及本论文的主要研究工作。 第二章块匹配运动估计原理与典型算法分析。介绍了运动估计的概念以及块 匹配运动估计的原理，叙述了块匹配运动估计的几项技术指标，列举了几种典型 的运动估计快速算法，分析了它们各自的技术特点和优缺点，为算法的进一步改 进提供依据。 第三章基于单参考帧的运动估计快速算法。详细介绍了本文提出的一种改进 的自适应十字方形运运动估计快速算法，并进行系统仿真实验来论证论文中的改 进算法，通过对比实验发现改进后的算法优于其他对比算法。 7 电子科技大学硕士学位论文 第四章基于多参考帧的运动估计快速算法。介绍了本文提出的一种改进的多 参考帧快速运动估计算法基于h 2 6 4 的多参考帧快速运动估计算法。详细介 绍了算法的原理，并进行系统仿真实验来论证了论文中算法的性能，通过对比实 验发现此算法与经典的算法相比有一定的优越性。 第五章总结与展望。总结了全文的研究成果，并对运动估计算法研究进行了 展望，提出了进一步的研究工作。 8 第二章块匹配运动估计原理与典型算法分析 第二章块匹配运动估计原理与典型算法分析 通常情形下，图像序列中的大多数宏块属于静止背景，同一场景相邻的前后 两帧图像之间在内容上的差异不会太大，也就是说相邻两帧，甚至是相邻数帧的 内容有很多是重复的，这说明相邻的图像帧是相关的，用香农的信息论观点解释 就是运动图像存在数据冗余，因为是在时间上连续的前后帧，即时间冗余。般 的视频图像中都存在大量的时间冗余，如果将上一帧相同空间位置处的像素值作 为待编码的当前帧的预测值，这种预测对图像中的静止背景部分将是很有效的。 但是对于运动部分，这种不考虑物体运动的简单的帧间预测效果并不好。如果有 办法在对当前帧某像素( 或像素块) 进行预测时知道这个像素( 或像素块) 是从 上一帧的哪个位置移动过来的，也就是找出它们的运动相关性，在预测时以那个 位置上的像素值作为预测值，那么预测的准确性将大为提高。这个方法就是运动 估计技术，这种技术广泛使用于众多视频压缩国际标准中，如m p e g 1 2 4 和 h 2 6 1 3 4 等。 典型的视频压缩编解码系统如图2 1 所示，运动估计算法实现帧间编解码的 基本过程是这样的：在编码端，如图2 1 ( a ) 所示当前帧与帧存器里的参考帧先 进行运动估计，得到当前帧的运动矢量，由运动矢量和参考帧补偿出当前帧的预 测帧，预测帧与当前帧相减得到预测误差，然后对预测误差进行d c t 变换和量化， 最后，把运动矢量和量化后的d c t 信息一起进行变长编码，同时，量化后的d c t 信息又经过反量化、i d c t 变换得到预测误差，预测误差与先前的预测帧相加得 到重建帧，存入帧存器作为下一帧的参考帧。在解码端，如图2 1 ( b ) 所示，压 缩码流经过变长解码分成两部分：运动矢量和预测误差的逆信息，然后将预测误 差的逆信息经过反量化、i d c t 变换得到预测误差，将运动矢量与帧存器里的前 一帧进行运动补偿得到预测帧，再将预测帧与预测误差相加就得到了当前帧的重 构图像，同时保存到帧存器里作为下一帧的参考帧。 9 电子科技大学硕士学位论文 ( a ) 编码器 ( b ) 解码器 图2 - 1 典型的视频压缩编解码系统框图 21 块匹配运动估计原理 出 运动估计的基本思想是将运动图像的每一帧分成许多互不重叠的块，并假定 块中所有像素有相同的位移量，对整帧图像的编码分解为对帧中每个宏块的编码。 对当前帧的当前块编码时，首先在参考帧中一定范围的搜索区域内，按照一定的 匹配准则，通常计算绝对误差和( s a d ) ，寻找最为相似的块作为匹配块，编码时 只需对匹配块与当前块的相对位移( 运动矢量) 和像素差值进行编码。图2 - 2 为 第二章块匹配运动估计原理与典型算法分析 块匹配运动估计的示意图。 帧k - 1 ( 参考哟 帧k ( 当前蜘 图2 - 2 块匹配运动估计示意图 运动估计可以看作是对相邻图像帧时域相关性的检测，通过对相邻图像帧之 间相似部分的搜寻来获得图像中景物对象的运动信息。运动估计和补偿的基本过 程是通过一定的方法在参考帧图像中搜索当前帧图像的运动信息，再根据这些运 动信息在参考图像上进行相应的运动补偿操作，得到一个当前帧的重构图像。由 于运动估计时得到了当前图像与参考图像的相关信息，这个重构图像与当前图像 的差值往往比直接用参考图像和当前图像作差而得到的比特数要少得多，因此， 运动估计与补偿技术能有效减少相邻帧之间的数据冗余，从而获得更高的压缩比， 降低视频压缩编码后的码率。 运动估计的一个基本问题是如何选择运动信息的表示方式，这又与运动估计 的算法模型密切相关。最直接的方法是对于每一个当前帧的像素都采用一个二维 矢量( 由于我们这里讨论的都是针对二维图像的运动估计，因此每个被估计的图 像单元的运动信息都可以表示为一个由水平方向分量和垂直方向分量构成的二维 矢量) 来表示其运动信息，即我们通常所称的运动矢量。这种方法具有普遍的适 用性，但是由于视频图像通常具有非常多的像素，这样对每一个像素都进行运动 估计是不现实的，同时这样得到的运动矢量场的数据量太大而使得总的编码比特 反而不能减少。因此，在实际中，我们一般将图像帧分割为许多互不重叠的宏块， 并假定宏块中的所有像素做相同的平动，这样就可以分别对每个宏块独立地估计 其运动信息参数即运动矢量，这就是目前在各种主流的视频压缩标准( 如 m p e g 4 、h 2 6 4 等) 中被广泛应用的基于块匹配的运动估计方法。这种方法在运 动估计精度与计算复杂度之间提供了一个较好的折衷，其基本原理如图2 2 所示。 在对某一帧图像进行运动估计时，首先将其按照一定的方式划分成互不重叠 电子科技大学硕士学位论文 的若干个宏块，设宏块的大小为mxn ( h 2 6 3 、m p e g 2 和m p e g 4 建议采用 m = n = 1 6 ，而在h 2 6 4 中，将宏块继续划分为更小尺寸的块) ，然后再对每帧中的 宏块依次进行运动估计，获得各自的运动矢量。在基于块匹配运动估计和补偿的 视频压缩编码系统中，宏块是进行d c t 变换、量化、运动估计、运动补偿及图像 重建等操作的基本单元，即在运动预测编解码过程中均以宏块作为操作的单位。 为了便于说明块匹配算法的基本原理，设当前帧中的某目标宏块左上角像素点的 坐标为j = ( 石，y ) 。需要说明的是，由于假设宏块中的所有像素都作相同的平移运 动，因此宏块中的任意一点都可以标明其位置。然后，在参考帧中，以待估计宏 块的位置坐标s 为中心，在水平方向分别向左和向右扩展一定长度的搜索距离正， 而在垂直方向分别向上和向下扩展d v ，则可得到一个大小为( 2 d ，+ 1 1 ( 2 d ，+ 1 1 的 运动矢量搜索窗。搜索窗中的每一个点都对应着一个候选匹配宏块，设某个候 选宏块的左上角像素点的坐标为s = ( x ，y ) ，则该候选宏块相对于目标宏块的偏 移量m y 就是该搜索点对应的运动矢量，即： m v = j 一j = ( 工7 ，y ) 一( x ，y ) = ( x 一x ，y 7 一y ) = ( x ，a y ) ( 2 - 1 ) 块匹配运动估计的目的是在搜索窗中搜寻与目标宏块最为匹配的候选宏块， 并获得相应的运动矢量。其中，搜索窗的大小由视频中景物对象的运动速度决定。 对象的运动速度越快，搜索窗也应越大，即d ，和d ，的取值需加大，以覆盖更大的 运动范围，从而获得更高的预测精度。不过，较大的搜索窗通常会使得搜索点增 多，从而加大计算量，因此，搜索范围的设定需综合考虑具体视频的运动特性、 运动估计的质量以及算法的计算量等因素，以获得最佳的估计性能。 2 2 运动估计的关键技术 块匹配运动估计可以从以下五个方面进行研究：块的形状和大小、块匹配准 则、搜索起点预测、搜索策略以及算法评价指标。 2 2 1 块的形状和大小 块匹配方法隐含着如下假设：同一块内的像素的运动是一致的。显然这个假 设具有一定的片面性，但选择合适的块形状与大小可在一定的程度上消除这种片 面性。一般来说，块形状选用正方形是比较自然的选择，这样既便于图像的划分， 又有利于块匹配准则函数的计算。但这并不是最佳选择，因此有的算法采用了其 1 2 第二章块匹配运动估计原理与典型算法分析 他形状，如文献 3 9 1 采用了三角形块，文献【4 0 】针对视频对象的边缘形状特征，将 宏块按照不同形状的模块进行分割。 关于块的大小，显然块越小，得到的残差块越小，但这会导致块内进入较多 的运动矢量，可能降低编码的效率。作为折衷，通常选择1 6 x1 6 的宏块作为单位， 但由于它块尺寸相对较大，可能包含图像中的不同的运动部分，造成预测精度的 下降；在h 2 6 3 和m p e g 4 标准中则在宏块运动矢量的基础上加入8 8 块的运动 矢量，预测精度得到了一定的提高。而在h 2 6 4 编码标准中，在标准的参考代码 中，有1 0 个模式可供选择，即s k i p ，1 6 x 1 6 ，1 6 x 8 ，8 1 6 ，8 x 8 ，8 x 4 ，4 x 8 ， 4 x 4 ，i n t r a 4 x 4 和i n t r a l 6 x1 6 。其中s k i p 模式是指直接拷贝前一帧中对应的某一 宏块的运动矢量；i n t r a 4 x 4 和i n t r a l 6 x1 6 是帧内预测模式；而其他的模式分别代 表不同的块类型，如图2 3 。一个宏块可以采用上述7 中模式中的任意一种或是 多种组合。 图2 - 31 0 种不同的块模式 另外，有的运动估计算法，如分级块匹配采用的块大小可变的方案。其基本 思想是从最低分辨率级开始，在每一层依次进行运动估计。较低分辨率用于确定 电子科技大学硕士学位论文 相对较大块的位移得出粗略估计，接着把低分辨率级位移矢量的估计值传递到下 一个高分辨率级，较高分辨率级使用精细局部搜索微调位移矢量。 2 2 2 常见的块匹配准则 块匹配准则是判断块相似程度的依据，因此匹配准则的好坏直接影响了运动 估计的精度；另一方面，匹配运算复杂度、数据读取复杂度在很大程度上取决于 搜索采用的块匹配准则。因此，提高运动估计算法的速度可以有两种途径：一种 是减少搜索匹配的点数，另外一种是降低块匹配准则来减少复杂度。 视频压缩的一些国际标准，如h 2 6 1 ，h 2 6 3 ，m p e g i 4 ，m p e g 2 ，m p e g 4 中，并没有对视频编码器中的匹配函数给出统一的规定，估计精度高、运算复杂 度低的匹配准则函数仍然是视频编码中的研究热点。 设块尺寸为m x n ，搜索范围为d ，则搜索窗口为( m + 2 d ) x ( n + 2 d ) 。目前 常用的匹配准则有最小绝对差( m a d ) 、绝对误差和( s a d ) 、归一化互相关函数 ( n c f f ) 、最小均方误差( m s e ) 、最大误差最小函数( m m e ) 、最大匹配像素数 ( m p c ) 等，分别定义如下： ( 1 ) m a d 的表达式为： m a d ( “) = 击善m 善ni 五( 聊，玎) 一无一。( 加“州) l ( 2 - 2 ) ( 2 ) m s e 的表达式为。 m s e ( f ，) = 面1 刍m 犁n 五( 肌，刀) 一刖所“玎+ 明2 ( 2 3 ) ( 3 ) n c f f 的表达式为。 n c c f ( g ，歹) = ( 4 ) m p c 的表达式为： mn 五( 掰，栉) 五一。( m + i ，栉+ ，) m = l = l 1 4 ( 2 4 ) 第二章块匹配运动估计原理与典型算法分析 脚c ( f ，j ) = e z t ( f k ( m ， ) ，五一。( m + i ，玎+ 川 m 纠：一士f ( 2 5 ) 式中，石和五一。分别表示当前帧和参考帧，m 为宏块大小，( f ，j ) 为位移矢量， t 为估计阈值。m 和m s e 准则都是取最小值点为最优匹配点，n c c f 和m p c 准则对应于其最大值点。通常用绝对误差和( s a d ) 代替m a d ，绝对方差和( s s e ) 代替m s e ，即： ( 5 ) s a d 的表达式为： m s a d ( i ，j ) = z z l f 。( m ，刀) 一五一。( m + f ，咒+ - ) l ( 2 - 6 ) m = ln = 1 ( 6 ) s s e 的表达式为： s s e ( ，歹) ：m n 五( m ，玎) 一五一。