運動估計中UMHexagonS的研究與改進

林永，楊印根，楊柳，許大姐

江西師范大學 計算機信息工程學院，南昌 330022

運動估計中UMHexagonS的研究與改進

林永，楊印根，楊柳，許大姐

江西師范大學 計算機信息工程學院，南昌 330022

H.264是新一代視頻壓縮編碼標準[1]，運動估計是視頻壓縮編碼中的一個關鍵部分，能有效地減少圖像序列的幀間冗余。在H.264整個編碼過程中，運動估計在編碼時間中占據了相當大的比例，因此，縮短運動估計時間是一個非常重要的環節。為了減少運動估計的時間，近年來國內外學者針對運動估計的快速搜索提出了很多經典的算法，其中包括：全局搜索算法（FS）、三步搜索算法（TSS）、新三步搜索算法（NTSS）、四步搜索算法（FSS）、菱形搜索算法（DS）、六邊形搜索算法（HS）、非對稱十字型多層次六邊形搜索算法（UMHexagonS）[2-3]。其中，UMHexagonS結合了其他算法的部分優點，在保證了較好的率失真性能的情況下，與FS算法相比較，節省了90%以上的運算量。目前，H.264已經正式采納了非對稱十字型多層次六邊形搜索算法。雖然如此，但對該算法的分析與研究可以發現UMHexagonS還存在一些不足之處，如起始點的預測復雜，整個搜索過程的搜索點數較多，運算復雜度較高，從整體來說，編碼時間還是較長，影響了編碼效率。

本文針對UMHexagonS算法的不足，在原算法基礎上，加入提前終止策略和搜索模板象限區域分割法，并且對UMHexagonS的螺旋搜索模板和多層次六邊形搜索模板進行了改進，減少了許多不必要的搜索點數，在保證較好的率失真性能的情況下，有效地節省了運動估計時間。

1 UMHexagonS算法介紹

（1）起始搜索點的預測，利用較高精度的起始點預測，計算得出預測運動矢量MVpred。

（2）非對稱十字型模板搜索，如圖1（a）所示。

（3）螺旋模板搜索，以上一步搜索的匹配點作為搜索中心，搜索坐標[-2，2]正方形區域內的25個候選點，類似于全局搜索，如圖1（b）所示。

（4）以非對稱十字型模板搜索的匹配點作為搜索中心，進行多層次大六邊形模板搜索，如圖1（c）所示。

（5）以上一步搜索的匹配點作為搜索中心，進行六邊形模板搜索，如圖1（d）所示。

（6）小菱形模板反復搜索，如圖1（e）所示，搜索得到最終的最佳匹配點。

圖1 UMHexagonS算法的主要搜索模板

2 UMHexagonS算法的改進方案

2.1 起始搜索點的預測

UMHexagonS算法中，起始搜索點的預測包括空間域預測方式和時間域預測方式兩種。空間域預測方式包括運動矢量中值預測、上層塊模式運動矢量預測和原點預測，時間域預測方式包括前幀對應塊運動矢量預測和時間域的鄰近參考幀運動矢量預測。其中的時間域預測會消耗大量的存儲空間，因此為了降低存儲空間，本文的優化方法僅僅使用空間域預測方式，從而簡化了起始點的預測，減少了起始點預測的時間。

2.2 部分搜索模板的改進和搜索模板象限區域分割法

由上述UMHexagonS搜索過程得知，該搜索算法在搜索過程中，搜索的候選點數較多，可以通過一些改進的方法減少搜索點數。本文采用了搜索模板象限區域分割法，根據文獻[4]得知預測運動矢量和最佳運動矢量落入某同一象限的平均概率在95%以上，準確度很高。因此，首先，利用混合時空域起點預測方法，找到起始點的運動矢量方向，由于起點運動矢量方向和最佳運動矢量方向所落入的象限范圍基本一致，所以在后面的搜索階段只需要在一個約定的象限區域內進行搜索，其他四分之三的區域都不用搜索，這樣就可以大大減少搜索點數，節省搜索時間。

