基于起點預測的不連續十字形快速搜索算法

收稿日期：2007-11-30；修回日期：2008-03-11

基金項目：國家“863”計劃資助項目（2006AA01Z335）

作者簡介：李會宗（1982-），男，河南新鄉人，碩士研究生，主要研究方向為視頻編/解碼、圖像處理(huizongli@uestc.edu.cn)；陳雷霆（1967-），男，重慶人，教授，博導，博士，主要研究方向為計算機圖形圖像技術；盧光輝（1971-），男，四川鄰水人，副教授，碩導，博士，主要研究方向為計算機網絡、圖形圖像處理；李曉瑜（1984-），女，山東菏澤人，碩士研究生，主要研究方向為數字多媒體技術、DSP開發、視頻編/解碼技術*

（電子科技大學 計算機科學與工程學院，成都 610054）

摘 要：提出了一種基于起點預測的不連續十字形塊搜索算法。該算法首先利用圖像幀的時間相關性和空間相關性預測出一個點作為不連續十字形搜索模板的初始中心點，再根據運動矢量概率分布的中心十字偏置特性，采用不連續十字形搜索模型，對運動矢量進行估計，得出最佳運動估計結果。在保證圖像質量的前提下，該搜索算法與完全搜索算法(FS)、三步搜索算法（TSS）和鉆石搜索算法（DS）相比，搜索速度顯著提高。

關鍵詞：塊匹配；運動估計；不連續十字形搜索；視頻編/解碼

中圖分類號：TP391

文獻標志碼：A

文章編號：1001-3695(2008)10-2929-03

Discrete cross fast search algorithm based on initial search point prediction

LI Hui-zong，CHEN Lei-ting， LU Guang-hui， LI Xiao-yu

(School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)

Abstract:This paper analyzed the spatial and temporal correlation of motion trend of the current block， studied the motion vector distribution， and proposed a novel adaptive discrete cross-search algorithm based on initial search point prediction. It utilized a novel initial pixel point selection strategy to improve the accuracy while keeping the computation cost less than other conventional algorithm. Experiments show that the algorithm is able to fit for all types of video sequences adaptively in spite of the degree of the motions，and it is better than the traditional fast motion estimation algorithms such as FS， TSS， and DS， in terms of speed and quality.

Key words：block-matching(BM); motion estimation; discrete cross-search; video codec

0 引言

視頻序列中包含大量的信息，如果不對這些信息進行處理就存儲或傳遞是很消耗資源的，因此對視頻序列進行壓縮處理就成為一個熱門話題。由于連續的運動圖像序列的各鄰近幀之間有時間冗余，可以運用運動估計對圖像進行數據壓縮。運動估計有很多種方法，塊匹配[1]就是其中的一種。塊匹配運動估計理論簡單且實現方便，現在大多數圖像壓縮標準如ITU-T H.26L、MPEG-1\\MPEG-2等都采用塊匹配方法進行運動估計。這種算法的主要思想就是把當前幀分成M×N個宏塊(MB)，然后以MB為單位，以一個預先定義的匹配標準為參考，并在以參考幀中相對應塊為中心的搜索區域中進行搜索，尋找一個最佳匹配塊，當前塊與最佳匹配塊之間的偏移為該塊的運動向量(MV)。在塊匹配運動估計中比較經典的算法有全局搜索算法（FS）、三步[2]搜索算法、四步[2]搜索算法和菱形搜索算法[3]等。在這些搜索算法中，FS最直接明了且效果最優，它比較搜索窗口內的所有像素點，最后得出最佳參考塊，但是FS計算量太大，搜索速度非常慢，不宜實際運用；三步搜索算法在減少計算量方面效果顯著，但由于搜索步長的原因，容易陷入局部最小而導致匹配精度很差；菱形搜索算法利用了運動矢量的中心偏置特性，在保證圖像質量的同時，使得計算量明顯減少，提高了搜索速度，但這種算法仍然存在不足，它雖然考慮了運動矢量的中心分布特性，但忽略了運動矢量的另外一個特性，即運動矢量在水平和垂直方向的分布概率遠大于其余方向。為了更好地提高運動估計的速度與精度，本文充分利用運動向量的分布特性，并結合起始點預測策略，提出了一種新的自適應塊匹配運動估計搜索算法，與一些經典搜索算法進行了比較。實驗證明本算法進一步縮短了運動搜索的時間和次數，并且圖像質量接近FS算法。

1 運動矢量的分布特性

人們對現實視頻序列進行深入研究后發現，視頻序列有菱形中心偏移性(DCB)和十字形中心偏移性(CCB)[4]。為了說明這一特性，本文引用文獻[5]中的數據，如表1所示。

表1 平均運動矢量概率分布％垂直半徑水平半徑

