HEVC的异构钻石模板快速搜索算法

唐浩漾，程颖涛，郭 娜，孙梓巍，王 婧

西安邮电大学 自动化学院，西安 710121

1 引言

HEVC（High Efficiency Video Coding）是新一代的视频编码标准[1]，在同等视频质量下减少50%的码率[2]。其中帧间预测的运动估计在HEVC编码过程中大约占据了一半的编码时间和运算复杂度[3]。对于运动估计精度影响最大的主要有块匹配准则[4]和搜索策略，为此学者们对其进行了大量的研究与优化[5-11]。

HEVC参考软件HM14.0中运动估计采用TZSearch算法，众多学者对此算法进行了改进和优化。文献[12]将光栅扫描算法模型使用直线钻石、小钻石或者水平钻石模板替换。文献[13]采用半径不断扩大的水平垂直六边形和旋转六边形代替钻石搜索方案，并设置阈值提前终止搜索。文献[14]采用旋转六边形模板用于在初始网格阶段和细化阶段替换钻石图案来找到全局最小值。但是文献[13-14]两种方案在最优点距离起始点较远的情况下，最优点的位置精度会下降。尽管这些算法对于减少HEVC编码复杂度均有一定的效果，但是以上算法往往以速率为第一目标，忽略或者很少考虑整体编码性能。

本文通过运动矢量的分布特性并结合TZSearch算法搜索模板中存在的问题，提出基于异构钻石模板的TZSearch快速搜索算法，在其中加入垂直水平六边形模板，使其更适合于水平和垂直纹理的图像，缩短运动估计模块的耗时，提高了编码的整体效率。

2 TZSearch搜索算法

TZSearch搜索算法步骤如下：

（1）运动矢量预测：从中值预测运动矢量、当前PU的左、上、右上运动矢量、零点运动矢量中选择SAD值最小的点的作为TZSearch搜索的起始点。

（2）初始网格搜索：在搜索窗内进行2的次幂增长的8点钻石或者正方形搜索（步长依次为2、4、8……64）。每次搜索之后都将SAD的最小值的搜索点作为下一步搜索的中心点，SAD最小的搜索点距离中心的距离即最佳步长。此步中需要确定搜索点总数如式（1），其中S是搜索窗的大小，P为模板中每次需要搜索的点数（六边形时P=6，钻石模板时P=8），floor为向下取整函数。

（3）栅格搜索：栅格搜索是对搜索窗进行一种下采样式全搜索。HM14.0设置的栅格扫描的单位为5，该参数作为搜索窗的采样参数。当之前搜索得到的最佳步长大于采样参数时进行栅格扫描，最佳步长被赋值为采样参数。如式（2），在栅格扫描时每一行/列需要搜索的点是ceil(S/R)，其中R是采样参数的值，n2的最大值为此步需要搜索的点数。如果条件不满足，将跳过此步。

（4）栅格/星型精细搜索：修正过程是为了确保最佳运动矢量的全局最优性，即当之前步骤得到的最佳步长大于0时用于对运动矢量的修正。一般情况下，只有一种修正模式（栅格修正或星型修正）是开启状态。星形修正过程中使用步长为2的次幂增长的8点钻石搜索或8点正方形进行搜索，直到最佳步长为1。栅格修正是通过对之前步骤得到的最佳步长作以2为单位的下采样操作，并以此作为步长进行钻石或正方形搜索，直到最佳步长为1。无论选择哪种修正方式，当最佳步长为1的时候都需要进行两点搜索。

HM14.0中的TZSearch搜索算法与FS算法相比，TZSearch算法提供了良好的率失真性能，编码时间提高了60%以上。但是TZSearch仍然存在不足之处：在搜索模板上，TZSearch没有根据视频存在的固有特性进行有区别的搜索，以2次幂为步长依次扩大的钻石搜索执行了8次，增加编码复杂度，但对于运动矢量水平垂直方向分布概率高于其他方向这种情况并未考虑在内，在编码时间和编码效率仍可以提高。

3 基于异构钻石模板的快速搜索算法

3.1 运动矢量分布规律

运动矢量的分布规律是匹配图像运动特征模板的重要因素。运动矢量具有以下分布特性：

（1）运动矢量具有中心偏移性。如图1所示，采用全搜索算法对 Akiyo、Football、Table Tennis和 Flower Garden等不同特征序列的运动矢量概率分布进行实验统计。图1中原点处为最优点的概率最大，约为67%，最优点处于1×1区域的概率大约为12%，最优点处于2×2区域中的概率大约为5%。

图1 运动矢量的分布情况

（2）运动矢量具有十字中心偏置特性。文献[15-16]研究表明运动矢量出现在水平和垂直方向的概率高于其他方向。

3.2 异构钻石模板

根据运动矢量的分布规律，本文采用一种新的异构钻石搜索模板，如图2所示。此模板在水平和垂直方向尽可能搜索更多的点来提高搜索精度。整个搜索过程分两个阶段，第一阶段包括由17点组成的异构钻石搜索，第二阶段按照第一阶段的搜索结果分别按照由7点组成的垂直水平六边形或者大菱形搜索。

图2 异构钻石模板

异构钻石算法搜索过程如下：

第一阶段：异构钻石搜索，以当前点为中心并搜索包括中心点在内的17点，确定匹配标准SAD的最小值发生位置。然后转到阶段二。

