一种基于HEVC视频编码的快速运动估计方法

韩从道， 许士芳

（上海应用技术学院电子与电气工程学院，上海 201418）

一种基于HEVC视频编码的快速运动估计方法

韩从道， 许士芳

（上海应用技术学院电子与电气工程学院，上海 201418）

运动估计是影响下一代视频编码标准高效率视频编码（HEVC）性能的关键因素，它通常利用当前帧的图像块在多重参考帧中对应的搜索窗口中寻找最佳匹配块来完成的.针对HEVC编码标准提出了一种快速的运动估计方法快速分级搜索（FHS）.首先，根据多个备用的运动矢量确定起始搜索点的位置，以起点为中心，执行搜索半径依次扩大的三圈钻石搜索，如果执行了内部两圈钻石搜索，最佳匹配点仍位于起点，则提前终止搜索.否则，根据最佳匹配点在内圈、中圈和外圈菱形边缘的情况，提出了不同的后续搜索策略.测试结果表明，提出的快速运动估计算法相对HM14.0提供的算法，平均搜索较少的点数，同时对编码后视频的质量只造成轻微的损失.

运动估计；匹配块；钻石搜索；六边形搜索；多重参考帧

高效率视频编码（HEVC）是由国际电信联盟远程通信标准化组织（ITU-T）和国际标准化组织（ISO）及国际电工委员会（IEC）共同组建的视频编码联合协作组推出的下一代视频编码标准，它相对于H.264标准具有无可比拟的优势［1］.它在数字视频压缩和传输、智能电视、高清电视领域有着良好的应用前景.在相同的视频压缩质量下，HEVC所产生的码流比特率可以节约50%左右［2］，压缩效率得到进一步提高.

运动估计在编码过程中大概占据了一半的编码时间和运算复杂度［3］，如何寻找快速高效的运动估计算法一直是视频编码领域所研究的一个热点问题.HEVC是将每帧按编码单元（CU）为基本单位进行编码的，每个CU是最大尺寸64×64至最小尺寸8×8不等的方形块.CU按照四元树结构进行组织，并且每个CU按照预测方式划分成不同尺寸的预测单元PU［4］.假设CU的尺寸是2N×2N，那么每个PU可能的尺寸有2N×2N、2N×N、N×2N、N ×N、2N×nU、2N×nD、n L×2N、nR×2N，其中N表示常数4、8、16、32、64.2N×2N是未划分的PU尺寸，2N×N、N×2N、N×N是对称划分后的PU尺寸，2N×n U、2N×nD、n L×2N、nR×2N是非对称划分后的PU尺寸［5］，nU和nD是处于上、下两个部分PU的垂直宽度，而n L和n R是处于左、右两个部分PU的水平宽度.对于2N×2N的CU，可以沿水平方向将其分割成2N×（N／2）和2N×（3N／2）的2个PU，处于上方的PU尺寸表示为2N× n U，处于下方的PU尺寸表示为2N×n D.类似地，2N×2N的CU也可沿垂直方向将其分割成（N／2）×2N和（3N／2）×2N的2个PU，处于左、右两边的PU尺寸分别表示为n L×2N和nR×2N.同时，运动补偿亮度块的最小尺寸只能为8×4或4×8.

确定最优的运动矢量，HEVC继承了H.264视频编码标准中的代价函数的方法.代价函数采用一个基于率失真（RD）模型的拉格朗日函数［6］，通常如下表示：

式中：J是代价函数；第1项是当前图像块与参考帧中匹配图像块之间失真，用两个图像块对应位置各像素亮度差的绝对值之和来表示，记成SAD；λMOTION是拉格朗日乘法因子；当前块候选的运动矢量MVcandidate与预测的运动矢量PMV之间的差记为MVD；函数R表示编码MVD所需要的比特数.

最优的运动矢量对应于取得最小代价函数的运动矢量［7］，可表示为：

1 发展与现状

