一種基于塊匹配的自適應(yīng)快速運(yùn)動(dòng)估計(jì)計(jì)算法

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

關(guān)鍵詞：運(yùn)動(dòng)估計(jì)；非對(duì)稱十字形算法；中心偏置；塊匹配

0 引言

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

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

1 自適應(yīng)搜索算法

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

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

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

2．1 搜索起始點(diǎn)和搜索方向的預(yù)測(cè)

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

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

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

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

如果θ小于π/4，則認(rèn)為當(dāng)前宏塊的運(yùn)動(dòng)方向?yàn)榇怪狈较?；如果θ大于或等于?4，那么當(dāng)前宏塊在水平方向上運(yùn)動(dòng)，屬于水平運(yùn)動(dòng)。

2．2 自適應(yīng)搜索過程

A-UDCS采用三個(gè)搜索模型(如圖2)：小十字搜索模型(SCSP)、水平十字搜索模型(HCSP)和垂直十字搜索模型(VCSP)。在本算法中，首先預(yù)測(cè)出自適應(yīng)搜索的搜索起點(diǎn)和宏塊的運(yùn)動(dòng)方向，然后根據(jù)預(yù)測(cè)的方向選擇適當(dāng)?shù)乃阉髂Ｐ?，在搜索過程中根據(jù)次最優(yōu)點(diǎn)的軌跡糾正預(yù)測(cè)方向并調(diào)整搜索模型直到獲得最優(yōu)匹配點(diǎn)。A-UDCS的具體搜索步驟如下：

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

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

(3)以最小BDM點(diǎn)為中心，選擇SCSP進(jìn)行塊匹配，并將得到的最小BDM點(diǎn)視為最優(yōu)匹配點(diǎn)，自適應(yīng)搜索結(jié)束。搜索過程如圖3所示。

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

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

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

4 結(jié)束語

與UDCS相比，A-UDCS利用預(yù)測(cè)法使算法在搜索的初始階段就已接近最優(yōu)匹配點(diǎn)，減少了進(jìn)一步搜索點(diǎn)的數(shù)目。它與傳統(tǒng)算法的不同點(diǎn)在于，考慮到了現(xiàn)實(shí)序列運(yùn)動(dòng)矢量分布的方向性，在搜索過程中根據(jù)運(yùn)動(dòng)特征選擇適當(dāng)?shù)乃阉髂Ｐ驮鰪?qiáng)了局部搜索的方向性，避免了搜索的盲目性。經(jīng)測(cè)試，A-UDCS比UDCS顯示出更為優(yōu)良的性能。與DS比較，A-UDCS在降低計(jì)算代價(jià)的同時(shí)，保證了PSNR值(圖像質(zhì)量)基本不發(fā)生明顯的變化，而對(duì)運(yùn)動(dòng)規(guī)律強(qiáng)的序列，A-UDCS表現(xiàn)更好。