李林格，張 戀，王 潔，周 巧，張 昊

(中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410083)

?

基于HEVC幀內(nèi)預(yù)測的復(fù)雜度控制

李林格，張 戀，王 潔，周 巧，張 昊

(中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410083)

幀內(nèi)預(yù)測在視頻編碼中是非常重要的模塊。在視頻實時編碼與傳輸過程中，場景切換會經(jīng)常出現(xiàn)。此時，一般會采用全I幀編碼。研究發(fā)現(xiàn)，即使是全I幀編碼，也往往會非常耗時?；诰幋a單元深度范圍和幀內(nèi)預(yù)測中候選預(yù)測方向個數(shù)研究了HEVC編碼器的復(fù)雜度控制問題。針對不同的目標編碼復(fù)雜度，算法自適應(yīng)地選擇不同的方法來優(yōu)化編碼過程。實驗結(jié)果表明，該算法在保證視頻質(zhì)量的前提下實現(xiàn)了對不同復(fù)雜度目標的控制。

視頻編碼；HEVC；幀內(nèi)預(yù)測；復(fù)雜度控制

1 HEVC視頻標準編碼

隨著視頻技術(shù)的發(fā)展，特別是高清(HD)、超高清(UHD)、3D和多視點(multi-view)視頻技術(shù)的興起，各種視頻信息已普及和深入到人們生產(chǎn)和生活的各個方面?；诨ヂ?lián)網(wǎng)的網(wǎng)絡(luò)視頻實時通信己經(jīng)成為當前通信領(lǐng)域的熱點，并在視頻會議、視頻監(jiān)控、遠程教育、視頻點播等方面得到廣泛的應(yīng)用，視頻壓縮技術(shù)受到巨大的挑戰(zhàn)。視頻應(yīng)用的多樣化和高清化趨勢對視頻壓縮性能提出了更高的要求。為此，2010年4月VCEG和MPEG再次組建視頻編碼聯(lián)合組(Joint Collaborative Team On Video Coding，JCT-VC)，聯(lián)手制定新一代視頻編碼標準——HEVC(High Efficiency Video Coding)[1]。相比以往的視頻編碼標準，HEVC沿用了傳統(tǒng)視頻編碼標準的混合視頻編碼基本框架，并在各個編碼模塊上進行了改進和革新。其核心模塊包括：預(yù)測、變換和量化、熵編碼、環(huán)內(nèi)濾波等。與先前的H.264/AVC標準相比，在相同應(yīng)用條件和視頻質(zhì)量的前提下HEVC的編碼效率要提高一倍。隨著HEVC的發(fā)展，基于HEVC的應(yīng)用級編碼器也隨之出現(xiàn)，目前可以直接使用的有兩個：x265，DivX265。類似于以往的國際標準，HEVC采用混合編碼框架，如圖1所示[2]，主要包括變換、量化、熵編碼、幀內(nèi)預(yù)測、幀間預(yù)測以及環(huán)路濾波等模塊[3]。

圖1 HEVC視頻標準編碼框

2 復(fù)雜度控制研究現(xiàn)狀

目前HEVC快速幀內(nèi)模式選擇算法，一般都只考慮在盡量少損失客觀質(zhì)量的情況下對模式進行選擇。一般的論文中，都只考慮3%以內(nèi)的質(zhì)量損失(采用BDBR或者BD-PSNR的指標)。在某些場合，僅僅采用這些保守的模式選擇算法，是達不到實際應(yīng)用需求的。由于HEVC的復(fù)雜程度很大，有時候需要通過相對比較大的質(zhì)量損失，以達到實時性[4]，在這方面，復(fù)雜度控制算法可以作為參考。針對H.264，已經(jīng)有很多復(fù)雜度控制方面的研究[5-7]。然而，由于HEVC與H.264的編碼結(jié)構(gòu)大不相同，因此其復(fù)雜度控制算法也需要重新設(shè)計。比如，在文獻[8]中，G.Correa通過同位區(qū)域中的紋理關(guān)系對編碼單元的深度進行調(diào)整。如果紋理關(guān)系相近，那么當前編碼CU也將采用這個深度。并且通過總的時間關(guān)系，對需要做算法的幀數(shù)進行提前計算，從而控制編碼的復(fù)雜度。

