AVS2幀內(nèi)預(yù)測模式快速選擇算法

鄭　成，王國中，范　濤，趙海武

(上海大學 通信與信息工程學院，上海 200444)

?

AVS2幀內(nèi)預(yù)測模式快速選擇算法

鄭成，王國中，范濤，趙海武

(上海大學 通信與信息工程學院，上海 200444)

AVS2是我國新一代具有自主知識產(chǎn)權(quán)的視頻編碼標準，相比于同代國際標準HEVC在壓縮效率上基本相當，而比上一代國標AVS在壓縮效率上提升了一倍左右。然而隨著壓縮效率的大幅度提升，其編碼復雜度也急劇增加，例如復雜的塊劃分，更多的預(yù)測模式等。為提升編碼速度，使其適用于實時應(yīng)用，提出一種快速幀內(nèi)模式選擇的算法，一方面通過對各幀內(nèi)模式的利用率分析，避免了RMD(Rough Mode Decision)野蠻遍歷各種模式；另一方面，通過先驗知識構(gòu)成終止RDO(Rate-Distortion Optimized)條件，且根據(jù)紋理估計進一步優(yōu)化其終止條件，可有效提高RDO的效率。實驗結(jié)果表明，在圖像質(zhì)量幾乎不下降的前提下，優(yōu)化后的RMD模式命中率高達98%，全I幀編碼BD-Rate大約增加0.96%，而編碼時間節(jié)省了約34%，大幅提升了AVS2幀內(nèi)編碼的速度。

AVS2；幀內(nèi)預(yù)測；模式選擇；紋理方向

AVS2是新一代音視頻編碼的國家標準，其主要包括3個部分，即音頻、視頻以及系統(tǒng)。AVS2-P2即《信息技術(shù)高效多媒體編碼》的視頻部分(以下簡稱為AVS2)于2014年7月已經(jīng)制定完成，其相比于上代編碼標準在幀結(jié)構(gòu)、編碼結(jié)構(gòu)、幀內(nèi)幀間預(yù)測技術(shù)、變換結(jié)構(gòu)、熵編碼以及環(huán)路濾波等都做了較大的改進。然而，大量新技術(shù)的引入導致算法復雜度也急劇上升[1-2]。為達到高清乃至超高清視頻的實時編碼，對編碼算法進行優(yōu)化是極其有必要的。AVS2對于幀的種類劃分基本沿用上一代標準，即I幀，B幀及P幀，并加入F幀(雙前向預(yù)測)，其中I幀作為GOP(Group of Pictures)的第一幀，在碼流中所占的比特數(shù)也是比較多的，同時它也是其他幀的參考幀，所以I幀對編碼效率以及圖像質(zhì)量影響較大。研究如何快而好地進行幀內(nèi)編碼對于整個編碼框架的優(yōu)化有著重要的意義。

1　AVS2幀內(nèi)預(yù)測

1.1CU，PU，TU的劃分

在編碼結(jié)構(gòu)上，AVS2采用了四叉樹結(jié)構(gòu)如圖1所示，其中64×64的塊被稱為LCU(Largest Coding Unit)，深度為0，往下遞歸劃分為4個相同的32×32的CU，深度為1，如此遞歸直到8×8。在每一個CU結(jié)構(gòu)中又可以有PU(Prediction Unit)與TU(Transform Unit)，顧名思義PU是預(yù)測時所用的單元，每個PU由尺寸、預(yù)測模式等信息構(gòu)成；TU是變換量化時所用的單元，每個TU由尺寸、殘差系數(shù)等信息構(gòu)成。

圖1　CU四叉樹劃分示意

