基于深度特性的帧间预测快速算法

彭同壮，刘立程，杨关水

（广东工业大学 信息工程学院，广东 广州 510006）

随着5G商用的到来，超高清视频的应用将会越来越广泛，同时对视频传输和压缩带来了挑战。为此2013年由JCT-VC (Joint Collaborative Team on Video Coding)小组制定的下一代高效视频编码标准HEVC(High Efficiency Video Coding，H.265/HEVC)应运而生，并采纳成国际标准。HEVC标准相比上一代视频编码H.264/AVC在同等视频质量下可以节省50%的码率[1-2]，其编码框架沿用H.264/AVC技术，增加了更先进的编码技术，当然复杂的编码技术需要大量的时间进行编解码，在性能上，其复杂度是H.264/AVC的4～10倍，对于实时视频应用则是5 000倍，这对于技术推广和实际运用带来巨大的挑战，并引起了学术界和工业界的极大关注。帧间预测编码是HEVC重要的一部分，也是影响编码计算复杂度高的模块之一，大约占视频编码时间的69%[3]，因此，优化帧间预测过程很有必要。

对于帧间编码的优化，许多学者进行了深入的研究。在文献[4]中，提出了一种早期的MERGE模式决策算法，针对父CU(Coding Unit，CU)提出了早期的MERGE模式决策；然后，通过考虑父CU和子CU之间的模式选择的相关性，为子CU提出早期MERGE模式决策，能有效地提升编码速度。文献[5]提出了一种使用编码CU深度历史(AECH)的自适应提前终止算法。AECH计算所有CU深度值的平均值，并从平均值中找到CU深度历史记录的标准偏差，自适应地选择目标CU深度范围。该算法虽然能降低时间复杂度，但是没有很好地利用到空域特性，且利用时域历史深度的平均值会使编码当前深度进入局部最优状态，从而将误差扩散下去，造成较高的误码率。文献[6]提出了一种新颖的方法，提出CTU(Coding Tree Unit，CTU)中的CU也可以逆序遍历，从下到上的访问顺序进行自适应访问，使用逆序访问顺序时从较高深度获得的编码信息，降低HEVC中深度选择，模式决策和帧间预测的复杂度具有较好的效果，但是算法提升时间有限，且在纹理简单的视频未能很好地发挥性能。在文献[7]中，报告了基于贝叶斯决策规则的早期终止方法，其中联合应用在线学习和离线学习来生成分类器的模型参数，此类基于机器学习的方式虽然在时间上能有较大的提高，但是编码结果不精确，误码率较高，并在视频纹理复杂场景下的误码率更大，不适用于场景突变或内容纹理复杂的视频序列。在文献[8]中提出了一种快速CU深度决策算法，首先，提出了HEVC零深度CU检测方法作为早期终止算法，其次，根据统计时空深度信息的标准差自适应地确定了CU深度划分策略。最后，当邻居不可用或相关性很弱时，编码树单元CTU的边缘梯度被认为是CU深度划分方法的主要因素，虽然算法有很好的提升，但是在不同序列上降低编码时间复杂度的差异较大，通用性不强，在视频纹理复杂的情况下，误码率较高。文献[9]提出了一种HEVC的快速帧间模式决策算法，利用序列的相关性，包括四叉树结构和时空相关性，共同用于确定块大小的范围，并跳过一些特殊的块。此类在编码过程中对特殊信息提取的方式，准确率难以保证，带来的误码率较高。文献[10]提出了一种快速帧间CU决策方案，其中设计了一种新颖的ME(Motion Estimation，ME)方法，并定义了一种名为运动补偿RD(Rate distortion，RD)成本的新概念。为了减少RD优化的时间，文献[11]在基于统计信息的Hadamard变换之后采用零块检测方案。文献[12]提出了一种基于内容相似度的快速参考帧选择算法，以减少基于多个参考帧的帧间预测的计算复杂性。基于父级预测单元Inter_2N×2N和子级预测单元Inter_2N×N，Inter_N×2N，Inter_N×N，Inter_2N×nU，Inter_2N×nD，Inter_nL×2N和Inter_nR×2N的内容相似度，通过学习子预测单元的父预测单元的结果来获得子预测单元的参考帧选择信息，但在进行四叉树划分时，父块划分为4个子块，那么根据父子块信息之间的继承关系来进行子块模式的判定往往存在误差。