文獻[9]中，A.Ukhanova通過率失真和復(fù)雜度的關(guān)系來選擇量化和深度參數(shù)，使用預(yù)測和博弈論作為基礎(chǔ)，對于某一些幀的最大CU深度進行限制，從而控制編碼復(fù)雜度。

文獻[10]中，M.Grellert提出了負載管理的方案。該方案的基本思路就是估算每一幀的復(fù)雜度預(yù)算，動態(tài)地控制每一幀的復(fù)雜度。比如通過限制最大CU深度的預(yù)測和運動搜索范圍等，并通過反饋的環(huán)路控制最大限度地減少RD損失。

文獻[11]中，J.Leng對相鄰和同位的編碼深度進行分析，通過閾值來避免一些無必要的編碼深度?？刂菩枰M行優(yōu)化的最大CU數(shù)量來調(diào)整編碼的復(fù)雜度。

文獻[12]中，X.Shen利用了貝葉斯的方法來對深度進行選擇。這個算法是基于離線的機器學(xué)習方法，使用貝葉斯決策的規(guī)則，對編碼單元是否需要劃分進行判斷。

綜上所述，已經(jīng)提出的方法一般針對編碼單元的深度進行調(diào)控，或者對模式數(shù)量進行調(diào)控，沒有把這兩者結(jié)合起來分析考慮。并且以前的工作都是針對幀間預(yù)測進行的復(fù)雜度控制，而在幀內(nèi)預(yù)測方面還沒有相關(guān)工作。本文將針對幀內(nèi)預(yù)測的復(fù)雜度控制進行研究。

3 幀內(nèi)預(yù)測復(fù)雜度分析

幀內(nèi)預(yù)測主要用于去除圖像的空間相關(guān)性。通過編碼后的重構(gòu)塊信息來預(yù)測當前像素塊以去除空間冗余信息，提高圖像的壓縮效率。幀間預(yù)測模塊主要用于去除圖像時間相關(guān)性。HEVC采用了編碼單元、預(yù)測單元、變換單元代替H.264宏塊的概念[13]。由于最大編碼單元比宏塊要大很多，而且編碼單元和變換單元都可以采用樹形分塊，預(yù)測單元采用了更多的分割模式，因此，HEVC復(fù)雜度比H.264要高很多。另外，對幀內(nèi)預(yù)測，HEVC的預(yù)測方向要比H.264多好幾倍[14-15]，如圖2所示。

圖2 LCU遞歸劃分過程

雖然一般來說幀間預(yù)測的復(fù)雜度高于幀內(nèi)預(yù)測，但是在實際視頻編碼中，幀間預(yù)測經(jīng)常會采用Merge甚至Skip模式[16]，可以大大節(jié)省計算量。而HEVC幀內(nèi)編碼可選擇編碼單元大小和預(yù)測方向都比較多，因此計算復(fù)雜度高，在實時性要求較高的場合(比如視頻聊天、直播)可能會引起卡幀現(xiàn)象[17-18]。本文主要對幀內(nèi)模式進行分析，找出最優(yōu)的編碼單元大小和預(yù)測方向組合，為具體應(yīng)用提供參考。

3.1 編碼單元深度的復(fù)雜度分析

在HEVC中，視頻編碼時采用樹型結(jié)構(gòu)編碼單元(CodingUnit，CU)，對于亮度像素CU，其尺寸可以從64×64一直遞歸劃分至8×8，CU的遞歸劃分過程如圖3所示。較大塊的CU可以被劃分成較小的CU，例如對于depth=n的CU，若劃分標志位(splitflag)為1，則繼續(xù)劃分為depth=n+1的4個小CU，每個較小CU的尺寸是上一深度CU的1/2。

圖3 CU中不同深度所占的復(fù)雜度

從圖3中可以得到，編碼單元CU的深度一共可分為0，1，2，3，分別對應(yīng)編碼單元的大小為64×64，32×32，16×16，8×8。在遞歸劃分的過程中需要進行大量的RDO計算，LCU的遞歸劃分過程也占到了編碼時間的90%，因此通過提前終止CU的劃分，減少CU深度大小能夠有效減少視頻編碼復(fù)雜度，達到縮短視頻編碼時間的目的[19]。

