基于机器学习的HEVC快速帧内预测算法研究进展

艾达 卢雪磊 高阳 董久军

摘 要： 高效率视频编码（HEVC）存在帧内预测计算复杂度过高的情况，而机器学习方法在HEVC快速帧内预测算法的研究取得了一定的进展。对近年来常用的机器学习算法在帧内预测快速深度决策和模式决策两方面的应用进行详述，总结比较不同文献提出的机器学习方法在编码性能上的优劣，最后分析机器学习算法在帧内编码应用中存在的问题，为下一步研究提供参考性建议。

关键词： 高效视频编码； 帧内预测； 深度决策； 模式决策； 机器学习； 计算复杂度

中图分类号： TN919.81?34 文献标识码： A 文章编号： 1004?373X（2018）18?0178?04

Advances in research of HEVC fast intra?frame prediction algorithm

based on machine learning

AI Da1， LU Xuelei1， GAO Yang2， DONG Jiujun2

（1. The Key Laboratory of Electronic Information Site?Survey Application Technology of The Ministry of Public Security， Xian University of Posts and Telecommunications， Xian 710121， China；

2. School of Communications and Information Engineering， Xian University of Posts and Telecommunications， Xian 710121， China）

Abstract： In view of the high computational complexity of intra?frame prediction in high efficiency video coding （HEVC）， and a certain progress that the machine learning method has made in research of the HEVC fast intra?frame prediction algorithm， the application of common machine learning algorithms in recent years to the depth decision and mode decision of fast intra?frame prediction is discussed in detail. The coding performance advantages and disadvantages of the machine learning methods proposed in different literatures are summarized and compared. The intra?frame coding application problems of machine learning algorithm are analyzed， which can provide reference suggestions for further research.

Keywords： HEVC； intra?frame prediction； depth decision； mode decision； machine learning； computational complexity

0 引 言

为了适应高清视频在应用中对数据处理能力的迫切需求，新一代视频压缩编码标准高效视频编码（High Efficiency Video Coding，HEVC）[1]应运而生。HEVC引入了一些新的编码技术：基于四叉树划分的编码单元（CU）、预测单元（PU）和变换单元（TU）[2]、35种帧内预测方向[3]、先进的运动矢量预测技术（AMVP）和运动信息融合技术（Merge）以及像素自适应补偿技术等，这些新技术的应用使HEVC可节省近50%比特率[4] 。但在提供相同视频质量前提下比上一代视频编码标准H.264，相应的编码复杂度[5]提高了2～4倍。如何在保证视频质量前提下降低HEVC编码复杂度问题已成为研究热点。

帧内编码作为高效视频编码中一个重要环节，采用了灵活的四叉树分割[6]技术和多角度帧内预测技术，导致帧内编码复杂度极高。目前国内外关于快速帧内编码算法研究主要是从CU快速划分决策和快速帧内预测模式决策[7]两方面进行的。传统方法根据图像相邻块的纹理特性与时空域相关性跳过或终止当前不必要的深度划分，在最优模式的选择上主要也是利用此方法，从而减少了大量率失真代价的计算。

近年来随着人工智能的兴起，机器学习已成为一个热点，其广泛应用于人工智能、模式识别和信号处理。它能从复杂情况的大数据中学习[8]，并给出最优的解决方案。有了这些优良的特性，国内外从事视频编码的研究人员，将机器学习的理论和方法应用到HEVC帧内编码的研究领域。用机器学习的方法替代复杂的率失真计算过程，从而起到保证视频质量的前提下，降低了编码计算的复杂度，取得了一定的成果。

本文详细叙述了常用的机器学习方法在HEVC帧内CU快速划分决策和快速预测模式决策两方面的应用。對各种方法取得编码性能做了总结与比较，提出了机器学习方法在快速帧内编码应用中面临的一些问题，为下一步研究提供参考性建议。

1 机器学习方法在HEVC帧内CU快速划分决策中的应用

