（电路与系统专业论文）h264avc运动估计和补偿加速器设计.pdf

摘要 摘要 随着宽带网络的普及和多媒体技术的不断发展，人们对数字视频业务产生了 越来越浓厚的兴趣。视频会议系统、视频监视系统、远程教育、视频点播系统 ( v o d ) ，高清晰数字电视d t v ) 以及网络聊天软件等多媒体实时业务逐渐得到广 泛的应用。尽管现在的网络状况不断地改善，但是相对于快速增长的视频业务而 言，网络带宽资源仍然是远远不够的。2 0 0 3 年3 月由两个专家组组成的联合视 频专家组( t ) 公布了这一压缩视频标准的最终草案，此标准被称为i t u t 的 h 2 6 4 协议或i s 伽e c 的m p e g 4 的高级视频编码部分，成为能够提供更高压缩 率和友好网络接口的新一代压缩视频标准。 h 2 6 4 a v c 标准通过引入多参考帧预测、可变编码块模式、1 4 像素精度运 动矢量、整形变换量化、基于内容的熵编码、新型帧内预测、去块效应滤波器等 方法来提高精度，所以在相同图像质量下，h 2 6 4 ，a v c 比m p e g 2 和h 2 6 3 的编 码性能至少提高一倍以上。但是也正是由于这些新方法的引入，使得运动估计和 补偿需要进行大量的运算因而成为了编码器的瓶颈。正是由于这个原因，人们不 断地在研究快速运动估计和补偿的方法。 我们在深入研究现有快速运动估计算法的基础上，结合包括初始点的预测， 多参考帧、多模式的选择策略，整数像素运动估计和小数像素运动估计搜索等方 面的研究，提出了快速运动估计和补偿的算法构想。同时还详细讨论了快速搜索 ， 中的阈值选取的问题，并进行了软件仿真测试。然后我们提出了实现这种运动估 计加速器的硬件设想并进行了一定程度的仿真。 关键词：视频压缩h 2 6 4 a v c 编解码器运动估计 a b s t r a c t d i 西t a lv i d e os e r v i c eh a sg a m e dp e o p l e sa n e n t i o ng r c a t l y 、) l ，i mt 1 1 ep r e v a l e n c eo f b m a d b 趾d ，a i l dt h ed e v e l o p m e n to fm u l t i m e d i ap m c e s s i n gt e c l m o l o g y t h e r ea r e m a n yr e a l - t i m em u l t i m e d i aa p p i i c a t i o n s ，s u c ha sv i d e o c o b r e n c es y s t e m s ，v i d e o m o 丑j t o r 粤y s t e 加s ，h d _ 丁ve l c _ a 】也o u 曲力e 沏d r k 肋v j m 枷e n lh a sb e e n 芦d g r c s s i l 】ga 1 0 t ，t 1 1 eb a l l d 、i d t hr c s o u r c ei ss t i l l1 i m i t e da sf h 嬲m ef b t 伊o w mo fm u l t i m e d i a a p p l i c a t i o n si sc o n c e m e d i nm a r c h2 0 0 3 ，n l ej o i n tv i d c ot e 咖( j v t ) c o m p o s e db y t w oe x p e r tt e a m sp u b l i s h e dt 1 1 ef i m a ld r a no ft l l i sc o m p r e s s c da u t o “d e os t a i l d a r d ， 、 d l i c hi sc a l l e dh 2 6 4a g 崩湖e n to fi t u lo rt 1 1 ea d v a l l c e dp a r to fa u t ov i d e oc o d 抽g o f m p e g - 4o f i s o i e c h 2 6 4 ，a v cb e c o m e st 量1 en e ws t a l l d a r do f v i d e o - c o m p r e s s i o n 血j c hc a n p r o “d eh i 曲e rc o f t l p 工e s s i b j l 毋a 1 1 dm o r e 倒e n d l yn e t 砸t e i f a c e f o rt 1 1 ee n h a n c e m e n to ft l l ec o m n ge 虢i e n c i e s ，t h cn e ws t a | 1 d a r da d o p t sn e w t o o i ss u c ha sm u l t i p i er e f e r e n c ep i c t i l r e s ，v a r i a b l eb i o c k - s i z ci nm 州o np r c d i c t i o n ， q u a r t e r - p i x e la c c u r a c yf o rm o t i o nv e c t o ls h o r 七w o r d - l e n g i l li n t e g e r 廿a n s f o t i n ， c o n t c ) ( t _ a d a p t i v ee n t r o p yc o d i n ga i l d1 0 叩f i l t e rd e b l o c k i n g m o t i o ne 幽a t i o n c o m p c n s a t i o ni sc r i t i c a lb u tc o m p u 协t i o n a l l ye x p e n s i v ef o rh 2 洲a v ci f 允l ls e a r c h i su s e d ，s oi ti sp f o p o s e df a s tm o t i 册e s t i m a t i o na l g 础t h m w ep r o p o s ea ni m 】) r o v e da 1 1 ds i 如p l i f i e df h s tm 曲o ne g t i m a t i o ns c h e m et of m h e r s p e e du pt h ee n c o d i n gp r o c e s s ，b yg t i l d y i n gm ee x i s t i n gr 印i dm o t i o ne s t i m a t i o n d i g o r i t h n l s w ea l s oa i l a l y z em es c h e m eh o w t oc h o i c et l l er e f e r c n c ef 锄e sa n dm o d e a n dt l l et h r e s h o l do fe a r l yt e 姗i n a t i o n ，e t c i no r d e rt om a k eg o o du s eo f0 1 1 rf h s t m o t i o ne s t i m a t i o ns c h e m e np u t sf o r w a r d 也eh 盯d 、a r cs m l c t l l r e 协也ec h a p t e r4 t h er e s u l ts h o w st h a c 也ep r o p o s e da c c e l e r a t o rc o u l dr e d u c em u c hm o n o ne s t i m a t i o n t i i 珀e k e y w o r d ：d e oc o m p r e s s i o nh 2 6 4 a v cc o d e cm o t i o ne s t i m a t i o n i i 浙江大学硕士学位论文 第一章绪论 随着互联网的飞速发展，消费类电子、通信、影视及广播、计算机技术日益 紧密地结合起来，使得基于互联网的多媒体产业成为本世纪初发展最快、规模最 大的产业之一。 多媒体是建立在计算机图形学、人机接口技术、传感技术和人工智能等学科 基础上的综合性极强的高新信息技术，由其带来的虚拟现实技术能创造身临其境 的神奇效果，从而广泛应用于影视、广告、游戏、教育、会展等领域。2 0 0 2 年 全球多媒体产业产值达3 0 0 亿美元，而以后的几年，多媒体产业的产值更是以惊 人的速度飞速增长。前不久，北京经济广播多媒体财经频道正式运行，实现了广 播节目既可以听又可以看的多项全新的广播服务功能。北京经济广播的多媒体财 经频道可以全天2 4 小时不间断地提供全球的外汇市场的行情、报价、市场信息 以及与外汇市场相关的国内国际重要财经新闻等信息；同时还可以使用节目中提 供的“汇眼”市场分析软件，自己来对市场进行分析，判断外汇市场的走势。从 这个实际例子中我们就可以看出多媒体业务的大部分应用都是和视频技术相关 联的。 1 1 为什么要进行视频压缩 目前，视频技术的应用范围很广，如网上可视会议、网上可视电子商务、网 上政务、网上购物、网上学校、远程医疗、网上研讨会、网上展示厅、个人网上 聊天、可视咨询等业务，但是，以上所有的应用都必须进行压缩。根据计算，一 张6 0 0 m 字节的光盘，仅能存放2 0 秒左右的6 4 0 4 8 0 象素的图像画面信息。如 果不进行编码压缩处理，单纯的靠扩大存储器容量、增加通信干线的传输速率的 办法，在多媒体信息的保存和传输的工作中所遇到的困难和成本之高是难以想象 的。从另一个角度来看，自然界有着数十亿种颜色，但是我们只能辨别大约1 0 2 4 种颜色。由于我们觉察不到一种颜色与其邻近颜色的细微差别，所以也就没必要 将每一种颜色都保留下来。还有( 一个冗余图像的问题) 如果在一个6 0 秒的视 频作品中每帧图像中都有位于同一位置的同一把椅子，有必要在每帧图像中都保 浙江大学硕士学位论文 存这把椅子的数据吗? 所以视频压缩至少有下面两个主要的好处：首先，它使在不能支持原始非压 缩视频传输和存储的环境下，能够使用数字视频。例如当前的i n t e r n e t ，即 使是在很低的视频帧率和很小的视频空间分辨率的情况下，它的吞吐速率也难以 实时处理没有压缩的视频；又如一张d v d 仅能存储几秒钟的相当于电视质量分 辨率和帧率的原始视频，所以在没有视频音频压缩的情况下，d v d 视频存储也 是不实用的。其次，视频压缩使得人们能够更有效地使用传输和存储资源，在一 个高效率的信道中，传输高分辨率的压缩视频或者多个压缩视频显然要比传输单 个低分辨率的未压缩的视频更具有吸引力。 1 2 研究运动估计和补偿加速器的意义 在过去的二十多年里，视频压缩一直是一个活跃的研究和发展领域，期间许 多不同的压缩解压缩方法被提了出来。从上个世纪8 0 年代以来，1 s o 膻c 和 i t u t 分别制定了m p e g - x 、h 2 6 x 两大系列视频编码国际标准，这些视频编码 标准追求的共同目标是在尽可能低的码率下获得尽可能好的图象质量。随着视频 压缩技术的不断发展，i n j t 视频编码专家组和i s o i e c 运动图像专家组共同制 定了新的视频编码标准- h 2 6 4 ，a v c 【1 1 】，其目的是提高压缩性能，提供“友 好的网络”( n e t w o r k 衔e n d l v ) 的视频表达方式。 h 2 6 4 标准分成三个档次( p r o f i l e ) ：b a s e l i l l e 、m a i np m f i l e 及e x t e n d e dp r o 丘l e ， 代表不同应用的算法集合和技术限定。图1 1 展示了三个档次之间的关系。 1 b a s e l i ep m f n e 的技术特征 受b 船e l i n ep r o f i l e 约束的解码器只对is l i c e 及ps l i c e 进行操作。对于所有 的is l i c e 编码序列，h 2 6 4 支持4 4 与1 6 1 6 的亮度编码模式和8 8 的色度 编码模式。为了保证s l i c e 的编码独立性，帧内预测是不允许跨越s l i c e 边界的。 对于ps l i c e 编码序列，h 2 6 4 支持帧内预测模式，帧间预测模式。 对于图像数据的组织及传输，在h 2 6 4 标准中的图像宏块能够以灵活的宏 块组织顺序( f m o ) 划分为多个s l i c eg r o u p ；s l i c e 之间相互独立，可以任意的顺 序传输到解码端( a s 0 ) 。在比特流中s l i c e 可以使用重复的方式( r s ) 传输，在s l i c e 2 浙江大学硕士学位论文 数据出错的情况下可用来进行恢复，增强了图像传输的鲁棒性。同时s 1 i c e 间的 相互独立性抑制了错误的空间传播，提高了比特流的容错性。 图1 1 三个档次之间的关系 b a s e l i n e 主要包含低复杂度、低延时的技术特征，主要针对交互式的应用， 考虑到恶劣环境下的容错性，内容基本都被其它更高级别的p r o f i l e 所包含。它 主要应用在可视电话、视频会议和无线通信等领域。 2 m a i np r o m e 的技术特征 m a i np r o f i l e 包含b a s e l i n ep r o f i l e 的所有算法并具有额外的技术特征，但它 并不支持f m 0 、a s o 及r s 等技术，只支持对i 、p 、bs l i c e 的处理操作。 在此框架内提出了适配块划分尺寸的变换( a b d 这一概念。此概念是针对帧 间编码的，其主要思想是将对预测残差进行变换编码的块尺寸与用来进行运动补 偿的块尺寸联系起来。这样就尽可能地利用最大的信号长度进行变换编码。但是， 由于复杂度的原因，进行变换的最大块尺寸被限制在8 8 以下。对熵编码部分， 为更高效地进行编码，这里使用了基于上下文的算术编码( c a b a c ) ，使熵编码 浙江大学硕士学位论文 的性能进一步提高。另外，m a i p r o f i l e 不支持多个s l i c eg r o u p 的划分。 m a i l lp m f i l e 是针对更高编码效率的应用，如视频广播，视频存储等领域。 3 e x t e n d e dp r o f i l e 的技术特征 该框架中包含所有容错技术、对比特流的灵活访问及切换技术。由于无限信 道带宽有限，错误发生的机率要比传统有限传输数据高的多。而该框架将为基本 框架设计的错误恢复功能提高到一个新的水平，提供更加完善、更有针对性的错 误隐藏方法。e x t e n d e dp r o f i l e 主要针对流媒体的应用。 相关研究表明 1 2 】，h 2 6 4 编码器在保证同等画质的前提下，平均码率比 h 2 6 3c h c 节省2 7 6 9 ，比m p e g 4s p 节省2 9 3 7 ，比h 2 6 3b a s e 节省 4 0 5 9 。由此可见，h 2 6 4 的压缩性能是相当出色的。正是由于其出色的压缩性 能，许多编码器都试图支持h 2 6 4 标准，但是由于其较高的复杂度，使得它的应 用受到了限制。 有研究表明【1 3 】，如果采用一个参考帧，运动估计的计算时间大约占整个编 码时间的6 0 ；而如果采用5 个参考帧( h 2 6 4 标准最多可以支持5 个参考帧) ， 运动估计的计算时间则占到了整个编码时间的8 0 。因此提高了运动估计的速 度，也就在很大程度上提高整个编码的速度。 1 3 主要研究内容及论文结构 本文以h 2 6 4 ，a v c 标准为基础，主要针对编码过程中关键模块运动估 计和补偿部分进行了研究和分析，分别从软件层面和硬件层面提出实现的思路。 软件部分主要从搜索算法、多模式多参考帧的策略选择，阈值的设计等方面切入 进行了论述；而硬件部分主要从它的结构实现及外围接口等方面进行分析。 全文共分五个章节： 第一章绪论，简要说明了进行视频编码的原因以及研究运动估计和补偿的研 究的必然性，在其中穿插介绍了h 2 6 4 ，a v c 标准的应用，最后提出了本文的研 究内容； 第二章h 2 6 4 佾v c 标准中的运动估计和补偿，简要介绍了运动估计和补偿 的原理以及在h 2 6 4 ，a v c 标准中关于运动估计和补偿部分的论述。 4 浙江大学硕士学位论文 第三章加速器的快速搜索算法的制定。分别从整数像素搜索，小数像素搜索， 多帧多模式选择的策略以及在快速算法中选择阈值的方法等方面，根据 h 2 6 4 ，a v c 标准中运动估计和补偿计算量大的特点，提出解决的思路，同时结合 软件来 贝| i 试快速算法的效果。 第四章加速器的硬件结构，根据第三章提出的种种策略，结合现有的一些硬 件研究理论，描述硬件的实现思路，并且对一些模块进行了仿真。 第五章全文总结和展望未来，总结全文，展望未来。 浙江大学硕士学位论文 第二章h 2 6 4 ，j a v c 标准中的运动估计和补偿 2 1 运动估计和补偿的原理 2 1 图2 1 运动估计和补偿原理图 由于视频图像在时间域上存在连续性，运动估计其实就是从已被编码的一帧 或多帧的参考帧中，寻找可以被利用来进行当前帧编码的数据。这些被利用参考 帧可以是过去的( 在现实中参考帧发生的时间比当前帧早) ，也可以是将来的( 在 现实中参考帧发生的时间比当前帧晚) 。所以运动估计就要求在为当前帧寻找有 用数据时，要尽可能的精确( 这样做会有更好的压缩效果) ，同时又要兼顾到计 算复杂度不能太高。图2 1 是一个典型的运动估计和补偿的原理图。图中的运动 估计模块就是根据一定的匹配原则，从一个或多个参考帧中，寻找与当前帧尽可 能匹配的帧。运动补偿则是通过当前帧与参考帧进行作差来形成一个残差，这个 残差经过编码和变换，携带一些解码器所需要的信息输出到解码器。同时经过编 码后的残差经过解码后，与参考帧相加后又重构回来( 注意由于存在精度的误差， 这个重构帧和先前编码的帧已有所不同了) 。重构的帧会被存储着用来作为下面 预测所需要的参考帧。 残差( 或者叫作d f d ，d i s p l a c e d 胁l ed i 疵r e n c e ) 在经过编码和变换后会带 有一些额外的信息，如在解码器解码时需要的运动矢量等等。最佳的压缩效果就 是这些经过编码的d f d 和额外的信息是最小的时候。d f d 编码后的大小是和经 6 浙江大学硕士学位论文 过运动补偿后残留在d f d 上的能量相关的。图2 2 一图2 4 向我们展示了先前帧， 当前帧和未经过运动补偿的d f d 之间的关系。 图2 2 先前帧 图2 4 未经运动补偿的d f d 图2 3 当前帧 从图中我们可以很明显的比较出在女孩和自行车的边界上或者说在运动物 体的边界上会有比较大的能量残余，这就需要我们通过运动估计和补偿来降低的 能量。 运动估计有很多种，包括全局运动估计，基于匹配像素点的运动估计，基于 匹配块的运动估计，基于匹配区域的运动估计，基于匹配网格的运动估计等等。 目前普遍采用的方法是基于匹配块的运动估计方法。 7 浙江大学硕士学位论文 2 2 小数像素的运动估计 在实际的视频中，匹配块位置的偏移量不一定都是整数。这样我们就需要通 过内插的方法可以获得这样的匹配块。这样整个搜索算法可以概括如下： 1 通过对参考帧中的搜索区域采用内插的方法，获得一个精度更高的搜索范 围。 2 通过整数像素搜索和小数像素搜索获得最佳的匹配块。 3 通过当前块和匹配块的作差得到残差。 由于小数像素搜索比整数像素搜索需要更大的计算量，所以为了控制这种复 杂度的增长，我们通常是在找到最匹配的整像素的匹配块后，在这个整像素位置 的周围进行小像素的搜索。尽管这么做，复杂度增加了一些，但是小像素的运动 估计和补偿在性能上能够比整数像素运动估计和补偿提高很多。这是因为在相邻 的视频帧之间，运动的物体不一定是以整数像素距离移动的，这样采用小数像素 搜索找到匹配块的可能性就比采用整数像素搜索来找大的多了。 2 3h 2 6 4 a v c 标准中的运动估计和补偿 2 2 1 帧闻预测 h 2 6 4 标准中的帧间预测与早期标准中的主要不同之处主要在于h 2 6 4 支持 不同的块尺寸( 从1 6 1 6 到4 4 ) 及支持非整数像素精度的运动矢量( 亮度是 1 4 像素精度) 。 树型结构的运动补偿 每个宏块( 1 6 1 6 像素) 的亮度分量可以按1 6 1 6 ， 1 6 8 ，8 x1 6 或者 1 6 m 目田 缸 e 瓠 61白国叠毋 图2 5 宏块的分割模式 8 8 四种方式进行划分( 如图2 5 所示) ，即按照一个1 6 1 6 的块，或者两个 1 6 8 的块，或者两个8 1 6 的块，或者4 个8 8 的块的划分来进行运动补偿。 浙江大学硕士学位论文 如果选择8 8 模式，宏块中的4 个8 8 块可以进一步划分为8 8 ，8 4 ，4 8 和4 4 块( 如图2 6 所示) 。这些分块和子块大大增加了每个宏块内部的组合 数。把宏块分成不同尺寸的运动补偿子块的方法就是为了实现树型结构的运动补 偿。 厂扎 广 广丁 刮制 敏en“ 图2 6 子块的划分 在h 2 6 4 编码中，每个分块都会产生一个单独的运动矢量。每个运动矢量均 需要编码和传输，同时分块模式信息需要进行编码并放在压缩比特流中。选择大 的分块尺寸( 1 6 1 6 ，1 6 8 ，8 1 6 ) 意味着运动矢量和分块尺寸需要很少的比 特，但是，对于含丰富细节的图像区域，运动补偿残差数据可能包含更多的信息。 选择一个小的分块尺寸( 8 4 ，4 4 等等) 可以减小运动补偿之后残差数据的 大小，但是需要传输更多的比特数，用于表示运动矢量和模式选择信息。所以分 块尺寸的选择对压缩性能有很大程度的影响。编码器需要在表示运动矢量和分块 模式信息的信息比特与运动估计的残差数据之间做很好的折中。一般情况下，大 的分块尺寸适合于图像中变化平缓的区域，而小的分块尺寸对细节区域比较好的 描述。 每个宏块中的色度分量( c b 和c r ) 的水平和垂直分辨率是亮度分量的一半。 每个色度块按照与亮度分量同样的分块方式进行划分，只是色度分块的尺寸是对 应的亮度分块的一半( 例如，亮度的8 1 6 分块对应于色度的4 8 分块，亮度 的8 4 分块对应于色度的4 2 分块等等) 。每个运动矢量的水平和垂直分量在 应用到色度块时要减少一半。 运动矢量 帧间编码宏块中的每个分块或者子块都从参考图像的一个同样大小的区域 9 浙江大学硕士学位论文 进行预测。这两个区域的运动矢量对于亮度分量达到l 4 像素精度，对于色度分 量达到1 8 像素精度。由于非整数点像素位置的亮度和色度像素在参考帧中并不 存在，所以必须利用对邻近编码像素进行内插来得到。如图2 7 中，当前帧的一 个4 4 块是从参考帧中与当前块位置相邻的区域进行预测的；如果运动矢量的 水平和垂直分量都是整数，则在参考帧中存在相应的像素( 灰色) ；如果一个或 者两个运动矢量分量是非整数，则预测值( 灰色) 是从参考帧中相邻像素( 白点) 进行插补得到的。 ooo0oo o o o o o 0 o o oooooo o0ooo0 oooooo oooood oo pooo odoooo oooooo 图2 7 小像素预测 ooo0oo 2 帧内预测 在帧内预测模式下，依据先前编码和重构之后的块形成一个预测块，当前块 减去这个预测块，将差值进行编码。对于亮度像素，分成4 4 块或者1 6 1 6 块进行预测。对于每个4 4 的亮度块，共有九种可选模式。对于1 6 1 6 的亮度 块，共有四种可选模式；对于色度块，共有四种可选模式。选择与当前块的差值 最小的预测模式作为当前块的帧内预测模式。 4 x 4 亮度块的预测模式 图2 8 显示了4 4 亮度块的九种预测模式。图中的箭头代表每种模式的预 测方向：垂直( 模式0 ) ，水平( 模式1 ) ，直流( 模式2 ) ，左下对角( 模式3 ) ， 右下对角( 模式4 ) ，右垂直( 模式5 ) ，下水平( 模式6 ) ，左垂直( 模式7 ) ，上 水平( 模式8 ) 。 o 0 0 0 0 0 0 oo o o o o o o o o oooooonoodoooooq。 o o o o 矿 0 0 0 0 0 浙江大学硕士学位论文 图2 84 4 亮度预测模式 1 6 1 6 亮度预测模式 与之前讲述的4 4 亮度模式一样，一个宏块的全部1 6 1 6 亮度分量可以在 一次操作中进行预测。帧内编码宏块的每个1 6 1 6 亮度分量是从上边和或左边 先前编码的亮度像素进行预测得到的。它的四种预测模式与8 8 的色度预测模 式相类似。这些模式是垂直( 模式o ) 、水平( 模式1 ) 、直流( 模式2 ) 和平面 ( 模式3 ) 。 2 4 运动估计和补偿的复杂性分析 h 2 6 4 标准和以往的视频标准相比，运动估计和补偿主要有以下的一些特点 2 3 】： 1 高精度运动估计。在h 2 6 3 标准中采用了半像素运动估计，在h 2 6 4 标 准中则进一步提升到1 4 像素甚至1 8 像素的运动估计，即真正的运动矢量的位 移可能是以1 4 甚至l 8 像素为基本单位的。在h 2 6 4 标准中采用了6 阶f i r 滤 波器内插获得l 2 像素位置上的值。当获得1 2 像素位置上的值后，1 4 像素值可 通过线性内插获得。理论上，如果将运动补偿的精度增加1 倍( 例如从整像素精 度提高到1 2 像素精度) ，可以有0 5 b i “s 锄p l e 的编码增益，但是经过实际验证 发现在运动矢量精度超过1 8 像素后，系统基本上就没有明显增益了。因此在 h 2 6 4 标准中，最后只采用了1 4 像素精度的运动矢量，而没有采用l 8 像素精 度的运动矢量。 2 树型结构的运动补偿。h 2 6 4 标准中支持从1 6 x 1 6 到4 x 4 范围尺寸的运动 补偿块，在这个范围中亮度样本有多种选择。每个图像宏块亮度分量可以按4 种模式划分：1 6 x 1 6 ，1 6 x 8 ，8 x 1 6 和8 x 8 。其中每一个子块都是宏块的一部分。 如果选择了8 x 8 的模式，每一个8 x 8 模块又可以按4 种模式分开；8 x 8 ，8 x 4 ，4 x 8 ， 浙江大学硕士学位论文 4 x 4 。这种块和予块的不同模式可以产生大量的组合，即实现了树型结构的运动 补偿。 3 多参考帧运动估计。在h 2 6 4 标准中，可以采用多个参考帧进行运动估 计。即在编码器的缓存中存有多个参考帧，编码器可以从其中选择一帧或多帧作 为参考帧，这样可以获得比只使用一个参考帧更好的编码效果。 正是由于h 2 6 4 甜，c 标准中的运动估计和补偿引入了以上一些新的特征， 使得运动估计模块的设计增加了较大的复杂度，也使得整体算法实现的复杂度成 倍增长。下面以j m 标准模型中的全搜索为例，对其实现进行一个评估。 首先对于帧内模式选择，j m 模型以色度模式为外循环，然后依次扫描亮度 的所有模式，其搜索的模式总数为( 9x1 6 + 4 ) x4 ，共5 9 2 种。这意味着为了得 到一个宏块的最佳模式，需要计算5 9 2 个不同模式的代价函数。这种方法编码质 量最高，需要的运算量也最大。 帧间模式包括由1 6 x 1 6 到4 x 4 等七种模式。这七种不同的模式下分别有1 ， 2 ，2 ，4 ，8 ，8 和1 6 个子块需要进行小数像素和多参考帧的运动估计和补偿， 其复杂程度成级数增长。 在h 2 6 4 标准中，搜索范围通常可以从8 扩大到6 4 ，搜索精度也可以进一 步提高，且由于运动估计引入了r d o 算法的判决，其实现复杂程度会更高。如 果搜索范围为1 6 ，则需要搜索的整像素点为( 1 6 x 2 + 1 ) 2 = 1 0 8 9 个像素点。而且 对于通过滤波器内插得到的小数像素点，如果采用分级的搜索方法，对于1 4 和 1 8 精度需要进一步搜索1 6 个或2 4 个小数像素点。所以运动估计如果采用全搜 索算法，其复杂性是显而易见的，所以快速运动估计算法也就成为算法优化的一 个关键问题。常用的快速运动估计方法是假设运动补偿对应的失真满足单峰分 布，以一定的搜索模式和搜索步骤，对搜索点与步长进行修正，逐渐逼近最优点。 与全搜索算法相比，这些快速运动估计方法通过减少搜索点的数目，利用不同的 搜索模式与策略来寻找最优的运动矢量。 h 2 6 4 ，a v c 支持最多5 个参考帧，对于每种模式下的子块都在每个参考帧内 进行运动估计，因此每增加一个参考帧，其复杂度会线性增长。在j m 模型中并 没有对参考帧选择的策略进行优化，它认为参考帧之间是相互独立的，并没有考 虑参考帧之间的相关性，也没有考虑其在具体应用环境中参考帧的不同作用。 1 2 浙江大学硕士学位论文 第三章加速器的搜索算法 3 1 加速器的搜索算法 3 1 1 加速器搜索算法中匹配块的评价方式 1 匹配块 基于匹配块的运动估计算法( b m m e - b l o c k m a t c h i n gm o 蛀o ne s t i m a t i o n ) 3 1 】和基于像素递归的运动估计算法( p r a p i x e l - r e c l l r s i v cm g o r i t h m ) 【3 2 】 这两种算法都是较为有效的运动估计的算法，它们都能够有效的消除视频数据的 时域冗余，实现较高的压缩效率。但是由于基于匹配块的运动估计算法具有计算 复杂度低，使用矩形视频图像和分块图像变换( 如离散余弦变换) 等优点，因而 成为一些主流的视频编码标准( h 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 4 ) 所普遍采用的运动估计和补偿的方法。 它的基本思想是将当前帧分成许多的矩形块，对每个块进行运动补偿。例如， 对于当前帧中大小为mxn 的块，它的运动估计和补偿的操作如下： 1 在参考帧中搜索mxn 尺寸的匹配块。将当前mx n 的块和参考帧搜索区 域( 一般是以当前块为中心，以一定宽度的矩形区域) 内的部分或所有mxn 块进行比较，找出其中最佳的匹配块( 这里涉及到了匹配标准的选择，我们将在 稍候进行讨论) 。这个过程就是我们通常所说的运动估计。 2 将搜索到的最佳匹配块作为当前块的预测块，用当前块减去预测块后得到 一个相应的mxn 残差块。这个过程就是运动补偿。 正是由于基于匹配块的运动估计和补偿的算法有着许多优点，所以在h 2 6 4 标准中仍然采用这种基于匹配块的运动估计和补偿的算法。在h 2 6 4 标准中一个 宏块可以有八种划分，它们是1 6 x 1 6 块，1 6 x 8 块，8 x 1 6 块，8 x 8 块，以及8 x 8 以下块。 8 x 8 以下块又可以分成8 x 8 块，8 x 4 块，4 x 8 块和4 x 4 块( 关于宏块和其他这些 块的划分的详细介绍可参看第二章的相关介绍) 。 2 加速器中选取匹配块的标准 浙江大学硕士学位论文 我们都知道，运动估计的目的就是使在运动补偿中的残差经过变换后，能量 最小化。而变换后残差的能量又取决于变换前残差块的能量，所以运动估计其实 就是寻找使得运动补偿时能量最小的那些“匹配”块。 通常我们需要对一系列不同的偏移量计算能量，而采用什么样的能量度量是 会影响到运动估计的精度和速度的。能量的度量有很多，如m s e ，m a e ，s a e ( s a d ) ， 拉格朗日开销( l a g 瑚1 9 ec o s t ) 3 3 】【3 4 】等等。式3 1 一式3 3 给出了几 个常用的度量能量的公式，它们分别是m s e ( m e a l ls q u a r e de d r ) ，m a e ( m e a n a b s o l u t ee r m r ) ，和s a e ( s u mo fa b s o l u t ee f r o r s ) s a d ( s u mo fa b s o l u t e d i 腩r e n c e s ) 。式中运动补偿块的大小均为nxn ，c i 为当前nxn 块中的像素 值，r i 为参考帧中对应块的像素值。 1 均平方误差： m s e = 紊萎豁吨f 越t 2 均绝对误差： m a e = 吉j c 日一r “ 式3 2 l 1 l = 0i 1 0 3 绝对误差和： s a d ( s 觚) = l c 日一r “ 式3 3 通过观察式3 1 一式3 3 ，我们可以很明显的发现式3 2 要比式3 1 简单一些， 因为它采用绝对值的运算替代了平方的运算，而度量的效果却没有减弱；同样的 道理式3 - 3 比式3 2 又简单了许多，因为它去除了除法运算，以此减小了运算的 复杂度，还提高了运算的精度。正是由于s a d 有着相对较低的计算复杂度，因 而被广泛采用来度量残差能量。 但是在实际应用中，由于位数的限制，使得s a d 的精度还不够，所以在我 们的h 2 6 4 模型中，先对残差进行了变换，然后对变换后的值进行绝对值求和， 即所谓的s a t d 。这样做有如下几个好处： 1 由于残差经过变换后常常会出现大量的零系数，变换后再进行求和就能够 克服因位数不够而导致的精度损失，这样就很好的克服了s a d 的不足之处。 浙江大学硕士学位论文 2 变换这个操作在编码过程本来就必须要完成的，提前进行变换后，后续编 码模块的压力会减轻，同时由于加速器将采用流水线的设计，所以对于加速器本 身来说开销并不会增加很多。 3 ，变换进行的仅仅是一些加法的运算，这就保证了运算的开销不会有太大的 提高。 顺便提下，并不是所有的时候都需要计算完s a d 的，比如说当前累计的 部分s a d 已经超过了以前计算的最小值时，我们就可以中途中止计算了。在实 际应用中，编码器会对累计的s a d 和以前的最小值进行比较，一旦超过了以前 的最小值，计算就会中止了。 3 1 2 加速器整数像素的搜索算法 l 全搜索算法 从理论上来说，为了从参考帧中寻找出与当前帧最匹配的块，必须比较在参 考帧中与当前块大小相同的所有的参考块，但如此大的运算量显然是不切实际 的。所以在实际应用中，我们常常会限定一个搜索范围( 称为搜索窗，通常是以 当前块为中心，一定的搜索步长w 为半径的一个矩形搜索范围) ，采用穷举的方 法，在搜索窗的范围内的对于每一个像素点重复使用公式3 3 进行搜索，这样一 定能找到在搜索窗中的最小的s a d ，这种搜索方法就是我们所熟悉的全搜索 【3 1 】。这种方法的好处是有很好的编码效率。但是它的计算量很大，对于固定帧 固定模式固定块条件下，需要计算( 2 w + 1 ) 2 次。 2 快速搜索算法 由于即使在限定了搜索窗之后，全搜索算法还是具有很高的计算复杂度，这 使得全搜索算法在很多场合下，应用都受到了限制。如在一些有实时要求的系统 中，由于全搜索的计算复杂度过高而导致了编码时间过长，满足不了实时系统实 时的要求。为了解决这一问题，一类被称为快速搜索的搜索算法诞生了。 根据它们在加速思想上的不同可以分成两类，一类是选取搜索窗中的一些特 殊位置的点，通过计算这些特殊点的能量度量( 如s a d ) 来代替计算搜索窗中 所有点的能量度量，进行获得运动估计的结果，以此来降低计算的复杂度。其主 浙江大学硕士学位论文 要代表有对数搜索法( l o g s ) 【3 5 ，三步搜索法( t s s ) 【3 6 ，新三步搜索法( n 3 s s ) 3 7 】，钻石搜索法( d s ) 【3 8 3 9 】，六边形搜索法( h e x b s ) 3 1 0 等等。这类搜索算法 的特点是搜索速度很快，但是编码的效率会下降很大。 另一类思想是降低能量度量( 如s a d ) 的计算复杂度，典型的代表有降采 样【3 1 l 一3 1 3 】，局部失真搜索法( p d s ) 3 1 4 】，规格化的p d s 3 1 5 3 1 6 】，逐次消元 法( s e a ) 【3 1 7 3 1 8 】。这类搜索算法虽然编码的效率还是不错，但是对于搜索 速度的提升并不明显。 正是由于以上两种方法各自都有很大的局限性，所以后来出现了一些结合以 上两类方法中的多种技术的新型算法，如p m 1 a s t 【3 1 9 】和u m h e x a g o n s 【3 2 0 】 等。它们就是结合了预测，钻石搜索，六边形搜索，部分失真和自适应提前中止 等多种方法。本文中的加速器的搜索算法也是受到了这类算法的启发后设计的。 3 加速器整数像素的搜索算法 在自然界中存在着成千上万种运动的视频图像，但是我们可以很容易把它们 归结到以下三类视频中来： 第一类是基本不怎么运动的视频，如视频会议，视频广播等，这是一类在特 定场合被广泛应用的视频； 第二类是运动比较平稳，场景慢慢在变换，但是又变换不会很突然的视频， 如平时的电视节目，自拍的生活视频等，这是一类和我们生活比较贴近的视频， 它和第一类构成了我们平时生活中接触到的大部分视频； 第三类是运动剧烈，场景不断变换的视频，虽然在现实中不太常见，但是它 也有着它们自己的应用空间。 当然这三类视频的划分也不是绝对的，我们的分类是以视频在绝大部分时候 所表现出来的情况来进行划分的。如在第一类和第二类的视频中也会出现一些场 景突然变换的片断，这些片断我们会归入第三类，但是总的来说这些视频还是属 于第一类或者第二类。 按照这样的三类标准来划分视频，基本上包括了我们生活中方方面面需要处 理的图像了，但是这样的划分太抽象了，没有可操作性。我们在仔细分析这三类 图像后不难发现，这样的分类和编码后的视频码流有着相对应的关系，它们( 从 1 6 浙江大学硕士学位论文 第一类到第三类依次) 可以简单的认为是和三类码流( 从低到高) 一一对应的。 有了这样的认识就有了我们搜索算法的雏形了。我们很容易就想到可以把整 个搜索分成三个搜索小过程，每个搜索小过程分别对应于从第一类到第三类不同 的视频，我们可以设定三个阈值来选择控制是立即结束搜索还是进入到下一个搜 索过程中去。图3 1 概括整数像素的快速搜索算法。 吐b i t s 式3 9 其中q u a t l t x 】【y 】为量化后进行熵编码前的数据，w 【x 】 y 】为变换后进行量化前 的数据，q i l a i l t _ c o e f 【q p 婶m 】【x 】 y 】为量化系数表中对应的量化参数，当q p 为编 码器输入时的量化参数时，式3 9 中的q p c o n s t _ ( 1 q _ b i 呦，6 ，q - b i t s = q p _ p e r + 1 5 ，q pp e r = q p ，6 ，q p - r e m 2 q p ) 6 。 如果量化后输出的数据为零，那么就可以等价为 q u a n t 【x 】【y 1 式3 1 0 但是由于在实际的编码中我们是不能等到变换量化都完成之后才来决定全 零块的判断闽值的，因为那时候运动估计都已经结束了，这时才来判断全零块的 阈值已经没有意义了。在前面的章节我们就已经讨论过了，在快速搜索中我们主 要是通过s a t d 来判断搜索到的块是否匹配，所以我们很容易就想到如果我们可 以利用s a t d 来直接进行全零块的判断，就可以有效的减少运动补偿时的计算量 了。 在4x4 块经过预测后得到的残差在经过变换量化后会按照z i g z a g 扫描顺 序放到一维的数组中去，然后会有一个块结束标志e o b ( e n d0 f b l o c k ) 来标识 数组中的最后一个非零数据。也就是说在这以后的所有数据都是零，这是为了更 有效的进行熵编码而设计的。我们可以想象一下，随着量化系数的逐渐增大，残 差信号的能量必然减小，变换量化后的数据也就更可能为零，这样e o b 的位置 就会不断往前移动。如果e o b 为零，那么就说明出现了全零的系数块。相对应 的，如果我们找出了s a l 巾类似的变化趋势，我们也就可以利用s a t 【) 的值作为 浙江大学硕士学位论文 闽值来进行全零块的判断和预测了。 3 3 1 快速算法中阈值大小的确定 在实际的应用中，人们普遍认为直流系数一般会大于交流系数，这也正是为 什么在h 2 6 4 标准中对于直流系数的处理和交流系数的处理会不同，标准会特别 “照顾”一下直流系数。我们下面的理论推导在很大程度上也是建立在这一假设 的基础上的。我们认为，在一般情况下，如果直流量化系数为零，那么该块的量 化系数也为零。所以我们利用直流系数最大这一假设得到了全零块预测的一个上 界。 由于直流系数即为q u a n t 【o 】【o 】，所以根据式3 1 0 ，同时结合式3 9 我们可以 得到量化后为零的条件满足式3 1l ： q u a n t o 】【0 】= r 。；( x ，y ) ( 2 4 一一q p c o n s t ) q l l a i l t c o e f 式3 1 1 我们把不等式右边的函数记为1 1 1 ( q p ) ，同