基于非對(duì)稱的三步搜索算法的運(yùn)動(dòng)估計(jì)

張 宸, 朱 娟, 王連明, 黃繼鵬

(東北師范大學(xué) 物理學(xué)院, 吉林 長(zhǎng)春 130024)

運(yùn)動(dòng)估計(jì)是視頻壓縮的核心技術(shù), 視頻壓縮目前在手機(jī)電視、數(shù)字衛(wèi)星廣播、數(shù)字視頻存儲(chǔ)等方面得到了普遍應(yīng)用.在視頻壓縮編碼中, 視頻圖形序列中存在大量的時(shí)間和空間冗余,為了減少時(shí)間冗余, 在視頻編碼標(biāo)準(zhǔn)中采用了基于塊匹配的運(yùn)動(dòng)估計(jì)和運(yùn)動(dòng)補(bǔ)償技術(shù)[1]. 在運(yùn)動(dòng)估計(jì)過(guò)程中首先要進(jìn)行匹配搜索,搜索的對(duì)象是宏塊, 現(xiàn)有的搜索算法中全搜索算法是最佳塊匹配的搜索方法, 但是全搜索的搜索時(shí)間很長(zhǎng). 由于運(yùn)動(dòng)估計(jì)在視頻壓縮中占了很大一部分, 為了更好更快地完成運(yùn)動(dòng)估計(jì)的過(guò)程,減少運(yùn)動(dòng)估計(jì)的計(jì)算量, 同時(shí)又能保證一定的視頻質(zhì)量, 有很多算法可以選擇,其中具有代表性的有二維對(duì)數(shù)搜索法(two-dimensional logarithm)[2-3]、三步搜索法(three step search)、新三步搜索法(new three step search )[4]、四步搜索法(four-step search)[5], 菱形搜索法(diamond search)[6]、六邊形搜索算法(hexagon search)[7]等.其中,三步搜素算法因其簡(jiǎn)單快捷的優(yōu)點(diǎn)得到大量應(yīng)用, 同時(shí),人們針對(duì)不同的場(chǎng)合對(duì)三步搜索算法也做了一些改變. 例如, 2002年楊清永等人提出將傳統(tǒng)的三步搜索算法中的前兩步的搜索步長(zhǎng)減半, 解決了傳統(tǒng)三步搜索算法小運(yùn)動(dòng)估計(jì)效果差等問(wèn)題[8].2003年文俊等人在分析運(yùn)動(dòng)向量場(chǎng)的空間和時(shí)間相關(guān)性后, 提出對(duì)傳統(tǒng)三步搜索算法的改進(jìn)[9]. 2016年張長(zhǎng)帥等人提出基于模糊邏輯的三步搜索算法, 將三步搜索算法與模糊理論進(jìn)行結(jié)合, 對(duì)三步搜索算法進(jìn)一步優(yōu)化[10].盡管近年來(lái)的優(yōu)化算法層出不窮, 算法越來(lái)越完善, 但仍有可進(jìn)步的空間.

以往的一些算法沒(méi)有關(guān)注到運(yùn)動(dòng)矢量的中心偏置特性,也沒(méi)有分析運(yùn)動(dòng)矢量分布的方向性,因此存在搜索精度低,搜索點(diǎn)數(shù)多等問(wèn)題.本文提出將三步搜索算法與非對(duì)稱十字形搜索結(jié)合,進(jìn)行并行運(yùn)算,減少搜索點(diǎn),提高編碼效率,使算法得到進(jìn)一步完善.

1 視頻壓縮基本原理

1.1 運(yùn)動(dòng)估計(jì)

在H.264視頻壓縮標(biāo)準(zhǔn)中, 最小的劃分單元是宏塊, 所有的編碼解碼流程都是以宏塊為單位進(jìn)行運(yùn)算的. 運(yùn)動(dòng)估計(jì)主要包括搜索和矢量運(yùn)算兩部分, 首先將一幀圖像分成若干宏塊, 這些宏塊互相不重疊. 然后根據(jù)空間相關(guān)性可以在當(dāng)前幀的前一幀或者前幾幀找到與當(dāng)前塊最匹配的塊, 這一過(guò)程就是搜索過(guò)程, 需要用到一些搜索方法, 在給定的搜索窗口里, 根據(jù)某些匹配原則進(jìn)行搜索運(yùn)算, 找到最佳匹配塊. 最后,根據(jù)當(dāng)前塊的位移和最佳匹配塊的位移得到相對(duì)位移, 相對(duì)位移也就是運(yùn)動(dòng)矢量(motion estimation, MV)[11]. 到此運(yùn)動(dòng)估計(jì)過(guò)程已經(jīng)完成, 接下來(lái)就是對(duì)運(yùn)動(dòng)矢量進(jìn)行編碼. 簡(jiǎn)單地說(shuō), 運(yùn)動(dòng)估計(jì)就是研究如何又快又好地找到最佳匹配塊的同時(shí)計(jì)算出MV.

