張聰聰，李子印，應(yīng)凌楷，郭笙聽

(中國計量學院 光學與電子科技學院，浙江 杭州 310018)

?

紋理的HEVC編碼塊尺寸決策算法

張聰聰，李子印，應(yīng)凌楷，郭笙聽

(中國計量學院 光學與電子科技學院，浙江 杭州 310018)

【摘要】針對高效視頻編碼(HEVC)幀內(nèi)編碼算法計算復(fù)雜度高的問題，提出了一種基于紋理的HEVC編碼塊尺寸快速決策算法.首先，提出了編碼塊四個方向的紋理復(fù)雜度衡量指標，再通過訓練視頻序列選取在不同量化參數(shù)(QP)下的最佳閾值，最后根據(jù)閾值判斷當前編碼塊的紋理復(fù)雜度，紋理復(fù)雜度高的編碼塊跳過率失真(RD)代價的計算，紋理復(fù)雜度低的編碼塊將會終止劃分.實驗結(jié)果表明，在全幀內(nèi)模式配置下，與HM10.0相比較，該算法的編碼時間可縮短45.3%，同時BD-Bitrate(Bjontegaard Delta Bitrate)增加了1.27%，BD-PSNR(Bjontegaard Delta Peak Signal-to-noise Rate)減少了0.058 dB；與GEC-LEC算法相比，編碼時間可節(jié)省3%，BD-Bitrate增加了0.5%，BD-PSNR減少了0.023 dB.

【關(guān)鍵詞】高效視頻編碼；紋理復(fù)雜度；編碼塊尺寸

隨著人們對高清和超高清視頻需求的不斷增加，H.264編碼技術(shù)在編碼效率上已經(jīng)不能滿足需求.另外，手機和電腦產(chǎn)生的海量視頻流量及視頻的實時傳輸，對當今的網(wǎng)絡(luò)提出了巨大的要求和挑戰(zhàn)[1].

視頻編碼技術(shù)是一種對視頻信息去除信息冗余，從而進行有效壓縮、存儲和網(wǎng)絡(luò)傳輸?shù)募夹g(shù).為了提高編碼效率，ITU-T和ISO/IEC 聯(lián)合制定了新一代高效視頻編碼(HEVC)標準.與H.264/AVC相比，HEVC支持更大的編碼深度和更大的編碼塊，以及更多的幀內(nèi)預(yù)測模式.HEVC支持的最大編碼塊的大小為64×64，定義其深度為0，最小編碼塊的大小為8×8，定義其深度為3，其余大小為32×32、16×16的編碼塊，其深度分別為1和2；而H.264支持的最大編碼塊為16×16的宏塊[2].HEVC的幀內(nèi)預(yù)測模式增加到了35個模式[3]，而H.264只有8個幀內(nèi)預(yù)測模式.由于HEVC有更大的編碼深度和更多的幀內(nèi)預(yù)測模式，以及基于四叉樹遞歸編碼方式，從而保證了HEVC幀內(nèi)編碼的高效性.HEVC采取基于四叉樹遞歸劃分方式來決定編碼塊的最終大小[4]，這種編碼塊遞歸劃分的方式，需要遞歸計算所有深度編碼塊的代價，因此，HEVC的幀內(nèi)編碼時間長于H.264的幀內(nèi)編碼時間.在保持HEVC編碼效率基本不變的前提下，縮短編碼時間，提出HEVC幀內(nèi)編碼塊尺寸的快速決策算法是相當必要的.

