一种基于宽钻石搜索的改进TZS算法

但鸿键，汪 伟

(上海理工大学 光电信息与计算机工程学院，上海 200093)

1 引 言

近年来，随着对短视频和视频直播中高清视频、超清视频需求量的迅速增长，视频信息已经成为数字化生活中不可或缺的一部分.然而，由于原始视频所具备的高分辨率和高帧频特性，使得其包含的数据量十分庞大，给数据存储和数据传输带来了巨大的压力.因而提高视频的编码性能和效率成为了该领域内的研究热点，而高效视频编码(High Efficiency Video Coding，HEVC)所具备的优秀性能，使得该编码标准得到了迅速的发展.

HEVC标准沿用了目前所广泛使用的H.264视频编码标准的结构框架，并在此编码框架基础上对H.264的各个环节都进行了不同程度的改进，使得总体编码效果得到大幅度的提升，在同等视频质量情况下降低了50%的码率.但是，编码效果提升的同时也带来了计算复杂度过高的问题[1-3].

在HEVC标准中，块匹配运动估计中的TZS(Test Zone Search)标准算法是目前运动估计算法中应用最广泛的方法之一，而TZS搜索算法的高计算复杂度在一定程度上影响了算法搜索效率，如何提升TZS的搜索效率是当前研究的热点之一.目前，对TZS算法搜索效率的提升主要是从以下几个方面来改进：提前终止策略、最佳搜索点的搜索方式、自适应调整搜索范围和栅格搜索模式.通过各个方面的改进，能够有效地减少TZS搜索算法的计算复杂度.

提前终止策略是一种有效减少寻找最佳匹配点搜索次数的方法.Purnachand等提出一种基于TZS算法的全局搜索提前终止策略，对当前块的空间相邻块和时间相邻块的代价值进行存储，并将其中最小的值作为终止的阈值，有效地减少了算法的搜索耗时[4]；针对运动剧烈程度不同的视频序列，余登超等利用统计学的概率来设置DS搜索的步长参考值，适当地跳过不必要的搜索，即通过选择不同的阈值来提前结束搜索[5].

此外，采用搜索效率更高的搜索方式也可有效地缩短算法运行时间.Li 等将TZS标准算法中的钻石搜索(Diamond Search，DS)和正方形搜索用六边形搜索来替代[6]；JEA等提出在初始网格搜索和精细搜索阶段，使用旋转五边形搜索(Rotating pentagon search，RPS)算法，使用更少的搜索点来寻找最佳匹配点[7]；Purnachand等在TZS算法的网格搜索阶段和精细搜索阶段使用步长逐渐变大的水平和垂直六边形搜索

1https：//vcgit.hhi.fraunhofer.de/jct-vc/HM/-/tree/HM-16.14

来代替钻石搜索，即采用的旋转六边形搜索模式也取得了较好的效果[8]，该搜索方式相比于DS搜索具有更高的搜索效率；Abdelrahman等先进行三次DS搜索，再采用半像素六边形搜索(Half-Pel Hexagon Search)最佳匹配点，保留了算法的搜索精度[9]；Nguyen 等提出用旋转宽钻石搜索算法代替TZS标准算法中的钻石搜索和正方形搜索，用可变步长采样搜索方式，从而有效减少搜索最佳匹配点的次数[10].

除上述两类方法外，自适应地减少搜索范围也是一种有效地减少TZS算法中搜索点数目的方法.Varma等提出在编码帧和参考帧中分别使用自适应外部和内部搜索范围缩减的算法，该算法根据空间相邻块的运动矢量差(Motion Vector Difference，MVD)和搜索中心的绝对差累加值(Sum of Absolute Difference，SAD)来自适应变化搜索范围[11]；Zhang等通过在预测精度内自适应地调整搜索范围，并利用运动矢量残差估计来达到提升编码效率的目的[12].

需要着重指出的是，栅格搜索是TZS算法中最耗时的步骤，提高栅格搜索效率是减少编码时间的重要环节.Goncalves等提出一种八边形-十字栅格模式(Octagonal-Axis Raster Pattern，OARP)的栅格搜索，根据运动矢量的分布规律调整栅格搜索范围，有效地提升了算法在栅格搜索中的搜索效率[13]；Nghia等将栅格搜索范围分成多个区域，按照顺序进行分区栅格搜索，当检测到匹配点时就退出栅格搜索的遍历过程，有效地减少栅格搜索总体的搜索点数量[14].

