引 言

目前，H.264 標(biāo)準(zhǔn)的視頻編解碼受到了廣泛地應(yīng)用，它的編碼效率很高，但是運(yùn)動(dòng)估計(jì)作為編碼的核心，其計(jì)算量也相當(dāng)復(fù)雜，這就增加了時(shí)間損耗，嚴(yán)重降低了視頻編解碼的效率。近年來(lái)，運(yùn)動(dòng)估計(jì)一直被作為研究熱點(diǎn)。

在各種視頻編碼標(biāo)準(zhǔn)中，塊匹配運(yùn)動(dòng)估計(jì)算法是應(yīng)用最廣泛的。全局算法（FS）能得到最佳的運(yùn)動(dòng)矢量，但是計(jì)算量很大，嚴(yán)重降低了編碼的實(shí)時(shí)性。為了減少算法的復(fù)雜度，很多算法被提出來(lái)，其中包括三步法[1]、四步法[2]、MVFAST[3] 等經(jīng)典算法。而 EPZS（預(yù)測(cè)區(qū)域的搜索算法）是一種被 JM 模型采用的整像素運(yùn)動(dòng)搜索算法，它由局部逐漸向最佳點(diǎn)靠近，對(duì)于搜索范圍較大的、運(yùn)動(dòng)很激烈的對(duì)象的搜索容易過(guò)早陷入局部最優(yōu)[4]。

在充分分析 EPZS 算法的基礎(chǔ)上，針對(duì)基于六邊形改進(jìn)的EPZS 算法搜索精度不高，搜索點(diǎn)數(shù)多的特點(diǎn)[5]，提出了對(duì)EPZS 終止搜索的條件以及搜索模板進(jìn)行改進(jìn)，改進(jìn)優(yōu)化后的算法搜索方向細(xì)化，精度更高，減少了搜索點(diǎn)數(shù)，降低了算法的復(fù)雜度，有效節(jié)省了運(yùn)動(dòng)估計(jì)的時(shí)間，增強(qiáng)了編碼的實(shí)時(shí)性。

1 EPZS算法的介紹以及存在的不足

EPZS 搜索算法利用視頻運(yùn)動(dòng)的空間和時(shí)間相關(guān)項(xiàng)，對(duì)當(dāng)前編碼的運(yùn)動(dòng)矢量進(jìn)行預(yù)測(cè)，提出一種相鄰塊失真的提前終止準(zhǔn)則來(lái)提前終止搜索 [6]，進(jìn)一步來(lái)提高搜索速度，減少編碼的復(fù)雜度。對(duì)于那些不能提前進(jìn)行終止搜索的，利用搜索模板來(lái)進(jìn)行相關(guān)運(yùn)動(dòng)矢量地完善。

1.1 計(jì)算提前終止搜索條件的不足

EPZS 根據(jù)相鄰塊的失真具有很高的相似度，而提出了一種基于相鄰塊失真的提前終止準(zhǔn)則。通過(guò)提前終止準(zhǔn)則，減少了算法的計(jì)算復(fù)雜度。在 EPZS 算法中，通過(guò)當(dāng)前塊 A 的左 側(cè)塊 B、正上方塊 C、右上方塊 D 三個(gè)相鄰塊的最小 SAD 值 來(lái)計(jì)算終止條件的標(biāo)準(zhǔn) [7]（分別記為 SADB、SADC、SADD）。 由此可知，EPZS 計(jì)算終止搜索的條件過(guò)于簡(jiǎn)單，對(duì)于大多數(shù) 情況計(jì)算出來(lái)的搜索終止條件是滿足的，但沒(méi)有考慮到運(yùn)動(dòng)較 小或者靜止情況下，這三個(gè) SAD 的值非常接近 [8]，由此可知， 這樣計(jì)算出來(lái)的 SAD 不一定是準(zhǔn)確的。

1.2 EPZS的搜索模板的不足

改進(jìn)后的EPZS 算法，搜索點(diǎn)數(shù)過(guò)多，對(duì)于運(yùn)動(dòng)較為復(fù)雜的運(yùn)動(dòng)場(chǎng)合，容易陷入局部最優(yōu)而提前進(jìn)入終止搜索，這樣就會(huì)產(chǎn)生更大的誤差。

2 改進(jìn)后的 EPZS算法

對(duì)EPZS 算法的優(yōu)化主要是針對(duì)其在計(jì)算終止搜索條件和搜索模板方面地優(yōu)化，通過(guò)終止搜索閾值 T0 地設(shè)定和不同的搜索模板方法來(lái)對(duì)當(dāng)前塊在不同的范圍內(nèi)進(jìn)行搜索，直至搜索到最佳點(diǎn)，得到最佳運(yùn)動(dòng)矢量。

2.1 搜索終止條件的優(yōu)化

我們將起始搜索點(diǎn)的SAD 值記為SADM，由于起始預(yù)測(cè)搜索點(diǎn)最接近于最佳點(diǎn)，SAD 的值和SADM 的值相關(guān)性越大， 我們可以更快地利用終止搜索的條件來(lái)得到最佳的 SAD 值， 我們?cè)O(shè)定終止搜索的閾值為 T0，如下公式所示：

T0=min（SADM，SADB，SADC，SADD）

2.2 精細(xì)搜索模板的改進(jìn)

