雷海軍，危 雄，楊 張，袁梅冷

(1. 深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院，廣東 深圳 51 8060；2. 廣東省普及型高性能計(jì)算機(jī)重點(diǎn)實(shí)驗(yàn)室，廣東 深圳 518060；3. 深圳市服務(wù)計(jì)算與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，廣東 深圳 518 060；4. 深圳職業(yè)技術(shù)學(xué)院，廣東 深圳 51806 0)

一種快速HEVC幀內(nèi)預(yù)測(cè)模式?jīng)Q策算法

雷海軍1,2,3，危 雄1,2,3，楊 張4，袁梅冷4

(1. 深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院，廣東 深圳 51 8060；2. 廣東省普及型高性能計(jì)算機(jī)重點(diǎn)實(shí)驗(yàn)室，廣東 深圳 518060；3. 深圳市服務(wù)計(jì)算與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，廣東 深圳 518 060；4. 深圳職業(yè)技術(shù)學(xué)院，廣東 深圳 51806 0)

高性能視頻編碼(HEVC)標(biāo)準(zhǔn)是視頻編碼聯(lián)合小組提出的新的視頻編碼標(biāo)準(zhǔn)。針對(duì)HEVC幀內(nèi)預(yù)測(cè)模式?jīng)Q策的高計(jì)算復(fù)雜度問題，提出一種基于邊緣方向強(qiáng)度檢測(cè)的快速幀內(nèi)預(yù)測(cè)模式?jīng)Q策算法。將35種幀內(nèi)預(yù)測(cè)模式根據(jù)5個(gè)基本方向分為5個(gè)預(yù)測(cè)候選模式集合，每個(gè)集合中有11種預(yù)測(cè)模式。分別計(jì)算預(yù)測(cè)單元(PU)的5個(gè)方向的方向強(qiáng)度，以及每個(gè)方向所占比例，選擇比例最大的方向所對(duì)應(yīng)的候選模式集合為該P(yáng)U塊的候選預(yù)測(cè)模式，有效減少幀內(nèi)預(yù)測(cè)的計(jì)算復(fù)雜度。實(shí)驗(yàn)結(jié)果證明，與HM8.0相比，該算法能夠以保證視頻質(zhì)量為前提，在高效率條件和低復(fù)雜度條件下平均節(jié)省15%和18%的編碼時(shí)間。

視頻編碼；高性能視頻編碼標(biāo)準(zhǔn)；幀內(nèi)預(yù)測(cè)；預(yù)測(cè)單元；模式?jīng)Q策；邊緣方向檢測(cè)

1 概述

高性能視頻編碼(High Efficiency Video Coding, HEVC)標(biāo)準(zhǔn)于2010年4月在德國德累斯頓召開的JCT-VC第一次會(huì)議上提出。該標(biāo)準(zhǔn)主要面向高性能高清視頻應(yīng)用，提供從QVGA(320×240像素分辨率)到1 080p甚至超高清(7 680× 4 320)分辨率的視頻應(yīng)用。HEVC的核心目標(biāo)在于：相比于H.264視頻編碼標(biāo)準(zhǔn)，大幅提高視頻壓縮效率，即在相同視頻質(zhì)量前提下，視頻流碼率減少50%[1]。

相比H.264標(biāo)準(zhǔn)，HEVC依然采用混合編碼框架[2]，但在很多方面做出了改進(jìn)來提高壓縮效率。具有代表性的技術(shù)方案有：基于大尺寸的四叉樹分割結(jié)構(gòu)[3]和殘差編碼結(jié)構(gòu)，多角度幀內(nèi)預(yù)測(cè)[4]，運(yùn)動(dòng)估計(jì)融合技術(shù)等。其中，多角度幀內(nèi)預(yù)測(cè)，HEVC的預(yù)測(cè)方向數(shù)從H.264標(biāo)準(zhǔn)中的9種增加到33種[4]，很大程度上提高了幀內(nèi)預(yù)測(cè)的精度，但同時(shí)也帶來了很高計(jì)算復(fù)雜度的負(fù)面效果。