本文为降低搜索过程中的计算复杂度，缩短编码时间，在HM-16.141的TZS标准算法的基础上进行了如下创新：首先，在初始网格搜索阶段，创新性地引入了搜索效率更高的宽钻石搜索(Wide Diamond Search，WDS)代替DS搜索，从而能以更少的搜索次数搜索出最佳匹配候选点.其次，在栅格搜索阶段，通过分析全搜索过程中运动矢量的十字中心偏置分布的特点，提出OARP的栅格搜索模型，能减少近75%的栅格搜索点数，有效地缩短了运动估计过程中算法的搜索时间，提高了视频编码效率.实验证明，对TZS标准算法改进后，能提高运动估计的搜索效率，并保持搜索算法的规律性，使算法易于在硬件上实现.

2 TZS标准算法流程

2.1 起始搜索点确定

找到起始搜索点是运动估计的前提，此过程需要先计算当前预测块左侧、上侧、右上的运动矢量，再对零块运动矢量和当前块运动矢量进行比较，最后从所有的运动矢量中选择SAD值最小的点，并以该点作为TZS搜索算法下一步搜索的起始搜索点.

SAD的计算方法如式(1)所示：

(1)

其中(i，j)是搜索点在相邻两帧之间的位移矢量，fk和fk-1分别是当前帧和前一帧的灰度值，M和N是当前块的长和宽，m和n是像素坐标值.

2.2 初始网格搜索

在TZS标准搜索算法里，初始网格搜索是在特定的搜索范围内，使用搜索步长为2n(n=0，1，2，3…)的钻石或正方形的搜索模式进行块匹配搜索，从而获得最佳的候选块，具体如图1(a)和图1(b)所示.

图1 TZS标准算法初始网格搜索Fig.1 Initial grid search of TZS standard algorithm

在初始网格搜索中，搜索的最大点数如式(2)和式(3)所示：

NDS=8×floor(log2R)-4

(2)

NSq=8×floor(log2R)

(3)

其中，NDS是表示钻石搜索的搜索点数，NSq是表示正方形搜索的点数，floor是向下取整数，R表示搜索范围边长.

当搜索到最佳匹配块、搜索到范围的边界或者在三次搜索后仍不能找到率失真更小的点时停止初始网络搜索.然后，以最佳匹配块与当前块的距离来决定是否进行下一步的栅格搜索.

2.3 栅格搜索

在TZS标准搜索算法里，栅格搜索只会在最佳候选块的距离大于设定的栅格搜索参数值时才会进行的一种下采样全搜索，栅格搜索是用于运动矢量与起始位置的距离过远时的搜索方法.在HM-16.14中，栅格搜索在一个正方形的范围内，搜索方式如图2所示.

图2 TZS标准算法栅格搜索Fig.2 Raster search ofclassical TZS standard algorithm

一般来说，栅格搜索参数值设定为5，是搜索范围内的采样距离.若从初始网格搜索中获得的最佳距离为0时，则停止搜索；若该最佳距离小于栅格采样参数值时，则直接进行精细搜索；若该最佳距离大于栅格采样参数值时，就执行栅格扫描，扫描的步长为栅格采样参数值.

栅格搜索会在完整搜索范围内执行，搜索范围如式(4)所示，其所需的搜索点数如式(5)所示：

SR=N×N

(4)

(5)

其中，SR是栅格搜索范围，N是搜索范围的边长，Nraster是栅格搜索需要搜索的最大点数，floor是向下取整，R是栅格搜索的步长.

2.4 精细搜索

为了确保搜索得到的运动矢量为全局最优，需要对之前搜索所获得的最佳候选块进行星型或栅格精细搜索.

1)星型精细搜索在优化运动矢量的过程中，执行步长为2的钻石搜索或正方形搜索，直到搜索最佳运动矢量为1或者到搜索范围的边界时停止步长为2的钻石或正方形搜索.若最佳运动矢量为1时，进行两点搜索找出最佳匹配块；