通過表中數據可以看到，約有45.44％的運動矢量是零矢量，說明運動矢量具有中心偏置特性；大約有75％的運動矢量分布在半徑為2的水平和垂直方向上，說明運動矢量具有十字形偏置特性。因此，實際中絕大多數圖像序列的運動都很小，其運動矢量分布通常集中在搜索窗的中心位置附近，同時落在水平和垂直方向上的概率遠遠大于其他方向上的概率。利用這些特性，學者們設計出了菱形搜索模板，并提出了菱形搜索算法。與以前的算法相比，該算法的搜索點數目更少，而且還可以獲得更好的效果。

2 本文搜索算法

21 運動估計準則

運動估計的目的就是在搜索區域內尋找與當前塊最匹配的數據塊，這樣就需要一種判斷兩個塊匹配的方法，即需要定義一個匹配準則。塊匹配準則的定義方法將影響運算復雜度和編碼效率。在本文中，塊匹配準則采用絕對差值和（SAD），如式（1）所示：SAD(f2 ， f1(mv)) =∑|f2((x，y)，mv)-

f1(x-mvx，y-mvy)|（1）其中：f2為當前幀：f1為解碼參考幀;mv是候選的運動矢量;mvx和mvy分別是mv在水平和垂直方向上的分量;x、y分別是相應像素點的坐標值。

22 不連續十字形搜索算法

根據運動矢量的分布特性，本文提出了一種不連續十字形搜索算法。該算法充分利用運動矢量的分布特性，集中精力搜索中心區域、水平和垂直方向上的點，從而可以更快地查找到最佳匹配點。下面本算法的搜索步驟如下：

a)在搜索區域內計算水平和垂直方向九個“●”像素點的SAD值，（圖1），求出SAD最小的點。若該點是中心點，則再計算該點周圍上、下、左、右四個點的SAD值（圖2），求出SAD值最小的點，并結束搜索。若該點是十字搜索模型中半徑為2處的點，則跳轉到b)；若該點是十字搜索模型中半徑為4的點，則跳轉到c)。若有搜索點落在搜索區域邊界上面，就取本次搜索點中SAD值最小的點作為最佳匹配點，并結束搜索。

b)以該點為中心，計算周圍矩形區域內的八個像素點的SAD值（圖3），求出SAD值最小的點，結束搜索。

c)以該點為中心，再擴展一個不連續十字形搜索區域（圖3），并跳轉到步驟a)繼續執行。

另外，當搜索范圍超出搜索區域時，就取此次搜索模型的區域內可得點中的SAD值最小的點作為最佳匹配點。

可以看出，本文中的不連續十字形搜索算法優先查找搜索區域內的中心點、水平和垂直方向的像素點，很好地利用了運動矢量的中心偏置特性和運動矢量落于水平、垂直方向的概率大于落在其他方向上的概率的特性。該算法的第二輪搜索補充計算了第一輪搜索所遺漏的點，增加了查找到最佳匹配點的機會，保證了搜索精度，同時減少了計算量，使運動估計的速度得到了提高。

23 起點預測策略

如果能使不連續十字形搜索算法的十字中心點在第一次搜索時就是最佳匹配點（或者靠近最佳匹配點），那么在后續搜索中計算量無疑是十分小的。為了達到這一效果，在上面算法的基礎上增加一個起點預測算法，即對十字搜索模型的初始十字中心點的位置進行預測。

由于視頻序列中對象的運動通常都是剛體運動，屬于一個對象的幾個塊通常有相似的運動矢量，可以利用時間域和空間域中鄰近的已編碼塊的運動矢量來預測當前塊的初始運動矢量，在此稱為預測的矢量（Pred_mv）。為了很好地預測出當前塊的Pred_mv，需要挑選參與預測的塊和定義計算Pred_mv的規則。

對于塊的挑選規則，一般方法是選擇當前塊空間域內的左邊塊、上邊塊和右上塊；在時間域內選擇與當前塊對應位置的塊[6]。預測運動矢量的方法是取上述幾個塊的運動矢量的中值。由于這些方法的思路對矢量的處理過程固定化，不能很好地體現已編碼塊內物體的運動趨勢，使預測出的運動矢量精確度不高。本文采用如下的起點預測方法：

a）塊的選擇原則。被選擇參與預測的塊如圖4所示。其中，A、B和 C屬于當前塊空間域內的左邊、上邊和右上塊；D、E屬于時間域內的塊，并且D塊的位置與當前塊的位置對應，E塊和D塊相鄰。本文的塊選擇原則比以往的策略多了一個E塊，這樣做的優點是可以更充分地利用鄰近塊內對象的運動趨勢信息，使得預測結果精確度更高。

b）計算Pred_mv的規則。Pred_mv的計算規則使用加權計算的方式，具體方法如下：Pred_mv=w1×MVa+w2×MV b+w3×MVc+

w4×MVd+w5×MVe（2）其中：wi是各個運動矢量的權值，權值分配按五個運動矢量的絕對值的大小比例分配；MVa、MVb和MVc分別是塊A、B、C的運動矢量，MVd和MVe分別是塊D和E的運動矢量。若某塊不可得，則設置該塊運動矢量的值為零。

