一種HEVC幀內(nèi)預(yù)測(cè)快速算法

張新晨,肖秀秀,趙 婭,黎 偉,江 昊,肖進(jìn)勝

(1.華中師范大學(xué)物理科學(xué)與技術(shù)學(xué)院,武漢430079;2.武漢大學(xué)電子信息學(xué)院,武漢430072)

一種HEVC幀內(nèi)預(yù)測(cè)快速算法

張新晨1,肖秀秀1,趙 婭1,黎 偉2,江 昊2,肖進(jìn)勝2

(1.華中師范大學(xué)物理科學(xué)與技術(shù)學(xué)院,武漢430079;2.武漢大學(xué)電子信息學(xué)院,武漢430072)

HEVC作為新一代的視頻編碼標(biāo)準(zhǔn),比現(xiàn)有H.264標(biāo)準(zhǔn)的壓縮效率提高近一倍,但其存在復(fù)雜度較高的問(wèn)題。為此,針對(duì)HEVC中幀內(nèi)預(yù)測(cè)最耗時(shí)的模塊,即編碼單元塊劃分模塊和幀內(nèi)預(yù)測(cè)模式選擇模塊,提出一種適合HEVC幀內(nèi)預(yù)測(cè)的快速算法。該算法將率失真(RD)代價(jià)作為閾值參數(shù),利用候選模式集中預(yù)測(cè)模式被選中概率快速遞減的規(guī)律,基于RD代價(jià)進(jìn)行幀內(nèi)預(yù)測(cè)塊劃分和幀內(nèi)預(yù)測(cè)模式選擇。實(shí)驗(yàn)結(jié)果表明,該算法在相同編碼質(zhì)量條件下可減少59%的HM10.0幀內(nèi)預(yù)測(cè)模塊復(fù)雜度,相應(yīng)比特率的增加幅度小于1.34%。

視頻編碼;HEVC標(biāo)準(zhǔn);幀內(nèi)預(yù)測(cè);塊劃分;模式選擇

1 概述

2013年1月,JCT-VC新一代視頻編碼標(biāo)準(zhǔn)HEVC正式發(fā)布,作為現(xiàn)行標(biāo)準(zhǔn)H.264/AVC的替換標(biāo)準(zhǔn),該標(biāo)準(zhǔn)應(yīng)用支持視頻分辨率從320×240像素至7 680×4 320像素,與H.264/AVC的高檔次編碼配置(High Profile)的編碼性能相比,能提高近一倍的編碼壓縮效率[1-2]。

但HEVC在獲得更高性能的同時(shí),也無(wú)可避免地增加了計(jì)算復(fù)雜度,在幀內(nèi)編碼過(guò)程中,采用了四叉樹遞歸編碼單元結(jié)構(gòu)以及采用枚舉法遍歷35種幀內(nèi)預(yù)測(cè)模式找出最佳模式[3],其計(jì)算復(fù)雜度成倍的增加導(dǎo)致HEVC不能有效地應(yīng)用于實(shí)時(shí)通信應(yīng)用。因此,在保持HEVC視頻主客觀質(zhì)量的前提下,有效地降低計(jì)算復(fù)雜度是普及HEVC視頻編碼標(biāo)準(zhǔn)和將其商業(yè)化應(yīng)用的關(guān)鍵所在[4-5]。

本文基于率失真(Rate-distortion,RD)代價(jià)函數(shù)提出一種提前終止四叉樹的幀內(nèi)預(yù)測(cè)塊劃分方法,并利用圖像相關(guān)性選取候選預(yù)測(cè)模式集進(jìn)一步降低預(yù)測(cè)模式選擇的計(jì)算復(fù)雜度。

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

HEVC參考模型(HM10.0)[6]采用樹形結(jié)構(gòu)和遞歸模式進(jìn)行編碼單元(Coding Unit,CU)塊的劃分,對(duì)于幀內(nèi)預(yù)測(cè)模式來(lái)說(shuō),CU塊的深度優(yōu)先遍歷遞歸從樹根最大編碼單元(Largest Coding Unit, LCU)(64×64)開始,依次出發(fā)搜索它的每個(gè)鄰接點(diǎn)(4個(gè)32×32的子CU塊),若鄰接點(diǎn)未曾訪問(wèn)過(guò),則以它為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷,一直遞歸至4×4大小的塊,直至四叉樹中所有節(jié)點(diǎn)均被訪問(wèn)為止,四叉樹深度優(yōu)先搜索結(jié)束[7-8]。

