用于快速塊運(yùn)動(dòng)估計(jì)的多方向鉆石搜索算法*

陰法明

(南京信息職業(yè)技術(shù)學(xué)院，南京 210013)

由于視頻序列的相鄰幀間具有很高的時(shí)間相關(guān)性，視頻編碼系統(tǒng)可以通過降低時(shí)間冗余度而獲得高壓縮率。幀間編碼利用前面的幀(或參考幀)預(yù)測(cè)當(dāng)前幀，降低連續(xù)幀間的時(shí)間冗余度。運(yùn)動(dòng)估計(jì)是幀間編碼的核心技術(shù)。相比于其他運(yùn)動(dòng)估計(jì)算法，塊匹配技術(shù)因?yàn)槠浜?jiǎn)單性與易于實(shí)現(xiàn)性，而被廣泛應(yīng)用于許多視頻編碼標(biāo)準(zhǔn)中，如MPEG2、H.26x。在塊匹配技術(shù)中，每幀都被劃分成塊，每塊都對(duì)應(yīng)一個(gè)運(yùn)動(dòng)矢量。運(yùn)動(dòng)預(yù)測(cè)通過搜索為當(dāng)前幀的每個(gè)塊產(chǎn)生一個(gè)運(yùn)動(dòng)矢量，它指向參考幀中的最佳匹配塊。該最佳匹配塊作為當(dāng)前塊的預(yù)測(cè)值。

全搜索(Full Search，F(xiàn)S)塊匹配算法是最簡(jiǎn)單的，并且性能最好。其缺點(diǎn)是計(jì)算復(fù)雜度大。它搜索參考幀搜索范圍內(nèi)的所有點(diǎn)，從而產(chǎn)生最佳匹配點(diǎn)。如果搜索窗在水平與垂直方向上的最大運(yùn)動(dòng)分量為±W，每塊需要搜索的點(diǎn)數(shù)為(2W+1)2。為了降低計(jì)算復(fù)雜度，快速搜索算法成為人們研究的重點(diǎn)?，F(xiàn)在，典型的快速算法有3 步搜索(TSS)［1］、新3 步搜索(NTSS)［2］、4 步搜索(FSS)［3］、基于塊的梯度下降搜索(BBGDS)［4］、鉆石搜索(DS)［5］、1 次1 步搜索法(One-at-a-time Search，OTS)［6］等。

TSS 由3 步組成，每步包含均勻空間分布的9個(gè)點(diǎn)。并且每步之后，點(diǎn)之間的距離都會(huì)變小，前1步的最佳備選點(diǎn)作為當(dāng)前的中心點(diǎn)。TSS 第1 步采用大搜索模板，使得其在搜索小運(yùn)動(dòng)量塊時(shí)顯得低效。這與現(xiàn)實(shí)視頻序列的運(yùn)動(dòng)矢量的中心偏置特性相矛盾［2］。NTSS 通過在TSS 第1 步的中心點(diǎn)周圍添加8個(gè)點(diǎn)，解決了這一問題。同時(shí)NTSS 允許在第1、第2 步后提前中止搜索，所以其搜索速度比TSS 要快，并且具有較好的搜索質(zhì)量。但對(duì)于擁有大量較大運(yùn)動(dòng)矢量的序列，NTSS 的計(jì)算量要比TSS的大。FSS 搜索質(zhì)量與NTSS 相仿，并優(yōu)于TSS。

本文第1 部分，講解視頻編碼中塊匹配運(yùn)動(dòng)估計(jì)算法的基本原理。DS、OTS 兩種快速搜索算法將在第2 部分中進(jìn)行介紹。第3 部分提出多方向鉆石搜索(MDDS)算法。第4 部分進(jìn)行試驗(yàn)。最后，第五部分對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

1 基于塊的運(yùn)動(dòng)估計(jì)基本原理