由Pred_mv所指向的點就是預測出來的點，以該點作為不連續十字形搜索算法第一次搜索的中心點展開搜索。采用起點預測算法后，最明顯的優點是可以使運動估計的起始搜索點更接近最佳匹配點，搜索算法只需執行較少的步驟就可以找到合適的匹配塊，從而減少計算量，提高搜索速度。

3 實驗結果

為了驗證本文算法的實際效果，采用以下視頻序列進行實驗：運動較小的Bus序列和運動較劇烈的Stefan序列。Bus序列采用130幀的長度，Stefan序列采用85幀。用來做參照對比的搜索算法為全像素搜索、三步搜索和鉆石搜索?；贏VS編碼標準的RM5.0版本。搜索范圍為16×16。實驗結果如表2、3所示，分別列出了幾種搜索算法的搜索結果，比較的參數指標是最能體現一種搜索算法優劣的平均PSNR值和匹配一個宏塊需要計算的點數。

表2 Bus視頻序列各種算法的比較序列搜索算法PSNR/dB搜索點數目Bus完全搜索33.3822500三步搜索32782631鉆石搜索32891425本文搜索32851345

表3 Stefan視頻序列各種算法的比較序列搜索算法PSNR/dB搜索點數目Stefan完全搜索29.21225.00三步搜索28.6325.53鉆石搜索28.5418.67本文搜索28.8413.81

從表中數據對比可以得出下面結果：

a)在搜索速度方面。對于圖像較為平緩的Bus視頻序列，完全搜索算法需要計算225.00個像素點；三步搜索算法需要計算26.31個像素點；鉆石搜索算法需要計算14.25個像素點；本文提出的算法在保證圖像質量的前提下，只需要計算13.45個像素點，在搜索速度上與FS、TSS算法相比分別提高了約94.0%和48.9%，稍優于DS算法。對于圖像變化比較劇烈的Stefan視頻序列，完全搜索算法需要計算225.00個像素點；三步搜索算法需要計算25.53個像素點；鉆石搜索算法需要計算18.67個像素點；本文提出的搜索算法只需計算13.81個像素點，搜索速度比FS、TSS和DS算法分別提高了93.9%、45.9%和26.0%。

b)在圖像質量方面。對于運動平緩的Bus視頻序列，完全搜索算法的平均PSNR為33.38 dB;三步搜索算法的平均PSNR為32.78 dB;鉆石搜索算法的平均PSNR為32.89 dB;本文算法的平均PSNR為32.85 dB，比全搜索算法低了0.53 dB，與鉆石搜索算法相當，比三步搜索算法高出 0.07 dB。對于運動劇烈的Stefan視頻序列，本文算法比全搜索算法低了0.23 dB，略優于三步搜索算法和鉆石搜索算法。

本文算法采用了起點預測，可以使初始查找點很接近（或者是）最佳匹配點，所以無論是運動劇烈或平緩的序列，都能夠較為精確地查找到最佳匹配塊，同時也減少了計算量。

4 結束語

本文所提出的算法首先進行起點預測，提高了初始搜索點接近最佳匹配點的可能性，減少了搜索量；充分利用了運動矢量的分布特性，可以更快地查找到最佳匹配點；同時，在第一步搜索可以覆蓋較大的面積，能夠更好地避免運動估計中的局部最小情況出現。實驗證明該算法不但適用于畫面運動小的序列，對畫面運動劇烈的序列運動估計的效果也很好。本文的搜索算法也存在不足之處，如不連續十字搜索模型在覆蓋面積大的同時也增加了計算量，起點預測的策略還可以更加靈活一些。今后的工作要朝這個方向努力。

參考文獻：

[1]SUSHMITHA M， RIZKALLA M E， SALAMA P，et al. High speed search algorithms for block-based motion estimation video compression[C]//Proc of International Conference on Computer Engineering and Systems. 2006:308-312.

[2]JING Xuan， CHAU L P. An efficient three-step search algorithm for block motion estimation[J]. IEEE Trans on Multimedia， 2004， 6(3): 435-438.

[3]THAM J Y， RAN GANATH S， RANGATH M， et al. A novel unrestricted center-based diamond search algorithm for block motion estimation[J]. IEEE Trans on Circuits Syst Video Technol， 1998， 8(4): 369-377.

[4]GHANBARI M. The cross-search algorithm for motion estimation[J]. IEEE Trans on Communications， 1990， 38(7): 950-953.

[5]梁燕，劉文研.基于起點預測的自適應快速搜索算法[J].計算機工程，2005，19(31):1-3.

[6]NAM J Y， KWAK J S. New fast-search algorithm for block matching motion estimation using temporal and spatial correlation of motion vector[J]. IEEE Tran on Consumer Electronics， 2000， 46(4): 934-942.