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

王 旭，王國中，李國平，滕國偉，趙海武

(上海大學通信與信息工程學院，上海200444)

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

王 旭，王國中，李國平，滕國偉，趙海武

(上海大學通信與信息工程學院，上海200444)

在視頻編碼中，運動估計占據約70%的編碼時間，是視頻編碼中的重要環節。整像素運動搜索UMHexagonS算法以較低的計算復雜度，達到了接近全搜索算法的率失真性能，而被H.264和AVS等標準所采納。在分析UMHexagonS算法的基礎上，對其非對稱十字形搜索和非均勻多層次六邊形格點搜索算法進行了改進。實驗表明，在基本保持原算法性能的同時，該算法比原算法減少了60%～70%的搜索點數，降低了運動估計的計算復雜度。

運動估計;UMHexagonS;低復雜度;視頻編碼

目前的視頻編解碼標準如H.264［1］，AVS1［2-3］等均采用了時空混合編碼框架，其中幀間預測作為框架中最為重要的部分，占據大部分的計算量。因而如何優化運動估計算法以提高編碼器的效率成為研究熱點。已有的運動搜索算法中，精度最高的是全搜索(Full Search，FS)［4］。由于它的計算量最大，一些有效的快速搜索算法被相繼提出，如三步搜索法(Three Step Search，TTS)［5］，菱形搜索法(Diamond Search，DS)［6］和性能更優越的六邊形搜索法(Hexagon-Based Search，HEXBS)［7］，顯著降低了計算復雜度。2002年Zhibo Chen等兼顧考慮以上算法的優缺點，提出了非對稱十字形多層次六邊形搜索算法UMHexagonS［8］，其性能接近全搜索算法，已被AVS1等標準所采納。但其復雜度仍較高，且實現較復雜。

本文將對UMHexagonS算法進行詳細分析，進一步利用像素的空間相關性及視頻序列的運動特性，改進搜索策略，降低了計算復雜度。實驗表明，在基本保持原算法率失真性能的同時，大量減少搜索點數。

1 UMHexagonS算法分析

1.1 搜索策略分析

UMHexagonS算法是一種混合搜索方案，它采用多種搜索模板進行混合搜索，同時利用了運動矢量在時空上的相關性，達到了良好的率失真性能，避免陷入局部最優。UMHexagonS算法包括4個搜索步驟，即:1)起始搜索點的預測;2)非對稱十字形搜索;3)非均勻多層次六邊形搜索;4)擴展六邊形搜索。該算法的搜索模板和算法的搜索過程分別如圖1～2所示。

圖1 UMHexagonS算法搜索模板

1)起始搜索點的預測

在搜索過程中，對起始點進行準確預測可保證搜索時在起始點周圍較小區域內快速找到匹配點，并不陷入局部最優，提升運動估計的整體性能。UMHexagonS算法采用了4種預測方式進行起始點預測，并按照得到的4個運動矢量及零矢量所指向的位置進行搜索，計算代價函數，選取代價函數值最小的運動矢量所對應的點作

圖2 UMHexagonS算法搜索過程

2)非對稱十字形搜索

起始點確定后，進行非對稱十字形搜索。大量統計結果表明，視頻序列中的運動矢量在水平方向和垂直方向上分布的概率最大，且在水平方向上運動更加劇烈。因此使用非對稱十字形搜索可以利用這一特點，更快得到運動矢量，為下一級搜索提供相對準確的起始搜索點。UMHexagonS算法采用的十字形模板中，水平方向的搜索點數取為垂直方向的兩倍，以達到相對精確的搜索結果。模板如圖1a所示。該模板可根據實際需要對搜索點數比例進行調整，以適應不同序列的運動特性。但由于要對十字形中每一個點進行搜索，而最佳匹配點只存在于十字形的某一個位置，存在較大的計算資源浪費。

3)非均勻多層次六邊形格點搜索

