基于運動類型與多模板的運動估計算法

潘琢金，張俊祥，羅 振，楊 華

（沈陽航空航天大學 計算機學院，遼寧 沈陽110136）

0 引 言

H.264因其高壓縮率和良好的網絡適應性，已被廣泛應用于視頻監控、數字電視、網絡交互媒體等領域，但其高壓縮率是以高計算復雜度為代價的，不能滿足低端編碼設備和無線傳輸等應用領域。運動估計耗費的時間占整個視頻編碼過程的60%－80%［1］，它的優劣直接影響到編碼的實時性和圖像的重建質量，因此在保證壓縮率和圖像質量的前提下，減少運動估計時間對提高編碼效率至關重要。研究者們在基于塊匹配［2］的基礎上提出了許多快速運動估計算法，這些算法主要通過以下3種方法來降低計算復雜度：第一種是結合運動矢量 （motion vector，MV）的時空相關性來快速預測起始點；第二種是利用統計規律，設定合理的閥值進行靜止塊判定或提前終止檢測［3］；第三種是根據MV 的分布特性［4］，通過設計或改進匹配模板和策略來減少搜索點數。以上方法在一定程度上縮短了運動估計時間，加快了搜索速度。UMHexagonS算法是一種優秀的運動估計算法，其搜索時間比全搜索算法節省了90%［5］，但該算法卻沒有充分考慮視頻序列的運動特征，搜索過程缺乏針對性。本文算法在UMHexagonS基礎上，添加了準靜止塊判定、簡化起始點預測、采用與運動分布相適應的模板和策略進行搜索。該方法有效避免了搜索冗余，縮短了運動估計時間，提高了編碼效率。

1 UMHexagonS算法

UMHexagonS算法結合了三步法、新三步法、四步法等搜索方法的優點［6］，它先采用高精度的起點預測，然后利用混合模板 （如圖1所示）進行全局和局部搜索，并在多處進行提前終止檢測［7］。具體的搜索步驟如下所示。

圖1 UMHexagonS算法

步驟1 起始點預測：首先通過5種［8］高精度的預測方式來獲得候選MV 集合，其次從中選取碼率和失真度代價函數值最小的點作為起始點。然后進行提前終止檢測，如果滿足終止條件，則轉入步驟4，進行擴展六邊形搜索；否則轉入步驟2。

步驟2 非對稱十字交叉搜索：以起始點為搜索中心，按圖1 （a）所示的模板進行搜索，找出最佳匹配點，并進行提前終止檢測，如果滿足終止條件，則轉入步驟4；否則轉入步驟3。

步驟3 非均勻多層次六邊形網格搜索：①以當前最佳匹配點為中心，在5＊5矩形區域內螺旋式搜索，找出最佳匹配點，如圖1 （b）所示。然后進行提前終止檢測，如果滿足終止條件，則轉入步驟4；否則進入下一步。②以當前最佳匹配點為中心，進行擴展的多層次六邊形搜索，如圖1（c）所示。在每次擴展之前先進行提前終止檢測，如果滿足終止條件，則轉入步驟4；否則繼續擴展，直至搜索窗邊界。

步驟4 擴展的六邊形搜索：①六邊形搜索，以當前最佳匹配點為中心，按圖1 （d）所示六邊形模板反復搜索，直至最佳匹配點位于其中心為止。②小菱形搜索，按圖1（e）所示小菱形模板反復搜索，直至最佳匹配點位于其中心為止，輸出MV。

從UMHexagonS算法搜索步驟可以看到，高精度的起點預測可以提高算法的效率。但對一些靜止塊或運動幅度很小的塊，則存在著搜索冗余。不同的視頻序列運動劇烈程度各異，其運動矢量分布也不相同，但UMHexagonS算法并未對其運動塊類型進行分類，均采用了混合模板依次搜索，其搜索缺乏針對性，搜索速度將會受到影響。

2 本文算法

本文借鑒了相關研究人員提出的優秀改進方法［9，10］，在準靜止塊判定、起始點預測、運動類型劃分與多模板搜索這3方面對UMHexagonS算法進行了改進，降低算法的計算復雜度，下面分別從這3方面描述該算法。

2.1 準靜止塊判定

