基于機器學習的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.