金智鵬，代紹慶，曾 濤

(1.嘉興職業(yè)技術學院 信息技術分院，浙江 嘉興 314036；2.中國(嘉興)微軟技術研究中心，浙江 嘉興 314000)

分級自適應的HEVC幀內預測模式快速選擇算法

金智鵬1，2，代紹慶1，曾 濤2

(1.嘉興職業(yè)技術學院 信息技術分院，浙江 嘉興 314036；2.中國(嘉興)微軟技術研究中心，浙江 嘉興 314000)

針對HEVC幀內預測編碼計算復雜度高的問題，提出了一種基于分組自適應的幀內預測模式快速選擇算法。該算法抽選12個候選模式進行預測方向初步判斷，然后根據初步判斷結果再精選預測模式；并根據粗選的HCost代價排除部分可能性較低的候選模式，以達到減少候選模式數量，降低計算復雜度的目的。在HEVC參考軟件HM12.0上的測試表明，該算法在BD-PSNR平均損失0.041 dB的情況下，平均可降低36.521%的編碼時間，顯著提高了編碼速度。實驗結果顯示，該算法的適應性強，對不同尺寸、不同紋理和運動特點的測試序列均有明顯效果，具有良好的實際應用價值。

視頻編碼；H.265/HEVC；幀內預測；模式判決；快速算法；提前排除

新一代高效視頻編碼標準(High Efficiency Video Coding,HEVC)于2010年4月在JCT-VC第一次會議上被提出來，并在之后逐步得到完善。相對于之前的H.264，HEVC在預測編碼方面有了長足的發(fā)展，提高了1倍的編碼效率。HEVC主要面向下一代4K分辨率高清電視、3D視頻、移動視頻、流媒體視頻等最新應用[1]。

HEVC采用了靈活的基于大尺寸四叉樹的分割結構和編碼結構[2]，包括編碼單元(Coding Unit，CU)、預測單元(Prediction Unit，PU)以及變換單元(Transform Unit，TU)。為滿足高清視頻中更為細致的紋理預測需要，HEVC最高支持35種幀內預測模式，其中方向預測增加到33種，提高了預測精度。此外，在DC均值模式的基礎上增加了Planar平滑預測模式，提高了對漸變式平滑紋理區(qū)的預測精度。但是，HEVC的高性能編碼是以極高的計算復雜度為代價的，而高計算復雜度卻是其面向實際應用的技術難題。因此，如何降低編解碼的計算復雜度，成為了HEVC當前的研究熱點。

1 HEVC幀內預測快速模式選擇算法分析

1.1 HEVC幀內預測模式判斷過程

為了提高預測精度，自參考軟件HM7.0之后，每個尺寸的PU都有35種幀內預測模式；HEVC幀內預測模式快速判斷的流程可分為以下3個階段。

階段一，采用Hadamard變換對所有35種模式進行RMD(Rough Mode Decision)模式粗選擇[3]。根據HCost選取代價最小的N個預測模式作為候選模式，加入粗選子集。針對4×4和8×8的PU尺寸，N=8；針對其他的PU尺寸，N=3。HCost定義為

HCostmode=HSATDmode+λ·bitsmode

(1)

式中：HSATD表示殘差信號哈達瑪變換系數絕對和，它在一定程度上反映了殘差比特率，其定義如式(2)所示；mode為35種幀內預測模式之一；λ為拉格朗日乘子；bits為該模式下的編碼比特數。

(2)

式中：T(D)=HDH是指Hadamard變換；H是Hadamard變換矩陣；D指殘差信號矩陣Diff(i,j)。

Diff(i,j)=Orig(i,j)-Pred(i,j)

(3)

式中：Orig(i,j)是指原始圖像塊中的像素值；Pred(i,j)是指預測值。

階段二，檢測當前編碼塊的最有可能模式MPM(Most Probable Mode)是否包含在粗選子集中。若不在，則將其加入粗選子集。換言之，無論RMD階段的模式粗選結果如何，都加入當前預測塊的左側塊和上方塊的最優(yōu)模式作為候選模式，使其具有自適應性[4]。MPM技術提高了RMD粗選模式子集的準確度，有效地降低了計算復雜度。