HEVC幀內(nèi)預(yù)測復(fù)雜度可以通過不同的編碼參數(shù)對其進行評估，比如說編碼的總時間。在本文中，在不需要考慮操作系統(tǒng)的其他性能時，可以通過軟件分析器來獲得編碼時間，統(tǒng)計3個1 280×720分辨率的視頻測試序列(Four People，Johnny和Kristen and Sara)的每個CU深度的編碼時間。其中每個序列的幀數(shù)均為150幀，因此總的編碼時間基本上也都很相似。

圖3顯示了每一個CU深度層的平均編碼時間比。CDN代表不同深度的時間比，N從0到3。從圖中可以看出，深度越大，計算所占的時間比重越大。因此，對復(fù)雜度的控制可以轉(zhuǎn)化為對深度進行優(yōu)化，從而大大減少編碼時間。

3.2 幀內(nèi)預(yù)測中候選預(yù)測方向個數(shù)復(fù)雜度分析

幀內(nèi)預(yù)測是視頻編碼過程中的一個重要組成部分，它充分利用圖像的空間相關(guān)性，來提高壓縮效率。然而幀內(nèi)預(yù)測具有極高的算法復(fù)雜度，實時性要求高的場合使用起來效果往往不是很好，特別是在出現(xiàn)場景切換時，編碼器會進行大量的幀內(nèi)預(yù)測。因此在實際應(yīng)用中需要加快幀內(nèi)預(yù)測過程，使得編碼過程更加流暢，減少卡幀現(xiàn)象。

對于不同尺度大小PU，最佳的候選預(yù)測方向個數(shù)也不同，大小為16×16，32×32，64×64的PU只有3個預(yù)測方向，大小為4×4和8×8的PU有8個預(yù)測方向。因此在保證圖像損失很小的情況下，可以減少候選預(yù)測方向個數(shù)來減少編碼時間。本文對不同大小的PU的候選預(yù)測方向個數(shù)進行調(diào)整，通過實驗定義了4種不同的候選預(yù)測方向個數(shù)組合CP1，CP2，CP3，CP4，如表1所示。

表1 不同PU大小對應(yīng)不同的候選預(yù)測方向組合

測試在定義的4種不同的候選預(yù)測方向個數(shù)組合下，記錄對應(yīng)的視頻編碼過程中的時間減少(ΔTime/%)和峰值性噪比的減少(ΔY-PSNR/dB)，變化趨勢如圖4所示。其中參與測試的視頻序列有BasketballPass，BQSquare，BasketballDrill，BQMall和FourPeople，編碼幀數(shù)為150幀。由圖4分析可得，隨著候選預(yù)測方向的減少，編碼時間會隨之減少，CP1組合有將近10%的時間減少，Y-PSNR的損失在0.01 dB以內(nèi)，而CP4組合有將近20%的時間減少，但是圖像質(zhì)量損失較大，已經(jīng)超過了0.1 dB。

圖4 不同候選模式組合與編碼時間和Y-PSNR的關(guān)系

綜合分析這4種組合的ΔTime和ΔY-PSNR可得：本文選擇CP1組合作為候選預(yù)測方向的最佳組合，此時時間下降明顯，同時視頻質(zhì)量沒有損失太多。此時，對復(fù)雜度的控制可以解釋為：先設(shè)定一個需要減少的目標時間，把候選預(yù)測方向的個數(shù)組合設(shè)定為CP1來達到復(fù)雜度控制的目的。

4 算法描述

為了更好地適應(yīng)視頻播放時出現(xiàn)場景切換的情況，并加快幀內(nèi)預(yù)測編碼時間來減少復(fù)雜度，本文提出了兩種解決方案：

1)對幀內(nèi)預(yù)測中編碼單元CU深度大小范圍進行調(diào)整，節(jié)省編碼時間；

2)對幀內(nèi)預(yù)測中的最佳候選模式數(shù)量進行調(diào)整。根據(jù)不同的情況，結(jié)合以上兩種方案，對編碼復(fù)雜度進行聯(lián)合控制。

在整個視頻序列中，分為需要做優(yōu)化算法的編碼幀Scn和不需要做優(yōu)化正常編碼的普通幀Su。如圖5所示，通常第一幀是不需要做優(yōu)化的普通幀，然而接下來的幀需要對其進行時間上的預(yù)測和控制，如果需要對其進行復(fù)雜度控制，則加入優(yōu)化算法，否則依然不需要進行優(yōu)化。

