基于塊運動類型與閾值相結(jié)合的運動估計算法

葉仕通，萬智萍

（1.廣東工業(yè)大學(xué) 華立學(xué)院，廣東 增城511325；2.中山大學(xué) 新華學(xué)院，廣東 廣州510520）

0 引 言

運動估計算法是現(xiàn)如今視頻壓縮領(lǐng)域中的一項核心技術(shù)，利用視頻運動在時間與空間上的關(guān)聯(lián)性有效地去除序列圖像幀間的冗余進而對視頻進行預(yù)測與壓縮；在保證視頻質(zhì)量的前提下能夠減少了視頻壓縮所需要的時間。因此，運動估計算法一直以來都是視頻壓縮領(lǐng)域中的研究熱點，許多專家學(xué)者也提出了許多快速運動估計算法，如三步搜索法 （TSS）、鉆石 搜索法 （DS）、全搜索算 法 （FS）等［1－3］，它們都是改進來降低整像素運動估計的復(fù)雜度，提高視頻的壓縮效率；但全搜索算法雖能保證視頻質(zhì)量但其計算量太大；而三步搜索法與鉆石搜索法雖通過減少搜索點數(shù)來提高搜索速度，但卻無法保證視頻的質(zhì)量；因此，這些算法都存在著不足，無法滿足人們的需求。本文為了避免出現(xiàn)算法的局部優(yōu)化問題，結(jié)合Chen zhi－bo等人提出了一種非對稱十字型多層次六邊形格點搜索算法，根據(jù)運動矢量的水平垂直偏置分布特性與半路中止的算法，并通過結(jié)合其他搜索模式的優(yōu)點，最終提出一套新的算法；從而在比全搜索算法的計算量少90%的情況下，能得到了與之相近的視頻壓縮效果，但為了進一步提高算法的搜索效率［4］，本文根據(jù)視頻的塊運動的劇烈程度將其運動塊劃分為不同的運動矢量分布［5－7］，并且結(jié)合加閾值［8］的方法對UMHexagonS算法進行改進，以減小該算法中的算法搜索冗余為目的，對其進行優(yōu)化，最終有效的減少算法在搜索過程的搜索點的數(shù)量，使得算法的搜索效率得到提高，更加有利于生活中的運用。

1 UMHexagonS算法基本步驟及改進

1.1 UMHexagonS算法總體思路與分析

視頻壓縮的過程中，采用多種模板進行宏塊匹配，同時結(jié)合空間與時間的相關(guān)性進行運動矢量的預(yù)測，進而達到對視頻壓縮的目的。下面為對UMHexagonS算法的基本步驟：

步驟1 起始搜索點的預(yù)測，用五種預(yù)測模式對預(yù)測運動矢量MV進行預(yù)測。并對SAD的值進行判斷，如果搜索點SAD的值很小，則跳到步驟6；如果SAD的值較大，則跳到步驟5；否則跳到步驟2。

步驟2 非對稱十字形模板搜索。并對SAD的值進行判斷，如果搜索點SAD的值很小，則跳到步驟6；如果SAD的值較大，則跳到步驟5；否則跳到步驟3。

步驟3 螺旋搜索

步驟4 多層六邊形模板搜索

步驟5 中六邊形模板搜索

步驟6 小菱形模板反復(fù)搜索，最終得到運動矢量。

UMHexagonS算法中的各種搜索模板如圖1所示。

圖1 UMHexagonS算法中的各種搜索模板

從UMHexagonS算法的流程我們可以看到，UMHexagonS算法在第一步的起始點搜索中，用5種預(yù)測模式進行搜索，有效的對運動塊進行預(yù)測，從而提高了算法的效率，但在一些塊進行搜索匹配點時依然存在著算法的冗余性，如在經(jīng)過預(yù)測時，如果起始點一開始就是最優(yōu)點，經(jīng)過中值預(yù)測，就能把他選出最佳匹配點，但算法依然對其進行5種模式進行預(yù)測，進而增加了搜索的冗余；視頻的塊運動可以根據(jù)運動劇烈程度來劃分不同的運動矢量分布，根據(jù)不同的情況進行分類搜索，而UMHexagonS算法對所有的候選搜索塊都進行多層六邊形搜索，因此也導(dǎo)致了算法的搜索冗余。

1.2 UMHexagons算法的改進

經(jīng)過對UMHexagons算法的基本思路的分析與研究，我們可以看到，該算法雖然能夠快速而高效的對視頻進行運動估計，但其中依然存在著很多的不足，本文根據(jù)視頻運動類型的自適應(yīng)法與在算法中加入閾值的方法對其UMHexagons算法進行改進，其目標是減少UMHexagonS算法搜索冗余，方法如下所示。

