一種改進的UMHexagonS運動估計算法

楊 齊，李子印

（中國計量學院光學與電子科技學院，浙江杭州 310018）

H.264是最新的國際通用的視頻編解碼標準，由動態圖像專家組（MPEG）和視頻編碼專家組（VCEG）聯合開發并于2003年正式發布。H.264因其高精度的運動估計、多參考幀預測、多宏塊劃分模式等特點而具有高效的編碼性能，得到了廣泛的應用，并將在無線多媒體傳感器網絡、高清數字電視、遠程視頻教學等諸多領域發揮很重要的作用［1］。運動估計是H.264視頻編碼器結構中的核心部分，它和運動補償占據著整個編碼過程總運算量的70%以上。目前UMHexagonS［2］算法已被H.264編碼標準正式采納為其整像素運動估計算法，其運動估計精度較高，但同三步法、新三步法、四步法等快速算法相比，該算法的搜索點數還較多，搜索速度還不夠快。

為了能在保持較好的率失真性能的同時，進一步降低算法的復雜度，提高編碼效率。本文從起始搜索點預測、運動類型自適應搜索選擇、搜索模板和提前終止判斷四個模塊對UMHexagonS算法進行了改進。

1 UMHexagonS算法介紹

UMHexagonS是一種混合的多層次運動估計算法，主要的搜尋步驟［3］可分為以下6步:

1）起始搜索點預測。分別采用4種不同的起始點預測方法（中值預測、對應塊預測、上層預測和臨近參考幀預測）來搜索出一個使得對應的代價函數J（m，λmotion）最小的候選運動矢量作為起始搜索點，并執行提前終止判斷。

2）不對稱的十字交叉搜索。由于自然界中常見運動場景的水平方向的運動要比垂直方向的劇烈一些，故使用如圖1a所示的不對稱的十字交叉搜索方法，并執行提前終止判斷。

3）正方形搜索。以當前最佳點為中心，搜索如圖1b所示的25點方形區域。

4）多層次的六邊形搜索。以正方形搜索所獲得的最優點為中心，在搜索窗中執行直徑不斷擴大一倍的16點六邊形模板（如圖1c所示）的搜索。

5）擴展六邊形模板搜索。采用圖1d所示的搜索模板反復進行搜索，直至最優點位于六邊形的中心點時結束搜索。

6）小菱形搜索。以當前最優點作為中心，反復采用小菱形模板（如圖1e所示）進行搜索，當最優點處在小菱形的中心點時結束搜索，并把此時對應的運動矢量選定為最終的運動矢量。

圖1 UMHexagonS算法中使用的各種搜索模板

2 對UMHexagonS算法的改進

2.1 起始搜索點預測的優化

起始搜索點預測是依據運動物體的整體性和序列運動的連續性，利用待估計塊和其周邊塊的時空相關性，用周邊已編碼塊的運動矢量進行當前塊的運動矢量的起始點預測［4］。本文在此基礎上，進一步考慮到中心偏移特性和固定背景上物體邊界的情況，在經中值預測得到mvpred_MD、上層預測得到 mvpred_UP、對應塊預測得到mvpred_CB、臨近參考幀預測得到mvpred_NRP的同時，也對原點（0，0）進行搜索預測并計算出J0（m，λmotion），其對應的預測矢量為mv=（0，0）。然后通過比較這5個運動矢量各自對應的值，選取J（m，λmotion）最小的運動矢量作為起始搜索的最終預測運動矢量。

2.2 運動類型自適應的搜索選擇

同一視頻幀中的不同區域塊有著不同的運動類型，可將物體運動類型區分為靜止或慢速運動、中速運動、快速運動三種。本文通過利用起始預測運動矢量的運動信息對當前塊的運動類型進行劃分，對靜止或慢速運動塊采用小模板進行一步停止法搜索、對中速運動塊也適當減少搜索步驟、對快速運動塊則仍采用多步的詳盡搜索［5］。

圖2 改進算法的流程圖

2.3 搜索模板的改進

UMHexaongS算法在不對稱十字交叉搜索之后，再搜索當前最優點周邊的25點正方形區域，并對一些較為劇烈的運動場景采用多層次的六邊形模板進一步搜索，以獲取最佳的匹配點，這種方法可以比較準確地找到當前塊的匹配塊，但其搜索點數還比較多［7］。本文在保證重要區域的點得到精確搜索的同時，除去了對一些不重要區域的點的搜索，從而進一步減少搜索點數、提高編碼效率。

2.3.1 正方形搜索模板的改進

根據運動矢量中心偏移特性及大量的實驗表明，最佳運動矢量落在以半徑為2的圓形區域內的可能性高達80%以上［8］，UMHexagonS算法中采用的25點正方形搜索區域中有不少點是落在該圓形區域的外面。基于此，采用含有該圓形區域內的所有整像素位置的13點菱形搜索模板代替正方形搜索模板，如圖3a所示。這種搜索模板能夠確保對重要搜索區域進行搜索，并可為該搜索步驟節省12個搜索點。

2.3.2 多層次大六邊形模板的改進

