基于SAD優化的運動估計搜索算法研究

易　葵,肖旭青

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

?

基于SAD優化的運動估計搜索算法研究

易葵1,肖旭青2

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

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

關鍵詞：運動估計;塊匹配;搜索算法

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

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

一、塊匹配準則及碼量分配分析

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

(1)

(2)

(3)

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

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

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

二、SAD優化的快速搜索算法

1.搜索起點預測

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

圖1　相鄰塊位置關系圖

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

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

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

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

3.自適應搜索策略

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

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

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

Step1：依據分類準則判斷當前塊運動類型，如果當前塊是靜態或準靜態塊，則進入step2；否則進入step3。

Step2：以SCSP模板進行搜索，如果最小SAD點在SCSP中心，或者最小SAD點的SADs值滿足SADs

Step3：以LCSP模板進行搜索，如果最小SAD點的SADs值滿足SADs

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

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

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

在整個搜索過程，我們加入了搜索排除準則來排除不需要進行匹配運算的塊以減少搜索點數。具體描述如下：

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)

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

三、實驗結果及分析

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

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

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

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

圖3　平均每塊搜索點數ASPB對比

圖4　平均每個象素MSE值AMP對比

四、結論

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

參考文獻：

[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

文獻標識碼：A