基于塊運動的閾值判斷自適應運動估計算法

魏文振， 昂志敏

（合肥工業(yè)大學 計算機與信息學院， 安徽 合肥 230009）

運動估計是H.264 標準中一項關鍵核心技術，同時也是所有視頻編碼標準中的一項核心技術。 采用運動估計和運動補償技術可以消除視頻信號的時間冗余并提高編碼效率。 從編碼器整個計算過程來看， 運動估計占整個系統(tǒng)的計算量60%～80%。 因為在壓縮過程中，運動估計能夠很好地去除視頻圖像中存在的時間冗余、空間冗余，實現(xiàn)高效的編碼效率。同時運動估計也是制約視頻圖像編碼效率的關鍵原因之一。綜上所述，改善運動估計的效率，使運動估計算法的搜索過程更快速、更高效具有重要的意義。

全搜索算法（FS）是一種搜索策略最全面的算法，找到的匹配點即全局最優(yōu)點，但其計算量較大，限制了實時壓縮的應用。 為了減少計算量，研究人員提出了很多基于固定模板的快速搜索算法，如三步搜索法（TSS）[1]、四步搜索法（FSS）[2]、基于塊的梯度下降搜索法（BBGDS）[3]、菱形搜索法（DS）[4]和六邊形搜索法（HS）[5]等。上述算法雖然提高了搜索速度，但是搜索容易陷入局部最優(yōu)，得不到最優(yōu)的運動矢量。 近些年又出現(xiàn)了一些基于預測矢量集的快速搜索算法，如非對稱十字型多層次六邊形搜索算法（UMHexagonS）[6]等。 這類算法利用運動矢量場的時相關性產生預測矢量集，通過搜索預測矢量位置產生搜索區(qū)域的中心位置，并根據(jù)運動類型自適應選擇搜索模板，加入了提前終止搜素的判斷策略，進一步提高了搜索速度。

在研究運動估計的過程中，利用提前終止策略來加速視頻編碼的編碼效率，已經成為研究的熱門問題。 塊匹配運動估計算法由于簡單、高效、開銷小、易于實現(xiàn)等優(yōu)點而被大多數(shù)視頻編碼標準所采用，該算法匹配的準則有3 種，即平均均方誤差（MSE）、平均絕對差（MAD）和歸一化函數(shù)（NC—CF）[7]。 為了降低計算復雜度，通常用絕對誤差和（SAD）來代替MAD。

1 UMHexagonS 算法的基本流程及分析

UMHexagonS 算法即非對稱十字形多層次六邊形格點搜索算法，是H.264 標準所采納的運動估計算法之一。 同全搜索算法相比，該算法在保持較好率失真性能的前提下，可以節(jié)約90%左右的計算量。 為了降低計算復雜度，在運動估計過程中，通常用絕對誤差和（SAD）來代替MAD，SAD 的定義如下：

UMHexagonS 算法的基本步驟如下：

Step1 起始搜索點預測。 依次進行中值預測、原點預測、上層預測、對應塊預測、相鄰參考幀預測，接著判斷SAD 值。若其很小，則跳至step6；

Step2 非對稱十字形搜索模板搜索。 此時對SAD 值進行判斷，若其值很小，判斷其為很滿意區(qū)，則跳至step6；若其值較大，判斷為不滿意區(qū)，則跳至step5；否則繼續(xù)下一步；

Step3 利用5*5 正方形模板進行螺旋式搜索；

Step4 利用多層六邊形模板進行搜索；

Step5 利用中六邊形模板進行搜索；

Step6 利用小菱形模板進行搜索，得到最終的運動矢量MV。

通過上述流程可以看出，UMHexagonS 算法在起始搜索點預測的過程中，依次進行五種預測。 這在一定程度上影響了運動估計的搜索時間。 而且算法中用到了正方形模板，非均勻多層六邊形模板和小菱形模板，也可以進行優(yōu)化，以提升運動估計算法的效率。

2 UMHexagonS 算法的優(yōu)化

通過對UMHexagonS 算法的分析和研究， 發(fā)現(xiàn)該算法在搜索效率上依然有可以提高之處，本文將從加入提前中止搜索的判斷策略和在不影響圖像整體質量前提下減少搜索點數(shù)兩方面進行改進，具體改進如下：1）在起始搜索點的預測時加入閾值進行判斷；2）根據(jù)運動劇烈程度的不同對運動類型進行自適應判斷；3）對部分搜索模板進行改進，提高搜索效率。

2.1 起始搜索點預測的閾值判斷

通過引入閾值來提前判斷是否停止搜索，從而更高效的對預測運動矢量MV 進行預測。 引入的閾值定義如下：

式中：m—閾值的自由項；Blocksize—當前編碼尺寸；blocktype—模式1 至模式7 可供選擇；αstop—常數(shù)組（α1=0.30，α2=0.33，α3=0.33，α4=0.27，α5=0.13，α6=0.13，α7=0.44）。

