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

江西師范大學(xué) 計(jì)算機(jī)信息工程學(xué)院，南昌 330022

運(yùn)動(dòng)估計(jì)中UMHexagonS的研究與改進(jìn)

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

江西師范大學(xué) 計(jì)算機(jī)信息工程學(xué)院，南昌 330022

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

本文針對(duì)UMHexagonS算法的不足，在原算法基礎(chǔ)上，加入提前終止策略和搜索模板象限區(qū)域分割法，并且對(duì)UMHexagonS的螺旋搜索模板和多層次六邊形搜索模板進(jìn)行了改進(jìn)，減少了許多不必要的搜索點(diǎn)數(shù)，在保證較好的率失真性能的情況下，有效地節(jié)省了運(yùn)動(dòng)估計(jì)時(shí)間。

1 UMHexagonS算法介紹

（1）起始搜索點(diǎn)的預(yù)測(cè)，利用較高精度的起始點(diǎn)預(yù)測(cè)，計(jì)算得出預(yù)測(cè)運(yùn)動(dòng)矢量MVpred。

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

（3）螺旋模板搜索，以上一步搜索的匹配點(diǎn)作為搜索中心，搜索坐標(biāo)[-2，2]正方形區(qū)域內(nèi)的25個(gè)候選點(diǎn)，類似于全局搜索，如圖1（b）所示。

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

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

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

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

2 UMHexagonS算法的改進(jìn)方案

2.1 起始搜索點(diǎn)的預(yù)測(cè)

UMHexagonS算法中，起始搜索點(diǎn)的預(yù)測(cè)包括空間域預(yù)測(cè)方式和時(shí)間域預(yù)測(cè)方式兩種?？臻g域預(yù)測(cè)方式包括運(yùn)動(dòng)矢量中值預(yù)測(cè)、上層塊模式運(yùn)動(dòng)矢量預(yù)測(cè)和原點(diǎn)預(yù)測(cè)，時(shí)間域預(yù)測(cè)方式包括前幀對(duì)應(yīng)塊運(yùn)動(dòng)矢量預(yù)測(cè)和時(shí)間域的鄰近參考幀運(yùn)動(dòng)矢量預(yù)測(cè)。其中的時(shí)間域預(yù)測(cè)會(huì)消耗大量的存儲(chǔ)空間，因此為了降低存儲(chǔ)空間，本文的優(yōu)化方法僅僅使用空間域預(yù)測(cè)方式，從而簡(jiǎn)化了起始點(diǎn)的預(yù)測(cè)，減少了起始點(diǎn)預(yù)測(cè)的時(shí)間。

2.2 部分搜索模板的改進(jìn)和搜索模板象限區(qū)域分割法

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

如圖2所示，整個(gè)宏塊可劃分為4個(gè)象限區(qū)域，分別是A1、A2、A3、A4，如果將當(dāng)前宏塊運(yùn)動(dòng)估計(jì)的起始點(diǎn)的最佳預(yù)測(cè)運(yùn)動(dòng)矢量記為MVpred(pred_x，pred_y)，則通過(guò)該運(yùn)動(dòng)向量計(jì)算得出：

圖2 預(yù)測(cè)矢量所屬4個(gè)區(qū)域

由式（1），可判斷得出預(yù)測(cè)運(yùn)動(dòng)矢量方向落入在哪個(gè)象限內(nèi)：

同時(shí)，根據(jù)運(yùn)動(dòng)矢量中心偏移特性[5]，在螺旋搜索模板中，靠近中心的搜索候選點(diǎn)的匹配點(diǎn)的概率更高，針對(duì)這點(diǎn)，下面對(duì)螺旋搜索模板進(jìn)行了適當(dāng)?shù)母倪M(jìn)。提出了一種菱-八邊形搜索模板，該模板首先是進(jìn)行小菱形搜索，再進(jìn)行菱形搜索，最后進(jìn)行小八邊形搜索，如圖3所示。

圖3 菱-八邊形搜索模板

由圖3可知，采用改進(jìn)后的菱-八邊形搜索模板比原螺旋搜索模板減少了4個(gè)搜索點(diǎn)，而靠近中心的候選點(diǎn)不變，只是減少了遠(yuǎn)離中心點(diǎn)的邊緣點(diǎn)，既符合運(yùn)動(dòng)矢量中心偏移的特性，又減少了搜索點(diǎn)數(shù)，同時(shí)節(jié)省了搜索時(shí)間。

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

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

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

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

圖5 改進(jìn)后的搜索模板

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

2.3 搜索提前終止策略

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

其中，數(shù)組Bsize為當(dāng)前宏塊尺寸，blocktype為塊模式1（16×16）到塊模式7（4×4）。α[blocktype]通過(guò)多次實(shí)驗(yàn)按其概率分布規(guī)律得到：α[1]=0.30，α[2]=0.30，α[3]=0.33，α[4]=0.27，α[5]=0.13，α[6]=0.13，α[7]=0.44。

2.4 算法改進(jìn)的具體流程

（1）進(jìn)行簡(jiǎn)化了的起始搜索點(diǎn)預(yù)測(cè)，判斷該起始點(diǎn)SAD值是否大于閾值T（2.3節(jié)中已定義），如果小于閾值T，則轉(zhuǎn)入步驟（7）；否則，轉(zhuǎn)入步驟（2）。