如圖2所示，整個宏塊可劃分為4個象限區域，分別是A1、A2、A3、A4，如果將當前宏塊運動估計的起始點的最佳預測運動矢量記為MVpred(pred_x，pred_y)，則通過該運動向量計算得出：

圖2 預測矢量所屬4個區域

由式（1），可判斷得出預測運動矢量方向落入在哪個象限內：

同時，根據運動矢量中心偏移特性[5]，在螺旋搜索模板中，靠近中心的搜索候選點的匹配點的概率更高，針對這點，下面對螺旋搜索模板進行了適當的改進。提出了一種菱-八邊形搜索模板，該模板首先是進行小菱形搜索，再進行菱形搜索，最后進行小八邊形搜索，如圖3所示。

圖3 菱-八邊形搜索模板

由圖3可知，采用改進后的菱-八邊形搜索模板比原螺旋搜索模板減少了4個搜索點，而靠近中心的候選點不變，只是減少了遠離中心點的邊緣點，既符合運動矢量中心偏移的特性，又減少了搜索點數，同時節省了搜索時間。

而且，多層次六邊形搜索模板搜索點數較多，搜索的范圍較大，由于運動矢量中心偏移特性，在多層次六邊形搜索模板中，最外層六邊形候選點作為匹配點的概率極小。因此，下面提出一種多層次八邊形搜索模板，可以大大減少搜索點數，如圖4所示。

圖4 多層次八邊形搜索模板

由圖4可知，多層次八邊形搜索模板只需要搜索36個候選點，而原多層次六邊形搜索模板需要搜索64個候選點，因此，大大節省了搜索點數。同時，與圖1（c）比較后可知，多層次八邊形搜索模板不需要搜索邊緣的候選點，搜索的層次數更少，同時搜索的范圍更加靠近中心點，因此，不僅增強了搜索的精度，而且進一步節省了搜索時間。

由圖2給出的4種運動矢量所屬象限的不同劃分，以及式（1）和式（2）的判斷，再結合改進后的菱-八邊形搜索模板和多層次八邊形搜索模板，可以得出在原UMHexagonS算法改進后，對非對稱十字型搜索模板、菱-八邊形搜索模板、多層次八邊形搜索模板、六邊形模板搜索和菱形模板搜索進行了象限區域的劃分，如圖5所示。

圖5 改進后的搜索模板

以16×16搜索范圍為例，只搜索一個象限區域，從圖5（a）可以看出，原搜索模板需要搜索24個候選點，采用象限劃分后，搜索點數只有原搜索算法的一半，將該改進后的搜索方法記為M1；如圖5（b），原算法需要搜索25個候選點，改進后的螺旋搜索模板需要搜索21個候選點，再同時采用象限劃分后只需要搜索8個點，將該改進后的搜索方法記為M2；如圖5（c），原多層次六邊形搜索模板需要搜索64個候選點，改進后的多層次八邊形搜索模板只需要搜索36個點，再同時采用象限劃分后只需要搜索12個候選點，將該改進后的搜索方法記為M3；如圖5（d），原搜索模板需要搜索6個候選點，改進后只需要搜索2個點，將該改進后的搜索方法記為M4；如圖5（e），原搜索模板需要搜索4個候選點，改進后只需要搜索2個點，將該改進后的搜索方法記為M5。因此，采用改進后的搜索模板以及象限區域劃分策略之后，與原算法相比較，優化及改進后，在整個搜索過程中總共減少了一半以上的搜索點數，極大地節省了搜索時間。

2.3 搜索提前終止策略

提前終止搜索策略的方法是設定閾值，在保證率失真的情況下，選擇合理的閾值T可以較好地提前終止搜索，減少不必要的搜索點數，節省搜索時間。在H.264標準中，采用塊匹配準則方式計算搜索點的最小絕對差值和（Sum of Absolute Differences，SAD），如果SAD值小于或等于設定的閾值T，則提前結束搜索。在基于塊匹配算法的運動估計中，宏塊分為16×16，16×8，8×16，8×8，8×4，4×8，4×4共 7種塊模式，各種塊模式的SAD值各有不同，為了減少計算量，可以根據不同塊模式的需求，設定7個不同的閾值。閾值T定義如下式：