PU和TU是同一層次上的結(jié)構(gòu)單元，它們都是在CU下劃分的。圖2給出了AVS2在幀內(nèi)預(yù)測中PU的4種劃分方式，依次為2N×2N，N×N，N×nN，nN×N，該技術(shù)被稱為短距離預(yù)測技術(shù)，能夠有效適應(yīng)某些獨特的條紋狀塊。AVS2中幀內(nèi)TU的劃分相較于HEVC的TU是比較簡捷的，沒有進一步對TU進行四叉樹劃分，而是和PU一樣大小，這樣做的原因是：PU中的像素值在空域中一般是符合一定的紋理規(guī)律，所以變換后在頻域上的分布也是相對集中的，如果對TU進行四叉樹劃分，性能幾乎不會有提升，反而會耗費大量時間。因此HEVC的諸多快速算法中大多數(shù)采用了Fast RDT(快速TU尺寸選擇)的方式提前終止TU的劃分。

圖2　AVS2幀內(nèi)PU劃分模式

1.2AVS2幀內(nèi)預(yù)測過程

與HEVC不同，AVS2采用自底而上的編碼順序，類似于四叉樹的后續(xù)遍歷。首先是CU層面的遞歸，確定某一個CU后對其進行PU的劃分。AVS2中只有8×8大小的CU才會進行N×N的PU劃分，其他大小的CU一律只做2N×2N的PU劃分。PU劃分確定后會對其進行模式選擇，大概分為4步：1)獲得周邊塊的模式；2)進行33種模式進行遍歷；3)計算33種模式的SAD代價進行模式粗選，選出9種候選模式構(gòu)成集合SC；4)對SC中的模式做RDO選出當前PU最佳預(yù)測模式，如圖3所示。

圖3　AVS2幀內(nèi)預(yù)測過程

從以上分析可以看出，AVS2的幀內(nèi)預(yù)測過程是比較復雜的，計算量主要集中在以下3個方面：1)遍歷LCU劃分CU的各種可能；2)RMD；3)RDO。本文主要針對后兩者進行分析。

2　快速幀內(nèi)模式選擇算法

HEVC中的幀內(nèi)快速算法對幀內(nèi)預(yù)測復雜度的減少主要集中在1.2節(jié)中總結(jié)的3點。文獻[3]提出了一種基于梯度方向和直方圖的CU遞歸提前終止的算法，平均節(jié)省時間20%左右。文獻[4]將CU的劃分看成一個統(tǒng)計估值的問題，利用貝葉斯決策來判斷CU是否劃分。本文在RDM和RDO兩方面對AVS2的幀內(nèi)模式選擇進行優(yōu)化。

2.1基于pRMS模型優(yōu)化的快速RMD

文獻[5]提出了一種pRMS(Progressive Rough Mode Search)模型以提升RMD的速度，其核心思想是定義兩種模式間的距離

(1)

式中：i和j為模式的標號，并且規(guī)定DC、Planar模式和其他角度模式中d為無窮大。pRMS模型主要對角度模式進行“下采樣”，采樣的步長為d=4，這樣就選出了特征模式集合SS。遍歷SS選出最佳的特征模式后，再計算與特征模式距離d=2的模式的代價，依次遞歸直至距特征模式d<4的模式全部計算完代價后截止，選出候選模式集合SC。

本文算法對AVS2中的RMD優(yōu)化也同樣是先特征后局部的思路，如圖4所示。但是，上述pRMS有兩方面點不足：一方面，選取特征模式步長為固定值4，沒有考慮到模式的利用率；另一方面，沒有考慮到不同尺寸PU的紋理特性導致的角度模式利用率。

圖4　特征模式12，17，21被選中

針對以上兩點，本文分別做出相應(yīng)的改進優(yōu)化。首先，經(jīng)實驗統(tǒng)計出AVS2幀內(nèi)預(yù)測模式的利用率，如圖5。先不考慮模式0～2特殊模式，從餅狀圖中可以很容易發(fā)現(xiàn)，模式12(垂直模式)和模式24(水平模式)這兩個模式本身以及其附近的模式利用率較高，根據(jù)這個特點，設(shè)計出如下特征模式集合

