基于時域相關性的快速HEVC幀間模式判決方法

劉 娟，鐘國韻，王 蕾，劉梅鋒，徐洪珍

（東華理工大學 軟件學院，江西 撫州 344000）

基于時域相關性的快速HEVC幀間模式判決方法

劉 娟，鐘國韻，王 蕾，劉梅鋒，徐洪珍

（東華理工大學 軟件學院，江西 撫州 344000）

高效率視頻編碼（HEVC）相比目前的國際視頻編碼標準H.264/AVC，在壓縮率方面有了較大的提高，但也帶來了巨大的編碼計算復雜度。為了降低HEVC的編碼計算復雜度，提出了一種快速HEVC幀間模式判決方法。統計并分析了相鄰兩幀之間對應塊的編碼單元（CU）和預測單元（PU）的時域相關性，在此相關性基礎上，跳過了一些冗余CU分割層和PU預測模式，CU層最多只取兩種PU預測模式，從而大大減少了所需要進行的率失真代價計算的數量。實驗結果顯示，與HM7.0相比，該方法在僅損失了0.21%～1.66%的壓縮率和0.01～0.09 dB的峰值信噪比的前提下，降低了52.3%～63.5%的編碼時間。

效率視頻編碼；編碼單元；預測單元；模式判決

目前的國際視頻編碼標準H.264/AVC[1]是由兩大國際標準化組織ITU-T和ISO/IEC的聯合視頻小組（JVT）開發的。該視頻編碼標準采用的最大的塊尺寸為16×16，隨著高清視頻的發展，國內外學者發現該塊尺寸已不能適應高清視頻高效編碼的需求[2]。為此，兩大國際組織專門成立了視頻編碼聯合協作組JCT-VC，以開發下一代國際視頻編碼（HEVC）標準[3-5]。該標準采用最大尺寸為64×64的編碼單元，其目標為在保持視頻質量不變的基礎上，壓縮率比H.264/AVC標準提高一倍。

相比H.264/AVC，HEVC最大的改進是采用了以下3種技術：編碼單元（CU）、預測單元（PU）和變換單元（TU）。HEVC采用了4種CU尺寸和8種PU預測模式，在每種CU尺寸和PU模式下均對其進行率失真代價值的計算，因此，總體的計算復雜度是巨大的。若要將HEVC應用于實際的實時視頻通信系統中，降低其計算復雜度是很必要的。針對H.264/AVC，近幾年國內外的學者提出了一些快速模式判決的方法。如干宗良等[6]提出了一種基于先驗預測的幀間編碼模式選擇快速算法。Li等[7]利用基本層和提高層之間的相關性跳過提高層的許多率失真代價的搜索數量來降低編碼計算復雜度。C.Grecos等[8]提出了根據幀內/幀間預測和代價函數的單調性，減少了所需進行的幀間預測模式數量。A.Yu等[9]提出了包含跳過、宏塊和子宏塊等3層的分等級結構，每一層采用不同的運動估計的復雜度，從而降低了編碼的計算復雜度。Ates等[10]提出一個聯合率失真和計算復雜度的優化框架，僅對最佳的分塊進行運動估計以降低編碼計算復雜度。Kim等[11]根據前一幀對應塊的編碼模式和率失真代價分布模式，提出了自適應的快速模式判決方法。文獻[12-13]中，通過在4×4塊歸一化運動向量場得到運動向量一致性，判決當前有可能出現的分塊模式，從而跳過其他一些不太可能出現的模式。M.Knesebeck等[14]利用16×16塊與其潛在最優的分塊之間率失真的相關性，跳過其他分塊的率失真代價計算。Zhao等[15]利用空、時域相鄰分塊之間的相關性，構建最優模式列表以節省其他模式的率失真代價的計算。文獻[16]通過利用當前塊與參考塊之間相位相關性，從候選預測模式中僅挑選一種最佳預測模式進行預測。P.Lee等[17]利用模糊邏輯的方法，通過對前一幀對應塊預測模式的分布情況進行分析，根據分析結果判決當前塊對某種模式進行率失真代價計算的必要性，從而跳過了一些不必要的預測模式。

上述方法均取得了較好效果，但均根據H.264/AVC的宏塊結構設計，并不適合HEVC。本文將分析相鄰兩幀間時域的相關性，根據該相關性，即相鄰兩幀之間CU及PU的相似度，跳過當前最大CU（LCU）中各種尺寸CU中的多個不太可能出現的PU模式，使得每個CU中最多只有兩種PU模式的率失真代價需要計算，從而減少編碼的計算復雜度。

1 HEVC幀間預測模式判決