塊匹配運(yùn)動(dòng)估計(jì)就是將圖像劃分成許多互不重疊的子塊，并假定子塊內(nèi)的所有象素具有運(yùn)動(dòng)一致性，且只作平移運(yùn)動(dòng)，然后對(duì)當(dāng)前幀圖像的每一子塊(也即宏塊)，在參考幀的一定范圍內(nèi)按照一定的匹配準(zhǔn)則進(jìn)行匹配，搜索與當(dāng)前子塊最相似的塊，即最佳匹配塊，由最佳匹配塊與當(dāng)前子塊的相對(duì)位置的偏移量，即為當(dāng)前子塊的運(yùn)動(dòng)矢量，如圖1所示。

圖1 基于塊的運(yùn)動(dòng)估計(jì)基本原理

為了判定最佳匹配塊，首先定義塊誤差準(zhǔn)則(Block Distortion Measure，BDM)。本文選擇絕對(duì)誤差和(Sum of Absolute Difference，SAD)作為BDM。其定義如下:

其中，－W≤mx，my≤+W。每個(gè)N×N 塊的左上角在當(dāng)前幀ft中的坐標(biāo)為(p，q)，它通過運(yùn)動(dòng)矢量(mx，my)在重建幀ft－Δt中得到同樣大小塊的預(yù)測(cè)值。

2 基礎(chǔ)算法簡(jiǎn)介

2.1 鉆石搜索算法

DS 算法使用兩種搜索模板:大鉆石搜索模板(Large Diamond Search Pattern，LDSP)與小鉆石搜索模板(Small Diamond Search Pattern，SDSP)，如圖2所示。

圖2 大鉆石搜索模板(LDSP)與小鉆石搜索模板(SDSP)

大鉆石搜索模板由9個(gè)點(diǎn)組成，小鉆石搜索模板則為5個(gè)。該算法步驟如下:

第1 步:將LDSP 放在搜索窗口的中心，計(jì)算模板上每個(gè)點(diǎn)的SAD。如果最小SAD點(diǎn)在LDSP 的中心(c，c)，則跳至第3 步。否則進(jìn)入第2 步。

第2 步:如果上一步的最小SAD點(diǎn)在LDSP 的頂點(diǎn)，如(c－2，c)、(c+2，c)、(c，c－2)或(c，c+2)，則將進(jìn)行頂點(diǎn)搜索。如果上一步的最小SAD點(diǎn)在LDSP 的邊上，如(c－1，c+1)、(c－1，c－1)、(c+1，c+1)或(c+1，c－1)，則進(jìn)行面搜索。

頂點(diǎn)搜索:以上一步的最小SAD點(diǎn)為新的LDSP 的中心，更新中心點(diǎn)(c，c)，并計(jì)算新增五個(gè)點(diǎn)的SAD。例如最小SAD點(diǎn)在(c，c+2)，新的LDSP位置如圖3(a)所示。

面搜索:以上一步的最小SAD點(diǎn)為新的LDSP的中心，更新中心點(diǎn)(c，c)，并計(jì)算新增三個(gè)點(diǎn)的SAD。例如最小點(diǎn)在(c+1，c+1)，新的LDSP 位置如圖3(b)所示。

圖3

如果模板覆蓋的點(diǎn)超出搜索窗的邊界則忽略。當(dāng)新的最小SAD點(diǎn)出現(xiàn)在(c，c)，跳至第3 步。否則，循環(huán)執(zhí)行第2 步。

第3 步:在點(diǎn)(c，c)使用SDSP，計(jì)算最后一個(gè)大鉆石搜索模板內(nèi)部四個(gè)點(diǎn)的SAD。類似，如果備選點(diǎn)超出搜索窗邊界，則忽略。最小的SAD點(diǎn)對(duì)應(yīng)的運(yùn)動(dòng)矢量作為預(yù)測(cè)塊的最終運(yùn)動(dòng)矢量。當(dāng)前塊的搜索過程完成，可以進(jìn)行下一塊的搜索。

2.2 一次一步搜索算法

