易　葵,肖旭青

(1.中航工業(yè)南方航空工業(yè)(集團(tuán))有限公司機(jī)動分公司，湖南　株洲　412002；2.株洲市發(fā)展和改革委員會，湖南　株洲　412007)

?

基于SAD優(yōu)化的運(yùn)動估計搜索算法研究

易葵1,肖旭青2

(1.中航工業(yè)南方航空工業(yè)(集團(tuán))有限公司機(jī)動分公司，湖南株洲412002；2.株洲市發(fā)展和改革委員會，湖南株洲412007)

摘要：基于對運(yùn)動估計SAD匹配準(zhǔn)則缺陷和碼量分配原理的分析，本文提出了針對影響運(yùn)動估計效率的三個主要因素：搜索中心預(yù)測、匹配準(zhǔn)則和搜索策略，提出了自適應(yīng)雙十字-鉆石-六邊形搜索算法。實(shí)驗(yàn)結(jié)果表明，該算法在失真度基本保持不變的情況下，搜索速度比MVFAST要提高78%，比PMVFAST要提高5.1%。

關(guān)鍵詞：運(yùn)動估計;塊匹配;搜索算法

在幀間視頻壓縮技術(shù)中，塊匹配運(yùn)動估計因簡單實(shí)用、便于VISL實(shí)現(xiàn)而被MPEG和H.26X標(biāo)準(zhǔn)普遍采用[1～3]，大部分塊匹配算法主要采用SAD作為匹配準(zhǔn)則，只考慮了殘差塊對編碼的影響，忽視了運(yùn)動矢量對編碼的影響，主要目標(biāo)就是搜索SAD值最小的預(yù)測塊。事實(shí)上，SAD最小并不是最佳匹配塊的充分條件，如何快速找到最有利于視頻壓縮的預(yù)測塊才是運(yùn)動估計的根本目標(biāo)。

為此，本文在綜合分析SAD準(zhǔn)則缺陷和碼量分配的基礎(chǔ)上，提出了基于SAD優(yōu)化的快速運(yùn)動估計搜索算法(SOMEA)。其主要思路是：首先利用相鄰塊之間的時空相關(guān)性，預(yù)測搜索起點(diǎn)；其次設(shè)計符合運(yùn)動矢量交叉-中心偏置分布特性的混合搜索模板，通過基于運(yùn)動內(nèi)容靈活處理不同的運(yùn)動塊，使其能夠自適應(yīng)選擇模板進(jìn)行搜索；最后采用高效的搜索中止準(zhǔn)則，平滑運(yùn)動矢量場，減少搜索復(fù)雜度和確保足夠的搜索精度。

一、塊匹配準(zhǔn)則及碼量分配分析

塊匹配算法一般有三種匹配準(zhǔn)則，即絕對差(SAD)、均方差(MSE)和歸一化相關(guān)函數(shù)(NCCF)。

(1)

(2)

(3)

式中，(i,j)為位移矢量，fk,fk-N分別為當(dāng)前幀和參考幀的灰度值，M×N為宏塊大小。由于匹配準(zhǔn)則對匹配精度的影響不是很大，為降低編碼器的時間開銷，在這三種算法中，不含乘除法的SAD準(zhǔn)則成為最常使用的匹配準(zhǔn)則。然而，運(yùn)動估值的實(shí)時性和精度是相互矛盾的，SAD準(zhǔn)則雖然運(yùn)算量最小，但是用該方法尋求最佳匹配塊存在較大的誤差，可能導(dǎo)致SAD值最小的匹配塊并非最優(yōu)。例如，存在一個4×4當(dāng)前塊Bcur和兩個參考塊Bref1和Bref2，如下：

