一種用于超分辨率重建的自適應(yīng)塊匹配算法

唐玲, 陳明舉

(四川理工學(xué)院自動化與電子信息學(xué)院, 四川自貢643000)

?

一種用于超分辨率重建的自適應(yīng)塊匹配算法

唐玲, 陳明舉

(四川理工學(xué)院自動化與電子信息學(xué)院, 四川自貢643000)

提出了一種基于自適應(yīng)塊匹配的超分辨重建算法。首先根據(jù)相鄰運動塊之間的相關(guān)性來預(yù)測搜索塊，然后利用圖像的運動特性自適應(yīng)地選擇合適的搜索模式，最后采用最大后驗概率估計算法對配準(zhǔn)后的圖像進行超分辨率重建。該算法可以有效減少搜索匹配點的個數(shù)，極大提高搜索速度，并且能夠獲得與全搜索算法同樣高的配準(zhǔn)精度，具有較大的峰值信噪比。實驗結(jié)果表明，所設(shè)計算法能獲得較好的視覺效果與重建效果，具有一定的實用價值。

超分辨率重建;自適應(yīng)塊匹配;最大后驗概率;峰值信噪比

引言

超分辨率重建是指將多幅具有互補信息的低分辨率圖像(或視頻序列)進行處理，融合估計出一幅或多幅高分辨圖像的技術(shù)。重建算法通常包括圖像配準(zhǔn)(或運動估計)、插值、消除模糊和噪聲幾個組成部分，也有一些空域算法將插值與去除模糊和噪聲合二為一，例如迭代反向投影(IBP)，最大后驗概率估計(MAP)等。在圖像重建過程中，圖像配準(zhǔn)是超分辨率算法實現(xiàn)的第一步也是極其重要的一步，在圖像配準(zhǔn)中對像素塊運動位置估計的準(zhǔn)確性將直接影響重建圖像的質(zhì)量。眾多的圖像配準(zhǔn)方法主要在圖像像素空間或圖像的頻率空間進行，其中基于像素塊的匹配算法是常見的一種高效方法。

在塊匹配算法中，全搜索(FS)算法是對圖像整個像素空間進行搜索，從而找出最符合匹配規(guī)則的點，通常圖像所含的信息量大、計算復(fù)雜度太高、耗時較大，因此，不適宜于實時系統(tǒng)。為此，學(xué)者提出了很多優(yōu)秀的運算簡單且耗時少的快速圖像匹配算法，例如三步搜索法(TSS)[1]、四步法(FSS)[2]、菱形搜索法(DS)[3]、六邊形搜索法(HEXBS)[4]等，這些算法都只是有效地利用運動矢量統(tǒng)計分布特性來固定地選擇合適的搜索方式。后來學(xué)者們提出來的自適應(yīng)配準(zhǔn)算法，如參數(shù)自適應(yīng)圖像配準(zhǔn)[5]、基于角點特征的自動配準(zhǔn)[6]、自適應(yīng)最優(yōu)塊匹配[7]等，在不同程度上提高了配準(zhǔn)準(zhǔn)確度，但是速度較慢且計算的復(fù)雜度較大。本文在對配準(zhǔn)算法研究的基礎(chǔ)上，針對其不足提出一種空域自適應(yīng)圖像塊匹配算法，可以靈活地根據(jù)圖像塊的大小選擇合適的搜索模式，從而在降低復(fù)雜度的同時進一步提高了搜索速度，獲得較高的配準(zhǔn)精度，最后利用最大后驗概率估計算法對已配準(zhǔn)圖像進行重建，取得了較好的重建效果。

1 自適應(yīng)搜索算法

該算法首先根據(jù)相鄰運動塊之間的相關(guān)性預(yù)測搜索塊，再利用圖像的運動特性選擇合適的搜索方式，針對運動塊較小的運動矢量選擇運算速度較快的算法搜索，大運動塊的運動矢量的搜索選擇精度較高的算法，從而以實現(xiàn)根據(jù)不同運動塊選擇不同搜索模式的自適應(yīng)。