針對(duì)H.264幀內(nèi)預(yù)測(cè)的高計(jì)算復(fù)雜度，已有眾多學(xué)者提出了優(yōu)化改進(jìn)的方法。文獻(xiàn)[5]提出了一種基于二維直方圖的快速幀內(nèi)預(yù)測(cè)算法，在幀內(nèi)預(yù)測(cè)之前對(duì)宏塊預(yù)判，減少預(yù)測(cè)算法復(fù)雜度，提高視頻壓縮編碼效率。文獻(xiàn)[6]利用預(yù)測(cè)圖中相鄰模式及次優(yōu)模式與最優(yōu)模式的相關(guān)性特點(diǎn)，對(duì)幀內(nèi)預(yù)測(cè)模式進(jìn)行選擇，提出了一種基于Intra4×4的快速模式選擇算法，減少了幀內(nèi)預(yù)測(cè)的候選模式數(shù)。文獻(xiàn)[7]通過對(duì)前4×4塊幀內(nèi)預(yù)測(cè)方向度量，利用相鄰塊和相鄰方向預(yù)測(cè)模式的相關(guān)性進(jìn)行幀內(nèi)模式預(yù)測(cè)。文獻(xiàn)[8]利用幀內(nèi)預(yù)測(cè)模式與視頻圖像塊紋理方向的相關(guān)性提出了一種快速幀內(nèi)預(yù)測(cè)算法，使用Sobel算子計(jì)算出視頻圖像中紋理最強(qiáng)的方向，在紋理最強(qiáng)方向和與該方向最接近的2個(gè)方向以及DC方向模式搜索最優(yōu)的預(yù)測(cè)方向，將H.264中的9種幀內(nèi)預(yù)測(cè)方向減少為4種預(yù)測(cè)方向，從而大量節(jié)省計(jì)算時(shí)間。

同樣，針對(duì)HEVC幀內(nèi)預(yù)測(cè)的高計(jì)算復(fù)雜度問題，文獻(xiàn)[9]采用反向預(yù)測(cè)順序進(jìn)行色度分量預(yù)測(cè)生成深度圖和候選預(yù)測(cè)模式集合，再進(jìn)行亮度分量幀內(nèi)預(yù)測(cè)，以降低HEVC幀內(nèi)預(yù)測(cè)計(jì)算復(fù)雜度。文獻(xiàn)[10]利用HEVC四叉樹編碼的特點(diǎn)，縮短預(yù)測(cè)像素與參考像素之間的距離，提高幀內(nèi)預(yù)測(cè)精度。這種短距離幀內(nèi)預(yù)測(cè)方向能大幅提高細(xì)節(jié)豐富的圖像的幀內(nèi)預(yù)測(cè)精度，從而提高編碼效率。

本文使用一種新的方法，對(duì)幀內(nèi)預(yù)測(cè)模式進(jìn)行優(yōu)化，減少參與率失真優(yōu)化(Rate Distortion Optimization, RDO)計(jì)算的幀內(nèi)預(yù)測(cè)模式，將HEVC中35種幀內(nèi)預(yù)測(cè)模式減少為11種預(yù)測(cè)模式來實(shí)現(xiàn)快速幀內(nèi)預(yù)測(cè)模式?jīng)Q策過程，從而降低幀內(nèi)編碼時(shí)間，提高編碼效率。

2 HEVC幀內(nèi)預(yù)測(cè)

HEVC標(biāo)準(zhǔn)定義了3種單元塊：編碼單元(Coding Unit, CU)，預(yù)測(cè)單元(Prediction U nit, P U)和變換單元(Transform Unit, TU)[11]。編碼單元是HEVC視頻編碼的基本單元，類似于H.264編碼中的宏塊，CU塊是正文形，并且CU塊的最大尺寸為64×64(即Largest Coding Unit, LCU)，最小尺寸為8×8(即Smallest C oding U nit, S CU)。對(duì)于每個(gè)CU塊，HEVC使用PU塊實(shí)現(xiàn)該CU塊的預(yù)測(cè)過程。PU塊支持多種分割類型，對(duì)于幀內(nèi)預(yù)測(cè)，PU塊的分割類型只能為2N× 2 N和N×N這2種類型。TU塊可支持對(duì)4×4至32×32基本單元的編碼變換和量化。圖1所示為CU與PU的分割關(guān)系。

圖1 C U、PU分割關(guān)系

HEVC軟件測(cè)試模型HM8.0[12]中的幀內(nèi)預(yù)測(cè)共有33種角度預(yù)測(cè)模式，如圖2所示，另外還包括2種非方向性預(yù)測(cè)模式：直流預(yù)測(cè)模式(Intra_DC)和平面預(yù)測(cè)模式(Intra_ planar)。PU塊的大小共有5種，分別為64×64，32×32，16×16，8×8，4×4，這5種尺寸PU塊所對(duì)應(yīng)的幀內(nèi)預(yù)測(cè)模式數(shù)分別為4，35，35，35，18。當(dāng)前PU塊的幀內(nèi)預(yù)測(cè)值是從相鄰PU塊的參考像素矩陣中通過線性內(nèi)插得到。該預(yù)測(cè)過程中，每個(gè)像素預(yù)測(cè)值需要大量的算術(shù)計(jì)算，增加了預(yù)測(cè)過程的計(jì)算復(fù)雜度。

