VVC帧间编码CU快速划分算法

褚嘉璐，李 强

重庆邮电大学 通信与信息工程学院，重庆 400065

由ISO/IEC的MPEG和ITU-T的VCEG联合制定的新一代视频编码标准——通用视频编码（versatile video coding，VVC）已于2020年7月正式发布。该标准技术将应用于4K视频、8K视频、直播和沉浸式媒体等多种商用场景。

VVC仍沿用基于块编码的技术，在上一代高效视频编码（high efficiency video coding，HEVC）框架[1]基础上通过引入许多新技术提高了编码效率。如在CU划分的过程中引入了更加灵活的多类型树划分[2]；在帧间预测中引入融合仿射运动预测[3]、几何块融合[4]、运动矢量差的融合[5]、帧内帧间联合预测[6]等新技术。目前VVC的测试模型VTM（VVC test model）已更新至VTM10.0版本。根据文献[7]，与HEVC的测试模型（HEVC test model，HM）相比，VTM10.0在随机接入（random access，RA）模式下的编码性能提升了38.42%，但编码时间却增加了977%，这使得VVC难以投入实际应用。因此在保证视频质量基本不变、编码性能损失较小的情况下，如何大幅度减少VVC的计算复杂度成了当前视频编码研究者的重点研究方向。

近些年来，很多研究者通过分析VVC帧间编码过程，借鉴HEVC帧间编码快速算法原理，提出了很多视频编码帧间预测加速方案，其中最直接有效的方法就是CU划分的提前终止。文献[8]提出了一种基于三帧差分的方法，先计算当前帧与两个参考帧对应位置像素绝对值之差，通过比较差值大于阈值的数量占CU总像素数量的比重，判断当前区域是否相对静止，决定是否跳过CU划分；文献[9]提出了限制划分层次的快速帧间预测算法，通过限制编码树单元（coding tree unit，CTU）在划分过程中的最大深度，提前结束CU划分过程；文献[10]使用了机器学习的方法，训练了多个基于随机森林的分类器，为每个CU选择最可能的划分模式，从而加速了编码过程。在对HEVC的相关研究中，文献[11]针对监控和会议视频的场景，提出了基于虚拟背景帧的快速帧间编码方法，利用帧间的时域相关性生成虚拟背景帧，进而对CU分类并限制划分深度，达成加速编码的目的；文献[12]利用当前CU与空时域相邻CU的相关性缩小当前CU需遍历的深度范围，从而减小编码计算量；文献[13]设计了一种基于卷积神经网络的快速CU决策算法，减少了待遍历的CU尺寸的数量，进而达到加速的效果。

帧间预测加速算法通常需要使用参考帧中的信息，利用帧与帧之间的相关性来消除视频序列的时间冗余，如文献[8]与文献[11]使用了已编码帧的像素信息，文献[12]则使用了参考帧中CU深度信息。在目前的帧间加速算法中，充分利用参考帧的运动矢量信息进行编码加速的算法较少。本文对VVC帧间编码的CU划分进行了研究，提出了一种基于参考帧运动矢量分布的CU划分模式提前选择方法。为了进一步加快编码速度，本文还提出了一种基于空域相邻CU预测模式的CU划分深度提前终止方法。这两种方法的结合能够在编码性能和图像质量损失较小的前提下，显著加快编码速度。

1 VVC的CU块划分结构

在视频编码过程中，视频序列首先被分为若干个图像组（group of pictures，GOP），一个GOP有若干图片。根据常规环境测试（common test condition，CTC）[14]，在RA模式下，一个GOP有16帧，第1帧为使用帧内预测的I帧，其余为使用帧间预测的B帧。在图1所示的一个GOP中，POC0作为I帧第一个被编码，GOP中的最后一帧POC16作为B帧第二个被编码，后续的编码顺序为8、4、2、1、3、6、5、7、12、10、9、11、14、13、15，先被编码的帧会作为后续编码的参考帧。

图1 GOP编码顺序Fig.1 GOP coding order

