H.264運動估計算法比較與分析

劉書平

（四川大學計算機學院，成都 610065）

H.264運動估計算法比較與分析

劉書平

（四川大學計算機學院，成都 610065）

針對H.264/AVC編碼器中幾種典型的運動估計算法進行研究，并用基本的測試視頻序列對這幾種運動估計算法進行實驗和測試，實驗結果表明優化的運動估計算法UMHexagonS和精簡的UMHexagonS（SUMHexagonS）在保持PSNR基本不變的情況下大大減少運動估計時間和整體的編碼時間，并且編碼每幀使用的比特數基本不變。同時總結出運動估計算法的優化方向，為以后的優化工作奠定基礎。

運動估計；FS；UMHexagonS；SUMHexagonS；PSNR

0 引言

運動估計算法是視頻編解碼算法的核心，優化運動估計算法可提高運動估計的速度，減少運動估計時間，從而大大減少編碼時間，提高編碼效率。通過對運動估計算法及其優化算法的研究，能夠從前人優化的經驗中找到優化方向，同時掌握優化最新進展，從而開發出新的更高效的運動估計算法。

H.264標準中，每一幀圖像都被分成大小相同的宏塊，即以宏塊為基本處理單元。運動估計的基本思想為：首先，將幀中每個宏塊分成多個互不重疊的塊，并且假設每個分塊內部所有像素的運動方向一致，然后對當前宏塊中的每一塊，在當前幀的前面幀的一幀或多幀中的某一給定搜索范圍按照一定的匹配原則和搜索策略找出和當前塊最為相似的塊，也就是最佳匹配塊，最后通過計算最佳匹配塊和當前塊的相對位置得到運動位移，該運動位移記為當前塊的運動矢量（MV）。對匹配塊和當前塊的差值、運動矢量和相應的參考索引進行編碼。運動估計研究的主要內容就是如何快速有效地找到最佳匹配塊并計算出運動矢量。

1 常用的快匹配準則

均方誤差（Mean Square Error，MSE）

平均絕對誤差 （Mean Absolute Difference/Error，MAD/MAE）

絕對誤差之和 （Sum of Absolute Difference/Error，SAD/SAE）

歸一化互相關函數 （Normalized Cross-Correlation Function，NCCF）

其中，（i，j）為運動矢量，f和fref為當前幀和參考幀的像素值，M×N為宏塊的大小，各匹配準則值最小時的（i，j）為最佳運動矢量，MSE精度最高，運算量最大，MAD和SAD精度相同，SAD運算量更小，只涉及減法和求絕對值的運算，一般選擇SAD作為匹配準則。

2 幾種典型的運動估計算法介紹

2.1 FS

FS（全搜索算法，Full Search）對搜索窗口中的所有像素點進行SAD值計算，并從得到的所有SAD中找出最小的SAD值，它對應的點所對應的偏移量即為所求的運動矢量，全搜索算法的搜索方式有2種：光柵式全搜索和螺旋式全搜索，下面以光柵式全搜索為例進行說明。如圖1所示，光柵式搜索是從搜索窗口的左上角開始按照從左到右從上到下的順序對搜索窗口中每一個像素點進行SAD值計算，直到搜索窗口中所有像素點的SAD值都被計算完為止，然后比較所有像素點的SAD值選出最小的SAD值，其對應的位移量即為運動矢量。通過全搜索算法找到的匹配點一定是全局最佳匹配點，然而它的計算量太大很難滿足實時處理的要求，所以實際應用中很少采用。

圖1 光柵全搜索的過程圖示

2.2 UMHexagonS

UMHexagonS算法[1]是由清華大學的Zhibo Chen等人提出來的一種快速運動估計算法，屬于混合型搜索算法，之所以稱之為混合型搜索算法是因為它分為4步，每一步都采用不同的搜索模式。

4個步驟分別為：搜索起始點預測，非對稱十字形搜索，不均勻多層六邊形搜索和擴展的六邊形搜索。UMHexagonS在每一個搜索步驟之后都使用了提前終止判斷函數，如果滿足搜索終止條件則終止當前搜索步驟，直接進入后面的擴展的六邊形搜索中的步驟，提前終止判斷函數（EARLY_TERMINATION）使用提前檢測零塊的技術實現，所謂零塊，即變換系數經量化后全為零的塊，經過理論推導，得出如果搜索塊的SAD（絕對誤差之和）小于門限值Ti則搜索結束，而對于不同的塊模式門限值Ti不同，當然，如果當前最小代價函數值比SAD（SAD小于門限值Ti的前提下）還小，則搜索過程也該停止，UMHexagonS還使用預測的SAD值來代替原始SAD值從而加快運動估計速度，門限值Ti的選擇、SAD的預測及具體的理論推導參見文獻[2]。

