面向AVS2的快速帧间预测算法

林 琪，赵海武，王国中，滕国伟，李国平

（上海大学 通信与信息工程学院，上海 200436）

AVS标准是中国“数字音视频编解码技术标准工作组”自主研发，拥有自主知识产权的第二代视频压缩标准。随着压缩技术不断地提升，标准工作组在完成AVS标准制定后，现又以超高清晰度视频为应用目标，积极地制定压缩效率更高的新一代视频编码标准AVS2。该标准在制定中引入了多种先进技术来提升编码效率。例如，编码块大小由原来的16×16扩展到64×64，并且采用了灵活的四叉树结构对编码块进行自适应划分[1]；引入多参考帧技术，规定了P帧可以参考前向的多帧，B帧可以参考前后两帧等。这些技术的引入大幅地提高了视频编码的效率，与此同时编码复杂度也成倍地增加。因此，有效地提高编码速度是AVS2标准成功推广的关键所在。

AVS2仍然沿用了上一代编码标准的混合编码框架，其中帧间预测仍然占据着大量的编码时间，如何减少帧间预测的复杂度依然是许多专家学者关注的重点。目前，对于帧间预测快速算法的研究主要集中在两类：第一类是快速运动搜索算法，如著名的三步搜索算法（TSS）、非对称十字型多层次六边形格点搜索算法（UMHexa⁃gonS）[2]等；第二类则是快速帧间模式选择算法，主要通过减小帧间候选模式搜索数目来加快编码的速度，如AVS2提案M3012采用了一种AMP快速决策机制[3]，利用水平（垂直）非方形划分模式上的相似性，在编码图像块的时候，使用对称非方形划分模式作为判断是否使用非对称非方形划分的依据，从而降低编码的复杂性。文献[4]则将运动估计快速算法与帧间模式选择算法结合在一起研究，打破了传统的将快速运动搜索算法与快速帧间模式选择算法独立研究的现象，避免了两种方法单独研究时存在的不足。

由于AVS2引入了更多的模式划分以及更多可供参考的参考帧数目，这使得帧间预测的编码复杂度进一步增加。针对该问题，本文通过对多模式划分的研究，在使用AMP快速决策算法的基础上，通过减小各种划分模式下参与运动估计计算的参考帧数目，进一步加快帧间编码速度。

1 AVS2帧间预测

1.1 图像的划分

AVS2依然采用分块的编码方式，但是块的尺寸可以自适应地改变。其中包含了3类处理单元，分别是编码单元（Coding Unit，CU），预测单元（Prediction Unit，PU）以及变换单元（Transform Unit，TU）。视频图像被划分成一系列编码树（Coding Tree Blocks，CTB），它是进行预测、变换、量化和熵编码等处理的基本单元，其尺寸可以是2N×2N，N∈(32,16,8)。而一个亮度CTB和相应的两块色度CTB，再加上相应的语法元素组成了一个编码树单元（Coding Tree Units，CTU）。CTU以四叉树递归的结构，被划分成尺寸大小相同的4个方块，即4个叶节点，每个叶节点，就是1个CU，共有64×64，32×32，16×16等3种尺寸。CU是帧内、帧间、Skip等预测模式的基本单元。在做帧间预测时，CU又可以被划分成一个或者多个用于帧间预测的PU。在一个大小为2N×2N的CU下，PU帧间模式划分有8种不同的划分：4个对称划分（NO_SPLIT，CROSS_SPLIT，HOR_SYM，VER_SYM）以及4个非对称划分（PHOR_UP，PHOR_DOWN，PVER_LEFT，PVER_RIGHT），如图1所示。

1.2 AVS2帧间模式选择原理

在对CU进行编码前，首先对该编码单元进行模式划分，然后对划分的模式遍历，分别进行运动估计和运动补偿。比如，在当前模式下对CU进行编码时，先对该CU下的PU分别做运动估计，利用式（1）从各个候选参考帧下选择失真代价最小的参考帧作为当前PU的最佳参考图像

式中：λmotion=，是拉格朗日因子；mv是当前PU相对于所选的参考图像块的运动向量；ref是当前所选的参考图像在参考帧队列中的索引值；SAD是当前编码块与参考图像块差值的绝对值之和；r(ref,mv)是参考图像块；R（mvd）+R（ref）表示的是码率，第一项表示对运动向量残差进行编码所需要的比特率，第二项表示对选择的参考图像的索引值进行编码所需的比特率。

