多标准视频编码器下的运动估计评估.pdf

《多标准视频编码器下的运动估计评估.pdf》由会员分享，可在线阅读，更多相关《多标准视频编码器下的运动估计评估.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 基金项目基金项目基金项目基金项目：国家自然科学基金资助项目(60970023)；国家“973”计划基金资助项目(2011CB302501)；国家“863”计划基金资助项目(2012AA010902,2012AA010901)。作者简介作者简介作者简介作者简介：孙公瑾(1983)，男，硕士研究生，主研方向：微处理器体系结构；安 虹，教授；范东睿，副研究员。收稿日期收稿日期收稿日期收稿日期：2013-03-07 修回日期修回日期修回日期修回日期：2013-04-03 E-mail： 多标准视频编码器下的多标准视频编码器下的多标准视频编码器下的多标准视频编码器下的运动估计运动估计运动估计运动估计评

2、估评估评估评估 孙公瑾孙公瑾孙公瑾孙公瑾1，安安安安 虹虹虹虹1，范东睿范东睿范东睿范东睿2(1.中国科学技术大学计算机科学与技术学院，合肥 230027；2.中国科学院计算技术研究所计算机体系结构国家重点实验室，北京 100190)摘摘摘摘 要要要要：运动估计是视频编码过程中最为复杂和耗时的阶段。为分析和优化其性能，从多个流行的开源视频编码器中提取出单独的运动估计算法模块，根据视频分辨率和视频内容的不同建立程序输入集，从而构成一套完整的测试程序集合。利用性能分析工具对算法性能和微体系结构性能进行量化分析，给出这些算法在当今主流处理器体系结构上的性能差异。实验结果表明，复杂视频和高分辨率视频下

3、的运动估计算法耗时最长，且大部分算法的指令级并行性没有太大差异。算法最后一级高速缓存的缺失率和分支误预测率都较低，分别在 0.01%和 7%以下。关键词关键词关键词关键词：视频编码；运动估计；钻石搜索；六边形搜索；视频内容；分辨率；微结构 Evaluation of Motion Estimation for Multi-standard Video Encoder SUN Gong-jin1,AN Hong1,FAN Dong-rui2(1.School of Computer Science and Technology,University of Science and Technolo

4、gy of China,Hefei 230027,China;2.State Key Laboratory of Computer Architecture,Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China)【Abstract】The Motion Estimation(ME)in the video coding is the most complex and time-consuming one of all the processing stages.This paper

5、extracts all the ME modules from multiple popular open source video codecs in order to evaluate and optimize their performance.In addition,a comprehensive input data set is constructed for these ME algorithms considering different video contents and resolutions.A quantitative analysis of runtime eff

6、iciency and microarchitecture characteristics are made for these algorithms by means of the profiling tool based on hardware performance counter,and the analysis exposes their performance difference on current mainstream processor architecture.The evaluation results show that for the input of comple

7、x and high-resolution video,the ME will consume the most time,while there are little difference between their low Instruction Level Parallelism(ILP).But the Last Level Cache(LLC)miss rate and branch misprediction rate of these algorithms are all rather low,which are respectively under 0.01%and 7%.【K

8、ey words】video coding;Motion Estimation(ME);diamond search;hexagon search;video content;resolution ratio;microarchitecture DOI:10.3969/j.issn.1000-3428.2014.04.058 计 算 机 工 程 Computer Engineering 第 40 卷 第 4 期 Vol.40 No.4 2014 年 4 月 April 2014 开发研究与工程应用开发研究与工程应用开发研究与工程应用开发研究与工程应用 文章编号文章编号文章编号文章编号：1000

9、-3428(2014)04-0295-06 文献标识码文献标识码文献标识码文献标识码：A 中图分类号中图分类号中图分类号中图分类号：TP181 概述概述概述概述 视频编码技术一直被广泛应用于多个重要领域，如媒体播放器、视频会议、在线视频点播等。编码器的性能特征也一直是视频领域的研究热点。通常一个经典的视频编码过程包括多个关键的阶段：视频预处理，运动估计，离散余弦变换和量化(包括反变化和反量化)，熵编码，视频后处理(去块滤波等)。在编码的多个阶段中，运动估计(Motion Estimation,ME)因涉及到太多复杂的计算而成为最耗时的部分1。该阶段的主要功能是对于当前的编码单元(片、帧或宏块)

