摘  要： 針對UMHexagonS算法計算復雜、耗時等問題提出改進算法。首先，通過在預測起始點處增加了準靜止塊閾值來判斷是否可以立即停止搜索；然后，用擴展的菱形搜索代替原算法中的5×5的螺旋式全搜索以降低計算復雜度；最后，利用多層次8點八邊形代替多六邊形網格搜索。實驗結果表明，改進算法在保證圖像質量的前提下可以有效地減少10%~30%的運動估計時間，提高了總體的編碼性能。
關鍵詞： H.264；運動估計；UMHexagonS算法；中止判斷

　運動估計是視頻壓縮編碼的關鍵部分，能有效地去除視頻序列中時間域上的冗余度[1]。目前各種視頻編碼標準中廣泛應用的運動估計算法是塊匹配算法，匹配準則是塊碼率-失真度。最新的H.264標準采用的框架與先前的標準（如MPEG-2、H.263、MPEG4等）大致相同[2]，在這個框架下，運動估計和補償是去除幀間冗余非常重要的方法，但同時也是編碼中比較耗時的部分[3]。
　目前，H.264已正式采納了“非對稱十字型多層次六邊形格點搜索”（UMHexagonS）算法，它的運算量相對于快速全搜索算法可節約90%以上，同時能保持較好的性能。但是其也存在運算量大、耗時多等不足。因此，本文針對UMHexagonS算法的不足提出了改進算法，在預測起始點處增加了一個準靜止塊閾值判斷，并用菱形搜索取代5×5的螺旋式全搜索以及對多六邊形搜索模板進行了改進。在保證原算法圖像質量的前提下，進一步降低運算量，從而提高整個H.264編碼器的編碼性能。
1 UMHexagonS算法
　UMHexagonS算法的搜索路徑如圖1所示，基本步驟[4]如下。
　（1）起始搜索點預測。在UMHexagonS算法中，采用了4種預測模式得到的矢量來估計當前塊的初始運動矢量，分別為中值矢量預測、上層矢量預測、空間相關塊矢量預測和參考幀對應塊矢量預測。
　（2）在步驟2中，算法進行一個水平搜索范圍為S而垂直搜索范圍為S／2的非對稱十字搜索，其中，S為搜索窗的范圍，搜索步長為2。取這些搜索位置中具有最小代價函數值（min_mcost）的點作為下一步的起始點。
　（3）在步驟3-1中，進行一個5×5共25個點的螺旋式全搜索，并取具有min_mcost的點作為下一步的搜索中心。
　（4）多層次大六邊形格點搜索如步驟3-2所示。從中心開始在整個搜索窗中逐步進行非對稱六邊形搜索，直到搜索窗的邊界，并取具有min_mcost的點作為下一步的搜索中心。
　（5）小六邊形模板反復搜索如步驟4-1和4-2所示。用一個擴展六邊形和一個小菱形搜索模式循環進行六邊形搜索，直到具有min_mcost的點位于六邊形的中心，然后再進行一個小菱形搜索，這4個位置中具有min_mcost的點即作為當前塊的運動矢量所指位置。

　　本文通過對不同標準序列的大量統計實驗分析得出，T過大會對圖像質量有明顯的影響，而T過小則不利于搜索時間的提高，T=700時能夠很好地區別出靜止或準靜止塊，在不影響圖像質量的情況下提高搜索速度。
2.2 5×5螺旋式全搜索的改進
　在UMHexagonS算法的步驟3-1中，5×5螺旋式全搜索需要檢查25個搜索點，這樣不僅復雜度高、運算量大而且費時。因此，有必要對其進行優化。
　通常來說，現實生活中的視頻圖像的運動矢量場通常是柔和平滑的，變化也比較平緩。參考文獻[7]中統計研究發現，超過80%的運動矢量預測值位于中心5×5的網格區域內，但不是均勻分布，如圖3所示。從圖3可以看出，總的5×5網格區域內的菱形區域（也就是A+B+C+D區域）運動矢量分布概率為77.52%，相對5×5網格區域的運動矢量分布概率81.79%只減少了4.27%，而搜索點數減少了12個。因此，本文將用菱形搜索（如圖4（a）所示）替換原來的5×5螺旋式全搜索（如圖4（b）所示），能夠在基本保證視頻的質量的情況下減少搜索點數，提高搜索速度。