PU最佳参考图像得到后，完成该模式下的运动估计，再使用式（2）获得代价最小的模式作为当前编码块的最优模式，完成后续的编码

式中：SAD表示在给定量化参数QP的条件下，该模式的预测单元与重建图像块的差值平方和；s是当前预测单元；c是重建图像块；mode是所选的帧间编码的模式；R是在该模式下编码所需要的比特数，包括了表示模式所需的比特数、运动向量的残差和变换块的信息；拉格朗日因子λmotion是根据量化参数QP获得的。

2 快速帧间预测算法

在对CU进行编码时，遍历参考图像缓冲区的候选参考图像获得最佳参考图像，以及对CU的多种划分模式进行遍历获得最优模式，编码器的编码复杂度会随着参考帧数目和模式划分数目增加而大幅度增大。针对多模式划分产生的计算复杂度增加问题，提案M3012提出的AMP快 速 决 策 机 制 ，根 据 HOR_SYM，HOR_UP，HOR_DOWN及VER_SYM，VER_LEFT，VER_RIGHT在划分模式上的相似性，提出在编码图像块时使用对称非方形划分模式作为判断是否使用非对称非方形划分的依据。若水平对称非方形划分（或垂直对称非方形划分）是当前最优模式，则编码端继续编码两种水平非对称非方形划分（或垂直非对称非方形划分）模式；否则，跳过该两种非对称非方形划分模式[3]。这种方法有效地降低了AMP的编码复杂度，然而它只是对帧间模式选择进行了快速运算，降低的时间有限，在多参考帧的帧间预测下，仍有较大的改进空间。

视频图像具有空间相关性，相邻块之间也有一定相关性，AMP快速决策机制正是鉴于该种特性，有效减低编码复杂度。研究相邻块的这一特性中，对同一CU下的PU的参考帧选择进行分析，统计相邻PU之间选择同一参考帧的概率，发现相邻PU不同CU深度选择参考帧呈现相同的规律，选择同一参考帧的概率较大。文献[5]也根据这一现象，深度挖据相邻PU之间参考帧的相关性，通过运动矢量mv判断是否缓冲区的参考帧进行遍历。然而该方法使用mv作为阈值判断，并不能很好地反映相邻PU之间的相关性。而文献[6]则提到运动矢量差值mvd（预测mv与当前mv的差值）反映了运动的复杂度，表示了当前PU与相邻PU的运动平缓度，mvd越小，物体运动越平缓，选用邻近参考帧最为最佳参考帧的概率就越大，该方法在使用时，通过参考帧的概率分布，预先为当前编码帧初始化一个参考帧集（RFS）来减小参与运动估计的参考帧数目，其编码速度的快慢很大程度上取决于参考帧集中元素的个数以及mvd阈值的选定。如果在编码某一划分模式下的PU，对参考图像缓冲区的候选参考帧进行遍历搜索，就会浪费大量的运算。

根据以上这些分析，本文将AMP快速决策机制与参考帧选择算法结合在一起研究，提出一种多模式多参考帧的快速帧间预测算法，在AMP快速决策算法基础上，适时地选用相邻PU的最佳参考帧作为当前PU的最佳参考帧，选用运动矢量差值作为阈值判断，进而达到减低编码复杂度的目的帧间预测。

算法的具体实现如下：

1）确定每一层CU的运动矢量残差（运动估计获得的运动矢量与预测获得的运动矢量的差值）的曼哈顿距离（=|mvd_x|+|mvd_y|）的阈值TH[i]，其中i代表CTU的深度，取值为0～2。对序列的初始两帧按照原始的方法进行编码，记录不同深度（不同CU尺寸），并分别对每层的求和，取其均值Mean_mvd[i]。TH[i]计算如式（3）所示

式中：k是常系数，本文中k均取1。确定阈值后，开始对各划分模式进行遍历，执行第2）步，编码端首先对水平对称非方形和垂直对称非方形划分进行分析。

2）编码当前CU下第一个PU（标号为0）时，按照原始方法对参考帧缓冲区中的候选参考帧进行遍历做运动估计，获得最佳参考帧。

3）编码当前CU左边（或下边）的PU时，首先以已编码的标号为0的PU对应的最佳参考帧作为当前PU的参考帧，进行运动估计计算，获得