改進一：起始搜索點的預(yù)測，在進行的運動矢量預(yù)測時，先使用中值預(yù)測，得到當前搜索點，設(shè)當前點為最佳點mincost，加入自適應(yīng)的閾值Th0進行預(yù)先判斷：

當mincost＜Th0時，則判斷為提前停止搜索；否則對其搜索點進行非對稱十字搜索，后進行原點預(yù)測、uplager預(yù)測和相鄰參考預(yù)測算法后，加入自適應(yīng)的閾值Th1與Th2，對其mincost進行判斷：

若mincost＜Th1；提前停止搜索

若Th1＜mincost＜Th2；跳到菱形模板搜索［9］

若Th2＜mincost；則執(zhí)行下一步

式中：βstop——塊的尺寸，αstop——常數(shù)組，

常數(shù) 組 αstop的 取 值 為 ｛0.30，0.33，0.33，0.27，0.13，0.13，0.44｝；

通過在起始點的預(yù)測過程在加入閾值，來到減少算法中的必要的搜索，從而節(jié)約了搜索的點數(shù)，進而提高搜索效率。在此過程中，能把運動矢量幅度小用菱形模板進行搜索，提前停止搜索，從而提高了搜索的效率。

改進二：加入運動類型的自適應(yīng)法，在現(xiàn)實生活中，視頻可以根據(jù)運動劇烈程度來劃分不同的運動矢量分布，分為如下3種：

（1）塊的運動幅度小的，其運動的矢量通常都是以（0，0）為中心向外擴散，而且越往外的，其發(fā)生的概率越小，因此，對于運動幅度小的可以理解為其運動矢量在搜索中心 （0，0）附近。

（2）塊的運動幅度中等，其運動的矢量通常不在搜索中心 （0，0），它會在距離中心位置較遠的地方出現(xiàn)，而且其出現(xiàn)的概率分布是向中心與外側(cè)出現(xiàn)的概率越來越小，呈環(huán)狀型，向中心與外側(cè)遞減。

（3）塊的運動幅度很大，其運動的矢量通常分布在遠離搜索中心 （0，0），主要出現(xiàn)在外側(cè)范圍。

為了能夠快速的判斷視頻的運動劇烈程度，引入閾值T［10］，通過cost （珡m ，λ）［11］與 T 的比較，來判斷視頻運動的幅度大小，進而對其分類，提高搜索效率，減少搜索的冗余：

1）當cost（，λ）＜T0時，其視頻圖像的塊運動幅度很小，可表示為相對靜止狀態(tài)，可以把搜索中心 （0，0）設(shè)置為最佳點，但由于在對起始點的閾值判斷的時候，已經(jīng)把運動矢量幅度小的排除了，因此，在這里無需對其進行判斷。

2）當cost（m珡，λ）＜＝T時，其視頻圖像的塊運動幅度中等，選用正方形搜索模板，即5×5的搜索。

3）當cost（m珡，λ）＞T時，其視頻圖像的塊運動幅度很大，則跳到Step 5，用多層六邊形模板搜索，后用中六邊形模板搜索，最后用小菱形模板對其反復(fù)的搜索，直到得到最佳結(jié)果。

研究表明當T＝800時，其能準確的把塊運動幅度中等與塊運動幅度很大進行有效的判斷。T＜＝800時，對于運動幅度中等的搜索效率很高，而在運動幅度很大的塊不適用。公式

其中B根據(jù)不同情況可取16，8或4

其中SAD式絕對誤差和；R是候選運動矢量碼率；λ是平衡碼率與失真度的因子；s是當前編碼的數(shù)據(jù)、c（m）是編碼重建的參考幀數(shù)據(jù)。

本文改進后UMHexagons算法的核心程序片段如下所示。

正方形搜索，只搜索前25點，相當于5×5區(qū)域全搜索：

多層六邊形模板搜索：

六邊形模板搜索：

2 改進后UMHexagons算

步驟1 起始搜索點的預(yù)測，先對搜索點進行中值預(yù)測，引入閾值Th0，進行初步的閾值判斷，設(shè)當前點位最佳點mincost，進行比較，如果mincost＜Th0，即提前停止搜索，否則進行原點預(yù)測、uplager預(yù)測和相鄰參考預(yù)測算法，后進行非對稱十字搜索，加入自適應(yīng)的閾值Th1與Th2，對其mincost進行判斷：若mincost＜Th1；提前停止搜索若Th1＜mincost＜Th2；跳到菱形模板搜索若Th2＜mincost；則執(zhí)行步驟2