圖2 幀內(nèi)預(yù)測(cè)模式方向

在HEVC軟件測(cè)試模型HM8.0中，首先根據(jù)當(dāng)前PU塊的大小得到當(dāng)前PU塊的可用幀內(nèi)預(yù)測(cè)模式，再通過對(duì)預(yù)測(cè)殘差哈達(dá)曼變換計(jì)算出各個(gè)模式下的殘差絕對(duì)值總和(Sum of Ab solute Transformed D ifference, SA TD)，選出SATD最小的前n種預(yù)測(cè)模式為率失真優(yōu)化(Rate Distortion Optimization, RDO)候選預(yù)測(cè)模式。幀內(nèi)預(yù)測(cè)過程中為保證預(yù)測(cè)的準(zhǔn)確性，最可能預(yù)測(cè)模式(Most Pr obable Mode, MPM)始終包括在RDO候選預(yù)測(cè)模式集合中。最后對(duì)各RDO候選預(yù)測(cè)模式進(jìn)行率失真優(yōu)化計(jì)算，得到幀內(nèi)最優(yōu)預(yù)測(cè)模式。

3 快速幀內(nèi)預(yù)測(cè)模式?jīng)Q策算法

3.1 P U塊邊界方向檢測(cè)

在HEVC的幀內(nèi)預(yù)測(cè)模式中，有33種方向性預(yù)測(cè)模式，若某個(gè)PU塊選中某一預(yù)測(cè)模式則說明該P(yáng)U塊的紋理方向與該預(yù)測(cè)模式方向具有相似性。因此，可以首先計(jì)算出各PU塊的紋理方向，對(duì)幀內(nèi)預(yù)測(cè)模式進(jìn)行快速搜索。如圖3所示，對(duì)4×4的PU塊，可以劃分為4個(gè)2×2的子塊。

圖3 用于邊緣方向檢測(cè)的PU塊4分割

每個(gè)子塊可以用其中包含的4個(gè)像素的平均值表示。各子塊的計(jì)算過程如下。

4×4的PU塊的各像素值為：p(m, n), m, n=0,1,2,3；則被分割后的各子塊的灰度值為：

對(duì)于該4×4的PU塊，若塊內(nèi)無明顯邊界，則(S00+S11)/2 與(S01+S10)/2的差將會(huì)很??；若塊內(nèi)存在一個(gè)明顯的水平邊界，則(S00+S01)/2與(S10+S11)/2將有明顯的差值，垂直方向類似；若塊內(nèi)存在一個(gè)明顯的45°對(duì)角線邊界，則S00與(S01+ S10+S11)/3或S11與(S00+S01+S10)/3有明顯差值，135°對(duì)角線邊界類似。

本文將PU塊劃分5種邊界方向，分別是無明顯邊界、水平邊界、垂直邊界、45°對(duì)角線邊界、135°對(duì)角線邊界、如圖4所示。

圖4 P U塊的5種邊界方向

這5種邊界方向的強(qiáng)度值Eθ(θ∈{ND,0,π/4,π/2,3π/4})的計(jì)算如表1所示，則PU塊的邊界方向即為Eθ最大值所對(duì)應(yīng)的邊界方向。

表1 邊界方向強(qiáng)度計(jì)算

以上為4×4的亮度塊的邊界方向檢測(cè)過程。對(duì)于8×8，16×16，32×32的PU塊，將其分割成4×4的PU單元，再進(jìn)行邊界方向檢測(cè)。如圖5所示，將16×16的PU塊分割成16個(gè)4×4的PU塊，計(jì)算這16個(gè)4×4的PU塊的邊界方向，則16×16的PU塊的邊界方向由16個(gè)4×4的PU塊邊界方向中占比例最大的方向決定。由于尺寸較大的PU塊被檢測(cè)為無邊界方向的可能性更大，為避免將有邊界方向誤判為無邊界方向，特別設(shè)定只有在無邊界方向的4×4塊所占比例超過75%時(shí)，當(dāng)前PU塊才被檢測(cè)為無邊界方向。

