賀艷春，林其偉

（華僑大學(xué) 信息科學(xué)與工程學(xué)院，福建 廈門 361021）

運(yùn)動估計(jì)中的塊匹配算法因運(yùn)算簡單、容易實(shí)現(xiàn)而成為目前運(yùn)動估計(jì)的主流。其中的全搜索算法（FS），因其窮盡搜索每個像素點(diǎn)，搜索精度最高，但計(jì)算太復(fù)雜，不能滿足實(shí)時性要求；而三步法（TSS）、四步法（FSS）以及交叉搜索法（CSS）等，相對FS，減少了搜索點(diǎn)數(shù)，滿足實(shí)時性要求，但不利于小的運(yùn)動塊的搜索；新三步法（NTSS）、 六邊形法 （HEX）、 鉆石法 （DS）、 新四步法（NFSS）等，雖然提高了運(yùn)動估計(jì)的速度，解決了早期算法不利于小運(yùn)動塊搜索的問題，但易陷入局部最優(yōu)點(diǎn)，且不能很好地處理圖像的運(yùn)動類型[1]。針對這些問題，CHEN Z B等[2]人提出了UMHexagonS算法，它是一種混合型搜索算法，綜合了非對稱十字形法、六邊形法、菱形法等，相對 FS，其均峰值信噪比（PSNR）保持基本不變，而運(yùn)動估計(jì)時間減少了近90%，是目前運(yùn)動估計(jì)搜索效率最高的快速搜索算法，己被JVT正式采納。

1 UMHexagonS算法簡介

UMHexagonS算法的搜索路徑如圖 1[3]所示，它主要分4步進(jìn)行搜索：

（1）初始搜索點(diǎn)預(yù)測。包括中值預(yù)測、上層預(yù)測、前幀預(yù)測以及鄰近參考幀預(yù)測，得到最佳的初始搜索點(diǎn)。

（2）以步驟（1）得到的最佳初始搜索點(diǎn)為中心，進(jìn)行非對稱的十字形搜索，取絕對差值和（SAD值）最小的點(diǎn)為當(dāng)前最佳匹配點(diǎn)。其中水平方向的搜索范圍為窗口寬度，垂直方向的搜索范圍為窗口寬度的一半，如圖1的step2所示。

（3）以步驟（2）得到的最佳匹配點(diǎn)為搜索中心，進(jìn)行5×5共25點(diǎn)的正方形螺旋搜索，如圖 1的 step3-1所示。接著進(jìn)行多層六邊形格點(diǎn)搜索，取最小SAD值所對應(yīng)的點(diǎn)為最佳匹配點(diǎn)，如圖1的step3-2所示。

（4）該步驟分兩步進(jìn)行：①以步驟（3）獲得的最佳匹配點(diǎn)為搜索中心，進(jìn)行擴(kuò)展的六邊形搜索。若當(dāng)前最小SAD值點(diǎn)位于六邊形的中心，則轉(zhuǎn)到 b；否則返回 a繼續(xù)進(jìn)行六邊形搜索，直到最小SAD值點(diǎn)位于六邊形的中心，如圖1的step4-1所示。②以步驟（3）的中心點(diǎn)為搜索中心，進(jìn)行小菱形搜索，直到最小SAD值點(diǎn)位于小菱形的中心時，停止搜索，如圖1的step4-2所示。

雖然UMHexagonS算法具有很高的編碼效率，但仍存在兩種不足：

（1）參考文獻(xiàn)[4]中指出，在如圖 2所示的 H.264的7種幀間預(yù)測模式中，有30.71%～98.03%的預(yù)測塊的運(yùn)動矢量全為0。若能在UMHexagonS算法進(jìn)行搜索之前就判決出這些零運(yùn)動矢量，就可以提前退出搜索，減少搜索時間。

