基于Ｈ．２６４的１／４像素精度的快速搜索算法

（西安電子科技大學 機電工程學院ICIE研究所 西安710071）

摘 要：新的視頻標準 H.264為了獲得更精確的運動向量和更高的壓縮比，引入了分數像素運動補償技術 但同時也增加了運動補償過程的復雜度。為了克服這一局限，根據相鄰分數像素點之間高度相關的運動估計匹配誤差和運動矢量方向，以及運動向量具有中心偏置的特性提出了一種新的1/4像素精度快速搜索算法(QAFSA)。實驗表明：該算法在保持圖像質量和碼率基本不變的情況下大大減少了搜索點的數目，有效地提高了分數像素運動估計的速度。

關鍵詞：H.264 視頻標準; 運動估計; 分數像素搜索; 相關性； 運動矢量方向

中圖分類號：TP391.72文獻標志碼：A

文章編號：1001-3695(2009)05-1958-03

Quarter-pixel accuracy fast search algorithm based on H.264

WEI Wei GUO Bao-long

(Institute of ICIE School of Electromechanical Engineering Xidian University Xi’an 710071 China)

Abstract:H.264 is a new video standardization in which fractional pixel motion compensation is applied in order to achieve more accurate motion description and higher compression efficiency. However it remarkably increases complexity in motion estimation process. Therefore reducing the computation load incurred by fractional pixel search is necessary. This paper proposed an efficient fast fractional pixel motion estimation algorithm (QAFSA) based on the highly correlation of motion estimation cost motion vector direction and the center-biased of motion vector for H.264. Test results show that the proposal algorithm greatly reduces the number of searching points and enhances the speed of motion estimation while keeping the nearly equal quality of the image.

Key words：H.264 coding standard; motion estimation; fractional pixel search; correlation； motion vector direction

新的視頻編碼標準H.264由ITU-T和MPEG組成的聯合專家組JVT共同制定^[1~3]。由于采取了增強的運動估計ME(motion estimation)與運動補償 MC(motion compensation)技術，如多參考幀預測編碼、多種可變塊大小的幀間編碼模式、1/4像素精度的運動補償等，取得了比之前的MPEG-2、H.263 等標準更高的效率，尤其在低碼率視頻方面比MPEG-4有明顯提高，具有更高的壓縮比、更好的IP和無線網絡信道的適應性。H.264在數字視頻通信和存儲領域得到越來越廣泛的應用，但同時計算復雜度也大幅增加，大約相當于H.263的3倍。

通過分析 H.264的編碼器可看出，運動估計的計算量占整個編碼器計算量的60%～80%。所以，如何減少運動估計的計算量成為問題的關鍵。運動估計可以分為兩步:a)整像素運動估計；b)分像素運動估計。H.264中采用的是1/4像素運動估計。隨著整像素運動估計的快速搜索算法的發展，整像素的搜索點數大幅度減少，平均只需要10個。這導致1/4像素運動估計的計算量占整個運動估計計算量的比重越來越大。因此如何減少1/4像素運動估計的計算量就成了一個重要問題。

1 已有的算法

整數像素搜索已經比較成熟，經典的主要有三步搜索法、鉆石搜索算法、基于塊的梯度下降搜索法、運動矢量場自適應搜索算法、UMHexagonS^[4]等。其中，由于非對稱十字型多層次六邊形網格搜索算法的運算量相對于H.26x中原有的快速全搜索算法，可節約90%以上，而且在高碼率、大運動圖像序列編碼時，在保持較好率失真性能的條件下運算量十分低，因此已被H.264標準正式采納。

現有的分像素快速搜索算法中，比較典型的算法如下：

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

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

c)基于運動補償誤差的數學模型快速算法^[7]。方法不需要通過整像素內插的方法求分像素，而是先根據最優整像素點及其周圍的八個整像素點的運動補償誤差值（即SAD值）來求出模型的系數；然后再用模型估計分像素位置的SAD值，從而求出最優的分像素位置。

