基于運動特征的HEVC幀間模式快速判決算法

金智鵬，代紹慶，王利華

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

?

基于運動特征的HEVC幀間模式快速判決算法

金智鵬1，代紹慶1，王利華2

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

摘要:為降低HEVC幀間預測編碼過程的計算復雜度，提出了一種新的基于運動特征的編碼單元(CodingUnits，CU)及預測單元(PredictionUnits，PU)快速判決算法。首先，通過二階幀差法檢測運動劇烈程度，并分析運動特征對CU及PU時域相關性的影響。然后，利用前幀相同位置CU及PU的最優模式預測當前CU的深度范圍，并根據運動劇烈程度優化預測范圍。最后，根據預測范圍跳過和終止部分不必要的CU深度和PU模式，從而加快幀間編碼速度。在HM12.0平臺上的實驗測試表明，該算法在BDPSNR僅降低0.068dB、BDBR只增加1.530%的情況下，提高了48.389%的編碼速度。

關鍵詞:HEVC；幀間預測；編碼單元(CU)；預測單元(PU)；前幀相同位置；CU深度范圍

新一代高性能視頻編碼國際標準(HighEfficiencyVideoCoding，HEVC)主要面向高清晰度、高幀率、高壓縮率的應用需求[1]。相比H.264，HEVC采用了四叉樹結構的編碼單元(CodingUnits，CU)、預測單元(PredictionUnits，PU)和變換單元(TransformUnits，TU)等眾多新技術[2]，將壓縮效率提高了一倍。

HEVC將每幀圖像按最大編碼單元(LargestCodingUnits，LCU)進行劃分，每個LCU又可分為一個或多個不同深度(depth)的CU，包括64×64(depth=0)、32×32(depth=1)、16×16(depth=2)、8×8(depth=3)等4種CU模式。每一深度的CU又可按2N×2N、2N×N、N×2N、N×N、2N×nU、2N×nD、nL×2N、nR×2N等8種PU模式進行預測編碼[3]。在編碼過程中，HEVC采用遍歷方式比較上述各種CU及其PU模式的率失真代價，并根據率失真代價確定LCU的最優四叉樹結構以及各深度CU的最優PU預測模式，這使得編碼器的計算量非常巨大。

為了降低編碼復雜度，HEVC采納了早期編碼單元設置(EarlyCodingUnit，ECU)[4]、快速合并模式(FastDecisionforMerge，FDM)[5]、編碼標志快速終止(CodedBlockFlag，CBF)[6]、自適應CU深度遍歷(AdaptiveCUDepthRange，ACUDR)[7]等一些快速編碼算法，以減少編碼時間。

為進一步提高HEVC的編碼速度，Kim等人[8]通過分析運動矢量差和CBF，提前檢測當前PU是否滿足Skip模式，并終止后續PU預測模式的遍歷計算。Lee等人[9]等利用時域相關性來預測當前CU的深度范圍，跳過部分可能性較低的CU模式。Shen等人[10]利用時空相關性以及CU層間相關性來預測當前CU的深度范圍，并通過檢查運動矢量和率失真代價，提前終止PU模式的計算，以降低編碼復雜度。

近來，蔣等人[11]提出了一種基于貝葉斯決策的CU快速判決算法，通過相鄰LCU的四叉樹結構來預測當前LCU的深度范圍，并依據率失真代價和閾值的比較進行CU提前終止判決。晏等人[12]提出了一種CU分級判決快速算法，采用自適應權值量化分析時空相鄰CU之間的相關性，并預測當前CU的深度范圍，跳過和提前終止不必要的深度計算。

上述快速算法在很大程度上減少了CU遍歷范圍，但若能結合CU運動特征分類進行CU深度預測，可進一步提高編碼速度。本研究將基于CU的運動特征，分類進行CU及PU模式的快速判決，加快HEVC幀間編碼速度。

1HEVC幀間模式快速判決算法

1.1CU運動特征檢測

在幀間編碼過程中，背景和紋理平滑區往往采用大尺寸CU進行編碼，以降低編碼碼率；運動劇烈區域往往采用小尺寸CU進行編碼，以提高編碼質量。因此，預判CU的運動特征是提高編碼速度的關鍵。

幀間差分法是比較常用且有效的運動對象檢測法[13]，即利用前后兩幀相同位置處像素的亮度絕對差來衡量運動變化程度。本文采用LCU中4個32×32子CU的二階亮度絕對差來檢測運動對象并衡量其運動幅度。32×32子CU的一階幀差(FirstDifferenceofCU，FD)計算如下

(1)

式中：FD(cur)表示當前32×32子CU的一階幀差；fcur(x,y)表示當前32×32子CU的亮度像素值；gcol(x,y)表示前一幀相同位置處32×32子CU的亮度像素值。