現(xiàn)有的HEVC幀內(nèi)編碼塊尺寸的快速決策算法大體上分可為三類：1)裁剪幀內(nèi)預(yù)測模式的算法；2)編碼塊遞歸劃分提前終止或跳過的算法；3)裁剪幀內(nèi)預(yù)測模式算法和編碼塊提前終止或跳過算法相結(jié)合的算法.Tian等人[5]首先把64×64大小的編碼塊下采樣成16×16的塊，通過計算16×16塊內(nèi)部的變化情況來決定編碼塊的最終大小，與HM4.0相比，編碼時間平均可節(jié)省28.8%；Nishikori等人[6]提出了基于方差的編碼塊遞歸劃分提前終止的快速算法，與HM8.0相比，其編碼時間平均可節(jié)省55%，BD-Bitrate平均增加了0.64%，但是只測試了六個視頻序列；Khan等人[7]基于香農(nóng)公式，提出了一種PUMA的編碼塊尺寸快速決策算法，與HM7.2相比，其編碼時間平均可節(jié)省43.7%，BD-Bitrate平均增加了1.27%，但是只測試了七個視頻序列；Kim等人[8]統(tǒng)計了所有編碼深度的率失真代價，提出了一種編碼塊遞歸劃分提前終止的快速算法，與HM5.2rc1相比，其編碼時間平均可節(jié)省24%，BD-Bitrate平均增加了0.83%；Zhang等人[9]提出了一種基于Hadmard代價的編碼塊遞歸劃分提前終止的快速算法，與HM7.0相比，其編碼時間平均可節(jié)省32%，BD-Bitrate平均增加了1.1%；Shen等人[10-11]提出了ADRD和ET-SCUME的快速分塊算法，與HM2.0相比，其編碼時間平均可節(jié)省42%，BD-Bitrate平均增加了1.49%；Min等人[12]提出了基于GEC-LEC的編碼塊遞歸劃分提前終止和跳過的快速算法，與HM10.0相比，其平均編碼時間可節(jié)省43.2%，BD-Bitrate平均增加了0.74%；Lim等[13]提出了一種基于相鄰編碼塊編碼深度和RMD代價的編碼塊尺寸快速決策算法，與HM14.0相比，其ΔBitrate增加了1.18%，平均編碼時間縮短了44.05%.

綜上所述，在控制編碼效率基本不變的條件下，HEVC編碼塊尺寸快速決策算法的計算復(fù)雜度還需進一步提升以適應(yīng)實時編碼的需求.本文提出了基于方向性紋理的HEVC編碼塊尺寸快速決策算法，定義了編碼塊水平、垂直、45°和135°這四個方向紋理復(fù)雜度的衡量指標，通過大量視頻序列的訓練選取最優(yōu)閾值，并對提案[14]中所提到的所有的視頻序列(除Nebuta和SteamLocomotive兩個視頻序列外)進行了測試.

1基于方向性紋理的HEVC編碼塊尺寸快速決策算法

1.1紋理復(fù)雜度函數(shù)的提出

文獻[10]指出，紋理豐富的編碼塊通常有更大的編碼深度，平坦的區(qū)域有較小的編碼深度.圖1為QP=32時，全幀內(nèi)模式配置下,原始HM10.0對BasketballDrive的最終劃分結(jié)果，可以看出其對紋理復(fù)雜的視頻區(qū)域會以更小的編碼塊進行編碼，對紋理簡單的視頻區(qū)域會以更大的編碼塊進行編碼.

圖1　當QP=32時，原始HM10.0對BasketballDrive的最終劃分結(jié)果Figure 1　Final CU partition given by HM-10.0 under all-intra-main test configuration with QP= 32 when applied to encode the first frame from the sequence BasketballDrive

在H.264中，文獻[15-16]提出了一種衡量編碼塊紋理復(fù)雜度的指標如下式：

(1)

(2)

1.2提出的HEVC編碼塊尺寸快速決策算法

GEC-LEC算法同時運用了Global算子和Local算子來決定編碼塊的最終大小，Global算子描述了編碼塊全局的變化情況，Local算子描述了編碼塊局部的復(fù)雜程度，將兩者進行結(jié)合，可以準確地描述編碼塊的紋理信息，但有較高的計算復(fù)雜度.本文將Global算子和Local算子相融合，提出了計算復(fù)雜度更低的基于編碼塊四個方向復(fù)雜度的衡量指標如式(3～6)所示，并將其只用于當前編碼塊來決定當前編碼塊的最終大小.

(4)

其中

(5)

其中

(6)

(7)

(8)

圖2　本文提出的算法流程圖Figure 2　Flowchart of the proposed algorithm

圖2為本文提出的編碼塊尺寸快速決策算法的流程圖.本文算法首先通過計算當前編碼塊的水平、垂直、45°和135°這四個方向的紋理復(fù)雜度，根據(jù)紋理復(fù)雜度可以對當前編碼塊做如下判定：

(9)

其中，ThrDepth為深度為Depth(取值為0，1，2，3)的編碼塊所選取的閾值，complexity為當前編碼塊的紋理復(fù)雜度.如果當前編碼塊紋理復(fù)雜度被判定為High，則其被認為是一個紋理復(fù)雜的編碼塊，被判定為復(fù)雜紋理的編碼塊將會以更大的編碼深度進行編碼，跳過當前編碼深度的率失真代價的計算，從而可以減少編碼的計算復(fù)雜度；如果當前編碼塊紋理復(fù)雜度被判定為Low，則當前編碼塊被認為是一個紋理簡單的編碼塊，被判定為簡單紋理的編碼塊將會以當前深度進行編碼，大于當前深度編碼塊的遞歸計算將會被終止，從而減少了編碼的計算復(fù)雜度.否則，通過計算率失真代價來決定當前編碼塊的最終劃分.