階段三，對粗選子集中的預測模式進行RDO(Rate Distortion Optimization)率失真代價計算，RDCost代價最小的模式即為最優(yōu)預測模式。然后通過最優(yōu)預測模式預測當前PU，并對預測殘差進行變換、量化和熵編碼。RDCost定義為

(4)

相較于進行35 次RDCost計算，通過RMD算法進行幀內預測模式粗選節(jié)省了大量的編碼時間；但即便如此，亮度幀內預測進行RDCost計算的過程仍然占用了50%～60%的幀內預測編碼時間[5]。因此，提高RMD粗選的準確性，減少需要進行RDCost計算的候選模式數量，是降低幀內預測編碼計算復雜度的關鍵。

1.2 HEVC幀內預測快速算法分析

在保持HEVC 編碼性能的前提下，很多學者開始研究降低算法的計算復雜度，以便實際應用和推廣。其中針對幀內預測部分有兩個研究熱點，分別是塊劃分算法的優(yōu)化和預測模式的快速判決。

1)文獻[6]提出了一種基于梯度的 HEVC 幀內預測模式快速選擇算法。該算法繼承了H.264中基于邊緣檢測的快速算法[7]，利用PU內的紋理梯度信息進行預測模式的快速選擇。實驗結果顯示，該算法能夠降低約20%的編碼復雜度。

2)由于色度幀內預測只有5種模式，因此文獻[8]提出先進行色度的幀內預測編碼，然后參考色度預測結果再進行亮度預測模式的篩選，以達到降低亮度幀內預測復雜度的目的。實驗結果顯示，在BD-PSNR(Bjontegaard delta PSNR)損失為0.05 dB的情況下，該算法能夠降低約30%的編碼復雜度。

3)文獻[9]提出了一種自適應的候選模式快速選擇算法。對于大尺寸的PU塊，如果最小HCost代價為DC或Planar模式，則只對DC和Planar模式進行RDCost計算。對于小尺寸的PU塊，檢查HCost代價最小的2個模式是否相鄰，將較佳候選模式數動態(tài)地減少為2～5個。在BD-BR(Bjontegaard delta bit rate)增加1%的情況下，該算法能夠降低約20%的編碼復雜度。

4)文獻[10]充分利用視頻序列的時域相關性，提出利用相鄰幀CU劃分信息提前判定當前編碼塊的最優(yōu)CU尺寸；并在PU層考察粗選模式的HCost代價，如果代價偏離過大，則將其排除出候選模式子集。該算法的PSNR平均損失為0.06 dB，碼率增加0.09%，編碼時間節(jié)省了約49%。

5)文獻[11]分析了圖像平滑特性與編碼塊尺寸大小的關系，提出一種依據紋理平滑性判斷的快速幀內編碼算法。算法首先對64×64的塊進行正常編碼，將其編碼率失真信息與閾值比較，判斷是否需要將其分割為4個更小的32×32編碼塊。在BD-BR增加約0.44%的情況下，編碼時間減少了24.8%。

6)文獻[12]提出了一種候選模式分組計算的幀內模式快速選擇算法。算法通過將35種預測模式分為3組進行計算，總共利用其中17種模式就能完成RMD階段的模式粗選。該算法可以降低約50%的編碼時間，但算法易陷入局部最優(yōu)，平均碼率損失達到了5.23%。

雖然以上幾種快速算法的性能損失極小，但編碼時間節(jié)省的幅度并不大。尤其對于4×4和8×8尺寸的PU塊，RMD粗選得到的候選模式數量較多，還需深入研究。

2 基于分級自適應的HEVC幀內預測模式快速選擇算法

2.1 算法設計依據

