一種HEVC幀內預測快速算法

張新晨,肖秀秀,趙 婭,黎 偉,江 昊,肖進勝

(1.華中師范大學物理科學與技術學院,武漢430079;2.武漢大學電子信息學院,武漢430072)

一種HEVC幀內預測快速算法

張新晨1,肖秀秀1,趙 婭1,黎 偉2,江 昊2,肖進勝2

(1.華中師范大學物理科學與技術學院,武漢430079;2.武漢大學電子信息學院,武漢430072)

HEVC作為新一代的視頻編碼標準,比現有H.264標準的壓縮效率提高近一倍,但其存在復雜度較高的問題。為此,針對HEVC中幀內預測最耗時的模塊,即編碼單元塊劃分模塊和幀內預測模式選擇模塊,提出一種適合HEVC幀內預測的快速算法。該算法將率失真(RD)代價作為閾值參數,利用候選模式集中預測模式被選中概率快速遞減的規律,基于RD代價進行幀內預測塊劃分和幀內預測模式選擇。實驗結果表明,該算法在相同編碼質量條件下可減少59%的HM10.0幀內預測模塊復雜度,相應比特率的增加幅度小于1.34%。

視頻編碼;HEVC標準;幀內預測;塊劃分;模式選擇

1 概述

2013年1月,JCT-VC新一代視頻編碼標準HEVC正式發布,作為現行標準H.264/AVC的替換標準,該標準應用支持視頻分辨率從320×240像素至7 680×4 320像素,與H.264/AVC的高檔次編碼配置(High Profile)的編碼性能相比,能提高近一倍的編碼壓縮效率[1-2]。

但HEVC在獲得更高性能的同時,也無可避免地增加了計算復雜度,在幀內編碼過程中,采用了四叉樹遞歸編碼單元結構以及采用枚舉法遍歷35種幀內預測模式找出最佳模式[3],其計算復雜度成倍的增加導致HEVC不能有效地應用于實時通信應用。因此,在保持HEVC視頻主客觀質量的前提下,有效地降低計算復雜度是普及HEVC視頻編碼標準和將其商業化應用的關鍵所在[4-5]。

本文基于率失真(Rate-distortion,RD)代價函數提出一種提前終止四叉樹的幀內預測塊劃分方法,并利用圖像相關性選取候選預測模式集進一步降低預測模式選擇的計算復雜度。

2 HEVC幀內預測

HEVC參考模型(HM10.0)[6]采用樹形結構和遞歸模式進行編碼單元(Coding Unit,CU)塊的劃分,對于幀內預測模式來說,CU塊的深度優先遍歷遞歸從樹根最大編碼單元(Largest Coding Unit, LCU)(64×64)開始,依次出發搜索它的每個鄰接點(4個32×32的子CU塊),若鄰接點未曾訪問過,則以它為新的出發點繼續進行深度優先遍歷,一直遞歸至4×4大小的塊,直至四叉樹中所有節點均被訪問為止,四叉樹深度優先搜索結束[7-8]。

參考模型深度優先遍歷四叉樹的每個節點,計算出四叉樹上每個節點的權重,即當前層次編碼單元CU的率失真代價RDCost。如果當前編碼單元CU所劃分的4個子CU的RDCost之和大于當前編碼單元CU自身的RDCost,則當前CU在編碼的時候不需要做劃分;否則,當前CU需要劃分。另外,將當前編碼單元CU的RDCost賦值為兩者之間的小者。通過這個算法,計算出使整個 64×64的RDCost最小的劃分路徑,用于編碼。在計算RDCost的過程中,主要采用以下3個步驟[9]獲得每個CU單元的最佳幀內預測模式:

步驟1 對所有34種或17種角度的預測模式,使用基于HAD(Hadamard transform Absolute Difference)的代價函數計算代價,然后按代價值從小到大的順序排列預測模式,選出前若干種代價最小的模式構成一組候選模式。候選模式集中的候選模式的數量如表1所示。

表1 角度幀內預測方向模式和候選模式數量

步驟2 從相鄰編碼單元中推導出最有可能模式(MPM),并將其加入候選模式集中,若候選集中已經有此模式,則不重復加入候選模式集中;否則,將MPM加入候選模式集的末尾。

步驟3 從這些候選模式中,使用基于 SSE (Sum of Square Error)的代價函數計算代價,選出有最小RDCost的模式作為最佳預測模式。

3 幀內預測的優化算法

幀內預測模式計算運算量巨大。幀內模式快速選擇算法的研究作為提高編碼效率的研究重點之一。通過上述HEVC中較為耗時模塊的分析,降低幀內預測算法復雜度可以從以下2個方面進行研究:(1)采用提前終止的思想,預判塊幀內編碼塊類型,節省塊劃分時間;(2)通過一些低復雜度的方法有效地將候選集中不太可能的模式過濾掉[7,10-12],從而減少計算的預測模式數量。