1.1 匹配準(zhǔn)則

在搜索過程中，對于評價搜索塊的相似性，選擇求和絕對誤差(SAD)以及求和絕對方差(SSE)作為判別準(zhǔn)則，其定義如下：

(1)

(2)

式中，(x,y)為位移矢量，fk和fk-1分別為當(dāng)前幀的圖像塊和前一幀的預(yù)測塊，m×n為宏塊大小，為了方便算法的實現(xiàn)，一般取m,n的值相等，通常，宏塊大小取值為16×16像素。在搜索相似塊時，匹配準(zhǔn)則選用求和絕對誤差SAD。當(dāng)SAD達到最小時的位移矢量(x,y)就是當(dāng)前塊的運動矢量(MV)，即求解：

(3)

1.2 目標(biāo)MV的預(yù)測

為了獲取當(dāng)前塊準(zhǔn)確的MV預(yù)測，我們首先要得到相鄰運動塊之間的相關(guān)性。通常相關(guān)性最強的參考相鄰塊，應(yīng)該是當(dāng)前塊左側(cè)、正上、左上和右上方向上的，其他方向上的塊與當(dāng)前塊的相關(guān)性較小，如圖1所示。通過對大量圖像序列的統(tǒng)計結(jié)果進行分析表明，當(dāng)前塊與其左側(cè)、正上相鄰塊的運動相關(guān)性最大，與左上、右上相鄰塊的相關(guān)性較小，因此本文只選擇上鄰塊作為預(yù)測塊，忽略其他方向相鄰塊，以減少運算量。

圖1 當(dāng)前塊的相鄰塊位置

1.3 搜索模式的選取

DS算法是一種高效的快速塊匹配算法，主要有兩種模式[8]：基于菱形的大九點搜索模式(LDSP)以及小五點搜索模式(SDSP)，如圖2所示。當(dāng)搜索距離中心小于兩個像素的小的運動矢量時，LDSP會導(dǎo)致過度搜索，而對于一些大的、復(fù)雜的運動圖像塊，LDSP搜索范圍顯得太小，從而搜索不足。針對LDSP這一問題，本文根據(jù)當(dāng)前塊運動等級來選擇搜索模塊的自適應(yīng)算法。對圖像塊進行運動估計，計算當(dāng)前塊與參考塊同一位置之間的SAD[9]，若其SAD值小于設(shè)定的誤差閾值則認為當(dāng)前塊的運動向量為0，并停止搜索，從而減少搜索的計算量；如果當(dāng)前塊的宏塊是第一行(列)，則認為當(dāng)前塊的運動等級低，為小運動，直接采用SDSP進行搜索，這樣搜索不會有較大的起伏；否則認為當(dāng)前塊的運動等級高，為大運動，此時先采用LDSP進行初步搜索，后采用SDSP進行精確定位。

圖2 搜索模式

在初步搜索階段，預(yù)測的MV的長度可以根據(jù)其水平、垂直坐標(biāo)來確定：

(4)

式中，Γ是MV的大小，round為取整，MV(x)和MV(y)分別是當(dāng)前MV的水平坐標(biāo)和垂直坐標(biāo)。為簡化起見，可以使用式(5)決定MV的長度：

(5)

把LDSP模型的中心對準(zhǔn)搜索窗的中心點，根據(jù)預(yù)測MV的長度檢測搜索點以及預(yù)測點，從而找到使SAD值達到最小的點，并把該最小點作為SDSP模型的中心點。完成初步搜索后，可以粗略估計運動對象的運動趨勢，然后通過SDSP模型檢測它的搜索點，如果最小SAD值在小菱形中心時，那么中心點即為運動矢量，此時停止搜索；反之重復(fù)此步驟，直到最小匹配點為SDSP的中心點，從而完成MV的精確定位。具體流程如圖3所示。

圖3 自適應(yīng)塊匹配搜索算法流程圖

2 基于最大后驗概率的超分辨重建算法