其中，數組Bsize為當前宏塊尺寸，blocktype為塊模式1（16×16）到塊模式7（4×4）。α[blocktype]通過多次實驗按其概率分布規律得到：α[1]=0.30，α[2]=0.30，α[3]=0.33，α[4]=0.27，α[5]=0.13，α[6]=0.13，α[7]=0.44。

2.4 算法改進的具體流程

（1）進行簡化了的起始搜索點預測，判斷該起始點SAD值是否大于閾值T（2.3節中已定義），如果小于閾值T，則轉入步驟（7）；否則，轉入步驟（2）。

（2）通過式（1）和式（2）計算后得到預測運動矢量方向落入所屬的象限區域，采用M1的方法進行搜索，同時判斷各候選點SAD值是否大于閾值T，如果小于閾值T，則轉入步驟（7）；否則，轉入步驟（3）。

（3）以上一步最小候選點為中心，在預測的象限區域內采用M2的方法進行搜索，同時判斷各候選點SAD值是否大于閾值T，如果小于閾值T，則轉入步驟（7）；否則，轉入步驟（4）。

（4）在預測的象限區域內采用M3的方法進行搜索，同時判斷各候選點SAD值是否大于閾值T，如果小于閾值T，則轉入步驟（7）；否則，轉入步驟（5）。

（5）以上一步最小候選點為中心，在預測的象限區域內采用M4的方法進行反復搜索，同時判斷各候選點SAD值是否大于閾值T，如果小于閾值T，則轉入步驟（7）；否則，轉入步驟（6）。

（6）在預測的象限區域內采，用M5的方法進行反復搜索。

（7）得到最佳匹配點，結束搜索。

算法改進后具體流程，如圖6所示。

圖6 UMHexagonS算法改進流程圖

表1 文獻[7]的算法改進與本文算法改進的實驗數據對比

表2 仿真實驗的差值及變化率對比

3 仿真實驗結果與分析

3.1 仿真實驗平臺與配置

為了測試改進后的算法，本文在VC++6.0的平臺上，將H.264標準測試JM10.1[6]集成到平臺上進行了算法改進后的測試。實驗所用PC機配置：Windows XP，CPU 1.68 GHz，內存為1 GB。選用的測試序列集為5個176×144的QCIF格式序列，所有序列都為Yuv4：2：0。采用Baseline編碼，編碼器主要參數配置：FramesToBeEncoded=100，FrameRate=30.0，UseHadamard=1，SearchRange=16，NumberReferenceFrames=5，其他參數為默認值。

3.2 實驗結果與分析

本仿真實驗主要針對文獻[7]中UMHexagonS算法的改進進行以下對照與比較。

文獻[7]的算法改進與本文采用改進方法后的仿真實驗數據對比，如表1所示。

文獻[7]的算法改進與本文采用改進方法后的仿真實驗數據的差值及變化率對比，如表2所示。

從表2的實驗數據中可以發現，本文改進后的算法與文獻[7]改進算法相比，只有Foreman序列的SNRY值降低了，其他SNRY值都沒有改變，同時在碼率變化不太明顯的情況下，運動估計時間（MET）卻減少了4%～26%。其中，對于運動比較緩慢的序列News而言，運動估計時間節省了4.66%，對于中度運動的序列Foreman而言，運動估計時間節省了10.27%，對于劇烈運動的序列Highway、Coastguard和Mobile而言，運動估計時間分別節省了14.82%、23.17%和26.62%。從實驗結果可以看出，改進后的算法相對于原算法，搜索速度隨運動序列劇烈強度的增加而提高。因此，本文算法在保證編碼性能的基礎上，可以大幅地減少原算法的運動估計時間，整體上提高編碼效率。

4 結束語

