朱鑫磊　汪伟

关键词：运动估计；块匹配提前终止；八边形-“十”字栅格搜索；精细搜索

中图分类号：TP391 文献标识码：A

1引言（Introduction）

随着5G网络通信技术的迅速发展，以及人们对视频质量要求的提高，促使编码标准不断改进和完善。高效率视频编码（H.265/HEVC）[1]作为应用最广泛的视频编码标准，满足了大部分领域的应用条件。与高度压缩数字视频编解码器标准（H.264/AVC）[2]相比，H.265/HEVC可以在使用H.264/AVC一半码流的情况下，解码重建出与其在主观上有着相同画面质量的高清视频，其更加优秀的压缩比可以在相同网络带宽的环境下传输清晰度更高的视频。虽然H.266标准已经被提出，其在深度学习和多特征融合方面展现了良好的效果，并且相较于HEVC，压缩率约提高了一倍[3]，但是HEVC仍然是目前使用最为广泛的视频编码标准，其针对机器学习中编码单元块的预测仍然很有效果[4]。运动估计算法作为高效视频编码中占比最高、时间处理最长的步骤，在视频编码中占据着举足轻重的地位。

近年来，熵编码[5]的应用，使得编码更加灵活，也更加多元。运动估计（ME）作为基于块的视频编码器的重要组成部分之一，其对编码算法的要求最高、最复杂、最苛刻。块匹配运动估计算法是H.265/HEVC中应用最广泛的算法之一，XU等[6]提出一种针对HEVC测试区域的搜索模式，通过对编码单元块进行块内复制，借助对编码内容的扩展，达到选中最佳匹配块的目的，但是该算法仍然存在很多的计算冗余。YANG等[7]提出基于方向的快速运动搜索方法，通过改进搜索方式减少搜索参考块的个数和计算次数，以此达到减少编码所需时间的目的，但是该算法存在计算量大的问题，而且视频编码运算中对实时性的要求无法较好地满足。CHUNG等[8]针对块匹配运动估计中存在运动伪影的问题，提出了一种将运动估计和图像重建的离散问题建模为可分离的非线性最小二乘问题的方法，使得编码质量获得提升。ABDELAZIM等[9]利用鉆石搜索的方式，在三次钻石搜索后采取半像素六边形搜索，保留了算法的搜索精度。MADHUVAPPAN等[10]提出了增强型测试区域搜索算法，对一定的搜索区域采取下采样遍历搜索，可以在一定程度上减少局部最优的情况，提高了编码的质量。唐浩漾等[11]通过研究运动矢量分布规律，提出一种基于HEVC的异构钻石模板快速搜索算法，提高了搜索精度。蔡于涵等[12]提出一种基于运动矢量细化的帧率上变换与HEVC结合的视频压缩算法，通过结合算法细化运动矢量，提高了重建速度。为了能够更好地适配硬件，张志勇等[13]提出一种基于并行螺旋搜索算法的整像素运动估计硬件架构，采取共享搜索过程的方式减少了搜索周期数。秦传义等[14]提出一种基于FPGA的运动估计算法，减小了系统架构的内部资源消耗，使得FPGA上资源利用率获得提升。基于现有的块匹配提前终止策略与运动估计改进算法的研究，本文提出了一种基于条件判据改进的提前终止运动估计算法，并且通过实验得出结论，在基本不影响视频质量的情况下，改进之后的算法相比原有标准算法，平均降低了42％的编码时间。

2运动估计标准算法（Motion estimation standardalgorithm）

2.1确定起始搜索点

研究人员利用先进运动矢量预测技术（AMVP）选出最小预测运动矢量MVP、当前预测单元块左侧、上侧、右上及零向量共五个候选矢量，并从中选出匹配误差最小点作为起始搜索点[15]。匹配误差（SAD）最小点计算公式如式（1）所示：

2.2初始网格搜索

HEVC标准算法中，初始网格搜索阶段首先将起始搜索点作为当前块匹配搜索的中心，接着以步长为1、2、4、8、16、32、64进行钻石搜索（Diamond Search）[16]或者栅格搜索，选取率失真代价最小的点作为初始网格搜索阶段的预测矢量。钻石搜索如图1（a）所示，栅格搜索如图1（b）所示。

2.3两点搜索

若初始网格所得到最佳候选点步长为1，就会导致该点周围有两个点没有搜索到，于是补充两点搜索，若得到的最佳点大于某个阈值，则以该点为起点，在一定范围进行全搜索，找到率失真代价最小点。

2.4精细搜索