本文提出了一種新的1/4像素快速搜索算法(QAFSA)，可使搜索點數減少到6~12個。相對于1/4像素全搜索算法需搜索17個點，效率提高約為 30%～70%。

2 H. 264中分數像素全搜索算法

H.264中經典的分數像素算法的搜索過程可以分為三個步驟：

a)在搜索區進行整像素運動估計，求出整像素最佳匹配點，對當前的重建參考幀進行內插，以建立用于1/2精度運動估計的參考幀。 

b)對整像素最優匹配點周圍八個1/2像素點計算 SAD，并與整像素最優點SAD值比較。其中，SAD最小的一個點即為1/2像素精度最優匹配點；然后對當前重建的半像素精度的參考幀像素進行內插，建立具有1/4像素精度的參考幀。

c)對1/2像素最優匹配點周圍八個1/4像素點計算SAD并與上一步中得到的1/2像素最優點 SAD值進行對比，取其中SAD值最小的即為1/4像素最優匹配點，如圖1所示。

從上面的搜索策略可以看出，H.264的分數像素全搜索算法是從整數像素到1/2像素，再到1/4像素的一個過程。另外必須考慮一種還比較常見的情況，即當1/4像素精度搜索后最優點仍位于最初搜索中心點5時(圖2)，則先后全搜索的八個1/2像素點和八個1/4像素點都將成為冗余計算。

3 QAFSA的提出

運動估計時間的長短取決于搜索點數的多少，對 H.264進行優化 就是在保證搜索準確性的前提下減少搜索點數。通過研究H.264的整數像素運動估計算法可以發現，實際中絕大多數圖像序列的運動都很小，其運動矢量總是高度集中在搜索窗的中心位置附近，在進行初始起點預測之后，預測起點更接近最優點，所以沒有必要將這些模板由大到小進行匹配運算，可以先利用小模板來判斷初始搜索點是否就是最優匹配點，如果滿足直接結束搜索。現有的大多數快速整像素搜索算法都是基于這種運動向量中心偏置的特性提出來的，并且效果不錯。圖3^[8]給出了最優整像素點周圍的最優分像素點的分布情況。

由此，提出一種新的想法，首先利用十字模板進行最優整像素點周圍的四個1/4像素點的搜索，當搜索結果的最優點為中心點時搜索結束；否則再進一步進行1/2 像素點的搜索。這樣當搜索后最優點仍位于搜索中心時，只需搜索五個點。

為了進一步減少1/2像素的搜索點數，可以利用已經搜索的四個1/4像素點的SAD值去預測^[9]最優點可能的方向，從而排除一些成為最優點可能性小的位置點，只搜索計算可能性大的點的SAD值，則將進一步提高運動搜索速度。

基于上述分析，本文提出這種新的快速 1/4像素運動估計搜索算法(QAFSA)。具體步驟如下： a)如圖4所示，首先搜索中心點5及其周圍十字形狀的4個1/4像素點a、b、c、d，比較各點SAD值（選出具有最小SAD值的點記為最優點，同時記錄具有次小SAD值的點為次優點）以確定最優1/4像素點。若最優點為搜索中心點 5 則搜索結束；否則進入下一步。b)若a為最優點，那么b、c、d是可能的次優點。若次優點為b，則搜索a、b朝向的1/2像素點，即1、2、4；若次優點為d，則搜索a、d朝向的2、3、6像素點；而c距a最遠，不可能優于b、d成為次優點。若最優點為其他點，依此類推。

c)比較步驟b)中搜索計算的三個1/2像素點和步驟a)中所得的最優1/4像素點(設為點b)的SAD值。同樣地，選出具有最小SAD值的點記為最優點，同時記錄具有次小SAD值的點為次優點。若最優點為1/4像素點a，則搜索結束；否則進入步驟d)。

