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

（沈陽(yáng)航空航天大學(xué) 計(jì)算機(jī)學(xué)院，遼寧 沈陽(yáng)110136）

0 引 言

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

1 UMHexagonS算法

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

圖1 UMHexagonS算法

步驟1 起始點(diǎn)預(yù)測(cè)：首先通過(guò)5種［8］高精度的預(yù)測(cè)方式來(lái)獲得候選MV 集合，其次從中選取碼率和失真度代價(jià)函數(shù)值最小的點(diǎn)作為起始點(diǎn)。然后進(jìn)行提前終止檢測(cè)，如果滿足終止條件，則轉(zhuǎn)入步驟4，進(jìn)行擴(kuò)展六邊形搜索；否則轉(zhuǎn)入步驟2。

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

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

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

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

2 本文算法

本文借鑒了相關(guān)研究人員提出的優(yōu)秀改進(jìn)方法［9，10］，在準(zhǔn)靜止塊判定、起始點(diǎn)預(yù)測(cè)、運(yùn)動(dòng)類型劃分與多模板搜索這3方面對(duì)UMHexagonS算法進(jìn)行了改進(jìn)，降低算法的計(jì)算復(fù)雜度，下面分別從這3方面描述該算法。

2.1 準(zhǔn)靜止塊判定

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

2.2 起始點(diǎn)預(yù)測(cè)

文獻(xiàn) ［7］中對(duì)起始點(diǎn)的5種預(yù)測(cè)方式的準(zhǔn)確度進(jìn)行了統(tǒng)計(jì)，發(fā)現(xiàn)中值預(yù)測(cè)和上層模式預(yù)測(cè)獲取的MV 準(zhǔn)確度最高。為了進(jìn)一步降低算法的復(fù)雜度，并使搜索中心位于最佳匹配點(diǎn)，本算法采用中值預(yù)測(cè)和上層模式預(yù)測(cè)方式選取具有最小碼率和失真度代價(jià)的點(diǎn)作為起始點(diǎn)。

2.3 運(yùn)動(dòng)塊類型劃分與多模板搜索

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

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

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

圖2 搜索模板

對(duì)于平緩運(yùn)動(dòng)塊，其運(yùn)動(dòng)矢量偏離起點(diǎn)不是很大，先選用非對(duì)稱小十字形模板 （如圖2 （e）所示）進(jìn)行初步定位，然后再選用菱形模板（如圖2 （f）所示）進(jìn)行細(xì)化搜索。

2.4 算法描述

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

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

步驟2 起始點(diǎn)預(yù)測(cè)：按照中值預(yù)測(cè)和上層預(yù)測(cè)方式搜索出代價(jià)函數(shù)值cost最小的MV 作為起始點(diǎn)，轉(zhuǎn)至步驟3。

步驟3 運(yùn)動(dòng)塊類型判斷：將起始點(diǎn)的cost值與閥值T2進(jìn)行比較。如果cost小于等于T2，則判定當(dāng)前塊為平緩運(yùn)動(dòng)塊，轉(zhuǎn)至步驟4 按平緩運(yùn)動(dòng)塊策略搜索；如果cost大于T2，則判定當(dāng)前塊為劇烈運(yùn)動(dòng)塊，轉(zhuǎn)至步驟5按劇烈運(yùn)動(dòng)塊策略搜索。

步驟4 平緩運(yùn)動(dòng)塊搜索。

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

（2）以當(dāng)前最佳匹配點(diǎn)為中心，按菱形模板進(jìn)行細(xì)化搜索，選取最佳匹配點(diǎn)。如果最佳匹配點(diǎn)在菱形邊上，則轉(zhuǎn)至步驟6；否則轉(zhuǎn)至步驟7。

步驟5 劇烈運(yùn)動(dòng)塊搜索。

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

（2）以當(dāng)前最佳匹配點(diǎn)為中心，按多層次八邊形模板進(jìn)行搜索，每次擴(kuò)展前，進(jìn)行提前終止檢測(cè)，如果滿足終止條件，則轉(zhuǎn)至步驟6；否則判斷是否繼續(xù)擴(kuò)展，直至搜索窗邊界，轉(zhuǎn)至步驟5 （3）。

（3）以當(dāng)前最佳匹配點(diǎn)為中心，按六邊形模板反復(fù)搜索，直至最優(yōu)點(diǎn)位于其中心，轉(zhuǎn)至步驟6。

步驟6 精細(xì)搜索，以當(dāng)前最佳匹配點(diǎn)為中心，按小菱形模板反復(fù)搜索，直至最優(yōu)點(diǎn)位于其中心，轉(zhuǎn)至步驟7。

步驟7 輸出MV。

圖3 本文算法流程

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

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

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

表1 實(shí)驗(yàn)結(jié)果記錄

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

表2 本文算法與UMH 算法性能比較結(jié)果

為測(cè)試本文算法的實(shí)用性，在開(kāi)源庫(kù)X264基礎(chǔ)上實(shí)現(xiàn)本文算法，并將其和JRTP實(shí)時(shí)傳輸協(xié)議移植到Android平臺(tái)，并對(duì)接口進(jìn)行封裝，通過(guò)JNI調(diào)用，實(shí)現(xiàn)Android終端的視頻采集和傳輸。測(cè)試使用的采集端為華為手機(jī)C8812，接收端為PC 機(jī)，實(shí)時(shí)播放效果如圖4 所示。在Wi－Fi局域網(wǎng)環(huán)境下，畫(huà)面播放流暢。

圖4 實(shí)時(shí)播放效果

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

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

［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）.［郭曉珉，姚睿，劉智躍，等.利用運(yùn)動(dòng)強(qiáng)度判據(jù)的高效自適應(yīng)運(yùn)動(dòng)估計(jì)算法 ［J］.中國(guó)圖象圖形學(xué)報(bào)，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）.［端木春江.視頻處理與編碼中的運(yùn)動(dòng)估計(jì)技術(shù) ［M］.南京：南京大學(xué)出版社，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）.［劉龍，宋琦軍，趙太飛，等.基于運(yùn)動(dòng)矢量時(shí)－空特性的快速運(yùn)動(dòng)估計(jì)算法研究 ［J］.通信學(xué)報(bào)，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中基于搜索區(qū)域劃分及評(píng)估的運(yùn)動(dòng)估計(jì) ［J］.中國(guó)圖象圖形學(xué)報(bào)，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）.［李子印，楊齊.基于運(yùn)動(dòng)信息自適應(yīng)的快速運(yùn)動(dòng)估計(jì)算法 ［J］.中國(guó)圖象圖形學(xué)報(bào)，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）. ［吳銀花，金龍旭，張寧，等.針對(duì)H.264改進(jìn)的快速整像素運(yùn)動(dòng)估計(jì)算法 ［J］.光學(xué)精密工程，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視頻編碼的運(yùn)動(dòng)估計(jì)算法優(yōu)化 ［J］.電子學(xué)報(bào)，2009，37 （11）：2541－2545.］

［9］Ko Yun－h(huán)o，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）.［葉仕通，萬(wàn)智萍，基于塊運(yùn)動(dòng)類型與閾值相結(jié)合的運(yùn)動(dòng)估計(jì)算法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34 （6）：2093－2097.］

［12］DING Xin，F(xiàn)AN 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）.［丁鑫，樊慧津.基于方向自適應(yīng)的運(yùn)動(dòng)估計(jì)混合模板搜索 算 法 ［J］. 中 國(guó) 圖 象 圖 形 學(xué) 報(bào)，2011，16 （1）：14－20.］