雷海軍，楊忠旺，陳 驍，袁梅冷

一種快速HEVC編碼單元決策算法

雷海軍1，楊忠旺1，陳 驍2，袁梅冷3

(1. 深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院，廣東 深圳 518060；2. 創(chuàng)維集團(tuán)深圳研究院，廣東 深圳 518060； 3. 深圳職業(yè)技術(shù)學(xué)院，廣東 深圳 518060)

分析高效視頻編碼標(biāo)準(zhǔn)(HEVC)的編碼單元算法，針對當(dāng)前視頻編碼標(biāo)準(zhǔn)計(jì)算復(fù)雜度大的問題，基于相鄰編碼單元相關(guān)性和紋理特性，提出一種快速HEVC編碼單元決策算法。該算法統(tǒng)計(jì)當(dāng)前編碼單元和相鄰編碼單元的相關(guān)性，分析編碼單元的紋理復(fù)雜度，并設(shè)定合理的閾值，決定檢測是否提前終止，以此快速找到最優(yōu)編碼單元。仿真結(jié)果表明，該算法與HEVC參考軟件HM8.0相比，在碼率增加忽略不計(jì)的情況下，編碼時(shí)間平均縮短了37.4%，最高可達(dá)48.2%。

高效視頻編碼；編碼單元；計(jì)算復(fù)雜度；提前終止；紋理特征；碼率

1 概述

隨著數(shù)字技術(shù)的快速發(fā)展以及互聯(lián)網(wǎng)的廣泛應(yīng)用，圖像和視頻壓縮技術(shù)已經(jīng)滲透到人們的日常生活中，而且近幾年對高清和超高清的需求服務(wù)越來越大。雖然H.264/AVC在高清視頻處理方面仍不能得到具體應(yīng)用，但隨著大量的新技術(shù)不斷涌現(xiàn)，編碼性能不斷提高，在H.264基礎(chǔ)上進(jìn)一步提升高清視頻的壓縮效率已成為可能。為此，國際電信聯(lián)盟(ITU-T)與ISO/IEC移動(dòng)圖像專家(MPEG)成立了視頻編碼聯(lián)合小組(JCT-VC)，通過研究并制定下一代視頻編碼標(biāo)準(zhǔn)——高效視頻編碼(High Efficient Video Coding, HEVC)，旨在H.264/AVC的高級檔次基礎(chǔ)上，使壓縮效率提高1倍[1-2]。

HEVC同樣采用預(yù)測加變換的混合編碼結(jié)構(gòu)，然而HEVC采用更加靈活的編碼塊結(jié)構(gòu)：編碼單元(CU)，預(yù)測單元(PU)和轉(zhuǎn)換單元(TU)，其中，CU作為編碼的基本單元，類似于H.264的宏塊；PU作為預(yù)測的基本單元，是在CU基礎(chǔ)上進(jìn)一步分割得到；TU作為變換的基本單元，更能適合不同圖像的內(nèi)容[3-4]。由于編碼單元決定最初塊的大小，對后面的預(yù)測單元、變換單元的一步劃分都有很大影響，文獻(xiàn)[5]指出不同的編碼單元的性能大不相同，相對于編碼大小為16×16，設(shè)置編碼單元大小為64×64可以減少12%的比特率。因此，編碼單元在降低編碼復(fù)雜度方面起著很重要的作用。

本文通過分析HEVC中相鄰編碼單元編碼模式的相關(guān)性和編碼單元的紋理，提出一種快速的編碼單元模式選擇算法，以降低編碼復(fù)雜度。

2 參考模型中的編碼單元決策算法

HEVC標(biāo)準(zhǔn)采用大小可變的編碼單元，范圍從最小編碼單元8×8到最大編碼單元64×64，按照四叉樹塊結(jié)構(gòu)，可以遞歸地把最大編碼單元(LCU)分割成4塊以得到合適的編碼單元大小。

