基于改進梯度算子的快速視頻編碼算法

藍 敏

(長沙民政職業(yè)技術(shù)學(xué)院,湖南 長沙 410004)

基于改進梯度算子的快速視頻編碼算法

藍 敏

(長沙民政職業(yè)技術(shù)學(xué)院,湖南 長沙 410004)

針對H.264的高復(fù)雜性，提出基于改進梯度算子的快速幀內(nèi)幀間模式選擇算法。借助運算量極小的改進梯度算子得出塊的梯度方向，以此來指導(dǎo)幀內(nèi)模式的選擇和幀間模式的劃分。這種算法使得模式選擇跳出了全遍歷，只鎖定在部分模式中，從而大大減少了時間復(fù)雜度，而且碼流不會明顯增加，視頻質(zhì)量也較佳。

視頻編碼；幀間預(yù)測；幀內(nèi)預(yù)測；模式選擇；基于紋理

隨著H.264/MPEG-4 part 10被聯(lián)合視頻組（Joint Video Team(JVT)，formed by ITU-T VCEG and ISO/IEC MPEG）作為新一代編解碼標準發(fā)布，視頻編解碼效率得到了很大的提高，但是復(fù)雜度也提高了不少[1][2]。特別是率失真優(yōu)化（The rate distortion optimization(RDO)）技術(shù)的應(yīng)用，使得編碼質(zhì)量提高并且碼率也得到了下降，但是它卻是以遍歷幀內(nèi)幀間模式為代價的：幀內(nèi)預(yù)測中亮度有9種模式，色度有4種；幀間預(yù)測中每個宏塊可以分割成7種宏塊模式和4種子宏塊模式。采用各種方式編碼后編碼效果和碼率差別較大，因此，每個宏塊的模式選擇是編碼過程中非常關(guān)鍵和耗時的步驟。

眾多快速算法應(yīng)用而生。快速幀內(nèi)預(yù)測模式選擇算法[3]，利用Sobel算子生成邊緣方向直方圖，找到相關(guān)性最強的方向模式，并使用其進行預(yù)測編碼，可大大減少不相關(guān)的模式計算，從而減小時間復(fù)雜度，但是要進行三角函數(shù)運算和直方圖統(tǒng)計，比較耗時。Jia-Ching Wang等人提出了一個簡單的邊緣檢測算法[4]，用五個空間域濾波器處理每個下采樣后的宏塊，通過比較濾波后的值來判斷宏塊紋理的走向。它被MPEG-7做為特征描述符采納，達到了更好的對比效果。An-Chao Tsai提出了一個更簡便的算子[5]，他并不考慮所有的像素，僅用一部分像素得出每個方向的梯度值，用以檢測塊的邊緣方向。

在幀間算法里，Inchoon Choi采用SKIP模式提前中止策略，這樣可以省掉后面很多模式的判決；針對在幀間編碼時還要遍歷intra4×4、intra16×16這兩種幀內(nèi)預(yù)測模式的情況，他通過比較宏塊時間和空間相關(guān)性大小的方法來有選擇地進行幀內(nèi)模式預(yù)測[6]。但他僅限于優(yōu)先SKIP模式和排除不必要的幀內(nèi)預(yù)測模式，除此之外的幀間模式未給予考慮。Andy C.Yu[7]提出利用當前塊的DCT系數(shù)計算該塊的能量，從而得到塊的紋理復(fù)雜度，進行快速劃分模式的選擇。該技術(shù)的一個不足之處是依靠AC系數(shù)總能量來判斷宏塊細節(jié)高低，這樣必須對宏塊進行額外的DCT變換，而DCT變換計算量較大。

針對這些弊端，本文提出了基于改進梯度算法的幀內(nèi)幀間算法。首先用改進梯度算子快速得出塊的梯度方向，之后以梯度方向為依據(jù)求出最佳幀內(nèi)預(yù)測模式。再利用梯度方向按照從大塊到小塊的順序去劃分幀間模式，即先計算skip模式和inter16×16模式，再有選擇地計算較小模式，從而快速鎖定最佳幀間模式。

