一種基于塊匹配的自適應快速運動估計計算法

摘 要：塊匹配運動估計算法是實時視頻編解碼技術的研究重點。為降低視頻編碼中運動估計的計算復雜度，考慮到現實序列運動矢量的分布存在方向性，文章提出了基于塊匹配的自適應快速運動估計算法。該算法在運動估計的初始階段，利用相鄰宏塊間的空間相關性來預測初始搜索點的位置，使搜索起點更接近理想的最優匹配點；在搜索過程中引入具有方向特征的非對稱十字形搜索模型，加快了搜索速度。實驗結果表明該算法具有很好的性能。

關鍵詞：運動估計；非對稱十字形算法；中心偏置；塊匹配

0 引言

降低幀間的冗余是視頻數據壓縮的關鍵，而實現這一步的重要環節是運動估計和運動補償。運動估計的目的在于降低視頻數據的時間冗余。塊匹配算法(BMA)是成功應用于視頻壓縮的運動估計方法之一，它已成為視頻編碼與標準(如ITU-T H.261、H.263、MPEG-1、2、4)中不可缺少的部分。目前，能夠很好地降低幀間冗余的算法是全搜索塊匹配算法，但是該算法由于巨大的計算量而很難滿足實時應用要求。后來出現了許多快速塊匹配算法，如：二維對數法(TDL)、三步搜索法(3SS)、新三步搜索法(N3SS)、四步法(4SS)、基于塊的梯度下降搜索法(BBGDS)、菱形搜索法(DS)以及六邊形搜索算法(HEXBS)等，這些算法或是搜索步長過長或是模型單一，易使搜索陷入局部最小。

最近出現了一種“非對稱十字形搜索(UDCS)”算法，該算法考慮圖像序列的中心偏置特性，在搜索的初始階段采用大、小十字搜索模型。在搜索過程中，該算法還采用非對稱的水平或垂直十字模型以適應現實序列具有對象或場景運動的方向性的特點。由于很好地考慮了中心偏置特性和運動方向性的特點，UDCS在保持圖像質量的前提下大大降低了運動估算的復雜度。本文將該算法的主要思想引入到預測法中，提出了“自適應的非對稱十字形搜索(A-UDCS)”算法。

1 自適應搜索算法

由于運動矢量的概率分布具有中心偏置特性，因此在各種非預測的基于塊的快速運動估計算法中，都是以搜索窗的中心為搜索起點的。然而，“運動矢量概率分布的中心偏置特性”是一個統計結果，它特別適合小運動量的圖像序列，而對于大運動量的圖像序列，其中心偏置特性就比較差。也就是說，有些序列的運動矢量并不一定集中在搜索窗的中心范圍內。圖1(a)是Garden序列的運動矢量(以搜索窗中心為參考中心)概率分布情況。從圖中可以看出，Garden的運動矢量大量集中在(1，0)點(占42.4％)，主要分布在(1，0)點、(2，0)點和(3，0)點(共占77.1％)。運動矢量的概率分布相對(0，0)點整體偏移，搜索窗中心的菱形區域內的運動矢量的分布概率為68.2％，其中心偏置特性比較差。

為了使搜索起點更接近最優匹配點，出現了先預測、再搜索的方法。只要選擇合適的搜索模型和終止準則進行搜索，使用該方法最終可以獲得具有足夠精度的運動矢量。預測法能顯著減少搜索點的數目，降低計算量。圖1(b)是Garden序列的運動矢量(以預測的搜索起點為參考中心)概率分布情況，其運動矢量絕大部分在(0，0)點(占66.2％)、(1，0)點(占10％)及(－1，0)點(占5，3％)，以預測的搜索起點為中心的菱形區域的運動矢量的分布概率為90，7％。由此可見，以預測的搜索起點為參考中心的運動矢量分布的“中心偏置特性”(這里稱之為“預測點偏置特性”)要遠好于以搜索窗中心為參考中心的中心偏置特性。顯然，小運動量圖像序列的預測點偏置特性也好于中心偏置特性，因此，在預測的基礎上進行搜索將比在沒有預測的情況下進行的搜索能更快地獲得最優匹配點。

2 自適應的非對稱十字形搜索算法(A－UDCS)

2．1 搜索起始點和搜索方向的預測

運動對象和場景的整體性和視頻運動的連續性決定了視頻圖像序列在時域和空域里必然存在相關性，因此，在空域預測中可以作以下兩個假設：①相鄰宏塊包含相同的視頻對象或場景；②相鄰的宏塊具有相同或相似的運動特征。根據這兩個假設，當前塊的運動矢量可利用與其相鄰塊的運動矢量來預測。實驗證明，當前宏塊與其左、上、上右三個相鄰宏塊的運動關系最為密切，且使用左、上、上右三個相鄰宏塊的運動矢量的中值來作為當前宏塊的運動矢量的預測值可獲得較佳效果。也就是說，若當前塊相鄰的左、上、上右三宏塊的運動矢量為MV_left、MV_above和MV_above-right，則預測運動矢量MV_ainent可用(1)式表達：