參考模型深度優(yōu)先遍歷四叉樹的每個(gè)節(jié)點(diǎn),計(jì)算出四叉樹上每個(gè)節(jié)點(diǎn)的權(quán)重,即當(dāng)前層次編碼單元CU的率失真代價(jià)RDCost。如果當(dāng)前編碼單元CU所劃分的4個(gè)子CU的RDCost之和大于當(dāng)前編碼單元CU自身的RDCost,則當(dāng)前CU在編碼的時(shí)候不需要做劃分;否則,當(dāng)前CU需要?jiǎng)澐?。另?將當(dāng)前編碼單元CU的RDCost賦值為兩者之間的小者。通過(guò)這個(gè)算法,計(jì)算出使整個(gè) 64×64的RDCost最小的劃分路徑,用于編碼。在計(jì)算RDCost的過(guò)程中,主要采用以下3個(gè)步驟[9]獲得每個(gè)CU單元的最佳幀內(nèi)預(yù)測(cè)模式:

步驟1 對(duì)所有34種或17種角度的預(yù)測(cè)模式,使用基于HAD(Hadamard transform Absolute Difference)的代價(jià)函數(shù)計(jì)算代價(jià),然后按代價(jià)值從小到大的順序排列預(yù)測(cè)模式,選出前若干種代價(jià)最小的模式構(gòu)成一組候選模式。候選模式集中的候選模式的數(shù)量如表1所示。

表1 角度幀內(nèi)預(yù)測(cè)方向模式和候選模式數(shù)量

步驟2 從相鄰編碼單元中推導(dǎo)出最有可能模式(MPM),并將其加入候選模式集中,若候選集中已經(jīng)有此模式,則不重復(fù)加入候選模式集中;否則,將MPM加入候選模式集的末尾。

步驟3 從這些候選模式中,使用基于 SSE (Sum of Square Error)的代價(jià)函數(shù)計(jì)算代價(jià),選出有最小RDCost的模式作為最佳預(yù)測(cè)模式。

3 幀內(nèi)預(yù)測(cè)的優(yōu)化算法

幀內(nèi)預(yù)測(cè)模式計(jì)算運(yùn)算量巨大。幀內(nèi)模式快速選擇算法的研究作為提高編碼效率的研究重點(diǎn)之一。通過(guò)上述HEVC中較為耗時(shí)模塊的分析,降低幀內(nèi)預(yù)測(cè)算法復(fù)雜度可以從以下2個(gè)方面進(jìn)行研究:(1)采用提前終止的思想,預(yù)判塊幀內(nèi)編碼塊類型,節(jié)省塊劃分時(shí)間;(2)通過(guò)一些低復(fù)雜度的方法有效地將候選集中不太可能的模式過(guò)濾掉[7,10-12],從而減少計(jì)算的預(yù)測(cè)模式數(shù)量。

3.1 基于率失真代價(jià)的幀內(nèi)預(yù)測(cè)塊劃分快速算法

對(duì)于當(dāng)前CU塊的最佳RD代價(jià),需要搜尋在每一個(gè)深度CU的每一個(gè)可能的模式。但是可以發(fā)現(xiàn),如果當(dāng)前CU的深度是逼近最優(yōu)的,停止分裂當(dāng)前CU只會(huì)導(dǎo)致一個(gè)微不足道的損失[13],但是速度卻會(huì)有一個(gè)巨大的提升[14]。

圖1是RaceHorses序列在標(biāo)準(zhǔn)HM代碼下的CU分割結(jié)果。在第一個(gè)64×64的LCU塊中,當(dāng)?shù)谝粋€(gè)32×32的塊計(jì)算出的代價(jià)逼近最優(yōu)模式時(shí),可以停止繼續(xù)分割CU,大幅提高編碼速率;在第4個(gè)32×32的塊計(jì)算出的代價(jià)很大時(shí),可以直接確定該塊需要繼續(xù)分割成4個(gè)16×16的子塊,無(wú)需在該32×32的塊中做量化等工作。要確定提前終止的條件,本文使用率失真代價(jià)RDCost。

圖1 RaceHorses序列的CU分割結(jié)果

通過(guò)設(shè)定一個(gè)閾值,當(dāng)RDCost小于該閾值時(shí),說(shuō)明預(yù)測(cè)效果很好,可以滿足編碼需要,則不需要進(jìn)一步的判斷以及下一層的遞歸劃分;否則,需要做進(jìn)一步的判斷和下一層的遞歸劃分。下面將詳細(xì)介紹閾值的選定流程。

其中,E表示錯(cuò)誤率;T是閾值。

因此,滿足dE/dT=0以及d2E/dT2＞0的閾值應(yīng)該是最佳的閾值,也可以視為2條曲線的交點(diǎn)。