圖5 16×16 PU塊分割成4×4 PU單元的方向檢測(cè)

3.2 幀內(nèi)預(yù)測(cè)模式的劃分

由于幀內(nèi)預(yù)測(cè)模式與視頻圖像塊內(nèi)的邊緣方向是密切相關(guān)的，因此可根據(jù)上述5種邊緣方向?qū)?3種幀內(nèi)預(yù)測(cè)模式劃分為5類。

(1)無邊界方向預(yù)測(cè)模式：END={0,1,3,4,5,6,7,8,9}；

(2)水平方向預(yù)測(cè)模式：EH={1,7,8,15,16,28,29,30,31}；

(3)垂直方向預(yù)測(cè)模式：EV={0,4,5,11,12,20,21,22,23}；

(4)45°對(duì)角線方向預(yù)測(cè)模式：E45°={5,6,9,13,17,24,25, 32, 33}；

(5)135°對(duì)角線方向預(yù)測(cè)模式：E135°={5,6,9,13,17,24,25, 32, 33}。

為保證幀內(nèi)預(yù)測(cè)的準(zhǔn)確性，Intra_DC和Intra_planar預(yù)測(cè)模式將加入到上述5個(gè)預(yù)測(cè)模式集合中，每個(gè)PU單元的可用預(yù)測(cè)模式數(shù)從33種減少為11種。若檢測(cè)到當(dāng)前PU塊的邊緣方向無明顯邊緣方向，則當(dāng)前PU的可用幀內(nèi)預(yù)測(cè)模式為集合END，對(duì)于其他方向的選擇過程與此類似。由于每個(gè)PU塊的可用幀內(nèi)預(yù)測(cè)模式數(shù)減少，本文所用方法中將4×4和8×8大小PU塊的候選幀內(nèi)預(yù)測(cè)數(shù)設(shè)定為5。

4 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證所提出方法的效率，本文以HEVC的軟件測(cè)試模型HM8.0為參照進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)平臺(tái)為Inter(R)酷睿雙核CPU，主頻2.83 GHz，內(nèi)存3 GB，操作系統(tǒng)Windows XP。實(shí)驗(yàn)所用的序列的測(cè)試條件來自文獻(xiàn)[13]，量化值分別為22、27、32、37。實(shí)驗(yàn)結(jié)果如表2所示。比較編碼效率的參數(shù)指標(biāo)有PSNR增量(ΔPSNR)、碼率增量(ΔBitrate)和編碼時(shí)間增量(Δtime)，分別用以下公式進(jìn)行計(jì)算：

表2 實(shí)驗(yàn)結(jié)果對(duì)比

從表2中可以看出，在高效率條件下本文提出的算法的碼率與HM8.0相比有明顯提升，視頻編碼質(zhì)量?jī)H提高了0.14 dB，但是編碼時(shí)間節(jié)省了約15%。，在低復(fù)雜度條件下本文算法的碼率與HM8.0相比有明顯提升，視頻編碼質(zhì)量?jī)H提高了0.12 dB，但是編碼時(shí)間節(jié)省了約18%。

5 結(jié)束語

本文通過檢測(cè)各PU塊的邊緣方向強(qiáng)度，將幀內(nèi)預(yù)測(cè)模式數(shù)從35種減少為11種，簡(jiǎn)化了對(duì)不必要的預(yù)測(cè)模式的率失真優(yōu)化(RDO)計(jì)算，從而降低視頻編碼的計(jì)算復(fù)雜度，節(jié)省編碼時(shí)間，提高編碼效率。實(shí)驗(yàn)結(jié)果證明本文所提出的快速幀內(nèi)預(yù)測(cè)模式?jīng)Q策算法是正確和有效的。但是所提出的算法僅優(yōu)化了HEVC幀內(nèi)預(yù)測(cè)的粗選模式?jīng)Q策過程，并未考慮幀內(nèi)預(yù)測(cè)模式的率失真優(yōu)化計(jì)算過程，有待進(jìn)一步研究以提高幀內(nèi)預(yù)測(cè)的編碼速度。

[1] Sullivan G J, Ohm J, Han W J, et al. Overvie w of the High Efficiency Video Coding(HEVC) Standard[J]. IEEE Transactions on Circuits and S ystems for V ideo Technology, 2012, 22(12): 1649-1668.

[2] Wiegand T, Ohm J R, Sullivan G J, et al. Special Section on the Joint Call for Proposals o n High Ef ficiency V ideo Coding(HEVC) Standardization[J]. IEE E T ransactions on Circuits and Sys tems for V ideo Technology, 201 0, 20(12): 1661-1666.