帧是块划分的基本单位[15]，在对一个B帧进行编码时，每一帧图像首先会被分为若干个CTU，再基于CTU进行下一步划分。HEVC的CTU大小为64×64，通过四叉树（quad-tree，QT）将CTU划分为CU，CU再进一步被划分为预测单元（prediction unit，PU）和变换单元（transform unit，TU）。而VVC的CTU尺寸变为128×128，并取消了CU、PU和TU的划分，即CTU划分为CU之后直接进行预测和变换。

VVC使用嵌套多叉树的四叉树（quad-tree with nested multi-type-tree，QTMTT）结构对CTU进行划分。MTT的结构包括垂直二叉树（vertical binary tree，VBT）、水平二叉树（horizontal binary tree，HBT）、垂直三叉树（vertical ternary tree，VTT）以及水平三叉树（horizontal ternary tree，HTT）。VBT与HBT将块按照1∶1分成两部分，而VTT与HTT类似HEVC中PU的非对称划分模式，将CU按对应方向进行1∶2∶1划分。

图2是一个CTU划分的例子，编码器若判决需对CTU进行QT划分，则对大小为64×64的块进行QT或MTT划分，但MTT划分之后不再允许进行QT划分，直到块的长或宽等于4为止。

图2 CTU划分实例Fig.2 CTU partitioning example

图3是图2对应的QTMTT结构示意图，是该CTU最终选择的编码树划分结构。在CTU的划分过程中，编码器的率失真优化（rate-distortion optimization，RDO）是一个深度优先遍历的过程（depth first search，DFS），遍历每一种划分的可能性并计算率失真代价[16]（ratedistortion cost，RD-cost），然后选取RD-cost最小的划分作为最终结果。由于VVC采用了更加灵活的划分方式，随着划分层数的加深，RDO需要遍历树的分支急剧增多，因此编码运算量大幅度增加。在CU划分过程中，如果能减少划分模式或者减小遍历的深度，就可以明显降低编码复杂度，加快编码速度。

图3 QTMTT结构示意图Fig.3 QTMTT structure schematic diagram

2 CU快速划分算法

2.1 VVC的CU划分过程

VTM10.0的CU划分流程如图4所示。第一步是初始化CU。编码器将所有允许执行的划分模式放入一个先进后出的栈中，候选栈中的划分模式越多，当前节点的下一层分支就越多，编码复杂度就越高；第二步，编码器计算当前CU执行跳过（skip）、融合（merge）、帧间运动估计（inter ME）等预测模式的RD-cost，并选取RD-cost最小的模式作为当前CU最优模式；第三步按顺序逐个调用之前栈中存放的划分模式，并根据当前CU尺寸以及执行过的划分顺序，确认是否可以执行该模式，如果可以，就将CU划分为子CU，并以递归的形式重复第一步。因此在初始化CU时，如果能减少栈中的划分模式个数，就可减少下一层的分支数量，降低CU划分的复杂度。在执行帧间预测模式之后，若能不进入下一层划分，就能加快CU划分速度。

图4 VVC编码CU流程图Fig.4 Flowchart of VVC encoding CU process

2.2 CU划分模式的提前选择

2.2.1帧间编码运动矢量特性分析

在帧间编码过程中，编码器通过运动估计（motion estimation，ME）为当前编码块在参考帧中寻找相似块。当前块与相似块在空间上的相对位置即为运动矢量（motion vector，MV）。图5是MV分布与CU划分的例子。通常一个区域内纹理越复杂，MV分布越密集，CU划分就越细致；相对的，一个区域纹理越简单，或者MV的分布越稀疏，CU划分就越简略。

图5 GOP中的两帧Fig.5 Two frames in GOP

图5中的视频帧（a）和（b）是同一GOP中的两个B帧，编码顺序（a）在（b）之前，但时间上（a）在（b）之后，（a）是（b）的参考帧。在图中，椭圆圈内的区域是纹理较复杂的静止区域，这些区域在（a）中划分层数较深，而在（b）中划分的层数相对浅；对于图像中移动的行人，在（a）中这部分区域的MV分布密集，说明该区域运动状态相对复杂，CU也相应地被划分为更小的块，对应地，在（b）中相应的运动区域的CU也被划分为更小的块，两帧中的对应区域在CU的划分特征上呈现了高度的相关性。对于右下角新出现的运动物体，编码器无法通过ME在参考帧中找到对应的块，因此采用帧内预测的方式进行编码，这些块通常也会被划分得很小，并且没有MV信息。