1.1 HEVC中的CU分割方式

HEVC中，一幅圖片可以分為多個片，而一個片可以由多個最大編碼單元（LCU）組成。LCU的尺寸最大可以設置為64×64，它的概念類似于H.264/AVC中的宏塊的概念。LCU尺寸為64×64，該尺寸CU處于第一層，它可分為4個相同尺寸的32×32的CU分塊。同樣，1個32×32尺寸的CU分塊可以分為4個相同尺寸的16×16的CU分塊，直到8×8尺寸的CU分塊。

1.2 HEVC中PU預測模式

伴隨著CU，HEVC同時也介紹了預測單元（PU），該單元與預測過程相關。PU只用在樹梢節點CU中，因此，PU尺寸由CU決定，PU可等于或小于CU的尺寸。但它的形狀并不一定為正方形，該形狀的設計能使它的邊界更加接近實際視頻圖像中對象的邊界。圖1顯示了HEVC中定義的8種PU預測模式。

圖1 HEVC中定義的8種PU模式

2 基于時域相關性的快速幀間模式判決

從上一節可以看出，HEVC對每種CU尺寸和PU預測模式下的率失真代價值均進行了計算。因此，這樣的遍歷帶來了巨大的計算量。為了降低HEVC的幀間預測模式判決的計算復雜度，國內外學者紛紛向HEVC標準制定大會提交了提案，目前的HEVC編碼標準中，在模式判決過程中加入了SKIP模式，跳過一些子樹上的率失真代價計算[18]；也提出了當編碼宏塊標準cbf為0時（此時CU的量化后AC系數均為0）跳過除PART_2N×2N外的其他模式的機制[19-20]。這些算法均已經加入到了HEVC最新的參考軟件HM7.0中。然而，若要將HEVC應用于實際的實時通信系統，其編碼計算復雜度必須進一步降低。

受文獻[17]針對H.264/AVC的算法的啟發，本文利用相鄰幀之間CU分割方式及PU預測模式的時域相關性，跳過一些當前塊的CU分割方式和PU預測模式，從而降低HEVC的編碼計算復雜度。

2.1 時域相關性及PU模式統計分析

為了分析相鄰幀之間時域相關性及各種PU模式之間的關系，首先統計相鄰兩幀之間的CU分割方式及PU預測模式的相似程度和每種尺寸CU中的各種PU模式的分布情況。

2.1.1 相鄰幀之間時域相關性統計分析

為了統計相鄰兩幀的對應位置塊之間CU分割方式及PU預測模式的相似度，分別定義了兩個概率：PCU和PPU，PPU代表相鄰兩幀對應塊之間CU相同的概率，而PPU代表相同的CU下PU模式相同的概率，具體定義為

式中：Asc是相鄰兩幀對應塊相同CU的面積；Atc是總的CU的面積；Asp是相鄰兩幀對應塊相同的CU中，有著相同PU模式的塊的面積；Atp是總的PU的面積。

為了統計實際視頻中相鄰兩幀之間的CU及PU的相似度，采用了6個不同分辨率和運動特性的視頻序列，在HEVC參考軟件HM7.0中進行了統計，結果如表1所示。

從表1中的統計結果可以看出，相鄰兩幀之間的CU分割方式和PU預測模式有著高度的相似性，因此，本文擬利用該相關性跳過當前塊的部分冗余的CU分割方式和PU預測模式是合理的。

表1 相鄰兩幀之間的CU及PU的相似概率

2.1.2 PU模式分布情況

為了統計各種尺寸下CU的PU預測模式分布情況，對6個視頻序列進行了統計，發現其中的PART_2N×2N具有最高的出現概率，并且遠高于其他模式出現的概率。表2列出了各種視頻下各種尺寸該模式最優的概率。從表2可以看出，在各層CU的遍歷中，其中PU預測模式PART_2N×2N最大，則率失真代價值可能最小，因此，本文將該模式設為最佳的PU預測模式。

表2 各種尺寸下PU模式PART_2N×2N的概率

2.2 快速HEVC幀間模式的分析及其判決方法的提出

由第1節可知，對于當前的LCU，編碼器將對其各種尺寸的CU均要進行遍歷，而每一塊CU在前一幀對應位置已編碼的CU尺寸只有一種，于是，當前CU分塊與前一幀對應CU尺寸大小之間關系存在3種情況：當前CU尺寸大于、等于和小于前一幀對應塊CU的尺寸，因此，必須在3種情況下分別討論分析當前CU的幀間模式判決方法。

2.2.1 當前CU尺寸小于對應CU尺寸