以上帧间预测模式快速算法一方面根据父子PU模式的相关性，利用父PU的模式来预测子PU模式过程，从而减少子PU不必要的遍历过程来降低时间复杂度。另一方面通过时空域的相关性，利用时域PU模式来跳过当前PU非必要模式的遍历。本文通过统计深度信息与PU模式之间的相关性，根据时空域相邻CTU的深度信息判断场景是否复杂，结合当前CU深度来对PU模式进行预测，算法在不同视频序列下误码率极小，时间节省明显，具有通用性。

1 HEVC帧间预测模式划分特性分析

为适应高分辨率的需求，HEVC的编码块CU采用了灵活的四叉树编码结构，一个CTU可以划分的尺寸为64×64～ 8×8的矩形编码块，其对应尺寸的深度为d，d的取值为0，1，2，3。HEVC编码结构如图1所示。

图1 CTU递归四叉树划分Fig.1 CTU recursive quadtree partition

HEVC进行帧间预测利用了视频序列的时间相关特性，通过去除时域冗余来达到高压缩率的效果。在帧间预测中需要在参考帧中找到最优的匹配块，然后对编码块CU从深度0到3进行递归划分，每个深度下的CU都需要进行遍历不同大小的PU模式，计算每种模式下的率失真代价，选出最优的模式作为当前编码模式。其率失真代价计算为

其中， D(Motion)、R (Motion)分别表示采用不同的运动模式下的失真和比特数，λMode为拉格朗日因子，率失真最小的模式即为最优预测模式。

帧间预测有8种预测模式，如图2所示，包括4种对称分割模式2N×2N，2N×N，N×2N，N×N和4种非对称分割模式2N×nU，2N×nD，nL×2N，nR×2N。每种模式下需要进行运动估计、运动补偿等过程，运动估计会进行运动矢量搜索，找到最优的匹配块，记录最优的运动矢量MV(Motion Vector，MV)，然后需要对当前运动矢量与预测运动矢量MVP(Motion Vector Prediction，MVP)进行差分编码，得到运动向量残差MVD(Motion Vector Difference，MVD)，即最后是通过编码MVD和像素残差信息进行编码。进行帧间预测过程中，深度为0、1、2的CU需要至少进行6次率失真计算，至多进行8次率失真计算(水平非对称划分标志Test_AMVPHor为真，只进行2N×nU，2N×nD的非对称遍历；垂直非对称划分标志Test_AMVPVer为真，只进行nL×2N，nR×2N的非对称遍历)，深度为3的CU只需要进行对称模式的划分，需要进行4次率失真计算，那么一个完整的CTU最少需要进行(1+4+16+64)×6=510次的率失真计算，并且分辨率越高的视频，其划分的CTU的数目越多，带来的计算复杂度越高，若能优化PU模式的遍历过程，则能大幅降低计算过程，对节省编码时间具有重要意义。

图2 PU帧间预测划分模式Fig.2 Inter-prediction partition mode

2 基于深度特性的帧间预测快速算法

2.1 PU统计特性分析

为分析不同深度下的PU特性，在官方测试软件HM16.9平台下统计PU在不同深度下的分布情况，测试的量化参数QP(Quantization Parameter, QP)设置32，CTU尺寸设置为64，最大深度设置3，编码配置LD模式下，测试统计数据如表1所示。对于较大的CU块，当前深度为0或1时，定义深度为SD(Small Depth，SD)；较小的CU块，当前深度为2或3时，定义深度为HD(High Depth，HD)。将帧间2N×N，N×2N，2N×nU，2N×nD，nL×2N，nR×2N等不规则尺寸模式划分统一用nN×mM表示，同时定义帧间2N×2N，N×N等规则尺寸模式划分统一用N×N表示。

表1 N×N、nN×mM分别在SD、HD深度下的概率统计Table 1 Statistics of N×N and nN×mM at depths of SD and HD respectively %