另外，在碼率控制作用下，Btotal=Bintra+Binter=Bintra+∑(Binter＿re+Binter＿mv)， 其中Btotal(總編碼量)、Bintra(幀內(nèi)編碼量)和Binter(幀間編碼量)基本為常數(shù)，Binter＿re(殘差系數(shù)編碼量)和Binter＿mv(運(yùn)動矢量編碼量)相互制約，Binter＿mv增加，Binter＿re則相應(yīng)減少。目前，視頻編碼標(biāo)準(zhǔn)對運(yùn)動矢量通常采用差分編碼方式，運(yùn)動矢量場越均勻，運(yùn)動矢量編碼量就越小。因此，在保證一定匹配精度的前提下，適當(dāng)平滑運(yùn)動矢量場，降低Binter＿mv，使殘差編碼獲得更多的比特數(shù)，進(jìn)而可以提高圖像質(zhì)量。

綜合以上分析可知，在運(yùn)動估計過程中，沒有必要花費(fèi)過多的代價去尋找SAD最小的預(yù)測塊，而通過高效的搜索中止策略，確保足夠的搜索精度，使運(yùn)動矢量場盡量平滑，就有可能獲得更好的視頻壓縮效果。

二、SAD優(yōu)化的快速搜索算法

1.搜索起點(diǎn)預(yù)測

為防止搜索陷入局部最小和有效降低搜索次數(shù)，運(yùn)動估計算法一般都采用起點(diǎn)預(yù)測，使搜索起點(diǎn)距離最佳匹配點(diǎn)足夠近。根據(jù)運(yùn)動物體所具有的整體性和視頻序列的連續(xù)性，可以利用時間和空間方向上的相鄰塊運(yùn)動場預(yù)測當(dāng)前塊的運(yùn)動場，圖1顯示相鄰塊的位置。

圖1　相鄰塊位置關(guān)系圖

文獻(xiàn)[4]闡述了各相鄰塊的預(yù)測效果，指出當(dāng)前塊的運(yùn)動矢量與B1，B2，B3，B4塊的運(yùn)動矢量相關(guān)性最大。綜合考慮計算量和預(yù)測效果等因素，本文選擇這B1，B2，B3，B4，B5塊預(yù)測搜索起始點(diǎn)，預(yù)測公式為：

MVini為預(yù)測的起始點(diǎn)位移，MVBi為Bi塊的運(yùn)動矢量，MVm為B1,B2,B4,B5四個塊運(yùn)動矢量的平均值，T為門限值，SADMVBi為Bi塊的SAD值，SAD0為當(dāng)前塊與B3塊的失真度。我們提出該預(yù)測公式的理論依據(jù)在于：(1)如果B1,B2,B4,B5塊屬于同一運(yùn)動物體，則argminMVBi‖MVBi-MVm‖所預(yù)測的起始點(diǎn)將非?？拷?dāng)前塊的真實(shí)運(yùn)動位置；如果不屬于同一運(yùn)動物體，那么選擇最小的位移偏差作為預(yù)測的起點(diǎn)，則可以保持運(yùn)動場的中心偏置特性。(2)ifmaxi=1,2,4,5‖MVBi-MVm‖T and SADMVBi?SAD0，通過SAD比較法得到的預(yù)測起點(diǎn)都是相鄰塊的運(yùn)動矢量，這種預(yù)測也有助于使運(yùn)動矢量場具有均勻性。(3)雖然當(dāng)前塊與B3塊的運(yùn)動矢量相關(guān)性大，但是當(dāng)運(yùn)動物體突然改變運(yùn)動方向，或者運(yùn)動速度不穩(wěn)定時，把B3的運(yùn)動矢量放入公式(4.1)中，將會帶來較大的預(yù)測誤差。所以我們僅把B3放入(4.2)中考慮。(4)由于零矢量非常有利于編碼效率的提高，在起點(diǎn)預(yù)測時對它給予一定的傾斜。

2.雙十字-鉆石-六邊形搜索模板