該搜索主要針對的是視頻中運動較劇烈或者不規則的情況。考慮到物體的實際運動規律，搜索點是非均勻分布的:在中心點附近分布較多，而在距離中心點的區域分布相對稀疏。該搜索模式在水平方向上的搜索點數要比垂直方向上多。

該搜索模型分為兩個步驟:

(1)如圖2中的step3-1所示，在搜索中心點周圍5×5的范圍內進行全搜索，試圖在小范圍內找到更加精確的運動矢量;

(2)如圖2中的step3-2所示，進行多層次六邊形格點的搜索，其搜索格點是由16點的六邊形模板為單位，再乘以不同的比例擴展得到的。擴展得到的格點非均勻地分布在整個搜索區域，在運動劇烈的視頻序列中可以避免搜索陷入局部最小點。整個搜索過程從內部向外部擴展。

該步驟可達到較高的搜索精度，但由于搜索層數較多且每層搜索的點數較多，會造成不必要的計算量浪費。

4)擴展六邊形搜索

經過多層次六邊形格點搜索之后，搜索精度可能不夠準確，可采用基于中心的搜索方案對運動矢量進行進一步的校正。因此一種擴展的六邊形搜索法被提出［8］，其搜索模板如圖1c中的“2”、“3”所示。在小搜索范圍內，由于得到的運動矢量已經十分精確，一般可以跳過以上兩步搜索，直接進行擴展的六邊形搜索。

1.2 UMHexagonS算法復雜度分析

由以上對于UMHexagonS算法分析可知，該算法中采用混合搜索，可實現精確的塊匹配，大大提高搜索的準確度。而搜索的點數是算法復雜度的重要體現，設搜索范圍為search_range，則進行非對稱十字形搜索時搜索點數SP1=(1+0.5)×search_range，進行非對稱多層次六邊形搜索時搜索點數SP2=4×search_range，兩步共需搜索點數SP_number=5.5×search_range。當搜索范圍增大，搜索的點數增多，如當搜索范圍為16時，共需要搜索88個點，計算復雜度較高，擴展到整個編碼過程中，占據主要運算量，因此本文將對這兩個步驟分別進行優化，進一步降低其計算復雜度。

2 改進的UMHexagonS算法

2.1 提前截止的非對稱十字形搜索

在視頻序列的每一幀圖像中，像素與像素之間存在著較強的空間相關性，并且通常情況下空間距離越近則相關性越強。據此，本文對UMHexagonS中的非對稱十字形搜索提出一種提前截止的改進方法。由于空間相關性的存在，與最佳匹配點空間上越近的搜索點，其匹配差值越小，則匹配差值越小則該點距最佳匹配點越近，反之則越遠。因此在搜索時，可以選取一個合理的匹配差值閾值，當匹配差值大于該閾值時，就停止搜索，從而減少不必要點的搜索，提高搜索速度。因此，可以以搜索起始點為界，可將水平和垂直方向的搜索點分別劃分為兩部分，如圖3所示。

設起始搜索點pmv為點0，其SAD為q，并將其作為匹配差值閾值。水平方向上，若最佳匹配點在紅色分界線的左邊，那么分界線左邊區域的搜索點與最佳匹配點的距離比起始搜索點0與最佳匹配點的距離遠，右邊搜索點的匹配差值比0點的要大。因此在搜索右邊區域的點時若出現匹配差值大于q的點，則可判定最佳匹配點不在右邊區域，停止對右邊區域的搜索，轉而搜索左邊區域的點，對于左邊區域采取同樣的方法。垂直方向與水平方向同理。

圖3 非對稱十字形搜索模板搜索點在水平和垂直方向的劃分

總之，在十字形的一個方向搜索時，若出現SAD值大于起始搜索點0的SAD值q的點，就提前終止這一方向的搜索，轉去搜索以0點為分界線的另外一邊區域，圖4說明了改進后算法的搜索流程。由于將4個方向的搜索縮減到匹配點所在方向上的搜索，這種提前截止的方法可以有效減少搜索點，降低運算量。實驗表明，使用該算法時搜索點數約為原算法搜索點數的1/3。且由于利用了像素間的空間相關性，視頻編碼質量下降很小。