第二阶段：以异构钻石搜索后的最小匹配标准点为中心，分别按照六边形或者大菱形进行搜索。最小匹配标准点即SAD最小的点分为A、B、C。根据最佳点所属的类型，可以分为以下三类：

（1）如果最佳点属于A类，也就是位于中心点，停止整个搜索过程。

（2）当最佳匹配点出现在B类，此时最佳点所处的方向决定了后序搜索采取的模板。当处于垂直方向时执行半径广和效率高的垂直六边形模板（如图3（a）），不断将搜索中心更新为当前最佳匹配点，直到最佳匹配点位于中心时，在执行一次步长为1的正方形搜索进行精细定位，确定最终的最佳匹配点。同样，若位于水平方向（与中心点水平）采用水平六边形搜索模板（如图3（b）），直到最佳点位于中心位置时，执行一次正方形搜索进行精细定位。

（3）当最佳匹配点归类为C类的时候，选用大钻石模板，不断更新搜索中心的位置，直到最佳匹配点不变。最后进行一次小菱形搜索进行精细定位，选择确立最佳的搜索点位置。

图3 垂直水平六边形模板

3.3 算法流程及步骤

算法的具体步骤如图4。

图4 基于异构钻石的TZSearch搜索算法

（1）从相邻预测运动矢量和零运动矢量中确定起始搜索点。

（2）选取步骤（1）中求的最优点作为搜索起点，进行异构钻石模板搜索，得到当前最优点。若当前最优点属于搜索模板中的A类时，结束整个搜索过程，当前最优点为全局最优点，得到最优运动矢量。若当前最优点属于B类，跳转至步骤（3）。若当前最优点属于C类，跳转至步骤（4）。

（3）若当前最优点位于水平方向（与中心点平行），跳转执行步骤（5）。若当前最优点位于垂直方向（与中心点垂直），跳转执行步骤（6）。

（4）用当前最优点当作搜索中心执行大钻石搜索，并且不断的将搜索中心更新为当前最优匹配点，直到最优点不再变化，执行一次小钻石搜索进行精细定位，得到最优点，确定最终的运动矢量。

（5）用当前最优点当作搜索中心执行半径广和效率高的水平六边形模板，并且不断地将搜索中心更新为当前最优匹配点，直到最佳匹配点位于六边形中心。跳转到步骤（7）。

（6）以当前最优点作为搜索中心执行半径广和效率高的垂直六边形模板，并且不断地将搜索中心更新为当前最优匹配点，直到最佳匹配点位于垂直六边形中心。跳转到步骤（7）。

（7）以当前最优点为搜索中心，执行步长为1的正方形搜索进行精细定位，确定最优点位置，得到运动矢量。

4 实验结果与分析

为了验证本文算法的有效性，在HEVC参考软件HM14.0上实现本文算法。在Intel酷睿i5处理器，8 GB的内存，Windows 64位的操作系统的硬件条件下进行实验，采用的编码帧结构是IPPPP，搜索区域的窗口设置为64×64，QP 从22变化到37（22、27、32和37）。测试序列为5类HEVC标准测试序列A类（2 560×1 080），B类（1 920×720），C类（832×480），D类（416×240）以及E类（1 280×720），测试帧数为100帧。

采用同等客观质量下的码率BDBR（Bjøntegaard Delta Bit Rate）、同等码率下的峰值信噪比BDPSNR（Bjøntegaard Delta Peak Signal-to-Noise Rate）[17]和编码时间变化率ΔTime作为快速算法的评价指标。BDBR和BDPSNR分别表示相同PSNR条件下码率的变化百分比和相同码率条件下PSNR的变化量。ΔTime计算方法如下：

其中HM和proposed分别代表HM14.0和本文算法。图5给出序列RaceHorses和BasketballPass使用HM14.0的搜索策略每帧需要搜索的平均点数分别大致在180和120周围波动，而使用本文提出的搜索模板搜索平均每帧需要搜索的点数分别在40和45左右波动，说明采用本文的搜索策略可使每帧搜索的点数进一步减少，继而减少编码时间。从表1可以看出本文算法总的编码时间减少了大约26.30%，最大可减少33.05%，而BDBR仅增加1.172%，BDPSNR也只降低了0.051 dB。

图5 QP=32时BasketBallPass每帧所需搜索的点数和RaceHorses每帧所需搜索的点数

表1 本文算法与HM14.0算法的对比结果

图6给出序列（BasketBallPass和RaceHorses）的RD曲线，从曲线图中可以看出所提出的TZSearch快速搜索算法与原始TZSearch搜索算法结果相差不大，保持了原有的编码性能。

产生此实验结果原因是本文只进行一次异构钻石搜索，改进了最耗时的搜索模块，其次当异构钻石搜索到最佳点位于中心位置，直接退出整个搜索过程，设置了提前退出搜索的条件。

5 结束语

本文针对HEVC帧间预测的运动估计高耗时问题，提出了一种快速的搜索算法。首先根据异构钻石搜索后最佳点所在位置的不同采取不同的搜索模板改进了TZSearch中的钻石搜索，其次去掉了TZSearch中最耗时的栅格搜索模块。实验结果表明，本文的算法与HM14.0的算法比较，编码时间最大可减少33.05%，同时BDPSNR仅下降了0.051 dB，具有一定的实用价值。

图6 BasketBallPass和RaceHorses序列在不同QP（22，27，32，37）下的RD曲线