1.2 塊匹配原則

數(shù)字圖像中的圖片都是以矩陣的形式存在,每一幀圖像都由許許多多的像素點(diǎn)構(gòu)成,然而在人的視覺(jué)中,這些像素點(diǎn)則是一幅完整的圖片.這種圖像像素概念為塊匹配技術(shù)帶來(lái)了便利性.為了搜索出與當(dāng)前塊最匹配的塊,比較常用的幾種塊匹配準(zhǔn)則有MSE(mean square error)法、MAD(mean absolute difference/error)法、NCCF(normalized cross-correlation function)法等,由于SAD(sum of absolute differences)法的運(yùn)算量相對(duì)較少,本文選擇SAD算法進(jìn)行匹配.

式中: (i,j)為運(yùn)動(dòng)矢量;f和fref分別為當(dāng)前幀和參考幀的像素值;M,N為宏塊的尺寸,各匹配準(zhǔn)則值最小時(shí)的(i,j)為最佳運(yùn)動(dòng)矢量. MSE算法精度最高, 運(yùn)算量最大, MAD算法和SAD算法精度相同, SAD算法運(yùn)算量更小, 只涉及減法和求絕對(duì)值的運(yùn)算. 一般選擇SAD作為匹配準(zhǔn)則.

2 三步搜索算法

2.1 傳統(tǒng)的三步法

三步法(three step search, TSS)因其簡(jiǎn)單,在可視電話和會(huì)議電視等低速率視頻編碼中被廣泛使用.傳統(tǒng)的三步搜索算法的流程為:第一步,以當(dāng)前塊中心為搜索起點(diǎn),在距離搜索起點(diǎn)為4的位置劃分出一個(gè)8×8的搜索窗口,然后如圖1所示,標(biāo)識(shí)為1的9個(gè)點(diǎn)就是第一步搜索的點(diǎn),根據(jù)匹配原則在9個(gè)點(diǎn)中找出最佳匹配塊;第二步,將上一步的最佳匹配塊的中心設(shè)為起點(diǎn),然后在距離起點(diǎn)為2的位置劃分一個(gè)4×4的搜索范圍,圖中標(biāo)識(shí)為2的8個(gè)點(diǎn)就是第二步要搜索的點(diǎn),此時(shí)的步長(zhǎng)為2,搜索到最佳匹配塊后進(jìn)入第三步;第三步將上一步的最佳匹配塊中心設(shè)為起點(diǎn),然后在距離起點(diǎn)距離為1的位置劃分出一個(gè)2×2的搜索范圍,這時(shí)搜索步長(zhǎng)為1,圖中標(biāo)識(shí)為3的點(diǎn)就是最后要搜索的8個(gè)點(diǎn),根據(jù)匹配原則找到最佳匹配塊并記下此點(diǎn)位移,最后根據(jù)此點(diǎn)位置與第一步的搜索中心位置求出相對(duì)位移,這個(gè)相對(duì)位移就是運(yùn)動(dòng)矢量.

圖1 傳統(tǒng)三步搜索算法Fig.1 Traditional TSS algorithm

2.2 非對(duì)稱三步算法

經(jīng)大量研究數(shù)據(jù)表明,運(yùn)動(dòng)矢量具有中心偏置特性.因?yàn)?無(wú)論視頻運(yùn)動(dòng)劇烈或者緩慢,相鄰的兩幀圖像之間的運(yùn)動(dòng)還是很小,所以,運(yùn)動(dòng)矢量大部分都是集中在搜索中心附近的.在對(duì)多種視頻圖像序列進(jìn)行多次試驗(yàn)后,可以發(fā)現(xiàn)運(yùn)動(dòng)矢量大部分是按照“十”字形來(lái)分布的,為了驗(yàn)證這一分布特性,對(duì)圖2中的m,n,p,q四點(diǎn)的運(yùn)動(dòng)矢量進(jìn)行測(cè)試,測(cè)試結(jié)果如表1所示.