在中小運動視頻序列中存在著大量運動幅度很小或幾乎靜止不動的塊。對于這類塊，其運動矢量主要分布在以零矢量為中心很小的范圍內，若對其進行起始點預測會造成時間上的浪費。因此，在起點預測前，有必要進行準靜止塊的判定。為此，本文采用絕對誤差和［5］（sum absolute difference，SAD）作為準靜止塊的判斷依據，通過設定合理的閥值T1，將零矢量處的SAD 值與T1進行比較。如果SAD小于或等于T1，則當前塊為準靜止塊，表明其偏移位置很小，只需在其周圍進行簡單搜索即可找到最佳匹配點。如果SAD 大于T1，則表明運動矢量產生了較大偏移，需要細化搜索。

2.2 起始點預測

文獻 ［7］中對起始點的5種預測方式的準確度進行了統計，發現中值預測和上層模式預測獲取的MV 準確度最高。為了進一步降低算法的復雜度，并使搜索中心位于最佳匹配點，本算法采用中值預測和上層模式預測方式選取具有最小碼率和失真度代價的點作為起始點。

2.3 運動塊類型劃分與多模板搜索

自然界中物體的運動快慢各異，其運動矢量分布也不相同，因此針對不同的運動類型應該選擇與其運動矢量分布相適應的搜索模板，這樣可以有效減少搜索冗余。在視頻序列中，物體在水平方向和垂直方向的運動占很大比例，并且存在著水平方向比垂直方向要劇烈的特性，為此可選用非對稱十字形模板來提高搜索效率［12］。為了能夠快速的判斷當前塊的運動類型，本文引入一個閥值T2，并與起始點預測中計算得到的最小碼率和失真度代價函數值 （記為cost）比較，來判斷當前塊的運動幅度大小［11］。如果cost小于閥值T2，則當前塊為平緩運動 （包括慢速和中速）塊，否則判定為劇烈 （或快速）運動塊。

本算法中使用到的搜索模板如圖2所示。為了保證算法的搜索精度，采取了如下策略進行搜索：首先以起始點為中心選用十字形模板進行方向性搜索；然后再根據運動類型選擇相應的模板進行細搜索；最后使用小菱形模板（如圖2 （d）所示）進行精細搜索。同時設定終止閥值T3，在十字形搜索和擴展多層次八邊形搜索時，通過與最佳匹配點的SAD 值進行比較判定是否滿足終止條件。若小于T3，則終止當前搜索，轉至小菱形模板搜索。

對于劇烈運動塊，其運動矢量偏離起點較大，UMHexagonS算法的混合搜索模板可以較精確地定位運動矢量，本文在此基礎上進行了改進以簡化原混合模板，采用了非對稱大十字形模板 （如圖2 （a）所示）、擴展多層次八邊形模板 （八邊形更容易捕捉到運動矢量）［12］（如圖2 （b）所示）和六邊形模板 （如圖2 （c）所示）。首先采用非對稱大十字形模板進行偏移方向性搜索；然后利用擴展多層次八邊形模板進行粗步定位，每次擴展前進行提前終止檢測；最后利用六邊形模板進行局部細化搜索。

圖2 搜索模板

對于平緩運動塊，其運動矢量偏離起點不是很大，先選用非對稱小十字形模板 （如圖2 （e）所示）進行初步定位，然后再選用菱形模板（如圖2 （f）所示）進行細化搜索。

2.4 算法描述

通過以上分析，本算法的流程如圖3 所示。具體的算法步驟如下：

步驟1 準靜止塊判斷：計算當前塊零矢量位置的SAD值，若該值小于等于T1，則以 （0，0）點為中心，按菱形模板進行搜索，找到最佳匹配點 （SAD 最小值點）后，轉至步驟7；若大于T1，則轉至步驟2。

步驟2 起始點預測：按照中值預測和上層預測方式搜索出代價函數值cost最小的MV 作為起始點，轉至步驟3。

步驟3 運動塊類型判斷：將起始點的cost值與閥值T2進行比較。如果cost小于等于T2，則判定當前塊為平緩運動塊，轉至步驟4 按平緩運動塊策略搜索；如果cost大于T2，則判定當前塊為劇烈運動塊，轉至步驟5按劇烈運動塊策略搜索。

