應用于電子穩像的改進塊匹配算法

楊 莉 邵克勇 劉遠紅 白麗麗 張會珍

(東北石油大學電氣信息工程學院，黑龍江 大慶 163318)

電子穩像是一種利用圖像處理手段實現視頻去抖的技術。經典電子穩像過程主要包含3部分：運動估計、運動分離和運動補償。其中，運動估計用來檢測視頻幀之間的全局運動矢量。作為穩像過程的第一步，其計算的準確性和速度對后續處理有重要影響。塊匹配(BMA)是電子穩像中常用的運動估計算法,其基本思想是將參考幀圖像分成一定大小的圖像塊，在當前幀中找到各塊的最佳匹配位置，以一定準則去除錯誤匹配，計算得到幀間全局運動矢量。

準確并快速定位最佳匹配位置是塊匹配搜索算法的研究目的。在已有的搜索算法中，基于平均絕對值誤差(MAD)和平均方差(MSE)的全局搜索算法(FS)被認為是塊匹配中最準確的算法[1]。但其缺點是計算量大，難以實時處理。常用的改進算法多是采用減少搜索點的數量來提高速度。比較典型的有三步法(NTSS)[2]、四步法(4SS)[3]及菱形搜索法(Diamond)[4]等。在此基礎上后繼學者又進行了很多改進，如文獻[5,6]中所提出的算法。這些快速搜索算法的主體思想，都是利用圖像運動矢量的中心偏置特性，即越接近最佳匹配位置，匹配誤差越小。在圖像小偏移的情況下，初始搜索位置大多在中心偏置區域內，所得運動估計具有很好的準確性和快速性。然而，在實際穩像應用中，圖像幀的偏移經常超出最小偏置作用區域，造成初始搜索方向不確定，很容易陷入局部最優，產生錯誤運動估計。為處理偏移較大的情況，可以擴大窗口搜索范圍，采用全局搜索方式找到最小匹配誤差的位置，但計算復雜度會大幅增加。針對這一缺陷，筆者提出了一種檢測大偏移運動的擴展搜索算法，綜合了全局搜索的準確性和中心偏置快速性。

1 準備工作①

1.1 塊的選取

圖像偏移過大時，邊緣區域不能在兩幀中重復出現，因此盡量避免將塊選擇在靠近邊緣區域的位置上，故將每幀圖像的四周預留10%的邊界補償區域。

塊匹配基于塊內各像素點做相同運動的原則。塊選得太大，內部像素運動的不一致性增大，且計算量增加；塊選得太小，匹配特征不顯著，易受噪聲干擾。筆者針對640×360大小的視頻幀，在區域內均勻選擇大小為16×16的塊，并使塊間間距與塊的大小相同。

位于圖像平坦區域或直線邊緣處的塊，所在區域紋理相近，塊的移動不能引起匹配誤差的顯著變化，難以精確定位，應用梯度閾值剔除這類塊。

1.2 降采樣全局搜索算法(DSFS)

在引出中心擴展搜索法之前，先介紹一種降采樣全局搜索算法。采用最小絕對誤差(SAD)作為搜索的匹配準則。

圖1a是全局搜索算法的示意圖，顏色越淺表示匹配誤差越小。計算搜索窗口內每一個點的SAD值，找到最小值(圖中顏色最淺的s)處為最佳匹配位置。圖1b是降采樣全局搜索算法示意圖，在搜索窗口內隔行隔列取點計算SAD值，在最小值處與相鄰的8個點比較，找到最佳匹配點位置。

a. 全局搜索算法 b. 降采樣全局搜索算法

與全局搜索算法相比，降采樣全局搜索算法減少了計算點數，由于其間隔只有一個像素，中心偏置特性在最佳匹配位置附近很顯著，其精確度與全局搜索相當。降采樣全局搜索法雖然減少了計算點數，依然無法克服全局搜索的缺陷，即窗口大小固定。對于無偏移的兩幅圖像，仍要遍歷完整個窗口尋找到最小偏差位置。這樣使得每個塊匹配的計算量只與預設搜索窗口大小有關，無論圖像實際偏移如何，計算開銷不變。顯然，這種搜索方式在大多數情況下將進行很多不必要的計算。

2 中心擴展搜索算法(CEXS)

