吳良堤， 馮桂

(華僑大學(xué) 信息科學(xué)與工程學(xué)院， 福建 廈門(mén) 361021)

HEVC幀內(nèi)預(yù)測(cè)編碼的快速CU決策算法

吳良堤， 馮桂

(華僑大學(xué) 信息科學(xué)與工程學(xué)院， 福建 廈門(mén) 361021)

提出一種快速編碼單元(CU)修剪方法和CU深度范圍決策方法.在快速CU修剪方法中，根據(jù)貝葉斯決策準(zhǔn)則,基于殘差信息Hadamard變換絕對(duì)值之和(SATD)提前結(jié)束CU的修剪；在CU深度范圍決策方法中，根據(jù)當(dāng)前CU深度與空間鄰近CU深度的相似性決策當(dāng)前CU深度級(jí)范圍.通過(guò)在HM10.1的實(shí)驗(yàn)證明：文中方法相比于HM10.1的標(biāo)準(zhǔn)代碼，能降低35.9%的編碼時(shí)間，且BDBR的增加僅為1.039%. 關(guān)鍵詞： 高效視頻編碼; 幀內(nèi)編碼; 編碼單元; 殘差信息; Hadamard變換

2013年，JCT-VC制定了高效視頻編碼(HEVC)，它采用混合編碼結(jié)構(gòu)[1].HEVC引入了新的編碼工具，使其具有更高的壓縮能力，同時(shí)也導(dǎo)致了編碼復(fù)雜度的提高.為了提高HEVC的實(shí)時(shí)性，研究者們提出了3類(lèi)快速幀內(nèi)編碼算法：快速CU尺寸決策算法、快速模式?jīng)Q策算法和RQT優(yōu)化算法.在快速CU尺寸決策算法上，Shen等[2]將CU分割公式化，提出基于貝葉斯準(zhǔn)則的快速CU決策；Shen等[3]根據(jù)鄰近CU提出一個(gè)預(yù)測(cè)當(dāng)前CU深度的公式，跳過(guò)某些CU深度級(jí)搜索；Kim等[4]設(shè)定一個(gè)基于RD代價(jià)的閾值來(lái)提前終止當(dāng)前CU的分割；Xu等[5]利用灰度級(jí)自相關(guān)函數(shù)來(lái)決策當(dāng)前CU的深度范圍，同時(shí)利用固定的殘差信息Hadamard變換絕對(duì)值之和(SATD)作為閾值來(lái)提前終止CU修剪過(guò)程.在快速模式?jīng)Q策算法方面，Ting等[6]采用了變換域的邊緣檢測(cè)法，減化RMD模式個(gè)數(shù)；Fang等[7]通過(guò)計(jì)算特定角度的方向能量減少進(jìn)行RMD過(guò)程的預(yù)測(cè)模式；Yan等[8]通過(guò)對(duì)RMD后的模式進(jìn)行分組合并，減少RDO侯選模式個(gè)數(shù).在RQT優(yōu)化算法中，Teng等[9]利用合并分割決策過(guò)程代替原來(lái)的深度優(yōu)先模式?jīng)Q策過(guò)程；Zhang等[10]根據(jù)不同尺寸CU的最大幀間RQT深度在編碼性能上不相同，提出一種幀間模式的自適應(yīng)RQT選擇.上述算法在測(cè)試中都取得了一定的效果.Cho等[11]提出以RMD后的代價(jià)和RDO后的代價(jià)為閾值，利用貝葉斯準(zhǔn)則自適應(yīng)地對(duì)CU進(jìn)行快速修剪和分割.基于此，本文以SATD為閾值，利用貝葉斯準(zhǔn)則來(lái)自適應(yīng)地提前終止CU修剪過(guò)程.

(a) CU的分割 (b) 四叉樹(shù)結(jié)構(gòu) 圖1 CU的分割及對(duì)應(yīng)的四叉樹(shù)結(jié)構(gòu)Fig.1 Partitioning CU and corresponding quadtree structure

1 HEVC幀內(nèi)預(yù)測(cè)編碼概述