分析上表可知，当视频处于SD深度时，帧间规则的划分模式的比例高达87.32%～94%，而帧间不规则的划分模式比例仅达6%～12.68%；而在视频处于HD深度时，帧间规则的划分模式比例达66.22%～85.53%，帧间不规则模式比例达14.47%～33.78%。明显可以看出在深度SD下规则划分远远大于深度为HD下的规则划分，深度SD下的不规则划分远远小于深度HD下的不规则划分。在深度SD下，不规则划分比例最高不超过13%，即在深度SD下，不规则划分可以适当优化，进行跳过；且BasketballDrill (分辨率832×480)是篮球比赛场景，运动较剧烈，纹理相对简单，在HD深度下不规则的模式比例达27.44%；ChinaSpeed (分辨率1 024×768)是游戏中赛车场景，纹理细腻，运动特性剧烈，在HD深度下不规则的模式比例达33.78%；KristenAndSara (分辨率为1 280×720)是会议对话场景，运动简单，人物只有面部表情变化，纹理简单，在HD深度下不规则的模式比例仅达14.47%；BQTerrace(分辨率为1 920×1 080)是茶餐厅场景，背景简单，运动量较小，纹理较复杂，在HD深度下不规则的模式比例达28.04%；Traffic (分辨率为2 560×1 600)是大楼和马路，背景固定，运动不复杂，纹理简单，在HD深度下不规则的模式比例达27.85%。所以在不同纹理复杂度下，处于HD深度的不规则模式的比例有所不同，复杂场景下不规则块明显偏高。针对以上分析，可以对不同深度的视频跳过不规则的PU模式选择过程，达到优化目的，在SD深度下不规则块模式可以忽略；在HD深度下，不规则块模式是否可忽略需要进一步分析。

2.2 基于时空域的PU特性分析

视频在时空域呈现一定的特性，如图3是QP为32时ChinaSpeed视频序列的第5帧的部分截图，如图4是QP为32时ChinaSpeed视频序列的第6帧部分截图，图3和图4同一视频中前后相邻两帧正常编码的视频图像，利用分析软件[13]框出了每一个CU的PU大小。从图3和图4可以看出，当前块为SD深度的周围(左边、上邻域)，很少出现不规则的PU划分方式，而当前块为HD深度的周围存在不规则的划分方式明显偏多。对比图3和图4在时域同一位置处，当前块位于深度为SD，且PU模式为规则划分，其相邻同位块的PU模式的划分方式也都是规则划分；而深度位于HD，当前PU虽为规则划分，其相邻同位块的PU模式不一定为规则划分模式。

图3 QP为32时ChinaSpeed视频序列的第5帧Fig.3 Frame 5 of ChinaSpeed video sequence under QP=32

图4 QP为32时ChinaSpeed视频序列的第6帧Fig.4 Frame 6 of ChinaSpeed video sequence under QP=32

经过上述直观的观察后，为进一步验证，编码了不同级别视频各10帧进行测试，测试的量化参数QP设置32，CTU尺寸设置为64，最大深度设置3，编码配置为LD模式[14]。定义上一帧同位PU规则划分为事件A，当前帧周围邻域规则划分为事件B，当前帧PU规则划分为事件C，P(C|A)表示在A事件发生的情况下，B事件发生的概率，P(C|B)同理。统计数据如表2所示。

表2 在QP为32时条件概率P(C|A)、P(C|B)统计Table 2 Statistics of conditional probability P (C | A) and P (C | B)under QP = 32 %

一般当前CU的邻域深度越深，即有较多HD深度出现时，说明当前块的纹理复杂度越高，可以通过邻域深度特性得知当前块的复杂度。通过不同级别视频下所得出的数据，在深度为SD下，P(C|A)的值处于97.88%～99.21%，在深度为HD下，P(C|A)的值处于82.64%～89.31%，在深度为SD下，P(C|B)的值处于95.21%～98.93%，在深度为HD下，P(C|B)的值处于81.46%～91.26%。可知在邻域具有复杂纹理特性时，深度HD下的视频序列其可能划分成不规则块的比例明显偏高；在邻域具有简单纹理特性时，在深度为SD下，大都是规则块划分；则可以对纹理复杂块和简单块的PU模式进一步优化。所以可以对具有不同纹理、不同运动特性的视频制定自适应的帧间模式优化方案。若当前运动和纹理特性都简单，可以跳过不规则的划分方式，否则需要在HD深度下对纹理复杂的块，进行不规则的PU划分方式的遍历。

2.3 基于深度特性的帧间预测模式快速算法

通过上节的分析，可以制定帧间预测模式的快速算法，算法将针对不同纹理复杂度的CTU制定自适应的PU模式算法。首先需要进行当前区域复杂度的判断，通过统计上一帧相邻同位CTU的深度和当前空域相邻CTU的深度，来确定当前CTU的复杂度，具体地，如图5所示。

图5 当前CTU的时空关系图Fig.5 Current CTU spatiotemporal diagram