基于塊的運(yùn)動(dòng)估計(jì)算法OTS 是由R.Srinivasan和K.R.Rao 在1985年首次提出［6］，在水平和垂直方向上先后應(yīng)用OTS 搜索策略。一個(gè)OTS 搜索路徑的例子如圖3所示。首先，搜索窗中心及其水平方向上相鄰的兩個(gè)點(diǎn)先被搜索，即(0，0)、(－1，0)、(1，0)三個(gè)點(diǎn)。如果最小SAD點(diǎn)是搜索窗中心的左邊點(diǎn)(－1，0)，則OTS 向搜索窗左邊執(zhí)行;如果最小SAD點(diǎn)搜索窗中心的右邊點(diǎn)(1，0)，則OTS 向搜索窗右邊執(zhí)行。當(dāng)最小SAD點(diǎn)出現(xiàn)在水平方向3點(diǎn)的中間時(shí)，OTS停止執(zhí)行。該點(diǎn)被看作搜索窗中心水平方向上的最小SAD點(diǎn)，假設(shè)為(s，0)。垂直方向的OTS 于此類似，首先搜索(s，1)、(s，－1)兩點(diǎn)。比較垂直方向上相鄰3點(diǎn)的SAD，如果最小SAD點(diǎn)為(s，1)，OTS 則沿著(s，1)向上執(zhí)行;如果最小SAD點(diǎn)為(s，－1)，OTS 則沿(s，－1)向下執(zhí)行。垂直方向上OTS 終止條件與水平方向上的相同。此時(shí)得到的最小SAD點(diǎn)對(duì)應(yīng)的MV 便是當(dāng)前塊的最終預(yù)測(cè)MV。簡(jiǎn)而言之，OTS 算法在誤差平面上進(jìn)行兩次一維的梯度下降搜索。雖然與其他搜索算法相比，只需要搜索很少的點(diǎn)，但搜索的質(zhì)量很低。因?yàn)橐痪S梯度下降搜索算法不能有效搜索到全局最佳匹配點(diǎn)的位置。

如圖4所示，一個(gè)用OTS 算法搜索的路徑例子，最終得到的最佳匹配點(diǎn)為⑦。

圖4 OTS 算法實(shí)例

3 多方向鉆石搜索算法

DS 算法只考慮塊誤差梯度下降最大的方向，從而降低了得到最佳匹配點(diǎn)為全局最優(yōu)的概率，本文提出了多方向鉆石搜索法。該方法為了考慮到SAD 可能下降的每個(gè)方向，在鉆石搜索法的第1 步之后，對(duì)LDSP 外圍8個(gè)點(diǎn)中小于中心點(diǎn)SAD 的方向上執(zhí)行OTS。

MDDS 算法中，LDSP 對(duì)應(yīng)的8個(gè)方向如圖5所示。

圖5 LDSP 對(duì)應(yīng)的八個(gè)方向

MDDS 算法的運(yùn)行步驟如下:

開始 以搜索窗的中心為起點(diǎn)，開始使用模板LDSP。先計(jì)算LDSP 中心點(diǎn)的SAD，并用中心點(diǎn)信息初始化臨時(shí)最佳匹配點(diǎn)的位置與SAD。

第1 步 計(jì)算LDSP 其它8個(gè)點(diǎn)的SAD。如果有點(diǎn)的SAD 小于中心點(diǎn)的SAD，則在該方向上執(zhí)行OTS。將OTS 后的最小BMD 與臨時(shí)最佳匹配點(diǎn)的SAD 比較，如果小，則更新臨時(shí)最佳匹配點(diǎn)的位置信息與SAD值。如果中心點(diǎn)為最小SAD點(diǎn)，則跳至第3 步。否則進(jìn)行第2 步。

第2 步 以上一步得到的臨時(shí)最佳匹配點(diǎn)為中心，重復(fù)執(zhí)行第1 步。

第3 步 使用SDSP，搜索LDSP 內(nèi)部剩余的4個(gè)點(diǎn)，得到的最小SAD點(diǎn)作為最佳匹配點(diǎn)。

一個(gè)用MDDS 算法搜索的路徑如圖6所示。其中虛線表示檢測(cè)過的SAD 可能下降的方向，實(shí)線表示所選擇的SAD 下降的方向，即每一步得到的最小SAD點(diǎn)。

圖6 MDDS 算法實(shí)例

4 測(cè)試結(jié)果