圖1顯示了HEVC中編碼單元在各深度的劃分。64×64是深度為0的最大的編碼單元(LCU)；8×8是深度為3的最小的編碼單元(SCU)。是否進(jìn)行分割由分割標(biāo)志決定，當(dāng)分割標(biāo)志為1時(shí)，LCU被分割成4個(gè)子編碼單元，否則LCU不進(jìn)行劃分；當(dāng)遞歸分割到四叉樹的葉結(jié)點(diǎn)或者達(dá)到制定要求時(shí)，終止繼續(xù)分割。這樣如果為找到一個(gè)最優(yōu)的編碼單元大小而計(jì)算所有的編碼單元，重復(fù)計(jì)算85個(gè)編碼單元的率失真消耗[6]，并且比對其大小，將花費(fèi)大量的編碼時(shí)間。

圖1 HEVC編碼單元結(jié)構(gòu)

現(xiàn)階段HEVC參考模型已經(jīng)采納了SKIP模式提前終止[7]、基于CBF的提前終止算法[8]和編碼單元提前終止算法[6]，這幾種方案都在一定程度上降低編碼復(fù)雜度。SKIP模式主要采用式(1)提前終止編碼單元分割：

雖然SKIP模式可以降低約50%的編碼時(shí)間，但由于圖像的質(zhì)量也隨之降低很大，默認(rèn)不可用。文獻(xiàn)[9]提出了 一種基于編碼單元部分檢測的快速選擇算法，編碼復(fù)雜度降低10%，文獻(xiàn)[10]通過貝葉斯統(tǒng)計(jì)設(shè)置閾值決策編碼單元的大小等。

HEVC測試模型8.0采用如圖2所示流程決定當(dāng)前編碼單元是否分割。首先初始化率失真值，編碼當(dāng)前的編碼單元，記錄當(dāng)前編碼的結(jié)果和消耗；然后查看現(xiàn)在編碼單元所處的深度是否達(dá)到最大的允許深度，如果達(dá)到最大深度，則終止繼續(xù)分割；遞歸處理分割的各個(gè)子編碼單元，計(jì)算得到率失真消耗；最后比較沒有分割時(shí)的編碼單元的消耗和分割后的率失真消耗，如果前者大于后者，則進(jìn)行分割；否則不進(jìn)行分割終止。

圖2 LCU分割方法流程

3 快速?zèng)Q策算法

3.1 相關(guān)性測試及閾值設(shè)定

本文根據(jù)當(dāng)前編碼單元和相鄰編碼單元的空間相關(guān)性合理設(shè)置閾值參數(shù)，在圖像質(zhì)量變化不大的情況下，降低了編碼復(fù)雜度。由于SKIP/MERGE模式提前終止算法已經(jīng)能很大程度上降低編碼復(fù)雜度，只要能降低對圖像質(zhì)量的損耗就可以達(dá)到一個(gè)很不錯(cuò)的效果。而且如果當(dāng)前的編碼單元的最佳模式為SKIP，那么式(1)中的權(quán)值參數(shù)能更高。所以本文分別測試相鄰編碼單元和父母編碼單元(如果當(dāng)前編碼單元的深度為1，則父母編碼單元為0)與當(dāng)前編碼單元的相關(guān)性。圖3顯示了當(dāng)前編碼單元的測試依賴關(guān)系。其中，0表示父母編碼單元；1表示當(dāng)前的編碼單元；2表示當(dāng)前編碼單元的左側(cè)相鄰編碼單元；3表示當(dāng)前編碼單元的上側(cè)相鄰編碼單元。

圖3 測試編碼單元相關(guān)性模型

為進(jìn)一步驗(yàn)證相鄰的CU的相關(guān)性概率，設(shè)定測試條件如下：

測試條件1當(dāng)前編碼單元為SKIP/MERGE模式時(shí)，相鄰的編碼單元為SKIP/MERGE模式的概率。

測試條件2父母編碼單元為SKIP/MERGE時(shí)，當(dāng)前編碼單元為SKIP/MERGE的概率。

由表1可以看出，使用測試條件1時(shí)的概率最大達(dá)到90%，平均相關(guān)性概率為73.4%；使用測試條件2時(shí)最大概率為接近90%，平均相關(guān)性概率達(dá)到75.8%。根據(jù)測試項(xiàng)及結(jié)果很明顯可以得到當(dāng)前編碼單元不僅與相鄰的編碼單元有很大的相關(guān)性，而且和上一層編碼單元也有很大的相關(guān)性。

表1 相關(guān)性概率 %