UMHexagonS步驟為：

圖2 UMHexagonS步驟實例（假設起始搜索點為（0，0），搜索窗口水平搜索范圍W=16）

（1）搜索起始點預測

使用運動矢量預測方法（中值預測，上層預測，對應塊預測，相鄰參考幀預測）對當前塊的運動矢量進行預測，選取代價最小的運動矢量預測值對應的點作為下一搜索步驟的起始點。

表1 當前塊模式與其運動矢量預測值的候選值間的關系

（2）非對稱十字形搜索（Unsymmetrical-cross search）

如圖3中step2所示，由上三角標注非對稱十字形，非對稱是指水平方向的搜索點多于垂直方向的搜索點，這是因為自然圖像序列的水平方向運動多于垂直方向的運動，所以水平方向的搜索范圍為W=16，垂直方向的搜索范圍為W/2=8，當圖像中垂直方向的運動多于水平方向的運動時也可將垂直方向的搜索點擴展至W，搜索點間距為2。具有最小代價的運動矢量將作為下一搜索步驟的搜索中心。非對稱十字形搜索可以近乎準確的給出最佳運動矢量。

（3）不均勻多層六邊形網格搜索（Uneven Multi-Hexagon-Grid Search）

分為兩步：

第一步，由圖2中step3-1所示，由紅色圓點標注，圍繞搜索中心的搜索范圍為2的全搜索；

第二步，由圖2中step3-2所示，由非填充矩形標注，以第一步搜索所得最優點為中心進行多層六邊形網格搜索。

由于自然圖像序列中水平方向的運動多于垂直方向的運動，所以采用16點六邊形模式（16-HP）作為基本搜索模式。多層六邊形網格是由基本的16點六邊形按照1到W/4的比例擴展得到，搜索時是從最里面的六邊形開始直到最外面的六邊形，通過這一步得到的最佳運動矢量將作為下一搜索步驟的搜索中心。

（4）擴展的六邊形搜索（Extended Hexagon-based Search，EHS）

也分為兩步，第一步如圖3-2中step4-1所示，由下三角標注，以上一搜索步驟得到的最優點為中心進行6個點的六邊形模板搜索，直到最優點位于六邊形模板的中心才進入第二步，否則重復該步驟。

第二步如圖中step4-2所示，由填充成黑色的矩形標注，以第一步得到的最優點為中心進行4個點的菱形搜索，直到最優點位于菱形模板的中心，該最優點即為最終的最優點。即使用上一步搜索得到的最優點為搜索中心進行六邊形搜索，直到最優點位于六邊形的中心，再使用菱形搜索模板進行搜索，直到最小塊失真的點位于新形成的菱形的中心，搜索得到的點即為整個搜索的最優點。

2.3 SUMHexagonS

SUMHexagonS（精簡的UMHexagonS算法）[3]是由Xiaoquan Yi等人在UMHexagons算法基礎上改進和簡化的算法，相比于UMHexagons和FS，SUMHexagonS能在實現相似甚至更好的率失真性能的情況下減少55%到94%的運動估計時間，并且與低復雜度模式下的FS算法相比，SUMHexagonS能減少18%的比特率，此外，使用SUMHexagonS產生的運動矢量更平滑，故編碼運動矢量差使用的比特數減少，這對易錯環境下的數據分割和不均等差錯保護很有利。

（1）低內存的運動矢量預測方案

SUMHexagonS提供了一種低內存的運動矢量預測方案，即相比于UMHexagonS算法，SUMHexagonS消耗的內存更小，UMHexagonS算法使用空域、時域預測和上層預測對運動適量及SAD進行預測，這些都需要消耗很大的內存，并且H.264/AVC多種塊大小、多參考幀及1/4像素精度的運動補償等技術使得時域預測消耗的內存最大， 這對內存受限的應用極其不利。SUMHexagonS提供的低內存運動估計預測方案為：對于運動矢量預測，只使用空域中值預測和上層預測，對于SAD預測，相比于UMHexagonS算法使用4種預測方法，SUMHexagonS只使用上層預測。仿真結果表明，SUMHexagonS使用這種低內存運動估計預測方案能達到和UMHexagonS算法近乎相同的性能。

UMHexagonS算法使用局部全搜索和十字形、鉆石（菱形）、六邊形和大六邊形等多種形狀模板來避免陷入局部最優，盡管使用了基于量化參數的提前終止技術，但仍然會耗費很多時間，同時，獲得門限值會對每個搜索塊進行浮點計算，這更加耗費時間。SUM HexagonS避免了使用局部全搜索，并且使用了簡化的提前終止技術。

SUMHexagonS流程如下[3]：

圖3 SUMHexagonS流程

圖4 每個視頻序列不同算法性能對比

