李芍，陈建文，何芸

(清华大学 电子工程系 清华信息科学与技术国家实验室，北京 100084)

2011年1 月，国际标准化组织ISO/IEC JTC1 sc29 wg11，即MPEG工作组在韩国Daegu会议上发布了一个新的工作项目.Type-1 licensing video coding.与以往的视频编码标准不同之处为，编码器不但要有高的编码效率，而且每一项技术和每一处标志都要符合 MPEG Type-1 licensing［1］要求.这项计划的结果将为网络视频通信带来巨大的自由度而被广泛应用.所以在MPEG 2011年3月日内瓦会议上将 Type-1 video coding命名为“网络视频编码”［2］.

快速运动搜索算法是视频编码器中一种有效的简化算法，在视频编码的帧间预测中，编码器需要在参考帧中找到具有最小MCOST(motion cost)值的块.如果采用全搜索算法，以H.264/AVC参考软件JM(JVT Model)为例，大约需要占用60% ～80%的编码时间［3］.早期的快速运动搜索算法包括三步搜索法［4］、六边形搜索法［5］等，这些算法的实现简单，但会带来较大的编码性能下降.UMHexagonS［3，6-9］算法是一个高效的运动搜索方法，相比于全搜索算法，该算法能够节省90%以上的时间，同时编码器的率失真性能(R-D性能)也能得到很好的保持.UMHexagonS算法已经被JVT(joint video team)标准组织采纳并集成在H.264/AVC的参考软件JM中，近年来针对UMHexagonS算法的研究给出了多种改进型方法.

针对Type-1平台的特征，本文提出了一种改进的UMHexagonS整象素快速搜索算法，本算法充分利用了运动矢量和MCOST在时空域上的相关性，改进了UMHexagonS搜索的提前截止阈值，从而提高了原算法在Type-1平台上的编码效率.

1 UMHexagonS整象素搜索算法简介

UMHexagonS的整象素搜索过程如图1所示.

图1 UMHexagonS算法流程Fig.1 Flow chart of the UMHexagonS

1.1 搜索起始预测

UMHexagonS算法的第1部分为确定搜索的起始运动矢量，包括空域预测和时域预测，空域预测包括中值预测和上层预测;时域预测包括相邻参考帧运动矢量预测和参考帧共同位置块的运动矢量预测，此外，还包括零运动矢量.在不发生提前截止的条件下，这一步中具有最小MCOST的运动矢量将作为下一步的搜索中心点.对于一个N×M大小的块来说，MCOST的计算公式如下:

式中:P(i，j，t)和 P(x+i，y+j，t-r)分别代表当前帧中坐标为i、j的象素值和参考帧中坐标为x+i、y+j的象素值，(x，y)代表运动矢量，λBits代表编码运动矢量带来的额外的代价.

1.2 主模型搜索

主模型搜索主要包含3个部分:非对称十字搜索，5×5正方形象素区域搜索和多尺度六边形搜索.搜索范围确定以后，这3种搜索模型需要搜索的象素点的个数和相对位置将被固定，搜索过程中的各个象素间无前后依赖关系，这种特性适合并行计算.在多尺度六边形搜索之后，如果不满足提前截止条件，还要进行局部优化搜索，例如六边形和十字型搜索.以16搜索区域为例，主模型搜索的象素位置如图2所示.

图2 UMHexagonS主模型搜索Fig.2 The main searching process of the UMHexagonS

1.3 提前截止算法

UMHexagonS包含2类提前截止条件，第1类跳转至局部优化搜索，第2类则结束搜索过程.第1类提前截止的阈值由当前块大小、当前量化步长、量化系数QP以及相邻块的MCOST值确定［3］:

第2类提前截止条件应用于搜索算法的第1步和最后一步，其阈值的计算［8-9］如下:

式中:QPfactor与Scalefactor分别与编码当前视频的量化系数以及当前视频的尺寸有关，文献［8-9］中指出:在使用较大的量化系数编码时应使用较小的QPfactor，编码较大尺寸视频序列时应使用较大的Scalefactor.

2 UMHexagonS在Type-1平台的分析

由于UMHexagonS在H.264/AVC标准算法中具有良好的RD性能、较快的搜索速度和优秀的并行性特征，本文尝试将UMHexagonS算法的整象素搜索部分移植到Type-1平台.

2.1 Type-1平台配置介绍