（2）候選搜索塊的運(yùn)動劇烈程度不同，其運(yùn)動矢量的分布也不同。UMHexagonS算法對所有的候選搜索塊都是進(jìn)行4層16點(diǎn)的六邊形搜索，沒有考慮到候選搜索塊的運(yùn)動劇烈程度的不同，因此搜索存在冗余。

2 基于UMHexagonS算法的改進(jìn)

（1）針對UMHexagonS算法的第一種不足，提出了零運(yùn)動矢量提前判決的方法。

在進(jìn)行初始搜索點(diǎn)預(yù)測時，最先進(jìn)行中值預(yù)測，且所有的模板都可以使用中值預(yù)測，因此，可以判斷中值預(yù)測得到的最佳匹配點(diǎn)mv（best_x，best_y）的 SAD值是否小于給定的閾值，若小于，則判決出該塊的運(yùn)動矢量為0。

定義SAD值為：

式中，s、c（MV）分別為編碼的原始數(shù)據(jù)和編碼重建的參考幀數(shù)據(jù)，MV為預(yù)測運(yùn)動矢量。

本文定義點(diǎn) mv（best_x，best_y）處的 SAD值滿足式（2）時，則判定其運(yùn)動矢量為0。

式中，Thresh[blocktype]是通過JM10.1的程序調(diào)試獲得的經(jīng)驗(yàn)閾值，表示7種幀間預(yù)測模式，取值為1，…，7。

（2）針對UMHexagonS算法的第二種不足，提出了自適應(yīng)選擇模板的方法。

[5]中指出，運(yùn)動劇烈程度不同的塊其運(yùn)動矢量的分布也不同：若塊的運(yùn)動幅度較小，其運(yùn)動矢量通常分布在離搜索中心較近的周圍；若塊的運(yùn)動幅度中等，其運(yùn)動矢量通常分布在離搜索中心較遠(yuǎn)的周圍；若塊的運(yùn)動幅度很大，其運(yùn)動矢量通常分布在遠(yuǎn)離搜索中心的周圍。

因此，在UMHexagonS算法中，可通過判斷塊的運(yùn)動劇烈程度，自適應(yīng)地選擇16點(diǎn)的六邊形的搜索層數(shù)。但因?yàn)榘诉呅伪攘呅胃咏鼒A，所以將16點(diǎn)的六邊形格點(diǎn)搜索減少為8點(diǎn)的八邊形格點(diǎn)的搜索，如圖3所示。

本文將當(dāng)前模塊的最小SAD值SADmin與自適應(yīng)的閾值進(jìn)行比較來確定其運(yùn)動劇烈程度：平緩的運(yùn)動、中等的運(yùn)動以及劇烈的運(yùn)動：

式中，pred_SAD為預(yù)測塊的最小 SAD值，β2、β3為自適應(yīng)系數(shù)，分別定義如下：

式中，blocktype取值1，…7，表示7種幀間預(yù)測模式。

因此，自適應(yīng)模板選擇過程如下：

（1）當(dāng)模塊的運(yùn)動為平緩的運(yùn)動時，選擇 5×5小正方形以及2層8點(diǎn)八邊形模板進(jìn)行搜索。

（2）當(dāng)模塊的運(yùn)動為中等的運(yùn)動時，選擇3層的8點(diǎn)八邊形模板進(jìn)行搜索。

（3）當(dāng)模塊的運(yùn)動為劇烈的運(yùn)動時，選擇4層的8點(diǎn)八邊形模板進(jìn)行搜索。

由于非對稱十字型搜索之后，需進(jìn)行5×5的正方形搜索，以得到這一步的最佳匹配點(diǎn)。但是通過上面的分析可知，當(dāng)模塊的運(yùn)動為中等的運(yùn)動或者很劇烈的運(yùn)動時，最佳匹配點(diǎn)在遠(yuǎn)離搜索中心點(diǎn)的周圍，則5×5的搜索就沒有必要了，只在模塊的運(yùn)動為平緩時，進(jìn)行5×5的搜索。參考文獻(xiàn)[6]中，5×5正方形的運(yùn)動矢量分布如圖4所示。