1.3閾值選擇分析

本文提出的算法性能很大程度上依賴于閾值的選取，選取最優(yōu)化的閾值是發(fā)揮本文算法優(yōu)勢相當關(guān)鍵的一步.如果閾值太小或者太大，編碼塊最終劃分結(jié)果與HM10.0相比，錯誤命中率都會偏高.文獻[8]指出，錯誤命中率與BD-Bitrate幾乎成線性關(guān)系，錯誤命中率越小，BD-Bitrate就會越小.

本文首先從ClassB-F中共選出7個視頻序列作為訓練樣本，計算了當QP=22，27，32，37時，7個視頻序列的平均錯誤命中率與閾值之間的關(guān)系曲線如圖3.平均錯誤命中率越低，則表明本文算法的編碼塊劃分結(jié)果與HM10.0的更為接近，進一步說明平均錯誤命中率最低時的閾值可以更精確的區(qū)分編碼塊的復(fù)雜程度，從而可以提早對編碼塊的大小進行跳過或終止的決策.

當QP=22，27，32，37時，本文選取7個視頻序列(Cactus,BasketballDrive,PartyScene,RaceHorses,BQSquare,FourPeople和SlideShow)的平均錯誤命中率最小時的閾值作為最優(yōu)閾值.當QP=22，27，32，37時, 本文最終選取的閾值ThrDepth如下式：

(10)

其中Depth為編碼塊的深度，取值為0，1，2，3.

圖3　平均錯誤命中率與閾值之間的關(guān)系曲線　Figure 3　Relationship between the average wrong hit rate and threshold

2測試結(jié)果及比較

本文算法是在HM10.0平臺上進行了算法改進的，算法的測試條件參考了提案[14]，測試的視頻序列包含了提案[14]中提到的Class A-F這六個序列.算法測試時，我們測試了視頻序列第一幀所用的編碼時間，對第一幀編碼10次求取該幀平均所用的編碼時間，節(jié)省的編碼時間ΔTS用下式去衡量：

(11)

本文算法的編碼效率是用BD-Bitrate和BD-PSNR來衡量的，它們的計算參考了提案[17].本文算法是在AI-Main配置下，在Intel Core i3-2120CPU @3.30GHz 5.0GB RAM Windows 7操作系統(tǒng)，VS2010的實驗環(huán)境中進行測試的，測試結(jié)果詳見表1.測試結(jié)果表明，與HM10.0相比，本文提出的算法可以減少45.3%的編碼時間，同時BD-Bitrate增加1.27%.本文算法也與GEC-LEC算法[12]進行了比較，編碼時間可節(jié)省3%，BD-Bitrate增加了0.5%，BD-PSNR減少了0.023 dB.由于本文中用來衡量紋理復(fù)雜度算子的計算復(fù)雜度更低，而且只需要計算當前編碼塊的紋理復(fù)雜度.因此，本文提出的算法在保持編碼效率幾乎不變的情況下，在編碼時間的節(jié)省上具有一定的優(yōu)勢.

表1　在全幀內(nèi)模式配置下，本文算法與HM10.0的算法性能比較

3結(jié)論

本文基于編碼塊四個方向的紋理復(fù)雜度提出了一種編碼塊尺寸快速決策算法.該算法計算了當前編碼塊四個方向的紋理復(fù)雜度，通過訓練選取最優(yōu)閾值，根據(jù)閾值決定當前編碼塊的最終大小.在QP=22，27，32，37時，本文選取所有訓練視頻序列的平均錯誤命中率最低時所對應(yīng)的閾值作為最優(yōu)閾值.實驗結(jié)果表明，與HM10.0相比較，本文提出的算法可以減少45.3%編碼時間，同時BD-Bitrate增加了1.27%，BD-PSNR減少了0.058 dB；與GEC-LEC算法相比，編碼時間可節(jié)省3%，BD-Bitrate增加了0.5%，BD-PSNR減少了0.023 dB.因此，本文提出的算法在保持編碼效率幾乎不變的情況下，在編碼時間的節(jié)省上具有一定的優(yōu)勢.

【參考文獻】