（2）通過(guò)式（1）和式（2）計(jì)算后得到預(yù)測(cè)運(yùn)動(dòng)矢量方向落入所屬的象限區(qū)域，采用M1的方法進(jìn)行搜索，同時(shí)判斷各候選點(diǎn)SAD值是否大于閾值T，如果小于閾值T，則轉(zhuǎn)入步驟（7）；否則，轉(zhuǎn)入步驟（3）。

（3）以上一步最小候選點(diǎn)為中心，在預(yù)測(cè)的象限區(qū)域內(nèi)采用M2的方法進(jìn)行搜索，同時(shí)判斷各候選點(diǎn)SAD值是否大于閾值T，如果小于閾值T，則轉(zhuǎn)入步驟（7）；否則，轉(zhuǎn)入步驟（4）。

（4）在預(yù)測(cè)的象限區(qū)域內(nèi)采用M3的方法進(jìn)行搜索，同時(shí)判斷各候選點(diǎn)SAD值是否大于閾值T，如果小于閾值T，則轉(zhuǎn)入步驟（7）；否則，轉(zhuǎn)入步驟（5）。

（5）以上一步最小候選點(diǎn)為中心，在預(yù)測(cè)的象限區(qū)域內(nèi)采用M4的方法進(jìn)行反復(fù)搜索，同時(shí)判斷各候選點(diǎn)SAD值是否大于閾值T，如果小于閾值T，則轉(zhuǎn)入步驟（7）；否則，轉(zhuǎn)入步驟（6）。

（6）在預(yù)測(cè)的象限區(qū)域內(nèi)采，用M5的方法進(jìn)行反復(fù)搜索。

（7）得到最佳匹配點(diǎn)，結(jié)束搜索。

算法改進(jìn)后具體流程，如圖6所示。

圖6 UMHexagonS算法改進(jìn)流程圖

表1 文獻(xiàn)[7]的算法改進(jìn)與本文算法改進(jìn)的實(shí)驗(yàn)數(shù)據(jù)對(duì)比

表2 仿真實(shí)驗(yàn)的差值及變化率對(duì)比

3 仿真實(shí)驗(yàn)結(jié)果與分析

3.1 仿真實(shí)驗(yàn)平臺(tái)與配置

為了測(cè)試改進(jìn)后的算法，本文在VC++6.0的平臺(tái)上，將H.264標(biāo)準(zhǔn)測(cè)試JM10.1[6]集成到平臺(tái)上進(jìn)行了算法改進(jìn)后的測(cè)試。實(shí)驗(yàn)所用PC機(jī)配置：Windows XP，CPU 1.68 GHz，內(nèi)存為1 GB。選用的測(cè)試序列集為5個(gè)176×144的QCIF格式序列，所有序列都為Yuv4：2：0。采用Baseline編碼，編碼器主要參數(shù)配置：FramesToBeEncoded=100，F(xiàn)rameRate=30.0，UseHadamard=1，SearchRange=16，NumberReferenceFrames=5，其他參數(shù)為默認(rèn)值。

3.2 實(shí)驗(yàn)結(jié)果與分析

本仿真實(shí)驗(yàn)主要針對(duì)文獻(xiàn)[7]中UMHexagonS算法的改進(jìn)進(jìn)行以下對(duì)照與比較。

文獻(xiàn)[7]的算法改進(jìn)與本文采用改進(jìn)方法后的仿真實(shí)驗(yàn)數(shù)據(jù)對(duì)比，如表1所示。

文獻(xiàn)[7]的算法改進(jìn)與本文采用改進(jìn)方法后的仿真實(shí)驗(yàn)數(shù)據(jù)的差值及變化率對(duì)比，如表2所示。

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

4 結(jié)束語(yǔ)

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

[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快速運(yùn)動(dòng)估計(jì)算法的改進(jìn)[J].光學(xué)精密工程，2010，18（11）：2489-2496.

[5]李會(huì)宗，陳雷霆，盧光輝，等.基于起點(diǎn)預(yù)測(cè)的不連續(xù)十字形快速搜索算法[J].計(jì)算機(jī)應(yīng)用研究，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運(yùn)動(dòng)估計(jì)的空間預(yù)測(cè)算法[J].計(jì)算機(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

針對(duì)UMHexagonS算法搜索點(diǎn)數(shù)較多，運(yùn)算量較大以及耗時(shí)等問(wèn)題，提出了改進(jìn)方案。一方面，對(duì)部分搜索模板提出了一種菱-八邊形搜索模板和一種多層次八邊形搜索模板；另一方面，在整個(gè)搜索過(guò)程中，結(jié)合象限區(qū)域分割法，可以有效減少搜索點(diǎn)數(shù)和搜索時(shí)間。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法在保證較好的PSNR和碼率情況下，比原算法減少了4%～26%的運(yùn)動(dòng)估計(jì)時(shí)間。

運(yùn)動(dòng)估計(jì)；UMHexagonS算法；八邊形；區(qū)域分割；閾值

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—），男，碩士研究生，主要研究領(lǐng)域?yàn)橐曨l壓縮編碼技術(shù)；楊印根（1962—），男，教授，江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院副院長(zhǎng)，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)；楊柳（1988—），女，碩士研究生，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)；許大姐（1987—），女，碩士研究生，主要研究領(lǐng)域?yàn)樽匀徽Z(yǔ)言處理。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