SS={5,9,12,17,21,24}

(2)

圖5　AVS2幀內(nèi)模式利用率

可以看出該集合中模式距離d不是一個固定值，而是在3～5直接浮動，靠近模式12和模式24，特征模式距離d相對較小。這樣特征模式就比原pRMS中固定步長選出的特征模式有了更明顯的針對性，突出了特征的含義。

其次，對于pRMS中不同尺寸的PU采用同樣方法，本文做了如下優(yōu)化。上面提到不同模式的利用率是不一樣的，那么，可以考慮不同尺寸PU的模式利用率也是各不相同。小尺寸的PU紋理方向復雜多變，大尺寸的PU平坦順滑，所以大尺寸的PU對于角度模式的利用率遠低于小尺寸的PU。實驗結(jié)果也很好地證實了這一推論。本文算法規(guī)定：32×32及以上尺寸的PU為大尺寸PU，其余為小尺寸PU。表1給出了不同尺寸PU對角度模式的利用率。

表1不同尺寸PU對角度模式利用率%

尺寸模式0～2模式12模式24模式25其他大尺寸39.349.4620.436.9823.80小尺寸31.649.4613.904.8440.16

據(jù)此，本文算法對于大尺寸的PU只選取模式0～2、模式12、模式24以及模式25，無須進行復雜的模式選擇。對于小尺寸的PU則進行上述的基于pRMS優(yōu)化的算法進行候選模式選擇。

經(jīng)實驗，表2與表3分別給出了優(yōu)化前后的命中率對比。命中率由式(3)給出

(3)

式中：Nm0,Nm1分別是候選模式集合SC中前兩種模式選中的數(shù)量；Nall指所做RMD次數(shù)的總數(shù)。

表2本文算法在RMD中的命中率

序列QPDepthd01234BasketballPass2294.44%94.56%99.33%99.63%99.33%3794.40%94.72%99.32%99.50%98.55%Video1720p2299.77%99.27%99.51%98.94%96.41%37100%99.26%99.36%98.20%94.28%平均值97.39%97.15%96.95%99.38%99.07%97.14%

表3文獻[5]中pRMS在RMD中命中率

序列QPDepthd01234BasketballPass2266.8%76.4%84.9%99.7%99.6%3769.8%82.9%85.8%99.6%98.55%Video1720p2289.7%87.9%90.2%98.4%99.5%3790.0%88.1%89.7%99.6%99.8%平均值89.84%79.08%83.83%87.65%99.33%99.36%

對比兩表中的數(shù)據(jù)可以看出，本文算法在RMD中命中率在各種分辨率和塊尺寸上分布均勻，平均命中率達到了97.9%，標準差僅為2.1%，優(yōu)于pRMS的89.8%和9.8%。

另一方面，經(jīng)實驗證明優(yōu)化后的RMD在全I幀配置下編碼時間節(jié)省約為15%且對編碼效率幾乎沒有影響。

2.2基于紋理估計的RDO提前終止

2.1節(jié)描述了在RMD中，根據(jù)塊大小分別選用不同的方法降低了原始RMD的復雜度，提升了速度。本節(jié)通過提前終止RDO以進一步降低原始RDO的復雜度。RDO是幀內(nèi)預(yù)測中最為耗時的模塊，因為它要對每一個TU進行變換、量化、熵編碼，所以RDO的提前終止在快速幀內(nèi)預(yù)測算法中是較為關(guān)鍵的一環(huán)。本文算法的思路是構(gòu)建一個終止條件模式集合ST和已遍歷模式集合SD，當這兩個集合滿足式(4)時終止RDO

SD∩ST=ST

(4)

首先論述集合ST的構(gòu)成。文獻[6]已經(jīng)證明候選模式集合SC中的前兩個模式成為最終的模式有很高的可能性，故而將選模式集合SC前兩種模式加入ST。其次，由于DC、平面以及雙線性模式的平均命中率高達32%，所以也加入到ST中。最后，實驗表明，MPM的命中率在50%以上，所以也將MPM中兩種模式m0和m1加入ST，此時ST中模式數(shù)量為3～7種