但是由于攝像機抖動、鏡頭運動、光照等影響，一階幀差的運動對象檢測效果并不理想。鑒于由攝像機抖動所產生的幀間差是持續的、大小相近的，因此本文通過計算二階幀差，濾除由攝像機抖動等因素所帶來的擾動和噪聲。32×32子CU的二階幀差(Second Order Difference of CU，SOD)的定義如下

(2)

式中：SOD(cur)表示當前32×32子CU的二階幀差；FD(col)表示前一幀相同位置處子CU的一階幀差。

基于上述分析，本文根據二階幀差SOD來衡量CU的運動特征，并將當前CU分為3種類型：背景平滑區、運動平緩區和運動劇烈區。具體分類如下

(3)

根據編碼經驗，設置T1=128，T2=3×T1，能取得較佳的編碼效果。

1.2運動特征對CU及PU時域相關性的影響

為了掌握相鄰兩幀之間CU及PU最優模式的相關性概率，分析CU運動特征對CU及PU模式劃分的影響，本文采用ClassA～E的15個不同分辨率和運動特性的視頻序列進行編碼統計。測試平臺為HEVC參考軟件HM12.0[14]，統計結果如圖1和表1所示。

表1中，PCU表示相鄰兩幀相同位置CU其模式相同的概率，即CU模式相同的面積/圖像總面積；PPU表示相同位置PU模式相同的概率。據表1的數據統計可知，運動劇烈區，其相鄰兩幀之間的PCU平均僅為50.4%；說明其時域相關性較弱，前幀相同位置的最優CU模式不具有參考意義。而對于背景平滑區，其相鄰兩幀之間的CU及PU模式有著高度的相似性，其PCU平均為82.6%，其PPU平均達89.2%，分別比運動劇烈區高出32.2%和27.7%。因此，對于背景平滑區，可以使用前幀相同位置的最優CU及PU模式來預測當前CU及PU的模式范圍；其預測準確性高，且對不同類型的序列都比較穩定。

表1相鄰兩幀之間CU及PU最優模式的相關性概率 %

從圖1可見，各種PU預測模式中，2N×2N模式的使用概率高達84.6%，遠高于其他預測模式的使用率。結合表1的統計數據，若當前CU被判為背景平滑區，則當前CU的PU模式更有可能為前幀對應位置的最優PU模式和2N×2N模式；因此，根據一定的判斷條件跳過其他冗余PU模式是合理的。

1.3CU劃分模式快速判決

步驟1)第1個P幀圖像，根據LCU的一階幀差結果進行運動區和背景區的判斷。如果當前LCU的一階幀差FD>1 920，則判為運動區；否則判為背景區。對運動區遍歷計算深度depth=1～3的CU模式，并根據率失真代價選擇最優的CU四叉樹結構；對背景區，則直接確定depth=0為最佳CU模式。

步驟2)后續P幀圖像，先進行二階幀差計算，判斷當前CU的運動特征，并根據CU特征選取相應的編碼策略。如果當前LCU中某個32×32子CU的二階幀差SOD>T2，則判定當前LCU處于運動區，轉入步驟3)；否則，判定當前LCU處于背景區，轉入步驟4)。

步驟3)運動區。如果當前32×32子CU的二階幀差SOD>T2，屬于運動劇烈區，則設置當前CU的深度遍歷范圍為depth=1～3。非運動劇烈區，首先獲取前幀相同位置處CU的最小深度MinDepth和最大深度MaxDepth，作為當前CU劃分的預測范圍。然后進一步優化，如果當前32×32子CU的二階幀差SOD>T1，屬于運動平緩區，則修正CU預測范圍MinDepth--、MaxDepth++。轉入步驟5)。

步驟4)背景區。首先獲取前幀相同位置處CU的最小深度MinDepth和最大深度MaxDepth，作為當前CU的預測范圍。進一步優化，如果當前32×32子CU的二階幀差SOD>T1，屬于運動平緩區，則MaxDepth++；如果當前32×32子CU的二階幀差SOD≤T1，屬于背景平滑區，則MinDepth--。

步驟5)跳過和終止不必要的CU深度，進行編碼計算。根據對當前CU的預測范圍，跳過深度depth

步驟6)對LCU中的每個子CU，遞歸進行步驟2)～5)的判決過程。

1.4 PU預測模式快速判決算法

步驟1)第1個P幀圖像，采用PU預測模式全遍歷計算，根據率失真代價選擇最優的PU預測模式。

步驟2)后續P幀圖像，依據二階幀差計算結果，分運動區、平緩區、背景區等3種情況設置PU模式候選范圍。

步驟3)運動區，采用所有PU預測模式全遍歷計算。