d)現在得到的是步驟c)中所得的最優1/2像素點，還需要在它周圍進行1/4像素精度的搜索。對于此1/4像素的搜索，采用已有的基于預測的方向搜索算法^[9~11]。同樣根據最優點和次優點的位置分兩種情況，如圖5所示。根據最優點和次優點所處的位置和方向選擇位于它們之間的三個點作為1/4像素的搜索點。

左圖情況：若1為最優點，2、4分別為次優點時，分別搜索e、 f、g和h、 j、g；若次優點為步驟a)中所得的最優1/4像素點b時，搜索i、g、 f。

右圖情況：若4為最優點，次優點為1，搜索h、 j、 g；次優點為2，搜索i、g、b；若次優點為步驟a)中所得的最優1/4像素點b時，搜索g、b、e。最優點為2的情況與之類似，不再贅述。

最后比較最優1/2像素點及其周圍搜索的1/4像素點的SAD值，選出具有最小的點作為經過1/4像素精度精確后的最優點。至此，搜索結束。

4 仿真結果與分析

在相同條件下，對上述算法進行驗證。分別對小運動和大運動的視頻序列進行測試。小運動序列選取Akiyu、salesman；大運動序列選取coastguard、foreman。量化值選取為28。測試過程中選用H.264 視頻編碼器的版本為JM10.2，YUV 取樣格式為4∶2∶0，編碼幀數為100幀，幀率為30 fps。為減少測試運行時間，選用1個參考幀，測試指標采用亮度信號信噪比(PSNR)，SAD計算使用Hadamard變換，進行RD優化，熵編碼采用CAVLC。表1為仿真結果。

從表1中可以看出，QAFSA的PSNR相對于全搜索算法下降幾乎為0，比特率略有增加；運動估計時間減少在40%～50%。其中，前兩個序列的編碼時間減少一半以上，這與該算法利用運動向量具有中心偏置的特點有關，而這一特點在小運動序列情況下更為突出。同時也看到新算法對于大運動序列coastguard與foreman編碼效率的提高也在40%以上。總體而言，新算法在保持圖像質量和碼率幾乎不變的情況下，適用于各種不同的運動序列，提升了應用的實時性，適合在硬件結構中實現。

5 結束語

本文通過分析 H.264視頻編碼中分數像素運動估計的過程，利用運動向量具有中心偏置的特性和針對絕大部分最優運動矢量均分布在最優整像素點周圍的特點，并根據相鄰分數像素點高度相關的運動估計匹配誤差和運動矢量方向，提出了一種新的快速1/4像素運動估計算法——QAFSA。其大大減少了分數像素搜索過程中的搜索點數，提高了運動估計的編碼速度，減少了編碼時間，符合實際應用中實時性的要求。

參考文獻：

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

[2]WILEGAND T SULIVAB G J JOINTEGAARD G B， et al. Overview of the H.264 video coding standard[J]. IEEE Trans on Circuits and Systems for Video Technology 2003 13(7):560-576.

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

[4]郭寶龍，倪偉，閆允一.通信中的視頻信號處理[M].北京:電子工業出版社，2007.

[5]CHEN Zhi-bo DU Cheng WANG Jing-hua，et al. PPFPS:a paraboloid prediction based fractional pixel search strategy for H.26L[C]//Proc of IEEE International Symposium on Circuits and Systems. 2002:9-12.

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

[7]JEONG J. Fast sub-pixel motion estimation having lower complexity [C]// Porc of IEEE International Conference on Consumer Electro-nics. 2003:174-175.

[8]WANG Yu-jen，CHEN Chao-chung CHANG T S.A fast fractional pel motion estimation algorithm for H.264/ MPEG-4AVC[C]//Proc of IEEE International Symposium on Circuits and System.2006.

[9]智西湖，智艾娣.面向H.264運動估計的分數搜索方法[J].計算機工程與應用2004 40(30):95-96.

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

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