ST={m0,m1,DC,Planar,Bilinear,MPM}

(5)

對比RMD后有6種或9種候選模式，ST中的模式數(shù)量還是較多的，尤其對于32×32以上的大塊，在RDO上幾乎沒有性能的提升。故而本文提出一種簡易的方法估計當前PU的紋理方向，據(jù)此減少ST中的模式。下面給出簡易估計PU塊紋理的方法。

首先計算當前PU塊在水平、45°以及垂直3個方向上的變化，如圖6所示。

圖6　AVS2幀內(nèi)模式利用率

式(6)以水平方向為例計算出水平方向的變化

(6)

(7)

式中：m為經(jīng)驗值，本文取30。式(7)反映了PU塊的起伏程度，如果滿足則選用DC、Planar模式的可能性很小。

進一步，如果dX,dX-Y,dY滿足

dY>dX-Y>dX

(8)

水平方向上的變化最小，由于模式12是垂直預(yù)測模式，故可以將ST中小于模式12的模式去掉。反之，可以將ST中大于模式24的模式去掉。

其次，初始化SD為

(9)

遍歷選模式集合SC中的模式mi，如果mi是SD中任意模式(除特殊模式)的附近模式，就將mi加入到SD中直至SD和ST滿足式(4)，此時SD中的模式即為需要做RDO的模式，這里定義附近模式為與特征模式距離d<Δd的模式。算法流程如圖7所示。

圖7　RDO提前終止流程

需要說明的是，選用附近模式的原因是考慮到2.1節(jié)中對大小塊采用了不同的處理方法，對于小塊采用較多的角度模式，而小塊的紋理雖然豐富多變，但是由于尺寸小，其紋理方向一般是單一的，所以mi與ST中的角度模式應(yīng)該集中在一個方向附近，而不是在不同方向上。本算法中Δd取2，其后的實驗結(jié)果印證了此條件對于復雜紋理的效率較高。

3　實驗結(jié)果

為驗證上述算法的性能，在AVS2參考代碼RD12.0版本中實現(xiàn)。實驗在全I幀的配置下，對不同尺寸、不同紋理復雜度以及不同QP情況下進行測試，以驗證算法在不同情況下的性能，測試條件如表4所示。

表4測試條件

項目內(nèi)容硬件平臺CPU:IntelCore(TM)i3-2310M內(nèi)存:6Gbyte1333MHz主板芯片組:IntelHM65芯片組操作系統(tǒng)Windows7旗艦版64位軟件平臺RD12.0軟件配置配置文件:encoder_ai.cfgQP:22,27,32,37測試序列尺寸1980×1080,1280×720,842×480,416×240

對編碼性能的分析采用了峰值信噪比差值(BDPSNR)和編碼比特率差值(BD-Rate)這兩個客觀指標來評判，它們是目前視頻編解碼中最為常用的客觀性能指標，其中BDPSNR用來衡量視頻序列中圖像失真的程度，BD-Rate可以用來衡量壓縮效率。除了上述兩個客觀指標，對編碼速度的提升用ΔT表示，定義為

(10)

式中：timepro表示本文提出算法耗時；timeref表示參考算法耗時。

另外，由于文獻[5]沒有給出BD-Rate數(shù)據(jù)，故用ΔR表示壓縮效率，定義為

(11)

式中：ratepro表示本文提出算法的比特率；rateref表示參考算法的比特率。

表5為本文算法相對于參考軟件的性能測試對比，其中每個序列的測試結(jié)果為QP取22，27，32，37時的均值。

表5本文算法測試結(jié)果