步驟4 平緩運動塊搜索。

（1）以起始點為中心，按非對稱小十字形模板進行方向性搜索，選取最佳匹配點。然后進行提前終止檢測，如果滿足終止條件，則轉至步驟6；否則轉至步驟4 （2）。

（2）以當前最佳匹配點為中心，按菱形模板進行細化搜索，選取最佳匹配點。如果最佳匹配點在菱形邊上，則轉至步驟6；否則轉至步驟7。

步驟5 劇烈運動塊搜索。

（1）以起始點為中心，按非對稱大十字形模板進行方向性搜索，選取最佳匹配點。然后進行提前終止檢測，如果滿足終止條件，則轉至步驟6；否則轉至步驟5 （2）。

（2）以當前最佳匹配點為中心，按多層次八邊形模板進行搜索，每次擴展前，進行提前終止檢測，如果滿足終止條件，則轉至步驟6；否則判斷是否繼續擴展，直至搜索窗邊界，轉至步驟5 （3）。

（3）以當前最佳匹配點為中心，按六邊形模板反復搜索，直至最優點位于其中心，轉至步驟6。

步驟6 精細搜索，以當前最佳匹配點為中心，按小菱形模板反復搜索，直至最優點位于其中心，轉至步驟7。

步驟7 輸出MV。

圖3 本文算法流程

3 實驗結果和性能分析

為測試本文算法性能，利用參考軟件JM18.6 所提供的編碼框架實現了本文提出的算法。實驗所用的PC硬件配置如下：AMD Athlon 64 X2 DualCore Processor 3800＋1.99GHz，2GB內存。操作系統為Windows XP SP3。實驗中的主要編碼參數如下：檔次為基本檔，編碼幀數為50，幀率為30，量化參數為28，幀類型為IPPP，熵編碼類型為CAVLC，搜索范圍為32，參考幀數為5，其它參數為默認設置。

實驗中選取了具有廣泛代表性的6個標準視頻測試序列：akiyo、news、foreman、mother－daughter、coastguard、mobile。所有測試序列格式為QCIF（176＊144），色度格式為yuv4∶2∶0，其中coastguard、mobile 為大運動序列，foreman、mother－daughter為中等運動序列，akiyo、news為小運動序列。對各個測試序列分別采用了UMHexagonS算法 （UMH）、EPZS算法和本文算法進行了實驗，主要從信噪比（PSNR－Y）、比特率 （BR）和運動估計時間 （MET）3個方面進行了比較。測試結果見表1。從表1中可以發現，本文算法的ME－T 明顯低于UMH 算法，但與EPZS算法相比，在大運動序列中，本文算法的ME－T 高于EPZS算法，而在中小運動序列中，要低于EPZS算法。

表1 實驗結果記錄

表2是本文算法與UMH 算法的性能比較結果。從運動估計時間比較來看，本文算法比UMH 算法縮短約了12%－28% （平均節省了19.31%），有效降低了計算復雜度。其中，對于中小運動序列的效果更加明顯。從峰值信噪比來看，有的測試序列有所下降，有的測試序列略有提高，但變化幅度都不大，在0.04dB 范圍內，對圖像質量影響很小，可以忽略。從比特率方面來看，變化幅度也很小，增幅在0.3%范圍內。

表2 本文算法與UMH 算法性能比較結果

為測試本文算法的實用性，在開源庫X264基礎上實現本文算法，并將其和JRTP實時傳輸協議移植到Android平臺，并對接口進行封裝，通過JNI調用，實現Android終端的視頻采集和傳輸。測試使用的采集端為華為手機C8812，接收端為PC 機，實時播放效果如圖4 所示。在Wi－Fi局域網環境下，畫面播放流暢。

圖4 實時播放效果

4 結束語

本文結合了視頻序列中運動塊的分布特點，提出一種基于運動類型與多模板的運動估計算法，通過準靜止塊判定和按運動分布進行針對性搜索，減少了搜索冗余，降低了算法的計算復雜度，滿足低復雜度的視頻編碼對算法的性能要求。在保證編碼質量的同時，該算法對于不同類型的視頻序列，均從不同程度上縮短了運動估計時間，對中小運動序列的效果尤為明顯。下一步將針對劇烈運動視頻序列進行深入研究，降低計算復雜度，使其更好地適應移動視頻實時傳輸。