（2）簡化的提前終止技術

SUMHexagonS將提前終止技術門限的初始值設置如下：

CrossSearchThreshold1=800，CrossSearchThreshold2 =7000，and ConvergeThreshold=1000，對于不同大小的塊可以通過簡單地移位操作來獲得這些門限值，相比與先前使用浮點乘法的提前終止技術，SUMHexagonS使用簡單的移位和比較將其簡化。

3 實驗結果及分析

3.1 測試環境

測試用軟件：H.264參考軟件JM，版本為JM10.1[4]

畫圖軟件：MATLAB版本7.11.0.584（R2010b）32位（Win32）

測試用PC：處理器為Intel Core i3 CPU M 370@ 2.40GHz 2.40GHz，內存為2.00GB（1.86GB可用），操作系統為Windows 7旗艦版32位操作系統

測試用序列為CIF格式（352×288，YUV 4:2:0），使用H.264基本檔次進行編碼，配置文件參考基本檔次配置文件encoderbaseline.cfg，保持大部分參數不變，只改變了其中幾個參數：

使用不同的運動估計算法UseFME的值不一樣

圖5 使用bus_cif序列對3種算法以幀為單位進行比較

3.2 結果與分析

首先從平均PSNR、碼率、總的ME時間（總的運動估計時間）、總的編碼時間4個方面使用5個測試視頻序列對3個算法：全搜索算法（FS）、UMHexagonS算法及SUMHexagonS算法進行了統計和對比，如圖1所示。

相對于FS，兩種優化算法在平均PSNR只降低0.01到0.06的范圍內，使運動估計時間降低56.64%到86.02%。

另外，還從PSNR、運動估計時間（MET）、編碼使用比特數、編碼總時間4個方面對3個算法基于幀進行了分析，下面為運動比較劇烈的測試視頻序列buscif（CIF，352×288）的實驗結果:

從實驗結果可以看出優化的運動估計算法UMHexagonS算法和SUMHexagonS算法在保持PSNR基本不變的情況下大大減少了運動估計時間和整體的編碼時間，并且編碼每幀使用的比特數基本不變。

4 結語

通過對上述幾種典型運動估計算法的詳細分析，總結出運動估計過程最關鍵的幾步為：確定搜索窗口的大小、形狀、位置，選擇搜索起始點，選擇塊匹配準則，確定搜索策略。優化方法都是相對于全搜索算法減少總的搜索點數，UMHexagonS算法在搜索起始點和搜索策略等方面對先前算法進行了改進，使用了搜索起始點預測、提前終止和多種搜索模板混合使用的技術，大大減少了運動估計的時間。SUMHexagonS算法在UMHexagonS算法的基礎上減少了搜索起始點預測的預測方法，簡化了提前終止技術，使用簡單的移位和比較技術設置提前終止的門限值，大大減少了原來使用浮點乘法實現的計算量。我們以后對運動估計算法的優化也可以從搜索起始點、搜索策略方面進行改進，同時也可以從搜索窗口的大小、塊匹配準則等方面對其進行優化。

參考文獻：

[1]Chen Z，Zhou P，He Y.Fast Integer Pel and Fractional Pel Motion Estimation for JVT[J].JVT-F017，2002:5-13.

[2]Chen Z，Zhou P，He Y.Fast Motion Estimation for JVT.JVT-G016.doc，Joint Video Team（JVT）of ISO/IEC MPEG&ITU-T VCEG [C].7th meeting，Pattaya，TH（March 5-13，2003），2003.

[3]Yi X，Zhang J，Ling N，et al.Improved and Simplified Fast Motion Estimation for JM[C].JVT-P021.doc，Joint Video Team（JVT）of ISO/IEC MPEG&ITU-T VCEG，16th meeting，Pozan，Poland.2005.

[4]JM參考軟件http://iphome.hhi.de/suehring/tml/

Comparison and Analysis of H.264 Motion Estimation Algorithms

LIU Shu-ping
（College of Computer Science，Sichuan University，Chengdu 610065）

Studies several typical motion estimation algorithms in H.264/AVC encoder,and tests these motion estimation algorithms with the basic test video sequence.The experimental results show that the optimized motion estimation algorithm UMHexagonS and SUMHexagonS greatly reduce the motion estimation time and the overall coding time while PSNR and the number of bits used per frame are almost unchanged.At the same time,summarizes the optimization direction of the motion estimation algorithm,which lays the foundation for the future optimization.

Motion Estimation;Full Search;UMHexagonS;SUMHexagonS;PSNR

1007-1423（2017）09-0041-06

10.3969/j.issn.1007-1423.2017.09.011

劉書平（1991-），女，四川簡陽人，碩士研究生，研究方向為圖形圖像技術

2017-01-12

2017-03-10