HEVC編碼中引入3種單元：編碼單元(CU)、預(yù)測(cè)單元(PU)和變換單元(TU).相對(duì)于H.264固定大小的宏塊，HEVC提供的CU尺寸從64×64到8×8，對(duì)應(yīng)深度(Depth)級(jí)分別從0到3.CU的分割及對(duì)應(yīng)的四叉樹(shù)結(jié)構(gòu)，如圖1所示.在HEVC測(cè)試模型(HM)中，幀內(nèi)預(yù)測(cè)編碼主要由CU分割和CU修剪完成.CU分割過(guò)程如下：首先，CU從Depth=0開(kāi)始進(jìn)行預(yù)測(cè)編碼，獲得率失真代價(jià)(RD Cost)；然后，將CU分割成4個(gè)等大的子CU，此時(shí)Depth=1，并對(duì)當(dāng)前CU進(jìn)行預(yù)測(cè)編碼得其RD Cost；以此類(lèi)推，直至CU深度為3時(shí)，結(jié)束分割.

CU修剪過(guò)程如下：從Depth=3的CU開(kāi)始，比較4個(gè)8×8子CU的RD Cost之和是否小于其父CU的RD Cost，若小于，則選擇子CU；否則，選擇父CU；以此類(lèi)推，直至Depth=0.32×32 CU的分割與修剪示意圖，如圖2所示.圖2中：灰色陰影為修剪過(guò)程;其他為分割過(guò)程.

HEVC幀內(nèi)預(yù)測(cè)提供了35種預(yù)測(cè)模式，如圖3所示.幀內(nèi)模式?jīng)Q策過(guò)程:首先,進(jìn)行粗選擇(RMD),即對(duì)35種預(yù)測(cè)模式進(jìn)行低復(fù)雜度的RD Cost計(jì)算，選出其中代價(jià)最小的N個(gè)，作為率失真優(yōu)化(RDO)的初始候選模式集;然后，判斷MPMs是否包含在初始候選模式集中，若不包含則將相應(yīng)模式添加到RDO初始候選模式集中，反之，則不添加;其次,對(duì)N到N+2個(gè)侯選模式用式(1)計(jì)算RD Cost，選出其中RD Cost最小的作為最佳預(yù)測(cè)模式;最后，利用RQT來(lái)得到最佳TU尺寸，即

(1)

式(1)中：SSE表示原始圖像塊與預(yù)測(cè)圖像塊差的平方和；λmode為拉格朗日乘子；Rmode為編碼預(yù)測(cè)模式信息所需的比特?cái)?shù).

圖2 32×32 CU的分割與修剪 圖3 幀內(nèi)預(yù)測(cè)模式及方向 Fig.2 32×32 CU splitting and CU pruning process Fig.3 Intra prediction modes and directions

2 快速幀內(nèi)CU尺寸決策算法

幀內(nèi)預(yù)測(cè)編碼復(fù)雜度增大的原因主要有兩方面：CU分割與修剪的復(fù)雜化和模式?jīng)Q策的復(fù)雜化.為了降低幀內(nèi)編碼的復(fù)雜度，根據(jù)當(dāng)前LCU與空間鄰近LCU深度的相似性，縮小LCU分割的深度范圍，同時(shí)提出了基于貝葉斯準(zhǔn)則利用SATD提前結(jié)束CU修剪過(guò)程.

圖4 當(dāng)前LCU的空間鄰近LCUFig.4 Spatial neighbor LCU of current LCU

2.1 空間鄰近LCU決策當(dāng)前LCU深度范圍

2.1.1 觀察與分析 在幀內(nèi)預(yù)測(cè)中，LCU分割深度級(jí)與圖像紋理有很大的關(guān)系.進(jìn)一步分析可知：當(dāng)前LCU的分割深度級(jí)與空間鄰近(左邊、上邊、左上、右上)LCU的分割深度級(jí)具有極大的相似性.當(dāng)前LCU與空間鄰近LCU 的空間位置關(guān)系,如圖4所示.

為了量化空間鄰近LCU與當(dāng)前LCU深度的相似度，定義相似度計(jì)算公式為