當前CU尺寸小于對應CU尺寸時，如圖2所示，此時當前CU尺寸為對應塊的1/2（指的是邊長），塊E可能對應的位置為A、B、C或者D。

圖2 當前CU尺寸小于對應CU尺寸時的相互關系

當對應CU分塊的PU模式為PART_nL×2N時，如圖3a所示，則當前CU分塊的PU模式應為PART_N×2N；若對應CU分塊的PU模式為PART_2N×nU時，如圖3b所示，則當前CU分塊的PU模式應為PART_2N×N。

圖3 當前CU尺寸小于對應CU尺寸時，PU模式的對應關系

因此，當前CU分塊尺寸小于對應CU分塊尺寸時，總的算法設計如下：

1）當前CU分塊尺寸為對應塊尺寸的1/2時，設區域A和E左上角的坐標分別為（x，y）和（s，t），則區域B、C和D的坐標分別為（x+l，y）、（x，y+l）和（x+l，x+l），其中l為當前CU分塊的邊長。定義一個當前CU分塊尺寸為對應塊尺寸的1/2時，兩者關系的總集合Ω1為

式中：Mw指的是對應塊的PU預測模式；w表示模式的序號；n表示對應CU分塊PU模式數量（如64×64尺寸為3，而32×32和16×16尺寸為7）。式（3）中①部分指的是塊E分別對應塊A、B、C和D的所有情況的集合，②部分指的是對應CU可能出現的所有PU預測模式的集合。設CO為對應CU分塊位置和PU模式的其中一種情況，CO∈Ω1。定義8種條件的集合為

式中：“?”和“?”分別表示交集和并集；PUco表示對應CU分塊的PU模式。此時最佳PU模式為

式中：Mb表示當前CU分塊最佳PU模式（除PART_2N×2N外）。

2）當前CU尺寸為對應CU尺寸的1/4時，CU分塊E只遍歷PART_2N×2N模式。

3）當前CU尺寸小于對應CU尺寸的1/4時，CU分塊E被跳過。

2.2.2 當前CU尺寸等于對應CU尺寸

當前CU分塊尺寸等于對應CU塊尺寸時，根據表1的統計結果，當前CU分塊的PU模式直接采用對應CU分塊的PU模式。

2.2.3 當前CU尺寸大于對應CU尺寸

當前CU尺寸大于對應CU尺寸時，CU分塊可能的PU模式包括PART_2N×2N，PART_2N×N，PART_N×2N，PART_nL×2N，PART_nR×2N，PART_2N×nU和PART_2N× nD等，除模式PART_2N×2N外，其他模式則必須通過對應塊中各個CU分塊的尺寸和PU預測模式進行判決。經過大量的實驗統計，本文用以下的方法進行歸類：將6種模式（除PART_2N×2N外）分為垂直和水平2種，按照對應塊中具體的CU和PU分布情況，判決當前CU分塊的PU模式應為垂直或水平模式中的哪一種。

將對應塊中垂直和水平模式CU所占的面積Av和Ah分別定義如下

式中：p和q分別為對應塊中垂直和水平PU模式的CU數量；Mi和Ni分別為第i個垂直和水平PU模式的CU分塊的邊長。

為了進一步判決當前CU分塊的PU模式，本文采用集合的方式來定義對應塊中CU的分塊尺寸及其PU模式分布情況

式中：CPAu，v，w指的A塊區域中所有的CU分塊尺寸和PU預測模式；u指的是A塊繼續四叉樹劃分的深度，當u為0時，指的是A塊不進行四叉樹劃分；v指的是四叉樹劃分后其中的CU塊序號；w指的是PU模式的序號。CPBu，v，w，CPCu，v，w和CPDu，v，w的意義同CPAu，v，w。因此，ΩA，ΩB，ΩC和ΩD分別指的是塊A，B，C和D中CU分塊方式和PU預測模式的所有可能組合的集合。同理，可以定義整個對應塊所有的CU分塊和PU預測模式的集合為

式中：u∈（1，m）是由于對應塊中CU尺寸小于當前CU分塊，將進行四叉樹劃分，因此u是從1開始的。

對于A塊，設A?為當A塊未進行四叉樹劃分并PU模式為PART_2N×2N時的集合，因此

于是，A塊中除了A?其他的情況為A?，A?可以由以下公式得到

同理可以分別得到B、C和D塊的B?、C?和D?

根據式（8）～式（17），設定7種條件，分別為

