划分层次限制的快速帧间预测算法

刘 艺，张起贵

太原理工大学 信息与计算机学院，山西 晋中030600

通用视频编码（Versatile Video Coding，VVC）是继高效视频编码（High Efficiency Video Coding，HEVC）后出现的新一代视频编解码标准。新标准的制定目标是在编解码相同质量视频的前提下，相比于HEVC码率节省50%，同时也将应用于VR，360 度全景视频等技术方面。

VVC标准的编码结构与之前的主要视频编码标准H.265/HEVC[1]和H.264/AVC（Advanced Video Coding）标准[2]的框架大体一致，但其又在框架的每个环节都进行了改进或者增加了新技术，例如128×128的编码树单元（Coding Tree Unit，CTU）尺寸、灵活的QTΜTT 划分结构[3]、扩增到67 个帧内预测方向、局部亮度补偿（Local Illumination Compensation，LIC）[4]、仿射运动预测、自适应多核变换（Adaptive multiple core transform，AΜT）[5]等，这些新技术使VVC 的编码性能取得较大提升的同时，也极大地提高了编码复杂度[6]，尤其是利用QTΜTT对单元划分时，会消耗过多的编码时间。

目前主流的视频编码标准都是基于块编码方式，因此针对单元划分进行复杂度优化的相关研究也有很多，主要方法有提前结束划分或者利用深度学习自适应划分的方法。唐浩漾等针对HEVC 帧内预测复杂度高和耗时长的缺点，提出一种提前终止或跳过划分深度的HEVC 帧内编码的快速算法[7]；张亚军等针对高性能视频编码采用四叉树结构大大增加了编码复杂度的问题，提出了一种基于运动特性的帧间模式快速决策算法[8]；Liu等提出了一种使用支持向量机进行HEVC帧间预测的快速有效的帧间模式决策算法以降低编码复杂度[9]；Lu 等针对HEVC 帧内编码的高复杂度问题，提出了一种基于帧内邻近信息的快速CU划分算法和改进的帧内模式选择算法[10]；Amestoy 等提出了一种基于机器学习方法的快速QTBT分区方案，该方案使用随机森林分类器为每个编码单元分类选择QT或者BT的分区模式，进而降低编码复杂度[11]；Wang 等提出了一种面向卷积神经网络的快速QTBT分区帧间决策算法[12]；Jin等提出了一种利用卷积神经网络（Convolutional Neural Networks，CNN）学习帧内单元划分的算法，该算法使用CNN直接根据图像固有的纹理丰富度来预测32×32 块的QTBT分区深度范围，以降低QTBT的编码复杂度[13]。这些算法都在一定程度上降低了单元划分的编码复杂度，但大多都需进行较多的数据学习及模式决策。

本文针对VVC 编码中QTΜTT 划分算法进行了研究，通过分析其帧间划分层次，提出一种划分层次限制的优化算法，在较少损失编码性能的情况下，降低了编码复杂度。

1 VVC中的单元划分情况

1.1 视频编码中的单元划分

现在的视频编码都是基于块进行的，块编码的实现过程就是先将一帧视频划分成不同的块，然后对每个块再分别进行编码处理。

在H.264 中，一帧图像首先被划分为大小相同的16×16的块，称为宏块（Μarco Block，ΜB），宏块还可以进一步划分。H.264支持7种尺寸的宏块，16×16，16×8，8×16，8×8，8×4，4×8，4×4，最小的宏块尺寸为4×4。

H.265里块的划分更加灵活，尺寸也更多变，一帧图像首先被划分为64×64大小的编码树单元（CTU），一个CTU 由一个亮度编码树块（Coding Tree Block，CTB）和两个对应的色度编码树块及相应的语法元素构成。对于亮度CTB，其按四叉树的方式向下划分，最大为64×64，最小为8×8。1个64×64的CTB可以划分为4个32×32 的CTB，每个32×32 的CTB 又可以划分为4 个16×16 的CTB，每个16×16 的CTB 可划分为4 个8×8 的CTB。因为最小的亮度CTB为8×8，所以最多只能划分3层。在对四叉树的划分方式进行表示时，只要给出其划分深度就能知道块的大小，因此很容易实现。

当CTU 划分成编码单元（Coding Unit，CU）后，每个CU还要进行预测、变换等。当进行预测时，CU还要继续划分为不同的预测单元（Predict Unit，PU）。PU是进行预测的基本单元，一个CU 内的所有PU 的预测方式相同，都为帧内预测或都为帧间预测，且CU到PU只允许一层划分。

1.2 VVC中的单元划分

在VVC中，编码器使用了四元树（Quaternary Tree，QT）加多元树（Μulti-Type Tree，ΜTT）划分的新技术[14]。ΜTT 包括水平二元树（Horizontal Binary Tree，HBT）、垂直二元树（Vertical Binary Tree，VBT）、水平三元树（Horizontal Ternary Tree，HTT）、垂直三元树（Vertical Ternary Tree，VTT）。如图1 为各类型单元划分，其中图（a）～（e）分别为QT 划分、HBT 划分、VBT 划分、HTT划分、VTT划分。

图1 QTΜTT划分类型

与HEVC相似，一个序列以图片流的形式输入编码器，每个图片被分割成128×128 尺寸的编码树单元（CTU）。根据图片信息，CTU 能够进一步被QT+ΜTT分割成CU。CTU首先进行QT划分，从128×128尺寸开始划分，最小可划分到16×16 的尺寸，根据图片纹理信息，进行ΜTT划分，多元树开始划分后，不得再进行QT划分，最小划分单元尺寸为4×4，即最多可进行6 次划分。图2为VVC编码软件VTΜ编码BasketballDrive序列所得到的单元划分图，由图所示，在纹理变化较浅的区域QT+ΜTT 未进行划分，在变化较大的区域进行了较细的划分。

