基于SVM的VVC帧内快速CU划分算法

本文为媒矿工厂发表的技术文章

论文标题：SVM Based Fast CU Partitioning Algorithm for VVC Intra Coding

发表会议：ISCAS2021

作者：武国庆

原文链接：https://ieeexplore.ieee.org/document/9401614（或点击阅读原文跳转）

2020年7月，联合视频专家组 (JVET) 完成了新的H.266/VVC视频编码标准。 VVC 采用了一种名为QTMT新的块划分结构，以提高编码效率。然而，与 HEVC 相比，新的块划分结构增加了大量的编码时间。为了降低编码复杂度，我们对VVC帧内编码提出了一种基于支持向量机（SVM）的快速 CU 划分算法，该算法通过使用纹理信息预测 CU 的划分来提前终止冗余划分。我们为不同大小的 CU 训练分类器，以提高准确性并控制分类器本身的复杂度。为每个分类器设置不同的阈值以实现编码复杂度和 RD 性能之间的权衡。实验结果表明，该方法可以节省编码器时间 30.78% 到 63.16%，BDBR 增加 1.10% 到 2.71%。

01

PART

Introduction

联合视频专家组（JVET）于 2020 年 7 月宣布完成VVC视频编码标准。 与之前的视频编码标准HEVC相比，VVC 在相同感知质量下可实现约 40% 的编码效率提升质量[1]。然而，VVC 的复杂度比HEVC高约18倍[2]。

VVC 采用了一种名为QTMT（四叉树嵌套多类型树）新的块划分结构来提高编码效率。多类型树结构包括竖直二叉树划分（BV）、水平二叉树划分（BH）、竖直三叉树划分（TV）和水平三叉树划分（TH）。QTMT允许编码树单元（CTU）在类似于HEVC的递归四叉树（QT）划分的基础上通过二叉树（BT）或三叉树（TT）进一步划分，如图1所示。

为了找到最优分区，VTM 遍历所有可能的划分，然后选择 RD cost最小的作为最终划分结果。这种暴力的 RDO 过程会导致巨大的编码复杂性，编码时间的 95% 以上都集中在具有嵌套多类型树 (QTMT) 分区的四叉树上[3]。

02

PART

方法

为了对VVC的划分有一个数学统计上理解，以指导加速算法的设计，我们统计了每个CU大小的划分信息。所有 VVC 测试序列均用 VTM-10.0进行编码，使用 All-Intra (AI) 配置和默认时域采样率（8帧）。表1显示了 VTM-10.0 的每个 CU 大小的划分比率。我们注意到，大多数不同大小的 CU 倾向于选择不划分 (NS)，尤其是矩形 CU。这意味着在这种情况下，如果编码器可以跳过分区过程，直接进行帧内预测，则可以节省大量的编码时间。此外，三叉树分区（包括TH和TV）仅占分区的一小部分，而水平划分（HS，包括BH和TH）和竖直划分（VS，包括BV和TV）占的比例更大。因此，在快速划分算法中，在不检查RDO过程的情况下预测是水平划分还是竖直划分及其重要。

基于上述，提前预测CU是否划分以及是水平划分还是竖直划分可以减少巨大的编码复杂度。是否划分以及是水平划分还是竖直划分都是二分类问题。我们使用 SVM 作为我们的分类器，其可以很好地处理非线性分类问题。快速划分算法在 CU 划分的过程中是递归的，如图 2 所示，具有两个名为 S-NS 和 HS-VS 的二元分类器。在对 CU 进行编码之前，我们利用 CU 深度和大小的限制来确定当前 CU 是否可以进一步划分，然后使用分类器 S-NS 和 HS-VS 预测进一步的划分结果。

考虑到 CU 大小不同，我们针对不同大小的 CU 训练了不同的分类器。这种设计的好处是对不同大小的 CU 进行单独训练可以提高分类器的预测精度，并且可以减少特征和支持向量的数量，从而减少 SVM 预测带来的overhead。我们将大小为 MxN 和 NxM 的 CU 视为相同类型的 CU (M>N)，并且仅针对大小为 MxN 的 CU 训练分类器。对于大小为 NxM 的 CU，我们只需要在采用我们的预测算法之前进行转置预处理。事实上，实验结果表明，直接确定大CU（如64x64）的划分模式会导致编码性能的巨大损失。此外，小 CU（如 8x4、16x4、32x4、8x8）不会占用太多编码时间，因此无需为这些 CU 实现快速算法。最后，我们决定使用我们提出的算法确定大小为 32x32、16x16、32x16、32x8、16x8 的 CU 的划分。