如前所述，在Type-1 Licensing的约束下，Type-1平台使用的编码工具较为简单，表1［10］给出了该平台与H.264/AVC的主要技术对比.由于该平台的亚象素仅有1/2精度，因此本文仅探讨整象素搜索部分.测试的主要配置如表2所示，这是目前Type-1平台中所使用的通用配置.实验的测试序列为正在制订中的国际标准ISO/IEC JTC1 sc29 wg11和ITUT sg16 Q.6联合工作组HEVC(high efficiency video coding)［11］的通用测试序列.

表1 H.264/AVC与Type-1帧间技术对比Table 1 Inter frame coding between H.264/AVC and Type-1

表2 Type-1平台通用测试配置Table 2 Brief test configuration in Type-1 platform

2.2 Type-1平台UMHexagonS性能测试

实验1中，由于Type-1平台只有1个参考帧，因此原UMHexagonS中的时域预测被移除，中值预测则被替换成Type-1平台中所对应的预测值，预测结构使用IPPP，其余保持不变.

表3中为2个序列在4个不同QP点测试结果的平均值，使用 BD-Rate和 BD-PSNR［12］比较 UMHexagonS算法与全搜索算法的结果，表中BD-Rate的正值说明UMHexagonS相对于全搜索消耗了更多的比特数，BD-PSNR的负值说明UMHexagonS相对于全搜索有客观性能的下降.这里的衡量标准BDRate和BD-PSNR具有“或”的关系.RaceHorse序列包含较剧烈和较不规则的运动，而Kimono1则包含有较多模糊的纹理.

表3 原始的UMHexagonS在Type-1平台的性能Table 3 The Type-1 performance of original UMHexagonS in Type-1

一般来说，用于视频编码标准制定的快速运动搜索算法在所有测试序列上允许的平均BD-PSNR下降不能超过0.05dB，单个序列不能超过0.1 dB，这样才能使编码器平台中的其他技术不会受到快速运动搜索的影响.在实验1中，导致性能下降的主要问题包括2个:1)提前截止的阈值不合适，2)起始搜索点数不足，这里给出Kimono 1和RaceHorse序列的RD曲线(见图3、4).

图3 RaceHorse序列搜索性能Fig.3 The Type-1 performance of UMHexagonS in RaceHorse

可以看出，对于RaceHorse序列在不同的码率下性能损失相近，这对应于搜索起始位置过少而导致搜索算法未能找到最优的搜索位置;对于Kimono 1序列而言，其高码率端的性能损失大于低码率端，这对应于提前截止条件的缺陷，因为在低码率端，提前截止的阈值较小，因此算法搜索的点数更多.

图4 Kimono1序列搜索性能Fig.4 The Type-1 performance of UMHexagonS in Kimono 1

为了验证提前截止阈值的论断，在实验2中采用与实验1相同的序列和配置，但是取消了UMHexagonS的第2类提前截止算法.测试结果见表4，可以看出，对于Kimono1序列而言，其平均性能已经优于全搜索算法，但是对于RaceHorse序列来说，性能损失仍然较大.

表4 无第2类提前截止的UMHexagonS算法性能Table 4 The Type-1 performance of UMHexagonS without early termination Type-2

3 UMHexagonS算法的改进

基于前面的分析，本文的改进包括2个方面:1)增加搜索的起始点以提高预测运动矢量的准确性;2)改变提前截止算法，使得阈值的取值能够更加的适应序列的特性.

3.1 起始搜索点的确定

在文献［13］中，搜索的起始点利用了相邻块之间的相关性.基于类似的思想，本文提出了一种涵盖各个方向的运动矢量预测方式，分别对应于16×16、8×8以及4×4大小的块.

3.1.1 16×16 块的预测点位置

16×16块的空域预测运动矢量包括左边、上边和右上3种;时域预测运动矢量来自前一个使用帧间编码的参考帧，共4个.如图5所示.

A～C块和当前块具有空间相邻的位置关系，D～G块的实际位置在参考帧中，它们在参考帧中的坐标和当前块4个角在当前帧上的坐标相同，这样的设计可以使得当前块的运动方向总会一定程度上反应在A～G的某一个参考块中.当参考帧与当前帧之间的距离可变时(例如IBBP结构)，还要使用运动矢量缩放.缩放采用线性运动模型(如图6所示)，即假设当前帧和参考帧具有共同位置的块属于同一个物体，设参考帧中块的运动矢量为Mref，参考帧序号为t+n，参考帧编码使用的参考帧序号为t，当前帧的序号为t+n+m，则当前块的运动矢量M由下式确定:

图5 16×16块运动矢量预测Fig.5 Motion vector prediction of 16 ×16 blocks