在對預測運動矢量MV 進行預測時， 首先采用中值預測， 得到當前搜索點A。 假設A 點為最佳點min_cost，對min_cost 進行判斷。

若min_cost＜Thred0 時，則停止搜索，得到最終MV；否則依次進行原點預測、uplager 預測、相鄰參考幀預測，接著進行非對稱十字模板搜索。 此時得到的min_cost1 需要同閾值Thred1，Thred2 進行判斷；

若min_cost1＜Thred1 時，則中止搜索；

若TH1＜min_cost1＜Thred2 時， 跳轉至改進型正方形模板繼續(xù)進行搜索；

若min_cost＞Thred2 時，則跳轉至下一步。

2.2 運動類型的自適應判斷

在UMHexagonS 算法中加入對運動類型的自適應判斷，來縮小運動估計過程中的搜索范圍。 視頻通?？梢愿鶕?jù)運動幅度的大小來進行劃分，劃分如下：塊的運動幅度較小的，可看做處于相對靜止的運動狀態(tài)。 其運動矢量通常是以（0，0）為中心向外進行擴散， 發(fā)生的概率隨著遠離中心越來越??；塊的運動幅度中等的，其運動矢量一般出現(xiàn)在距離中心位置較遠的地方，呈環(huán)形分布。 離中心位置越近，出現(xiàn)概率越小；塊的運動幅度較大的， 其運動矢量一般分布在外側范圍，離中心位置較塊運動幅度中等的運動矢量更大。

為了更好的判斷視頻的運動劇烈程度，引入閾值TH[8]。實驗研究表明， 當TH=800 時能夠較好的區(qū)分運動類型。通過cos t[9]與TH 的比較作為依據(jù)。 cos t的定義如下：

其中SAD—絕對誤差和；B—根據(jù)情況不同， 可選4、8、16；γ—平衡碼率與失真度的因子；s—當前編碼的數(shù)據(jù)；c（m）—編碼重建的參考幀數(shù)據(jù)。

2.3 正方形搜索模板的優(yōu)化

原算法采用的是5*5 的搜索模板中，一次螺旋搜索共有25 個搜索點，計算量較大。 通過對不停的的視頻序列的運動向量進行分析后發(fā)現(xiàn)，大約有80%的運動向量預測中心落在5*5 區(qū)域內， 而其中又有70%落在3*3 的區(qū)域內。同時3*3 搜索模板的搜索點數(shù)是5*5 搜索模板的搜索點數(shù)的1/3 左右。 故本文采用3*3 的正方形模板進行搜索，提高搜索效率。

圖1 3*3 正方形模板Fig. 1 3*3 square template

2.4 多層六變形搜索模板的優(yōu)化

根據(jù)搜索模板圓形最優(yōu)理論， 八邊形更符合圓形最優(yōu)理論。故將原算法中多層六邊形模板利用八邊形模板進行代替。八邊形的八個頂點到中心點的距離都是。 雖然在垂直方向和水平方向相比六邊形各多出兩個點， 但是在模板總搜索點數(shù)上卻減少了16 個點，故可有效減少搜索點數(shù)，提高搜索速率。 搜索模板如圖2 所示。

2.5 小菱形搜索模板的優(yōu)化

原算法中采用的小菱形模板搜索時搜索的只是圖2 中小菱形的4 個頂點， 同正方形模板搜索相比， 圖形質量較低。 但是若采用正方形搜索模板勢必將導致搜索的點數(shù)增加?，F(xiàn)在依然采用正方形模板，但通過利用SAD 值之和作為判斷標準的方法來減少搜索點數(shù)，同時圖像質量也會高于小菱形搜索。 將六邊形的相鄰兩個點看成一個小組，如圖3 所示，共A、B、C、D、E、F 六組。在六邊形模板搜索結束前，分別計算每一小組中兩個點的SAD 之和。 若SAD 和最小的是水平方向上的組，即E 組或F 組，則只需搜索圖2 中小正方形模板中的水平方向上的3 個點。 若SAD 和最小的是斜方向上的組， 則只需搜索小正方形模板中最靠近該斜邊的兩個點。 從上述分析可看出，無論采用這兩種搜索方法中的任意一種， 都比利用小菱形模板搜索和正方形模板搜索時所搜索的點數(shù)要少。

圖2 多層八邊形模板Fig. 2 Multilayer octagon template

圖3 改進型正方形模板Fig. 3 Improved square template

3 UMHexagonS 算法改進后的流程

3.1 改進算法基本流程描述

Step1 首先采用中值預測，得到當前搜索點A，假設A 點為最佳點min_cost。 若min_cost＜Thred0 時，則停止搜索，得到最終MV；否則依次進行原點預測、uplager 預測、相鄰參考幀預測，接著進行非對稱十字模板搜索[10]。 繼續(xù)引入閾值Thred1，Thred2 進行判斷。 若min_cost1＜Thred1 時，則中止搜索； 若Thred1 ＜min_cost1 ＜Thred2 時， 跳 轉 至STEP6；若min_cost＞Thred2 時，則跳轉至STEP2；