步驟4)平緩區，采用2N×2N、2N×N、N×2N、和前幀對應位置的最優PU模式組成候選集。

步驟5)背景區，采用2N×2N、前幀對應位置的最優PU模式組成候選集。

步驟6)根據PU模式候選集，計算最優PU模式。如果在2N×2N模式下，殘差經量化后的所有系數為0，且運動矢量差值也為0，則認定2N×2N模式為當前CU的最優PU模式，提前終止PU模式候選集的計算。

本文算法CU及PU模式判決過程如圖2所示。

2實驗結果及數據分析

為測試與分析快速算法的性能，在HM12.0軟件平臺上按通用測試條件[15]進行測試分析。編碼器采用低復雜度配置、低延時編碼方案，具體測試參數為：

IPPP，MaxPartitionDepth=4，MotionSearchRange=64；采用快速合并模式判決算法(FastDecisionforMerge，FDM)、快速運動估計搜索算法(EnhancedPredictiveZonalSearch，EPZS)和運動搜索加速算法(FastEncoderDecision，FEN)；編碼QP設置為22、27、32和37。

算法性能采用BDBR和BDPSNR[16]指標進行評價，分別表示同樣PSNR下碼率的損失和相同碼率下PSNR的損失情況。采用平均節省時間(AverageSavingTime，AST)表示編碼復雜度，其定義如下

(4)

式中：AST表示本文算法相比HM12.0節省的編碼時間；Timeproposed和TimeHM12.0分別表示本文算法和HM12.0的總體編碼時間。

由表2可見，與HM12.0編碼器相比，本文算法的BDBR平均增加1.530%，BDPSNR平均損失0.068dB，編碼時間AST平均節省48.389%。這一結果說明，本文提出的HEVC幀間模式快速判決算法具有良好的率失真性能，能大幅降低編碼時間。特別是對于背景靜止、運動復雜度較低的序列，本文算法可以跳過大量不必要的CU深度和PU模式計算，加速效果尤為顯著。

表2本文快速算法測試結果與HM12.0的比較

圖3和圖4分別為HM12.0和本文快速算法對“BasketballPass”(416×240)序列進行編碼的最優CU劃分示意圖。根據圖3和圖4的對比可見，僅有5處地方CU劃分結構不同，且CU劃分深度差都僅為1(如圖4中圓圈標識的區域)。這說明本文快速算法的CU劃分準確性較高。

為進一步評估本文快速算法的性能，筆者將文獻[11]中編碼單元裁剪與快速選擇算法、文獻[12]中時空相關的CU分級判決算法和本文基于運動特征的快速算法進行比較。從表3各種快速算法的率失真和編碼時間對比數據可知，與文獻[11]提出的算法相比，本文算法的BDBR降低0.65%，編碼時間能多節省6%；與文獻[12]提出的算法相比，本文算法的編碼時間能節省3%，BDPSNR提高0.02dB，BDBR降低0.98%。因此，本文快速算法的綜合性能要優于這兩種快速算法。其主要原因是本文算法通過二階幀差法提取運動對象，提高了對不同運動特征的CU及PU的預測針對性和準確性，特別是有效減少了背景平滑區的CU及PU遍歷范圍。

3小結

根據運動特征對CU及PU時域相關性的影響分析，本文提出了一種新的基于運動特征的CU及PU模式快速判決算法。該算法首先采用二階幀差法提取運動對象并判定運動劇烈程度，然后根據運動特征采用不同的編碼策略。對運動劇烈區，仍以大范圍遍歷計算為主；對背景平滑區，則主要以前幀相同位置CU及PU的最優模式來預測當前CU的深度范圍，從而有效減少了CU及PU的遍歷范圍。實驗結果顯示，本文算法提高了48.389%的編碼速度，能促進HEVC面向高清視頻監控、視頻會議以及低復雜度實時編碼等領域的應用。

參考文獻：

[1]沈燕飛，李錦濤，朱珍民，等. 高效視頻編碼[J]. 計算機學報，2013，36(11)：2340-2355.

[2]CORREAG，ASSUNCAOP，AGOSTINIL，etal.Performanceandcomputationalcomplexityassessmentofhigh-efficiencyvideodecoders[J].IEEEtransactionsoncircuitsandsystemsforvideotechnology，2012，22(12)：1899-1909.

[3]劉昱，胡曉爽，段繼忠. 新一代視頻編碼技術HEVC算法分析及比較[J]. 電視技術，2012，36(20)：45-49.

[4]CHOIK，PARKSH，JANGES.CodingtreepruningbasedCUearlytermination[C]//Proc.JCT-VC6thMeeting.Torino：JCT-VC， 2011：14-22.