圖5 視頻編碼幀結(jié)構(gòu)

為了控制編碼復(fù)雜度，在CU深度方面對當前編碼幀的每一個64×64的CU塊進行統(tǒng)計，對其中的深度大小進行范圍統(tǒng)計，得到當前CU的深度范圍區(qū)間[MinDepth，MaxDepth]和深度范圍大小NumDepth，可以用來限制下一幀的同位CU的編碼深度的選擇。當需要進行優(yōu)化算法的編碼幀Scn進行編碼時，可以使用前一幀的深度信息去限制當前編碼塊的最大和最小深度，這樣就不需要做所有的RDO計算，從而節(jié)省了編碼時間。由于視頻存在時間相關(guān)性，前一幀與當前編碼幀存在一定的相似性，所以同位的CU區(qū)域也會擁有一個相似的深度范圍，在不影響編碼效率的情況下，可以對當前同位的CU使用前一幀的編碼深度范圍。

而在候選預(yù)測方向個數(shù)方面，通過前文分析可以得到，在使用CP1的候選預(yù)測組合時，時間減少了近10%，而圖片的質(zhì)量損失可以忽略不計。在本文中，主要考慮時間復(fù)雜度，定義視頻的編碼總時間復(fù)雜度為Tt，目標時間復(fù)雜度為Td，已編碼幀的時間復(fù)雜度為Tp。對當前幀進行編碼時，若已編碼的平均時間復(fù)雜度TYave比未編碼的平均時間復(fù)雜度TNave大，則加入優(yōu)化算法；若已編碼的平均復(fù)雜度TYave比未編碼的平均時間復(fù)雜度TNave小，則不加入優(yōu)化算法，正常編碼。TYave和TNave的計算公式如式(1)和式(2)所示

(1)

(2)

式中：n代表已經(jīng)編碼的幀數(shù)；N代表總編碼幀數(shù)。

總體的算法流程框圖如圖6所示。

圖6 算法結(jié)構(gòu)流程圖

具體的復(fù)雜度控制度算法如下：

1)第一幀正常編碼，記錄每個CU塊中的深度范圍[MinDepth，MaxDepth]和深度的范圍大小NumDepth。

2)通過式(1)和(2)得到TYave與TNave，如果TYave大于等于TNave的1.1倍，轉(zhuǎn)向步驟3)；若小于TNave的1.1倍并且大于等于TNave，則轉(zhuǎn)向步驟4)，其他情況轉(zhuǎn)向步驟5)。同時記錄當前幀的編碼深度信息。

3)當TYave大于等于TNave的1.1倍，表示當前需要減少的編碼時間較多，則直接利用深度優(yōu)化算法。如果前一幀同位CU的NumDepth大于0時，則表示前一幀同位CU中有不同的深度，那么當前編碼CU只需要遍歷[MinDepth，MaxDepth]。否則，表示前一幀同位CU深度都一樣，那么當前編碼CU需要編碼[0，MaxDepth]。同時記錄下當前幀的序號，如果連續(xù)超過4幀圖像使用深度優(yōu)化算法，為了保證視頻圖像的質(zhì)量，則從第5幀開始，對每個當前編碼塊的同位CU的MaxDepth減1。

4)當TYave小于TNave的1.1倍并且大于等于TNave，表示當前需要減少的編碼時間較少，為了保證視頻圖像質(zhì)量，則不使用深度優(yōu)化，直接調(diào)整模式候選個數(shù)，將候選模式預(yù)測組合切換到CP1。

5)當TYave小于TNave時，表示前面已編碼幀數(shù)的平均時間已經(jīng)小于目標時間下的剩余編碼平均時間，如果標記為優(yōu)化幀Scn，那么編碼總時間會達不到目標時間，所以直接標記為Su即可。

6)重復(fù)到步驟2)，直到編碼結(jié)束為止。

5 實驗分析