Step2 對視頻運動劇烈程度進行自適應判斷。 若時，跳至STEP 3；若時，直接跳至STEP 4 繼續(xù)進行搜索；

Step3 采用3*3 正方形搜索模板；

Step4 多層八邊形模板進行搜索；

Step5 中六邊形模板進行搜索；

Step6 改進型正方形模板搜索。

3.2 改進后算法的整體流程圖

圖4 改進后UMHexagonS 算法流程Fig. 4 Improved UMHexagonS algorithm process

4 實驗結果及分析

本文基于JM18.4 平臺對上述改進方法進行實現(xiàn)， 選取QCIF 的6 個 標 準 視 頻 測 試 序 列：akiyo_qcif、mobile_qcif、coastguard_qcif、news_qcif、bus_qcif、football_qcif 進 行 仿 真 測試。 其中akiyo_qcif、news_qcif 的運動較為緩慢，可看做運動幅度小的運動序列；mobile_qcif、bus_qcif 可看做是運動幅度中等的運動序列；coastguard_qcif、football_qcif 可看做是運動幅度較大的運動序列。 本文在編碼幀數(shù)為60，參考幀數(shù)為5，幀率為30，量化參數(shù)QP 為28 的參數(shù)設定情況下進行測試，并將改進后的算法同UMHexagonS 算法在運動估計時間和亮度信號峰值信噪比兩方面進行比較。 通過表1 可以看出，改進后的算法較原算法在運動估計時間都有提升，平均節(jié)省時間比為20.15%，尤其對運動劇烈的視頻序列效果更佳。 通過表2 可以看出，改進后算法同原算法相比，亮度信號峰值信噪比基本持平[11]，說明峰值的變化范圍很小。 由此可見，本文對UMHexagonS 算法進行改進后，在保持原算法率失真性能的前提下，減少了運動估計的編碼時間，達到提高工作效率的目的。

表1 UMHexagonS 算法與改進算法的運動估計時間比較Tab. 1 Time comparison of motion estimation between UMHexagonS algorithm and the improved UMHexagonS algorithm

表2 UMHexagonS 算法與改進算法的亮度信號峰值信噪比（PSNR）比較Tab. 2 PSNR comparison of motion estimation between UMHexagonS algorithm and the improved UMHexagonS algorithm

5 結束語

本文通過對UMHexagonS 算法的研究，首先在運動估計的起始搜索點預測階段增加閾值來提前判斷是否中止搜索。若起始點一開始就是最優(yōu)點，通過閾值判斷策略可以大大節(jié)省搜索時間。 然后在算法的過程中，通過加入對運動類型的自適應判斷來縮小搜索范圍，同時優(yōu)化搜索各階段的搜索模板，最終達到了提高運動估計效率的目的。 從實驗結果可以看出， 在保持PSNR 基本不變的前提下， 搜索時間提高了20.15%。

[1] 王艷營，馮進玫. 基于EPZS 的H. 264 運動估計算法的改進[J]. 計算機技術與發(fā)展，2012，22（1）:100－107.

[2] Po L M，Ma W C. A novel four-step search algorithm for fast block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology，1996，6（3）:313-317.

[3] Liu L K， Feig E. A block-based gradient descent search algorithm for block motion estimation in video coding[J]. IEEE Transactions on Circuits and Systems for Video Technology，1996，6（4）:419-422.

[4] Zhu S， Ma K K. A new diamond search algorithm for fast block-matching motion estimation[J]. Image Processing，2000，9（2）:287-290.

[5] Zhu C，Lin X，Chau L P. Hexagon-based search pattern for fast block motion estimation [J]. Circuits and Systems for Video Technology，2002，12（5）:349-355.

[6] Chen Z，Zhou P，He Y. Hybrid unsymmetrical-cross multihexagon-grid search strategy for integer pel motion estimation in H.264[C]//Proc. Picture Coding Symposium，2003:17-22.

[7] Wang Q，Zhuo L，Zhang J，et al. Frame layer rate control method for stereoscopic video coding based on a novel ratedistortion model [C]//The Era of Interactive Media. Springer New York，2013:205-216.

[8] 朱小龍，羅星，陳祖爵. 帶有模式選擇的改進的方向性菱形搜索算法[J]. 計算機應用研究，2010，27（1）:393-395.

[9] Kim C G，Lee I J，Kim S D. Reduced uneven multi-hexagongrid search for fast integer pel motion estimation in H.264/AVC [C]//Proc. Image Analysis and Recognition. Berlin Heidelberg: Springer Verlag，2007，4633:708-714.

[10]黃婷，黃偉. 基于不同算法求解子問題的Benders分解法在無功規(guī)劃中的應用[J]. 陜西電力，2013（3）:23-26.

[11]施先旺，王鵬武. 發(fā)動機工況實時調節(jié)軟件設計[J]. 火箭推進，2012（5）:70-76.