图6 时域运动矢量缩放Fig.6 Temporal motion vector scaling

3.1.2 8×8 块的预测点位置

8×8块的空域运动矢量预测包括左边块、上边块、右上方块和左下方块的运动矢量;而时域的预测则采用了位于当前8×8块外部的4个块，如图7所示.

图7 8×8块运动矢量预测Fig.7 Motion vector prediction of 8 ×8 blocks

3.1.3 4 ×4 块的预测点位置

在Type-1平台中的帧间预测中，大多数的块尺寸为16×16和8×8，4×4块实际使用的频率非常低，如表5给出的Type-1平台编码序列RaceHorces得到的块大小分布.UMHexagonS中上层预测的准确性较高，已经能够很好地预测较小尺寸块的运动矢量［3］，因此，不采用4×4块的时域预测而仅添加4个空域运动矢量预测，4×4块的空域预测方式与8×8块一致.可见，在最不好情况下，改进的UMHexagonS算法比原算法增加了大约4～8个搜索点.

表5 编码块大小分布Table 5 Block size distribution

3.2 第2类提前截止阈值修正

在UMHexagonS算法中，第2类提前截止的阈值计算见式(3)，其中的QPfactor与Scalefactor计算方法如下:

式中:image(QP)表示当前编码序列的量化系数QP，Img_width表示当前视频的象素宽度，Min_width=176，a、b为预定义的常数.当序列尺寸为高清时，Scalefacter的取值在3.9左右，此时如果QPfacter较小，提前截止的阈值将达到2倍的Thd_Base左右.这对于具有较大平坦区域的序列来说较为合适［8-9］，但是对于纹理细节较多的序列(Kimono 1)则不然.在提前截止算法1中，左边和上边块的MCOST值被用于计算第1类阈值.在本文中，也同样采用相邻块MCOST的估计方法.定义搜索结束后16×16块与其左边16×16块，上边16×16块和参考帧内共同位置的16×16块的MCOST相关系数分别为 ρL、ρT和 ρC:

式中:Bx，y，t代表当前帧 t中坐标为(x，y)的 16 × 16大小块的 MCOST 值，Bx，y，t'代表参考帧 t'中坐标为(x，y)的16×16大小块 MCOST 值，代表当前帧和参考帧中所有16×16大小块MCOST值的方差.此外，这里的均值E(·)不是统计均值，而是算数均值.考虑到某些块的左边、上边块不存在，因此这里的计算和概率意义下的相关系数不能完全等价.对IPPP预测结构和IBBP预测结构中的P帧进行上述计算，采用前述实验2的平台，并加入3.1节关于起始位置的改进，得到的结果见表6.

表6 MCOST相关系数(IPPP/IBBP)Table 6 Correlation coefficient of MCOST(IPPP/IBBP)

可见，MCOST的空域相关性更为鲁棒一些，受到序列特性和预测结构的影响不大;而其时域相关性仅在IPPP预测结构下的某些特定序列上较大，在IBBP预测结构下则较小.因此，采用简单的空域MCOST对第2类提前截止的阈值进行修正:

式中:Spatial_Thd的值等于当前块的左边块MCOST值与上边块MCOST值中的较小者，最终的Threshold值为Spatial_Thd与第2类提前截止阈值Thd的平均.采取简单修正的目的是为了尽量避免复杂修正算法所带来的搜索时间增加，例如复杂度较高的相关性渐进拟合算法会提高搜索时间.

4 实验结果

在实验中，采取前述的实验条件配置、改进的搜索算法与Type-1平台已有的全搜索算法以及原始的UMHexagonS搜索算法进行比较，结果如表7.

表7 改进的UMHexagonS与全搜索算法的性能对比Table 7 Modified UMHexagonS v.s.full search

表7中的平均节省时间的计算方式以下式计算:

式中:Tfull和Tfast分别代表全搜索占用的时间和改进后的UMHexagonS搜索算法所占用的时间.可以看出，相对于全搜索算法，节省了97% ～98%的时间，平均PSNR降低控制在0.032dB之内，最坏的情况是IBBP结构下的RaceHorse序列编码，性能下降达到了0.109dB.表8给出了改进后的UMHexagonS搜索算法和原始的UMHexagonS搜索算法在Type-1平台上的性能对比，采用IPPP预测结构.

表8 改进的UMHexagonS与原始的UMHexagonS性能对比Table 8 Modified UMHexagonS v.s.original UMHexagonS

表8中的平均节省时间的计算方式如下:

式中:Torg和Tfast分别代表原始的UMHexagonS算法所占用的时间和改进后的UMHexagonS所占用的时间.可以看出，尽管增加了起始搜索点及修改了第2类提前截止阈值计算，但是几乎在所有的测试序列中，改进后的算法占用的时间都要少于原算法的时间.其原因包括2个方面:1)虽然增加了起始搜索点，但同时提高了预测的准确性，这将导致更多的提前截止出现;2)改进的第2类阈值计算虽然会在某些时候降低最终的提前截止阈值(Kimono 1)，但在其他其他其他情况下，这将导致最终的提前截止阈值增加，从而使得更多的块搜索可以提前截止.

5 结束语

本文提出了一种改进的UMHexagonS算法并在Type-1平台上实现.该算法通过大量使用空域和时域的运动矢量预测，在参考帧数目受限和编码模式受限的条件下提高了原有快速算法的搜索精度;同时，采用低复杂度自适应MCOST预测方法更好的估计了算法的提前截止阈值.因此，充分地利用时空域中的运动矢量和MCOST信息能够明显的改善快速运动搜索算法的搜索精度，同时还能够一定程度上减少搜索时间，在视频编码器中具有很好的实用价值.本算法最近已经集成在最新版本的Type-1编码器平台中.在实验结果中，最大的 BD-PSNR有0.1 dB多的下降，进一步的实验结果表明这种现象来源于主模型搜索，由于RaceHorse序列中的物体运动不规则，时空域的预测不准确，主模型搜索由于形状相对固定，最优预测点会无法索引到，故而编码效率下降.因此，对于UMHexagonS算法的进一步研究将继续进行.

［1］ITU-T，ITU-R，ISO/IEC.ITU-T/ITU-R/ISO/IEC common patent policy［Z］.Geneva:ITU and ISO/IEC，2007.

［2］MPEG.Requirements for Internet Video Coding/ISO/IEC JTC1 sc29 wg11 w12045［Z］.Geneva，2011.

［3］CHEN Zhibo，ZHOU Peng，HE Yun，CHEN Yidong.Fast integer pel and fractional pel motion estimation for JVT/JVT-F017［Z］.Joint Video Team(JVT)of ISO/IEC sc29 MPEG ＆ ITU-T SG16 VCEG.Awaji，2002.

［4］KOGA T，IINUMA K，HIRANO A，LIJIANG Y.Motion compensated inter frame coding for video conferencing［C］//Proceedings of National Telecommunications Conference.New Orleans，1981:G5.3.1-G5.3.5.

［5］ZHU Ce，LIN Xiao，CHAU Lap Pui.Hexagon-based search pattern for fast block motion estimation［J］.IEEE Transactions on Circuits and Systems for Video Technology，2002，12(5):349-355.

［6］CHEN Zhibo，ZHOU Peng，HE Yun，et al.Fast motion estimation for JVT/JVT-G016［Z］.Joint Video Team(JVT)of ISO/IEC sc29 MPEG ＆ ITU-T SG16 VCEG.Pattaya，2003.

［7］CHEN Zhibo，XU Jianfeng，HE Yun，et al.Fast integerpel and fractional-pal motion estimation for H.264/AVC［J］.Journal of Visual Communication and Image Representation，2006，17(2):264-290.

［8］XU Xiaozhong，HE Yun.Modification of UMHexagonS fast ME/JVT-R085［Z］.Joint Video Team(JVT)of ISO/IEC sc29 MPEG ＆ ITU-T SG16 VCEG.Bangkok，2006.

［9］XU Xiaozhong，HE Yun.Improvements on fast motion estimation strategy for H.264/AVC［J］.IEEE Transactions on Circuits and Systems for Video Technology，2008，18(3):285-293.

［10］CHEN Jianwen，RONG Yaocheng，XU Feng，et al.Potential option-1 software Platform［Z］.ISO/IEC JTC1 sc29 m19455.Daegu，2011.

［11］WIEGAND T，OHM J R，SULLIVAN G J，et al.Special section on the joint call for proposals on high efficiency video coding(HEVC)standardization［J］.IEEE Transactions on Circuits and Systems for Video Technology，2010，20(12):1661-1666.

［12］BJONTEGAARD G.Calculation of average PSNR differences between RD-Curves［Z］.VCEG-M33，ITU-T sg16 VCEG.Porto Seguro，2001.

［13］XU Jiebin，PO Laiman，CHEUNG Chok Kwan.Adaptive motion tracking block matching algorithms for video coding［J］.IEEE Transactions on Circuits and Systems for Video Technology，1999，9(7):1025-1029.