基于Bayesian理論的最大后驗概率估計(MAP)算法[10]以其受抗噪聲干擾能力強、解唯一等優(yōu)點得到了廣泛的應(yīng)用。基于MAP的圖像重建的基本思想是在已知低分辨率圖像的前提下，使重構(gòu)后的高分辨率圖像的后驗概率達到最大。

假設(shè)有N幅觀測低分辨率圖像序列為{yk,k=1,2,…,N}，理想高分辨率圖像為x，它們之間的關(guān)系可以表示為yk=DkHkFkx+nk，其中，Dk、Hk和Fk分別為下采樣矩陣、模糊矩陣和仿射變換矩陣，nk為高斯白噪聲。在不失一般性條件下，假設(shè)所有低分辨率圖像序列都具有相同的D和H，那么MAP算法的求解代價函數(shù)為：

(6)

式中，λ是正則化參數(shù)，J(x)是正則化泛函，距離范數(shù)為p，當(dāng)p=1時，并將上式對x求變分得到迭代的求解式為：

(7)

式中，J(x)進行變分后為L(x)x，迭代步長為β。求解時，D、H默認為已知量。在圖像超分辨率重構(gòu)中，H對光學(xué)系統(tǒng)的點擴散方程進行估計而得到。在非聯(lián)合求解算法中，F(xiàn)k可以通過圖像配準(zhǔn)算法計算得到，本文將采用前面提出的自適應(yīng)塊匹配算法得到的配準(zhǔn)參數(shù)用于超分辨率重建。

3 實驗及結(jié)果分析

實驗1：采用大小為16×16像素的宏塊，搜索范圍為±8像素，匹配準(zhǔn)則采用SAD準(zhǔn)則。為驗證本文提出的自適應(yīng)塊匹配搜索算法的有效性，將提出的配準(zhǔn)算法與FS、DS兩個序列的搜索結(jié)果進行比較，采用平均峰值信噪比(PSNR)、平均搜索點數(shù)(塊匹配次數(shù))以及相對于FS搜索的速度倍數(shù)作為評價標(biāo)準(zhǔn)(表1)。從表1可以看出，本文算法相比其他兩種算法不僅有效減少了匹配點的搜索個數(shù)、大幅度提高搜索速度，從而減少搜索的時間，并且重構(gòu)后的圖像與其他兩種算法一樣可以獲得較高的PSNR。

表1 視頻測試序列在不同算法中的性能比較

圖4 是采用Tennis序列分析不同算法的PSNR性能曲線。從圖4可以看出本文算法能夠獲得的峰值信噪比與全搜索算法FS基本相同，配準(zhǔn)精度較高。

圖4 不同算法的PSNR比較

實驗2：對一幅512×512像素的高分辨率圖像按表2進行平移和降采樣，從而產(chǎn)生4幅64×64的低分辨率圖像(q=8)，將這些圖像通過上述自適應(yīng)塊匹配搜索方法配準(zhǔn)后采用最大后驗概率估計(MAP)算法進行重建。自適應(yīng)塊匹配搜索計算得到的位移量見表2，其中第一幅圖像y1是參考幀。由表2可見，采用自適應(yīng)塊匹配算法得到的各低分辨率圖像幀之間的位移量與實際位移量非常接近，誤差范圍在0.05左右。重建圖像結(jié)果如圖5所示。

表2 低分辨率圖像幀間的位移量

圖5 圖像序列超分辨率重建結(jié)果

圖5(a)為原始高分辨率圖像，圖5(b)是將參考幀經(jīng)過雙線性插值重建后的結(jié)果，可以看出雙線性插值的圖像整體比較模糊，損失了圖像的細節(jié)，圖5(c)是采用DS算法配準(zhǔn)后采用MAP重建的高分辨率圖像，圖5(d)是采用本文的自適應(yīng)搜索算法配準(zhǔn)的重建結(jié)果，通過比較發(fā)現(xiàn)，本文方法實現(xiàn)的超分辨率重建效果無論在清晰度還是在細節(jié)保持方面較雙線性插值算法都有所改善，重構(gòu)后圖像的視覺效果與采用快速DS配準(zhǔn)相接近。但是根據(jù)實驗1的結(jié)論，本文所提出的算法能極大提高搜索速度，因此更能達到實時性要求，具有更好的應(yīng)用價值。