10、通过一些有效的图像搜索算法找到一个最优的运动向量和参考图像。它需要很多的计算和数值比较操作。运动估计的精度将直接影响到最终的码流文件(被压缩后的文件)质量。因 此，单独对编码器中的运动估计算法进行观察和研究将会提供更多的性能提升空间，这些算法已经被广泛用于很多流行的编码器中2-4，比如钻石搜索算法、六边形搜索算法、UMH搜索算法等。但是对它们的分析不能通过分析完整的编码器进行，因为编码器的编码效果不仅由运动估计部分决定，而且还与其他一些因素相关。如果仅通过配置跟运296 计 算 机 工 程 2014 年 4 月 15 日 动估计相关的运行参数然后再去评估编码效果，这样不会给出关于运动估计部分任

11、何精确而有深度的结论。更有效的办法是从现有的编码器中提取出跟搜索算法有关的关键模块，使它们变为可独立运行的程序，这样就可以单独地分析其行为特征和性能表现。另一方面，虽然现在有一些多媒体benchmark包，比如Berkeley Multimedia5、Mediabench6、Mediabech II7、EEMBC8、HD-VideoBench9等，但它们都只包含完整的编码器，没有所需要的独立算法模块和程序片段。而且，它们中的大部分程序都是基于一些比较老的视频编码标准，比如MPEG-2和MPEG-4，没有包含最新的标准，如VP810。因此，不能直接拿这些已有的Benchmark包进行研究。本文从

12、已有的编码器中将运动估计的算法模块(程序片段)提取出来，并构成可独立运行的程序。2 运动估计算法提取运动估计算法提取运动估计算法提取运动估计算法提取 2.1 编码器选择编码器选择编码器选择编码器选择 每个视频编码器都有自己的设计原理，要考虑自己的需求，如目标压缩率、编码算法的选择和实现、数据格式的定义、输入视频序列的特征以及编码器最适于运行的微结构平台等。不同的编码器有不同的性能表现和应用领域，比如有的适合于实时编码，有的则更擅于离线压缩；有的适合于嵌入式平台，有的则更适合于大型数据中心。因此，必须首先选择合适的候选编码器，这样提取出的算法才更具适应性和代表性。可以作为候选的视频编码器应该满足

13、以下条件：(1)被选择的应该是视频处理领域中的主流编码器，有广泛的代表性。(2)该编码器包含主流的运动估计算法。(3)如果编码器是按照某个标准(比如H.264)来实现的，那它应该实现该标准定义和描述的全部特征，或者至少是标准中某一个层次所描述的全部特征。(4)考虑到移植性，编码器应该包含体系结构无关代码。(5)编码器的性能不能太低。不仅要考虑到编码器的编码质量，而且也要考虑到其可用性以及效率。如果一个视频编码标准的参考软件仅仅只是为了验证该标准但却有很差的运行效率，那么它就没有太大的实用性，更不适合拿来作为一个评估对象。(6)需要有一组完整的视频测试序列，包含多个典型的视频场景和图像分辨率。每