机器学习是一门多领域交叉融合的学科，其是人工智能的核心，主要使用归纳、综合，而不是演绎。常见的机器学习算法有许多，根据算法的功能和形式的类似性，把算法分类为支持向量机、神经网络、决策树算法、回归算法、聚类算法、朴素贝叶斯算法等。以上算法已广泛应用在HEVC帧内预测快速算法的研究中。本节具体介绍了几种常用的机器学习方法在CU快速划分决策中的应用。

1.1 CU快速划分SVM算法

由Vapnik提出的支持向量机（Support Vector Machine，SVM）算法是一种解决模式识别的方法[9]。该算法将样本点映射到一个高维特征空间中，通过最大化两个类之间的边界来寻找最佳的分离超平面。将SVM用在帧内编码CU快速划分决策中，主要舍去复杂的率失真计算，降低编码的复杂度。

文献[10]中首先分析了HEVC中CU深度决策过程，将CU深度决策过程建模为三级分层决策问题；其次提出了一种改进的CU深度决策结构，允许每个CU深度决策的性能在编码复杂度和RD性能之间取得均衡；最后，针对最优训练参数确定得到了复杂的RD复杂度模型。该算法比特率增加了1.98%，平均编码时间减少了51.45%。

文献[11]对CU多重纹理信息分析进而对CU四叉树划分进行了剪枝，从而缩小深度划分的区间。第一步应用自定义的图像纹理提取方法提取出编码单元多重纹理特征；第二步利用SVM训练提取的特征参数得到决策函数，在训练过程对训练数集进行标记；第三步使用决策函数对测试集进行预测，根据决策函数跳过前面不必要的划分和提前终止划分。该算法比特率增加了0.84%，平均编码时间减少43.23%。

文献[12]应用SVM将CU分区决策建模为一个二进制分类问题。为了减少异常值的影响以及在发生错误分类时保持率失真（RD）性能，由于错误分類引起的RD损失将作为SVM训练中的权重引入。该算法在随机访问模式（RA）下比特率增加了1.35%，平均编码时间减少44.7%，低延时模式（LD）模式下比特率增加了1.66%，平均编码时间减少了41.9%。

文献[13]应用SVM提取图像有效特征后，SVM将每个CU分类为均匀、复杂和不确定三类。然后，均匀CU可以提前终止，复杂的CU可以跳过，这大大降低了帧内编码的计算复杂度。该算法比特率增加了1.2%，平均编码时间减少了53%。

文献[14]通过使用拉普拉斯透明复合模型（LPTCM）从原始帧中提取二值化异常值系数（SBOC）向量的特征，然后发送到在线训练SVM。 将两个SVM组合以预测CU分区决策，使得编码过程可以显著加快。在全帧内模式（AI）下该算法比特率增加了0.78%，平均编码时间减少了48%。

通过上述对不同文献应用SVM算法编码性能的比较分析可以得到，文献[14]利用SVM将提取的图像特征直接分为三类，从而根据三类不同图像特征确定CU划分情况。与其他技术比较，比特率增加最少，平均编码时间减少符合预期。而文献[10]平均编码时间减少最多，但其比特率增加相应最多。

1.2 CU快速划分决策树算法

决策树算法广泛应用在CU快速分区决策中。决策树算法与支持向量机和逻辑回归算法类似，都是经典的分类方法。前期对收集到的数据处理，利用归纳算法得到决策树，利用生成的决策树对数据进行分析。

文献[15]使用低复杂度属性（例如CU块的均值和方差）实现决策树，提前终止CU划分，避免对整个大小的RDO评估。该算法比特率增加少于0.6%，平均编码时间减少了28%。

文献[16]针对视频纹理特征，选择灰度差分统计（GDS）的熵和绝对转换差值（SATD）的最小值作为两个重要特征，可以在计算复杂度和分类性能之间取得平衡。根据所选择的特征，可以通过离线训练为不同大小的CU构建自适应决策树。所提出的算法在编码效率几乎无损失的情况下，比特率增加忽略不计，平均编码时间减少了34%。

文献[17]使用了一个加权和方法来进行分区决策。利用邻近的CU作为一个参考分区，为当前的CU设置尺寸大小范围。然后，引入随机森林来预测CU尺寸64×64或32×32。在编码之前，在随机森林方案中输入图像块中的像素，并输出决策过程是否停留在当前深度，或者直接跳过当前的CU大小，并开始预测更高的深度。该算法比特率增加了0.80%，平均编码时间减少了48.31%。