本文對運動估計UMHexagonS算法進行了分析和研究，針對其不足之處提出了一些改進。針對原搜索模板提出了菱-八邊形搜索模板和多層次八邊形搜索模板，同時引入預測運動矢量方向性判別搜索區域從而降低搜索點數，以及設定閾值提前終止搜索。實驗結果表明，本文算法在PSNR值和碼率與原算法相近的情況下，運動估計時間得以大幅減少。因此，本文的改進算法與原算法相比，具有明顯的優勢。

[1]Wiegand T，Sulivan G J，Luthra A.JVT of ISO/IEC JTC1/SC29/ WG11 and ITU-T SG16/Q.6，Doc.JVT-G050r1 Draft ITU-T recommendationH.264andfinaldraftinternationalstandard 14496-10 AVC[S].Geneva，Switzerland，2003-05.

[2]Yang P，He Y，Yang S.An unsymmetrical-cross multi-resolution motionsearchaigorithmforMpeg4-Avcm.264coding[C]// Proceedings of the IEEE International Conference on Multimedia and Expo（ICME），2004：531-534.

[3]Yang P，Wu H，Yang S.Fast motion estimation algorithm for H.264[J].Journal of Tsinghua University，2005，45（4）：527-531.

[4]李桂菊，劉剛，梁靜秋.H.264快速運動估計算法的改進[J].光學精密工程，2010，18（11）：2489-2496.

[5]李會宗，陳雷霆，盧光輝，等.基于起點預測的不連續十字形快速搜索算法[J].計算機應用研究，2008，25（10）：2929-2931.

[6]JVT reference software of H.264[EB/OL].[2011-10].http：//iphome.hhi.de/suehring/tml/.

[7]盧文濤，樊濱溫.基于H.264運動估計的空間預測算法[J].計算機工程，2010，36（7）：236-238.

LIN Yong,YANG Yingen,YANG Liu,XU Dajie

College of Computer Information Engineering,Jiangxi Normal University,Nanchang 330022,China

As the UMHexagonS algorithm exists problems such as excessive searching points,complicated computation and consuming time etc.,this paper puts forward some improving plans.On the one hand,to some of the searching template,a diamondoctagon searching template and a multi-level-octagon searching template are proposed;on the other hand,in the whole searching process,when using quadrant regional segmentation method,searching points and searching time can be effectively reduced. The experimental results show that the improved algorithm in the situation of guaranteed Peak Signal to Noise Ratio（PSNR）and bit rate,compared to the original algorithm,saves the 4%～26%of the motion estimation of time.

motion estimation;UMHexagonS algorithm;octagon;quadrant segmentation;threshold

針對UMHexagonS算法搜索點數較多，運算量較大以及耗時等問題，提出了改進方案。一方面，對部分搜索模板提出了一種菱-八邊形搜索模板和一種多層次八邊形搜索模板；另一方面，在整個搜索過程中，結合象限區域分割法，可以有效減少搜索點數和搜索時間。實驗結果表明，改進后的算法在保證較好的PSNR和碼率情況下，比原算法減少了4%～26%的運動估計時間。

運動估計；UMHexagonS算法；八邊形；區域分割；閾值

A

TN919.81

10.3778/j.issn.1002-8331.1111-0071

LIN Yong,YANG Yingen,YANG Liu,et al.Research and improvement on UMHexagonS for motion estimation.Computer Engineering and Applications,2013,49（13）：207-210.

林永（1984—），男，碩士研究生，主要研究領域為視頻壓縮編碼技術；楊印根（1962—），男，教授，江西師范大學計算機信息工程學院副院長，主要研究領域為計算機網絡；楊柳（1988—），女，碩士研究生，主要研究領域為計算機網絡；許大姐（1987—），女，碩士研究生，主要研究領域為自然語言處理。E-mail：linyong516@126.com

2011-11-07

2012-02-29

1002-8331（2013）13-0207-04

CNKI出版日期：2012-04-25http://www.cnki.net/kcms/detail/11.2127.TP.20120425.1722.084.html