在 VVC 中，QTMT 划分结构与图像纹理密切相关。一般来说，纹理复杂的区域往往会被进一步划分。此外，复杂的纹理也能反映CU划分的方向。如果水平方向的纹理复杂度高于垂直方向的纹理复杂度，则CU更倾向于水平划分，反之亦然。基于以上思路，考虑到特征计算的复杂性，我们选择以下特征：

lQP：当前CU的量化参数。

lVar：当前CU像素值的方差。

lGrad：当前CU的梯度，包括水平梯度Gradx和竖直梯度Grady。

lGradm：当前CU的最大梯度值。

其中Gradx，Grady和Gradm计算过程如下

除了全局纹理特征，sub-part纹理特征也可以用于预测CU划分。我们使用两个局部特征：

lFb：水平二叉树划分的两个sub-part的特征值与垂直二叉树划分的两个sub-part特征值的差异，包括Fb(Var)，Fb(Gradx)，Fb(Grady)。

lFq：四叉树划分中每两个sub-part的特征值之间的最大差异，包括Fq(Var)，Fq(Gradx)，Fq(Grady)。

我们使用最大互信息系数（MIC）来评估所选特征。MIC用于衡量两个变量之间的相关程度，比Mutual Information具有更高的准确度。图3显示了分类器 S-NS 和 HS-VS 的所有评估特征的 MIC。我们按照分类器 MIC 值的降序选择特征，同时避免特征冗余。分类器 S-NS 的特征集由 8 个特征组成：QP、Var、Gradx、Grady、Gradm、Fq(Var)、Fq(Gradx)、Fq(Grady)。分类器 HS-VS 的特征集由 6 个特征组成：QP、Gradx、Grady、Fb(Var)、Fb(Gradx)、Fb(Grady)。

03

PART

实验

机器学习的有效性与训练数据集的多样性和相关性密切相关。训练序列包括：FoodMarket4、DaylightRoad2、BasketballDrive、RaceHorsesC、BQSquare、Johnny。这些序列被证明具有良好的空间信息和时间信息分布。均用 VTM-10.0进行编码，使用 All-Intra (AI) 配置和默认时域采样率（8帧）。

SVM分类器的预测过程是计算当前特征向量与所有支持向量的内积之和。因此，SVM 分类器的支持向量数量决定了预测过程的复杂程度。为了在保证预测精度的同时控制分类器自身的复杂度，我们将训练子集的大小设置为200个数据，并使用交叉验证的方法来确定最优子集。因此，分类器的支持向量数不会超过200，在减少大量冗余支持向量的同时，预测精度不会显着下降。

为了提高分类器的鲁棒性，我们为每个分类器设置了不同的阈值，以实现编码复杂度和 RD 性能之间的权衡。当预测概率小于阈值时，CU 将选择执行完整的 RDO 过程以避免不必要的 RD 性能损失。图 4 给出了所有分类器中随着阈值变化的预测精度结果。根据经验，我们选择85%准确率对应的值作为每个分类器的阈值。

提出的快速划分算法在 VVC 参考软件 VTM-10.0 上实现以评估性能。表 II 显示了与 VTM-10.0 相比所提出算法的实验结果。分类器HS-VS在所有序列编码性能相似，平均复杂度降低了53.24%，BDBR增加了1.66%。对于分类器 S-NS，节省了 30.78% 的编码时间，增加了 1.10% 的 BDBR。实验结果表明，与VTM-10.0相比，所提出的算法可以降低约63.16%的计算复杂度，RD性能损失为2.71%。这些结果表明，与有关降低复杂性和性能的相关工作相比，我们的算法提供了具有竞争力的结果。

04

PART

参考文献

[1] S. L. B. Bross, J. Chen, Versatile Video Coding (Draft 10). JVETS2001, 2020.

[2] S. K. J. Chen, Y. Ye, Algorithm description for Versatile Video Coding and Test Model 10 (VTM 10). JVET-S2002, 2020.

[3] Tissier et al. “Complexity reduction opportunities in the future vvc intra encoder,” MMSP, 2019.