［1］GAO Xiaomin，YAO Rui，LIU Zhiyue，et al.Efficient adaptive motion estimation algorithm based on motion intensity ［J］.Journal of Image and Graphics，2012，17 （4）：504－511 （in Chinese）.［郭曉珉，姚睿，劉智躍，等.利用運動強度判據的高效自適應運動估計算法 ［J］.中國圖象圖形學報，2012，17 （4）：504－511.］

［2］Arora SM，Rajpal N.Comparative analysis of motion estimation algorithms on slow，medium and fast video sequences［C］／／International Conference on Reliability，Optimization and Information Technology－ICROIT，2014：422－427.

［3］DUANMU Chunjiang.Motion estimation technology in video processing and coding ［M］.Nanjing：Nanjing University Press，2011 （in Chinese）.［端木春江.視頻處理與編碼中的運動估計技術 ［M］.南京：南京大學出版社，2011.］

［4］LIU Long，SONG Qijun，ZHAO Taifei，et al.Fast motion estimation based on the special and temporal characteristic［J］.Journal on Communications，2013，34 （1）：121－127 （in Chinese）.［劉龍，宋琦軍，趙太飛，等.基于運動矢量時－空特性的快速運動估計算法研究 ［J］.通信學報，2013，34 （1）：121－127.］

［5］SHEN Zhou，LI Zhengming，PAN Tianhong.Motion estimation based on the partition and evaluation of the search a REA in H.264／AVC ［J］.Journal of Image and Graphics，2010，15 （2）：242－246 （in Chinese）. ［申舟，李正明，潘天紅.H.264／AVC中基于搜索區域劃分及評估的運動估計 ［J］.中國圖象圖形學報，2010，15 （2）：242－246.］

［6］LI Ziyin，YANG Qi.Fast motion estimation algorithm based on motion information adaptation ［J］.Journal of Image and Graphics，2012，17 （9）：1069－1074 （in Chinese）.［李子印，楊齊.基于運動信息自適應的快速運動估計算法 ［J］.中國圖象圖形學報，2012，17 （9）：1069－1074.］

［7］WU Yinhua，JIN Longxu，ZHANG Ning，et al.Improvement of fast integer pixel motion estimation algorithm for H.264［J］.Optics and Precision Engineering，2013，21 （4）：1017－1025 （in Chinese）. ［吳銀花，金龍旭，張寧，等.針對H.264改進的快速整像素運動估計算法 ［J］.光學精密工程，2013，21 （4）：1017－1025.］

［8］WU Xiaojun，BAI Shijun，LU Wentao.Optimization on motion estimation algorithm based on H.264 ［J］.Acta Electronica Sinica，2009，37 （11）：2541－2545 （in Chinese）. ［吳曉軍，白世軍，盧文濤.基于H.264視頻編碼的運動估計算法優化 ［J］.電子學報，2009，37 （11）：2541－2545.］

［9］Ko Yun－ho，Kang Hyun－soo，Lee Si－woong.Adaptive search range motion estimation using neighboring motion vector differences［J］.IEEE Transactions on Consumer Electronics，2011，57 （2）：726－730.

［10］Ismail Y，Mcneely JB，Shaaban M，et al.Fast motion estimation system using dynamic models for H.264／AVC video coding ［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22 （1）：28－42.

［11］YE Shitong，WAN Zhiping.Combination of motion estimation algorithm type with threshold value of block－based motion［J］.Computer Engineering and Design，2013，34 （6）：2093－2097 （in Chinese）.［葉仕通，萬智萍，基于塊運動類型與閾值相結合的運動估計算法 ［J］.計算機工程與設計，2013，34 （6）：2093－2097.］

［12］DING Xin，FAN Huijin.A mix－pattern motion estimation search algorithm based on direction adaptation ［J］.Journal of Image and Graphics，2011，16 （1）：14－20 （in Chinese）.［丁鑫，樊慧津.基于方向自適應的運動估計混合模板搜索 算 法 ［J］. 中 國 圖 象 圖 形 學 報，2011，16 （1）：14－20.］