#多叉树深度遍历_结合深度学习的视频编码方法--帧内预测

-- 本文来自于VIP Lab的陈俊安同学撰稿

本文将分为四个部分对基于机器学习的帧内预测进行介绍。第一部分简要介绍帧内预测的流程；第二部分选取近年来国内外学者针对H.265/HEVC帧内预测提出的具有代表性的机器学习算法进行介绍；第三部分介绍了几种针对新一代编码标准H.266/VVC中帧内预测的快速算法；最后一部分做一个简单的总结和展望。本文选取的文章主要针对加速，仅一篇针对性能优化。

1. 帧内预测的基本原理

帧内预测的基本思想是使用一帧图像中相邻像素的相关性来消除空间上的冗余，它主要分为块划分和模式判决两个部分。不做任何加速处理的帧内预测需要对划分进行递归，对模式进行穷举，是一个非常耗时的过程。

1.1 块划分

在HEVC中，块划分以四叉树的形式划分CU，它是判断CU是否需要划分为4个子CU的过程。在这个过程中，编码器首先自上而下遍历LCU的子CU，然后自下而上比较子CU的RD cost与当前深度CU的RD cost。一个LCU的遍历顺序如图1所示。编码器以Z字型按照6464 →3232 →1616→88的顺序处理CU。只有在当前CU所含的所有子CU全都遍历过后，才对当前CU进行处理，通过比较2N2N和NN两种情况下的RD cost，判断当前CU的划分方式。若子CU的RD cost更小，则分割当前CU为4个子CU；若当前CU的RD cost更小，则不继续分割。LCU的四叉树划分如图2所示。

在VVC中，块划分不再局限于原有的四叉树，而是新加入了二叉树和三叉树。一个四叉树节点可以按照图3的5种方式进一步划分，二叉树或三叉树节点则只能按照图3的后4种方式进行划分。判断是否划分的过程与HEVC一致。多叉树的划分方式可以更好地匹配各种不同纹理的图像，但划分种类的增多大大增加了预测时判断最终划分所需的时间。

1.2 模式判决

HEVC中规定了35种帧内预测模式，包括Planar模式、DC模式和33种角度模式。这35种模式基于PU定义，预测过程以TU为单位。帧内模式预测简单概括起来，分为三个步骤：判断当前TU的相邻参考像素是否可用，若不可用则需要按标准中给出的规则进行填充；对参考像素进行滤波；利用滤波后的参考像素值计算出当前TU的预测像素值。

VVC将原有的35种模式扩展到了67种，除Planar模式和DC模式之外，在原来的33种角度模式的每两个之间再插入一个，即一共插入32个新的角度模式。这样一来，编码器可以更准确地描述视频中任意边界的方向，使得编码性能提升，同时毫无疑问，也会增加预测的复杂度。

更多VVC帧内预测内容可参考：https://blog.csdn.net/weixin_42979679/article/details/84172738

随着人们对视频清晰度的需求越来越高，视频编码标准不断改进以寻求以更少的比特编出更优质的画面。通常不可避免的是，在性能大幅度提升的同时，运算复杂度也会大大提升，这对于视频的实时传输十分不友好。正因为如此，视频编码领域的学者针对帧内预测中的计算过程提出了不少快速算法。由于块划分的判决对于编码性能的影响相较于模式判决更为显著，多数研究以加速块划分为主，加速模式判决为辅。

2. HEVC帧内预测中使用的机器学习算法

应用在帧内预测加速方面的机器学习方法大致可以分为两类。一类是传统的机器学习方法，如决策树、支持向量机、贝叶斯决策等；另一类则是神经网络。

2.1 传统机器学习算法

X. Liu等人提出了一个基于SVM的加速算法[1]。该方法以NMSE、DCom、SCCD和QStep这几个特征作为衡量CU的纹理是否复杂的标准。经过分类，CU的复杂度将被归入三种情况，GroupA和GroupB分别表示复杂度高和复杂度低，这是两种不易出错的情况，而GroupC表示复杂度中等。PUMs（PU mode selection）即从35种模式中选取RDO最优的一个。那么再结合下面所示的流程图，在CU被划分为复杂度高的一类时，如果深度≤3，则无需对当前深度进行模式选择，直接进入下一深度的判断；如果CU被划分为复杂度低的一类，则只对当前深度进行模式选择；如果CU复杂度中等，无法明确确定它属于A类或B类，则当前深度和下一深度的模式选择都要进行，以保证编码性能。

原文链接：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8119994

W. Kuang等人提出的是一个基于贝叶斯决策的方法[2]。这个方法是在HEVC的扩展screen content coding（SCC）上实现的。他们使用在线学习的方法来加速块划分和模式判决。首先，提取角点（corner point）作为一个很重要的特征；然后，获取一个CU中不同的颜色数量，使用在线学习来构建一个精准的模型，这个模型用来排除一些不可能的模式。接下来，相邻CU的模式将被用来分析，进一步排除一部分不需要的候选模式。最后，使用贝叶斯决策来选出最佳的划分方式。

原文链接：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8752273

2.2 神经网络算法

近年来神经网络的方法在视频领域非常风靡，这里选择了三篇文章进行总结。

第一篇是2016年发表在TIP的文章[3]。Z. Liu等人利用CNN实现了一个可以支持CU级硬件并行的帧内加速算法。在处理CTU中的CU时，首先根据其大小进行降采样，得到一个8x8的矩阵作为CNN的输入。CNN是一个比较普通的“卷积-池化-全连接”的架构，当然这其中考虑到了QP的影响，所以QP被设置为全连接层的一个神经元，参与权值的分配。CNN的输出就表示CU划分或不划分。由于每次CU划分的判断都与相邻块无关，所以可以很好地实现硬件并行。