2.2.2CU划分模式提前选择算法

因为参考帧的MV分布的疏密程度与当前编码CU划分的细致程度存在明显的相关性，所以为了加速CU的划分过程，本文提出了一种基于参考帧对应区域MV分布特性的CU划分提前选择算法。通过判断参考帧对应区域的MV分布特性，提前选择一种或者几种划分模式，进而减少需要遍历的划分模式个数，从而达到加速编码的效果

首先确定当前区域的MV是否具有一致性。本文采取的方法如图6所示第一步是获取与当前CU相邻的上CU和左CU的MV。若两个MV不一致，则说明当前区域和参考帧对应区域的运动情况复杂，MV分布情况无法准确地指导当前CU的划分。如果二者相等，则说明当前区域的运动有较高的一致性。参考帧对应位置坐标以公式（1）和（2）的方式计算。其中，Xcol和Ycol是参考帧中对应位置的横坐标和纵坐标，Xcur和Ycur是当前编码CU的横坐标和纵坐标，MV x和MV y是当前编码CU相邻的MV的横向分量和纵向分量。

图6 获取相邻CU的MVFig.6 Deriving MVs of adjacent CUs

其次获取参考帧的MV。本文获取参考帧MV的模型如图7所示，当前编码CU是一个如图7（a）所示的正方形时，在参考帧对应区域以同样的长和宽总共取9个点的MV，取样点位于边长的1/4，1/2，3/4处；若当前编码的CU是类似图7（b）或（c）所示的矩形，则按照与当前CU相同的形状，在参考帧对应区域取6个点的MV。（b）和（c）中取样点的距离，较长的边为1/4，1/2，3/4，较短的边为1/4，3/4。

图7 获取MV的三种模型Fig.7 Three models of deriving MVs

结合VTM10.0中编码器的特性，本文算法在获取MV的过程中有如下性质：

（1）取MV的过程与参考帧中对应区域的CU划分方式无关。以图7（a）为例，取9个采样点并不意味着该区域会有对应的9个CU。如果1、2、3点对应的MV属于同一CU，或者1、2、3点所属不同CU，但它们的MV相同，那么从1、2、3点所取到的MV将完全相同。

（2）因为CU长和宽的最小值为4，所以对于图7（b）和（c）的情况，本文算法只考虑矩形最短边的边长大于等于8，较长的边大于等于12的情况，对于图7（a）只考虑长和宽大于等于12的情况。

（3）参考帧中的取样点如果超出了图像范围，则不使用提前选择算法。

最后通过分析参考帧中MV的分布特点，将部分划分模式加入候选栈中，然后编码器从这些模式中选出最可能的划分方式。

CU划分模式提前选择算法流程如图8所示。

图8 CU划分模式提前选择算法流程图Fig.8 Flowchart of early selection algorithm for CU partition modes

（1）判断相邻MV是否一致，若不一致，则使用VTM10.0原有的方法进行初始化，否则进入下一步骤。

（2）通过当前CU坐标加MV的偏移得到参考帧对应位置坐标。

（3）判断当前CU是否为正方形，如是正方形，使用9MV模型，否则进入步骤（4）。

①判断1，2，3点的MV是否一致。若一致，进入②；如果不一致，则判断1，4，7的MV，如果一致，则将HTT和HBT模式入栈，如果不一致，则将QT，VTT，HTT模式入栈。

②判断4，5，6的MV是否一致，若一致，则进入③，否则将VTT和VBT模式加入栈。

③判断7，8，9的MV是否一致，若一致，则进入④，否则将VTT和VBT模式加入栈。

④若所有MV一致，则不向栈中添加任何模式，否则仅将VTT模式加入栈。

（4）若CU的长大于宽，则在参考帧中使用横向6MV模型，否则进入步骤（5）。

①若1，2不一致，但1，3，5一致，则将HTT和HBT加入栈；若1，3，5不一致，则加入VTT和HTT模式；若1，2一致，则进入②。

②若3，4不一致，则添加VTT和VBT模式进入栈；若一致，进入③。

