引 言

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

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

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

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

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

1.1 計算提前終止搜索條件的不足

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

1.2 EPZS的搜索模板的不足

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

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

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

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

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

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

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

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

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

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

圖1 搜索模板

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

算法的搜索步驟如下： 

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

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

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

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

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

結(jié) 語

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