基于塊運(yùn)動(dòng)類型與閾值相結(jié)合的運(yùn)動(dòng)估計(jì)算法

葉仕通，萬(wàn)智萍

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

0 引 言

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

1 UMHexagonS算法基本步驟及改進(jìn)

1.1 UMHexagonS算法總體思路與分析

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

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

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

步驟3 螺旋搜索

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

步驟5 中六邊形模板搜索

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

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

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

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

1.2 UMHexagons算法的改進(jìn)

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

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

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

若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｝；

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

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

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

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

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

為了能夠快速的判斷視頻的運(yùn)動(dòng)劇烈程度，引入閾值T［10］，通過(guò)cost （珡m ，λ）［11］與 T 的比較，來(lái)判斷視頻運(yùn)動(dòng)的幅度大小，進(jìn)而對(duì)其分類，提高搜索效率，減少搜索的冗余：

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

2）當(dāng)cost（m珡，λ）＜＝T時(shí)，其視頻圖像的塊運(yùn)動(dòng)幅度中等，選用正方形搜索模板，即5×5的搜索。

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

研究表明當(dāng)T＝800時(shí)，其能準(zhǔn)確的把塊運(yùn)動(dòng)幅度中等與塊運(yùn)動(dòng)幅度很大進(jìn)行有效的判斷。T＜＝800時(shí)，對(duì)于運(yùn)動(dòng)幅度中等的搜索效率很高，而在運(yùn)動(dòng)幅度很大的塊不適用。公式

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

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

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

正方形搜索，只搜索前25點(diǎn)，相當(dāng)于5×5區(qū)域全搜索：

多層六邊形模板搜索：

六邊形模板搜索：

2 改進(jìn)后UMHexagons算

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

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

步驟3 菱形模板搜索，得到最終的運(yùn)動(dòng)矢量。

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

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

步驟6 中六邊形模板搜索

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

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

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

圖2 UMHexagons算法

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

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

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

表1 原始算法與改進(jìn)算法的運(yùn)動(dòng)估計(jì)時(shí)間比較 （表1題目排列參表2）

表2 原始算法與改進(jìn)算法的各分量峰值信噪比較

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

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

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

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

：

［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）. ［王艷營(yíng)，馮進(jìn)玫.基于EPZS的H.264運(yùn)動(dòng)估計(jì)算法的改進(jìn)［J］.計(jì)算機(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］.計(jì)算機(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）.［陳宮，牛秦洲.圖像序列運(yùn)動(dòng)估計(jì)中經(jīng)典塊匹配算法研究 ［J］.計(jì)算機(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ùn)動(dòng)估計(jì)算法優(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ù)像素運(yùn)動(dòng)估計(jì)快速算法 ［J］.小型微型計(jì)算機(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ùn)動(dòng)類型和方向預(yù)測(cè)相結(jié)合的快速搜索算法 ［J］.計(jì)算機(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ùn)動(dòng)矢量場(chǎng)自適應(yīng)搜索算法的一種改進(jìn)方案 ［J］.計(jì)算機(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)運(yùn)動(dòng)估計(jì)與補(bǔ)償算法研究 ［J］.計(jì)算機(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)運(yùn)動(dòng)估計(jì)搜索算法 ［J］.計(jì)算機(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ìn)的方向性菱形搜索算法 ［J］.計(jì)算機(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ùn)動(dòng)估計(jì)算法優(yōu)化研究 ［J］.計(jì)算機(jī)測(cè)量與控制，2012，20 （5）：1326－1329.］