原文链接：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7547305

第二篇文章[4]同样发表于TIP，是2018年的。这篇文章给出了一个完全不同的思路。一般在处理块划分问题时，我们倾向于直接判断是否划分，最多加上一个不确定的模糊分类，也就是将问题简化为二分类或三分类问题。这篇文章的作者M. Xu等人则是使用CNN来输出一整个CTU的划分层次HCPM（hierarchical CU partition map）。也就是说，将CTU输入这个网络，可以直接得到整个CTU的划分。当然，CTU在输入网络之前需要做一些预处理。

原文链接：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8384310

第三篇文章发表于Trans. on Multimedia，不同于前文所述的加速算法，在这里，H. Sun等人给出的是一个性能优化的方法[5]。文中提供了两种策略，一种叫appending scheme，另一种叫substitution scheme。从下面两个流程图中显而易见appending和substitution的区别，即前者为在传统的35中模式之外加入NM，后者是用NM来代替一部分传统模式。所谓NM（神经网络模式），指的是使用神经网络作为一种“预测模式”。神经网络的input是参考像素，output是当前块的预测值。该方法相比于之前的方法，Y、U、V分量分别可以节省2.6%、3.8%和3.1%的bitrate。

原文链接：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8947942

3. VVC帧内预测中使用的机器学习算法

VVC作为新一代编码标准，仍在不断改进中。在它被提出之后短短两年时间里，涌现出不少使用机器学习方法加速帧内预测的文章，当然大部分依然是针对块划分的。这里选取DT算法和CNN算法的文章各一篇进行介绍。

3.1 传统机器学习算法

H. Yang等人使用DT的方法[6]进行划分方式的选择。包括块大小、横纵向梯度、上下/左右边界差异、QTMT深度等在内的Global texture information、Local texture information、Context information被提取出来，作为决策树使用的特征。除此之外，这篇文章还做了模式判决主要通过计算MPM的Hadamard cost然后进行梯度下降搜索，最终在MPM中确定唯一的一个候选模式Md。Full RDO只需计算{DC, Planar, Md}这三种模式。文中给出的测试结果是，只加速块划分时，BDBR增加1.56%，编码时间降低52.59%。再加上模式部分的加速，编码器总体的BDBR增加1.93%，时间降低62.46%。

原文链接：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8664144

3.2 神经网络算法

我们实验室使用神经网络方法加速VVC的块划分已经取得了不错的时间和性能的trade-off。这篇文章[7]针对VVC中CU的长和宽可能出现的各种情况，将CNN中的池化窗口大小设定为变量，即根据输入的矩阵大小判断，最后得到同样大小的矩阵，方便处理。

原文链接：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8965679

4. 总结和展望

做帧内方法有很多，哪怕只是使用神经网络，加几个层、调整卷积核的大小、改变数据集等等都可能会获得新的意想不到的收获。这是一个不断尝试的过程，有可能一次成功，也可能接连碰壁。

对于最新一代标准VVC来说，它相比HEVC的不同之处是在研究中很重要的点，譬如块划分中新加入的multi-type tree（MT）。原来的HEVC仅有QT一种划分方式，所以只需要判断CU是否继续划分。而VVC有5种划分方式，所以不仅仅是划不划分的问题，还要判断该如何划分。如何处理非对称块（长方形块）的划分也是很有意思的问题。

参考文献

[1] X. Liu, Y. Li, D. Liu, P. Wang and L. T. Yang, "An Adaptive CU Size Decision Algorithm for HEVC Intra Prediction Based on Complexity Classification Using Machine Learning," in IEEE Transactions on Circuits and Systems for Video Technology, vol. 29, no. 1, pp. 144-155, Jan. 2019.

[2] W. Kuang, Y. Chan, S. Tsang and W. Siu, "Online-Learning-Based Bayesian Decision Rule for Fast Intra Mode and CU Partitioning Algorithm in HEVC Screen Content Coding," in IEEE Transactions on Image Processing, vol. 29, pp. 170-185, 2020.

[3] Z. Liu, X. Yu, Y. Gao, S. Chen, X. Ji and D. Wang, "CU Partition Mode Decision for HEVC Hardwired Intra Encoder Using Convolution Neural Network," in IEEE Transactions on Image Processing, vol. 25, no. 11, pp. 5088-5103, Nov. 2016.

[4] M. Xu, T. Li, Z. Wang, X. Deng, R. Yang and Z. Guan, "Reducing Complexity of HEVC: A Deep Learning Approach," in IEEE Transactions on Image Processing, vol. 27, no. 10, pp. 5044-5059, Oct. 2018.

[5] H. Sun, Z. Cheng, M. Takeuchi and J. Katto, "Enhanced Intra Prediction for Video Coding by Using Multiple Neural Networks," in IEEE Transactions on Multimedia.

[6] H. Yang, L. Shen, X. Dong, Q. Ding, P. An and G. Jiang, "Low Complexity CTU Partition Structure Decision and Fast Intra Mode Decision for Versatile Video Coding," in IEEE Transactions on Circuits and Systems for Video Technology.

[7] G. Tang, M. Jing, X. Zeng and Y. Fan, "Adaptive CU Split Decision with Pooling-variable CNN for VVC Intra Encoding," 2019 IEEE Visual Communications and Image Processing (VCIP), Sydney, Australia, 2019, pp. 1-4.