基于决策树的 VVC 快速算法
来源：PCS 2021 Bristol 主讲人：Gosala Kulupana 内容整理：赵研 本文来自 PCS 2021 SS1 的第六场演讲，主要介绍了 Kulupana 等人提出的一种基于决策树的 VVC 快速算法。
目录
- 1. 介绍
- 2. 相关工作
- 3. 提出方法
- 1） CU 级特征提取
- 2） 对特征进行筛选
- 3） 构建随机森林
- 4） 对森林中的决策树进行筛选，优化森林性能
- 5） 制定基于规则的块划分提前停止算法
- 算法整体流程
- 4. 实验设定
- Naive fast VTM encoder
- 5. 实验结果
1介绍
Versatile Video Coding (VVC) 是目前最优的视频编码标准，它具有很高的编码效率，同时也带来了很高的复杂度。为了解决这一问题，Kulupana 等人提出了一种基于机器学习（ML）的 VVC 帧间编码快速算法。
具体来说，要先对每个 CU 进行特征提取，并使用得到的特征训练一组随机森林（Random Forest， RF） —— 分别对 17 种块尺寸构建单独的 RF。随后，对森林中的决策树进行筛选，选出最优的决策树子集（optimal subset），以此提高随机森林的分类准确性。此外，通过引入基于规则的提前停止策略，该方法可以进一步降低编码复杂度。
实验表明，在 VTM-8.0 上使用该方法可以带来 42% 的编码时间节省，而 BD-rate 损失只有 1.26%。
2相关工作
VVC 参考编码器 VTM 中有一些自带的早停机制，可以在一定程度上降低编码复杂度。相比于 HEVC，VVC 的帧内预测复杂度大大提高（约 25 倍），因此现有的许多工作都着力于 VVC 帧内预测加速。
此外，从下表可以看出，VVC 中现有的块划分策略没有在码率和复杂度方面做出很好的权衡（起码与“new tools”相比），因此不论是对帧内预测还是帧间预测的快速算法，大多数工作都会对块划分策略进行改动，以节省编码时间。Kulupana 等人也在这里使用了基于机器学习的块划分预测方法，以做到块划分流程的提前终止。
表 1：相比于 HEVC，VVC 的性能增益来源
3提出方法
整个算法框架包括以下几个部分：
1） CU 级特征提取
对每种块尺寸和每种划分方式都进行特征提取，一共得到 131 种特征；
2） 对特征进行筛选
通过衡量每种划分决策和特征之间的关系，以及各个特征之间的关系，可以筛选掉一些冗余的特征指标。具体来说，如果两种特征之间的相关性很大，那么就丢掉二者中和划分决策相关性小的那个，保留另一个。这样将特征全部处理完之后，将它们按照与划分决策之间的相关性大小进行排序，并从这个有序排列的特征集合中选取一些（这个数量是预先定义的）作为最终的特征集合。该流程如下图所示。
图 1：特征筛选流程
3） 构建随机森林
选用的特征集合决定之后，就可以构建随机森林并进行训练。训练数据来自于 10 个视频序列，分别来自 class A~F, 具体如下图所示。
每个随机森林都包括 40 个决策树，每个决策树的最大深度是 20。此外，每个训练样本的重要性（权重）是不同的，判断错误带来的 RD-cost 损失越大，则该训练样本权重越大。
图 2：训练数据来源
4） 对森林中的决策树进行筛选，优化森林性能
上一步得到的随机森林还要进行进一步筛选，以选出各自最优的决策树子集，提高决策树的分类准确性。该过程如下图所示：为每个随机森林构建两个集合：'Evaluated' 和 'non-Evaluated'，前者的初始值为空集，后者的初始值为整个 RF。随后开始迭代的比较过程，即逐个将 'non-Evaluated' 中的决策树加入到 'Evalueted' 集合中，然后对 'Evaluated' 集合的性能进行评估，得到具备最高准确性的决策树集合。
图 3：随机森林优化流程
图 4：曲线 <分类准确性 - 森林中树的个数>
5） 制定基于规则的块划分提前停止算法
根据编码过程的统计信息，该工作还提出了一系列划分提前停止策略，主要针对于 TT 划分。其基本思路是：如果当前 CU 足够平滑，即截止到 TT 划分测试前，最优的模式是 non-split 模式（除了 INTER_ME 模式和 GEO 模式），就不必进行 TT 划分的测试。然而，比较狭窄的 CU（如
.
,
）则不受上述约束，没有 TT 划分的提前停止。流程如下图所示。
图 5：块划分提前停止算法流程
算法整体流程
提出算法的整体流程如下图所示，其中使用了两个 RF 分类器，分别用于 QT/MTT 的决策和 Hor/Ver 的决策，但是 BT/TT 划分的判断没有使用 RF 分类器，而是通过提前停止策略对 TT 划分进行限制。
图 6：算法整体流程
4实验设定
文中方法在 VTM-8.0 上实现，测试环境为 JVET Random Access CTC，作者还额外测试了一些 Netflix UHD 序列。
根据 RF 中有多少 DT 的输出与整体输出相同，可以将算法分为三个版本（e.g.
意味着与 RF 输出结果相同的 DT 树占比为
）：
- Slow Preset:
under CTC
- Medium Preset:
under CTC
- Fast Preset:
with
(default is 3)
Naive fast VTM encoder
通过关掉 VTM 中的一些工具，可以得到一个称为"naive fast VTM encoder"的 baseline。具体来说，关掉的工具有：Affine, SMVD, AffineAMVR, BCW, MMVD, ISP, SBT 和 MIP。其性能如下图所示。
图 7：naive fast VTM encoder 的编码性能
5实验结果
文中方法的实验测试结果如下图所示。可以看出，随着复杂度的降低，损失也逐渐增大。与 Amestoy 等人提出的方法相比，文中方法的 Slow Preset 在性能和复杂度上均好于 Amestoy 工作中的 Slow Preset；而文中提出的 Medium Preset 和 Amestoy 等人提出的 Fast Preset 具有相近的性能表现。此外，文中方法三种版本的 BD-rate 损失明显好于 naive fast VTM，而 Fast Preset 还可以带来更大的时间节省。
图 8：实验结果
附上演讲视频：