2)栅格精细搜索执行以2为搜索步长的栅格搜索，直到运动矢量为1或者到搜索范围的边界时，停止步长为2 的栅格搜索.若最佳运动矢量为1时，采取两点搜索找出最佳匹配块.

精细搜索是最终确定最佳匹配点的关键步骤，由精细搜索得出的搜索点代表了当前帧中的运动物体在下一帧图片上的最佳匹配位置.

3 改进的TZS搜索算法

目前，在HM-16.14中使用的是TZS标准搜索算法，此算法与全搜索算法相比有着良好的运算速度，同时也保证了视频质量.本文对TZS标准算法的搜索策略和搜索模型作了进一步改进，提出了一种改进的TZS搜索算法，并于本小节对改进算法进行具体阐述.

本文提出的改进算法具体流程如图3所示.

图3 改进的TZS搜索流程图Fig.3 Flow chat of modified TZS search

3.1 起始搜索点确定

继续沿用TZS标准算法中的确定起始点的方法，先预测当前块的运动矢量，再从预测的运动矢量中选取SAD匹配标准下最小值的位置，最后以该位置作为下一步搜索的起始搜索点.

3.2 基于WDS的初始网格搜索

TZS标准算法比全搜索算法在运动估计时间和计算复杂度上有着显著的降低，然而在运动估计中仍然存在大量的耗时和计算复杂度.尤其在找到最佳匹配点之前，需要进行的搜索点数量还是有些庞大.

为进一步提高视频编码效率，本文引入了基于WDS的初始网格搜索策略，将前两次DS搜索过程中所需要遍历的搜索点数减小了一半，从而极大地减小了搜索算法的计算复杂度.

使用WDS快速搜索算法代替初始网格搜索算法中使用的钻石搜索算法，如图4(a)所示.

图4 WDS搜索示意图Fig.4 Search steps for WDS

1)在搜索范围内，先搜索起始搜索点距离为1的上下左右4个点；

2)先使用水平方向步长为1，垂直方向为水平方向步长两倍的WDS搜索模式进行块匹配搜索，然后在之后每一次搜索的步长均以2的次幂增长，直到搜索至范围边界或3次搜索后仍无法得到率失真更小的最佳匹配点时，结束网格搜索；

3)最后比较最佳搜索距离与栅格采样参数的大小，根据比较结果来判断是否进行栅格搜索.

在搜索匹配点后，检测该匹配点是否为最佳的匹配点.比较每次WDS搜索方法得到的最佳匹配候选点的率失真代价，逐步找到最佳匹配点.若得到的最佳候选点与起始点的距离为1或2时，适当地比较该候选点周围的几个点来检测该点是否是最佳匹配点.

最佳匹配点的具体检测示例如图4(b)所示.

·若1.1为最佳候选点，将此点与3.8、3.11、3.12比较；

·若1.2为最佳候选点，将此点与3.4、3.5、3.6、3.7比较；

·若1.3为最佳候选点，将此点与3.9、3.10、3.13比较；

·若1.4为最佳候选点，将此点与3.14、3.15、3.16、3.17比较；

·若2.1为最佳候选点，将此点与3.1、3.2、3.3比较；

·若2.2为最佳候选点，将此点与3.18、3.19、3.20比较.

例如1.1为最佳候选点，比较1.1和3.8、3.11、3.12的左侧、上侧、右上的块的运动矢量和零块运动矢量的SAD值，将SAD值最小的那个点作为下次搜索的起点.当搜索3轮之后还没找出比SAD值更小的点，停止网格搜索过程.

3.3 基于OARP的栅格搜索

由于栅格搜索需要进行全搜索模式下的子采样搜索，且覆盖整个搜索范围，这是整个搜索过程中最复杂的步骤，该步骤所耗费的平均搜索时间在全部TZS搜索过程中占用约80%的比例.另外，由研究表明[15]，运动矢量的分布具有中心

2https：//hevc.hhi.fraunhofer.de/

十字偏置的特性，如图5(a)所示，即在初始搜索点周围、水平和垂直方向上分布了绝大多数的运动矢量.然后对TZS搜索算法的复杂度进行分析，并于尺寸不同的预测单元中分析整个算法在各个步骤中的耗时时长.