[5]LAROCHEG，POIRIERT，ONNOP.Encoderspeed-upforthemotionvectorpredictorcostestimation[C]//Proc.JCT-VC8thmeeting.SanJose，CA，USA：JCT-VC，2012：121-128.

[6]GWEONRH，LEEYL，LIMJ.EarlyterminationofCUencodingtoreduceHEVCcomplexity[C]//Proc.JCT-VC6thmeeting.Torino：JCT-VC，2011：1-5.

[7]LIX，ANJC，GUOX，etal.AdaptiveCUdepthrange[C]//Proc.JCT-VC5thMeeting.Geneva：JCT-VC，2011.

[8]KIMJ，YANGJ，WONK，etal.EarlydeterminationofmodedecisionforHEVC[C]//Proc.PictureCodingSymposium(PCS).Kraków，Poland：PCS2012：449-452.

[9]LEEHS，KIMKY，KIMTR，etal.Fastencodingalgorithmbasedondepthofcoding-unitforhighefficiencyvideocoding[J].Opticalengineering，2012，51(6)：56-61.

[10]SHENLiquan，LIUZhi，ZHANGXinpeng，etal.AneffectiveCUsizedecisionmethodforHEVCencoders[J].IEEEtransactionsonmultimedia，2013，15(2)：465-470.

[11]蔣剛毅，楊小祥，彭宗舉，等. 高效視頻編碼的快速編碼單元深度遍歷選擇和早期編碼單元裁剪[J]. 光學精密工程，2014，22(5)：1322-1330.

[12]晏軻，滕國偉，胡錦雯，等. 一種基于時空相關性的編碼單元深度快速分級判決算法[J]. 光電子·激光，2014，25(1)：156-162.

[13]姚春蓮，郭克友. 一種利用幀差信息的實時運動對象檢測算法[J]. 計算機工程與應用，2011，47(8S)：390-393.

[14]JCT-VC．HEVCReferenceSoftwareHM-12.0 [EB/OL][2014-09-01].https//hevc.hhi.fraunhofer.de/svn/svn_HEVCSoftware/tags/HM-12.0.

[15]BOSSENF.JCTVC-L1100,Commontestconditionsandsoftwarereferenceconfigurations[S].2013.

[16]PATEUXS，JUNGJ.Anexceladd-inforcomputingbjontegaardmetricanditsevolution[S].2007.

金智鵬(1982— )，碩士，副教授，主要研究方向為低復雜度視頻編碼與傳輸、圖像質量評價等；

代紹慶(1972— )，碩士，副教授，主要研究圖像壓縮、圖像處理與模式識別；

王利華(1977— )，高級工程師，主要研究網絡視頻測試與傳輸技術。

責任編輯：時雯

FastintermodedecisionalgorithmforHEVCbasedonmotionfeatures

JINZhipeng1，DAIShaoqing1，WANGLihua2

(1.Information Technology Branch Institute，Jiaxing Vocational Technical College，Zhejiang Jiaxing 314036，China；2. Zhejiang(Jiaxing) Microsoft's Technology Research Center，Zhejiang Jiaxing 314000，China)

Keywords:HEVC；interprediction；codingunits(CU)；predictionunits(PU)；co-locatedposition；CUdepthrange

Abstract:ToreducethecomplexityofHEVCinterpredictioncoding，anovelfastCU(CodingUnits)andPU(PredictionUnits)modedecisionalgorithmbasedonmotionfeaturesisproposed.Firstly，todetectmovementintensitythroughsecondorderdifferencemethod，andtoanalyzetheimpactofmotionfeaturestoCUandPUtemporalcorrelation.Secondly，topredictthecurrentCUdepthrangeandPUmodeusingthebestCUandPUmodeoftheco-locatedpositioninthepreviousframe.Then，tooptimizethepredictedrangeaccordingtothemotionfeatures.Finally，inordertospeeduptheinterpredictioncoding，toskipandterminationofsomeunnecessaryCUandPUmodeaccordingtothepredictedrange.ExperimentalresultsonHM12.0showthattheproposedalgorithmcanreduceencodingtimefor48.389%，whileBDPSNRlossisonly0.068dBandBRBRincrementis1.530%．

中圖分類號：TN919.8

文獻標志碼:A

DOI：10.16280/j.videoe.2016.01.003

基金項目：浙江省教育廳科研計劃項目(Y201431212)；嘉興市科技計劃項目(2014AY11003)

作者簡介：

收稿日期：2014-9-12

文獻引用格式：金智鵬,代紹慶,王利華.基于運動特征的HEVC幀間模式快速判決算法[J].電視技術,2016，40(1)：13-18.

JINZP，DAISQ，WANGLH.FastintermodedecisionalgorithmforHEVCbasedonmotionfeatures[J].Videoengineering,2016,40(1)：13-18.