唐玲, 陳明舉

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

?

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

唐玲, 陳明舉

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

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

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

引言

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

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

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

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

1.1 匹配準(zhǔn)則

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

(1)

(2)

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

(3)

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

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

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

1.3 搜索模式的選取

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

圖2 搜索模式

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

(4)

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

(5)

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

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

2 基于最大后驗(yàn)概率的超分辨重建算法

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

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

(6)

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

(7)

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

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

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

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

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

圖4 不同算法的PSNR比較

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

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

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

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

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

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

[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] 韓磊,黃陳蓉,須夢(mèng)溪,等.參數(shù)自適應(yīng)的圖像亞像素級(jí)配準(zhǔn)方法[J].計(jì)算機(jī)應(yīng)用,2013,33(2):487-490.

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

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

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

[9] 孫琰玥,何小海,宋海英,等.一種用于視頻超分辨率重建的塊匹配圖像配準(zhǔn)方法[J].自動(dòng)化學(xué)報(bào),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

四川省教育廳科研項(xiàng)目(13ZB0138);人工智能四川省重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金項(xiàng)目(2013RYY02)

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

1673-1549(2015)03-0033-04

10.11863/j.suse.2015.03.07

TN919.8

A