14、个序列都有自己独特的运动特征，诸如剧烈运动、镜头晃动、场景切换、静止图像、波动图像等。分辨率要包括低分辨率(比如cif(352288)、4cif(704576)和高清视频(比如720P和1080P)。(7)编码器应该是开源的，这样其他的研究人员可以根据自己的需要访问、修改并分发这些源代码。根据以上条件，选择了流行的视频编解码器来提取其中的运动估计算法模块。表1列出了这些编码器以及相应的描述。表表表表1 用用用用于于于于提取运动估计模块的候选编码器提取运动估计模块的候选编码器提取运动估计模块的候选编码器提取运动估计模块的候选编码器 候选编码器 描述 xvid(版本:1.3.2)一个优秀的MPEG

15、-4开源视频编码器11 x264(版本:core 116)一个被广泛应用的H.264开源编码器，其性能超过了很多同类的其他编码器12-13 vp8(版本:1.0.0)VP8是一个由Google发布的新视频编码规范，目前实现的软件版本是1.0.010 2.2 运运运运动估计程序的提取动估计程序的提取动估计程序的提取动估计程序的提取 将原始编码器中的算法模块连同其调用的子函数及相应的头文件全部提取成单独的程序文件，然后编译成可独立执行的程序文件。表2列出了所提取的运动估计算法模块及其相应的特征描述。表表表表2 提取出的运动估计算法提取出的运动估计算法提取出的运动估计算法提取出的运动估计算法 候选编

16、码器 运动估计搜索算法 特征 xvid xivd_me_advdia 高级钻石搜索 xvid_me_square 正方形搜索 xvid_me_dia 钻石搜索 x264 x264_dia 钻石搜索，半径为1 x264_hex 六边形搜索，半径为2 x264_umh 非对称十字多层六边形(UMH)搜索 vp8 vp8_diamond 钻石搜索 3 经典运动估计算法描述经典运动估计算法描述经典运动估计算法描述经典运动估计算法描述 程序集包含7个搜索算法模块，其中一些在原理上是类似的。下面对一些重要的算法进行简单描述。3.1 搜索算法描述搜索算法描述搜索算法描述搜索算法描述 3.1.1 钻石搜索 图

17、1给出了钻石搜索算法的原理。01111222 图图图图1 钻石搜索算法原理钻石搜索算法原理钻石搜索算法原理钻石搜索算法原理 以图1为例描述搜索过程：图中的每一个圆圈代表一个像素，圆圈0表示其实搜索像素。(1)计算起始像素0周围4个像素(标号为1)的代价，然后和像素0的代价进行比较。(2)如果0的代价最小，那么搜索结束；否则选择标号1中代价最小的像素(如图中圆圈)作为新的起始搜索像素。(3)重复以上步骤直到找到最匹配的像素。3.1.2 六边形搜索 和钻石搜索相比，六边形搜索有更高的效率和精确性。其搜索原理和搜索过程分别如图2和图3所示。第40卷 第4期 297 孙公瑾，安 虹，范东睿：多标准视频

18、编码器下的运动估计评估 图图图图2 六边形搜索原理六边形搜索原理六边形搜索原理六边形搜索原理 图图图图3 六边形六边形六边形六边形搜索搜索搜索搜索算法过程算法过程算法过程算法过程 3.1.3 非对称十字多层六边形搜索 非对称十字多层六边形(Uneven-cross Multi-Hexagon-grid,UMH)搜索算法混合了钻石搜索和六边形搜索的特征，是目前搜索效率最高的快速运动估计搜索算法。图4给出了原理图，不同的数字代表不同的搜索步骤。图图图图4 非对称非对称非对称非对称十字多层六边形十字多层六边形十字多层六边形十字多层六边形搜索原理搜索原理搜索原理搜索原理 3.1.4 全搜索 全搜索是对

19、参考帧图像中的每一个像素进行搜索匹配，因此，必然可以找到最优的运动向量，精确度相对其他搜索算法也最高，但是也最为耗时。全搜索算法一般用硬件实现，本研究不涉及该算法的评估。3.2 输入集设计输入集设计输入集设计输入集设计 除了编码器自身的算法特征外，编码过程还受到输入视频序列的极大影响，比如视频的内容或者分辨率。视频内容代表着具体的图像运动特征，这些特征对编码器的执行路径和最终产生的码流文件有关键性的影响。如画面呈现剧烈运动的视频意味着要花更多时间在运动估计模块上面。另一方面，视频的分辨率也和编码的效率有直接关系，高分辨率视频通常要求运动估计算法搜索更大的像素范 围，进行更多次的计算和比较，使得

20、编码的速度急剧下降。为了选择合适的视频产生运动估计程序集所需要的输入集，进行2个量化分析来观察视频内容和分辨率对编码的影响，评估的指标有4个，分别是峰值信噪比(Peak Signal Noise Ratio,PSRN)、码率、压缩比和编码速度。实验的环境如下：处理器是Intel的Xeon E5520，Nehalem微结构，OS是Linux。PSNR被用来评估编码后的视频质量，单位是dB。该值受运动估计算法和量化算法的影响，值越高代表着编码质量越高。码率反映了压缩后的文件对带宽的需求，单位是Kb/s。运动估计越精确，编码图像和参考图像之间的残差就越小，经过后面的DCT和量化后产生的码流就更少，码

21、率也更低。压缩比被定义为压缩后的文件和原始视频文件的比。小的压缩比代表着更好的压缩效果。受运动估计算法和量化算法影响最大。编码速度被定义为原始视频文件的大小与编码时间的比，此处为了统一不同分辨率之间的比较基线，以Mb/s为单位。正如前文所说，运动估计部分是编码中最耗时的阶段，直接影响着编码的速度。如果运动估计速度提高，那么整个编码时间也就会大大降低。3.2.1 视频内容相关性分析 选择8个不同的视频进行实验，它们除了视频的运动特征不同外，都具有相同的分辨率(cif,352288)、帧数和帧率。图5给出了3个编码器之间的比较结果。可以看出，xvid和x264的PSNR比vp8的要高。在所有视频中

22、，akiyo的PSNR最好，而riverbed最差。对于反映带宽需求的码率而言，xvid和x264中的riverbed最高，football其次，akiyo最低。可是，vp8并没有显示出以上这些差别。而压缩比数据就很明显，akiyo的压缩效果是最好的，riverbed和football仍然是最差的2个。对于编码速度，从图上看出，对xvid和x264而言，akiyo仍然有最高的值，riverbed和football是最慢的2个。在这3个编码器中，xvid的编码速度最快，vp8最慢。akiyo表现良好和riverbed、football表现较差的原因在于它们的视频运动特征不同。在akiyo中，前景

23、是一个新闻播音员在播送新闻。背景几乎不动，只有播音员的面部表情发生细微变化。这类视频在编298 计 算 机 工 程 2014 年 4 月 15 日 码中不需要复杂的运动估计和密集的计算，编码速度高，压缩效果也非常好。(a)码率对比 峰值信噪比/dB(b)峰值信噪比对比 (c)压缩率对比 (d)编码速度对比 图图图图5 对对对对8个不同内容个不同内容个不同内容个不同内容视频视频视频视频的编码性能对比的编码性能对比的编码性能对比的编码性能对比 相比较而言，riverbed有相对复杂的运动特征，它是一个河床流水的视频，有波动性和透明性等特征。football是很多球员在踢球的视频，镜头移动非常快，画

24、面中人物运动也相当剧烈。这些复杂的图像特征需要编码器在运动估计阶段做许多计算和比较，增加了编码这些视频的难度。3.2.2 视频分辨率相关性分析 该部分比较了同一视频内容下不同分辨率(qcif:176 144,cif:352288,4cif:704576,720p:1 280720,1080p:1 9201 080)的4个编码器的编码效果，图6显示了结果。显然，高清的HD视频需要更多的码率，同时也会有更好的压缩效果，诸如更高的PSNR和更低的压缩比。xvidx264vp8码率对比riverbed_qcifriverbed_cifriverbed_4cifriverbed_720priverbed

25、_1080p05 00010 00015 00020 00025 00030 00035 00040 00045 00050 000(a)码率对比 (b)峰值信噪比对比 (c)压缩率对比 (d)编码速度对比 图图图图6 对对对对5个内容相同但分辨率不同的视频编码性能对比个内容相同但分辨率不同的视频编码性能对比个内容相同但分辨率不同的视频编码性能对比个内容相同但分辨率不同的视频编码性能对比 第40卷 第4期 299 孙公瑾，安 虹，范东睿：多标准视频编码器下的运动估计评估 就编码器而言，虽然vp8的编码质量比xvid和x264要差一点，但是它的码率和压缩比要比后两者低。最令人感兴趣的是编码速度。

26、vp8中5个视频的编码速度顺序和xvid的正好相反。x264中这5个值却是几乎一样。因此，vp8对高清视频的支持要好于xvid或x264。3.3 输入集构建输入集构建输入集构建输入集构建 根据以上的分析，选择4个典型的视频(总共包含4个分辨率)来产生ME程序集所需要的中间数据。在3个编码器中加入插桩代码来截取运动估计模块所需要的输入数据，将其作为单独的文件保存于磁盘上。这些数据文件正是ME程序所需要的输入文件。表3列出了所选择的视频和相应的特征描述以及ME程序集的输入文件数。表表表表3 运动估计算法程序集的输入集运动估计算法程序集的输入集运动估计算法程序集的输入集运动估计算法程序集的输入集 分

27、辨率 视频序列 视频内容特征 输入数据文件数 cif(352288)akiyo 背景静止 前景细微变化 7(7个ME程序)city 镜头缓慢移动 7 football 镜头快速移动 7 riverbed 水流/透明/波动 复杂的运动 很难被编码 7 4cif(704576)akiyo city football riverbed 同上 28 720p(1 280720)riverbed 同上 7 1080p(1 9201 080)riverbed 同上 7 4 性能分析性能分析性能分析性能分析 4.1 实验环境实验环境实验环境实验环境 处理器和OS前文已经给出，具体的实验环境配置如 表4所示。

28、表表表表4 实验环境配置实验环境配置实验环境配置实验环境配置 参数 内容 处理器 Intel Xeon E5520 频率 2.27 GHz 微结构 Nehalem 指令集 x86_64 核数 4 每核硬件线程数 2 L1 Cache 32 KB指令+32 KB数据 L2 Cache 256 KB，片上Cache L3 Cache 8 MB，片上Cache，四核共享 分支预测器 二级BTB OS CentOS release 5.3,Linux kernel 2.6.18-128.e15 Compiler gcc 4.1.2，无优化参数 性能分析工具用的是基于硬件事件采样的Oprofile。对7

29、个运动估计程序(单线程)进行了2种分析：算法性能分析和微结构性能分析。前者观察其在不同视频内容和分辨率下的运行时间，后者观察其在同分辨率不同视频内容下的微结构特性，包括指令级并行性(Instruction Level Parallelism,ILP)、LLC(Last level cache)Cache miss和分支预测精确度。4.2 算法性能分析算法性能分析算法性能分析算法性能分析 以算法运行时间为指标进行衡量。图7和图8分别就视频内容和分辨率的2种配置进行统计(图7中的分辨率是cif:352288)。数据走向跟前文的分析一致，运动程度剧烈的高复杂视频和高分辨率视频有着更长的ME运行时间。

30、xvid_me_advdiaxvid_me_squarexvid_me_diax264_diax264_hexx264_umhvp8_diamondakiyocityfootballriverbed01020304050607080运动估计算法 图图图图7 ME算法在算法在算法在算法在相相相相同分辨率同分辨率同分辨率同分辨率、不同内容视频输入的性能对比不同内容视频输入的性能对比不同内容视频输入的性能对比不同内容视频输入的性能对比 运行时间/s 图图图图8 ME算法在算法在算法在算法在相相相相同内容同内容同内容同内容、不同分辨率视频输入的性能对比不同分辨率视频输入的性能对比不同分辨率视频输入的性

31、能对比不同分辨率视频输入的性能对比 4.3 微结构性能分析微结构性能分析微结构性能分析微结构性能分析 4.3.1 指令级并行性 本节实验统计ME算法在Nehalem上的单核指令级并行性。用IPC(Instructions Per Cycle)来衡量这个指标。IPC越高，表明程序在该微结构上的指令级并行性就越好。图9给出了7个程序在同一分辨率(cif:352288)不同视频内容下的IPC。xvid_me_advdiaxvid_me_squarexvid_me_diax264_diax264_hexx264_umhvp8_diamond 图图图图9 ME算法在算法在算法在算法在相相相相同分辨率同分

32、辨率同分辨率同分辨率、不同内容视频输入的不同内容视频输入的不同内容视频输入的不同内容视频输入的IPC 300 计 算 机 工 程 2014 年 4 月 15 日 从图9中可以看出，除了xvid_me_advdia和xvid_me_ square在riverbed上的IPC偏低外，其他运行实例的IPC都保持在1.7左右。因为Nehalem单核的指令发射宽度为4，所以理想的IPC应为4。显然，当前的运动估计算法在Nehalem上普遍没有太好的指令级并行性，原因和算法的逻辑及代码实现有更大关系，这两方面都需要进一步改进以便提高现存及未来编码器的性能。4.3.2 LLC Cache缺失率 在所有的28

33、次运行中(7个程序，每个接受4个视频输入)观察到的LLC Cache缺失次数与retired的访存指令数(Loads/Stores)相比几乎可以忽略不计，差距达到了5个数量级，命中率几乎都在99.99%以上。可见Nehalme的Cache机制对ME算法的支持是非常好的。因为所有运行实例的缺失率都非常低(缺失率不到0.01%)，所以本部分不再画图表示。4.3.3 分支预测精确性 本节实验统计ME算法在Nehalme上的分支预测性能。衡量指标为分支误预测率，表示运行时误预测的分支指令数占总分支指令数的比例。误预测率越低，表示微结构对程序的分支指令有越好的性能支持。图10给出了7个程序在同一分辨率(

34、cif:352288)不同视频内容下的分支误预测率(Branch Misprediction Rate,BMR)。图图图图10 ME算法在算法在算法在算法在相相相相同分辨率同分辨率同分辨率同分辨率、不同内容视频输入的不同内容视频输入的不同内容视频输入的不同内容视频输入的BMR 从图10中可以看出，总体上所有程序的分支误预测率都比较低，在10%以下。而对比3个编码器，注意到xvid中的运动估计算法相对另外2个编码器有着更高的分支误预测率，而且差距非常大。尤其是在具有复杂运动特征的视频下非常明显，比如在football和riverbed上的差距平均值分别达到了3.5%和5.5%。由此可知xvid中

35、的ME算法有着相对不规则的分支行为，而Nehalme的分支预测器对这种行为支持得不够好，因此，还需要从算法或代码上优化来提高性能。另一方面，对比4个视频之间的BMR，可以发现复杂视频比简单视频的误预测率更高，而在xvid的ME算法中这一差距更明显。不同视频之间的BMR对比跟前文4.2节图中的数据走势一致，原因是复杂视频需要运行更长的时间，即执行更多的指令，包括分支指令，因此，造成了分支误预测率的上升。但是从图中也可以看出，这种升高幅度在x264和vp8的ME算法中很小，说明这些算法的分支行为模式能被Nehalme的分支预测器很好地预测，即使执行的分支指令数增多也不会造成BMR的大幅度提高。5

36、结束语结束语结束语结束语 本文针对当前流行的视频编码器中的运动估计算法进行了详细的对比研究。选取了3个典型的视频编码器xvid、x264和vp8，并从中提取出独立的运动估计算法模块。然后在分析了大量不同类型视频序列的基础上构建了这些模块的输入集。最后在Intel Nehalem微结构平台上对这些算法的算法性能和微结构性能进行了量化分析。实验结果表明，对于具有复杂运动特征的视频或是高分辨的视频而言，ME的运行时间要远高于其他视频。同时，这些ME算法的IPC相差不大，基本上都分布在1.51.8之间，平均在1.7左右。对于四发射的单处理器核而言，这个值偏低，表明ME算法在Nehalem上的指令级并行

37、度不高。但是所有算法的LLC Cache miss rate都非常低，达到了几乎可以忽略不计的地步，反映出它们极好的Cache性能。对于分支误预测率，虽然xvid的表现不太良好，但总体上也比较低，而另外2个编码器x264和vp8基本都在1%以下，反映出这7个ME算法还是有着相对较好的分支代码性能。下一步的工作是研究更高效的运动估计算法，包括算法上和代码上的优化，并在处理器微结构平台上(如Sandy Bridge、Ivy Bridge等)分析其性能特征，以便为今后诸多挑战性的视频应用，如更高效的编码器、更复杂的视频、超高清视频等提供相应的研究基础。参考文献参考文献参考文献参考文献 1 Zheng

38、 Weiguo,Ahmad I,Liou M L.Benchmark the Software Based MPEG-4 Video CodecC/Proc.of the 8th IEEE International Conference on Electronics,Circuits System.S.l.:IEEE Press,2001:289-292.2 毕厚杰,王 健.新一代视频压缩编码标准:H.264/AVCM.2 版.北京:人民邮电出版社,2009.3 周 巍,史浩山,周 欣.基于 H.264 的快速运动估计算 法J.计算机工程设计,2007,28(2):379-382.4 吕 瑞,卿粼波,何小龙,等.一种用于运动估计的十字六边形搜索算法J.计算机工程,2007,33(13):227-229.5 Slingerland N T,Smith A J.Design and Characterization of the Berkeley Multimedia WorkloadJ.Multimedia Systems,2002,8(4):315-327.(下转第304页)