基于Ｈ．２６４的一種快速１／４像素運動估計算法

摘要:提出了一種新的1/4像素運動估計算法。新算法根據相鄰分數像素點之間高度相關的運動估計匹配誤差和運動矢量方向，選擇最優整像素點周圍最有可能的1/2像素點進行搜索，擯棄可能性較小的1/2像素點，在最優1/2像素點周圍進行鉆石搜索得到最優的1/4像素點。新算法只搜索7個點，與全搜索的16個點相比少了56.3%。實驗證明，與全搜索法相比，新算法的峰值信噪比平均下降了0.06 dB，比特率平均上升了1.3%。

關鍵詞:H.264; 相關性; 匹配誤差; 運動矢量方向

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001－3695(2008)02－0373－03

在視頻編碼中，運動估計(ME)是消除圖像幀間冗余度的有效方法。現代視頻壓縮編碼算法中廣泛應用了簡單有效的塊匹配式的運動估計算法。國際標準H.261采用的是整像素的塊匹配算法。然而，若使用整像素作為單位描述實際運動物體的位移，將產生較大誤差;若使用1/2像素進行描述將能降低很大部分的運動補償誤差。所以，H.263#65380;MPEG－1#65380;MPEG－2等國際標準中相繼采用半像素精度的運動估計。同時又因為精確的運動描述可以得到更小的預測誤差，獲得更好的視覺效果，所以H.264[1~3]中引入了1/4像素精度運動估計技術來提高運動補償的精度，進一步減少預測誤差，提高壓縮率。

近年來，研究者們提出了許多正像素快速運動估計算法，如三步搜索法[4]#65380;新鉆石搜索法[5]等來降低整像素運動估計的復雜度，但是研究分數像素精度運動估計的人卻為數不多。事實上，分數像素精度運動估計對PSNR值有較大影響，與不使用分數像素精度運動估計時相比可以提高2~3 dB，但同時也具有較大的計算復雜度。

現有的分數像素快速搜索算法中，比較典型的算法有:

a)分數像素的拋物線預測算法[6]。根據SAD(絕對差值之和)函數在最優匹配點周圍子區域內為凸函數的特性，先求出最優1/2像素點;然后再根據最優和次優1/2像素點求出最優的1/4像素點。

b)基于MSE的小數像素運動估計快速算法[7]。根據MSE(均方誤差)在[0，1]內可近似為二次曲線D(x)=ax2+bx+c的特性，可求出當D(x)在[0，1]取最小值時的x值。由于二維函數D(x，y)可以分解為兩個一維函數D(x)和D(y)，分別對x和y進行一維計算，得出的點(x，y)就是最優的分數像素點。

本文提出了一種新的1/4像素快速搜索算法(a fast algorithm based on highly correlation of motion estimation cost and motion vector direction，CCD)。該算法基于相鄰分數像素點高度相關的運動估計匹配誤差(用SAD值表示)和運動矢量方向，可使搜索點減少到7個。在極小圖像質量損失的前提下，該算法大大提升了編碼速度，有利于實時應用。

1分數精度運動矢量的特性

實驗證明，如果匹配誤差曲面在搜索窗口內是單峰值的，那么快速運動估計算法將能得到最優的效果。

在搜索范圍較大#65380;視頻內容較復雜的情況下，整像素運動估計匹配誤差曲面不是單峰值的。所以，整像素搜索就容易陷入局部最小點。如果對整像素進行插值，則相鄰分像素之間的相關性將大大高于相鄰整像素之間的相關性。在多數情況下，分像素精度的誤差曲面都是單峰值的[8]。因此，越靠近全局最小點匹配誤差就越小。

很明顯，多種內容的圖像中，超過90%的最優運動矢量點都在搜索中心。但仍然不能忽視分數像素精度的運動矢量搜索。即使微小的分像素精度的運動矢量的錯誤偏移，都會帶來比特率的明顯增大。

在全搜索方法中，對最優整像素點周圍所有的分像素點都進行搜索。但是，基于單峰值匹配誤差曲面的設想，如果候選的分像素點成為分像素運動矢量最優點的概率不相等時，快速搜索算法能取得較好的效果。

21/4像素全搜索法原理

其中:p代表先前重建圖像中的整像素點或分像點;c代表當前圖像中的像素點;L(·)代表像素的亮度值。

1/4像素全搜索算法分為兩步:a)計算C點周圍的8個1/2像素點的F(p)值，求出最優的1/2像素點，假設為I點;b)計算最優的1/2像素點I周圍8個1/4像素點的F(p)值，求出最優的1/4像素點。總共需要搜索16個像素點。

3CCD算法分析

從前面的分析中可知，分數像素的匹配點都緊鄰著最優的整像素點，因而可以縮小搜索半徑來減少搜索點，略過那些可能性較小的點[10]。同時經研究發現分像素運動矢量與整像素運動矢量以及整像素次優點有較強的相關性[11]，所以在上面的基礎上再利用整像素最優點和整像素次優點來預測分數像素運動矢量的大致方向。這樣就可以進一步減少計算量。CCD算法就是基于這樣的思想提出來的。