围绕提高编码速度、降低运算复杂度的课题，很多快速的运动估计算法被提出.Pan等［7］针对HEVC中的测试区域（TZ）搜索提出了一种早期终止算法，基于使用大CU和小CU得到的不同的最佳点，分别使用钻石搜索或六边形搜索来早期终止TZ搜索.Yang等［8］提出了一种基于方向搜索的快速运动方法.它首先以起始点为中心，搜索其周围8个点，如果具有最小率失真代价的点仍位于中心，则停止搜索.否则，根据处于边缘的最优点位置方向，不断补充新的相邻三点，直到新产生的最优点位置不再发生改变为止.最后，在可能的水平或垂直方向轴上，寻找大位移的运动矢量，从所有可能的候选点中，找到具有最小RD值的运动矢量.

Kibeya等［3］对TZ算法进行了改进，提出了用直线钻石模式、小钻石模式或水平钻石模式取代光栅扫描算法的模型.但是，这种单纯的小钻石搜索容易导致陷入局部最优的情形.Purnachand等［4］采用半径不断扩大的水平和垂直六边形以及旋转的六边形来代替钻石搜索方案，并采用一个自适应的阈值来提前终止搜索.但是，当最优点离起始搜索中心较远时，最优点的位置精度会下降.

HEVC编码软件采用的运动估计方法是一种快速的TZ搜索，它首先从几个候选的运动矢量中挑选一个作为搜索的起点.然后以该点为中心，进行距离每次翻倍扩大（从1到64）的多圈钻石或正方形搜索.为了提高搜索效率，一般选取钻石形搜索.如果经过连续三圈搜索，最优点的位置未发生变化，则退出当前的多圈搜索.如果最优点仍位于起始点，则提前结束搜索.如果最优点离起始点的距离为1，则再搜索最优点附近的两点，然后退出.如果最优点离起始点的距离超过5，则还需进行光栅式网格搜索.以新的最优点为起点，进行精细搜索，直到最优点位置不再发生改变.这种方法对于大位移的运动矢量，由于要采用光栅网格搜索，导致搜索的点数过多，影响编码性能.

本文在TZ快速搜索方法的基础上，提出了一种分级搜索的策略，同时，避免了高成本的栅格搜索.首先，确定始搜索点的位置.然后，以该点为中心，执行搜索距离依次扩大的三圈钻石搜索，如果内部两圈钻石搜索执行完后，最佳匹配点位于起点，则提前结束搜索.否则根据最佳匹配点在内圈、中圈和外圈菱形边缘的情形，采用不同的后续搜索模式.

2 测试区域TZ搜索

在HEVC编码中，采用基于测试区域TZ的搜索.它既包含了以往H.264编码方案中常用的钻石搜索，又有覆盖范围广的光栅网状搜索，其基本算法可分为4个部分.

2.1 起始搜索点的确定

HEVC中采用两个候选的运动矢量.一个是预测的运动矢量，它是当前PU左边、上方和右上方3个PU的运动矢量的中值.另一个是零运动矢量（0，0），记为MVzero，从这两个运动矢量中选出具有最小RD代价的作为起始搜索点MVstart，那么MVstart一定是由预测的运动矢量和零运动矢量所构成的集合中的元素，如下式所示：

搜索限定在以起始坐标为（0，0）点，水平和垂直方向各为［-64，64］的区间范围里.

预测的运动矢量通常记为pmv，而当前PU实际的运动矢量记作mv，两者之间的差记作Δmv，运动搜索可以看成确定Δmv的过程，则

2.2 距离扩大的钻石搜索

以起始搜索点为中心，进行搜索距离不断翻倍（从1～64）的钻石搜索，如图1所示.

图1 搜索距离为1～64的钻石组模型Fig.1 The diamond group model with search distance from 1 to 64

从最内圈到最外圈的钻石形的搜索距离依次为1，2，…，64，由于搜索距离为64的钻石形过大，故最外圈钻石形作了简略表示.以起点为中心，由内圈往外圈依次搜索，不断更新搜索到的最优点位置.如果经过连续3圈，最优点的位置未发生改变，表明最优点位置稳定，则退出钻石组搜索.随着搜索往外圈推进，各点之间的间距较大，影响搜索的精度.在最差情形下，最多搜索除起点外的64个点.

2.3 栅格搜索

如果搜索得到的最优点位于中心点，则提前结束整个搜索过程.如果最优点位于离中心距离为1的小菱形上，则补充搜索与最优点对角相邻的两个点，然后结束全部搜索.图2示出了当最优点位于小钻石上方需补充搜索的两点情形，以空心点表示.如果上述两种情形都没有满足，则将最优点离起始点的距离存入变量uiBest Distance.