2.3 多六邊形搜索的改進
　本文提出的改進算法的搜索步驟如圖5所示。本文利用多層次8點八邊形搜索代替UMHexagonS算法中的非對稱六邊形搜索。將每層搜索的點數由原來的16個減少到8個，即能夠減少約50%的計算量。同時經研究發現，雖然搜索點數減少了，但是新的搜索模板更接近于圓，從而保持了各方向的勻稱，可以更有效地檢測出最優運動矢量的位置，因此具有較好的搜索效率，同時也保持了良好的圖像質量。
改進后的算法主流程圖如圖6所示。

3 實驗結果與分析
　本文在H.264的參考軟件JM10.1上實現了原算法和改進后的UMHexagonS算法，選取3個具有代表性的標準QCIF測試序列和3個CIF序列的前100幀進行測試，編碼模式為IPPP。測試序列如表1所示，實驗參數設置如表2所示，其他參數設置為默認值。實驗平臺為：Windows7系統，Intel Core i3，2.2 GHz CPU，4 GB內存，VS2010。實驗結果如表3~表5所示。

　從表3可以看出，改進算法比原算法的運動估計時間減少了10%~30%，且隨著運動程度由平緩到劇烈，算法節省的時間也隨之增加。表4顯示了圖像的峰值信噪比，除了akiyo序列下降了0.01外，其他都不降反升，說明改進算法很好地保持了圖像的質量。從表5顯示的碼率變化來看，碼率平均增加了0.5%左右，最大的也不超過1%，對信道傳輸影響不大。

　其中，對于變化區域小且緩慢的akiyo序列，改進算法速度提高相對較少，只有9.511%，而對于變化區域大且運動相對較劇烈的bus和football序列而言，速度提高較大，在30%左右。因此，本文提出的改進算法適合各種運動類型的視頻序列，尤其對于運動劇烈的圖像序列效果更好。
　圖7和圖8分別顯示了3個QCIF序列和3個CIF序列原算法和改進算法峰值信噪比的變化情況，原算法與改進算法在每幀的峰值信噪比變化很小，未出現大的波動，即改進算法沒有影響運動估計的準確性。通過兩幅圖的對比可以看出，CIF圖像比QCIF圖像的峰值信噪比變化更加平穩，即對于CIF圖像，改進算法的效果更好。
為了提高視頻的總體編碼性能，本文針對UMHexagonS算法的不足提出了3個方面的改進：（1）增加了準靜止塊的判斷；（2）擴展的菱形搜索模型；（3）多層次的8點八邊形格點搜索。實驗結果表明，改進算法在PSNR和碼率與原算法相近的情況下，減少了原算法中不必要的搜索點，運動估計時間減少了10%~30%，提高了編碼性能。

參考文獻
[1] 畢厚杰.新一代視頻壓縮編碼標準H.264/AVC[M].北京：人民郵電出版社，2009.
[2] WIEGAND T， SULLIVAN G J， LUTHRA A， et al. Overview of the H.264 / AVC video coding standard [J]. IEEE Transactions on CSVT， 2003，13（7）：560-576.
[3] ISO/IEC JTC1 /SC29 /WG11 and ITU-T SG16 /Q. 6 Draft ITU-T， Recomm endation H. 264 and Final Draft International Standard[S].
[4] Chen Zhibo， Zhou Peng， He Yun. Fast motion estimation for JVT[C]. JVT- G016， 2003-03.
[5] DUANMU C J， Chen Xing. Mixed diamond， hexagon， and cross search fast motion estimation algorithm for H.264[C]. Proceedings of 2008 IEEE International Conference on Multimedia and Expo， 2008：761-764.
[6] Ding X， Fan H J. A mix-pattern motion estimation search algorithm based on direction adaptation[J]． Journal of Image and Graphics，2011，16（1）：14-20．
[7] LAM C H， PO L M， CHEUNG C H. A novel kite-cross-diamond search algorithm for fast block motion estimation[C]. Proceedings of 2004 IEEE International Symposium on Circuits and Systems， 2004：729-732.