經(jīng)過搜索起點(diǎn)預(yù)測后，一般情況下，匹配塊運(yùn)動矢量將非常接近MVini。為此，我們提出的雙十字-鉆石-六邊形混合搜索模板的基本搜索步長為1，具體描述如圖2，其基本思想主要來源文獻(xiàn)[5,6]的結(jié)論：(1)運(yùn)動矢量具有中心偏置特性；(2)運(yùn)動矢量的概率分布是以(0，0)點(diǎn)為中心遞減的；(3)運(yùn)動矢量分布具有交叉偏置特性。

3.自適應(yīng)搜索策略

視頻序列中不同區(qū)域的運(yùn)動劇烈程度往往不同，本文算法首先對當(dāng)前塊進(jìn)行分類，分類準(zhǔn)則為：(1)如果MVB1=MVB2=MVB4=MVB5，或者maxi=1,2,4,5‖MVBi-MVm‖?2，則稱之為靜態(tài)或準(zhǔn)靜態(tài)塊(stationaryorquasi-stationaryblock)；(2)否則，稱之為動態(tài)塊。

圖2　又十字—鉆石—六邊形搜索模板

其次，設(shè)置早期搜索終止準(zhǔn)則。為提高運(yùn)動估計速度，許多快速算法常采用SAD閾值作為搜索終止條件。由于當(dāng)前塊的SAD值與前一幀相同位置塊的SADB3值具有很強(qiáng)的相關(guān)性，本文選擇SAD

Step1：依據(jù)分類準(zhǔn)則判斷當(dāng)前塊運(yùn)動類型，如果當(dāng)前塊是靜態(tài)或準(zhǔn)靜態(tài)塊，則進(jìn)入step2；否則進(jìn)入step3。

Step2：以SCSP模板進(jìn)行搜索，如果最小SAD點(diǎn)在SCSP中心，或者最小SAD點(diǎn)的SADs值滿足SADs

Step3：以LCSP模板進(jìn)行搜索，如果最小SAD點(diǎn)的SADs值滿足SADs

Step4：如果LCSP搜索得到的最小SAD點(diǎn)在(0±1),或(±1，0)，如圖2(c)所示，搜索最靠近Step3最小SAD點(diǎn)的兩個點(diǎn)，也就是位于四個候選點(diǎn)(±1，±1)中的兩個點(diǎn)，如果這一步得出的新的最小SAD點(diǎn)和step3得出的一致，或者SADs

Step5：以Step4獲得的最小SAD點(diǎn)作為新的HHSP(或VHSP)模板中心進(jìn)行搜索，如果搜索得到最小SAD點(diǎn)位于新的HHSP(或VUHSP)中心，則進(jìn)入step6；否則，這循環(huán)搜索。

Step6：用上一步找到的最小SAD點(diǎn)作為新的SCSP模板中心，搜索最小的SAD點(diǎn)作為運(yùn)動矢量的最終解。

在整個搜索過程，我們加入了搜索排除準(zhǔn)則來排除不需要進(jìn)行匹配運(yùn)算的塊以減少搜索點(diǎn)數(shù)。具體描述如下：

fk(m,n)-fk-Ns(m+i,n+j)?|fk(m,n)-fk-Ns(m+i,n+j)|

(5)

fk-Ns(m,n)-fk(m+i,n+j)?|fk(m,n)-fk-Ns(m+i,n+j)|

(6)

對(5)、(6)兩式的兩邊分別求累加和，可得

C-R(i,j)?SAD(i,j)

(7)

R(i,j)-C?SAD(i,j)

(8)

C-SAD(i,j)?R(i,j)?C+SAD(i,j)

(9)

在實(shí)際搜索過程中，只有候選塊R(i,j)滿足式(9)時才有必要進(jìn)行計算，否則不予考慮，這樣就大大降低了計算的復(fù)雜度。

三、實(shí)驗(yàn)結(jié)果及分析