分辨率序列ΔT/%ΔR/%BD-Rate/%BDPSNR/dB1920×1080Kimono1-39.850.350.58-0.02BasketballDrive-30.440.540.17-0.01平均-35.150.450.38-0.021280×720City-34.310.500.95-0.07Grew-37.241.021.13-0.04平均-35.780.761.04-0.06832×480BQMall-33.320.721.14-0.07PartyScene-31.320.531.02-0.09平均-32.320.631.08-0.08416×240Racehorse-33.681.011.53-0.12BlowingBubbles-30.440.781.17-0.08平均-32.060.901.35-0.10

對表5數(shù)據(jù)進行分析可以發(fā)現(xiàn)，相比于參考軟件，ΔT約為-33.83%，BD-Rate約為0.96%，BDPSNR約為-0.06 dB。序列分辨率越大時，一方面提速越發(fā)明顯，另一方面，其BD-Rate和BDPSNR也越小?？梢哉f明，該算法在分辨率高的時候性能比較好。分辨率相同時，紋理復雜度越高，算法性能也越好。上述兩點都是由于算法對小塊處理更為細致，比如粗選模式的選用，RDO提前終止的條件都是符合小塊的紋理特性。文獻[7]是目前AVS2平臺上為數(shù)不多的幀內(nèi)快速算法之一，其算法相對于參考軟件，ΔT約為-16.5%，BD-Rate約為0.89%，BDPSNR約為-0.03 dB，具體數(shù)據(jù)如表6所示。

表6文獻[7]提出算法測試結(jié)果

分辨率ΔT/%BD-Rate/%BDPSNR/dB1920×1080-18.571.38-0.031280×720-17.851.18-0.03832×240-15.470.48-0.03416×240-14.240.54-0.02

對比兩組數(shù)據(jù)可以看出，本算法首先在提速上相比于文獻[7]算法有了進一步提升，ΔT大約是其2倍。其次，本文算法在編碼效率上相對于文獻[7]算法幾乎沒有變低，其中BD-Rate相當，BDPSNR有所偏低。進一步對比，本文算法在720p的序列中，速度上遠遠比文獻[7]算法快，并且在編碼效率上也不分上下；在1 080p的序列中，無論是速度提升、編碼效率均遠好于文獻[7]算法?？紤]到新一代編解碼標準是為解決高清、超高清視頻的傳輸與存儲的，所以本算法在高分辨率、紋理復雜的序列中表現(xiàn)出的優(yōu)良性能遠優(yōu)于文獻[7]算法。

4　結(jié)語

本文重點分析了AVS2幀內(nèi)預(yù)測過程，其相比于上一代視頻編碼標準在模式數(shù)量、模式選擇過程以及CU遞歸劃分上均復雜很多。針對這一問題，分析了各模式在不同大小塊中的利用率，并且利用此分布特性對不同尺寸選用不同的模式集合進行粗選，減少模式數(shù)量，并在此基礎(chǔ)上優(yōu)先考慮塊的紋理特性，設(shè)計了RDO的終止條件，節(jié)省了RDO的次數(shù)，提高了RDO的效率。

實驗結(jié)果表明，本文算法對于AVS2幀內(nèi)預(yù)測提速效果明顯，節(jié)約時間約33.83%，且編碼效率幾乎沒有下降，尤其在高分辨率、復雜紋理情況下算法性能優(yōu)異，為AVS2在高清、超高清視頻方面的應(yīng)用奠定了一定基礎(chǔ)。

不可忽略的是，HEVC中同類算法由于考慮到了CU劃分的提前終止，其幀內(nèi)預(yù)測過程相比于HM在ΔR約1.0%的情況下，提速達到了60%左右[5]，明顯好于當前AVS2的幀內(nèi)快速模式選擇算法。下一步，一方面可以借鑒CU劃分提前終止的思路，在AVS2中根據(jù)當前LCU的信息跳過一些底層CU的遍歷。另一方面，模式選擇中進行率失真優(yōu)化時總需要熵編碼，花費了大量的時間，如果能采用一定的方法估計出比特數(shù)，這樣能大幅度提升編碼的速度。