RMD模式粗選是幀內預測的關鍵步驟，圖1展示了RMD粗選模式和MPM模式最終成為當前PU最優(yōu)預測模式的概率統(tǒng)計。本文的數據是在HEVC的參考軟件HM12.0上(encoder_intra_main配置)進行50幀全I幀編碼統(tǒng)計的結果，實驗對象為Class A～E共5個類別的20個標準測試序列。通過圖1的實驗數據分析，RMD粗選后代價最小的模式Mode_HCost 0最終成為當前PU最優(yōu)預測模式的平均概率達到了71.5%；而且，從Mode_HCost 0～Mode_HCost 7，隨著候選模式在RMD粗選中排名的降低，呈現出概率快速衰減的趨勢，如圖1所示。

根據實驗統(tǒng)計數據，MPM模式最終成為當前PU最優(yōu)預測模式的平均概率達到了76.2%，并且這個比率是所有候選模式中最高的。因此，有必要將MPM模式始終作為候選模式之一參與RDO階段的判決。

圖1 各RMD粗選模式成為最優(yōu)模式的概率分布圖

2.2 分級自適應的幀內預測模式快速選擇算法

本文提出的快速算法的核心思路為：首先查找最佳預測方向可能所在的大方向區(qū)間，然后對大方向區(qū)間內的模式進行精細搜索，以求得更精確的預測模式；并依據HCost代價提前排除部分可能性較小的候選模式。算法的具體描述如下。

步驟1，采用如圖2所示的12個一級候選模式進行RMD粗選計算，初步確定最優(yōu)預測方向所在的大方向區(qū)間。一級候選模式中的Planar模式主要考慮紋理平滑區(qū)域的決策，其余11個方向預測模式采用角度均勻間隔的方式抽選。

圖2 用于RMD粗選的12個一級候選模式

步驟2，經步驟1計算后，檢測代價最小的2個較佳預測模式中是否存在Planar模式。如果存在Planar模式，則轉入步驟3；否則轉入步驟4。

步驟3，增加3個二級候選模式進行RMD粗選計算，即DC模式、較佳預測方向的左右2個相鄰預測模式，計算出較為準確的候選模式范圍。轉入步驟5。

步驟4，增加4個二級候選模式進行RMD粗選計算，即2個較佳預測方向的左右2個相鄰預測模式，計算出較為準確的預測方向區(qū)間。

步驟5，初步確定RMD預測模式篩選結果，得到粗選模式子集。針對16×16，32×32和64×64的PU尺寸，N=3。針對4×4和8×8的PU尺寸，N=2+二級候選模式數量。

步驟6，提前排除法(Early Rule Out，ERO)?？疾齑诌x模式子集中各個預測模式的代價大小，若其代價HCostmode>α×HCostmin，則將其排除出粗選模式子集。根據編碼經驗α=1.2。如果代價差異大，說明當前PU塊的紋理方向性明顯，再結合圖1的概率分布，可以排除一部分可能性較小的候選模式。

步驟7，檢測最有可能模式MPM是否包含在粗選子集中。若未包含，則將其加入到粗選子集。最后，對粗選子集中的預測模式計算率失真代價RDCost，代價最小的模式即為最終的最優(yōu)預測模式。

2.3 算法計算量的理論分析

在RMD階段，本算法一級候選模式含有12個模式，二級候選模式含有3～4個模式，這樣總共需要進行HCost計算的模式有15～16個，還不及全體35個預測模式數量的一半，節(jié)約了一半的計算量。

在RDO階段，經過步驟6的ERO提前排除法，能提前排除部分可能性較小的候選模式。經過ERO提前排除后，對16×16以上尺寸的PU塊，本算法的候選模式將動態(tài)地減少為1～3個；對8×8以下尺寸的PU塊，候選模式將動態(tài)地減少為1～6個，有效地減少了復雜的RDCost計算次數。

3 實驗結果與分析

