摘  要： 針對(duì)UMHexagonS算法計(jì)算復(fù)雜、耗時(shí)等問題提出改進(jìn)算法。首先，通過在預(yù)測(cè)起始點(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ù)測(cè)起始點(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ù)測(cè)。在UMHexagonS算法中，采用了4種預(yù)測(cè)模式得到的矢量來估計(jì)當(dāng)前塊的初始運(yùn)動(dòng)矢量，分別為中值矢量預(yù)測(cè)、上層矢量預(yù)測(cè)、空間相關(guān)塊矢量預(yù)測(cè)和參考幀對(duì)應(yīng)塊矢量預(yù)測(cè)。
?。?）在步驟2中，算法進(jìn)行一個(gè)水平搜索范圍為S而垂直搜索范圍為S／2的非對(duì)稱十字搜索，其中，S為搜索窗的范圍，搜索步長(zhǎng)為2。取這些搜索位置中具有最小代價(jià)函數(shù)值（min_mcost）的點(diǎn)作為下一步的起始點(diǎn)。
　（3）在步驟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)作為下一步的搜索中心。
?。?）小六邊形模板反復(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)矢量場(chǎng)通常是柔和平滑的，變化也比較平緩。參考文獻(xiàn)[7]中統(tǒng)計(jì)研究發(fā)現(xiàn)，超過80%的運(yùn)動(dòng)矢量預(yù)測(cè)值位于中心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ù)減少了，但是新的搜索模板更接近于圓，從而保持了各方向的勻稱，可以更有效地檢測(cè)出最優(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測(cè)試序列和3個(gè)CIF序列的前100幀進(jìn)行測(cè)試，編碼模式為IPPP。測(cè)試序列如表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.