通過編碼單元的相關(guān)性調(diào)整式(1)中的權(quán)值系數(shù)，首先調(diào)整權(quán)值系數(shù)為0.8，然后如果相鄰的編碼單元為SKIP/ MERGE模式時(shí)，更改權(quán)值系數(shù)為1；如果更高一層或父母編碼單元為SKIP/MERGE時(shí)，同樣調(diào)整編碼系數(shù)為1.5。

3.2 編碼單元紋理特征分析

HEVC支持最大編碼達(dá)到64×64，如果編碼單元比較平緩或者具有方向(垂直方向水平方向等)，則當(dāng)前編碼單元比較適合大尺寸編碼單元預(yù)測。這樣可以通過式(2)當(dāng)前編碼單元的紋理復(fù)雜度，然后設(shè)定不同大小編碼單元的閾值，從而快速地決策當(dāng)前的編碼單元是否進(jìn)行分割，從而減少編碼時(shí)間[11]，如果當(dāng)前的編碼單元的大小為64×64，然后計(jì)算相應(yīng)的紋理復(fù)雜度，若小于設(shè)定的閾值，當(dāng)前的編碼單元不進(jìn)行分割，否則把當(dāng)前編碼單元分割成更好的編碼單元，然后再比較分割后的大小，并且判斷此時(shí)是否滿足對應(yīng)此大小的閾值。

其中，表示當(dāng)前編碼單元的紋理復(fù)雜度；為當(dāng)前編碼像素?cái)?shù)；(,)為(,)所制定的像素值。

3.3 整體算法流程

經(jīng)過上述過程分析以及HM8.0，采用圖4所述的算法流程。首先從最小深度，也就是最大編碼單元LCU開始，選取預(yù)測模式，然后進(jìn)行SKIP/MERGE模式的提前終止檢測，如果滿足條件，則直接終止；如果不滿足條件則檢測當(dāng)前編碼單元的紋理復(fù)雜度，如果小于設(shè)定的閾值則編碼單元相對平坦不進(jìn)行劃分，否則按照標(biāo)準(zhǔn)中的判斷方式進(jìn)行檢測，這樣既可以保證準(zhǔn)確度，又可以減少編碼單元分割所需時(shí)間。算法具體流程如圖4所示。

圖4 本文算法流程

4 實(shí)驗(yàn)仿真結(jié)果

本文實(shí)驗(yàn)仿真采用HEVC參考模型HM8.0，測試條件與測試序列采用提案JCTVC-E700[12]。電腦配置如下：CPU為Intel Pentium E5800 3.2 GHz，內(nèi)存為2 GB。

表2顯示了本文算法與HM8.0之間編碼性能的比較結(jié)果。其中，(%)表示碼率的變化，采用文獻(xiàn)[13]中公式計(jì)算；Δ(%)表示時(shí)間的變化，根據(jù)下式計(jì)算：

表2 編碼性能比較 %

可以看出，本文算法與HM8.0相比，PSNR減少幅度較小，平均減少0.9 dB，碼率稍有增長，平均增加1.2%，但是編碼時(shí)間最大可節(jié)省48.2%，平均節(jié)省37.4%，而且在較平緩序列中節(jié)省時(shí)間相對更大。通過合理設(shè)定閾值能在很少增加或者不增加比特率的情況下，大幅提高編碼效率，降低編碼時(shí)間。

5 結(jié)束語

本文分析HEVC編碼在單元空間上的相關(guān)性，研究編碼單元的紋理特性，通過減少編碼單元預(yù)測模式，提出一種快速的編碼單元決策方法。與HEVC參考模型相比，本文算法平均可減少37.4%編碼時(shí)間，而且對不同的序列有明顯的效果，能很好地提高編碼效率、降低編碼復(fù)雜度。下一步主要將結(jié)合編碼單元和預(yù)測單元，進(jìn)一步加快編碼單元決策，減少幀內(nèi)模式預(yù)測數(shù)量，降低預(yù)測單元模式選擇復(fù)雜度，提高整個(gè)編碼端的效率。

[1] OurazadMTP, DoutreC,AzimiM, et al.HEVC:The New Gold Standard for Video Compression[J].IEEE Consumer Electronics,2012, 1(3):36-46.

[2] 蔡曉霞, 崔巖松, 鄧中亮, 等. 下一代視頻編碼標(biāo)準(zhǔn)關(guān)鍵技術(shù)[J]. 電視技術(shù), 2012, 36(2): 80-84.