4）将该与当前PU所处深度的对应阈值TH[i]进行比较，如果≤TH[i]，则当前预测所用的参考帧即为最佳参考帧，也就是相邻PU的最佳参考帧，结束当前PU对参考图像缓冲区中其余候选参考帧的遍历；否则，＞TH[i]，遍历参考图像缓冲区中剩余的候选参考帧，找到最佳参考帧。

5）当前模式是方形对称模式时，则编码右下方PU时，若其上边、左边PU的最佳参考帧相同，则以该参考帧作为当前PU的最佳参考帧；否则，遍历参考图像缓冲区中的所有候选参考帧。

6）最后将该划分模式与当前最优划分模式比较，取代价较小的模式更新当前最优模式。若当前最优模式是水平对称非方形划分（或垂直对称非方形划分），则编码端继续编码水平非对称非方形划分（或垂直非对称非方形划分），重复第2），3），4）步；否则，跳过该两种非对称非方形划分模式，重复第2），3），4），5）步。

算法流程图如图2所示。

图2 算法流程图

3 实验结果

为了验证本文提出快速帧间预测算法的有效性，在AVS2参考软件RD5.0中加入本文算法，通过使用本文算法所需的编码时间（time）与使用AMP快速决策算法以及原始搜索算法两种算法的编码时间分别进行比较，测试不同量化参数（QP）、不同序列下的编码性能。具体配置如表1所示。表2为本方法的实验结果，本文主要从编码时间与文献[3]方案以及全搜索方案进行对比。此外采用RD曲线对编码性能进行对比。

表2中，Δtime表示总编码时间的变化，如果为负，表示编码时间减小，反之则增加。由表2可知，本文提出的算法较全搜索算法相比编码时间有大幅度下降，平均下降36%左右。若视频较为平缓如Video1，本文方法时间则节省约40.6%；与文献[3]中AMP快速决策算法相比，本文方法的编码时间也有明显的下降，平均下降约为14%，如Video1这类运动较为平缓的会议视频，其编码时间下降有17%，如RaceHorses这类运动较为剧烈的视频，其编码时间下降也有10%。性能方面，由图3～图8可知，本文方法对编码效率基本没有影响。

表1 实验测试条件

表2 本文算法在RD5.0下的实验比较

4 结论

本文重点研究了在AVS2的帧间预测中，使用多划分模式、多参考帧技术带来的编码复杂度增加问题。针对这一问题，本文在已有的AMP快速决策算法的基础上，对其进一步研究，并将其与降低多参考帧数目方法相结合，利用同一CU下相邻PU的相关性，减小各模式下PU对参考图像缓冲区中的候选参考图像的搜索概率，进而降低帧间的编码时间。实验结果表明，本文提出的算法应用于AVS2参考软件中，可以使编码时间平均下降36%左右。比原始AMP快速决策算法的编码时间平均下降14%，编码性能基本保持不变。由此可见，本文方法对解决AVS2标准中使用多种先进技术而带来的编码复杂度大幅度升高问题有一定地帮助，从而促进AVS2的进一步发展。

：

[1]SUNIL L.AVS视频提案A AVS_M2973:Proposal for AVS2.0 refer⁃ence software[EB/OL].[2014-02-17].http://www.avs.org.cn/index.asp?meetingid=65＆filetype=proposal.

[2]陈超峰.基于AVS快速运动估计的视频编码研究[D].广州：华南理工大学，2011.

[3]郑萧桢.AVS视频提案A AVS_M3012：AMP快速决策机制/Fast mode decision for AMP[EB/OL].[2014-02-10].http://www.avs.org.cn/index.asp?meetingid=65＆filetype=proposal.

[4]BELGHITH F，KIBEYA H，LOUKIL H，et al.A new fast motion estimation algorithm using fast mode decision for high-efficiency video coding standard[J].Journal of Real-Time Image Processing，2014:1-17.

[5]沈晓琳.HEVC低复杂度编码优化算法研究[D].杭州：浙江大学，2013.

[6]WANG Shanshe，MA Siwei，WANG Shiqi，et al.Fast multi reference frame motion estimation for high efficiency video coding[C]//Proc.20th IEEE International Conference.Melbourne:IEEE Press，2013：2005-2009.

[7]BJONTEGAARD G.Calculation of average PSNR differences be⁃tween RD curves[R].[S.l]：Joint Video Team （JVT） of ISO/IEC MPEG and ITU-TVCEG，2001.