3.1 基于率失真代價的幀內預測塊劃分快速算法

對于當前CU塊的最佳RD代價,需要搜尋在每一個深度CU的每一個可能的模式。但是可以發現,如果當前CU的深度是逼近最優的,停止分裂當前CU只會導致一個微不足道的損失[13],但是速度卻會有一個巨大的提升[14]。

圖1是RaceHorses序列在標準HM代碼下的CU分割結果。在第一個64×64的LCU塊中,當第一個32×32的塊計算出的代價逼近最優模式時,可以停止繼續分割CU,大幅提高編碼速率;在第4個32×32的塊計算出的代價很大時,可以直接確定該塊需要繼續分割成4個16×16的子塊,無需在該32×32的塊中做量化等工作。要確定提前終止的條件,本文使用率失真代價RDCost。

圖1 RaceHorses序列的CU分割結果

通過設定一個閾值,當RDCost小于該閾值時,說明預測效果很好,可以滿足編碼需要,則不需要進一步的判斷以及下一層的遞歸劃分;否則,需要做進一步的判斷和下一層的遞歸劃分。下面將詳細介紹閾值的選定流程。

其中,E表示錯誤率;T是閾值。

因此,滿足dE/dT=0以及d2E/dT2＞0的閾值應該是最佳的閾值,也可以視為2條曲線的交點。

因而,對于每個2N×2N單元,如果ΔC2N大于離線訓練的閾值,則被認為是應該被分割成N×N的塊。否則,2N×2N預測單元大小對編碼這種2N× 2N單元來說是合適的。按照這一辦法,在訓練集中的每個序列和量化參數(Quantization Parameter, QP),只需要一次編碼迭代就能得到一整套閾值,復雜度降低的同時,能得到接近圖1的最佳結果。

本文選擇5種不同分辨率的測試序列進行閾值訓練,如表2所示。對于每一個序列,QP值分別為22,27,32和37。在獲得所有序列的閾值組合后,計算5個序列的平均閾值,最終采用的閾值如圖2所示,有4條曲線對應于4種單元尺寸在不同QP下的閾值。

表2 測試序列

圖2 算法訓練后采用的閾值

以RaceHorses序列為例,在使用上述算法流程改進后的HM代碼下,該視頻序列的CU分割結果如圖3所示。

圖3 RaceHorses序列的CU分割結果

3.2 幀內預測模式快速選擇

本文提出的幀內預測模式選擇快速算法具體步驟如下:

(1)從所有角度模式中,使用基于HAD代價的代價函數,并按代價值從小到大,選出若干個模式構成一組候選模式。

(2)從相鄰編碼單元中推導出最有可能模式MPM,判斷該MPM是否是候選模式集中代價最小的模式,如果是,直接選為最佳預測模式,否則,將其加入候選模式集中,并跳至第(3)步。

(3)從這些候選模式中,選出最小RD代價的模式作為最佳預測模式。

4 實驗結果及分析

本文算法在HM10.0上實現,配置文件選用配置encoder_intra_main.cfg,測試過程中I幀的周期設置為1,所有編碼幀均為幀內編碼。

表3的實驗結果表明,本文算法在幀內預測編碼平均節省58.97%的編碼時間,在PSNR幾乎沒有下降的同時編碼碼率增加了1.34%,這個性能損失值是可以接受的。在不同的分辨率或者序列特征下,可以實現降低幾乎相同的復雜度,表明本文所提出的算法在實時HEVC編碼應用的潛力較大。

表3 塊劃分和模式選擇結合快速算法的性能比較

5 結束語

本文在分析HEVC中幀內預測算法和現有快速算法的基礎上,提出一種提前終止四叉樹的遞歸處理方法,提前終止的判斷參數選用率失真代價,再利用圖像的相關性,對HEVC幀內預測候選模式集中根據概率快速遞減的規律,減少了候選模式數目。最后,針對HEVC幀內編碼在HM10.0參考模型中實現了快速處理算法,降低了原算法的計算復雜度和幀內編碼時間。實驗結果表明,與參考模型中的算法相比,本文算法在不降低編碼質量的情況下進行幀內編碼時縮減了59%的編碼時間,考慮到編碼過程中其他模塊的耗時,幀內預測處理的速度實際上有了成倍的提高。因此,本文提出的針對HEVC幀內預測的快速算法具有較高的實用和研究參考價值。

[1] Bross B,Hhi F.High Efficiency Video Coding(HEVC) Text Specification Draft 10[C]//Proc.of the ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11 12th Meeting.Geneva,Switzerland:[s.n.],2013:14-23.

[2] 劉梅峰,陸 玲.新一代視頻編碼標準HEVC變換方法的研究[J].電視技術,2012,36(1):1-5.

