基于多时-空相关的AVS2快速帧间预测算法
2016-12-29李国平王国中赵海武滕国伟
陈 芳，李国平，王国中，赵海武，滕国伟
(上海大学 通信与信息工程学院，上海 200444)
基于多时-空相关的AVS2快速帧间预测算法
陈 芳，李国平，王国中，赵海武，滕国伟
(上海大学 通信与信息工程学院，上海 200444)
针对新一代视频标准AVS2引进四叉树分割、多参考帧等技术而带来的帧间预测复杂度增加的问题，提出一种基于多时-空相关的快速帧间预测算法。该算法利用上下层相邻编码单元(Coding Unit, CU)和空时域相邻CU在预测模式选择上的相关性，计算当前CU的模式复杂度，根据复杂度为当前CU分配合适的候选预测模式；同时利用相邻预测单元(Prediction Unit, PU)在参考帧选择上的相关性，计算当前PU的参考帧索引，根据索引为当前PU分配合适的候选参考帧。实验表明，该算法在BD-Rate(Bjontegaard delta bit rate)增加1.22%，BD-PSNR(Bjontegaard delta peak signal-to-noise rate)降低0.04 dB的前提下，平均减少47.54%的编码时间。
AVS2；多时-空相关；模式复杂度；预测模式；参考帧
为了满足高分辨率视频的需求，进一步提高视频压缩率，AVS工作组历时3年制作完成了新一代拥有自主知识产权的视频编码标准AVS2[1]，它的编码效率与最新国际标准H.265/HEVC相当，比上一代国家标准AVS1以及上一代国际标准H.264/AVC的效率提高1倍。特别对于监控视频等场景类视频，AVS2压缩效率又翻了一番，达到H.264/AVC的4倍。
AVS2引入了一些新的编码工具[2]以提升编码效率，如大尺寸四叉树编码单元划分、多参考帧预测、编码单元非对称分割、多角度帧内预测和像素自适应补偿滤波等。这些技术在提高编码效率的同时，也显著增加了编码复杂度。为了实现AVS2在电视直播、视频会议等视频通信系统中的实时应用，必须降低其编码的计算复杂度。
在AVS2编码标准中，帧间预测占据着大量的编码时间，因此如何降低帧间预测的复杂度成为降低编码复杂度的关键。目前，针对帧间预测快速算法的研究主要有两种：一是模式快速选择，基于空时域相邻块的相关性和一些已知的编码参数对当前块的划分模式或预测模式提前判决。如文献[3]利用上层相邻块和空时域相邻块的预测模式计算当前块的预测模式复杂度，根据复杂度为当前块分配合理的预测模式，跳过不需要的模式。这种方法充分利用了相邻块间的相关性，准确地预测了模式候选值。郑萧桢等提出了一种非对称运动划分(Asymmetric Motion Partitions, AMP)快速决策机制[4]，利用水平、垂直非方形划分模式的一致性，将对称非方形划分模式作为判断是否使用非对称非方形划分的依据。这种方法充分利用了模式间的纹理相关性为AMP模式提前作出判决。二是参考帧快速选择，减少各模式下参与运动估计的参考帧数目。如文献[5]以运动矢量差值为阈值，选择适当的相邻块的最佳参考图像获得当前块的参考图像集，减少参考帧遍历的冗余。
文献[3]虽然取得了较好的效果，但只是基于HEVC模型中帧间预测的特征统计对模式快速选择。由于AVS2在编码单元类型、运动矢量预测、率失真代价计算等方面和HEVC有很大的不同，该算法并不能直接应用在AVS2中。文献[4]和[5]分别只是针对AVS2模型中的AMP特殊模式和参考帧选择作出优化，降低的编码时间有限。基于AVS2的预测模式和参考帧选择的特征，本文提出了一种新的算法，充分利用具有较强相关性的下层相邻的4个块和空时域相邻块的预测模式获得当前块的候选模式，同时利用相邻块的参考帧索引预测当前块的候选参考帧，减少遍历预测模式和参考帧的时间。
1 AVS2帧间预测关键技术介绍
1.1 预测模式选择
AVS2采用了更加灵活的编码结构，包括编码单元(Coding Unit,CU)、预测单元(Prediction Unit,PU)和变换单元(Transform Unit,TU)。一幅图像被分割成固定大小的编码树单元(Coding Tree Unit,CTU)，CTU按照四叉树的迭代方式划分为一系列的CU。CU尺寸范围为8×8至64×64。CU又被划分为一个或多个PU和TU。
图1 CU的预测模式
如图1所示，帧间预测时CU有8种帧间预测模式(NO_SPLIT，HOR_SYM，VER_SYM，CROSS_SPLIT，HOR_UP，HOR_DOWN，VER_LEFT，VER_RIGHT)和4种帧内预测模式(I_NO_SPLIT，I_CROSS_SPLIT，I_HOR，I_VER)。CU的帧间预测模式还包括SKIP和DIRECT两种特殊模式。
AVS2模型采用率失真优化方式决定最佳预测模式。遍历图1中所有预测模式，分别根据式(1)计算每种模式对应的率失真代价，选择代价最小的模式作为最佳预测模式。
J(s,c,mode|QP,λmode)=SAD(s,c,mode|QP)+
λmodegR(s,c,mode|QF)
(1)
式中：mode为当前预测模式；SAD表示在给定量化参数QP的条件下，当前mode的重建块c与原始块s的绝对误差和；λmode是拉格朗日乘子；R表示编码运动矢量残差、参考帧索引和变换块系数等语法元素需要的比特数。
1.2 参考帧选择
AVS2模型采用率失真优化方法选择最优参考帧。在当前预测模式下对CU进行编码时，对该CU的每个PU分别做运动估计，利用式(2)从参考帧配置集中选择率失真代价最小的参考帧作为当前PU的最佳参考图像。这种方法需要遍历参考配置集中的每个参考帧。
J(mv,ref|λmotion)=SAD(s,r(ref,mv))+λmotion×
(R(mvd)+R(ref))
(2)
式中：ref为当前PU选择的参考帧；SAD表示原始块s与参考块r(ref,mv)的绝对误差和；mv是当前PU相对于参考块的运动矢量；；R表示编码运动矢量残差(mvd)和ref需要的比特数。
根据上述分析，确定一个CU的最终划分形式，需要遍历CU的14种预测模式和CU下PU的每个参考帧，这使得帧间预测的复杂度很大。然而，相邻CU在预测模式选择和参考帧选择上具有很大相关性，可以根据这种相关性减少遍历带来的复杂度。本文将统计相邻CU的相关性，并根据相邻CU的相关因子和编码信息为当前CU分配合适的预测模式和参考帧。
2 快速帧间预测算法
2.1 相邻CU的相关性分析
本文采用的相邻CU的位置关系如图2所示。CU_curr为当前编码CU；CU_nextdepth为相邻的下层深度的4个CU；CU_left，CU_leftup，CU_up，CU_rightup分别为空域相邻的左、左上、上和右上CU；CU_belcol和CU_aftcol为前后相邻帧的对应位置CU。AVS2模型采用类似四叉树后序遍历的方式对CU遍历，因此在编码当前CU时，这些相邻CU均是已编码CU，获取它们的信息不会增加计算复杂度。
图2 当前CU与相邻CU的位置关系
帧间预测时，两个相邻CU间的运动一致性越高，相关性越强。为了统计相邻CU的相关性，本文以AVS2参考软件RD14.0为平台，绝对误差和(SAD)为相关性的指标。以CU_left为例，由RD14.0的传统方法预测CU_left，可以得到CU_left在最佳编码模式(包括最佳的预测模式、参考帧、运动矢量)下的SAD。CU_curr不作帧间预测，直接利用CU_left的最佳编码模式编码，同样可得CU_curr的SAD。若这两个CU的SAD值越接近，则它们的运动一致性越高，相关性越强。类似地，可统计得到当前CU与其他相邻CU的相关性。
定义相关性因子RF表示各相邻CU间的相关性，RF的计算公式为
(3)
式中：SADnei表示相邻CU在最佳编码模式下的SAD；SADcurr表示当前CU用相邻CU的最佳编码模式编码得到的SAD。计算下层的每个CU的RF时，由于尺寸是当前CU的1/4，为了使SADnei与SADcurr具有可比性，取实际得到的下层CU的SAD值的4倍带入SADnei。
相邻CU的相关性因子RF如表1所示。表中“(×)”中的数字表示CU的个数。这些相邻CU的相关性均大于0.5，说明相邻CU与当前编码CU均具有较强的相关性。由于自然序列中水平和垂直的运动最频繁，左边和上边CU的相关性最强。下一深度的4个CU和当前CU具有内容的重复性，相关性其次。前后帧对应位置的CU相关性相对最小。
表1 各相邻CU的相关因子RF
2.2 预测模式快速选择
纹理简单、运动平缓的CU选择简单的预测模式以减少编码比特率，而纹理复杂、运动剧烈的CU选择复杂的预测模式增加预测准确度。因此，表2针对不同运动和纹理的CU，将CU的预测模式分为5类，定义模式复杂度因子MCF表征其运动和纹理的复杂度。
表2中MCF值的分配由实验所得。每种预测模式对应一个MCF值，简单的预测模式对应较小的MCF值，复杂的预测模式对应较大的MCF值。相邻CU编码选出最佳的预测模式后，根据表2将预测模式映射为相应的MCF值，结合表1中的相关因子RF，可预测当前CU的MCF值。根据预测得到的MCF值可为当前CU分配合适的候选预测模式。
表2 预测模式分类及与MCF的对应
定义由相邻CU预测得到的当前CU的模式复杂因子为PMCF，即
(4)
式中：N取为9;MCFi表示各相邻CU的模式复杂度因子MCF;RFi表示相邻CU的相关因子RF;Ei表示相邻CU是否存在。Ei=1表示相邻CU存在，Ei=0则表示不存在。由表2可得PMCF的取值范围为[0,5]。
PMCF很大程度上反映了当前CU的预测模式复杂度，根据PMCF的取值为CU分配适当的候选预测模式，分配公式为
(5)
式中：{MODEcand}表示当前CU的候选预测模式；Num表示相邻CU的存在数量。当Num>N/2且相邻CU都选择SKIP模式时，PMCF=0，说明当前CU无运动且纹理很简单，当前CU只选择C1为预测模式；当0
2.3 参考帧快速选择
自然视频序列中当前帧与相邻帧的相关性大于与远端参考帧的相关性，相邻帧被选为最佳参考帧的概率远大于其他参考帧[6]。因此可利用视频的特征减少对参考帧的搜索，减少编码计算复杂度。
表1的数据显示，相邻CU具有强相关性。相邻PU也具有类似的相关性。本文利用相邻PU的最佳参考帧索引预测当前PU的参考帧索引值，根据预测得到的索引值为当前PU分配合适的候选参考帧，去除参考帧遍历的冗余。前后帧对应位置的PU对当前PU参考帧选择的参考意义较小，本文所选的相邻PU不包含前后帧对应位置的PU。相邻PU的位置关系类似图2中相邻CU的位置关系。
定义由相邻PU预测得到的当前PU的参考帧索引为PRI。类似PMCF计算公式，PRI的计算公式为
(6)
式中：N取为7；RIi为各相邻PU的最佳参考帧索引，RIi按照与当前帧距离由近到远依次取值为1,2,3，…，M-1，M为总参考帧数；RFi表示相邻PU的相关因子RF，本文采用表1中的相关性因子；Ei表示相邻PU是否存在，Ei=1表示相邻PU存在，Ei=0则表示不存在。
根据PRI的取值为当前PU分配候选的参考帧。候选参考帧的分配为
(7)
式中：{REFcand}为PU的候选参考帧；Num表示相邻PU的存在数量。当Num>N/2且PRI=0时，相邻PU都选择最近的参考帧，说明当前PU与最近参考帧中的参考块的相关性最强，当前PU选择最近参考帧为最佳参考帧；当Num>2且PRI 为了验证本文提出的快速帧间算法的有效性，在AVS2最新参考软件RD14.0中实现本文算法，选择不同分辨率和不同运动纹理程度的序列进行测试，实验具体配置如表3所示。采用峰值信噪比差值(Bjontegaard delta peak signal-to-noise rate, BD-PSNR)和编码比特率差值(Bjontegaard delta bit rate, BD-Rate)[7]分别衡量视频序列中图像失真程度和压缩效率，评估算法的整体率失真特性。编码时间变化则用ΔT表示，即 (8) 式中，TRD和Tpro分别表示RD14.0中传统方法和所提的快速算法的编码时间。 本文除了和RD14.0的传统方法对比之外，还选择在RD14.0的基础上对文献[5]的算法进行横向对比，结果如表4所示。由表4可得，文献[5]的算法相对于RD14.0传统方法在BD-Rate增加3.00%，BD-PSNR降低0.1 dB的前提下，平均减少32.04%的编码时间。而本文算法相对于RD14.0传统方法在BD-Rate增加1.22%，BD-PSNR降低0.04 dB的前提下，平均减少47.54%的编码时间。因此，本文算法比传统方法节省了较多时间，而且与文献[5]的算法相比，本文算法不仅额外节省15.5%的时间，而且BD-Rate降低1.78%，BD-PSNR增加0.06 dB。 表3 实验测试条件 表4 各算法与RD14.0对比的结果 对于运动速度较快的RaceHorses和纹理相对复杂的City，本文所提算法节省的时间较少。而对于运动缓慢的Crew和纹理相对简单的BasketballDrive，本文所提算法节省的时间较多。由于Crew存在镜头闪烁，Cactus旋转运动较多，候选的预测模式和参考帧误差相对其他序列较大，视频质量下降较多。 选择实验数据中BD-Rate增加较多，BD-PSNR降低较多的序列Crew和Cactus绘制RD曲线。如图3所示，本文算法与RD14.0方法的RD曲线基本重合，对这两种序列的编码效率影响很小。因此可证本文算法对于视频编码质量和压缩效率影响很小。 图3 本文算法与RD14.0传统方法的的RD曲线 选择实验数据中时间节省较少的序列RaceHorses和City，分别绘制4个不同QP下，文献[5]和本文算法较RD14.0中传统方法的时间节省图。如图4所示，横坐标为编码的QP，纵坐标为相对于RD14.0的编码时间节省。由图4中走势可得，随着QP的增加，快速算法的时间节省越多，本文算法相对于RD14.0中的传统方法时间节省较多。而且和文献[5]比较，本文算法也能额外节省不少时间。因此，本文的快速算法是有效的。 图4 各算法相对于RD14.0传统方法的时间节省图 本文重点研究了在AVS2的帧间预测中，使用多划分模式、多参考帧技术带来的编码复杂度增加问题。针对这一问题，本文创新性地使用与当前编码CU有着强相关性的下一深度的4个CU的编码信息，并结合空时域相邻CU的编码信息。统计这些相邻CU的相关性，并由相邻CU的相关因子和预测模式为当前CU分配合理的候选预测模式，同时利用相邻PU的相关因子和参考帧索引预测当前PU的候选参考帧，避免了预测模式和参考帧遍历的冗余。实验结果表明，本文算法与RD14.0的传统方法相比，在BD-Rate增加1.22%，BD-PSNR降低0.04 dB的前提下，平均减少47.54%的编码时间。与文献[5]的算法相比，不仅节省15.5%的时间，而且BD-Rate降低1.78%，BD-PSNR增加0.06 dB。由此可见，本文算法在视频质量和比特率损失很小的情况下，编码时间节省较多。 [1] HE Z C,YU L, ZHENG X Z, et al. Framework of AVS2-video coding[C]//Proc. the 20th IEEE International Conference on Image Processing. Piscataway: IEEE，2013: 1515-1519. [2] 马思伟.AVS视频编码标准技术回顾及最新进展[J].计算机研究与发展,2015,52(1):27-37. [3] SHEN L Q, ZHANG Z Y, LIU Z. Adaptive inter-mode decision for HEVC jointly utilizing inter-level and spatiotemporal correlations[J]. IEEE transactions on circuits and systems for video technology,2014,24(10): 1709-1722. [4] 郑萧桢.AVS_M3012:AVS快速决策机[EB/OL]. [2016-04-10]. ftp://124.207.250.92/public/avsdoc/1212_Beijing/contrib/. [5] 林琪,赵海武,王国中,等.面向AVS2的快速帧间预测算法[J].电视技术,2014,38(17):76-84. [6] 张淑芳,李华.基于H.264的多参考帧快速选择算法[J].电子学报,2009,37(1):62-66. [7] BJONTEGAARD G. Calculation of average PSNR difference between RD-curves[EB/OL]. [2016-04-10]. http://ftp3.itu.ch/av-arch/video-site/0104-Aus/. 陈 芳(1992— )，女，硕士生，主研视频编解码技术； 李国平(1974— )，硕士生导师，主研视频编解码技术、复用技术等； 王国中(1962— )，博士生导师，主研视频编码与多媒体通信、图像处理等； 赵海武(1973— )，硕士生导师，主研视频编解码技术、复用技术等； 滕国伟(1975— )，硕士生导师，主研视频编解码技术、智能视频分析等。 责任编辑：薛 京 Fast inter-frame prediction algorithm for AVS2 based on multiple temporal-spatial correlations CHEN Fang, LI Guoping, WANG Guozhong, ZHAO Haiwu, TENG Guowei (ShanghaiUniversity,SchoolofCommunicationandInformationEngineering,Shanghai200444,China) The complexity of inter-frame prediction is increased in the new generation video standard AVS2 by introducing the technology of quad-tree division, multiple reference frames, etc. To solve the problem, a fasted inter-frame prediction algorithm based on multiple temporal-spatial correlations is proposed. The mode complexity of current coding unit(CU) is calculated by the correlations of adjacent depth and adjacent temporal-spatial CU in terms of the selection of prediction mode, then the appropriate candidates of prediction mode are distributed according to the mode complexity. At the same time, the reference index of current prediction unit(PU) is calculated by the correlations of adjacent PU in terms of the selection of reference frame, then the appropriate candidates of reference frame are distributed according to the reference index. Experimental results show that, the proposed algorithm can reduce the encoding time by 47.54% on average, with a 1.22% increase of Bjontegaard delta bit rate(BD-Rate) and a 0.04dB decrease of Bjontegaard delta peak signal-to-noise rate(BD-PSNR). AVS2; multiple temporal-spatial correlation; mode complexity; prediction mode; reference frame 国家自然科学基金项目(61271212);国家“863”计划项目(2015AA015903) 陈芳，李国平，王国中，等.基于多时-空相关的AVS2快速帧间预测算法[J]. 电视技术，2016,40(12)：1-6. CHEN F, LI G P, WANG G Z，et al.Fast inter-frame prediction algorithm for AVS2 based on multiple temporal-spatial correlations[J]. Video engineering，2016,40(12)：1-6. TN919.81 A 10.16280/j.videoe.2016.12.001 2016-05-203 实验结果
4 小结