(2)

式(2)中：cur(i)為當(dāng)前第i個(gè)LCU的深度；nei_X(i)為與當(dāng)前第i個(gè)LCU鄰近(X=L表示左鄰近，以此類(lèi)推)的LCU的深度；N為統(tǒng)計(jì)的當(dāng)前LCU的總個(gè)數(shù)；SL，SU，SLU，SRU分別為與當(dāng)前LCU左鄰近、上鄰近、左上鄰近和右上鄰近LCU的相似度.當(dāng)前LCU的深度與鄰近LCU的深度相等時(shí)，cur(i)=nei_X(i)為1；否則為0.因此，SX的取值為[0，1].

經(jīng)過(guò)上述定義后，取各分辨率的序列，計(jì)算當(dāng)前LCU與各鄰近LCU的相似度.每個(gè)序列在不同的量化參數(shù)下編碼，量化參數(shù)選擇為22，27，32，37.其中：PeopelOnStreet，Cactus，BasketballDrill，BasketballPass屬于紋理復(fù)雜、運(yùn)動(dòng)較劇烈的序列；Traffic，BQMall，BQSquare屬于紋理較均質(zhì)、平坦，運(yùn)動(dòng)變化較小的序列；FourPeople，AristenAndSara屬于背景較簡(jiǎn)單、前景較復(fù)雜的序列.得到當(dāng)前LCU與鄰近LCU相似度SL，SU，SLU，SRU分別為0.795，0.794，0.788，0.763.由此可知:當(dāng)前LCU與左鄰近LCU、上鄰近LCU、左上鄰近LCU、右上鄰近LCU的相似度呈遞減趨勢(shì).因此，可以利用空間鄰近LCU的深度級(jí)跳過(guò)當(dāng)前LCU不太可能的深度級(jí)搜索.

2.1.2 算法內(nèi)容 記當(dāng)前LCU空間鄰近4個(gè)LCU的深度分別為：LDepth(左邊)、UDepth(上邊)、LUDepth(左上)、RUDepth(右上).

將LDepth，UDepth，LUDepth，RUDepth的異同分兩大類(lèi)：LDepth，UDepth，LUDepth，RUDepth有任意兩個(gè)深度相等；LDepth，UDepth，LUDepth，RUDepth的深度級(jí)各不相等.

對(duì)于第一大類(lèi)，又可分成兩小類(lèi)：LDepth≠UDepth和LDepth=UDepth.當(dāng)LDepth=UDepth時(shí)，當(dāng)前LCU有極高的可能性選擇與其相同的深度級(jí)作為當(dāng)前LCU的最佳分割深度級(jí).為了減少這種情況引起的編碼性能的損失，增加一個(gè)額外的深度級(jí)進(jìn)行搜索.此額外深度級(jí)e_Depth定義為

(3)

當(dāng)LDepth≠UDepth時(shí)，可通過(guò)判斷空間鄰近LCU各深度級(jí)的個(gè)數(shù)決策當(dāng)前LCU的深度級(jí)搜索.若空間鄰近LCU中深度0和深度1的個(gè)數(shù)之和多于深度2和深度3的個(gè)數(shù)之和，則將當(dāng)前LCU搜索深度級(jí)最大值設(shè)為2；反之，則將當(dāng)前LCU搜索深度級(jí)最小值設(shè)為1.

表1 空間鄰近LCU預(yù)測(cè)當(dāng)前LCU深度范圍命中率Tab.1 Hit-ratio of spatial neighbor LCU to predicted depth of current LCU

對(duì)于第二大類(lèi)，當(dāng)LDepth,UDepth,LUDepth只要有一個(gè)的深度為3，此時(shí)當(dāng)前LCU選擇深度級(jí)0為最佳分割的概率非常小.因此,將當(dāng)前LCU的深度級(jí)最小值設(shè)為1；反之，將當(dāng)前LCU的深度級(jí)最大值設(shè)為2.