[3] Kim I K, Min J, Lee T, et al. Block Partitioning S tructure in the HEVC S tandard[J]. IEEE T ransactions on Circuits and Systems for Video Technology, 2012, 22(12): 1697-1706.

[4] Lainema J, Bossen F, Ha n W J, et al. Intra Coding of the HEVC S tandard[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2012, 22(12): 1792-1801.

[5] 謝 晶, 賈克斌. 一種基于二維直方圖的H.264/AVC快速幀內(nèi)預(yù)測(cè)判決算法[J]. 電子與信息學(xué)報(bào), 2005, 27(7): 1053-1057.

[6] 王維哲, 周 兵, 張行進(jìn). H.264 編碼中的幀內(nèi)預(yù)測(cè)模式選擇算法[J]. 計(jì)算機(jī)工程, 2008, 34(2): 226-228, 231.

[7] 王啟文, 黃東軍. H.26 4中4×4塊的快速幀內(nèi)預(yù)測(cè)算法[J].計(jì)算機(jī)工程, 2010, 36(2): 217-219.

[8] Pan F, Lin X, Rahardja S, et al. Fast Mode Decision Algorithm for Intra Predict ion in H.264/AVC V ideo Coding[J]. IEEE Transactions on Circuits and Systems for V ideo Technology, 2005, 15(7): 813-822.

[9] Chen Weijing, Su Jia, Li Bin, et al. Reversed Intra Prediction Based on Chroma Extraction In HEVC[C]//Proc. of International Symposium on In telligent Signal Processing and Communications Systems. [S. l.]: IEEE Press, 2011: 1-5.

[10] Cao Xiaoran, Lai Changcai, Wang Yunfei, et al. Short Distance Intra Coding Scheme for HEVC[C]//Proc. of Picture Coding Symposium. [S. l.]: IEEE Press, 2012: 501-504.

[11] Han W J, Min J, Lee T, et al. Improve d Video Compression Efficiency Through Flexible Unit Representation and Corresponding Extension of Coding Tools[J]. IEEE Transactions on Circuits and Systems for V ideo Technology, 2010, 20(12): 1709-1720.

[12] JCT-VC. The Reference Software of HEVC[EB/OL]. (2012-11-10). https://hevc.hhi.fraunhofer.de/svn/svn_HEVCSoftware/ tags/HM-8.0.

[13] Bossen F. Common Test Conditions and S oftware Reference Configurations[Z]. 2011.

編輯 顧逸斐

A Fast Mode Decision Algorithm for Intra Prediction in HEVC

LEI Hai-jun1,2,3, WEI Xiong1,2,3, YANG Zhang4, YUAN Mei-leng4

(1. College of Computer Science & Software Engineering, Shenzhen University, Shenzhen 518060, China; 2. Key Laboratory of Affordable High Performance Computer in Guangdong Province, Shenzhen 518060, China; 3. Key Laboratory of Service Computing and Application at Shenzhen, Shenzhen 518060, China; 4. Shenzhen Polytechnic, Shenzhen 518060, China)

High Efficiency Video Coding(HEVC) is a kind of new standard of video coding developed by the Joint Collaborative Team on Video Coding(JCT-VC). For the problem of high computational complexity of intra prediction in HEVC, a fast intra prediction alg orithm based on edge direction detection is pro posed. The proposed method divides 35 intra prediction mo des into 5 sets o f candidate modes according to 5 basic directions, and each set contains 11 intra prediction modes. The edge direction strength of Prediction Unit(PU) in 5 directions are calculated. The proportion of each direction is calcul ated and the candidate modes are selected to set corresponding edge direction with the lar gest proportion as best ca ndidate modes for PU to reduce computational complexity effectively. Experimental results show that the proposed method saves encoding time of 15% and 18% on average compared with HM8.0 in high efficiency and low complexity.

video coding; High Efficiency Video Coding(HEVC) standard; intra prediction; Prediction Unit(PU); mode decision; edge direction detection

10.3969/j.issn.1000-3428.2014.05.056

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

雷海軍(1968－)，男，副教授，主研方向：圖像處理，網(wǎng)絡(luò)多媒體技術(shù)；危 雄，碩士研究生；楊 張，碩士；袁梅冷，副教授。

2013-01-28

2013-04-01E-mail：yangzhang120@163.com

1000-3428(2014)05-0270-04

A

TP301.6

·開發(fā)研究與工程應(yīng)用·