圖4 改進的非對稱十字形搜索流程

2.2 簡化的非均勻多層次六邊形格點搜索算法

在UMHexagonS算法的非均勻多層次六邊形格點搜索(如圖5所示)中，由于充分考慮了運動特性和搜索精度，使用了水平垂直非均勻，共4層的搜索方法。這種方法對運動較為劇烈的場景較為適合，而對于普通序列搜索了很多不必要的點，因此有必要減少搜索點數，降低其運算量。

圖5 改進后的多層次六邊形模板(搜索范圍為16)

大量序列的運動方向大致均勻分布，據此本文提出了一種新的多層次六邊形模板，如圖5所示。在該模板中，采取了均勻分布的搜索路徑，共12個搜索點，在搜索點數上比原有算法的非均勻16點模板每層減少了4點，有效減少了搜索點數;同時，由于上一步的均勻十字形搜索得到了較為準確的起始點，原模板的較密的4層搜索將消耗很多不必要的計算量。為此，該模板將多層次六邊形每兩層之間的間距加大一倍，搜索順序仍為從內向外。則當搜索范圍不變時，搜索層數將減少一半。由于每少一層六邊形就可以減少12個搜索點，可以進一步地減少搜索點數，降低搜索的運算量，提高運動搜索速度。在實際應用中，搜索點數可根據搜索范圍自動調整。實驗表明，這種模板下進行運動搜索時，搜索點數大大減少，而視頻編碼效率只有微弱下降。

將兩種改進算法結合后，進一步減少了運動估計過程中的搜索點數，并能保證視頻編碼效率不產生較大的降低。

3 實驗結果與分析

3.1 實驗平臺與參數配置

本文所使用開發環境是VS2005。實驗所用平臺配置為:Intel(R)Pentium(R)Dual 1.60 GHz，1 Gbyte內存，操作系統為Windows XP。

在測試改進算法的性能時，采用了3種不同分辨率的視頻序列，分別為 D1:720×576，CIF:352×288，1 080i:1 980×1 080。編碼參數的配置如表1所示。

表1 編碼參數

3.2 實驗結果與性能分析

本實驗選用了運動程度和分辨率不同的視頻序列用于原有UMHexagonS算法與改進算法的編碼性能對比。實驗中共測試了3種不同分辨率的序列，每種分辨率測試3個序列。D1:分辨率720×576，測試序列為basketball，horseriding和foreman;CIF:分辨率352×288，測試序列為carph，news和stefan;1 080i:分辨率1 980× 1 080，測試序列為fireworks，kayak和stockholmpan。各個序列的實驗結果對比如表2所示。其中，improve1代表只對非對稱十字搜索算法改進，improve2代表只對多層次六邊形算法改進。improve1+2代表改進的非對稱十字形搜索和多層次六邊形搜索結合后的算法。在實驗中，各算法的編碼比特率基本保持不變。

由以上實驗數據可以看到，本文的改進算法與原UMHexagonS算法相比，PSNR只對部分序列有小幅下降，在搜索次數大幅度減少的情況下基本保持了原有算法的性能。

單獨進行改進的非對稱十字搜索時，搜索次數比原算法的十字搜索次數減少了70%以上，單獨進行改進的多層次六邊形搜索時，搜索次數比原算法的非均勻多層次六邊形搜索次數減少了60%以上。改進的十字形搜索與多層次六邊形搜索結合起來進行搜索時，總搜索次數比原來減少65%左右，可見運動估計的速度整體有了大幅的提高。由于運動估計是編碼中最耗時的模塊，因此改進的算法可以有效降低編碼時間，提高編碼器效率。