假設進入中心偏置區域內時，梯度向量的方向基本一致，指向最佳匹配中心。基于降采樣全局搜索法(DSFS)原理，以起始點為中心，向外逐層擴展，搜索到進入中心偏置區域內的點，再在中心偏置區域內準確定位最佳匹配位置。具體步驟如下：

a. 以起始點P0為圓心，找到半徑r1的圓環C1上的最小SAD值SAD(P1)，P1為最小SAD值所在位置，并記圓心到P1的向量為LV1=P1-P0。

b. 令r2=r1+Δr，得到半徑r2的圓環C2上最小SAD值SAD(P2)和位置P2，并得到向量LV2=P2-P1。

c. 用相同的計算方式得到在半徑為rk=r1+(k-1)Δr的圓周Ck上最小SAD值SAD(Pk)和位置Pk，并得到向量LVk=Pk-Pk-1。

e. 若不滿足步驟d中的條件，則繼續執行步驟c，直到半徑擴大到搜索窗口的邊界為止。

圖2 中心擴展搜索算法原理示意圖

實際中，為了計算方便，用方形環代替圓環，可以得到很好的近似。

3 實驗結果與分析

實驗在Matlab 2012a仿真平臺上進行，處理器主頻為2.1GHz，內存2G，操作系統Windows7。對一段分辨率為640×360大小的抖動視頻，應用筆者所提算法進行穩像。先通過實驗比較算法處理兩幀圖像的效果，再給出處理整段視頻序列的結果。分別就幀間小偏移和大偏移兩種情況，采用全局搜索算法、菱形搜索算法、降采樣全局搜索算法和中心擴展搜索算法獲得幀間(水平、垂直、旋轉)偏移參數，得到校正前后兩幀的峰值信噪比(PSNR)，同時記錄每種算法的運行時間。

圖3為實驗小偏移時選用的兩幀圖像，表1列出4種算法處理后的PSNR值和運行時間。

a. 參考幀 b. 當前幀

搜索算法PSNRdB時間消耗s全局搜索法32.687 48.557 7菱形搜索法32.687 40.064 2降采樣全局搜索法32.687 42.196 9中心擴展搜索法32.687 40.795 5

圖4為視頻中大偏移的相鄰兩幀圖像，表2是4種算法處理后的結果對比。

由實驗結果可以看出，幀間小偏移時4種算法的峰值信噪比相同，均能準確得到全局運動向量，其中菱形搜索法耗時最少；大偏移情況下，菱形搜索法的峰值信噪比明顯小于其他3種算法，原因是其計算參數出現錯誤，其他3種算法均可靠，且中心擴展搜索法耗時最少。

a. 參考幀 b. 當前幀

搜索算法PSNRdB時間消耗s全局搜索法22.769 16.427 9菱形搜索法17.229 10.082 3降采樣全局搜索法22.767 51.656 2中心擴展搜索法23.060 00.865 9

圖5a為視頻前100幀相鄰幀間的峰值信噪比對比圖，全局搜索法(FS)、降采樣全局搜索法(DSFS)和中心擴展搜索算法(CEXS)的PSNR值基本相同，菱形搜索法(DS)出現很大波動，在偏移較大的情況先得出錯誤的全局運動矢量。圖5b中顯示了4種算法的時間消耗，其中全局搜索、降采樣全局搜索算法的計算量主要與搜索窗口的大小有關，故其時間消耗對不同圖像幀不發生顯著變化，菱形搜索在較小范圍內會找到最優解，總體計算量小，時間消耗顯示在圖中也很平緩。中心擴展搜索算法波動比較明顯，其計算量隨幀間偏移情況的不同而變化。

a. PSNR值對比 b. 計算時間對比

4 結束語

針對電子穩像中傳統塊匹配算法的缺陷，提出了一種中心擴展搜索算法，利用半全局搜索結合最小中心偏置特性，避免搜索陷入局部最優，同時降低了計算復雜度，能在一定程度上根據視頻幀的偏移大小調整搜索步數，減少計算量。實驗表明：新算法在具有全局搜索算法準確性的同時還提高了計算速度。然而提出的穩像算法尚需進一步完善，在圖中可以看出，菱形搜索算法能準確定位的地方，新算法的時間消耗比其要高，需要繼續改進。