[3] Lainema J,Ugur K.Angular Intra Prediction in High Efficiency Video Coding(HEVC)[C]//Proc.of the 13th IEEE International Workshop on Multimedia Signal Processing.Hangzhou,China:[s.n.]:2011:1-5.

[4] Saygili G,Gurler C G,Tekalp A M.Evaluation of Asymmetric Stereo Video Coding and Rate Scaling for Adaptive 3D Video Streaming[J].IEEE Transactions on Broadcasting,2011,57(2):593-601.

[5] Bossen F,Drugeon V.Video Coding Using a Simplified Block Structure and Advanced Coding Techniques[J]. IEEE Transactions on Circuits and Systems for Video Technology,2010,20(12):1667-1675.

[6] Bross B,McCann K.JCT-VC AHG Report:HEVC Draft and Test Model Editing[C]//Proc.of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11 12th Meeting. Geneva,Switzerland:[s.n.],2013:1085-1090.

[7] Sun Heming,Zhou Dajiang,Goto S.A Low-complexity HEVC Intra Prediction Algorithm Based on Level and Mode Filtering[C]//Proc.of 2012 IEEE International Conferenceon Multimedia and Expo.Melbourne, Australia:IEEE Press,2012:1085-1090.

[8] Saxena A,Fernandes F C.On Secondary Transforms for Intra Prediction Residual[C]//Proc.of IEEE International Conference on Acoustics,Speech and Signal Processing.Kyoto,Japan:IEEE Press,2012:1201-1204.

[9] Bross B,Han W,Ohm J,et al.WD5:High Efficiency Video Coding(HEVC)Text Specification Draft 9[C]// Proc.of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/ WG11 11th Meeting.Shanghai,China:2012.

[10] Yeo Chuohuo,Tan Yihhan.Mode-Dependent Transforms for Coding Directional Intra Prediction Residuals[J]. IEEE Transactions on Circuits and Systems for Video Technology,2012,22(4):545-554.

[11] Huang Yihsin,Ou Taosheng,Chen H H.Fast Decision of Block Size,Prediction Mode,and Intra Block for H.264 Intra Prediction[J].IEEE Transactions on Circuits and Systems for Video Technology,2010,20(8):1122-1132.

[12] 成益龍,滕國偉,石旭利,等.一種快速HEVC幀內預測算法[J].電視技術,2012,36(21):4-7.

[13] Lim K,Kim S.Fast Block Size and Mode Decision Algorithm for Intra Prediction in H.264/AVC[J].IEEE Transactions on Consumer Electronics,2012,58(2): 654-660.

[14] Yeo C,Tan Y H.Low-complexity Mode-dependent KLT for Block-based Intra Coding[C]//Proc.of the 18th IEEE International Conference on Image Processing. Brussels,Belgium:IEEE Press,2011:3685-3688.

編輯 金胡考

A Fast Intra-frame Prediction Algorithm for HEVC

ZHANG Xin-chen1,XIAO Xiu-xiu1,ZHAO Ya1,LI Wei2,JIANG Hao2,XIAO Jin-sheng2
(1.College of Physics Science and Technology,Central China Normal University,Wuhan 430079,China;
2.School of Electronic and Information,Wuhan University,Wuhan 430072,China)

As a new generation video coding standard,HEVC has more compression efficiency than the existing video coding H.264 standard,but it has higher complexity.Aiming at this problem,after brief analysis of the intra prediction algorithm,a fast algorithm based on Rate-distortion(RD)cost of intra prediction block dividing and the intra-frame prediction mode selection fast algorithm is proposed to reduce the HEVC intra-frame prediction complexity.This algorithm takes full use of the advantages of rate distortion cost and the probability of the prediction mode is selected in the candidate pattern quick descending law.Experimental results show that complexity reduction from HM10.0 is over 59% and stable for various sequences,which makes the proposed algorithm suitable for real-time applications.The corresponding bit rate increase is lower than 1.34%.

video coding;HEVC standard;intra-frame prediction;block partitioning;mode decision

1000-3428(2014)10-0017-03

A

TP18

10.3969/j.issn.1000-3428.2014.10.004

國家自然科學基金資助項目(61371126);教育部-中國移動科研基金資助項目(MCM20122041)。

張新晨(1977-),男,副教授、博士,主研方向:視頻編碼,多媒體通信;肖秀秀,碩士研究生;趙 婭,本科生;黎 偉,碩士研究生;江 昊,教授、博士;肖進勝,副教授、博士。

2013-09-03

2013-11-12E-mail:zxc9501@163.com

中文引用格式:張新晨,肖秀秀,趙 婭,等.一種HEVC幀內預測快速算法[J].計算機工程,2014,40(10):17-19,24.

英文引用格式:Zhang Xinchen,Xiao Xiuxiu,Zhao Ya,et al.A Fast Intra-frame Prediction Algorithm for HEVC[J]. Computer Engineering,2014,40(10):17-19,24.