為了評估本文提出的SOMEA算法性能，我們選擇100幀Qcif序列Football、Coastguard和Mother_daughter進(jìn)行實(shí)驗(yàn)仿真。三個序列分別代表了不同類型的運(yùn)動，F(xiàn)ootball序列運(yùn)動變化劇烈，Coastguard序列的運(yùn)動變化平穩(wěn)，Mother_daughter序列只有部分區(qū)域運(yùn)動。實(shí)驗(yàn)參數(shù)設(shè)置如下：塊尺寸16×16,搜索窗±16，T=7，t1=0.95，t2=1.07。

Table1和Table2分別列出了不同算法針對不同序列的平均每塊搜索點(diǎn)數(shù)(ASPB)、速度提升比率(SIP)和平均每個像素MSE值(AMP)、MSE降低比率(DM)。從中可以清楚看到：(1)本文提出的算法與MPEG4推薦的兩種算法MVFAST和PMVFAST相比，在MSE基本保持不變的情況下，平均SIP分別提升了78%和5.1%。(2)本算法對于包含平穩(wěn)運(yùn)動和靜止背景的視頻序列，其性能提升要好于運(yùn)動劇烈的視頻序列，主要原因在于運(yùn)動劇烈使得前后幀相關(guān)度急劇下降，導(dǎo)致SAD

表1　平均每塊搜索點(diǎn)數(shù)(ASPB)和速度提升比率(SIR%)

表2　平均每像素均方差(AMP)和MSE降低比率(DMSE%)

圖3　平均每塊搜索點(diǎn)數(shù)ASPB對比

圖4　平均每個象素MSE值A(chǔ)MP對比

四、結(jié)論

本文在分析傳統(tǒng)的SAD塊匹配準(zhǔn)則和碼量分配對編碼質(zhì)量的影響的基礎(chǔ)上，提出了一種新基于SAD優(yōu)化的運(yùn)動估計算法(SOMEA)。該算法根據(jù)視頻運(yùn)動的相關(guān)性，綜合運(yùn)動矢量場中心偏置特性與SAD比較法從當(dāng)前塊的時空位置相鄰塊的運(yùn)動矢量中選擇最佳的初始運(yùn)動矢量；利用簡單的運(yùn)動分類準(zhǔn)則和搜索轉(zhuǎn)移條件，自適應(yīng)選擇搜索模式，并在搜索過程中加入搜索終止閾值和搜索排除準(zhǔn)則，使搜索結(jié)果具有足夠的精度和較低的復(fù)雜度。實(shí)驗(yàn)結(jié)果顯示，本文算法在MSE基本保持不變的基礎(chǔ)上，獲得了比MVFAST和PMVFAST更高的搜索速度。

參考文獻(xiàn)：

[1]HonglunJia.Anewcrossdiamondsearchalgorithmforblockmotionestimation,IEEEInternationalConference.ICASSP, 2004,3(5):17～21.

[2]Ma.K.K.Performancereportofmotionvectorfieldadaptivesearchtechnique(MVFAST)[S].In:ISO/IECJTC1/SC29/WG11MPEG99/m5851,Noordwijkerhout,NL, 2000,(3).

[3]Tourapis.A.M.Fastblock-matchingmotionestimationusingpredictivemotionvectorfieldadaptivesearchtechnique(PMVFAST)[S].In:ISO/IECJTC1/SC29/WG11MPEG2000/N3324,Noordwijkerhout,NL, 2000,(3).

[4]C.Hsieh.Motionestimationalgorithmusinginterblockcorrelation[J].Electron,1990,26(3):276～277.

[5]Chun-Ho.Cheung.Anovelcross-diamondsearchalgorithmforfastblockmotionestimation[J].IEEETrans.CircuitsSyst.VideoTechnol,2002,12(12): 1 168～1 177.

[6]Chun-Ho.Cheung.Novelcross-diamond-hexagonalsearchalgorithmsforfastblockmotionestimation[J].IEEETrans.Multimedia,2002,7(2).

文章編號：2095-4654(2016)05-0018-04

* 收稿日期：2015-12-28

中圖分類號：TN911.73

文獻(xiàn)標(biāo)識碼：A