通過(guò)研究各種搜索模板，我們可以發(fā)現(xiàn)搜索模板越是接近圓形，其搜索性能越好 [9]，因?yàn)閳A形的方向覆蓋全，搜索范圍更精確，更容易讓我們找到最佳點(diǎn)，從而得到最佳運(yùn)動(dòng)矢量，而這里十二邊形無(wú)限接近于圓形，它共有 13 個(gè)點(diǎn)分別為（0，0）、（1，4）、（3，3）、（4，1）、（4，－ 1）、（3，－ 3）、（1，－ 4）、（－1，－ 4）、（－3，－ 3）、（－4，-1）、（－4，1）、（－3，3）、（－1，4），搜索中心點(diǎn)和外圍的 12 個(gè)不同方向的點(diǎn)，求得最佳點(diǎn)，判斷搜索到的點(diǎn)是不是最佳點(diǎn)，如不是以此點(diǎn)為中心進(jìn)行非對(duì)稱十字形搜索，判斷是否為最佳點(diǎn)，直到最佳點(diǎn)為中心點(diǎn)，此時(shí)的向量為最佳運(yùn)動(dòng)矢量MV。利用十二邊形進(jìn)行最佳點(diǎn)方向的判斷搜索，方向覆蓋更全面，減少了搜索點(diǎn)數(shù)，能夠很快很好地得到最佳點(diǎn)，從而得到最佳運(yùn)動(dòng)矢量。

這里采用小菱形搜索模板[10]、非對(duì)稱十字形搜索模板和（類圓形）十二邊形的搜索模板。模板如圖 1 所示：

（a）小鉆石形（b）非對(duì)稱十字形（c）十二邊形

圖1 搜索模板

在初始化搜索點(diǎn)后，對(duì)塊類型進(jìn)行判別來(lái)選擇相應(yīng)的模板進(jìn)行搜索最佳點(diǎn)，然后進(jìn)行閾值判斷來(lái)判別是否終止搜索。算法的搜索步驟和流程如圖 2 所示。

算法的搜索步驟如下： 

（1）判斷當(dāng)前塊是否是靜止塊，若是靜止塊直接跳入步 驟（5），否則進(jìn)入步驟（2）。 

（2）判斷當(dāng)前塊是小運(yùn)動(dòng)塊還是大運(yùn)動(dòng)塊，如果當(dāng)前塊 為小運(yùn)動(dòng)塊，即運(yùn)動(dòng)平緩，則進(jìn)入步驟（3），否則進(jìn)入步驟（4）。 

（3）當(dāng)前塊為小運(yùn)動(dòng)塊，對(duì)其進(jìn)行小鉆石形模板搜索， 直到 SAD 小于閾值 T0，得到最佳運(yùn)動(dòng)矢量。 

（4）當(dāng)前塊為大運(yùn)動(dòng)塊，即運(yùn)動(dòng)比較激烈，此時(shí)應(yīng)該先 進(jìn)行初始搜索點(diǎn)預(yù)測(cè)，然后對(duì)其進(jìn)行十二邊形模板搜索，對(duì) 得到的 SAD 進(jìn)行分析，是否為最佳點(diǎn)，若為最佳點(diǎn)，則對(duì)其 進(jìn)行小鉆石形模板搜索，直到得到最佳運(yùn)動(dòng)矢量 ；若不是最 佳點(diǎn)則對(duì)其進(jìn)行非對(duì)稱十字形搜索，然后再次判斷是否為最 佳點(diǎn)，若不是則一直進(jìn)行非對(duì)稱十字形搜索，直到得到 SAD 最佳點(diǎn)，然后再對(duì)其最佳點(diǎn)進(jìn)行小鉆石型搜索，直到 SAD 小 于閾值 T0，得到最佳運(yùn)動(dòng)矢量。 

（5）搜索結(jié)束。 本文是以 H.264 官方的標(biāo)準(zhǔn)測(cè)試模型 JM 10.1 為平臺(tái)， 在此基礎(chǔ)上對(duì)改進(jìn)算法進(jìn)行測(cè)試的實(shí)驗(yàn)。優(yōu)化后的算法和基 于六邊形改進(jìn)的 EPZS 算法相比較，在不影響圖像質(zhì)量的前提 下，運(yùn)動(dòng)估計(jì)的時(shí)間明顯減少，搜索效率明顯提高。

結(jié) 語(yǔ)

本文基于EPZS（預(yù)測(cè)區(qū)域的搜索算法）來(lái)展開(kāi)分析和討論，充分利用圖像運(yùn)動(dòng)的空間域和時(shí)間域的相關(guān)特性，利用初始預(yù)測(cè)矢量和閾值終止標(biāo)準(zhǔn)來(lái)進(jìn)行相關(guān)運(yùn)動(dòng)矢量地求解。改進(jìn)后的算法在搜索中使用小鉆石形、非對(duì)稱十字形以及十二邊形等搜索模板，在保證圖像恢復(fù)質(zhì)量不變的情況下，運(yùn)動(dòng)估計(jì)時(shí)間明顯減少，特別是對(duì)運(yùn)動(dòng)對(duì)象較為劇烈的場(chǎng)合有顯著的效果，編碼效率有了顯著地提高，提高了視頻運(yùn)動(dòng)序列編碼的實(shí)時(shí)性，具有一定的實(shí)用價(jià)值。