熊承義,董朝南

(中南民族大學電子信息工程學院,武漢430074)

H.264是當前最具影響力的多媒體數據壓縮編碼國際標準之一.與之前編碼標準相比,H.264引入了許多新的壓縮技術,如多參考幀預測、可變塊運動補償及分數像素運動估計等.較之M PEG-2標準而言,H.264能夠在保證視頻圖像質量的前提下降低50%的比特率[1],但其算法的運算復雜度同時也大幅提高,尤其是運動估計部分占用80%的計算量[2].運動估計分為整數像素運動估計和分數像素運動估計.隨著整數像素運動估計快速算法的發(fā)展,整數像素搜索點數大大減少,使得分數像素運動估計的計算量占整個運動估計的比重不斷加大.因此,減少分數像素運動估計的運算量對于H.264標準尤為重要.

隨著對分數像素運動估計的不斷研究,人們提出了一些分數像素快速搜索算法.Chen等人[3]提出利用最佳整數點及其周圍相鄰8個整數點擬合分數像素誤差曲面模型,直接預測最佳分數像素點,但一般情況下整數像素搜索過程最后采用小菱形模型,只搜索最佳整數點及其上下左右4個點.W ang等人[4]提出通過鄰近像素值的預測,將分數像素點進行分組從而減少搜索點.Shen等人[5]提出利用整數像素點線性擬合分數像素點,并建立提前退出分數像素搜索的模型以減少運算量.Du等人[6]提出的PPHPS算法首先利用整數像素搜索的結果擬合誤差曲面,通過誤差曲面預測最佳分數像素點的位置,從而省略部分分數像素點的搜索.Chen等人[7]提出的CBFPS算法采用小菱形模型直接對1/4像素點進行搜索以減少運算量,但該方法只應用于分塊小于8×8的情況,對于較大的宏塊仍采用全搜索法.針對當前分數像素搜索方法存在的不足,本文通過分析分數像素搜索范圍誤差曲面的特點并結合CBFPS算法,提出一種分數像素運動估計的改進算法.該算法首先利用整數像素搜索的結果建立拋物線模型從而跳過不必要的分數像素搜索,對于8×8及以下分塊采用CBFPS算法,當分塊較大時,分析搜索中心點及其相鄰4個較近分數點的像素值,由分析的結果決定其它分數像素點是否搜索或部分搜索,從而減少分數像素搜索點數.該算法在保證搜索準確率的條件下顯著提高了計算速度.

1 H.264中分數像素搜索

在視頻編碼過程中,運動矢量位移的精度越高,幀間誤差越小,傳輸碼率越低,壓縮比越高.H.264在整數像素精度搜索完成后,進一步對亮度成分采用1/4像素精度,色度成分1/8像素精度進行階層式全搜索.搜索過程中采用拉格朗日函數作為運動搜索的代價判斷準則.拉格朗日函數如下:

式中:rmv為運動矢量;D(rmv)為當前rmv的塊匹配誤差;R(rmv)為對當前rmv編碼所需的比特數;λ為拉格

圖1 分數像素全搜索過程Fig.1 Illustration o f fu ll fractionalp ixel search

2 分數像素運動估計分析

由于搜索范圍較大,視頻內容較復雜,整數像素運動估計匹配誤差曲面一般不是單峰值的,因此在整數像素搜索過程中容易陷入局部最小點.而在分朗日因子.該函數綜合考慮了運動矢量rmv的匹配誤差和編碼開銷.

全搜索過程如下:假設A點為整數像素搜索后得到的最優(yōu)點,然后以該點為中心搜索其周圍的8個1/2像素點,比較各點對應的拉格朗日函數值,并找出具有最小函數值的1/2像素位置,假設為F點;完成1/2像素精度搜索之后,以最優(yōu)1/2像素點F為中心搜索其周圍8個1/4像素點,同理找出具有最小拉格朗日函數值的1/4像素點,整個搜索過程共計16個分數像素點,如圖1所示.分數像素位置的亮度和色度并不存在于參考圖像中,需利用鄰近已編碼點進行內插而得.因此,搜索的點數越多,運動估計的計算量就越大[8].