PC機實驗平臺為： CPU Intel(R)Xeon(R) W3503 雙核，主頻2.4 GHz，內存2 Gbyte×2，操作系統(tǒng)為Windows7 SP1，編譯軟件為Microsoft Visual Studio 2008。實驗測試模型為HM12.0(encoder_intra_main配置)，具體實驗參數設置為：IntraPeriod=1(即全I幀編碼)，編碼前50幀，幀頻30 f/s(幀/秒)，MaxCUWidth=64，MaxCUHeight=64，MaxPatitionDepth=4，CABAC為熵編碼。

為了更客觀更全面地對算法性能進行比較，本文選擇了HEVC Class A～E等5種不同尺寸的標準YUV測試序列進行實驗測試。測試序列中Class A是分辨率為2 560×1 600的超清序列，Class B和Class E是分辨率為1 920×1 080和1 280×720的高清和標清序列，Class C和Class D分別為832×480及416×240的WVGA和WQVGA小尺寸序列。

表1和表2反映了本文提出的快速算法與HM12.0中幀內預測算法的編碼性能對比情況。ΔPSNR=PSNRproaposed-PSNRref，表示本文算法和HM12.0中幀內預測算法PSNR的差值；ΔRate表示兩者碼率差值的百分比

(5)

式中：Rateref和Rateproposed分別指HM12.0幀內預測算法和本文算法的編碼碼率。ΔTime表示兩者編碼時間差值的百分比，參考式(5)進行計算。

依據表1的實驗數據，本文基于分級自適應的幀內預測模式快速選擇算法具有良好的編碼性能，碼率平均增加0.164%，亮度PSNR平均降低0.032dB；這個損失對編碼RD性能的影響微乎其微，人眼基本察覺不到畫面質量的損失。同時，對不同尺寸、不同紋理和運動特點的測試序列，本文算法都獲得了大致相同的效果，顯示出良好的適應性，更貼近實際應用。

表1 本文算法和HM12.0算法的實驗測試比較

表2 相對于HM12.0本文算法的實驗測試結果

BD-PSNR表示在相同碼率下，本文算法和HM12.0算法的亮度PSNR的差值，具體可參考文獻[13]的計算方法。從表2的BD-PSNR實驗數據可以看出，在相同的碼率下，本文快速算法的平均PSNR損失只有0.041 dB，編碼時間平均能縮短36.521%；而文獻[8]的BD-PSNR損失達到了0.05 dB，而編碼時間只縮短了30%，可見本文算法具有更好的編碼性能。

表3是本文快速算法與其他幾種快速算法的性能比較。根據表3的數據，本文快速算法的PSNR、碼率和編碼時間等指標都要明顯優(yōu)于文獻[9]和[12]的算法。與文獻[10]的算法相比，編碼性能指標互有優(yōu)劣。主要是文獻[10]的算法包括快速CU劃分算法，節(jié)省了更多的計算量。

圖3和圖4給出了Class A People on Street和Class B Kimono1序列的編碼率失真曲線?？梢钥闯?，本文算法與HM12.0算法的RD曲線幾乎重合，表明兩者的編碼性能差異極小。

表3 本文算法與其他快速算法的性能比較

圖3 Class A People on Street序列的RD曲線對比圖

圖4 Class B Kimono1序列的RD曲線對比圖

4 結論

在分析了HEVC幀內預測編碼技術和最新的快速算法的基礎上，提出了一種分級自適應的幀內預測模式快速選擇算法。該算法采取分級計算、逐步精細的模式篩選方法；并根據粗選的HCost代價排除部分可能性較低的候選模式，以達到減少RDCost計算次數、降低計算復雜度的目的。實驗結果顯示，相比于HM12.0，本文算法在編碼效率損失非常小的情況下，顯著提高了編碼速度；且算法的適應性強，對于不同類型的測試序列均有明顯效果，具有良好的實際應用價值。

[1]吳敏，公衍超，楊楷芳.面向高效率視頻編碼標準的快速碼率控制算法[J]．計算機應用，2013，33(5)：1251-1254.

[2]李軼夫，蔣毅飛，陳李維，劉宏偉.HEVC分像素插值與自適應環(huán)路濾波融合結構設計[J]．計算機輔助設計與圖形學學報，2014，26(3)：493-501.