CTUcur为当前CTU，CTUabove为当前CTU的上方CTU，CTUleft为当前CTU的左方CTU，CTUabove-left为当前CTU左上方CTU，CTUabove-right为当前CTU右上方CTU，CTUcol为当前CTU的同位参考CTU。当前相邻帧的同位CTU的深度值用dcol表示，当前空间上邻域CTU深度值用da表示，当前空间左邻域CTU深度值用dl表示，若dcol值为3或者da和dl的值为2或3，即认定当前CTU为复杂块；然后根据不同复杂度CTU在不同深度进行不同的PU模式遍历。当前CTU复杂度δ计算方式见式(2)。

具体算法实现步骤如下：

(1) 按式(2)判断当前CTU纹理是否复杂，若复杂，进行第(2)步；若简单，进行第(3)步。

(2) 若当前CU深度为SD，尝试进行帧间2N×2N等规则划分，分别计算率失真代价，并跳过其他不规则模式划分，从规则划分模式中计算最优的率失真代价，将其划分模式作为当前最佳PU模式；若当前深度为HD，遍历所有的帧间PU模式，计算最优的率失真代价，将其划分模式作为当前最佳PU模式；进行第(4)步。

(3) 对所有深度下的CU进行帧间2N×2N，N×N等规则模式划分，分别计算率失真代价，并跳过其他不规则模式划分，从规则划分模式中计算最优的率失真代价，将其划分模式作为当前最佳PU模式；进行第(4)步。

(4) 当前CU深度小于3，若是，则按步骤(1)进行子CU的PU遍历；若否，结束划分过程。

3 实验与结果分析

在操作系统为Windows10，CPU为Inter® Core™i5-38300H @ 2.3GHz，内存8 G的硬件平台下进行了仿真实验，配置主要参数为：最大编码单元尺寸为64×64(深度d = 3)，编码配置为低时延和随机访问，量化参数(QP)为22、27、32和37，通过HEVC测试软件HM16.9对算法进行了仿真实验。本文测试了不同分辨率下的5种级别视频序列，根据分辨率的不同，2 560×1 600为Class A，1 920×1 080为Class B，832×480为Class C，416×240为Class D，1 280×720为Class E。

本算法采用的评价标准为平均峰值信噪比BD-PSNR和BD-Bitrate[15]，平均编码时间时间差为 Δt，见式(3)。

其中， QPi∈{22, 27, 32, 37}， to(QPi)表示HM16.9算法在 QPi的编码时间，ts(QPi) 表示本文算法在Q Pi的编码时间。本算法与标准对比实验结果见表3。从表3中可以看出，在低时延编码结构配置下，5个级别的视频序列在本文算法下相比HM16.9，编码时间节省了25.7%～31.72%，平均降低了28.6%，同时BDPSNR平均下降了0.03 dB，BDBR平均增加了1.1%；在随机接入编码结构配置下，编码时间节省了19.4%～28.7%，平均降低了23.6%，同时BDPSNR平均下降了0.02 dB，BDBR平均增加了0.73%。特别是，对于不同级别的视频均不会造成大的误码率，时间节省大致相同且效果明显，对于各类场景及分辨率下的视频具有通用性。

表3 实验仿真结果Table 3 Experimental results

为了展现本算法对编码器编码性能的影响，本文做出HM16.9和本文算法下编码器的RD曲线，图6和图7是不同级别的视频序列的RD曲线。从图6和图7中可以看出，在不同级别的视频序列中，本算法的RD曲线与HM16.9的RD曲线基本重合，相差微小，这说明本算法对比HM16.9来说，编码器的编码性能基本不变，即对率失真曲线的影响极小。本算法可以在保证编码性能不受太大影响的条件下，对降低编码时间取得较显著的效果。且不同视频序列下，比特损失，节省时间差异不大，可应用于各类场景下，通用性强。

图6 随机接入配置下RD曲线Fig.6 RD performance with random access

图7 低时延配置下RD曲线Fig.7 RD performance with low delay

4 结语

本文深入研究了帧间预测模式的流程，分析不同场景不同深度下视频序列的帧间PU模式，提出基于深度特性的帧间预测快速算法。通过统计不同深度下PU划分特性，对深度进行分层为SD区和HD区，对纹理简单的块只进行规则划分；对于纹理复杂的块进行不同深度的细化，在SD深度下，只进行规则划分，在HD深度下，遍历所有不规则的划分。实验结果表明，本文提出的算法与HM16.9相比，在基本不影响视频编码质量情况下，可以显著降低了编码时间，对于各类场景及分辨率下的视频具有通用性。