為提高編碼效率,H.264支持16×16、16×8、8×16、8×8、8×4、4×8 及4×4 等7 種不同大小分塊的預測,該7種分塊分別稱為模式1到模式7.當分塊模式為模式1到模式3時,采用全搜索算法,其它模式采用CBFPS算法,如圖2所示.該算法首先比較(0,0)和frac-p red-m v的拉格朗日函數值,值較小的作為分數像素搜索起始點,其中frac-p redm v由公式(2)得出.然后以起始點為中心進行小菱形方式搜索,直到搜索中心為最小值為止.式中,p red-m v為當前塊左、上及左上(或右上)方向塊運動矢量的中值;m v為當前塊整數像素的運動矢量.數像素搜索過程中,分數像素位置的亮度和色度值是利用鄰近已編碼點進行內插得到,所以與整數像素相比,分數像素運動矢量之間的相關性大大增強.通過實驗表明,分數像素運動估計時,尤其是在搜索點接近全局中心點時,其誤差曲面大都是單峰值的[4].

圖2 CBFPS搜索過程Fig.2 Illustration o f CBFPS algo rithm

在全搜索法中,對最佳整數像素周圍的所有分數像素點進行搜索.基于搜索中心點周圍為單峰值誤差曲面的假定,且周圍候選的分數像素點成為最優(yōu)點的概率不等,則使用快速分數像素搜索算法將取得較好的效果.通過統(tǒng)計分析,在各種內容的圖像中,超過90%的最優(yōu)搜索點都在搜索中心[4].但是仍不能忽視分數像素的搜索,因為微小分數像素精度運動矢量的偏差,都可能帶來比特率的明顯增大.

由圖1可知,B,C,D,E,F,G,H,I為整數像素點A周圍的8個1/2像素點.本文將其分為兩組,其中B,C,D,E4個點與A點的距離相同,分為第1組;F,G,H,I4個點與A點的距離相同,分為第2組.顯然,第1組與A點的距離比第2組更小.由上節(jié)分析可知,搜索點周圍局部的誤差曲面為單峰值,并且分數像素位置的亮度和色度像素值由鄰近已編碼點進行內插而得.因此,與第2組相比,第1組的搜索點與A點的相關性更強.

文獻[4]指出在各類內容的圖像中,超過90%的最優(yōu)搜索點都在搜索中心.在進行分數像素搜索的初始階段能否通過相關性較強的鄰近4個1/2像素點而預測最優(yōu)搜索點是否在搜索中心?此處采用全搜索法對new s-qcif.yuv等6個視頻序列進行統(tǒng)計分析.實驗中比較B,C,D,E4個點的拉格朗日函數值,若A點為其最小點,而1/2像素搜索完成后的最佳點為F,G,H,I中的某一點,則說明僅通過第1組4個1/2像素點預測A點為最佳點不可靠,計數值N1加1,否則說明預測準確,計數值N2加1,實驗中1/2像素搜索總次數用N0表示,統(tǒng)計結果如表1所示.

表1 預測中心的準確度統(tǒng)計結果Tab.1 Statistical resu ltsof accu racy fo r the p redicted center

由表1可知,鄰近1/2像素點對最優(yōu)點是否在搜索中心預測的平均準確率為98.84%.因此,通過計算與最佳整數像素點較近的第1組1/2像素點預測實際的運動矢量是否為搜索中心可信.

由前文分析可知,距離搜索中心較近的點與其相關性較強,因此可以通過第1組1/2像素點運動矢量的變化趨勢來預測實際最佳點的位置,從而舍棄部分第2組中1/2像素點的搜索.此處同樣對new s-qcif.yuv等6個視頻序列進行統(tǒng)計分析.實驗中采用全搜索法,計算與最佳整數像素點較近的第1組1/2像素點和較遠的第2組1/2像素點的拉格朗日函數值.如果以下4種情況之一發(fā)生:a.第1組中最匹配的1/2像素點為圖1中的B點,而全搜索后最佳的1/2像素點為圖1中的H點或I點;b.第1組中最匹配的1/2像素點為圖1中的C點,而全搜索后最佳的1/2像素點為圖1中的F點或G點;c.第1組中最匹配的1/2像素點為圖1中的D點,而全搜索后最佳的1/2像素點為圖1中的G點或I點;d.第1組中最匹配的1/2像素點為圖1中的E點,而全搜索后最佳的1/2像素點為圖1中的F點或H點,則說明實際的運動矢量變化趨勢與第1組中的運動矢量變化趨勢方向不同,這樣利用第1組1/2像素點預測實際最佳點的位置不準確,此時計數值N1加1,否則說明預測準確,計數值N2加1.實驗中1/2像素搜索總次數用表示N0,統(tǒng)計結果如表2所示.