以两点搜索所得最优点为新的起始搜索点，继续跳转到初始网格搜索步骤中进行精细搜索，直到两次得到的精细搜索结果为一致时，停止搜索[17]，此时得到的就是最优预测矢量。

3改进后的运动估计算法（Improved motionestimation algorithm）

3.1起始搜索点的确定

为了减少寻找起始搜索点所需时间，先进运动矢量预测技术应运而生，它能够有效地去除运动信息之间的冗余，一般算法步骤为从候选的五个位置中选取两个候选预测矢量，分别是当前块的左侧和上侧，以这两个候选预测矢量为中心，进行步长为1的钻石搜索，如果一次钻石搜索之后能够检测到一个可用的运动矢量，那么直接选用该矢量作为候选预测矢量，不再检测其他剩余的候选，这就使得预测运动矢量的时间缩短了很多。将先进运动矢量预测技术选出的率失真代价最小的预测运动矢量MVP与以该点为中心进行步长为1和2的钻石搜索选出的最佳匹配点P进行对比，判断是否一致，若一致，则搜索终止，完成运动估计；若不一致，则按照原来的标准算法进行起始搜索点的确定。该步骤主要目的就是利用快速搜索的方式，提前确定一些相对静止区域的最佳匹配点，不必再将这些预测矢量采取标准算法中的复杂步骤。具体流程如图2所示。

3.2基于编码单元块提前终止策略的初始网格搜索

在HEVC中，一幅图像被划分为许多个编码树单元，每个编码树单元又被划分为一个或者是多个编码单元[18]，在编码单元的基础上，又可以被划分为多个预测单元和变换单元。CU作为编码单元，在HEVC中是基于四边形的编码单元，其最大尺寸为64×64像素，编码单元用来确定预测矢量是帧内模式还是帧间模式。PU为预测单元，包括帧内预测和帧间预测两类。TU为变换单元，用来变换和量化的基本单元，尺寸受编码单元的限制。

当一个划分深度为d 的编码单元块进行完整的编码步骤，终止编码剩余深度的选择过程等价于在率失真优化过程中采用的候选集：

3.3八边形-“十”字栅格搜索

根据GONCALVES等[20]提出运动估计算法的复杂度分析，运动矢量的分布具有中心“十”字偏置的特性，运动矢量基本都分布在搜索点的水平方向、垂直方向及搜索中心的周围，在搜索点比较远的地方，基本没有运动矢量的分布。由于此特性的存在，搜索时可以适当移除距离较远的非水平和垂直区域的栅格搜索，对于水平和垂直区域来说，运动矢量分布较多，不能忽略该搜索区域，如果忽略，虽然搜索时间减少了一点，但是有可能会使得运动矢量陷入局部最优。因此提出一种八边形-“十”字栅格搜索（Octagon-crossraster search）模板用于缩小栅格搜索的范围，以此节约搜索时间，提高搜索的效率。

八边形-“十”字栅格搜索模板选取标准栅格搜索正中央25％的区域作为搜索范围，在此基础上，进一步缩小搜索范围，将这25％的栅格搜索区域四个角的范围忽略不计，因为这四个角落与中心搜索点距离较远，并且所含的运动矢量很少。同时，增加水平和垂直方向上的搜索，使得搜索更加精确，节约了搜索时间。按照该方式进行栅格搜索，可以在保证视频质量的情况下，节约一些搜索时间。八边形-“十”字栅格搜索模型如图3所示。

3.4精细搜索

精细搜索经过分析，决定采取钻石搜索或者栅格搜索的方式来完成。为了找到率失真代价最小的点，所以将会首先以搜索步长1进行钻石搜索，然后在此基础上采取步长为2、4、8、16、32、64……这种方式继续进行钻石搜索，最终将会有两种情况出现，一种是搜索到了边界，不得已结束搜索模式，另一种是找到了最佳运动矢量为1的点，这样也可以停止精细搜索，将找到的最优矢量为1的点再进行两点搜索，这样就找到了最佳匹配块，以这种方式对其他块进行搜索，就可以完成对图片帧的精细搜索。

当遇到了搜索边界，不得以停止搜索的情况时，将会采取栅格搜索方式，将初始网格搜索得到的点与阈值进行比较，将大于阈值的点找出来[21]，并且将该点作为中心，进行步长为2的栅格搜索，遍历搜索区域，得到的率失真代价最小点就是最优点。该方式虽然相对烦琐并且会浪费一定的搜索时间，但是准确率在很大程度上得到满足，并且基本不会发生重复搜索的情况，保证了搜索的准确率。