1.改進梯度算子

在文獻[5]中，圖象梯度如圖所示，每個方向取出四個標黑了的像素的梯度。（見圖1-1）

梯度算子是：G(x)=-1/2*P(x-1)+1/2*P(x+1)

G(x)代表像素x的梯度強度，當它接近或者等于0時，意味它有個方向。

圖1-1 基于梯度算子的四個方向

梯度算子在四個方向都能得到很好的效果，但是仔細研究發(fā)現(xiàn)，它實際上只取了部分像素計算其梯度，并不夠精確。對它的一種改造如下[8]：

預(yù)測4×4塊的紋理方向：

圖1-2 下采樣4×4亮度塊

以平均值為依據(jù)計算出紋理的走向 (挑出以下最小值的就是這個4×4塊的紋理走向)。

可以看出，式1-1反映了四個方向上像素塊的緊密程度， （x＝0、45、90、或 135）越小，紋理的走向越接近這個方向。

2.基于改進梯度算子的快速幀內(nèi)算法

由上一節(jié)可以得到每個4×4塊的梯度方向，而幀內(nèi)預(yù)測模式和梯度方向有極大的相關(guān)性。9種幀內(nèi)預(yù)測模式中，除了DC模式是沒有方向的，其余8種代表了8個不同方向。于是選取梯度方向及其相鄰的兩個方向的模式，再加上DC模式，總共只要計算4種模式，這比起JM要遍歷9種模式，節(jié)省了50%以上的計算復(fù)雜度。

同理，可以求出16×16塊的模式方向，只不過下采樣時，涉及的像素點更多。采樣塊還是以上圖1-1為例，但a～p不是16個像素，而是16個4×4小塊的平均值。由于16×16宏塊只有4個方向的模式選擇，所以只要計算梯度方向的模式和DC模式，同樣也能節(jié)約不少的計算復(fù)雜度。

3.基于改進梯度算子的快速幀間算法

盡管H.264中編碼模式很多,但通過對不同復(fù)雜度視頻序列的仿真,發(fā)現(xiàn)7種編碼模式所占比例并不均衡，skip模式和inter16×16模式占據(jù)了很大的比重。這是因為在自然視頻序列中存在著一些空域上均勻或者時域上平穩(wěn)的區(qū)域,如圖像的背景區(qū)域等。在這種類型的區(qū)域中,通常以比較大的塊尺寸進行編碼比如inter16×16或者skip模式。本文首先考慮這兩種模式，并計算它們的率失真代價值。

接著，開始考慮其他模式，按照大塊到小塊的順序?qū)Ξ斍皦K計算率失真值，符合終止條件時，即可不做之后的遍歷。根據(jù)仿真實驗可知，只要小塊模式的率失真值比大塊的大，遍歷即可終止；否則，繼續(xù)搜索計算更小的模式。比inter16×16小的有inter16×8和inter8×16，比 inter8×8 小的也有 inter8×4、inter4×8 和inter4×4，到底應(yīng)該采用哪一種呢？這個時候，用梯度方向來決定小塊模式的選擇。

小塊模式劃分的準則是：

1.分的原則：梯度方向是水平的塊，小塊模式采用水平劃分；梯度方向是垂直的塊，小塊模式采用垂直劃分。如：16×16的4個8×8小塊中，只要有3個及3個以上的塊是水平的，那么16×16塊就分為兩個16×8小塊；只要有3個及3個以上是垂直的，那么16×16塊就分為兩個8×16小塊。也就是說在計算完skip模式和inter16×16模式的率失真值后，我們只要計算inter16×8或inter8×16模式二者之一就可以了。

2.合的原則：相鄰小塊的梯度方向如果相同，那么這兩個小塊就可以合并。如：8×8小塊中有4個4×4的小塊，它們的梯度方向如果相同，就可以合并為8×4小塊或者4×8小塊。