為了驗證本文算法的有效性，本文在HEVC參考軟件HM-15.0上進行仿真實驗。實驗平臺的硬件配置為Iter(R)-Core(TM)i7-4790CPU，主頻為3.60GHz，內(nèi)存為8Gbyte，操作系統(tǒng)為64位Windows7，開發(fā)工具為VS2013。實驗中，配置文件是“encoder_intra_main.cfg”。全I幀，原始的深度范圍是0～3(即[0，1，2，3])，其他參數(shù)均采用HM默認配置。

設(shè)定不同的目標復(fù)雜度，記為TC(%)={90，80，70，60}，在不同的目標復(fù)雜度的情況下，使用本文提出的復(fù)雜度控制算法。使用比特率的變化幅度百分比ΔBR、峰值性噪比(PSNR)的差值ΔPSNR和編碼時間減少TS來衡量編碼性能，TS計算方法如下[16]

(3)

實驗結(jié)果如表2所示，其中在不同的目標時間復(fù)雜度下，對表中19組不同的視頻測試序列使用不同量化參數(shù)QP進行測試，計算了QP分別為22，27，32，37時的ΔBR，ΔPSNR和TS的平均值。根據(jù)表2數(shù)據(jù)，分析3個視頻序列(BasketballPass，PartyScene，F(xiàn)ourPeople)的目標復(fù)雜度和實際復(fù)雜度的對比圖如圖7所示，可以明顯得出實際測得的復(fù)雜度和目標復(fù)雜度相差不多。從所有視頻序列的平均情況來看，目標時間復(fù)雜度TS從90%到60%，ΔPSNR平均值從0.01 dB到0.08 dB，其中效果最差的是序列BQSquare，在目標時間復(fù)雜度是60%的時候，PSNR下降了0.31 dB，總體上來說圖像的質(zhì)量損失不大，可以忽略不計。ΔBR平均值從0.02到2.32，其中效果最差的是序列BQSquare和BasketballDrill。除此之外，總體上比特率的變化不大。圖8給出了序列Johnny在不同QP下達到不同的目標復(fù)雜度時的PSNR和比特率，可以看出視頻圖像的質(zhì)量損失可以忽略不計。

為了能更好地看到每一幀時間復(fù)雜度的變化，圖9統(tǒng)計了目標復(fù)雜度為70%時，編碼100幀的時間折線圖。從圖中可以看到，實際每一幀的編碼時間在平均每一幀的編碼時間線的上下波動。更加明顯地體現(xiàn)了復(fù)雜度控制的作用性。綜上所述：本文提出的算法基本能達到目標的時間，從而對編碼過程進行復(fù)雜度的控制，同時編碼性能基本不變，保證了視頻圖像的質(zhì)量。

表2 實驗結(jié)果

圖7 序列的目標復(fù)雜度與實際復(fù)雜度

圖8 序列Johnny性能分析

6 結(jié)論

本文研究了基于HEVC幀內(nèi)預(yù)測的復(fù)雜度控制方法。提出了改變CU深度范圍和減少RDO候選模式個數(shù)的方法來聯(lián)合控制編碼復(fù)雜度。算法針對不同復(fù)雜度目標來自適應(yīng)地選擇不同的復(fù)雜度方法。當目標復(fù)雜度調(diào)整幅度比較大的時候采取CU深度范圍調(diào)整，而目標復(fù)雜度調(diào)整幅度較小的時候?qū)⑦x取減少RDO候選模式個數(shù)的方法。實驗結(jié)果表明，以上算法的效果比較明顯，能夠把復(fù)雜度控制做給定目標附近。

圖9 在目標復(fù)雜度為70%時，序列BasketballDrive每一幀所花費的時間

[1] SULLIVAN G J，OHM J，HAN W J，et al. Overview of the high efficiency video coding (HEVC) standard[J]. IEEE transactions on circuits and systems for video technology，2012，22(12)：1649-1668.

[2]朱秀昌，李欣，陳杰.新一代視頻編碼標準——HEVC.[J].南京郵電大學(xué)學(xué)報，2013，33(3)：2-3.

[3] POUAZAD M T，DOUTRE C，AZIMI M. HEVC：the new gold standard for video compression how does heve compare with H.264/AVC[J]. IEEE consumer electronis magazine，2012，1(3)：36-46.

[4]余越，周健，王貽良，等.一種場景切換檢測及自適應(yīng)碼率控制方法[J].通信學(xué)報，1999(5)：50-55.