图2 当最优点位于小钻石上方需补充搜索的两点位置Fig.2 The location of two points which are needed to search additionally when the best point is on the top of the small diamond

如果uiBest Distance超过光栅间隔值iRaster通常设置为5），则启动光栅扫描搜索，并将uiBestDistance的值置为iRaster.搜索在整个测试区域TZ进行.搜索从测试区域的左上角位置开始，逐行扫描，点与点之间的水平和垂直间距为iRaster.由于水平方向的区间范围为［-64，64］，故一行需要扫描Floor［（64+64）／5］+1=26个点，搜索完整个测试区域TZ需要26×26=676个点，可见光栅扫描的运算成本很高.图3列出了光栅扫描的示意图.

图3 光栅扫描示意图Fig.3 The diagrammatic sketch of raster scan

2.4 搜索的精细化

循环执行下面的搜索，直到uiBest Distance为零，或者最优点位于最内圈的小钻石上为止.

步骤1 以当前得到的最优点作为新的中心，执行如图1搜索距离不断扩大的钻石组搜索.

步骤2 判断是否满足退出循环的条件.

退出上述循环后，如果最优点位于最内圈的小钻石上，则补充搜索与最优点对角相邻的两点.将最后得到的最优点作为搜索得到的运动矢量，返回给主程序.可以看出，对于存在大运动幅度的视频，运动矢量的幅值普遍较大，执行钻石组和光栅搜索所消耗的运算量是巨大的.

3 快速分级搜索（FHS）方法

在运动估计过程中，既要提高运动搜索的速度，又要考虑到搜索得到运动矢量的精度.本文提出的快速分级搜索（FHS）方法主要分3个部分，起始搜索点的确定仍采用2.1节的方法.

3.1 精简的钻石组搜索

多圈钻石组搜索会出现各圈之间距离较大以及搜索点稀疏分布的情形.在开始阶段，FHS以起始点为中心，从内往外执行三圈钻石搜索，如图4所示.如果执行内部两圈后，最优点位于中心点，则提前退出，整个搜索过程结束.

图4 以起点为中心进行的三圈钻石搜索Fig.4 Three circle diamond searches centered on the starting point

3.2 分级的搜索模式

如果令精简的钻石组搜索搜得最佳匹配点P位于圈数round（P）上，则后续的搜索模式可表示为：

当最优点位于最内圈小菱形时，表明当前PU的运动强度较弱，则补充搜索与之对角相邻的两点，如图2所示，然后结束全部搜索.

如果最优点位于中圈菱形时，表明当前PU可能具有中等运动强度，则循环地执行中圈钻石搜索，并不断调整搜索中心到当前最优点位置，直到最优点位置不再改变为止.最后，以获得的最优点为中心，执行一次距离为1的小菱形搜索.类似地，如果最优点位于小菱形上，再补充搜索两点.图5举例说明了这种搜索的过程.

图5 具有中等运动强度PU的运动搜索过程举例Fig.5 The example of motion search process for PUs with medium motion intensity

在图5中，假设起始中心点的坐标是（0，0），x方向往右、y方向往下为坐标增大方向.在执行第1次中菱形搜索后，最优点位置变成（0，2）.因此，第2次搜索以当前最优点（0，2）为中心进行.由于有些点已经搜索过，本次只需再搜索5个新点，得新最优点坐标为（1，3）.类似地，第3、4次搜索得到的最优点位置为（2，4），由于连续两次最优点的位置未发生变化，故以（2，4）为中心进行一次小菱形搜索，图中以序号5标出.第5次搜索得到的最优点坐标为（3，4）.最后，检查与（3，4）对角相邻未搜索过的两点（4，3）和（4，5），发现（3，4）点比（4，3）和（4，5）具有更小的RD代价值.所以，搜索得到的最终运动矢量为（3，4）.

如果最优点位于图4的外圈菱形时，当前PU的运动强度可能很大，因此选用搜索半径广和效率高的六边形模式［9］.以外圈菱形上的最优点为中心进行六边形搜索，通过反复更新搜索中心的位置，不断执行六边形搜索，直到最优点位于六边形中心为止.最后，以最优点为中心，执行一次正方形搜索.图6举例说明了该搜索的过程.