對6種視頻進行上述7種條件下出現6種PU預測模式的概率統計，由于各種視頻及CU尺寸下總體趨勢類似，為了簡明清晰，本文只給出各種視頻及CU尺寸下各種條件下平均的PU模式分布情況，如圖4所示。從圖4可以看出，條件Con1～Con6下分別出現的模式1～6的概率最大，而Con7條件下則不能判決哪種模式概率最大。圖5顯示了條件Con1～Con7下各種出現概率最大的PU預測模式（除模式PART_2N×2N外）。

圖4 各種CU尺寸、條件下PU模式分布

圖5 條件Con1～Con7下出現概率最大的PU模式

根據圖4和圖5的結果，當前CU尺寸大于對應塊中CU尺寸時，本文具體算法設計如下：

1）當前塊尺寸為64×64時，最佳PU模式為

2）當前塊尺寸為32×32或16×16時，設此時對應塊中CU分塊模式和PU預測模式為Ωco，則最佳PU模式為

3 實驗結果及分析

由于目前未有對HEVC最新參考軟件HM7.0中對應模式判決進行改進的算法報導，因此，本文將所提出的算法與HM7.0進行比較。采用了6種視頻序列：Basket?ball-Drill，Partyscreen，Fourpeople，Johnny，Kimono1和BQ?Terrace。測試其中的前100幀，圖像組結構（GoP）設為“IPPP”，最大分塊深度（MPD）設為4，即CU尺寸為64× 64，32×32，16×16和8×8等4種，運動估計采用快速搜索方法，搜索范圍設為64，時能量化、變換跳過（SKIP）方法，內部比特深度設為10 bit，使能其他所有的編碼工具：樣值自適應補償（SAO）、自適應環路濾波（ALF）、基于亮度的色度幀內模式（LMC）、非正方形變換（NSQT）和非對稱運動分塊（AMP）等。QP值取22，27，32和37。為了比較本文算法和HM7.0算法之間的性能，本文采用了以下3種指標

式中：Bitratepro和Bitrateref分別表示本文算法和HM7.0的比特率；ΔBitrate表示本文算法相比HM7.0增加比特率的百分比；PSNRpro和PSNRref分別表示本文算法和HM7.0的峰值信噪比（PSNR），該性能指標代表了視頻的客觀質量；ΔPSNR表示本文算法相比HM7.0提高的視頻質量；Timepro和Timeref分別表示本文算法和HM7.0的總體編碼時間；ΔTime表示本文算法相比HM7.0增加編碼時間的百分比。表3顯示了本文算法相比HM7.0各方面性能的比較結果。從表中可以看出，相比HM7.0，本文算法在損失了0.21%～1.66%的壓縮率和0.01～0.09 dB的視頻質量的前提下，節省了52.3%～63.5%的編碼時間。

4 結論

本文首先統計分析了相鄰兩幀之間CU分塊方式和PU預測模式的相似性和各種CU尺寸下的PU模式分布情況，接著將當前塊與對應塊之間尺寸大小關系分為大于、等于和小于3種情況討論，每種情況下，分別根據對應塊中CU分塊的PU預測方式情況，利用集合的方法分析并統計了當前塊最有可能出現最小率失真代價值的PU預測模式，并根據統計結果設計了各種情況下幀間模式方法。實驗結果顯示，與HM7.0相比，本文提出的方法在比特率和視頻質量損失很小的情況下，節省了52.3%～63.5%的編碼時間。

表3 本文算法與HM7.0在比特率、視頻質量和編碼時間方面的比較

[1]WIEGAND T，SULLIVAN G，BJONTEGAARD G，et al.Overview of the H.264/AVC video coding standard[J].IEEE Trans.Circuits Syst.Video Technol.，2003，13（7）：560-576.

[2] LEE K，ALSHINA E，MIN J.Technical considerations for ad hoc group on new challenges in video coding standardization[EB/OL]. [2013-08-02].http://www.doc88.com/p-485729021575.htm l.

[3]UGUR K，ANDERSSON K，FULDSETH A，et al.High performance，low complexity video coding and the emerging HEVC standard[J]. IEEE Trans.Circuits Syst.Video Technol.，2010，20（12）：1688-1697.

[4]劉梅鋒，陸玲.新一代視頻編碼標準HEVC變換方法的研究[J].電視技術，2012，36（1）：1-5.

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

[6] 干宗良，齊麗娜，朱秀昌.H.264中基于先驗預測的幀間編碼模式選擇算法研究[J].電子與信息學報，2006，28（10）：1883-1887.

[7] LIH，LI Z，WEN C.Fastmode decision algorithm for inter-frame coding in fully scalable video coding[J].IEEE Trans.Circuits Syst.，Video Technol.，2006，16（7）：889-895.