本文選取的測(cè)試模型為JM，版本為15.1，測(cè)試序列為CIF4:2:0 格式，其中Football、Ice 具有高度空間細(xì)節(jié)與大量運(yùn)動(dòng);Soccer 具有中度空間細(xì)節(jié)和中量運(yùn)動(dòng);Silent、Coastguard 具有中度空間細(xì)節(jié)和少量運(yùn)動(dòng);Flower 具有低度空間細(xì)節(jié)和少量運(yùn)動(dòng)。W 取16，序列長度為100 幀，幀率為30 幀/秒，采用5個(gè)參考幀。序列編碼方式為IPPP…，即第1 幀為I 編碼，剩余99幀采用P 編碼。I 幀的QP(量化參數(shù))設(shè)為36，P 幀的QP為38。幀間編碼只采用16×16 的宏塊。熵編碼方法為基于上下文的二進(jìn)制算術(shù)編碼。相互比較的搜索算法有:FS、NTSS、FSS、BBGDS、DS 與本文提出的MDDS。性能比較的參數(shù)為PSNR 與平均搜索點(diǎn)數(shù)(Average Number of Searched Points，ANSP)。實(shí)驗(yàn)結(jié)果如表1所示。

表1 MDDS 算法與FS、NTSS、FSS、BBGDS、DS 算法測(cè)試結(jié)果 單位:dB

5 小結(jié)

從表1 可以看出，F(xiàn)S 能夠取的最好的搜索質(zhì)量，但其計(jì)算復(fù)雜度太大?？焖偎阉魉惴ㄔ谔岣咚阉魉俣鹊耐瑫r(shí)，很小程度的降低了搜索質(zhì)量?？傮w來說，前四個(gè)快速搜索算法中，BBGDS 搜索速度最快，但質(zhì)量也是最差的;FSS 算法搜索速度比較慢，對(duì)于幀間圖像含有少量運(yùn)動(dòng)的序列性能最好;NTSS 搜索速度最慢，但搜索質(zhì)量最佳，尤其是幀間圖像具有大量運(yùn)動(dòng)和豐富空間細(xì)節(jié)的序列，對(duì)于幀間圖像具有少量運(yùn)動(dòng)的序列性能一般。DS 算法搜索速度僅次于BBGDS 算法，但性能不如FSS 算法與NTSS 算法。

表2 MDDS 算法與DS 性能比較 單位:dB

如表2所示，本文提出的MDDS 搜索速度略低于DS，每個(gè)16×16 宏塊平均多出0.48～1.86個(gè)搜索點(diǎn)，性能有很大提升，PSNR 最多提高了0.07 dB。序列幀間圖像的運(yùn)動(dòng)量越大，空間細(xì)節(jié)信息越豐富，性能相對(duì)提高的越多。對(duì)于幀間圖像含有中量與大量運(yùn)動(dòng)的序列，其性能略次于NTSS 算法;對(duì)于幀間圖像含有少量運(yùn)動(dòng)的序列，性能持平或好于NTSS 算法。因此，該算法在搜索速度與性能上都具有一定的競(jìng)爭(zhēng)優(yōu)勢(shì)。

［1］Koga T，Iinnma K，Hirano A，et al.Motion-Compensated Interframe Coding for Video Conferencing［C］//Nut.Telecommun.Con，pp.G5.3.145.G5(3).145－153.1981.

［2］Li R，Zeng B，Liou M L.A New Three-Step Search Algorithm for Block Motion Estimation［J］.IEEE Trans.Circuits Syst.Video Technol.，1994，4:438－442.

［3］Po L M，Ma W C.A Novel Four-Step Search Algorithm for Fast Block Motion Estimation［J］.IEEE Trans.Circuits Syst.Video Technol.，1996，6:313－317.

［4］Liu L K，F(xiàn)eig E.A Block-Based Gradient Descent Search Algorithm for Block Motion Estimation in Video Coding［J］.IEEE Trans.on Circuits and Systems for Video Technology，1996，6:419－422.

［5］Tham J Y，Ranganath S，Ranganath M，et al.A Novel Unrestricted Center-Biased Diamond Search Algorithm for Block Motion Estimation［J］.IEEE Trans.on Circuits and Systems for Video Technology，1998，8:369－377.

［6］Srinivasan R，Rao K R.Predictive Coding Based on Efficient Motion Estimation［J］.IEEE Trans.Commun.，1985，COM－33:888－896.