在图6中，假设六边形的中心点坐标为（0，0），执行完第1次六边形搜索后，最优点出现在（1，2）处，以该点为中心，执行第2次六边形搜索，本次只需搜索3个新点.类似第2次搜索得到的最优点为（3，2），而第3、4次搜索得到的最优点都为（5，2）.这表明用六边形进行的粗搜索结果已经稳定，故以（5，2）为中心进行一次短距离的正方形精细搜索，确定全局最优点的位置.经搜索得到点（6，3）具有全局最小的RD代价值，从而确定出最终的运动矢量.

完整的快速分级搜索FHS算法的流程如图7所示.

图6 具有较高运动强度PU的运动搜索过程举例Fig.6 The example of motion search process for PUs with higher motion intensity

图7 快速分级搜索FHS算法流程图Fig.7 The flow chart for fast hierarchical search algorithm FHS

3.3 FHS方法的特点

首先，FHS方法确立了早期搜索退出机制，只要经过内部两圈菱形搜索，最优点仍在起始点，就可满足退出的条件，节约了搜索的运算资源.其次，根据最优点在三圈不同菱形上的位置，初步判定当前PU的运动强度.对于不同的强度，选用不同的后续搜索方案.对于中、高运动强度的PU，移动的菱形或六边形搜索都可进行远距离运动矢量的搜寻，后者具有更高的效率.

4 实验与仿真

提出的算法FHS在HEVC参考软件HM14.0平台上进行仿真.本文采用6个包含了不同运动程度的视频序列进行测试.视频的画面尺寸是416× 240，搜索区域的窗口是［-64，64］.实验中采用的编码帧结构是IPPPP….本文将FHS算法与HM14.0标准软件中提供的快速算法TZSearch进行比较.

对于不同的视频序列，各取200帧进行测试.对于不同的运动估计算法，采用平均每次块匹配所需搜索的点数NSP来衡量搜索的效率.将编码压缩后的结果再解码得到的视频与压缩之前的原始视频进行对比，并计算每幅图像帧的平均峰值信噪比PSNR，这是评价编码后压缩视频质量的重要指标.

4.1 平均每次搜索点数NSP

编码重建帧的视频质量与量化参数QP有关，QP越大，重建的视频质量越粗糙，许多图像细节因量化而消失.为了尽可能多的保存细节，本文选用量化参数QP为32进行测试.经统计得到6个序列的测试结果，如表1所示.

表1 QP为32时平均每次块匹配搜索的点数NSPTab.1 The average number of search points NSP for each block matching when QP equals 32

图8所示为两者不同算法的Flowervase序列每帧平均NSP值对比曲线.可以看到，不同序列TZSearch搜索的NSP值相差较大，对于运动平缓的序列如BQSquare，NSP值较小.同时，TZSearch算法求得的各帧平均NSP随视频画面中对象的运动程度起伏不定.而对于运动剧烈的视频，如赛马序列RaceHores，平均NSP值达到180.5，主要原因是由于大运动矢量的存在，TZSearch经常执行图1中的多圈菱形搜索和图3的光栅搜索，而一次光栅搜索需计算676个点的RD代价值.

图8 QP为32时Flowervase序列各帧平均NSP比较Fig.8 The average NSP comparison of each frame for sequence Flowervase when QP equals 32

FHS方法的结果相对比较稳定.一方面，由于在多数情况下，实际的运动矢量mv和预测的运动矢量pmv比较接近，因而Δmv较小，而F HS对于小运动矢量采用了两圈菱形早期退出机制和补充搜索两点的方法，搜索的成本较小.对于运动程度中等或较高的PU，则采用了移动的中菱形或六边形，可以快速到达最优匹配点附近，因此，整体消耗的搜索点数不多.

4.2 平均峰值信噪比PSNR

两种方法每帧平均PSNR性能的比较归纳在表2中，总体PSNR的计算是基于像素的亮度Y和色度U、V分量进行的，可用下式表示［10］：

由表2可知，两种方法编码后重建帧的质量仅有较小的差别.FHS方法的平均PSNR值比TZSearch方法只有微小的下降.