③若5，6不一致，则添加VTT和VBT进入栈，否则进入④。

④若所有MV一致，则不加入划分模式，否则仅将VTT模式加入栈。

（5）CU的长小于宽，使用纵向6MV模型。

①若1，2不一致，且1，3，5不一致，则加VTT，HTT模式；若1，3，5一致则添加VTT，VBT模式；若1，2一致，则进入②。

②若3，4不一致，则将HTT，HBT入栈，若一致，进入③。

③若5，6不一致，则将HTT和HBT入栈。否则进入④。

④若所有MV一致，则不加入划分模式，否则仅将HTT加入栈。

（6）结束初始化CU。

2.3 CU划分深度的提前终止

2.3.1相邻CU空域相关性分析

目前很多视频编码快速算法研究利用编码CU的空域相关性加速其划分过程，如文献[12]在HEVC中利用尺寸相近的相邻CU的深度提前终止CU划分。在VVC以前的视频编码标准中，具有同样划分深度的块意味着具有同样的尺寸，因此可以直接参考相邻块的深度来辅助编码CU的划分。但VVC由于引入了更灵活的块划分机制，相同深度下块的尺寸很有可能不相同。在VTM10.0中，当前CU深度值用currDepth来描述，其数值表示经历过的划分次数。例如当前CU经历过2次QT划分，2次BTT划分，那么currDepth为4，此时的CU长和宽分别为32和8。但如果经历了4次QT划分，currDepth为4，但是此时的CU的长和宽都为8，与前者在尺寸上相差了4倍。因此想要找到与当前CU尺寸相近或相同的块，应直接比较长和宽的值，而非深度值。

由于图像相邻像素空域相关性强，相邻CU的最优预测模式通常会呈现较高的一致性。例如，序列中如果一个区域纹理简单，运动缓慢，则该区域的CU很大可能以skip模式作为最优的预测模式；如果一个区域的运动有一致性，则该区域CU可能以Merge模式作为最优预测模式；但某个区域有突然出现的物体，由于参考帧中没有对应的像素块，该区域的CU会选择帧内预测作为最优预测模式。为了统计相邻CU的空域相关性，本文选取了如表1所示的四个特征不同的序列，对于每个CU以及相邻尺寸相同CU的最优预测模式进行了统计。

表1 四种测试序列及其特征Table 1 Four test sequences and their features

本文在统计时，考虑了当前CU的左、左下、左上、上、右上五个方向的相邻CU的预测模式信息。在RA模式下，量化参数（quantity parameter，QP）取22，27，32，37，每个序列测试两个GOP（32帧）。统计在与当前CU有两个及以上相同尺寸CU的前提下，这些同尺寸CU的最优预测模式与当前CU最优预测模式相同的概率，I帧的数据不计入结果，统计数据如表2所示。

表2 同尺寸CU预测模式相同的概率Table 2 Probability of same size CUs having same prediction mode %

由表2可知，在四个不同QP值下，相邻同尺寸CU与当前CU预测模式相同的概率分别为80.45%、76.60%、74.71%和75.30%。可以看出在空间上相邻CU的预测模式具有较高相关性。但相关性与序列运动特性有关，如运动剧烈的RaceHorses序列，这种相关性相对要小些；而运动复杂程度一般，且纹理简单的Johnny序列，则相关性相对更大。

根据表2的统计结果，由于图像中相邻像素在空域的相关性，同尺寸相邻CU的预测模式具有较高的参考价值，若它们的最优预测模式与当前CU相同，则当前的划分深度可能是最优深度，不必继续向下划分。在对CTU的率失真优化过程中，编码器会选择RD-cost最小的划分结果作为最优划分。公式（3）是RD-cost的计算公式：

其中，J即是RD-cost；R是编码比特率，用来衡量编码效率；D是失真，衡量重建块与原始块的差别。如果将CU划分得更小，失真这一指标会明显降低，但另一方面需要表示该CU信息的比特数会增加，因此RD-cost是一个综合的指标。

2.3.2CU划分深度提前终止算法