[3] BossenF, BrossB, SuhringK,et al. HEVC Complexity and Implementation Analysis[J]. IEEE Transactionson Circuits and Systems for Video Technology, 2012,22(12):1685-1696.

[4] SullivanGJ, OhmJR, HanWJ, et al. Overview of the High Efficiency Video Coding(HEVC) Standard[J]. IEEE Transac- tions on Circuits and Systems for Video Technology, 2012,22(12): 1649-1668.

[5] Kim M K J.Report on Large Block Structure Testing[C]//Proc.of JCT-VC’10. Guangzhou, China: [s. n.], 2010: 1-4.

[6] ChoiK, JangES. Fast Coding Unit Decision Method Based on Coding Tree Pruning for High Efficiency Video Coding[J]. Optical Engineering, 2012, 51(3).

[7] Han WJ, Min J, Lee T, et al. Improved Video Compression Efficiency Through Flexible Unit Representation and Corres- ponding Extension of Coding Tools[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2010, 20(12):1709-1720.

[8] GweonRH,LeeYL, LimJ. Early Termination of CU Encoding to Reduce HEVC Complexity[C]//Proc. of JCT-VC’11. Torino, Italy: [s. n.], 2011: 1-5.

[9] TanHuili, LiuFengjiao, TanYH, et al. On Fast Coding Tree Block and Mode Decision for HEVC[C]//Proc. of Conference on Acoustics, Speech and Signal Processing. Kyoto,Japan: [s. n.], 2012:825-828.

[10] ShenXiaolin, YuLu,ChenJie. Fast Coding Unit Size Selection for HEVC Based on Bayesian Decision Rule[C]//Proc. of 2012 Picture Coding Symposium. Krakow, Poland: IEEE Press, 2012: 453-456.

[11] TianGuifen, GotoS. Content Adaptive Prediction Unit Size Decision Algorithm for HEVC Intra Coding[C]//Proc. of 2012 Picture Coding Symposium. Krakow,Poland: IEEE Press, 2012: 405-408.

[12] BossenF. Common Test Conditions and Software Reference Configurations[C]//Proc. of JCT-VC’11.Geneva,Switzerland: [s. n.], 2011: 1-22.

[13] Senzaki K, Chono H, Aoki J, et al. BD-PSNR/Rate Compu- tation Tool for Five Data Points[C]//Proc. of JCT-VC’10. Geneva, Switzerland: [s. n.], 2010: 1-11.

編輯 金胡考

A Fast Coding Unit Decision Algorithm for HEVC

LEI Hai-jun1, YANG Zhong-wang1, CHEN Xiao2, YUAN Mei-leng3

(1. College of Computer and Software, Shenzhen University, Shenzhen 518060, China; 2. Shenzhen Research Institute of Skyworth Group,Shenzhen 518060, China; 3. Shenzhen Polytechnic, Shenzhen 518060, China)

This paper analyzes coding unit algorithm of High Efficient Video Coding(HEVC) standard. Aiming at its high computational complexity, this paper proposes a fast coding unit decision algorithm for HEVC based on the coding unit correlation and texture of coding unit. This algorithm counts the correlation of current coding unit and adjacent coding unit, calculates texture complexity of encoding units, sets a reasonable threshold, and detects early termination, to quickly find the optimal coding unit. Simulation results show that, compared with the HEVC conference software HM8.0, the proposed algorithm can reduce about 37.4% encoding time and up to 48.2%, while it suffers from negligible on bit-rates performance.

High Efficient Video Coding(HEVC); coding unit; computational complexity; early termination; texture characteristic; bit rate

1000-3428(2014)03-0270-04

A

TP37

國家自然科學(xué)基金資助項(xiàng)目(60972037)；廣東省部產(chǎn)學(xué)研基金資助項(xiàng)目(2012B091100495, 2009B090300267)；深圳市基礎(chǔ)研究基金資助項(xiàng)目(JCYJ20120613113419607)。

雷海軍(1968－)，男，副教授，主研方向：圖像/視頻處理，模式識別；楊忠旺，碩士研究生；陳 驍，工程師、碩士；袁梅冷，副教授、碩士。

2013-01-23

2013-03-18 E-mail：15969714254@163.com

10.3969/j.issn.1000-3428.2014.03.057