[1]SULLIVAN G J, OHM J R, HAN W J, et al. Overview of the high efficiency video coding standard[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2012, 22(12): 1649-1668.

[2]DE JESUS OCHOA DOMINGUEZ H, VERGARA VILLEGAS O O, CRUZ SANCHEZ V G, et al. The h.264 video coding standard[J]. IEEE Potentials,2014,33(2):32-38.

[3]LAINEMA J, BOSSEN F, HAN W J, et al. Intra coding of the hevc standard[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2012, 22(12): 1792-1801.

[4]KIM I K, MIN J, LEE T, et al . Block partitioning structure in the hevc standard[J]. IEEE Transactions on Circuits and Systems for Video Technology,2012,22(12):1697-1706.

[5]TIAN Guifen, GOTO S. Content adaptive prediction unit size decision algorithm for hevc intra coding[C]//29th Picture Coding Symposium (PCS). Krakow: IEEE,2012:405-408.

[6]NISHIKORI T, NAKAMURA T, YOSHITOME T, et al. A fast cu decision using image variance in hevc intra coding[C]//IEEE Symposium on Industrial Electronics and Applications (ISIEA). Kuching: IEEE,2013:52-56.

[7]KHAN M U K, SHAFIQUE M, HENKEL J. An adaptive complexity reduction scheme with fast prediction unit decision for hevc intra encoding[C]//20th IEEE International Conference on Image Processing (ICIP). Melbourne: IEEE, 2013: 1578-1582.

[8]KIM J H,CHOE Y, KIM Y G. Fast coding unit size decision algorithm for intra coding in hevc[C]//IEEE International Conference on Consumer Electronics. Vegas: IEEE, 2013: 637-638.

[9]ZHANG Hao, MA Zhan. Early termination schemes for fast intra mode decision in high efficiency video coding[C]//IEEE International Symposium on Circuits and Systems. Beijing: IEEE,2013:45-48.

[10]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.

[11]SHEN Liquan, LIU Zhi, ZHANG Xinpeng, et al. An effective cu size decision method for hevc encoders[J]. IEEE Transactions on Multimedia, 2013, 15(2): 465-470.

[12]MIN B, CHEUNG R C C. A fast cu size decision algorithm for the hevc intra encoder[J]. IEEE Transactions on Circuits and Systems for Video Technology,2015,25(5):892-896.

[13]LIM K, LEE J, KIM S, et al. Fast pu skip and split termination algorithm for hevc intra prediction[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2015, 25(8): 1335-1346.

[14]BOSSEN F. Common test conditions and software reference configurations[C]//Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11 12th Meeting. Geneva: ITU, 2013: 1-4.

[15]LIM K, KIM K, LEE J, et al. Fast block size and mode decision algorithm for intra prediction in h.264/avc[J]. IEEE Transactions on Consumer Electronics, 2012, 58(2): 654-660.

[16]HUANG Y H, OU T S, CHEN H H, et al. Fast decision of block size, prediction mode, and intra block for h.264 intra prediction[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2010, 20(8): 1122-1132.

[17]PATEUX S, JUNG J. An excel add-in for computing bjontegaard metric and its volution[C]//ITU-Telecommunications Standardization Sector STUDY GROUP 16 Question 6 Video Coding Experts Group (VCEG) 31st Meeting. Marrakech: ITU, 2007: 1-5.

Fast coding unit size decision algorithms based on texture complexity for high efficiency video coding

ZHANG Congcong, LI Ziyin, YING Lingkai，GUO Shengting

(College of Optical and Electronic Technology, China Jiliang University, Hangzhou 310018, China)

Abstract:To reduce the computational complexity of the high efficiency video coding (HEVC) intra coding algorithm, a fast coding unit size decision algorithm based on four directional texture complexity for the HEVC was proposed. We proposed the four directional texture complexity metrics and selected the best thresholds in different quantization parameters (QP) by training video sequences and portioned the current coding unit according to the best thresholds. Experimental results showed that the encoding time reduced by 45.3% on average, with 1.27% BD-Bitrate increasing and 0.058 dB BD-PSNR decreasing under the all-intra-main test configuration compared with the reference software HM10.0. The encoding time reduced by 3% on average, with 0.5% BD-Bitrate increasing and 0.023 dB BD-PSNR decreasing under the all-intra-main test configuration compared with the GEC-LEC algorithm.

Key words:high efficiency video coding；texture complexity；coding unit size

【文章編號】1004-1540(2015)01-0086-05

DOI:10.3969/j.issn.1004-1540.2016.01.016

【收稿日期】2015-09-23《中國計量學院學報》網(wǎng)址：http://zgjl.cbpt.cnki.net

【作者簡介】張聰聰(1990- )，男，甘肅省慶陽人，碩士研究生，主要研究方向為高效視頻編碼技術(shù).E-mail:zccyman@163.com

【中圖分類號】TN919.18

【文獻標志碼】A

通信聯(lián)系人：李子印，男，副教授.E-mail:liziyin@cjlu.edu.cn