一种HEVC整像素运动估计优化算法

崔岩松，赵佳瑜，任维政

(北京邮电大学智能交通信息与网络技术实验室，北京100876)

HEVC/H.265视屏编解码标准是新一代视频编解码国际标准，由ISO与ITU共同制定，它主要是为在保证视频质量的情况下提高压缩率、降低网络带宽，支持更大的视频尺寸，更精细的编码控制，用于对视频要求更高的场合［1-2］。但是，HEVC由于其复杂度高，很难具有实用的效果，所以必须进行优化加速。本文以研究HEVC标准为基础，在加深HEVC标准理解的基础上，着手对测试模型HM进行优化加速。

和现有的视频编码标准类似［3］，HEVC保留混合编码的基本体系结构［4-5］。一个显著的区别在于用类似四叉树(quadtree)的结构替代了传统的宏块(macroblock)［6］。HEVC编码流程可分解为预测、变换、量化和熵编码4部分［7］。预测部分将对编码器性能产生很大的影响［1］。预测分为帧间预测(inter prediction)，和帧内预测(intra prediction)［1］，帧内预测消除视频序列的空间相关性，用于编码I帧图像［8-9］，帧间预测消除视频序列的时间相关性，用于编码P帧图像［8，10］。其中，帧间预测的大致流程为:输入像素块与前一帧参考帧进行运动估计后［11-12］，先进行整像素运动估计、分像素内插和分像素运动估计，产生运动矢量，之后对已获得的运动矢量进行运动补偿得到预测数据块［1，13］。所以相比帧内预测，帧间预测消除的时间相关性对视频压缩的压缩比有很大的关联［14］。本文主要对整像素运动估计所采用的算法进行优化。

1 整像素运动估计优化算法

HEVC中快速运动的估计首先进行整像素运动估计，运用搜索模板找到最佳匹配的整像素点;之后进行分像素内插，再进行分像素运动估计，在整像素运动估计所找到的最佳匹配点的周围进行，检测其1/2和1/4像素点，找到最佳匹配的分像素点，主要通过调用底层的函数来实现［16］。整像素运动估计得到的是运动矢量的整像素值，决定了运动矢量的大致方向，因此，对其进行优化是十分必要的。

本文主要针对整像素运动估计采用的EPZS算法进行优化。HEVC沿用了H.264/AVC的EPZS作为默认的快速运动估计算法。该算法主要由运动矢量选择、提前终止策略、运动矢量提取3部分组成。文献中测试显示，EPZS算法比全搜索算法加速比最大达6倍［15］，且能保证良好的压缩性能和图像质量。HEVC整像素运动估计中采用的EPZS算法可以简述为:在大小为64×64的搜索框中，使用步长(l)从1开始，以2的指数递增的8点菱形搜索，当SAD小于设定的阈值时停止搜索，得到运动矢量。在快速算法中，不同类型和尺寸的搜索模板一定程度上决定了搜索的效果。根据视频序列的中心偏移性(MVD)，其运动矢量分布通常集中在搜索窗的中心位置附近，即大多数图像序列的运动都是平稳和缓慢的。8点菱形搜索适合搜索步长适中的点，对于搜索步长较小的点或较大的点，得到的搜索效果并不理想。因此，应该更改开始和提前终止的策略，优化搜索模板。

为此，在提出运动矢量搜索优化算法之前，需要统计现实序列运动矢量的分布，根据统计结果进行类型划分和调整搜索模板，减少搜索次数和运动估计计算量。由于搜索终止步长分布可以间接反映运动矢量分布情况，且数据易于得到、统计方便，本文模板优化的依据为搜索终止步长的统计分布。

通过测试得到176×144(qcif)测试序列搜索终止步长的统计分布和176×144(qcif)测试序列搜索终止步长的统计分布，如表1和表2所示。

表1 176×144(qcif)测试序列搜索终止步长的统计百分比 %

表2 1 920×1 080(class E)测试序列搜索终止步长的统计百分比 %

根据以上分析，提出一种EPZS优化算法及搜索模板，搜索模板见图1。搜索框尺寸保持默认值64，调整的EPZS搜索点为3类:4点的菱形搜索，8点的菱形搜索和16点的菱形搜索。当步长小于2时使用4点菱形搜索模板，如图1a所示;当步长在2～4时使用8点菱形搜索模板，如图1b所示;当步长大于8时使用精度大的16点菱形搜索模板，如图1c所示。开始整像素运动估计算法之后，从距离为1开始对起始搜索点附近的点进行搜索，每次搜索步长以2的幂次增长，每次搜索根据步长选择对应的模板。即4点菱形搜索只是搜索距离为1时的搜索模板，8点菱形搜索是搜索距离为2，4，8的时的搜索模板，16点菱形搜索是搜索距离为16，32，64的时候的搜索模板。