通过对不同文献应用SVM算法编码性能的比较分析可以得到，文献[17]通过相邻CU作为参考与随机森林预测相结合。与其他技术比较，比特率增加与平均编码时间减少均达到最优。文献[16]虽然编码比特率增加小于0.6%，但平均编码时间减少最少。

1.3 CU快速划分神经网络算法

神经网络 （Neural Networks） 是一种非参量化的分析技术，使用自适应学习技术来提取异常行为的特征，通过对广泛数据集的训练与测试得出计算机能识别的正常行为。神经网络由大量的处理单元组成，单元间通过带有权值的连接来进行交互。目前，神经网络已有多种模型在HEVC帧内预测中应用。

文献[18]为了预测最佳的编码树单元（CTU）分区，采用3个小神经网络分别应用在各个分区层级上，由各自的有限状态机控制。神经网络从编码线程中经过不断的训练，并在训练完成后立即应用。由于计算复杂度的降低，采用准牛顿训练法[19]，为了减少训练时间，采样采用非零CU深度层次。该算法比特率增加可以忽略不计，编码时间最大可减少65%。

文献[20]利用当前块丰富的图像纹理，因此能够提高预测当前块的准确性。与此同时，对最近三个块的重建也可以加以改进。该算法比特率增加0.70%。

2 机器学习方法在HEVC快速帧内预测模式决策中的应用

2.1 帧内快速预测模式决策树算法

决策树算法已经在帧内CU划分中广泛应用，同样的在帧内编码快速模式选择上也取得了一定研究进展。

文献[21]利用参考像素的方差表示平滑程度，并根据PU参考像素值的平滑程度，自定义三种不同的情况，并根据不同的情况规定其对应的预测模式数量，然后使用机器学习软件平台Weka运行出模式选择的决策树。在训练过程中将PU块作为输入信息，利用所生成的分类决策树预测出各个PU块需要遍历的预测模式，从而不必要每一个PU都遍历35种预测模式，降低了帧内编码的计算复杂度。该算法在高码率情况下，比特率增加了0.25%，平均编码时间减少了大约16.18%，相当于BD?PSNR平均降低大约0.02 dB；在低码率情况下，比特率增加了0.04%，平均编码时间减少了大约20.75%，相当于BD?PSNR平均降低大约0 dB。

2.2 帧内快速预测模式逻辑回归算法

回归算法是采用对误差的衡量来探索变量之间的关系的一类算法。应用逻辑回归算法将帧内编码复杂的帧内运算过程化为分类问题区解决，从而减少了计算量。

文献[22]将CU划分建模为二进制分类问题。逻辑回归方法为划分和不划分提供合适的分类，逻辑回归分类器是通过离线学习预先构建的。此外，考虑了不同的特征，应用基于F?分数的特征选择方法来选择最佳特征。该算法比特率增加了1.29%，平均编码计算复杂度降低了55.5%。

2.3 帧内快速预测模式神经网络算法

卷积神经网络是神经网络中一种高效的识别方法。卷积神经网络已经成为众多科学领域的研究热点之一。由于该网络避免了对图像的复杂前期预处理，可以直接输入原始图像内容，利用卷积神经网络对其进行特征提取，以达到更高的神经网络识别准确率，因而得到更为广泛的应用。近年来学者将卷积神经网络这一特征与帧内编码结合，取得了一定成果。

文献[23]应用卷积神经网络（CNN）来分析源图像块的纹理结构，然后减少CU模式的最大数量。在CNN的结构设计中，通过考虑量化对编码成本的影响，引入了量化参数。进一步优化了CNN训练策略，提高了预测精度。该算法比特率增长了2.66%，节省了63%的编码时间。

文献[24]应用卷积神经网络对一个CU的纹理进行了分析，经过两个卷积层特征提取之后，提高了分类的准确率。最后确定了最优的CU/PU模式的候选模式，以进行详尽的率失真优化处理。该算法比特率增加3.39%，平均节省了61.1%的编码时间。