[1]黃鐵軍. AVS2標準及未來展望[J]. 電視技術(shù)，2014，38(22)：7-10.

[2]周蕓. AVS2視頻編碼關(guān)鍵技術(shù)[J]. 廣播電視信息，2015，9(2)：18-21.

[3]JIANG W，MA H，CHEN Y. Gradient based fast mode decision algorithm for intra prediction in HEVC[C]//2012 2nd International Conference on Consumer Electronics，Communications and Networks (CECNet). [S.l.]：IEEE，2012：1836-1840. DOI：10.1109/CECNet.2012.6201851.

[4]SHEN X，YU L， CHEN J. Fast coding unit size selection for HEVC based on Bayesian decision rule[C]//Picture Coding Symposium(PCS).California：IEEE，2012：453-456.DOI：10.1109/PCS.2012.6213252.

[5]ZHANG H，ZHAN M. Fast Intra mode decision for high efficiency video[J]. IEEE transactions on circuits and systems for video technology，2014，24(4)：660-668.DOI：10.1109/TCSVT.2013.2290578.

[6]ZHAO L，ZHANG L，MA S，et al. Fast mode decision algorithm for intra prediction in HEVC[C]//IEEE VCIP.[S.l.]：IEEE，2011：1-4.

[7]趙超，趙海武，王國中，等.快速AVS2幀內(nèi)預(yù)測選擇算法[J].計算機應(yīng)用，2015，35(11)：3284-3287.

鄭成(1992— )，碩士生，主研視頻編碼標準、新媒體技術(shù)；

王國中(1962— )，博士生導師，主要研究方向為中國音視頻編解碼標準AVS、三網(wǎng)融合、基于AVS和DTMB的雙國標數(shù)字地面電視系統(tǒng)和3DTV等；

范濤(1983— )，博士生，主研視頻編碼標準、3DTV、新媒體技術(shù)、三網(wǎng)融合技術(shù)等；

趙海武(1973— )，碩士生導師、博士，主要研究方向為數(shù)字視頻編解碼技術(shù)、轉(zhuǎn)碼技術(shù)等。

責任編輯：時雯

Fast intra prediction mode decision algorithm for AVS2

ZHENG Cheng，WANG Guozhong，F(xiàn)AN Tao，ZHAO Haiwu

(SchoolofCommunicationandInformationEngineering，ShanghaiUniversity，Shanghai200444，China)

AVS2 is a new generation of video coding standard with independent intellectual property rights. Compared with the international standards HEVC， it is roughly equal on compression efficiency. Compared to AVS1，AVS2′s compression efficiency is improved twice. Along with the increases in compression efficiency， its complexity has increased dramatically， such as Complex block partition， more prediction mode and so on. To increase encoding speed， a fast intra mode decision algorithm is proposed in the paper. On the one hand， through the analysis of the utilization of intra mode， proposed algorithm can avoid the traverse of various modes in the RMD. On the other hand， the termination condition of RDO (Rate-Distortion Optimized)，based on prior knowledge and texture estimation， has effectively improved the speed of RDO. Experimental results have show that，on the premise of almost no decline in quality of the image， AVS2 intra-frame coding time is greatly reduced.

AVS2； intra prediction； mode decision； texture direction

TN919.81

ADOI：10.16280/j.videoe.2016.10.001

國家“863”計劃項目(2015AA015903)

2016-03-27

文獻引用格式：鄭成，王國中，范濤，等.AVS2幀內(nèi)預(yù)測模式快速選擇算法[J].電視技術(shù)，2016，40(10)：1-5.

ZHENG C，WANG G Z，F(xiàn)AN T，et al.Fast intra prediction mode decision algorithm for AVS2[J].Video engineering，2016,40(10)：1-5.