表2 運動矢量相關性分析Tab.2 Co rrelation analysis o fm o tion vecto r

由表2可知,鄰近整數像素點的運動矢量趨勢與實際的運動矢量趨勢相同率達到99.80%.因此,通過計算與最佳整數像素點較近的4個第1組1/2像素點的運動矢量預測實際的運動矢量可信.

3 分數像素運動估計改進算法

3.1 分數像素運動估計跳過條件

H.264標準編碼時首先進行整數像素運動估計,然后以最佳整數點為中心進行分數像素精度搜索.當分數像素搜索之后最佳點仍為整數點時,分數像素搜索過程可以直接跳過.整數像素運動估計最后一般利用小菱形模型搜索,因此整數最佳點及其上下左右4個點的拉格朗日函數值都已知.如圖1中A,H1,H2,V1,V2點的坐標分別為(0,0),(-1,0),(1,0),(0,-1)和(0,1),其函數值已知,表示為F(A),F(H1),F(H2),F(V1),F(V2).考慮一維情況下(水平方向為例),F(A),F(H1),F(H2)3點可構造一拋物線模型,表達式如下:

式中x0表示F取得最小值時的像素位置,a,x0,b3個未知參數可通過F(A),F(H1),F(H2)的值得出,經推導可得:

當x0在(-1/8,1/8)區(qū)間時,F(A)小于F(1/4)和F(-1/4),如圖3(a)所示.此時預測在水平方向上最佳整數點的函數值小于其周圍的分數像素位置函數值,可跳過分數像素搜索;當x0不在(-1/8,1/8)時,最佳整數點的函數值大于其周圍的分數像素位置函數值,如圖3(b)所示,則分數像素搜索是必要的.由此可將跳過分數像素搜索的條件歸納為｜x0｜＜1/8,為避免分母部分可能為0的情況,將其轉化為:

在垂直方向上同理得:

由此得出跳過分數像素搜索的條件為(5)和(6)式同時成立.

圖3 分數像素運動估計誤差曲面拋物線模型F ig.3 Parabo licm odel of error surface of fractiona l p ix elM E

3.2 改進的運動估計算法

通過以上分析,本文提出一種改進的分數像素運動估計算法.算法首先利用上節(jié)的結論,分析公式(5)和公式(6)是否成立,若成立則直接跳過分數像素運動估計,不成立則進行分數像素運動估計.然后判斷分塊模式是否為模式4到模式7,若是則采用CB FPS算法,不是則計算與最佳整數像素點鄰近4個1/2像素點的拉格朗日函數值,通過對1/2像素點函數值的比較預測實際運動矢量的變化趨勢并進行分數像素搜索.以1/2像素精度搜索為例,詳細過程如下.

計算整數像素點A及第1組中4個1/2像素點B,C,D,E的拉格朗日函數值,得到函數值最小的1/2像素點,共分為5種情況:

(1)若A點拉格朗日函數值最小,則A點為最佳1/2像素點,搜索結束;

(2)若B點拉格朗日函數值最小,則又分為3種情況:

①D,E兩點的函數值相同,則繼續(xù)搜索F,G兩點,得到函數值最小的1/2像素點;

②D,E兩點中D點的函數值較小,則只繼續(xù)搜索F點,得到函數值最小的1/2像素點;

③D,E兩點中E點的函數值較小,則只繼續(xù)搜索G點,得到函數值最小的1/2像素點.

(3)若C點拉格朗日函數值最小,則又分為3種情況:

①D,E兩點的函數值相同,則繼續(xù)搜索H,I兩點,得到函數值最小的1/2像素點;

②D,E兩點中D點的函數值較小,則只繼續(xù)搜索H點,得到函數值最小的1/2像素點;

③D,E兩點中E點的函數值較小,則只繼續(xù)搜索I點,得到函數值最小的1/2像素點.

(4)若D點拉格朗日函數值最小,則又分為3種情況:

①B,C兩點的函數值相同,則繼續(xù)搜索F,H兩點,得到函數值最小的1/2像素點;