[3]PIAO Y，MIN J，CHEN J.Encoder improvement of unified intra prediction[EB/OL].[2014-03-21].http://phenix.int-evry.fr/jct/doc_end_user/documents/3_Guangzhou/wg11/JCTVC-C207-m18245-v2-JCTVC-C207.zip.

[4]ZHAO L，ZHANG L，ZHAO X.Further encoder improvement of intra mode decision [EB/OL].[2014-03-21].http://phenix.int-evry.fr/jct/doc_end_user/documents/4_Daegu/wg11/JCTVC-D283-v3.zip.

[5]李元，何小海，鐘國韻，等.基于時域相關性的HEVC快速幀內預測算法[J].電視技術，2013，37(9)：1-4.

[6]JIANG W， MA H J，CHEN Y W.Gradient based fast mode decision algorithm for intra prediction in HEVC[C]//Proc.2nd International Conference on Consumer Electronics，Communications and Networks(CECNet 2012).[S.l.]：IEEE Press，2012：1836-1840.

[7]金智鵬，郁梅.用于移動終端的低復雜度快速模式選擇算法[J]．計算機工程與應用，2014，50(5)：151-155.

[8]CHEN Wenjin，SU Jia，LI Bin.Reversed intra prediction based on chroma extraction in HEVC[C]//Proc.Intelligent Signal Processing and Communications Systems(ISPACS 2011).[S.l.]：IEEE Press，2011：1-5.

[9]ZHANG Mengmeng，ZHAO Chuan，XU Jizheng.An Adaptive fast intra mode decision in HEVC[C]//Proc.IEEE International Conference on Image Processing，2012.Orlando：IEEE Press，2012：221-224.

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

[11]蔣潔，郭寶龍，莫瑋，等.利用平滑區(qū)域檢測的HEVC幀內編碼快速算法[J].西安電子科技大學學報：自然科學版，2013，40(3)：194-200.

[12]石飛宇，劉昱.一種HEVC快速幀內模式判斷算法[J].電視技術，2013，37(11)：8-11.

[13]PATEUX S，JUNG J.An excel add-in for computing Bjontegaard metric and its evolution[S].2007.

金智鵬(1982— )，碩士，副教授，主研低復雜度視頻編碼技術；

代紹慶(1972— )，副教授，主要研究視頻系統(tǒng)編碼與質量評價；

曾 濤(1970— )，高級工程師，主要研究移動視頻技術。

責任編輯：時 雯

Fast Intra Prediction Algorithm for HEVC Based on Classification-adaptively

JIN Zhipeng1，2，DAI Shaoqing1，ZENG Tao2

(1.InformationTechnologyBranchInstitute，JiaxingVocationalTechnicalCollege，ZhejiangJiaxing314036； 2.China(Jiaxing)Microsoft′sTechnologyResearchCenter，ZhejiangJiaxing314000)

In view of the high computational complexity of HEVC intra prediction， a new fast intra prediction mode decision algorithm based on classification-adaptively is proposed．Firstly， the algorithm dividing 12 candidate modes for the rough angular decision， then according to the results of preliminary judging， careful choice prediction mode. And according to theHCostprice excluding some modes of less likely， to speed up the intra prediction of HEVC.The experimental result tested in HM12.0 shows that， the proposed algorithm can reduce about 36.521% encoding time with drops of 0.041 dBBD-PSNR， improve the encoding speed significantly．And the algorithm has a strong adaptability and obvious effect for various test sequence with different size， different texture and motion characteristics， has good practical application value.

video coding；H.265/HEVC；intra prediction；mode decision；fast algorithm；early rule out

浙江省教育廳科研項目(Y201431212);嘉興市科技計劃項目(2013AY11028)

TN391.41

A

10.16280/j.videoe.2015.05.004

2014-04-28

【本文獻信息】金智鵬，代紹慶，曾濤.分級自適應的HEVC幀內預測模式快速選擇算法[J].電視技術,2015，39(5).