圖2 像素位置示意圖Fig.2 Pixel position map

由表1可知,絕大多數(shù)的像素運(yùn)動(dòng)矢量位于m,n,p,q點(diǎn)處,也就是說(shuō)運(yùn)動(dòng)矢量概率以十字形分布,因此本文將十字搜索與三步搜索結(jié)合.

表1 像素運(yùn)動(dòng)矢量分布特征統(tǒng)計(jì)Table 1 Pixel motion vector distribution statistics %

運(yùn)動(dòng)矢量具有方向性,自然圖像序列的水平運(yùn)動(dòng)要高于垂直運(yùn)動(dòng).根據(jù)這兩個(gè)特性提出了非對(duì)稱十字搜索方法.再結(jié)合運(yùn)動(dòng)矢量的中心偏置特性,本文先搜索起點(diǎn)附近的較小區(qū)域.在三步搜索算法中,一共需要匹配9+8+8=25次,而在本文中,需要判斷匹配點(diǎn)是否在水平方向上,所以匹配次數(shù)為9+8=17次,9+10=19次,或9+10+8=27次.這樣數(shù)據(jù)的處理時(shí)間就大幅減少了,提高了搜索效率.

在傳統(tǒng)的三步算法中,都是以中心點(diǎn)為標(biāo)準(zhǔn)進(jìn)行正方形范圍內(nèi)的串行式搜索,這種搜索雖然比全搜索好很多,但是依然會(huì)產(chǎn)生很多的搜索點(diǎn).又因?yàn)榈谝徊降乃阉鞣秶?沒(méi)有充分考慮到中心偏置特性,直接將最佳匹配點(diǎn)的位置擴(kuò)遠(yuǎn)了.在大量的統(tǒng)計(jì)中可以看到在自然的圖像序列中,圖像的水平運(yùn)動(dòng)明顯要比垂直方向的運(yùn)動(dòng)要?jiǎng)×襕12],因此可以增加水平方向的搜索點(diǎn),將傳統(tǒng)的三步搜索算法與非對(duì)稱十字搜索結(jié)合,進(jìn)行并行搜索,如圖3所示,改進(jìn)的三步搜索算法主要步驟如下.

(1) 進(jìn)行傳統(tǒng)三步搜索,按步長(zhǎng)為4進(jìn)行8個(gè)點(diǎn)的搜索,同時(shí)并行非對(duì)稱十字搜索,也就是在水平方向上增加步長(zhǎng)為2的兩個(gè)搜索點(diǎn).所以第一步為圖3中實(shí)心黑點(diǎn).

(2) 在第(1)步的搜索點(diǎn)中選出最佳匹配點(diǎn),計(jì)算位移進(jìn)行判斷.如果豎直方向位移為0,進(jìn)行第(3)步;否則,進(jìn)行第(4)步.

(3) 此時(shí)匹配點(diǎn)在水平方向上,接下來(lái)進(jìn)行步長(zhǎng)為1的搜索,需要搜索8個(gè)點(diǎn).加上本身一共9個(gè)點(diǎn),找出最佳匹配點(diǎn).就是最后要找的匹配點(diǎn).

(4) 此時(shí)匹配點(diǎn)在其他位置,然后按步長(zhǎng)為2進(jìn)行8個(gè)點(diǎn)搜索,同時(shí)并行非對(duì)稱十字搜索,在水平方向上增加步長(zhǎng)為1的兩個(gè)搜索點(diǎn),為圖3中右下角空心圓部分.

(5) 同樣對(duì)最佳匹配點(diǎn)進(jìn)行判斷.如果豎直方向位移為0,則匹配點(diǎn)為最后匹配點(diǎn).否則進(jìn)行第(6)步.

(6) 對(duì)這時(shí)的匹配點(diǎn)進(jìn)行步長(zhǎng)為1的8個(gè)點(diǎn)搜索,找出最后的匹配點(diǎn).

圖3 改進(jìn)的三步搜索算法Fig.3 Improved TSS algorithm

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