MV_current=median(MV_left，MV_above，MV_above-right) (1)

在預測到起始搜索點之后，進一步確定最小BDM點成為關鍵。由于現實運動序列的運動矢量在整體上呈十字形分布，即其水平運動和垂直運動幾率大，并且具有極強的沿中心水平和垂直軸偏置分布的方向性，因此，可以將宏塊的運動分為水平運動和垂直運動兩個方向。如果在搜索前知道宏塊的運動方向并在搜索過程中使用帶方向性的搜索模型，將會提高搜索效率。圖2(a)是一個水平臂比垂直臂長的搜索模型，稱為水平十字搜索模型(HCSP)，它在水平方向上的移動速度快于垂直方向。將其用于對具有水平運動特征的宏塊的運動估計，既可以加快水平方向上的搜索速度，還可以減少對不必要的點(垂直方向上的點)的匹配，從而減少匹配點的數目。因此，HCSP更適合對具有水平運動特征的運動矢量的搜索。同理，圖2(b)是垂直十字搜索模型(VCSP)，它更適合搜索在垂直方向上的運動矢量。

為了在搜索的初始階段選擇正確的搜索模型，需要先預測宏塊的運動方向。根據當前宏塊與相鄰宏塊間的密切相關性可知，當前宏塊運動方向的預測可由已預測的運動矢量獲得。設預測運動矢量的坐標為MV_cunrent=(V_xV_y)，其與水平直線的夾角為θ(0≤θ＜π/2)，其值可用公式(2)表達。

如果θ小于π/4，則認為當前宏塊的運動方向為垂直方向；如果θ大于或等于π/4，那么當前宏塊在水平方向上運動，屬于水平運動。

2．2 自適應搜索過程

A-UDCS采用三個搜索模型(如圖2)：小十字搜索模型(SCSP)、水平十字搜索模型(HCSP)和垂直十字搜索模型(VCSP)。在本算法中，首先預測出自適應搜索的搜索起點和宏塊的運動方向，然后根據預測的方向選擇適當的搜索模型，在搜索過程中根據次最優點的軌跡糾正預測方向并調整搜索模型直到獲得最優匹配點。A-UDCS的具體搜索步驟如下：

(1)在搜索的初始階段，通過預測獲得自適應搜索的搜索起點和宏塊的運動方向。根據運動方向(即θ的值)選擇初始搜索模型進行塊匹配。如果為垂直方向，應選擇VCSP；如果為水平方向，則選擇HCSP。進入下一步。

(2)通過匹配獲得最小BDM點，如果該點在中心，則進入第三步；如果該點不在中心，則以最小BDM點為中心，以連續兩個最小BDM點的相對位置關系來重新選擇搜索模型：如果兩個最小BDM點在水平方向上，選擇HCSP；如果兩個最小BDM點在垂直方向上，則選擇VCSP，并重復本步驟。

(3)以最小BDM點為中心，選擇SCSP進行塊匹配，并將得到的最小BDM點視為最優匹配點，自適應搜索結束。搜索過程如圖3所示。

3 實驗結果

實驗使用了多個圖像序列來驗證所提出的算法的性能，包括American(CIF)、Foreman(CIF)、Garden(SIF)及Football(SIF)各100幀。在測試過程中，以平均絕對差和(sAD)作為BDM標準，宏塊大小為16×16，搜索窗口為w＝±7。

表1給出了在不同圖像序列下各種算法的平均搜索點數和各算法相對全搜索算法的搜索速度比。從表中可以看出，A-UDCS比UDCS算法搜索點數少1.032至4.446點，平均少搜索2.94點，相對UDCS算法速度提高26.99％；而A-UDCS比DS算法平均少搜索9.144點，相對DS算法速度提高53.48％。各算法平均搜索點數總體表現為：A-UDCS

4 結束語

與UDCS相比，A-UDCS利用預測法使算法在搜索的初始階段就已接近最優匹配點，減少了進一步搜索點的數目。它與傳統算法的不同點在于，考慮到了現實序列運動矢量分布的方向性，在搜索過程中根據運動特征選擇適當的搜索模型增強了局部搜索的方向性，避免了搜索的盲目性。經測試，A-UDCS比UDCS顯示出更為優良的性能。與DS比較，A-UDCS在降低計算代價的同時，保證了PSNR值(圖像質量)基本不發生明顯的變化，而對運動規律強的序列，A-UDCS表現更好。