基于非對稱的三步搜索算法的運動估計

2019-07-05 03:36:50王連明黃繼鵬

沈陽大學學報(自然科學版) 2019年3期

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

(東北師范大學物理學院, 吉林長春 130024)

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

以往的一些算法沒有關注到運動矢量的中心偏置特性,也沒有分析運動矢量分布的方向性,因此存在搜索精度低,搜索點數多等問題.本文提出將三步搜索算法與非對稱十字形搜索結合,進行并行運算,減少搜索點,提高編碼效率,使算法得到進一步完善.

1 視頻壓縮基本原理

1.1 運動估計

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

1.2 塊匹配原則

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

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

2 三步搜索算法

2.1 傳統的三步法

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

圖1 傳統三步搜索算法Fig.1 Traditional TSS algorithm

2.2 非對稱三步算法

經大量研究數據表明,運動矢量具有中心偏置特性.因為,無論視頻運動劇烈或者緩慢,相鄰的兩幀圖像之間的運動還是很小,所以,運動矢量大部分都是集中在搜索中心附近的.在對多種視頻圖像序列進行多次試驗后,可以發現運動矢量大部分是按照“十”字形來分布的,為了驗證這一分布特性,對圖2中的m,n,p,q四點的運動矢量進行測試,測試結果如表1所示.

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

由表1可知,絕大多數的像素運動矢量位于m,n,p,q點處,也就是說運動矢量概率以十字形分布,因此本文將十字搜索與三步搜索結合.

表1 像素運動矢量分布特征統計Table 1 Pixel motion vector distribution statistics %

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

在傳統的三步算法中,都是以中心點為標準進行正方形范圍內的串行式搜索,這種搜索雖然比全搜索好很多,但是依然會產生很多的搜索點.又因為第一步的搜索范圍太大,沒有充分考慮到中心偏置特性,直接將最佳匹配點的位置擴遠了.在大量的統計中可以看到在自然的圖像序列中,圖像的水平運動明顯要比垂直方向的運動要劇烈[12],因此可以增加水平方向的搜索點,將傳統的三步搜索算法與非對稱十字搜索結合,進行并行搜索,如圖3所示,改進的三步搜索算法主要步驟如下.

(1) 進行傳統三步搜索,按步長為4進行8個點的搜索,同時并行非對稱十字搜索,也就是在水平方向上增加步長為2的兩個搜索點.所以第一步為圖3中實心黑點.

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

(3) 此時匹配點在水平方向上,接下來進行步長為1的搜索,需要搜索8個點.加上本身一共9個點,找出最佳匹配點.就是最后要找的匹配點.

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

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

(6) 對這時的匹配點進行步長為1的8個點搜索,找出最后的匹配點.

圖3 改進的三步搜索算法Fig.3 Improved TSS algorithm

3 實驗結果

在Windows 7,MATLAB 2016軟件平臺中用標準運動序列stefan_cif、foreman_part_qcif、carphone_qcif等進行運動估計,來驗證全搜索算法、傳統三步搜索算法、改進的三步搜索算法的性能.以stefan_cif圖像序列為例,其中圖4圖5為相鄰的兩幀圖像,圖6是兩幀圖像的幀間差值,圖7是在全搜索、傳統三步搜索、改進的三步搜索3種不同的搜索算法下的匹配差值.圖8是3種搜索算法恢復圖像的對比.從壓縮算法解碼后的效果看,3種壓縮算法圖像均不失真.

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

全搜索算法是所有算法中精度最高,但是耗時最長,最復雜的一種搜索算法,其核心思想是要遍歷圖像中的每一點,因此全搜索算法搜索點數最多.實驗中,在算法部分增加了對搜索點數的計數功能,統計3種算法的搜索點數,得到表2.從表2中可以看出3組圖像的全搜索算法的搜索點數明顯大于后2種算法,通過計算可得,本文的搜索算法的搜索點數比全搜索算法平均減少了89%,比傳統的三步搜索平均減少了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)—傳統三步搜索算法; (c)—本文算法.

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

表2 搜索點數對比表Table 2 Search point comparison table

表3 算法時間對比表Table 3 Search time comparison table s

將3種算法的搜索時間進行了比較,如表3.從表3中可以看出本文的搜索算法的搜索時間比全搜索算法平均減少了67%,比傳統的三步搜索平均減少了40%.

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