基于中心點預(yù)測的分?jǐn)?shù)像素運動估計改進(jìn)算法

熊承義,董朝南

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

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

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

1 H.264中分?jǐn)?shù)像素搜索

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

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

圖1 分?jǐn)?shù)像素全搜索過程Fig.1 Illustration o f fu ll fractionalp ixel search

2 分?jǐn)?shù)像素運動估計分析

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

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

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

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

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

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

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

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

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

由前文分析可知,距離搜索中心較近的點與其相關(guān)性較強,因此可以通過第1組1/2像素點運動矢量的變化趨勢來預(yù)測實際最佳點的位置,從而舍棄部分第2組中1/2像素點的搜索.此處同樣對new s-qcif.yuv等6個視頻序列進(jìn)行統(tǒng)計分析.實驗中采用全搜索法,計算與最佳整數(shù)像素點較近的第1組1/2像素點和較遠(yuǎn)的第2組1/2像素點的拉格朗日函數(shù)值.如果以下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像素點預(yù)測實際最佳點的位置不準(zhǔn)確,此時計數(shù)值N1加1,否則說明預(yù)測準(zhǔn)確,計數(shù)值N2加1.實驗中1/2像素搜索總次數(shù)用表示N0,統(tǒng)計結(jié)果如表2所示.

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

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

3 分?jǐn)?shù)像素運動估計改進(jìn)算法

3.1 分?jǐn)?shù)像素運動估計跳過條件

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

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

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

在垂直方向上同理得:

由此得出跳過分?jǐn)?shù)像素搜索的條件為(5)和(6)式同時成立.

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

3.2 改進(jìn)的運動估計算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果及分析

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

表3 分?jǐn)?shù)像素搜索算法實驗結(jié)果Tab.3 Sim u lation resu ltso f fractionalp ixel search algo rithm

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

5 結(jié)束語

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

[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] 畢厚杰.新一代視頻壓縮編碼標(biāo)準(zhǔn)-H.264/AVC[M].北京:人民郵電出版社,2005:97-99.