4实验结果与分析（Experimental results andanalysis）

4.1建立测试数据库

4.1.1 最优预测点测试数据库

为验证算法的有效性， 选取B Q M a l l （ 8 3 2 × 4 8 0 ） 、V i d y o 4 （ 1 2 8 0 × 7 2 0 ） 、C a c t u s （ 1 9 2 0 × 1 0 8 0 ） 、PeopleOnStreet（2560×1600）四组视频编码测试序列，根据最佳匹配点为预测矢量点的次数在运动估计算法调用总次数中所占的比重，判断该方法的有效性。

4.1.2编码单元块提前终止策略测试数据库

建立A 类（ 8 3 2 × 4 8 0 ） 、B 类（ 1 2 8 0 × 7 2 0 ） 、C 类（1920×1080）、D类（2560×1600）四组视频编码测试序列，序列均为YUV格式，测试序列帧数均为500 帧。

4.1.3改进后运动估计算法测试数据库

采用与“ 4 . 1 . 2 ” 部分中相同的测试数据库， 即选取YUV格式的视频序列，并且选取BQMall（832×480）、V i d y o 4 （ 1 2 8 0 × 7 2 0 ） 、C a c t u s （ 1 9 2 0 × 1 0 8 0 ） 、PeopleOnStreet（2560×1600）四组视频编码测试序列，测试序列帧数均为500 帧。

4.2实验参数及环境设置

该实验所采用的硬件平台为酷睿I 5 - 8 2 5 0U处理器、8GB的内存和2.8 GHz的主频。软件配置为Windows 10 64位操作系统、Elecard HEVC Anlyzer编码视频检测工具和yuvplayer视频序列播放器。HM-16.14中配置的量化步长序号为37、32、27、22，其他配置为默认值。

4.3算法评估指标

采用最佳匹配点为最优预测点的次数在运动估计中调用总次数中所占的比重，判断最优预测点与最佳匹配点的相近程度。

4.4 实验结果

4.4.1 最优预测点为最佳匹配点概率

由表1计算可知，改进之后得到的最优预测点为最佳匹配点的平均概率为71.51％，尤其是图像中存在很多相对静止和相对平坦区域的Vidyo4序列，最优预测点为最佳匹配点的概率达到了75.15％，体现了很好的改进效果。

4.4.2编码单元块提前终止策略测试结果

在运动估计过程中，用Depth L表示划分深度为0或1的大尺寸编码单元块，用Depth S表示划分深度为2或3的小尺寸编码块。表2中的HR_L代表运动估计中使用Depth L划分的编码单元块，HR_S代表运动估计中使用Depth S划分的编码单元块。量化步长序号分别设置为22、27、32、37，以此判断不同量化参数时有效命中概率的准确性。从表2中可以看出，改进的基于编码单元块划分的提前终止运动估计算法的有效性。

4.4.3改进后的运动估计算法实验结果

为了验证本文提出算法的效果，在实验环境中进行四组不同量化参数值的运动估计标准搜索和本文改进搜索，编码得到四组不同量化参数值的峰值信噪比（PSNR）、比特率和运动估计搜索时间的参数平均值，Bitrate为编码的码率，T为运动估计搜索时间。由实验结果可知，改进后的算法在基本不影响视频质量的情况下，提高了编码速度，降低了算法的计算复杂度，节约了时间。具体结果如表3所示。

5结论（Conclusion）

针对编码器复杂度比较高、标准算法计算冗余的问题，提出一种基于条件判据改进的提前终止运动估计算法。首先利用先进运动矢量预测技术（AMVP）选出最优点MVP，并且以该点为中心进行步长1和2的钻石搜索，得到最佳匹配點P，判断MVP与P是否一致。其次利用条件判据，在最优点为最佳匹配点的情况下跳出循环，在不一致的情况下先采取标准算法中的方式确定初始搜索点，然后按照编码单元块提前终止策略进行初始网格搜索。在最佳候选块距离大于5的情况下，进行条件判据。最后使用八边形-“十”字栅格搜索与精细搜索完成算法改进。由实验结果可知，该方法所得最优点与最佳匹配点相同的平均概率为71.51％，编码单元块有效命中概率的平均值超过97.83％，并且在基本不影响视频质量的情况下，平均节约了42.47％的运动估计搜索时间，体现了良好的改进效果。

作者简介：

朱鑫磊（1997-），男，硕士生.研究领域：视频编码，图像处理.

汪伟（1979-），男，博士，讲师.研究领域：医疗影像处理与分析，医用机器人.