因而,對(duì)于每個(gè)2N×2N單元,如果ΔC2N大于離線訓(xùn)練的閾值,則被認(rèn)為是應(yīng)該被分割成N×N的塊。否則,2N×2N預(yù)測(cè)單元大小對(duì)編碼這種2N× 2N單元來(lái)說(shuō)是合適的。按照這一辦法,在訓(xùn)練集中的每個(gè)序列和量化參數(shù)(Quantization Parameter, QP),只需要一次編碼迭代就能得到一整套閾值,復(fù)雜度降低的同時(shí),能得到接近圖1的最佳結(jié)果。

本文選擇5種不同分辨率的測(cè)試序列進(jìn)行閾值訓(xùn)練,如表2所示。對(duì)于每一個(gè)序列,QP值分別為22,27,32和37。在獲得所有序列的閾值組合后,計(jì)算5個(gè)序列的平均閾值,最終采用的閾值如圖2所示,有4條曲線對(duì)應(yīng)于4種單元尺寸在不同QP下的閾值。

表2 測(cè)試序列

圖2 算法訓(xùn)練后采用的閾值

以RaceHorses序列為例,在使用上述算法流程改進(jìn)后的HM代碼下,該視頻序列的CU分割結(jié)果如圖3所示。

圖3 RaceHorses序列的CU分割結(jié)果

3.2 幀內(nèi)預(yù)測(cè)模式快速選擇

本文提出的幀內(nèi)預(yù)測(cè)模式選擇快速算法具體步驟如下:

(1)從所有角度模式中,使用基于HAD代價(jià)的代價(jià)函數(shù),并按代價(jià)值從小到大,選出若干個(gè)模式構(gòu)成一組候選模式。

(2)從相鄰編碼單元中推導(dǎo)出最有可能模式MPM,判斷該MPM是否是候選模式集中代價(jià)最小的模式,如果是,直接選為最佳預(yù)測(cè)模式,否則,將其加入候選模式集中,并跳至第(3)步。

(3)從這些候選模式中,選出最小RD代價(jià)的模式作為最佳預(yù)測(cè)模式。

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

本文算法在HM10.0上實(shí)現(xiàn),配置文件選用配置encoder_intra_main.cfg,測(cè)試過(guò)程中I幀的周期設(shè)置為1,所有編碼幀均為幀內(nèi)編碼。

表3的實(shí)驗(yàn)結(jié)果表明,本文算法在幀內(nèi)預(yù)測(cè)編碼平均節(jié)省58.97%的編碼時(shí)間,在PSNR幾乎沒(méi)有下降的同時(shí)編碼碼率增加了1.34%,這個(gè)性能損失值是可以接受的。在不同的分辨率或者序列特征下,可以實(shí)現(xiàn)降低幾乎相同的復(fù)雜度,表明本文所提出的算法在實(shí)時(shí)HEVC編碼應(yīng)用的潛力較大。

表3 塊劃分和模式選擇結(jié)合快速算法的性能比較

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

本文在分析HEVC中幀內(nèi)預(yù)測(cè)算法和現(xiàn)有快速算法的基礎(chǔ)上,提出一種提前終止四叉樹的遞歸處理方法,提前終止的判斷參數(shù)選用率失真代價(jià),再利用圖像的相關(guān)性,對(duì)HEVC幀內(nèi)預(yù)測(cè)候選模式集中根據(jù)概率快速遞減的規(guī)律,減少了候選模式數(shù)目。最后,針對(duì)HEVC幀內(nèi)編碼在HM10.0參考模型中實(shí)現(xiàn)了快速處理算法,降低了原算法的計(jì)算復(fù)雜度和幀內(nèi)編碼時(shí)間。實(shí)驗(yàn)結(jié)果表明,與參考模型中的算法相比,本文算法在不降低編碼質(zhì)量的情況下進(jìn)行幀內(nèi)編碼時(shí)縮減了59%的編碼時(shí)間,考慮到編碼過(guò)程中其他模塊的耗時(shí),幀內(nèi)預(yù)測(cè)處理的速度實(shí)際上有了成倍的提高。因此,本文提出的針對(duì)HEVC幀內(nèi)預(yù)測(cè)的快速算法具有較高的實(shí)用和研究參考價(jià)值。

[1] Bross B,Hhi F.High Efficiency Video Coding(HEVC) Text Specification Draft 10[C]//Proc.of the ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11 12th Meeting.Geneva,Switzerland:[s.n.],2013:14-23.

[2] 劉梅峰,陸 玲.新一代視頻編碼標(biāo)準(zhǔn)HEVC變換方法的研究[J].電視技術(shù),2012,36(1):1-5.