在9個測試序列中，序列 basketball，horseriding，carph，stefan以及kayak的運動比較劇烈，news和stockholmpan的運動程度較小。實驗數據表明，改進算法對運動程度小的序列率失真性能較好，其PSNR值幾乎沒有出現下降;對運動程度大的序列的性能次之，PSNR值出現了少許降低。因此該改進算法對運動程度小的視頻序列的更加適合。

表2 改進算法與原算法實驗結果對比

4 小結

本文在分析UMHexagonS搜索算法的基礎上，提出了提前截止的非對稱十字形搜索算法和簡化的非均勻多層次六邊形搜索算法。實驗表明，改進后的算法有效減少了運動估計中的搜索點數，提高了運動估計的速度，并保持原算法的率失真性能，有利于本算法的硬件實施和實時應用。

［1］WIEGAND T，SULLIVAN G，lUTHRA A.Overview of the H.264/AVC video coding standard［J］.IEEE Trans.Circuits and System for Video Technology，2003，13(7):560-576.

［2］黃鐵軍，高文，王國中.數字音視頻編解碼技術標準AVS發展歷程與應用前景［J］.上海大學學報:自然科學版，2013，19(3):221-224.

［3］虞露，胡倩，易峰.AVS視頻的技術特征［J］.電視技術，2006，30(7):8-11.

［4］SHENOLIKAR P，NAROTE S.Different approaches for motion estimation［C］//Proc.INCACEC 2009.［S.l.］:IEEE Press，2009:1-4.

［5］ JING X，CHAU L.An efficient three-step search algorithm for block motion estimation［J］.IEEE Trans.Multimedia，2004，6(3):435-438.

［6］ZHUS，MA K.A new diamond search algorithm for fastblock-matchingmotion estimation［J］.IEEE Trans.Image Processing，2000，9(2):287-290.

［7］ZHU C，LIN X，CHAU L.Hexagon based search pattern for fast block motion estimation［J］.IEEE Trans.Circuits and System for Video Technology，2002，12(5):349-355.

［8］CHEN Z，ZHOU P，HE Y.Fast integer pel and fractionalpelmotion estimation for JVT［S］.2002.

王國中(1962—)，博士生導師，教授，主研視頻編解碼與多媒體通信;

李國平(1974—)，碩士生導師，主研視頻壓縮編碼理論算法與實現，視頻編解碼軟件設計與實現;

滕國偉(1975—)，碩士生導師，主研先進音視頻壓縮技術、先進視頻監控技術及3D視頻處理技術;

趙海武(1973—)，碩士生導師，主研數字音視頻編解碼技術、復用技術及編解碼技術標準。

Im proved UMHexagonSM otion Estimation Algorithm

WANG Xu，WANG Guozhong，LIGuoping，TENG Guowei，ZHAO Haiwu
(School of Communication and Information Engineering，Shanghai University，Shanghai200444，China)

Motion estimation is a significantpartof video coding，accounting for around 70%of the computing time.Integer pixelmotion search algorithm UMHexagonS achieves a performance close to full search algorithm with lower computation complexity，so is adopted by H.264 and AVS.An improved nonsymmetrical cross search and anisotropic multilayer hexagon search method is proposed in this paper.Experiment results show that the proposed algorithm reduces search points by 60%～70%while keeping the original performance generally，so the computation complexity ofmotion estimation process is reduced.

motion estimation;UMHexagonS;low complexity;video coding

TN919.81

A

工信部電子信息產業發展基金項目(1213711)為下一步搜索的起始點。根據得到的SAD可判斷是否跳過后面兩個步驟直接進行擴展六邊形搜索。這種方法同時利用了幀內和幀間的運動矢量相關性，實驗表明預測準確率很高。

王 旭(1989—)，女，碩士生，主研視頻圖像處理;

?? 雯

2013-12-12

【本文獻信息】王旭，王國中，李國平，等.一種改進的UMHexagonS運動估計算法［J］.電視技術，2014，38(23).