[5]TAN Y H，LEE W S，THAM J Y， et al. Complexity scalable H.264/AVC encoding[J]. IEEE transactions on circuits & systems for video technology， 2010， 20(9)：1271-1275.

[6]SU L， LU Y， WU F， et al. Complexity-constrained H.264 video encoding[J]. IEEE transactions on circuits & systems for video technology， 2009， 19(4)：477-490.

[7]MA S， GAO W， LU Y. Rate-distortion analysis for H.264/AVC video coding and its application to rate control[J]. IEEE transactions on circuits & systems for video technology， 2005， 15(12)：1533-1544.

[8]CORREA G，ASSUNCAO P，AGOSTINI L，et al. Complexity control of high efficiency video encoders for power-constrained devices[J]. IEEE transations on consum. electron.，2011，57(4)： 1866-1874.

[9]UKHANOVA A，MILANI S，F(xiàn)ORCHHAMMER S. Game-theoretic ratedistortion-complexity optimization for HEVC[C]//Proc. IEEE 20th Int. Conf. Image Processing.[S.l.]：IEEE，2013：1995-1999.

[10] GRELLERT M. An adaptive workload management scheme for HEVC encoding[C]//Proc. IEEE 20th Int. Conf. Image Process.， Sep. 2013， pp. 1850-1854.

[11]LENG J, SUN L, IKENAGA T, et al. Content based hierarchical fast coding unit decision algorithm for HEVC[C]//Proc. Int. Conf. Multimedia Signal Processing. [S.l.]：IEEE，2011：56-59.

[12]SHEN X，YU L，CHEN J. Fast coding unit size selection for HEVC based on Bayesian decision rule[C]//Proc. Picture Coding Symp.[S.l.]：IEEE，2012：453-456.

[13]LAINEMA J， BOSSEN F， HAN W， et al. Intra coding of the HEVC standard[J]. IEEE transctions on circuits and systems for video technology，2012，22(12)：1792-1801.

[14]KIM I， MIN J， HAN W，et al. Block partitioning structure in the HEVC standard[J]. IEEE transctions on circuits and systems for video technology，2012，22(12)：1697-1706.

[15] OJALA T，PIETIKAINEN M，MAENPAA T. Multiresolution gray scale and rotation invariant texture classification with local binary patterns[J]. IEEE transactions on pattern analysis and machine intelligence，2002，24(7)：971-987.

[16]FENG P. Fast mode decision for intra prediction[S]. 2003.

[17]楊任爾，鄭紫薇，金煒.基于圖像特征的隱寫術(shù)載體圖像的旋轉(zhuǎn)[J].光電子·激光，2014，25(4)：764-768.

[18] WANG Z，BOVIK A C，SHEIKH H R，et al. Image quality assessment：from error visibility to structural similarity[J]. IEEE transactions on image processing， 2004，13(4)：600-612.

[19]XU D W，WANG R D，WANG J C. Prediction mode modulated data-hiding algorithm for H.264/AVC[J]. Journal of real-time image processing，2012，7(4)：205-214.

責任編輯：時 雯

Complexity control of HEVC intra prediction

LI Linge，ZHANG Lian，WANG Jie，ZHOU Qiao，ZHANG Hao

(SchoolofInformationScienceandEngineering,CentralSouthUniversity，Changsha410083，China)

Intra prediction is a very important module in video coding. In real-time video coding and transmission， scene changes frequently occur and all-I frames are usually adopted. Researches have showed that it also takes lots of time even using the all-I frames coding. In this paper， the coding unit depth range and the number of candidate prediction in intra prediction are used to control the coding complexity. According to different target coding complexity， different algorithm is adaptively used to optimize the coding process. The experiment results show that the algorithm in this paper achieves the different target complexity control on the condition of ensuring the quality of the video.

video coding； HEVC； intra prediction； complexity control

李林格，張戀，王潔，等.基于HEVC幀內(nèi)預(yù)測的復(fù)雜度控制[J].電視技術(shù)，2016，40(11)：18-24. LI L G，ZHANG L，WANG J，et al.Complexity control of HEVC intra prediction[J].Video engineering，2016,40(11)：18-24.

TN911

A

10.16280/j.videoe.2016.11.004

2016-03-30