一種用于超分辨率重建的自適應塊匹配算法

唐玲, 陳明舉

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

?

一種用于超分辨率重建的自適應塊匹配算法

唐玲, 陳明舉

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

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

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

引言

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

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

1 自適應搜索算法

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

1.1 匹配準則

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

(1)

(2)

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

(3)

1.2 目標MV的預測

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

圖1 當前塊的相鄰塊位置

1.3 搜索模式的選取

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

圖2 搜索模式

在初步搜索階段，預測的MV的長度可以根據其水平、垂直坐標來確定：

(4)

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

(5)

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

圖3 自適應塊匹配搜索算法流程圖

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

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

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

(6)

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

(7)

式中，J(x)進行變分后為L(x)x，迭代步長為β。求解時，D、H默認為已知量。在圖像超分辨率重構中，H對光學系統的點擴散方程進行估計而得到。在非聯合求解算法中，Fk可以通過圖像配準算法計算得到，本文將采用前面提出的自適應塊匹配算法得到的配準參數用于超分辨率重建。

3 實驗及結果分析

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

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

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

圖4 不同算法的PSNR比較

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

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

圖5 圖像序列超分辨率重建結果

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

4 結束語

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

[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] 韓磊,黃陳蓉,須夢溪,等.參數自適應的圖像亞像素級配準方法[J].計算機應用,2013,33(2):487-490.

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

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

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

[9] 孫琰玥,何小海,宋海英,等.一種用于視頻超分辨率重建的塊匹配圖像配準方法[J].自動化學報,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