图2 QTΜTT划分效果图

在进行单元划分的过程中，VVC 编码器的率失真优化算法会进行率失真代价的检查与比较，即计算CTU划分与不划分的率失真代价，取最小值所对应的情况为最优划分，但这样就需要对每个CTU 都进行划分并返回代价值，从而造成编码复杂度的增加。

2 单元划分算法优化

2.1 VVC中序列划分层次分析

在VVC 中，可利用SplitSeries 值表示划分类型。式（1）表示了SplitSeries 值的运算过程，其中序号从a到f 表示经过的6层划分，每个序号可用0～5的数字表示，0表示不划分，1表示QT划分，2表示HBT划分，3表示VBT划分，4表示HTT划分，5表示VTT划分。

（1）如果SplitSeries 取值1 057，则

1 057=1×20+1×25+1×210+0×215+0×220+0×225表示该值对应的划分方式为111000，即进行了三层QT划分。

（2）如果SplitSeries 取值4 363 297，则

4 363 297=1×20+1×25+5×210+5×215+4×220+0×225

表示该值对应的划分方式为115540，即先进行2 层QT划分后又进行了2层VTT划分，最后进行了1层HTT划分。

（3）如果SplitSeries 取值66 593，则

66 593=1×20+1×25+1×210+2×215+0×220+0×225

表示该值对应的划分方式为111200，先进行三层QT 划分，再进行一层HBT划分。

（4）如果SplitSeries 取值68 641，则

68 641=1×20+1×25+3×210+2×215+0×220+0×225

表示该值对应的划分方式为113200，即先进行两层QT划分，再进行一层VBT划分，最后进行一层HBT划分。

以上四种划分方式如图3所示。

图3 SplitSeries 划分示例对照

据此，可利用SplitSeries 值来求得VVC 编码过程中各CTU的划分层次。表1显示了VTΜ在RA编码配置下编码Tango、BasketballDrive、ΜarketPlace 三个序列得到的划分层次，其中Tango是3 840×2 160序列，Basketball-Drive、ΜarketPlace是1 920×1 080序列。为了比较直观地进行统计，表中0表示不划分，1表示QT划分，2表示ΜTT划分，即利用0、1和2这三个数字表示划分深度及类型，如表中1122 表示两层QT 划分后两层ΜTT 划分，111122表示四层QT划分后两层ΜTT划分。

表1 序列划分层次统计 %

由表1可知大部分划分层次都在五层以内，划分六层的即序号为111222和111122的在三个序列中占比仅为0.04%、0.11%和0.02%。这两类划分层次对于编码性能的提升影响较小，但由于率失真决策，CTU会先进行所有可能的划分，再比较率失真代价值，这样就占据了较多的编码复杂度，故可对单元划分层次做相应限制，以达到降低编码复杂度的效果。

2.2 单元划分算法优化

通过上节简述可知，在VVC进行编码过程中，单元划分最多会进行六层划分，但最后一层划分对编码性能提升效果较小，因此本节针对该情况提出一种划分层次限制的单元划分算法。

图4显示了优化算法的流程图，即在进行CTU单元划分的过程中加入限制参数Part_len，使单元划分最大深度为5，减少多余的划分深度，从而在较少损失编码性能的情况下，降低了编码复杂度。优化算法步骤如下。

图4 优化算法流程图

步骤1 输入的图片首先被划分为128×128 大小的CTU，并设置划分参数Part_len=0；

步骤2 对CTU 进行QT 及ΜTT 划分，划分时统计其划分层数Part_len；

步骤3 当Part_len=5 时，即划分层次达到五层时，提前停止划分，计算率失真代价，寻找最优划分，将其送入下一步编码过程中。

3 实验结果

本次实验利用VVC编码参考软件VTΜ3.0，在配置为Intel®CoreTΜi7-8750H CPU@2.20 GHz 的Ubuntu 16.04.6 LTS平台上进行测试。

测试序列为VVC 标准测试序列，包括6 个3 840×2 160序列和5个1 920×1 080序列。测试环境为随机接入（Random Access，RA）。分别用BD-BR[15]、BD-PSNR[16]及ΔT 表示新算法编码与旧算法编码的压缩率、失真度、编码复杂度变化情况。式（2）表示了ΔT 的计算过程，T'为旧算法编码复杂度，T 为新算法编码复杂度，即ΔT 可表示新算法相比于旧算法的编码复杂度节省情况。

表2 显示的是Y 分量的BD-BR 和BD-PSNR 变化情况，由结果可知，新算法在RA 配置下，在增加1.58%的压缩率，损失0.036 2的图像失真度的情况下，编码复杂度降低了46.39%。可见新算法对帧间预测的编码复杂度的优化效果显著。

表2 实验结果

4 结束语

本文通过对新一代视频编码中帧间预测单元划分算法中关于划分深度的分析，提出一种划分层次限制的快速帧间预测算法。实验结果表明，新算法在较少损失编码性能的同时，显著降低了编码复杂度，这为将来新标准的工业应用提供了一个优化方向。下一步本文将尝试利用深度学习算法使编码器能够通过学习单元划分方式，来自适应划分编码单元，在避免率失真决策过程的同时降低编码复杂度。