图5(a)是3个具有代表性的高分辨率YUV视频序列的运动矢量平均分布图，即BQTerrace、YachtRide和Cactuse序列.像素灰度值代表不同的运动矢量分布概率，在搜索范围中心的附近区域和水平垂直方向上的区域的运动矢量分布最为密集.随着与搜索中心的距离增加，运动矢量分布概率在逐渐减小.

图5 改进的TZS栅格搜索Fig.5 Raster search of modified TZS

HM-16.14中栅格搜索是一种步长为5的下采样全搜索，使得PU块的搜索在一个完整搜索过程中占用50%到90%的搜索时间.由图中可知，运动矢量大多分布在搜索点的周围、水平和垂直方向，而在距搜索点较远的非水平垂直方向几乎没有运动矢量分布.因此，可以适当地移除这些距离较远的非水平垂直区域进行栅格搜索，采用更小更高效的区域作为搜索范围.

根据运动矢量分布特性，采用OARP搜索模板来进行TZS算法中耗时最多的栅格搜索，缩小栅格搜索的范围，确定最佳的匹配块的分布情况.

虽然OARP搜索模板使用的搜索范围约为原搜索范围的25%，却覆盖了绝大多数的最佳匹配块.OARP搜索模板显著降低了TZS算法的复杂度，大概率地覆盖了最佳匹配块所在区域，保证了运动估计编码的效率.

采用OARP搜索模板保留了栅格搜索的规律性，不需要用到复杂的算法来自适应调节最佳匹配块的位置范围，使得算法更易于在硬件平台上实现.

OARP搜索模板的形状如图5(b)所示：

1)OARP搜索模板选取原搜索范围的正中央的25%的区域作为搜索范围；

2)在第一步得到的范围基础上，去掉该正方形区域内的左上、左下、右上、右下的4个角落区域；

3)在第二步的范围基础上加上水平和垂直的区域作为最终的搜索范围.

3.4 精细搜索

经过WDS网格搜索和OARP栅格搜索后，沿用TZS标准算法中的精细搜索方法，采用星型/栅格精细搜索找出最佳匹配候选点，作为最终确定的最佳匹配点.

4 实验结果与分析

4.1 实验设定

4.1.1 测试数据库

为了验证本文算法有效性，在参考软件HM-16.14下实现该算法.由于要验证本文提出的算法的编码性能，故测试了5类HEVC标准的测试序列，序列均为YUV格式.

5类序列分别为A类(2560×1080)，B 类(1920×720)，C 类(832×480)，D 类(416×240)以及E类(1280×720)，A类、B类、D类和E类包含两个不同运动激烈程度的序列，C类中包含了两个运动程度类似的序列，总共10个序列.

4.1.2 算法评价指标

为评定使用算法的优劣，本文采取从算法的搜索时间和视频质量两个方面来进行分析和评价，分别对TZS标准搜索算法、基于OARP的TZS算法[15]和本文提出的改进TZS搜索算法进行了实验结果对比.

实验中分别收集了编码时间、Bitrate和PSNR(peak signal-to-noise rate)等参数，并基于HM-16.14的编码器上的编码时间变化ΔT、BDBR(Bjøntegaard delta bit rate)、BDPSNR(Bjøntegaard delta peak signal-to-noise rate)2等数据来分析编码效果[16].

1)本文基于编码时间来比较算法的编码速度，其编码时间变化ΔT计算方法如式(6)、式(7)所示：

(6)

(7)

其中ΔTproposed和ΔTOARP分别为本文算法、基于OARP的TZS算法与HM-16.14中TZS标准算法的编码时间变化.

2)BDBR表示相同PSNR条件下码率的变化百分比，BDPSNR表示相同码率条件下PSNR的变化量，两者参数都是用于视频编码质量和算法编码性能的比对.

4.1.3 实验环境及参数设定

实验中所使用的硬件平台为酷睿I5-4200H处理器、2.8 GHz主频和8GB的内存.对应的软件配置为Windows1064位操作系统、yuvplayer视频序列播放器以及Elecard HEVC Anlyzer编码视频检测工具.

使用的测试序列A类、B类、C类、E类序列的测试帧数为100帧，D类的BQSquare使用600帧，BlowingBubbles使用500帧.

