應(yīng)用于電子穩(wěn)像的改進(jìn)塊匹配算法

楊 莉 邵克勇 劉遠(yuǎn)紅 白麗麗 張會(huì)珍

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

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

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

1 準(zhǔn)備工作①

1.1 塊的選取

圖像偏移過大時(shí)，邊緣區(qū)域不能在兩幀中重復(fù)出現(xiàn)，因此盡量避免將塊選擇在靠近邊緣區(qū)域的位置上，故將每幀圖像的四周預(yù)留10%的邊界補(bǔ)償區(qū)域。

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

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

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

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

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

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

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

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

假設(shè)進(jìn)入中心偏置區(qū)域內(nèi)時(shí)，梯度向量的方向基本一致，指向最佳匹配中心?；诮挡蓸尤炙阉鞣?DSFS)原理，以起始點(diǎn)為中心，向外逐層擴(kuò)展，搜索到進(jìn)入中心偏置區(qū)域內(nèi)的點(diǎn)，再在中心偏置區(qū)域內(nèi)準(zhǔn)確定位最佳匹配位置。具體步驟如下：

a. 以起始點(diǎn)P0為圓心，找到半徑r1的圓環(huán)C1上的最小SAD值SAD(P1)，P1為最小SAD值所在位置，并記圓心到P1的向量為L(zhǎng)V1=P1-P0。

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

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

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

圖2 中心擴(kuò)展搜索算法原理示意圖

實(shí)際中，為了計(jì)算方便，用方形環(huán)代替圓環(huán)，可以得到很好的近似。

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

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

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

a. 參考幀 b. 當(dāng)前幀

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

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

由實(shí)驗(yàn)結(jié)果可以看出，幀間小偏移時(shí)4種算法的峰值信噪比相同，均能準(zhǔn)確得到全局運(yùn)動(dòng)向量，其中菱形搜索法耗時(shí)最少；大偏移情況下，菱形搜索法的峰值信噪比明顯小于其他3種算法，原因是其計(jì)算參數(shù)出現(xiàn)錯(cuò)誤，其他3種算法均可靠，且中心擴(kuò)展搜索法耗時(shí)最少。

a. 參考幀 b. 當(dāng)前幀

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

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

a. PSNR值對(duì)比 b. 計(jì)算時(shí)間對(duì)比

4 結(jié)束語(yǔ)

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