有了這兩個準則，在計算完skip和inter16×16模式后，可以清楚地知道接下來該采用哪種較小的模式。如果這種較小模式的代價值比之前的更小，那么再考慮選擇更小的模式；如果這種較小模式的代價值比之前的更大，那么遍歷終止。

4.實驗結(jié)果及對比

實驗在JM12上進行。表1是JM編碼器參數(shù)配置，表2是實驗數(shù)據(jù)。

表2

5.結(jié)束語

在JM12平臺中，幀內(nèi)模式選擇和幀間模式選擇是分開進行的。如果要用幀內(nèi)模式進行編碼（如I幀），那么不必考慮幀間模式，我們可用改進梯度算子方便地得到幀內(nèi)編碼模式；如果要用幀間模式進行編碼(如P幀)，JM12平臺仍然會去計算幀內(nèi)模式intra4×4、intra16×16(如在實時視頻的場景發(fā)生變化時，后一幀是無法利用前一幀進行編碼的，此時最好是采取幀內(nèi)模式編碼)。既然幀間模式選擇也要用到幀內(nèi)模式，那么改進梯度算子就有了很大的通用性。

[1]ITU-T Recommendation H.264.Advanced Video Coding for Generic Audiovisual Services,H.264 Standard,2005.

[2]Wiegand,T.,Sullivan,G.J.,Bjontegaard,G.,Luthra,A.Overview of the H.264/AVC video coding standard.IEEE Trans.Circuits Syst.Video Technol.,vol.13,no.7,Jul.2003.560-576.

[3]Feng Pan,Xiao Lin,Rahardja,S.,Lim,K.P.,Li,Z.G.,Dajun Wu,Si Wu.Fast mode decision algorithm for intraprediction in H.264/AVC videocoding.IEEE Trans.Circuits Syst.Video Technol.,vol.15,no.7,Jul.2005.813-822.

[4]Jia-Ching Wang,Jhing-Fa Wang,Jar-Ferr Yang,Jang-Ting Chen.A fast mode decision algorithm and its VLSI design for H.264/AVC intra prediction.IEEE Trans.Circuits and Syst.Video Technol.,vol.17,no.10,Oct.2007.1414-1422

[5]An-Chao Tsai,Anand Paul,Jia-Ching Wang,Jhing-Fa Wang.Intensity Gradient Technique for Efficient Intra-Prediction in H.264/AVC.IEEE Trans.Circuits Syst.Video Technol.,vol.18,no.5,May 2008.694-698.

[6]Choi,I.,Lee,J.,Jeon,B.Fast Coding Mode Selection with Rate-Distortion Optimization for MPEG-4 Part-10 AVC/H.264.IEEE Trans.Circuits Syst.Video Technol.,vol.16,no.12,Dec.2006.1557-1561.

[7]Yu,A.C.Efficient Block-size Selection Algorithm for Inter-frame Coding in H.264/MPEG-4 AVC Acoustics IEEE International Conference on Acoustics,Speech and Signal Processing,vol.3,no.17-21,May 2004.169-172.

[8]Tsai,A.C.,J.F.Wang,J.F.Yang&W.G.Lin.Effective Subblockbased and Pixel-based Fast Direction Detections for H.264 Intra Prediction[J].IEEE Trans.Circuits Syst.Video Technol.,2008,18(7):975-982.

[9]畢厚杰.新一代視頻壓縮編碼標準-H.264/AVC[M].北京:人民郵電出版社，2003.

[10]余兆明，查日勇，黃磊，周海嬌.圖象編碼標準H.264技術(shù)[M].人民郵電出版社,2005.

TP301

A

1671-5136（2011） 01-0120-03

2010-12-13

藍敏(1982-)，男，湖南長沙人，長沙民政職業(yè)技術(shù)學(xué)院軟件學(xué)院助教、碩士。研究方向：計算機圖形圖像。