对 HEVC CU深度快速选择方法的思考和实践

导语 ：本文主要讲解了HEVC中CU深度的快速选择方法，分析了当前编码中存在的问题，提出解决方案，并给出了具体的实践流程，及得到的收益。文档涉及到了机器学习，目的想将视频压缩与机器学习相结合，做一个跨界尝试。

期望目标

在质量轻微下降的情况下，提升编码速度，降低计算的复杂度，从而降低对HEVC实时编码机器的要求。

技术背景

未来视频的发展趋势是高清晰度，高帧率，高压缩率，现在普及的H.264压缩方式，在原理上存在一定的局限性，不能适应未来的需求，因此HEVC编码协议应运而生。

但HEVC编码协议，在2013年已经定稿，截止到今天，还不能普及起来，除了还没有浏览器支持的原因之外，一个关键因素是HEVC算法太复杂，对机器性能要求比较高，普通机器还不能达到实时编码的能力。

一个标准的HEVC编码框架如下：

一帧图像送入到编码器，先经过帧内或帧间预测之后，得到预测值与输入数据的残差，然后进行DCT变化和量化，得到残差系数，然后送入熵编码模块输出码流，同时，残差系数经反量化反变换之后，得到重构图像的残差值，然后和帧内或者帧间的预测值结合，从而得到了重构图像，重构图像再经环内滤波之后，进入参考帧队列，作为下一帧的参考图像，从而一帧帧向后编码。

其中，帧内帧间预测时，从最大编码单元（LCU，Largest Code Unit）开始，每层按照4叉树，一层层向下划分，做递归计算。对于每一个CTU，由CU64x64 到CU32x32，由CU32x32到CU16x16，及由CU16x16到CU8x8，总共三个层次的递归过程，然后再逐层比较，选出最优模式的CU划分情况。

问题分析

下图是所有CU划分情况计算之后，选出的最优结果：

从上图示例来看，有些块做了第一层划分之后，就找到了最优的模式，不必再向下计算。实际上有些块第一层都不需要划分，下一层的所有计算都可能是中间参考，没有被最终采用。也就是说，机器做了很多冗余计算。

下面2个图是2个常见场景的CU大小分布情况：

由图，可看出2个1080p系列的CU64x64的占了四分之一以上，也就是说有30%的情况根本不需要坐做CU64x64及后面CU32x32、CU16x16,CU8x8的计算，另外，还有25%的情况不需要做CU32x32，及后面的CU16x16,CU8x8的计算，还有23%的情况不用再做CU16x16，及后面CU8x8的计算，因此，可以看出，CU划分这块有很大的优化空间。

但是，如果不计算，没有比较又怎么能知道当前CU计算是不是有用呢？

因此，问题就转化为怎么找出一个能根据周围已计算块的信息，来预测当前块CU划分的方法。

解决思路

根据一些输入信息，来预测一个未知情况，比较成熟的技术有机器学习、线性分析等。

1、利用神经网络预测

比较常用的是BP神经网络，其框架如下：

在BP神经网络中，单个样本有个输入，有个输出，在输入层和输出层之间通常还有若干个隐含层。一般隐含层取一层。

网络训练时，包含了正向传递和反向传递两个过程。

（1）正向传递过程

设节点

和节点

之间的权值为

，节点

的阀值为

，每个节点的输出值为

，而每个节点的输出值，是根据上层所有节点的输出值、当前节点与上一层所有节点的权值，和当前节点的阀值，还有激活函数来实现。

具体计算方法如下:

（2）反向传递过程

主要是误差信号反向传递过程，假设输出层的所有结果为

，误差函数如下：

而BP神经网络的主要目的，是反复修正权值和阀值，使得误差函数值达到最小。

网络训练完成之后，即可用来预测，预测过程只包含了正向传递过程。

2、利用支持向量机预测

支持向量机(Support Vector Machine，SVM)是一种监督式学习的方法，可广泛地应用于统计分类以及回归分析。它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。

SVM的原理是将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边，建有两个互相平行的超平面。建立方向合适的分隔超平面使两个与之平行的超平面间的距离最大化。其假定为，平行超平面间的距离越大，分类器的总误差越小。