表2 QP为32时平均每帧峰值信噪比PSNR（d B）Tab.2 The average peak signal to noise ratio for each f rame when QP equals 32

5 结 语

本文针对HEVC中运算耗时的运动估计问题提出了一种快速的分级搜索方法.首先根据邻近块的运动信息确定起始搜索点.为了提高搜索效率，对于小的运动矢量，采用早期退出或补充搜索与当前最优点对角相邻两点的方法.对于中、高运动强度的图像块，分别采用移动的中菱形和六边形搜索，快速到达最优点附近位置.最后，采用精细的小菱形或正方形确定出全局最优点.实验结果表明，FHS与HEVC的TZSearch方法相比，编码后重建帧的质量没有明显的下降，但平均每次搜索的点数显著减少，降低了编码的运算复杂度.

［1］ Ohm J R，Sullivan G J，Schwarz H，et al.Comparison of the coding efficiency of video coding standards—including high efficiency video coding（HEVC）［J］. IEEE Transactions on Circuits and Systems for Video Technology，2012，22（12）：1669-1684.

［2］ Sullivan G J，Ohm J R，Han W J，et al.Overview of the high efficiency video coding（HEVC）standard［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22（12）：1649-1668.

［3］ Kibeya H，Belghith F，Loukil H，et al.TZSearch pattern search improvement for HEVC motion estimation modules［C］／／1st International Conference on Advanced Technologies for Signal and Image Processing.New York：IEEE，2014：95-99.

［4］ Purnachand N，Alves L N，Navarro A.Fast motion estimation algorithm for HEVC［C］／／2012 IEEE Second International Conference on Consumer Electronics.New York：IEEE，2012：34-37.

［5］ Bossen F，Bross B，Suhring K，et al.HEVC complexity and implementation analysis［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22（12）：1685-1696.

［6］ Helle P，Oudin S，Bross B，et al.Block merging for quadtree-based partitioning in HEVC［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22（12）：1720-1731.

［7］ Pan Z，Zhang Y，Kwong S，et al.Early termination for TZSearch in HEVC motion estimation［C］／／The 38th International Conference on Acoustics，Speech，and Signal Processing.New York：IEEE，2012：1389-1393.

［8］ Yang S，Jiang J，Yang H.Fast motion estimation for HEVC with directional search［J］.ElectronicsLetters，2014，50（9）：673-675.

［9］ Zhu C，Lin X，Chau L P.Hexagon-based search pattern for fast block motion estimation［J］.IEEE Transactions on Circuits and Systems for Video Technology，2002，12（5）：349-355.

［10］ Yu L，Fu G，Men A，et al.A novel motion compensated prediction framework using weighted AMVP prediction for HEVC［C］／／2013 Visual Communications and Image Processing.New York：IEEE，2013：1-6.

（编辑 俞红卫）

A Fast Approach to Motion Estimation Based on HEVC Video Coding

H AN Cong-dao， XU Shi-fang
（School of Electrical and Electronic Engineering，Shanghai Institute of Technology，Shanghai 201418，China）

Motion estimation is a critical factor which affects the coding efficiency of next video coding standard HEVC.It is usually performed by searching the best matched block of current frame image block in corresponding search windows of multiple reference frames.A fast motion estimation approach FHS was proposed for HEVC coding standard.Firstly，the position of initial search point was determined on the basis of multiple available motion vectors.Centered with the starting point，three circle diamond searches were performed with the expansion of search radius.The searches would terminate if the best matched point was still situated at the starting point when the two inner circle diamond searches were finished. Otherwise different successive search strategies were put forward based on the cases that the best matched point situated at the edge of inner，middle or outer circle diamond.The test results showed the proposed fast algorithm could attain less average search points compared to that afforded by H M14.0，meanwhile，it only did slight damage on the quality of coded video.

motion estimation；matched block；diamond search；hexagon search；multiple reference frames

TN 919.81

A

1671-7333（2015）01-0079-07

10.3969／j.issn.1671-7333.2015.01.014

2014-08-29

上海应用技术学院引进人才基金资助项目（YJ2012-5）

韩从道（1971-），男，讲师，博士，主要研究方向为视频编码与信号处理.E-mail：hancongdao＠163.com