文献[25]应用卷积神经网络对源视频序列像素内容的训练得出对应的35种预测模式。因此，在没有对所有可用模式进行优化的情况下，将选定的内部预测模式作为一种分类的问题。该算法编码效率的损失可以忽略不计。

文献[26]应用卷积神经网络分析了一个CU的纹理特征，然后在32×32/16×16和8×8/4×4 CU/PU模式对中决定出最可能的候选模式，从而代替了复杂的率失真代价计算过程。该算法比特率增加了2.67%，平均编码时间减少61.1%。通过上述对不同文献应用卷积神经网络的方法可以得知，与其他方法相比，此方法取得平均编码时间减少最多。文献[26]通过直接训练原始图像得出预测模式的结果比特率增加最少，平均编码时间减少最多，是最优方法。

3 结 论

本文详细论述了各种典型机器学习方法在帧内编码快速深度决策与模式选择两方面的应用。通过对各种应用方法的归纳和比较，总结得出，机器学习神经网络算法在HEVC帧内编码应用中平均编码时间减少最多，省去了前期对源图像复杂特征的分类，直接对源图像进行分析。同时目前方法的应用也面临一些问题，如前期对图像纹理进行分类方法仍存在通用性和阈值选择方面的问题；用机器学习方法在训练过程中存在参数选择和个数问题。为此，在下一步研究提出以下参考性建议：

1） 神经网络算法的应用关键是提高预测准确率，对前期输入网络图像特征要求很高，利用图像处理方法对输入图像做一些基本处理，有利于提高预测的准确率。

2） 应用深层次的卷积网络对输入图像做特征提取也能在一定程度上提高分类的准确性，从而在减少编码时间的同时，降低比特率的开销。

机器学习作为科学研究的热门领域，在众多研究人员不懈的努力下，更多符合人工智能的快速幀内编码算法会不断涌现，从而推动视频编码技术快速发展。

参考文献

[1] SULLIVAN G J， OHM J R， HAN W J， et al. Overview of the high efficiency video coding （HEVC） standard [J]. IEEE transactions on circuits and systems for video technology， 2013， 22（12）： 1649?1668.

[2] KIM I K， MIN J， LEE T， et al. Block partitioning structure in the HEVC standard [J]. IEEE transactions on circuits and systems for video technology， 2012， 22（12）： 1697?1706.

[3] LAINEMA J， BOSSEN F， HAN W J， et al. Intra coding of the HEVC standard [J]. IEEE transactions on circuits and systems for video technology， 2012， 22（12）： 1792?1801.

[4] OHM J， SULLIVAN G J， SCHWARZ H， et al. Comparison of the coding efficiency of video coding standards： including high efficiency video coding （HEVC） [J]. IEEE transactions on circuits and systems for video technology， 2013， 22（12）： 1669?1684.

[5] BOSSEN F， BROSS B， SUHRING K， et al. HEVC complexity and implementation analysis [J]. IEEE transactions on circuits and systems for video technology， 2013， 22（12）： 1685?1696.

[6] CORREA G， ASSUNCAO P， AGOSTINI L， et al. Complexity control of HEVC through quadtree depth estimation [C]// Proceedings of EUROCON. Zagreb： IEEE， 2013： 81?86.

[7] MERCAT A， ARRESTIER F， HAMIDOUCHE W， et al. Constrain the docile CTUs： an in?frame complexity allocator for HEVC intra encoders [C]// Proceedings of IEEE International Conference on Acoustics， Speech and Signal Processing. New Orleans： IEEE， 2017： 1163?1167.

[8] 颜松远.机器学习理论及应用[J].计算机工程与科学，2012，34（9）：201.

YAN Songyuan. Theory and application of machine learning [J]. Computer engineering and science， 2012， 34（9）： 201.

[9] CHERKASSKY V. The nature of statistical learning theory [J]. IEEE transactions on neural networks， 1997， 8（6）： 1564.

[10] ZHANG Y， KWONG S， WANG X， et al. Machine learning?based coding unit depth decisions for flexible complexity allocation in high efficiency video coding [J]. IEEE transactions on image processing， 2015， 24（7）： 2225?2238.