根据以上分析可知，在当前CU选择了与相邻同尺寸CU相同的预测模式的前提下，如果RD-cost小于它们的平均值，则可以认为当前块的划分比较合理，进一步划分带来的性能收益可能比较小。针对这种特性，本文提出了划分深度提前终止算法，通过参考相邻CU的尺寸、预测模式以及RD-cost决定是否进入下一深度划分。算法的流程如图9所示。

（1）按照相邻的上、左上、右上、左的顺序获取五个相邻CU的编码信息。

（2）判断是否有两个及以上可用的相邻CU，其判断方式如下：

①如果相邻CU与当前CU尺寸不同，则该CU不可用。

②如果相邻CU最优预测方式与当前CU不同，则该CU不可用。

（3）按照公式（4）计算RD-cost的平均值AvgCost，

其中CurCost是当前CU的RD-cost，n为相邻可用CU的个数。

（4）如果当前CU的RD-cost小于平均RD-cost，则停止划分，否则进一步划分。

3 实验结果及分析

本文算法在VTM10.0上进行了实现，并在配置为Intel®CoreTMi7-9750H CPU的Windows10平台上进行了测试。按照CTC标准，在RA模式下，GOP为16，CTU为128×128，每32帧中有一帧是I帧，其他为B帧。测试序列分为B，C，D，E，F这5个类型共20个测试序列，量化参数QP分别取22，27，32，37。以BD-BR（Bjntegaard delta bit rate）和BD-PSNR（Bjntegaard delta peak signal to noise ratio）[17]分别表示本文提出的算法与原平台在编码效率和图像质量的变化。BD-BR越高，说明编码效率损失得越多，BD-PSNR越接近0，说明图像质量损失越小。ΔT表示本文算法的编码时间相较于原平台编码时间的提升百分比，公式（5）是其计算公式，其中TVTM10.0和Tproposed分别表示VTM10.0和采用本文算法的编码时长，QPi对应在不同QP值下进行测试的数据。

最终测试结果如表3所示。

表3 本文算法与VTM10.0对比Table 3 Performance comparisons with VTM10.0

对比VTM10.0算法，在RA模式下，本文提出的算法在编码时间上平均减少了39.28%，而视频的平均PSNR损失为0.05 dB，平均输出比特率增加了1.62%。针对高分辨率视频序列，加速性能较好。对于如RaceHorses，BasketballDrive这类运动剧烈的序列，编码效率和图像质量损失相对较大。对于Kimono，BQMall这类运动平缓的序列，在编码速度上有较大的提升。测试数据表明，在RA模式下，本文算法能够有效降低编码复杂度，加速帧间编码的过程。

文献[8]使用三帧差分算法实现帧间编码的加速，同样利用了GOP中帧与帧之间的时域相关性。由于文献[8]的测试平台是较早VTM3.0版本，因此将本文所提算法移植到VTM3.0中进行了性能测试。并且在F序列中，改用了与文献[8]相同的ChinaSpeed，另外由于文献[8]没有给出BD-PSNR指标，因此本文也没列出该项指标。

比较结果如表4所示。BQTerrace，BQSquare，Basketballpass这类摄像头运动拍摄的测试序列由于视频中静止的区域较少，因此文献[8]算法的加速效果相对较差，而本文算法加速性能较好；对于运动和纹理简单，纹理简单的FourPeople，Johnny，SlideEditing序列，本文算法要略好于文献[8]算法。而针对运动复杂，纹理复杂的RaceHorses，BasketballDrive，本文算法在BDBR上的损失较小。从平均结果来看，在VTM3.0平台上采用本文算法，可实现37.23%的编码速度提升，相较于文献[8]算法编码速率提速了5.8%，但编码输出比特率增加了0.23%。

表4 本文算法与文献[8]对比Table 4 Performance comparisons with paper[8]

4 结束语

本文针对VVC编码复杂度过高的问题，提出了一种基于时空域的CU划分快速算法。首先利用时域参考帧MV分布特性，筛选掉部分划分模式，减少需要遍历的分支。然后，分析当前CU与空域相邻同尺寸CU预测模式的一致性，决定是否进入下一深度进行遍历，减小了CU划分的深度。实验结果表明，在输出比特率上升有限，视频质量损失很小的前提下，本文算法明显降低了编码复杂度，加速了编码过程。