在Windows 7,MATLAB 2016軟件平臺(tái)中用標(biāo)準(zhǔn)運(yùn)動(dòng)序列stefan_cif、foreman_part_qcif、carphone_qcif等進(jìn)行運(yùn)動(dòng)估計(jì),來(lái)驗(yàn)證全搜索算法、傳統(tǒng)三步搜索算法、改進(jìn)的三步搜索算法的性能.以stefan_cif圖像序列為例,其中圖4圖5為相鄰的兩幀圖像,圖6是兩幀圖像的幀間差值,圖7是在全搜索、傳統(tǒng)三步搜索、改進(jìn)的三步搜索3種不同的搜索算法下的匹配差值.圖8是3種搜索算法恢復(fù)圖像的對(duì)比.從壓縮算法解碼后的效果看,3種壓縮算法圖像均不失真.

圖4 第一幀圖像Fig.4 The first frame

全搜索算法是所有算法中精度最高,但是耗時(shí)最長(zhǎng),最復(fù)雜的一種搜索算法,其核心思想是要遍歷圖像中的每一點(diǎn),因此全搜索算法搜索點(diǎn)數(shù)最多.實(shí)驗(yàn)中,在算法部分增加了對(duì)搜索點(diǎn)數(shù)的計(jì)數(shù)功能,統(tǒng)計(jì)3種算法的搜索點(diǎn)數(shù),得到表2.從表2中可以看出3組圖像的全搜索算法的搜索點(diǎn)數(shù)明顯大于后2種算法,通過(guò)計(jì)算可得,本文的搜索算法的搜索點(diǎn)數(shù)比全搜索算法平均減少了89%,比傳統(tǒng)的三步搜索平均減少了6.5%.

圖5 第二幀圖像Fig.5 The second frame

圖6 幀間差值Fig.6 Frame difference

圖7 3種算法的匹配差值Fig.7 Matching difference of the three algorithms(a)—全搜索算法; (b)—傳統(tǒng)三步搜索算法; (c)—本文算法.

圖8 3種算法恢復(fù)后的第二幀圖像Fig.8 Images of the second frame after the recovery of three algorithms(a)—全搜索算法; (b)—傳統(tǒng)三步搜索算法; (c)—本文算法.

表2 搜索點(diǎn)數(shù)對(duì)比表Table 2 Search point comparison table

表3 算法時(shí)間對(duì)比表Table 3 Search time comparison table s

將3種算法的搜索時(shí)間進(jìn)行了比較,如表3.從表3中可以看出本文的搜索算法的搜索時(shí)間比全搜索算法平均減少了67%,比傳統(tǒng)的三步搜索平均減少了40%.

通過(guò)表2表3可以初步判定本文的算法在時(shí)間和搜索點(diǎn)數(shù)上是有優(yōu)勢(shì)的,但是,這種優(yōu)勢(shì)可能會(huì)導(dǎo)致匹配不到最佳塊,因此重構(gòu)出的圖像質(zhì)量會(huì)降低.為了對(duì)本文算法進(jìn)行驗(yàn)證,在算法中引入一種評(píng)價(jià)圖像的客觀標(biāo)準(zhǔn)----峰值信噪比(PSNR).它是原圖像與被處理圖像之間的均方誤差(式2)相對(duì)于某個(gè)數(shù)的對(duì)數(shù)值,單位是dB,見(jiàn)式3.其中,(i,j)為運(yùn)動(dòng)矢量,MSE為均方誤差,m、n為圖像尺寸.I和K分別為原圖像和現(xiàn)圖像像素點(diǎn)的灰度值.

(3)

由表4可以看出3種算法的信噪比相差不大,可以認(rèn)為3種方法重構(gòu)出的圖像的圖質(zhì)量相當(dāng).但是由于本文算法在搜索點(diǎn)數(shù)和搜索時(shí)間上有優(yōu)勢(shì),所以總體來(lái)看本文算法優(yōu)于全搜索算法和傳統(tǒng)的三步搜索算法.

表4 峰值信噪比對(duì)比表Table 4 PSNR comparison table dB

4 結(jié) 論

本文在傳統(tǒng)的三步搜索算法上結(jié)合了非對(duì)稱十字搜索,將傳統(tǒng)的串行運(yùn)算三步算法進(jìn)行并行運(yùn)算,同時(shí)采用經(jīng)典的圖像序列,將全搜索算法、傳統(tǒng)的三步搜索算法、本文的搜索算法在各方面進(jìn)行對(duì)比.在信噪比變化不大的情況下,本文的算法要比其他兩種算法的搜索點(diǎn)數(shù)少,降低了搜索時(shí)間,從而提高了編碼效率.