摘 要： 針對UMHexagonS算法計算復(fù)雜、耗時等問題提出改進算法。首先，通過在預(yù)測起始點處增加了準靜止塊閾值來判斷是否可以立即停止搜索；然后，用擴展的菱形搜索代替原算法中的5×5的螺旋式全搜索以降低計算復(fù)雜度；最后，利用多層次8點八邊形代替多六邊形網(wǎng)格搜索。實驗結(jié)果表明，改進算法在保證圖像質(zhì)量的前提下可以有效地減少10%~30%的運動估計時間，提高了總體的編碼性能。
關(guān)鍵詞： H.264；運動估計；UMHexagonS算法；中止判斷
運動估計是視頻壓縮編碼的關(guān)鍵部分，能有效地去除視頻序列中時間域上的冗余度[1]。目前各種視頻編碼標準中廣泛應(yīng)用的運動估計算法是塊匹配算法，匹配準則是塊碼率-失真度。最新的H.264標準采用的框架與先前的標準（如MPEG-2、H.263、MPEG4等）大致相同[2]，在這個框架下，運動估計和補償是去除幀間冗余非常重要的方法，但同時也是編碼中比較耗時的部分[3]。
目前，H.264已正式采納了“非對稱十字型多層次六邊形格點搜索”（UMHexagonS）算法，它的運算量相對于快速全搜索算法可節(jié)約90%以上，同時能保持較好的性能。但是其也存在運算量大、耗時多等不足。因此，本文針對UMHexagonS算法的不足提出了改進算法，在預(yù)測起始點處增加了一個準靜止塊閾值判斷，并用菱形搜索取代5×5的螺旋式全搜索以及對多六邊形搜索模板進行了改進。在保證原算法圖像質(zhì)量的前提下，進一步降低運算量，從而提高整個H.264編碼器的編碼性能。
1 UMHexagonS算法
UMHexagonS算法的搜索路徑如圖1所示，基本步驟[4]如下。
?。?）起始搜索點預(yù)測。在UMHexagonS算法中，采用了4種預(yù)測模式得到的矢量來估計當(dāng)前塊的初始運動矢量，分別為中值矢量預(yù)測、上層矢量預(yù)測、空間相關(guān)塊矢量預(yù)測和參考幀對應(yīng)塊矢量預(yù)測。
（2）在步驟2中，算法進行一個水平搜索范圍為S而垂直搜索范圍為S／2的非對稱十字搜索，其中，S為搜索窗的范圍，搜索步長為2。取這些搜索位置中具有最小代價函數(shù)值（min_mcost）的點作為下一步的起始點。
?。?）在步驟3-1中，進行一個5×5共25個點的螺旋式全搜索，并取具有min_mcost的點作為下一步的搜索中心。
?。?）多層次大六邊形格點搜索如步驟3-2所示。從中心開始在整個搜索窗中逐步進行非對稱六邊形搜索，直到搜索窗的邊界，并取具有min_mcost的點作為下一步的搜索中心。
?。?）小六邊形模板反復(fù)搜索如步驟4-1和4-2所示。用一個擴展六邊形和一個小菱形搜索模式循環(huán)進行六邊形搜索，直到具有min_mcost的點位于六邊形的中心，然后再進行一個小菱形搜索，這4個位置中具有min_mcost的點即作為當(dāng)前塊的運動矢量所指位置。
本文通過對不同標準序列的大量統(tǒng)計實驗分析得出，T過大會對圖像質(zhì)量有明顯的影響，而T過小則不利于搜索時間的提高，T=700時能夠很好地區(qū)別出靜止或準靜止塊，在不影響圖像質(zhì)量的情況下提高搜索速度。
2.2 5×5螺旋式全搜索的改進
在UMHexagonS算法的步驟3-1中，5×5螺旋式全搜索需要檢查25個搜索點，這樣不僅復(fù)雜度高、運算量大而且費時。因此，有必要對其進行優(yōu)化。
通常來說，現(xiàn)實生活中的視頻圖像的運動矢量場通常是柔和平滑的，變化也比較平緩。參考文獻[7]中統(tǒng)計研究發(fā)現(xiàn)，超過80%的運動矢量預(yù)測值位于中心5×5的網(wǎng)格區(qū)域內(nèi)，但不是均勻分布，如圖3所示。從圖3可以看出，總的5×5網(wǎng)格區(qū)域內(nèi)的菱形區(qū)域（也就是A+B+C+D區(qū)域）運動矢量分布概率為77.52%，相對5×5網(wǎng)格區(qū)域的運動矢量分布概率81.79%只減少了4.27%，而搜索點數(shù)減少了12個。因此，本文將用菱形搜索（如圖4（a）所示）替換原來的5×5螺旋式全搜索（如圖4（b）所示），能夠在基本保證視頻的質(zhì)量的情況下減少搜索點數(shù)，提高搜索速度。
2.3 多六邊形搜索的改進
本文提出的改進算法的搜索步驟如圖5所示。本文利用多層次8點八邊形搜索代替UMHexagonS算法中的非對稱六邊形搜索。將每層搜索的點數(shù)由原來的16個減少到8個，即能夠減少約50%的計算量。同時經(jīng)研究發(fā)現(xiàn)，雖然搜索點數(shù)減少了，但是新的搜索模板更接近于圓，從而保持了各方向的勻稱，可以更有效地檢測出最優(yōu)運動矢量的位置，因此具有較好的搜索效率，同時也保持了良好的圖像質(zhì)量。
改進后的算法主流程圖如圖6所示。
3 實驗結(jié)果與分析
本文在H.264的參考軟件JM10.1上實現(xiàn)了原算法和改進后的UMHexagonS算法，選取3個具有代表性的標準QCIF測試序列和3個CIF序列的前100幀進行測試，編碼模式為IPPP。測試序列如表1所示，實驗參數(shù)設(shè)置如表2所示，其他參數(shù)設(shè)置為默認值。實驗平臺為：Windows7系統(tǒng)，Intel Core i3，2.2 GHz CPU，4 GB內(nèi)存，VS2010。實驗結(jié)果如表3~表5所示。
從表3可以看出，改進算法比原算法的運動估計時間減少了10%~30%，且隨著運動程度由平緩到劇烈，算法節(jié)省的時間也隨之增加。表4顯示了圖像的峰值信噪比，除了akiyo序列下降了0.01外，其他都不降反升，說明改進算法很好地保持了圖像的質(zhì)量。從表5顯示的碼率變化來看，碼率平均增加了0.5%左右，最大的也不超過1%，對信道傳輸影響不大。
其中，對于變化區(qū)域小且緩慢的akiyo序列，改進算法速度提高相對較少，只有9.511%，而對于變化區(qū)域大且運動相對較劇烈的bus和football序列而言，速度提高較大，在30%左右。因此，本文提出的改進算法適合各種運動類型的視頻序列，尤其對于運動劇烈的圖像序列效果更好。
圖7和圖8分別顯示了3個QCIF序列和3個CIF序列原算法和改進算法峰值信噪比的變化情況，原算法與改進算法在每幀的峰值信噪比變化很小，未出現(xiàn)大的波動，即改進算法沒有影響運動估計的準確性。通過兩幅圖的對比可以看出，CIF圖像比QCIF圖像的峰值信噪比變化更加平穩(wěn)，即對于CIF圖像，改進算法的效果更好。
為了提高視頻的總體編碼性能，本文針對UMHexagonS算法的不足提出了3個方面的改進：（1）增加了準靜止塊的判斷；（2）擴展的菱形搜索模型；（3）多層次的8點八邊形格點搜索。實驗結(jié)果表明，改進算法在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.