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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析
　本文在H.264的參考軟件JM10.1上實(shí)現(xiàn)了原算法和改進(jìn)后的UMHexagonS算法,，選取3個(gè)具有代表性的標(biāo)準(zhǔn)QCIF測試序列和3個(gè)CIF序列的前100幀進(jìn)行測試,，編碼模式為IPPP。測試序列如表1所示,，實(shí)驗(yàn)參數(shù)設(shè)置如表2所示,，其他參數(shù)設(shè)置為默認(rèn)值。實(shí)驗(yàn)平臺(tái)為：Windows7系統(tǒng),，Intel Core i3,，2.2 GHz CPU，4 GB內(nèi)存,，VS2010。實(shí)驗(yàn)結(jié)果如表3~表5所示,。

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

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

參考文獻(xiàn)
[1] 畢厚杰.新一代視頻壓縮編碼標(biāo)準(zhǔn)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.