[8] GRECOS C，YANG M.Fast mode prediction for the baseline and main pro f les in the H.264 video coding standard[J].IEEE Trans. Multimedia，2006，8（6）：1125-1134.

[9] YU A，MARTIN G，PARK H.Fast inter-mode selection in the H.264/AVC standard using a hierarchical decision process[J].IEEE Trans.Circuits Syst.Video Technol.，2008，18（2）：186-195.

[10] ATES H，ALTUNBASAK Y.Rate-distortion and complexity opti?mized motion estimation for H.264/AVC video coding[J].IEEE Trans.Circuits Syst.Video Technol.，2008，18（2）：159-171.

[11] KIM S，HO Y.Fastmode decision algorithm for H.264 using statis?tics of rate-distortioncost[J].Electron.Lett.，2008，44（14）：849-850.

[12] LIU Z，SHEN L，ZHANG Z.An efficient intermode decision algo?rithm based on motion homogeneity for H.264/AVC[J].IEEE Trans. Circuits Syst.Video Technol.，2009，19（1）：128-132.

[13] SHEN L，LIU Z，ZHANG Z，et al.Fast inter mode decision using spatial property ofmotion field[J].IEEE Trans.Multimedia，2008，10（6）：1208-1214.

[14] KNESEBECK M，NASIOPOILOS P.An efficient early-termination mode decision algorithm for H.264[J].IEEE Trans.Consum.Elec?tron.，2009，55（3）：1501-1510.

[15] ZHAO T，WANG H，KWONG S，et al.Fastmode decision based on mode adaptation[J].IEEE Trans.Circuits Syst.Video Technol.，2010，20（5）：697-705.

[16] PAUL M，LIN W，LAU C，et al.Direct intermode selection for H.264 video coding using phase correlation[J].IEEE Trans.Image Process.，2011，20（2）：461-473.

[17]LEE P，KUO K，HUANG S，et al.Codingmode determination using fuzzy reasoning in H.264 motion estimation[J].IET Signal Process.，2011，5（2）：242-250.

[18] TAN H，LIU F.On fast coding tree block and mode decision for high-efficiency video coding（HEVC）[C]//Proc.IEEE International Conference on Acoustics，Speech and Signal Processing（ICASSP）. Kyoto：IEEE Press，2012：825-828.

[19]KIM J，YANG J，WON K，et al.Early determination ofmode deci?sion for hevc[C]//Proc.29th Picture Coding Symposium.Poland：IEEE Press，2012：449-452.

[20] GWEON R，LEE Y.Early termination of CU encoding to reduce HEVC complexity[J].IEICE Trans.Fundamentals of Electronics, Communications and Computer Sciences，2012（7）：1215-1218.

Fast Inter-mode Decision for HEVC Based on Tem porally Correlation

LIU Juan，ZHONG Guoyun，WANG Lei，LIU Meifeng，XU Hongzhen
（College of Software，East China Institute of Technology，Jiangxi Fuzhou 344000，China）

High efficiency video coding（HEVC）achieves higher compression ratio than the current international video coding standard H.264/AVC.However，it has brought about tremendous computational complexity than H.264/AVC.In order to reduce this complexity，a fast inter-mode decision for HEVC is proposed in this paper.The temporally correlation of coding unit（CU）and prediction unit（PU）between two adjacent frames is counted and analyzed.Based on this correlation，at most two PU prediction modes are selected for Rate Distortion（RD）cost calculation to skip the other modes，greatly reducing the number of the needed RD cost calculations.The experiment results show that the proposed algorithm reduces 52.3%～63.5%coding time with only 0.21%～1.66%compression ratio loss and 0.01～0.09 dB peak signal-to-noise ratiodegradation，compared to HM7.0.

high efficiency video coding（HEVC）；coding unit（CU）；prediction unit（PU）；mode decision

TN919.81

A

劉 娟（1989—），女，碩士生，研究方向為多媒體通信；

鐘國韻（1979—），本文通訊作者，博士，講師，研究方向為多媒體通信；

王 蕾（1979—），副教授，研究方向為圖像與圖形處理；

劉梅鋒（1979—），講師，研究方向為電路與系統、視頻編碼；

徐洪珍（1976—），博士，副教授，研究方向為軟件理論。

?? 雯

2013-08-16

【本文獻信息】劉娟，鐘國韻，王蕾，等.基于時域相關性的快速HEVC幀間模式判決方法[J].電視技術，2014，38（13）.

國家自然科學基金項目（61262001）；江西省自然科學基金項目（20114BAB201043）；江西省科技支撐計劃項目（20112BBE50048）