HM-16.14中配置参数设置如下：QP的值为37、32、27、22，其它配置参数保留默认值(最大CU尺寸为64×64，最大划分深度为4).

4.2 实验结果

为了验证本文算法的效果，在上述的实验环境中进行4组不同QP值的TZS标准搜索、基于OARP的TZS搜索[13]和本文的改进搜索，4组不同QP值的实验结果的参数平均值如表1所示，PSNR为YUV视频序列的峰值信噪比，Bitrate为编码的码率，T为TZS搜索的时间.

表1 不同TZS算法实验结果(QP=22，27，32，37)Table 1 Experimental results of different TZS algorithms(QP=22，27，32，37)

以此实验结果对比基于OARP的TZS算法和本文算法，表2中是4组不同QP值的基于OARP的TZS算法、本文算法和TZS标准算法的平均实验对比结果，结果表明本文算法比TZS标准算法平均减少约26.59%的编码耗时，在Tennis 和PeopleOnStreet运动复杂的高分辨率序列中甚至减少40%以上耗时，BDBR平均减少了0.023%，BDPSNR平均增长了0.0149dB.与基于OARP的TZS算法[13]相比，本文算法也显著缩短了编码耗时，并且BDBR和BDPSNR的平均变化量更小，以更少的Bitrate表现出相同的PSNR，体现出了更加优异的视频编码效果.

表2 不同TZS算法平均对比结果(QP=22，27，32，37)Table 2 Averageresults comparison of different TZS algorithms(QP=22，27，32，37)

图6是表示本文算法、基于OARP的TZS算法和TZS标准算法的编码时间的柱状图.从图6中可以清楚的看出，本文算法在搜索时间上的耗时要低于TZS标准搜索算法和基于OARP改进的TZS的算法，展现出了本文算法良好的编码速度.

图6 3种不同算法搜索算法的搜索时间对比柱状图Fig.6 Search time comparison bar chart of 3 different search algorithms

图7为3种搜索算法的RD曲线图.由于10个序列中各算法的RD曲线都十分接近，因此，从中取4组典型曲线作为代表.由RD曲线可以看出，本文提出的改进TZS搜索算法与其它两种算法，在同等码率的情况下，PSNR几乎保持不变.图7说明了本文算法能够在明显缩短编码时间的情况下仍保持了良好的视频质量.

图7 4种不同序列的RD曲线Fig.7 RD of curve of 4 different sequences

4.3 实验分析

通过分析实验结果，本文提出改进的TZS搜索算法可有效缩短TZS标准算法在同等客观视频质量下的搜索耗时.与TZS标准算法、基于OARP的TZS算法在PSNR相同情况下，所需要的Bitrate有着少量的减少，但保持了几乎相同的视频质量.本文算法之所以能够缩短搜索耗时并保持视频质量基本不受影响的主要原因在于：

1)引入了WDS搜索，改进了搜索方式，减少了初始网格搜索最佳点的次数，相比于DS搜索在相同PSNR时所需的Bitrate更少，在相同Bitrate时得到的PSNR更高.

2)OARP搜索模板的使用，减少了近75%的低效搜索区域，使得搜索的效率得到明显的提高.

3)对最佳候选点精细搜索，确定全局最佳匹配点，为编码序列的视频质量提供了有效保障.

但是本文算法也存在缺点，无法搜索到光栅搜索中某些运动复杂且不规则的物体在OARP模式外有极低概率存在的最佳匹配点，会将局部最佳匹配点当成全局最佳匹配点，造成微小的视频质量损失.

5 结束语

针对HEVC帧间预测的运动估计中的高复杂度和高耗时问题，基于HM-16.14中的TZS标准算法搜索结构，本文提出了一种改进TZS搜索算法.一方面，在初始网格搜索中，用WDS搜索代替DS搜索；另一方面，在栅格搜索中，用OARP的搜索模板进行下采样全搜索缩小了光栅搜索的范围，减少了搜索过程中的搜索点数，提高了视频的编码效率.实验结果表明，本文提出的改进TZS搜索算法提高了搜索效率，较好的缩短了编码耗时；同时，BDPSNR和BDBR没有明显变化，视频质量保持良好.总之，该算法对视频编码有着一定的实际应用价值.