步驟2 根據(jù)運動類型自適應(yīng)法，對搜索點運動矢量幅度的大小進行判斷，當cost（珡m，λ）＜＝T時，選用正方形搜索模板。當cost（珡m，λ）＞T時，其視頻圖像的塊運動幅度很大，則繼續(xù)步驟5。

步驟3 菱形模板搜索，得到最終的運動矢量。

步驟4 正方形搜索模板，得到最終的結(jié)果。

步驟5 多層六邊形模板搜索

步驟6 中六邊形模板搜索

步驟7 小菱形模板反復(fù)搜索，最終得到運動矢量。

改進后UMHexagons算法流程圖如圖2所示。

3 實驗結(jié)果與分析

圖2 UMHexagons算法

使用JVT的h.264／AVC編碼參考模，在JM12.2平臺上進行改進算法的驗證。本文根據(jù)運動幅度的大小選取了QCIF的3個標準視頻測試序列：mobile、foreman、akiyo對算法進行仿真，其中akiyo的空間細節(jié)比較少，并且運動較為緩慢，因此用來表示運動幅度小的運動序列；Foreman雖然鏡頭與畫面的背景一起運動，但其紋理復(fù)雜度一般，因此用來表示運動幅度中等的運動序列；mobile運動形式豐富并且其紋理的復(fù)雜度極高，因此用來表示運動幅度很大的運動序列。編碼幀數(shù)為60，參考幀數(shù)為5，幀率為30，編碼格式為IPPPP。兩種種算法在不同的量化參數(shù) （QP）下進行測試。

運動估計算法的效率主要依據(jù)是視頻的峰值信噪比高低和搜索速度快慢。只有做到運動估計的準確性，才能做到的圖像質(zhì)量就越高，視頻序列的搜索越塊的效果；本文根據(jù)本文主要采用Y、U、V各分量的峰值信噪比（PSNR）、運動估計時間 （MET）作為算法性能評判的標準。Y、U、V各分量的PSNR表明壓縮后圖像的質(zhì)量，而運動估計時間能有效的表明算法的有效性。其測試結(jié)果：表1為原UMHexagons算法與改進后算法的運動估計時間比較，表2為原UMHexagons算法與改進后算法的各分量峰值信噪比較，如下所示。

通過實驗可以看，本文通過改進后的算法與原始的UMHexagons算法的PSNR各分量數(shù)據(jù)進行比較，可以再表2中看出，在QP值變化的情況下，PSNR的各個分量的峰值變化很小，最大的變化也只有3%，而從表1中，我們可以看出，在QP值變化的情況下，skiyo視頻測試序列的運動估計時間變化平均在18%左右，foreman視頻測試序列的運動估計時間變化平均在37%左右，而mobile視頻測試序列的運動估計時間變化平均在26%左右；由此可見，本文改進后的UMHexagons算能在保持了原算法的率失真性能下，減少運動估計編碼時間。

表1 原始算法與改進算法的運動估計時間比較 （表1題目排列參表2）

表2 原始算法與改進算法的各分量峰值信噪比較

為了更加直觀的展示原始算法與改進后算法在搜索點數(shù)的優(yōu)化程度，本文用過MATLAB對其進行仿真，經(jīng)實驗，圖3為skiyo視頻測試序列的搜索數(shù)、圖4為foreman視頻測試序列的搜索、圖5為mobile視頻測試序列的搜索數(shù)。

通過MATLAB對其算法搜索點數(shù)的驗證，我們可以看到，本文根據(jù)視頻運動塊的運動幅度的大小，有效的減少了UMHexagons算法中的搜索冗余性，在視頻預(yù)測序列skiyo與foreman和mobile的搜索數(shù)與原UMHexagons算的搜索點相比有明顯的減少，其中視頻預(yù)測序列foreman的搜索點個數(shù)減少的最多；與預(yù)測的結(jié)果相符，充分證明的算法的可行性。

4 結(jié)束語

本文通過在UMHexagons算法中增加閾值的形式，來減少原UMHexagons算法中的搜索冗余，通過比較判斷，根據(jù)運動矢量幅度的大小，對視頻的運動塊進行分類，有效的減少模塊的不必要重復(fù)搜索，從而減少運用估計時間，結(jié)果表明，改進后的運動估計算法在運動幅度平緩的視頻序列中，性能略有提高；在運動幅度很快的視頻序列中，性能較好；在運動幅度中等的視頻序列中，性能優(yōu)異，與預(yù)期的效果相符。但改進后算法還存在著不足，如可通過優(yōu)化各種搜索模板使算法更加完善，在日后的研究工作中，會將其作為深入的研究，使其能夠更加適用于實際的生活。