由圖 4可知，5×5的正方形區(qū)域內(nèi)，3×3的小正方形區(qū)域的運(yùn)動矢量分布概率為71.792%，相對5×5的正方形區(qū)域的運(yùn)動矢量的分布概率81.791%只減少了9.999%，而搜索點(diǎn)數(shù)減少了16點(diǎn)。因此，將5×5的正方形區(qū)域搜索改為3×3的小正方形區(qū)域搜索，能夠在基本保證視頻的質(zhì)量的情況下，減少搜索點(diǎn)數(shù)，提高搜索速度。

改進(jìn)后的算法流程圖如圖5所示。

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

本文采用JM10.1模型進(jìn)行測試，分別對運(yùn)動劇烈的coastguard序列、運(yùn)動中等的 foreman序列、運(yùn)動平緩的news序列以及運(yùn)動較復(fù)雜、細(xì)節(jié)較多、水平方向運(yùn)動特征明顯的Football序列進(jìn)行了測試，這些序列都采用QCIF格式。編碼100幀，IPPPP……編碼模式，采用Hardmard變換，CABAC熵編碼，QP取 28，選取 5幀參考幀。比較運(yùn)動估計(jì)時間Me-time和峰值信噪比PSNR值。測試數(shù)據(jù)結(jié)果如表1所示。

表1中，△Me-time表示改進(jìn)的 UMHexagonS算法的運(yùn)動估計(jì)時間減去原UMHexagonS算法的運(yùn)動估計(jì)時間得到的差值與原UMHexagonS算法的運(yùn)動估計(jì)時間的百分比；△PSNR表示改進(jìn)后與改進(jìn)前的UMHexagonS算法的PSNR值的差值；△bit-rate/（kb/s）表示表示改進(jìn)后與改進(jìn)前的UMHexagonS算法的比特率的差值，正號表示增加，負(fù)號表示減少。由表1可知，改進(jìn)后的算法與原算法相比，PSNR值基本保持不變，比特率有所增加，但是在誤差允許的范圍之內(nèi)（±0.2 kb/s）；運(yùn)動估計(jì)所消耗的時

表1 各種算法下的PSNR值和運(yùn)動估計(jì)時間

間減少了10%～25%。達(dá)到了一定的改進(jìn)效果。

本文通過分析UMHexagonS算法的一些不足，提出了零運(yùn)動矢量提前判零、自適應(yīng)選擇水平方向和垂直方向搜索范圍的相應(yīng)的改進(jìn)措施以及自適應(yīng)的選擇搜索模板。這樣的改進(jìn)在保證圖像編碼質(zhì)量基本不變的情況下，減少了運(yùn)動估計(jì)的搜索時間，從而提高了編碼效率。

參考文獻(xiàn)

[1]袁濤.基于 H.264運(yùn)動估計(jì)算法的研究[D].重慶：重慶大學(xué)，2009.

[2]CHEN Z B，ZHOU P， HE Y.Fastintegerpeland fractional pel motion estimation for JVT[C].6th meeting：Awaji，Japan.JVT-F017，2002.

[3]畢厚杰.新一代視頻壓縮編碼標(biāo)準(zhǔn)-H.264/AVC（第二版）[M].北京：人民郵電出版社，2009.

[4]陳桂蘭，劉子堅(jiān).基于H.264的運(yùn)動估計(jì)算法優(yōu)化研究[J].濮陽職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2010，23（2）：150-153.

[5]Xie Lifen，Huang Chunqing.UMHexagonS search algorithm forfastmotion estimation [C].IEEE， 3rd International conference on ICCRD 2011 3rd Intenational Conference on ICCRD，2011，4：483-487.

[6]LAM C H，PO L M，CHEUNG C H.A novel kite-crossdiamond search algorithm for fast block motion estimation[C].Proceeding s of 2004 IEEE International Symposium on Circuits and Systems.Canada： IEEE， 2004：729-732.