考慮到常見視頻序列的水平、垂直方向較其他方向運動更加劇烈，采用多層次大菱形搜索模板代替UMHexagonS算法中所采用的多層次大六邊形搜索模板，如圖3所示。這種改進可使該步驟中的搜索點數變為原來的一半。

圖3 改進后的模板

2.4 提前終止判斷的優化

本文沿用了UMHexagonS算法所采用的提前終止判斷方法［9］。具體如下

如果滿足條件（1），其SAD值判定為很小，執行第6步;如果滿足條件（2），其SAD值判定為較小，跳至第5步;若滿足條件（3），其SAD值判定為很大，執行下一步。

UMHexagonS源算法中，在正方形搜索和多層次大六邊形搜索后均未進行提前終止的判斷。本文在改進后的13點菱形搜索和8點多層次菱形搜索的步驟后均加入了提前終止判斷（閾值判斷）條件。

結合以上四個方面對改進算法的描述，將整個改進算法的實現流程［10-11］繪制如圖2所示。

3 實驗仿真及分析

為了測試改進算法的性能，采用H.264的參考軟件JM10.2在Visual C++6.0實驗平臺上實現該算法。編碼幀數為80，參考幀數為5，搜索范圍為±16，量化參數為28，熵編碼為CABAC，編碼類型為IBPBP，幀率為30 Hz，其他參數為缺省默認設置。

實驗中選取了akiyo，foreman，coastguard三個 QCIF格式的不同運動類型的序列進行測試。其中akiyo代表慢速的運動序列，foreman代表中速運動序列，coastguard代表快速運動序列［12］。分別使用全搜索算法（FS）、UMHexagonS算法（UMH）和本文改進的算法進行實驗，實驗結果及分析如表1～3所示。

表1 實驗結果記錄

表2 改進算法相對FS算法的變化

表3 改進算法相對于UMHexagonS算法的變化

通過對表2、表3的觀察和分析可知，改進算法相比于全搜索算法而言，信噪比平均降低0.015 dB，碼率變化率為-0.7% ～+0.8%，運動估計時間節省60% ～80%;改進算法相比于UMHexagonS算法而言，信噪比平均增加0.008 dB，碼率變化率為-0.3% ～+1.1%，運動估計時間節省10%～25%。由此可知，改進后的算法在保持信噪比和碼率基本不變的情況下，大大節省了運動估計的搜索時間，有效地提高了編碼器的實時性能。

4 小結

本文提出的改進算法利用運動矢量的運動信息對視頻序列的運動類型進行劃分，并結合原點預測、模板替換和提前終止，從四個方面對UMHexagonS算法進行改進和優化。仿真結果表明，新改進的算法在維持圖像質量基本不變甚至略有改善的情形下，較大幅度地減少了搜索點數，使得運動估計的時間節省了10% ～23%，能夠更好地滿足許多實時場合（如實時視頻監控、可視電話、物聯網）的應用要求，具有較強的實用價值。

：

［1］畢厚杰，王健.新一代視頻壓縮編碼標H.264/AVC［M］.北京:人民郵電出版社，2009.

［2］CHEN Zhibo，ZHOU Peng，HE Yun.Fast integer pel and fractional pel motion estimation for JVT［C］//Proc ISO/IEC MPEG&ITU-T VCEG 6th Meeting.［S.l.］:JVT，2002.

［3］羅哲.基于快速運動估計算法UMHexagonS的改進和優化［J］.研究與開發，2011（3）:29-31.

［4］熊承義，白云.基于方向信息的快速整像素運動估計優化［J］.中南民族大學學報，2010，29（1）:62-67.

［5］楊曉珍，吳延海，王鋒.基于塊運動類型的自適應菱形運動估計搜索算法［J］. 計算機工程，2007，33（23）:220-222.

［6］丁鑫，樊慧津.基于方向自適應的運動估計混合模板搜索算法［J］.中國圖象圖形學報，2011，16（1）:14-20.

［7］申舟，李正明，潘天紅.H.264/AVC中基于搜索區域劃分及評估的運動估計［J］. 中國圖象圖形學報，2010，15（2）:242-246.

［8］LIN C C，LIN Y，HSIEH H J.Multi-direction search algorithm for block motion estimation in H.264/AVC［J］.IEEE Trans.Image Processing，2009，3（2）:88-99.

［9］楊曉琴，季曉勇.基于H.264的快速運動估計算法［J］.計算機工程與應用，2011，47（4）:174-175.

［10］盧政，盧俊.基于UMHexagonS的快速運動估計算法優化［J］.電視技術，2011，7（35）:29-31.

［11］SHI Zhiru，FERNANDO W A C，DE SILVA D V S X.A motion estimation algorithm based on predictive intensive direction search for H.264/AVC［C］//Proc.2010 ICME.［S.l.］:IEEE Press，2010:667-672.

［12］WU Xiaomin，XU Weizhang，ZHU Nanhao.A fast motion estimation algorithm for H.264［C］//Proc.2010 ICSAP.［S.l.］:IEEE Press，2010:112-116.