摘 要： 為了提高運動估計的搜索效率,，提出了一種基于JM模型的UMHexagonS算法的改進方案。該方案減少了搜索點數(shù),，從而減小了運算量,。經(jīng)過實驗測試，改進后的UMHexagonS算法在保證編碼圖像的質(zhì)量基本不變的同時,，能顯著減少搜索時間,。
關(guān)鍵詞： UMHexagonS算法；運動估計,；運動矢量
運動估計中的塊匹配算法因運算簡單、容易實現(xiàn)而成為目前運動估計的主流,。其中的全搜索算法（FS）,，因其窮盡搜索每個像素點，搜索精度最高,，但計算太復(fù)雜,，不能滿足實時性要求；而三步法（TSS）,、四步法（FSS）以及交叉搜索法（CSS）等,，相對FS,，減少了搜索點數(shù)，滿足實時性要求,，但不利于小的運動塊的搜索,；新三步法（NTSS）、六邊形法（HEX）,、鉆石法（DS）,、新四步法（NFSS）等，雖然提高了運動估計的速度,，解決了早期算法不利于小運動塊搜索的問題,，但易陷入局部最優(yōu)點，且不能很好地處理圖像的運動類型[1],。針對這些問題,，CHEN Z B等[2]人提出了UMHexagonS算法，它是一種混合型搜索算法,，綜合了非對稱十字形法,、六邊形法、菱形法等,，相對FS,，其均峰值信噪比（PSNR）保持基本不變，而運動估計時間減少了近90%,，是目前運動估計搜索效率最高的快速搜索算法,，己被JVT正式采納。
1 UMHexagonS算法簡介
UMHexagonS算法的搜索路徑如圖1[3]所示,，它主要分4步進行搜索：
?。?）初始搜索點預(yù)測。包括中值預(yù)測,、上層預(yù)測,、前幀預(yù)測以及鄰近參考幀預(yù)測，得到最佳的初始搜索點,。
?。?）以步驟（1）得到的最佳初始搜索點為中心，進行非對稱的十字形搜索,，取絕對差值和（SAD值）最小的點為當(dāng)前最佳匹配點,。其中水平方向的搜索范圍為窗口寬度，垂直方向的搜索范圍為窗口寬度的一半,，如圖1的step2所示,。
（3）以步驟（2）得到的最佳匹配點為搜索中心，進行5×5共25點的正方形螺旋搜索,，如圖1的step3-1所示,。接著進行多層六邊形格點搜索，取最小SAD值所對應(yīng)的點為最佳匹配點,，如圖1的step3-2所示,。
（4）該步驟分兩步進行：①以步驟（3）獲得的最佳匹配點為搜索中心,，進行擴展的六邊形搜索,。若當(dāng)前最小SAD值點位于六邊形的中心，則轉(zhuǎn)到b,；否則返回a繼續(xù)進行六邊形搜索,，直到最小SAD值點位于六邊形的中心，如圖1的step4-1所示,。②以步驟（3）的中心點為搜索中心,，進行小菱形搜索，直到最小SAD值點位于小菱形的中心時,，停止搜索,，如圖1的step4-2所示。
雖然UMHexagonS算法具有很高的編碼效率,，但仍存在兩種不足：
?。?）參考文獻[4]中指出，在如圖2所示的H.264的7種幀間預(yù)測模式中,，有30.71%~98.03%的預(yù)測塊的運動矢量全為0,。若能在UMHexagonS算法進行搜索之前就判決出這些零運動矢量，就可以提前退出搜索,，減少搜索時間,。
（2）候選搜索塊的運動劇烈程度不同,，其運動矢量的分布也不同,。UMHexagonS算法對所有的候選搜索塊都是進行4層16點的六邊形搜索，沒有考慮到候選搜索塊的運動劇烈程度的不同,，因此搜索存在冗余,。
2 基于UMHexagonS算法的改進
（1）針對UMHexagonS算法的第一種不足,，提出了零運動矢量提前判決的方法,。
在進行初始搜索點預(yù)測時，最先進行中值預(yù)測,，且所有的模板都可以使用中值預(yù)測，因此，可以判斷中值預(yù)測得到的最佳匹配點mv（best_x,，best_y）的SAD值是否小于給定的閾值,，若小于，則判決出該塊的運動矢量為0,。
定義SAD值為：
3 實驗結(jié)果與分析
本文采用JM10.1模型進行測試,，分別對運動劇烈的coastguard序列、運動中等的foreman序列,、運動平緩的news序列以及運動較復(fù)雜,、細節(jié)較多、水平方向運動特征明顯的Football序列進行了測試,，這些序列都采用QCIF格式,。編碼100幀，IPPPP……編碼模式,，采用Hardmard變換,，CABAC熵編碼，QP取28,，選取5幀參考幀,。比較運動估計時間Me-time和峰值信噪比PSNR值。測試數(shù)據(jù)結(jié)果如表1所示,。
表1中,，△Me-time表示改進的UMHexagonS算法的運動估計時間減去原UMHexagonS算法的運動估計時間得到的差值與原UMHexagonS算法的運動估計時間的百分比；△PSNR表示改進后與改進前的UMHexagonS算法的PSNR值的差值,；△bit-rate/（kb/s）表示表示改進后與改進前的UMHexagonS算法的比特率的差值,，正號表示增加，負號表示減少,。由表1可知,，改進后的算法與原算法相比，PSNR值基本保持不變,，比特率有所增加,，但是在誤差允許的范圍之內(nèi)（±0.2 kb/s）；運動估計所消耗的時間減少了10%~25%,。達到了一定的改進效果,。
本文通過分析UMHexagonS算法的一些不足，提出了零運動矢量提前判零,、自適應(yīng)選擇水平方向和垂直方向搜索范圍的相應(yīng)的改進措施以及自適應(yīng)的選擇搜索模板,。這樣的改進在保證圖像編碼質(zhì)量基本不變的情況下，減少了運動估計的搜索時間,，從而提高了編碼效率,。
參考文獻
[1] 袁濤.基于H.264運動估計算法的研究[D].重慶：重慶大學(xué),，2009.
[2] CHEN Z B，ZHOU P,， HE Y． Fast integer pel and fractional pel motion estimation for JVT[C]． 6th meeting：Awaji,，Japan. JVT-F017，2002．
[3] 畢厚杰.新一代視頻壓縮編碼標準-H.264/AVC（第二版）[M].北京：人民郵電出版社,，2009.
[4] 陳桂蘭,，劉子堅. 基于H.264的運動估計算法優(yōu)化研究[J].濮陽職業(yè)技術(shù)學(xué)院學(xué)報，2010,，23（2）：150-153.
[5] Xie Lifen,， Huang Chunqing. UMHexagonS search algorithm for fast motion estimation[C]. IEEE， 3rd International conference on ICCRD 2011 3rd Intenational Conference on ICCRD,，2011,，4：483-487.
[6] LAM C H， PO L M,， CHEUNG C H. A novel kite-cross-diamond search algorithm for fast block motion estimation [C]. Proceeding s of 2004 IEEE International Symposium on Circuits and Systems. Canada： IEEE,， 2004：729-732.