②B,C兩點中B點的函數值較小,則只繼續(xù)搜索F點,得到函數值最小的1/2像素點;

③B,C兩點中C點的函數值較小,則只繼續(xù)搜索H點,得到函數值最小的1/2像素點.

(5)若E點拉格朗日函數值最小,則又分為3種情況:

①B,C兩點的函數值相同,則繼續(xù)搜索G,I兩點,得到函數值最小的1/2像素點;

②B,C兩點中B點的函數值較小,則只繼續(xù)搜索G點,得到函數值最小的1/2像素點;

③B,C兩點中C點的函數值較小,則只繼續(xù)搜索I點,得到函數值最小的1/2像素點.

1/4像素精度搜索方法與1/2像素精度搜索方法同理,以1/2像素搜索的最佳點為中心搜索其周圍的1/4像素點,并同樣分5種情況最終搜索出1/4像素精度的最佳點.在該算法中,1/4像素精度搜索一般只需計算4個分數像素點,極少的分塊搜索需計算5個點或6個點.與全搜索法相比,在保證編碼質量的情況下搜索的點數明顯減少.

4 實驗結果及分析

本文采用QC IF格式序列,實驗平臺為JM 12.2版,幀率30H z,編碼幀數為100.第1幀為I幀,其余部分為P幀,參考幀為5幀,熵編碼采用CABAC,量化因子QP=28,整數像素部分的運動估計方法為UM HexagonS,實驗結果如表3所示.

表3 分數像素搜索算法實驗結果Tab.3 Sim u lation resu ltso f fractionalp ixel search algo rithm

由表3可知,本文提出的算法與全搜索法相比,圖像的PSNR近似不變,B itrate平均上升4.48%,分數像素平均搜索點數為4.91,比全搜索法的16個點下降69.32%.而CBFPS算法和PPHPS算法的PSNR分別下降0.18dB和0.02dB,B itrate上升0.18%和3.25%,分數像素平均搜索點數下降52.71%和31.25%.從實驗結果可以看出,本文算法在大幅提高計算速度的同時較好的保持了編碼圖像的PSNR和B itrate.

5 結束語

通過分析分數像素運動估計的過程,利用分數像素點之間相關性強及搜索中心點周圍局部范圍為單峰值誤差曲面的特點,提出了一種改進的分數像素運動估計算法.該算法在保證圖像質量和增加較少碼率的條件下,能有效減少搜索點數,從而使搜索速度顯著提高,便于硬件實現,能較好地滿足實際應用中實時性的要求.

[1] W iegand T,Su llivan G J,B jon tegaard G,et al.O verview o f the H.264/AVC video coding standard[J]. IEEE T ransactions on C ircuit and System fo r V ideo Techno logy,2003,13(7):560-576.

[2] Chang Jingfu,Jin Jang leou.A quad ratic p red iction based fractional-p ixel m o tion estim ation algo rithm fo r H.264[J].Jou rnalo f V isualComm un ication and Im age Rep resen tation,2006,17(5):1 074-1 089.

[3] Chen Gang,Jia Zhenhong,Chen H e.A fast quarterp ixelm o tion estim ation algo rithm fo r H.264/AVC[J].Op toelectronics L etters,2008,4(1):66-68.

[4] W ang Yu jen,Cheng Chaochung,Chang T iansheuan.A fast fractional pelm o tion estim ation algo rithm fo r H.264/M PEG-4 AVC [J]. IEEE In ternational Sym posium on C ircuits and System s,2006(1):3 974-3 977.

[5] Shen L iquan,Zhang Zhaoyang,L iu Zh i,et al.A n adap tive and fast fractional p ixel search algo rithm in H.264[J].Signal Processing,2007,87(11):2629-2639.

[6] Chen Du,H e Yun,Zheng Jun li.PPHPS-a parabo lic p red iction-based fast half-p ixel search algo rithm fo r very low bit-rate m oving-p ictu re coding[J]. IEEE T ransactions on C ircuits and System s fo r V ideo Techno logy,2003,13(6):514-518.

[7] Chen Zh ibo,Xu Jianfeng,H e Yun,et al. Fast in teger-pel and fractional-pelm o tion estim ation fo r H.264/AVC[J].Jou rnal o f V isual Comm unication and Im age Rep resen tation,2006,17(2):264-290.

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