4 結(jié)束語

本文在研究基于塊匹配的圖像配準(zhǔn)基礎(chǔ)上，針對傳統(tǒng)算法的不足，提出了一種自適應(yīng)塊匹配算法用于超分辨率重建，該算法采用自適應(yīng)方式選擇搜索模式，能夠明顯降低平均搜索點數(shù)、提高配準(zhǔn)速度，且從配準(zhǔn)圖像的峰值信噪比值可以看出提出算法同其他快速塊匹配算法相比都具有較高的配準(zhǔn)精度。并且使用本文的配準(zhǔn)方法進行最大后驗概率估計重建得到的超分辨圖像具有較好的視覺效果，有一定的實用價值。

[1] Koga T,Linuma K,Hirano A,et al.Motion compensated interframe coding for video conference[C]//In Proc.Nat.Telecommunication Conf.,New Orleans,LA,November 29-December 3,1981:531-535.

[2] Po L M,Ma M C.A novel four-step search algorithm for fast block motion estimation[J].IEEE Trans on Circuits and Systems for Video Tech,1996,6(3):313-317.

[3] Zhu S,Ma K K.A new diamond search algorithm for fast block-matching motion estimation[J].IEEE Trans on Image Processing,2000,9(2):287-290.

[4] Zhu C,Lin X,Chau L P.Hexagon-based search pattern for fast block motion estimation[J].IEEE Trans On Circuits System Video Technology,2002,12(5):349-355.

[5] 韓磊,黃陳蓉,須夢溪,等.參數(shù)自適應(yīng)的圖像亞像素級配準(zhǔn)方法[J].計算機應(yīng)用,2013,33(2):487-490.

[6] 趙前鑫,楊英寶.一種基于角點特征的遙感影像自動配準(zhǔn)方法[J].測繪科學(xué),2013,38(3):160-162,133.

[7] 蔡成濤,梁小龍,譚吉來,等.自適應(yīng)最優(yōu)塊匹配視頻穩(wěn)像算法[J].系統(tǒng)工程與電子技術(shù),2013,35(6):1324-1329.

[8] 張培珍,江華俊,沈玉利.自適應(yīng)塊匹配搜索算法研究[J].計算機應(yīng)用,2006,26(4):797-798,802.

[9] 孫琰玥,何小海,宋海英,等.一種用于視頻超分辨率重建的塊匹配圖像配準(zhǔn)方法[J].自動化學(xué)報,2011,37(1):37-43.

[10] Schultz R,Stevenson R.Extraction of high-resolution frames from video sequences[J].IEEE Trans Image Processing,1996,5(6):996-101.

An Adaptive Block Matching Algorithm for Super-resolution Reconstruction

TANGLing,CHENMingju

(School of Automation and Electronic Information, Sichuan University of Science & Engineering, Zigong 643000, China)

This paper presents an adaptive block matching algorithm of super-resolution reconstruction. Firstly, the search block is predicted according to the correlation between adjacent blocks, and then the appropriate search mode is adaptively selected by using the motion characteristics of the image, finally, the image after rectification is super-resolution reconstructed by the maximum posterior probability estimation algorithm. The algorithm greatly improves the search rate，at the same time effectively reduces the search number of matching points, and can obtain the same registration accuracy compared with the full search algorithm, maintains a high peak signal to noise ratio(PSNR). Experimental results show that the algorithm has better visual effect and reconstruction effect, which confirms a practical value of the algorithm.

super-resolution reconstruction; adaptive block matching; maximum posterior probability; PSNR

2015-03-11

四川省教育廳科研項目(13ZB0138);人工智能四川省重點實驗室開放基金項目(2013RYY02)

唐 玲(1981-),女,重慶銅梁人,講師,碩士,主要從事信號與信息處理方面的研究，(E-mail)fashion-kitty@163.com

1673-1549(2015)03-0033-04

10.11863/j.suse.2015.03.07

TN919.8

A