图1 4点、8点和16点菱形搜索模板

2 测试结果

根据优化算法，对测试模型HM进行优化，并使用不同格式的视频序列对优化后的编码器进行了测试，下面给出了尺寸为176×144(qcif)和1 920×1 080(class E)的几个视频序列的测试结果。

测试视频序列配置如下:测试序列尺寸为176×144(qcif)，编码帧数为60帧，帧率为155 f/s(帧/秒)，序列比特深度为8;测试视频序列尺寸为1 920×1 080(classE)，编码帧数为5，帧率为25 f/s，序列比特深度为8。

表3显示了尺寸176×144(qcif)测试视频序列优化前后比较结果，其中编码帧数60，帧率5 f/s，序列比特深度为8。

表3 176×144格式图像编码优化测试前后的性能变化 %

表4显示了尺寸1 920×1 080(class E)测试视频序列优化前后比较结果，其中编码帧数60，帧率5 f/s，序列比特深度为8。

表4 1 920×1 080格式图像编码优化测试前后性能变化百分比 %

3 结束语

根据表3和表4，可以得到结论如下:

对于尺寸为176×144测试视频序列，优化后，对于视频质量的客观值，亮度分量Y平均下降0.005 0 dB，色度分量U平均下降0.043 4 dB，色度分量V平均下降0.072 6 dB，编码后码流比特率最多上升2.21%，耗时最少下降3.03%。

对于尺寸为1 920×1 080测试视频序列，优化后，对于视频质量的客观值，亮度分量Y平均上升0.008 1 dB，色度分量U平均下降0.014 9 dB，色度分量V平均下降0.047 7 dB，编码后码流比特率最多上升0.40%，耗时最少下降1.25%。

因此，可以确定该算法对尺寸为176×144和1 920×1 080视频序列的编码实现了优化。在保证视频质量不变和编码后码流略微上升的前提下，降低了编码耗时，且在每一次视频序列测试中，编码耗时下降程度超过了编码后比特率的上升程度。

［1］ SULLIVAN G，OHM J，HAN W，et al.Overview of the high efficiency video coding(HEVC)Standard ［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1649-1668.

［2］ ZHOU M，GAO W，JIANG M，et al.HEVC lossless coding and improvements［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1839-1843.

［3］ OHM J，SULLIVAN G，SCHWARZ H，et al.Comparison of the coding efficiency of video coding standards-including high efficiency video coding(HEVC)［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1669-1684.

［4］ KIM I，MIN J，LEE T，et al.Block partitioning structure in the HEVCstandard ［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1697-1706.

［5］ High efficiency video coding［EB/OL］.［2014-06-05］.http://en.wikipedia.org/wiki/High_Efficiency_Video_Coding.

［6］ HELLE P，OUDIN S，BROSSB，et al.Block merging for quadtreebased partitioning in HEVC［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1720-1731.

［7］ OHM J，SULLIVAN G，WIEGAND T，et al.Introduction to the special section on the HEVC standard ［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1647-1648.

［8］林福宗.多媒体技术教程［M］.北京:清华大学出版社，2009.

［9］ LAINEMA J，BOSSEN F，HAN W，et al.Intra coding of the HEVC standard ［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1792-1801.

［10］ KAMP S，WIEN M.Decoder-side motion vector derivation for block-based video coding［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1732-1745.

［11］ LI H，LI B，XU J.Rate-distortion optimized reference picture management for high efficiency video coding［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1844-1857.

［12］ SJOBERG R，CHEN Y，FUJIBAYASHI A，et al.Overview of HEVC high-level syntax and reference picture management［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1858-1870.

［13］ YUAN Y，KIM I，ZHENG X，et al.Quadtree based nonsquare block structure for inter frame coding in high efficiency video coding［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1707-1719.

［14］ BOSSEN F，BROSS B，SüHRING K，et al.HEVC complexity and implementation analysis［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1685-1696.

［15］徐荣飞.HEVC编解码算法的CUDA优化［D］.北京:北京邮电大学，2013

［16］ CHI C，ALVAREZ-MESA M，JUURLINK B，et al.Parallel scalability and efficiency of HEVC parallelization approaches［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1827-1838.