圖3中假設C點是整像素運動預測所得的最優整像素點。D1#65380;D2#65380;D3#65380;D4#65380;H1#65380;H2#65380;V1和V2是C點周圍8個相鄰的整像素點(圖3中小方塊表示的點);Ⅰ#65380;Ⅱ#65380;Ⅲ#65380;Ⅳ#65380;V#65380;Ⅵ#65380;Ⅶ#65380;Ⅷ(圖3中小圓點表示的點)是C點周圍的8個1/2像素點;1#65380;2#65380;3#65380;4(圖 3中小菱形塊表示的點)是1/2像素點I周圍的4個1/4像素點。

CCD算法需要假定最優整像素點周圍的8個鄰點(D1#65380;D2#65380;D3#65380;D4#65380;H1#65380;H2#65380;V1#65380;V2)的SAD值作為已知條件，然后只需要比較這8個SAD值得到整像素次優點。這一點不難得到。例如對于三步搜索法，它最后的搜索步長是1，即整像素運動估計結束時，最優整像素點C周圍的8個鄰點的SAD值已經得到。對于鉆石搜索法等，在搜索完成后，8個點中的絕大多數都已經得到，只需要再計算出個別未知的整像素點的SAD值即可。

CCD算法的思想是，根據D1~D4#65380;H1#65380;H2#65380;V1#65380;V28個點中SAD值最小的點與C點的相對位置來決定最有可能的1/2像素點的搜索方向。

如果次優整像素點在最優整像素點(C)的對角位置，則搜索如圖4(a)所示位置的3個1/2像素點;如果次優整像素點和最優整像素點的相對位置如圖4(b)所示，則搜索兩點之間如圖所示的3個1/2像素點，得到最優的1/2像素點。然后用鉆石搜索法搜索最優1/2像素點周圍的4個1/4像素點，得到4個1/4像素點的SAD值;取SAD值最小的1/4像素點作為搜索到的最優1/4像素點。

4仿真結果

本文采用兩種格式的序列:CIF格式(352×288)的stefan;QCIF格式(176×144)的coastguard#65380;foreman#65380;mobile#65380;news。實驗平臺使用H.264的JM10.2版，幀率是30 Hz，編碼100幀。除第一幀是I幀，其他都是P幀，參考幀為1幀，SAD計算使用Hadamard變換，進行RD優化，熵編碼采用CAVLC。表1~3分別為量化因子QP=24，28，32時的仿真結果。

在不同QP值下，在不同的序列中， CCD算法與參考算法相比，圖像的PSNR值平均只下降了0.06 dB，最多的也只下降了0.1 dB，比特率平均增加了1.2%。可以看出，CCD算法適用于各種不同的運動序列，提升了應用的實時性，適合在硬件結構中實現。

5結束語

針對絕大部分最優運動矢量均分布在最優整像素點周圍的特點，根據相鄰分數像素點高度相關的運動估計匹配誤差和運動矢量方向，本文提出了一種新的快速1/4像素運動估計算法—CCD算法。該算法與全搜索法相比，可以提高20%以上的運動估計速度。與此同時，PSNR值平均只下降0.06 dB左右，是一種快速高效的1/4像素運動估計算法，適用于各種不同的運動序列，符合實際應用中實時性的要求。

參考文獻:

[1]H.264/ISO/IEC 14496－10 AVC， Joint video specification joint committee draft[S].

[2]WILEGAND T， SULLIVAB G J， BJOINTEGAARD G， et al. Overview of the H.264 video coding standard[J]. IEEE Tansactions on Circuits and Systems for Video Technology， 2003，13(7):560－576.

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

[4]KOGA T， IINUMA K， ISHIGURO T. Motion compensated interframe coding for video conferencing[C]//Proc of Nat Telecommun Conf. 1981:1－5.

[5]ZHOU S， MA K K. A new diamond search algorithm for fast block－matching motion estimation[J]. IEEE Transaction on Image processing， 2000，9(2):287－290.

[6]CHEN Zhi－bo， DU Cheng， WANG Jing－hua， et.al. PPFPS: a para－boloid prediction based fractional pixel search strategy for H.26L[C]//Proc of ISCAS. 2002:9－12.

[7]王維東，姚慶棟，劉鵬.小數像素運動估計快速算法[J].通信學報，2003，24(4):128－132.

[8]CHEN Zhi－bo， ZHOU Peng， HE Yun. Fast motion estimation for JVT[C]// JVT G－016 JVT of ISO/IEC MPEGITU－T VCEG(ISO/IEC JTC1/SC29/WG11 and ITU－T SG16 Q.6).Pattaya Ⅱ，Thailand:[s.n.]， 2003.

[9]WANG Yu－jen， CHENG Chao－chung， CHANG Tian－sheuan. A fast fractional pel motion estimation algorithm for H.264/MPEG－4 AVC[C]//IEEE International Symposium on Circuits and Systems. 2006.

[10]向友君，郭寶龍.基于起點預測的快速運動估計算法[J].西安電子科技大學學報，2003，30(3):386－390.

[11]喬軒，樊星，葉秀清.H.264中1/4像素運動預測的快速搜索算法[J].電視技術，2004(9):15－17.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”