為了證明上述算法中利用空間鄰近LCU深度預(yù)測(cè)當(dāng)前LCU深度搜索范圍的合理性，取與上述一致的測(cè)試序列，統(tǒng)計(jì)其命中率.統(tǒng)計(jì)結(jié)果如表1所示.通過(guò)表1分析可知：利用空間鄰近LCU跳過(guò)當(dāng)前LCU不必要的深度級(jí)搜索，平均命中率達(dá)到了94.1%，足以說(shuō)明所提出的利用空間鄰近LCU決策當(dāng)前LCU的深度范圍能精確、有效地排除不必要的深度級(jí)搜索.

由上幀內(nèi)預(yù)測(cè)編碼概述可知，HEVC引入了RMD算法，其計(jì)算代價(jià)表示為

(4)

式(4)中：SATD為殘差信息絕對(duì)Hadamard變換之和；λpred為拉格朗日乘子；Rpred為編碼預(yù)測(cè)模式信息所需的比特?cái)?shù).SATD的定義為

(5)

式(5)中：N為殘差信息塊的大小；di,j為殘差信息經(jīng)Hadamard變換后位于(i,j)的值,其定義式為

(6)

式(6)中:S為原始圖像塊；C為重構(gòu)圖像塊；H為Hadamard矩陣.

2.2.1 動(dòng)機(jī)與統(tǒng)計(jì) 將當(dāng)前CU不分割標(biāo)記為w1，分割標(biāo)記為w2，則由貝葉斯公式可得

(7)

式(7)中：P(SATD|wj)為在已知分割(或不分割)下SATD的條件概率；P(wj)為分割(或不分割)的先驗(yàn)概率，表示為

(8)

P(SATD)表示SATD的先驗(yàn)概率，表示為

2004年，為了開(kāi)拓外部市場(chǎng)，李淑榮被公司選派為新組建的南方項(xiàng)目組組長(zhǎng)，負(fù)責(zé)川東北地區(qū)測(cè)井解釋及方法研究工作。盡管有著豐富的工作經(jīng)驗(yàn)和驕人的工作業(yè)績(jī)，但擺在李淑榮面前的，不僅是川東北油區(qū)井深、含氣井段長(zhǎng)、多含硫化氫等復(fù)雜的地質(zhì)條件，還有和其他同行同臺(tái)競(jìng)技、搶奪市場(chǎng)份額的激烈競(jìng)爭(zhēng)。困難面前,李淑榮與她的團(tuán)隊(duì)選擇迎難而上。

(9)

由式(7)可知：為了利用貝葉斯準(zhǔn)則判斷當(dāng)前CU分割與否，需先統(tǒng)計(jì)相關(guān)的參量，如表2所示.

表2 各CU級(jí)下需獲取的參數(shù)Tab.2 Needed parameters in each CU depth level

為使算法具備較好的適應(yīng)性，文中相關(guān)參量都是在線周期性更新，更新周期為幀率.

如同文獻(xiàn)[11]的JSATD服從高斯隨機(jī)分布，文中也先假設(shè)SATD服從高斯分布.從這一假設(shè)出發(fā)，統(tǒng)計(jì)了SATD與P(SATD|w2)，SATD與P(SATD|w1)的關(guān)系.經(jīng)過(guò)使用各種測(cè)試序列進(jìn)行大量的實(shí)驗(yàn)，證明了SATD近似服從高斯分布.以BasketballDrill這一序列為例，其中,SATD以200為間隔，統(tǒng)計(jì)了QP=37,深度為2時(shí)的實(shí)際分布，并給出其擬合的高斯模型，如圖5所示.

(a) P(SATD|w2) (b) P(SATD|w1)圖5 BasketballDrill序列的RDcost實(shí)際分布及其擬合高斯模型Fig.5 BasketballDrill sequence actual distribution of RD cost and fit Gaussian distribution

2.2.2 閾值的計(jì)算 CU提前修剪的貝葉斯決策，如圖6所示.由圖6可知：αST表示在CU繼續(xù)分割時(shí)被判斷為不再分割的概率.在每一個(gè)CU的深度級(jí)上，當(dāng)最小SATD小于預(yù)設(shè)閾值SATD_TH時(shí)，則執(zhí)行提前修剪算法.由圖6易得