：

［1］WANG Yanying，F(xiàn)ENG Jinmei.Improved H.264motion estimation algorithm based on EPZS ［J］.Computer Technology and Development，2012，22 （1）：103－107 （in Chinese）. ［王艷營，馮進玫.基于EPZS的H.264運動估計算法的改進［J］.計算機技術(shù)與發(fā)展，2012，22 （1）：103－107.］

［2］ZHANG Sha，TIAN Fengchun，TAN Hongtao.Fast block matching search algorithm based on down－sampling and its application in denoising ［J］.Journal of Computer Applications，2010，30 （10）：2819－2822 （in Chinese）.［張莎，田逢春，譚洪濤.基于下采樣的快速塊匹配搜索算法及降噪應(yīng)用 ［J］.計算機應(yīng)用，2010，30 （10）：2819－2822.］

［3］CHEN Gong，Niu Qinzhou.On classical bma in motion estimation of image sequence ［J］.Computer Applications and Software，2012，29 （5）：147－151 （in Chinese）.［陳宮，牛秦洲.圖像序列運動估計中經(jīng)典塊匹配算法研究 ［J］.計算機應(yīng)用與軟件，2012，29 （5）：147－151.］

［4］HUANG Chunqing，QIU Xiaobin.Optimization on fast motion estimation algorithm based on x264 ［J］.Control Engineering of China，2010，19 （6）：820－823 （in Chinese）.［黃春慶，邱曉彬.基于x264的快速運動估計算法優(yōu)化 ［J］.控制工程，2010，19 （6）：820－823.］

［5］ZHANG Xinan，GONG Yanjun，LI Xiaowu.Fast integer pixel motion estimation algorithm for AVS－M ［J］.Journal of Chinese Computer Systems，2011，32 （4）：793－796 （in Chinese）.［張新安，宮彥軍，李小武.一種AVS－M整數(shù)像素運動估計快速算法 ［J］.小型微型計算機系統(tǒng)，2011，32 （4）：793－796.］

［6］CHEN Tianzhuang，LIANG Jiuzhen，HAN Jun.A fast algorithm based on mot ion classification and direct ion prediction［J］.Computer Engineering ＆ Science，2100，33 （7）：112－117（in Chinese）.［陳天壯，梁久禎，韓軍.一種基于塊運動類型和方向預(yù)測相結(jié)合的快速搜索算法 ［J］.計算機工程與科學(xué)，2100，33 （7）：112－117.］

［7］FANG Muyun，WU Yuan，LI Qian.Improvement on motion vector field adaptive search algorithm ［J］.Computer Technology and Development，2011，21 （6）：70－73 （in Chinese）.［方木云，吳元，李倩.運動矢量場自適應(yīng)搜索算法的一種改進方案 ［J］.計算機技術(shù)與發(fā)展，2011，21 （6）：70－73.］

［8］XIE Hongtu，GAO Guangzhu，HE Zhiyong.Research of adaptive motion estimation and compensation algorithm based on redundant discrete wavelet transformation ［J］.Application Research of Computers，2011，28 （1）：368－370 （in Chinese）.［謝洪途，高廣珠，何智勇.基于冗余小波變換的自適應(yīng)運動估計與補償算法研究 ［J］.計算機應(yīng)用研究，2011，28 （1）：368－370.］

［9］MENG Lei，LI Hang.Adaptivemotion estimation search algorithm in H.264／AVC ［J］.Computer Applications and Software，2010，27 （8）：145－147 （in Chinese）.［孟磊，李航.H.264／AVC自適應(yīng)運動估計搜索算法 ［J］.計算機應(yīng)用與軟件，2010，27 （8）：145－147.］

［10］ZHU Xiaolong，LUO Xing，CHEN Zujue.Improved directional diamond algorithm with mode decision ［J］.Application Research of Computers，2010，27 （1）：393－395 （in Chinese）.［朱小龍，羅星，陳祖爵.帶有模式選擇的改進的方向性菱形搜索算法 ［J］.計算機應(yīng)用研究，2010，27 （1）：393－395.］

［11］HUANG Wenbin，WANG Guanglong.Research of optimization on fast motion estimation algorithm based on multi－template search ［J］.Computer Measurement ＆ Control，2012，20 （5）：1326－1329 （in Chinese）.［黃文斌，王廣龍.基于多模板快速搜索的運動估計算法優(yōu)化研究 ［J］.計算機測量與控制，2012，20 （5）：1326－1329.］