[3] Lainema J,Ugur K.Angular Intra Prediction in High Efficiency Video Coding(HEVC)[C]//Proc.of the 13th IEEE International Workshop on Multimedia Signal Processing.Hangzhou,China:[s.n.]:2011:1-5.

[4] Saygili G,Gurler C G,Tekalp A M.Evaluation of Asymmetric Stereo Video Coding and Rate Scaling for Adaptive 3D Video Streaming[J].IEEE Transactions on Broadcasting,2011,57(2):593-601.

[5] Bossen F,Drugeon V.Video Coding Using a Simplified Block Structure and Advanced Coding Techniques[J]. IEEE Transactions on Circuits and Systems for Video Technology,2010,20(12):1667-1675.

[6] Bross B,McCann K.JCT-VC AHG Report:HEVC Draft and Test Model Editing[C]//Proc.of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11 12th Meeting. Geneva,Switzerland:[s.n.],2013:1085-1090.

[7] Sun Heming,Zhou Dajiang,Goto S.A Low-complexity HEVC Intra Prediction Algorithm Based on Level and Mode Filtering[C]//Proc.of 2012 IEEE International Conferenceon Multimedia and Expo.Melbourne, Australia:IEEE Press,2012:1085-1090.

[8] Saxena A,Fernandes F C.On Secondary Transforms for Intra Prediction Residual[C]//Proc.of IEEE International Conference on Acoustics,Speech and Signal Processing.Kyoto,Japan:IEEE Press,2012:1201-1204.

[9] Bross B,Han W,Ohm J,et al.WD5:High Efficiency Video Coding(HEVC)Text Specification Draft 9[C]// Proc.of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/ WG11 11th Meeting.Shanghai,China:2012.

[10] Yeo Chuohuo,Tan Yihhan.Mode-Dependent Transforms for Coding Directional Intra Prediction Residuals[J]. IEEE Transactions on Circuits and Systems for Video Technology,2012,22(4):545-554.

[11] Huang Yihsin,Ou Taosheng,Chen H H.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.

[12] 成益龍,滕國(guó)偉,石旭利,等.一種快速HEVC幀內(nèi)預(yù)測(cè)算法[J].電視技術(shù),2012,36(21):4-7.

[13] Lim K,Kim S.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.

[14] Yeo C,Tan Y H.Low-complexity Mode-dependent KLT for Block-based Intra Coding[C]//Proc.of the 18th IEEE International Conference on Image Processing. Brussels,Belgium:IEEE Press,2011:3685-3688.

編輯 金胡考

A Fast Intra-frame Prediction Algorithm for HEVC

ZHANG Xin-chen1,XIAO Xiu-xiu1,ZHAO Ya1,LI Wei2,JIANG Hao2,XIAO Jin-sheng2
(1.College of Physics Science and Technology,Central China Normal University,Wuhan 430079,China;
2.School of Electronic and Information,Wuhan University,Wuhan 430072,China)

As a new generation video coding standard,HEVC has more compression efficiency than the existing video coding H.264 standard,but it has higher complexity.Aiming at this problem,after brief analysis of the intra prediction algorithm,a fast algorithm based on Rate-distortion(RD)cost of intra prediction block dividing and the intra-frame prediction mode selection fast algorithm is proposed to reduce the HEVC intra-frame prediction complexity.This algorithm takes full use of the advantages of rate distortion cost and the probability of the prediction mode is selected in the candidate pattern quick descending law.Experimental results show that complexity reduction from HM10.0 is over 59% and stable for various sequences,which makes the proposed algorithm suitable for real-time applications.The corresponding bit rate increase is lower than 1.34%.

video coding;HEVC standard;intra-frame prediction;block partitioning;mode decision

1000-3428(2014)10-0017-03

A

TP18

10.3969/j.issn.1000-3428.2014.10.004

國(guó)家自然科學(xué)基金資助項(xiàng)目(61371126);教育部-中國(guó)移動(dòng)科研基金資助項(xiàng)目(MCM20122041)。

張新晨(1977-),男,副教授、博士,主研方向:視頻編碼,多媒體通信;肖秀秀,碩士研究生;趙 婭,本科生;黎 偉,碩士研究生;江 昊,教授、博士;肖進(jìn)勝,副教授、博士。

2013-09-03

2013-11-12E-mail:zxc9501@163.com

中文引用格式:張新晨,肖秀秀,趙 婭,等.一種HEVC幀內(nèi)預(yù)測(cè)快速算法[J].計(jì)算機(jī)工程,2014,40(10):17-19,24.

英文引用格式:Zhang Xinchen,Xiao Xiuxiu,Zhao Ya,et al.A Fast Intra-frame Prediction Algorithm for HEVC[J]. Computer Engineering,2014,40(10):17-19,24.