圖6 CU提前修剪的貝葉斯決策Fig.6 Bayes decision for early CU pruning

(10)

式(10)中:x=SATD.將式(10)變換為

(11)

(12)

式(12)中：z為服從標(biāo)準(zhǔn)正態(tài)分布變量積分的上界，可由查找標(biāo)準(zhǔn)正態(tài)分布表得到其值.即

(13)

大量實(shí)驗(yàn)證明，取αST=0.1時(shí)，在編碼時(shí)間與碼率損失之間可以達(dá)到較好的平衡.

3 結(jié)果與分析

文中提出的快速幀內(nèi)CU尺寸決策算法在HM10.1上實(shí)現(xiàn).實(shí)驗(yàn)配置參照文獻(xiàn)[12]，使用QP=22，27，32，37，LCU尺寸為64×64，最大深度級(jí)為4.測(cè)試使用JCT-VC推薦的5個(gè)類(lèi)別序列：ClassA，ClassB，ClassC，ClassD，ClassE.所用計(jì)算機(jī)處理器為AMD Athlon(tm)2×2 B28.使用BDBR，BDPSNR[13]來(lái)衡量編碼性能，用平均節(jié)省時(shí)間(ATS)來(lái)衡量編碼復(fù)雜度的降低,即

(14)

式(14)中：TimeHM10.1(QPi)，Timepro(QPi)分別為原始HM10.1與文中算法在不同QP下的編碼時(shí)間.

文中算法與文獻(xiàn)[3]，[4]比較的實(shí)驗(yàn)結(jié)果，如表3所示.文中算法與文獻(xiàn)[5]ClassE測(cè)試序列的對(duì)比結(jié)果，如表4所示.

表3 文中算法與文獻(xiàn)[3],[4]算法比較結(jié)果Tab.3 Performance comparison between proposed and literature [3]，[4]

表4 文中算法與文獻(xiàn)[5]算法ClassE測(cè)試序列的比對(duì)Tab.4 Coding performance compared with ClassE in literature [5]

通過(guò)表3可知：文中算法平均能節(jié)省35.9%的編碼時(shí)間，引起1.039%的BDBR增加.同時(shí)，從表3中可以發(fā)現(xiàn)：相較于文獻(xiàn)[3]，文中算法以增加微量的BDBR為代價(jià)，平均多節(jié)省了14.5%的編碼時(shí)間；與文獻(xiàn)[4]相比較，文獻(xiàn)[4]算法對(duì)ClassE的測(cè)試序列碼率增加比較大，平均為3.339%；而文中算法對(duì)18個(gè)測(cè)試序列編碼性能的損失都沒(méi)那么嚴(yán)重，最大僅為1.654%；同時(shí)可以發(fā)現(xiàn)兩者的平均率失真性能幾乎相等，但文中算法編碼時(shí)間減少的更多，平均多降低了3.4%.這說(shuō)明文中算法與文獻(xiàn)[4]相比，所有的測(cè)試序列都能在編碼時(shí)間與碼率之間達(dá)到更好的平衡.

由表4可知：雖然文中算法在編碼時(shí)間降低上略有不足，但其對(duì)ClassE序列平均BDBR的增加為1.654%；而文獻(xiàn)[5]對(duì)ClassE序列平均BDBR增加了4.765%，在Johnny測(cè)試序列中達(dá)到了7.565%這是比較難以接受的.通過(guò)這一點(diǎn)的對(duì)比，更能突顯出文中算法對(duì)序列的自適應(yīng)性.

4 結(jié)束語(yǔ)

提出了基于貝葉斯準(zhǔn)則使用SATD提前終止CU修剪過(guò)程，同時(shí)利用空間鄰近LCU與當(dāng)前LCU深度級(jí)的相似性決策當(dāng)前LCU深度范圍的快速CU尺寸決策算法.該算法相比于原本的HM10.1，平均能節(jié)省35.9%的編碼時(shí)間，而引起的平均碼率增加只有1.039%.下一步的研究方向主要是在幀內(nèi)模式?jīng)Q策上進(jìn)行改進(jìn)，從而獲得更大的編碼復(fù)雜度降低.