[11] 张峻，董兰芳，余家奎.高效率视频编码快速帧内预测算法[J].计算机应用，2015，35（8）：2327?2331.

ZHANG Jun， DONG Lanfang， YU Jiakui. Fast intra prediction algorithm for high efficiency video coding [J]. Journal of computer applications， 2015， 35（8）： 2327?2331.

[12] SHEN X， YU L. CU splitting early termination based on weighted SVM [J]. EURASIP journal on image & video processing， 2013（1）： 1?11.

[13] LIU D， LIU X， LI Y. Fast CU size decisions for HEVC intra frame coding based on support vector machines [C]// Proceedings of International Conference on Dependable， Autonomic and Secure Computing. Auckland： IEEE， 2016： 594?597.

[14] SHAN Y， YANG E H. Fast HEVC intra coding algorithm based on machine learning and Laplacian transparent composite model [C]// Proceedings of IEEE International Conference on Acoustics， Speech and Signal Processing. New Orleans： IEEE， 2017： 2642?2646.

[15] RUIZ?COLL D， ADZIC V， FERN?NDEZ?ESCRIBANO G， et al. Fast partitioning algorithm for HEVC intra frame coding using machine learning [C]// Proceedings of IEEE International Conference on Image Processing. Paris： IEEE， 2015： 4112?4116.

[16] ZHENG X， ZHAO Y， BAI H， et al. Fast algorithm for intra prediction of HEVC using adaptive decision trees [J]. KSII transactions on internet and information systems， 2016， 10（7）： 3286?3300.

[17] DU B， SIU W C， YANG X. Fast CU partition strategy for HEVC intra?frame coding using learning approach via random forests [C]// Proceedings of Asia?Pacific Signal and Information Processing Association Annual Summit and Conference. Hong Kong： IEEE， 2016： 1085?1090.

[18] MOMCILOVIC S， ROMA N， SOUSA L， et al. Run?time machine learning for HEVC/H.265 fast partitioning decision [C]// Proceedings of IEEE International Symposium on Multimedia. Miami： IEEE， 2016： 347?350.

[19] SETIONO R， HUI L C K. Use of a quasi?Newton method in a feedforward neural network construction algorithm [J]. IEEE transactions on neural networks， 1995， 6（1）： 273?277.

[20] CUI W， ZHANG T， ZHANG S， et al. Convolutional neural networks based intra prediction for HEVC [C]// Proceedings of Data Compression Conference. Snowbird： IEEE， 2017： 436.

[21] 祝世平，张春燕.基于机器学习的HEVC帧内模式快速决策算法[J].光电子·激光，2016，27（11）：1199?1207.

ZHU Shiping， ZHANG Chunyan. A fast HEVC intra mode decision algorithm based on machine learning [J]. Journal of optoelectronics·laser， 2016， 27（11）： 1199?1207.

[22] HU Q， SHI Z， ZHANG X， et al. Fast HEVC intra mode decision based on logistic regression classification [C]// Proceedings of IEEE International Symposium on Broadband Multimedia Systems and Broadcasting. Nara： IEEE， 2016： 1?4.

[23] LIU Z， YU X， CHEN S， et al. CNN oriented fast HEVC intra CU mode decision [C]// Proceedings of IEEE International Symposium on Circuits and Systems. Montreal： IEEE， 2016： 2270?2273.

[24] YU X， LIU Z， LIU J， et al. VLSI friendly fast CU/PU mode decision for HEVC intra encoding： leveraging convolution neural network [C]// Proceedings of IEEE International Conference on Image Processing. Quebec： IEEE， 2015： 1285?1289.

[25] LAUDE T， OSTERMANN J. Deep learning?based intra prediction mode decision for HEVC [C]// Proceedings of Picture Coding Symposium. Nuremberg： IEEE， 2017： 1?5.

[26] LIU Z， YU X， GAO Y， et al. CU partition mode decision for HEVC hardwired intra encoder using convolution neural network [J]. IEEE transactions on image processing， 2016， 25（11）： 5088?5103.