陰法明

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

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

全搜索(Full Search，F(xiàn)S)塊匹配算法是最簡單的，并且性能最好。其缺點(diǎn)是計算復(fù)雜度大。它搜索參考幀搜索范圍內(nèi)的所有點(diǎn)，從而產(chǎn)生最佳匹配點(diǎn)。如果搜索窗在水平與垂直方向上的最大運(yùn)動分量為±W，每塊需要搜索的點(diǎn)數(shù)為(2W+1)2。為了降低計算復(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個點(diǎn)。并且每步之后，點(diǎn)之間的距離都會變小，前1步的最佳備選點(diǎn)作為當(dāng)前的中心點(diǎn)。TSS 第1 步采用大搜索模板，使得其在搜索小運(yùn)動量塊時顯得低效。這與現(xiàn)實(shí)視頻序列的運(yùn)動矢量的中心偏置特性相矛盾［2］。NTSS 通過在TSS 第1 步的中心點(diǎn)周圍添加8個點(diǎn)，解決了這一問題。同時NTSS 允許在第1、第2 步后提前中止搜索，所以其搜索速度比TSS 要快，并且具有較好的搜索質(zhì)量。但對于擁有大量較大運(yùn)動矢量的序列，NTSS 的計算量要比TSS的大。FSS 搜索質(zhì)量與NTSS 相仿，并優(yōu)于TSS。

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

1 基于塊的運(yùn)動估計基本原理

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

圖1 基于塊的運(yùn)動估計基本原理

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

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

2 基礎(chǔ)算法簡介

2.1 鉆石搜索算法

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

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

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

第1 步:將LDSP 放在搜索窗口的中心，計算模板上每個點(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)，并計算新增五個點(diǎn)的SAD。例如最小SAD點(diǎn)在(c，c+2)，新的LDSP位置如圖3(a)所示。

面搜索:以上一步的最小SAD點(diǎn)為新的LDSP的中心，更新中心點(diǎn)(c，c)，并計算新增三個點(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，計算最后一個大鉆石搜索模板內(nèi)部四個點(diǎn)的SAD。類似，如果備選點(diǎn)超出搜索窗邊界，則忽略。最小的SAD點(diǎn)對應(yīng)的運(yùn)動矢量作為預(yù)測塊的最終運(yùn)動矢量。當(dāng)前塊的搜索過程完成，可以進(jìn)行下一塊的搜索。

2.2 一次一步搜索算法

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

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

圖4 OTS 算法實(shí)例

3 多方向鉆石搜索算法

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

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

圖5 LDSP 對應(yīng)的八個方向

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

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

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

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

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

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

圖6 MDDS 算法實(shí)例

4 測試結(jié)果

本文選取的測試模型為JM，版本為15.1，測試序列為CIF4:2:0 格式，其中Football、Ice 具有高度空間細(xì)節(jié)與大量運(yùn)動;Soccer 具有中度空間細(xì)節(jié)和中量運(yùn)動;Silent、Coastguard 具有中度空間細(xì)節(jié)和少量運(yùn)動;Flower 具有低度空間細(xì)節(jié)和少量運(yùn)動。W 取16，序列長度為100 幀，幀率為30 幀/秒，采用5個參考幀。序列編碼方式為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 算法測試結(jié)果 單位:dB

5 小結(jié)

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

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

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

［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.