[1] SULLIVAN G J,HAN W J,WIEGAN D T.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] SHEN Xiaolin,YU Lu,CHEN Jie.Fast coding unit size selection for HEVC based on Bayesian decision rule[C]∥Picture Coding Symposium.Krakow：IEEE Press，2012:453-456.

[3] SHEN Liquan,ZHANG Zhaoyang,AN Ping.Fast CU size decision and mode decision algorithm for HEVC intra coding[J].IEEE Transactions on Consumer Electronics,2013,59(1):207-213.

[4] KIM J,CHOE Y,KIM Y G.Fast coding unit size decision algorithm for intra coding in HEVC[C]∥IEEE International Conference on Consumer Electronics.Las Vegas:IEEE Press,2013:637-638.

[5] XU Dongxu,LIN Qiwei,DONG Xiaohui.Fast intracoding unit size decision algorithm for high-efficiency video coding[J].Journal of Electronic Imaging,2014,23(1):013012.

[6] TING Y C,CHANG T S.Fast intra prediction algorithm with transform domain edge detection for HEVC[C]∥IEEE Asia Pacific Conference on Circuits and Systems.Kaohsiung:IEEE Press,2012:144-147.

[7] FANG Cemin,CHANG Yuanteng,CHUNG Wenhao.Fast intra mode decision for HEVC based on direction energy distribution[C]∥IEEE 17th International Symposium on Consumer Electronics.Hsinchu:IEEE Press,2013:61-62.

[8] YAN Shunqing,HONG Liang,HE Wei-feng,etal.Group-based fast mode decision algorithm for intra prediction in HEVC[C]∥Eighth International Conference on Signal Image Technology and Internet Based Systems.Naples:IEEE Press,2012:225-229.

[9] TEND S W,HANG H M,CHEN Y F.Fast mode decision algorithm for residual quadtree coding in HEVC[C]∥IEEE Visual Communications and Image Processing.Tainan:IEEE Press,2011:1-4.

[10] ZHANG Yongfei,ZHAO Mingfei.An adaptive RQT mode selection algorithm for HEVC[C]∥5th International Congress on Image and Signal Processing.Chongqing:IEEE Press,2012:173-177.

[11] CHO S,KIM M.Fast CU splitting and pruning for suboptimal CU partitioning in HEVC intra coding[J].IEEE Transactions on Circuits and Systems for Video Technology,2013,23(9):1555-1564.

[12] BOSSEN F.Common HM test conditions and software reference configuration[C]∥12th JCT-VC Meeting.Geneva:JCTVC-L1100,2013:1-3.

[13] BJONTEGAARD G.Calculation of average PSNR difference between RD-curves[C]∥13th VCEG-M33 Meeting.Austin:[s.n.],2001：290-294.

(責(zé)任編輯： 黃曉楠 英文審校： 吳逢鐵)

Fast CU Decision Algorithm for HEVC Intra Prediction Coding

WU Liangdi， FENG Gui

(College of Information Science and Engineering, Huaqiao University, Xiamen 361021, China)

In this paper, a fast coding unit (CU) pruning and depth levels decision method is proposed. The early CU pruning method is performed according to a Bayes decision rule method based on the absolute sum of Hadamard transformed coefficients of the residual signal (SATD). Based on the depth information resemblance between spatio adjacent CUs and the current CU, some depths can be excluded. Experimental results show that the proposed algorithm achieves 35.9% encoder time saving on average compared to the original coding in HM10.1 with only 1.039% bit rate increment in coding performance.

high efficiency video coding; intra coding; coding unit; residual information; absolute sum of Hadamard transformed

10.11830/ISSN.1000-5013.201704021

2016-09-04

馮桂(1960-)，女，教授，博士，主要從事圖像信息處理的研究.E-mail:fengg@hqu.edu.cn.

福建省自然科學(xué)基金資助項(xiàng)目(2014J01242, 2016J01306)

TN 919.81

A

1000-5013(2017)04-0556-06