SVM的关键在于核函数。低维空间向量集通常难于划分，解决的方法是将它们映射到高维空间。但这个办法带来的困难就是计算复杂度的增加，而核函数正好巧妙地解决了这个问题。也就是说，只要选用适当的核函数，就可以得到高维空间的分类函数。

中国台湾大学林智仁(LinChih-Jen)博士等开发设计的一个简单、易于使用和快速有效的SVM模式识别与回归的软件包，叫作LIBSVM，可以解决分类问题（包括C- SVC、n - SVC ）、回归问题（包括e - SVR、n - SVR ），以及分布估计（one-class-SVM ）等问题，提供了线性、多项式、径向基和S形函数四种常用的核函数供选择，可以有效地解决多类问题、交叉验证选择参数、对不平衡样本加权、多类问题的概率估计等。

LIBSVM 是一个开源的软件包，需要者都可以免费的从作者的个人主页http://www.csie.ntu.edu.tw/~cjlin/ 处获得。具体使用方法参考附件《LIBSVM 使用方法简介.doc》

3、阈值判断

结合周围块的划分情况，来推测当前块的CU划分情况。比方下列方式，姑且称作rskip算法。

首先，要计算相邻块对应深度的平均代价，然后计算当前块的对应深度的已编码CU的平均代价，最后判断当前块是否要做depth+1的进一步深度划分。

第一步：计算相邻块对应深度的平均代价

取当前CTU 4个相邻位置的CTU，如下图所示，左边、上边、左上角，及右上角4个LCU的CU划分信息，每个LCU的所有深度对应的代价。

计算周围相邻块的平均代价，相邻块按照左边:上边:左上:右上=2:2:1:1的权重计算。

第二步：计算当前CTU内，已经确定的，相同深度CU代价的平均值，记作，Avg_curr_CU_depth1,Avg_curr_CU_depth2,Avg_curr_CU_depth3。

如果当前深度depth=1时，已确定的CU个数为0，则代价cost=0，否则cost为所有块代价的平均值。

其他深度的计算类似，不再累述。

第三步：预测当前CU是否做进一步分割。

定义阈值 Threshold_depth1 = ( Avg_depth1_cost 4 + Avg_curr_CU_depth13)/(3+4);

当前CU做完merge和skip计算之后，其最优模式对应的代价，记作curr_cost_depth1，如果 curr_cost_depth1 < Threshold_depth1,则认为当前CU不需要再做进一步深度划分，否则需要作进一步划分。

Depth=2 和depth = 3的判断过程与depth等于1相同，均取相同深度的代价进行判断。

4、其他

像线性回归、多元线性回归、最小二成回归、fisher判别等多元统计方法均可用于预测，此处不做重点介绍，感兴趣同学可以看看这方面的书籍。

实施方案

在我们实施案例中，采用了支持向量机（SVM）和rskip算法相结合来预测当前块的CU划分情况。流程如下：

如上图所示，当非I帧的当前CTU开始做CU深度划分计算时，先对当前CU块做merge 和 skip的计算，然后判断当前最优模式的残差是否为0，如果为0，说明当前块是skip 块，直接结束CU计算，如果非0，则需要计算CU深度划分计算。接着，判断当前块的深度depth是否为0，如果非0，则执行rskip算法，再根据rskip的结果进一步判断当前块是否做depth+1层的CU计算；如果当前块depth为0，则根据当前块和相邻块来提取特征向量，然后看当前块所在slice 是Bslice还是Pslice，分别调用对应B帧或者P帧的预测模型，然后开始预测，根据预测结果来决定是否进一步做depth+1层的CU计算。

方案效果

最终方案为svm (p cu64+b cu64)+rskip(p cu32+p cu16+ b cu32+b cu16)，对每层CU都做了快速选择，该方案在x265上落地，并进行多序列测试，相比于x265 veryslow模式，编码速度提升了94%，压缩性能下降了3.1%，因此编码器的计算复杂度大大降低。

结论

将机器学习引入到编码器优化上，是个较大胆的尝试，而且从效果来看，编码速度提升显著，且压缩性能下降不多，说明该方法是可取的，这也为后面编码器优化拓宽一个好的思路。