潘璐璐，延偉東，鄭紅嬋

（西北工業(yè)大學(xué)理學(xué)院應(yīng)用數(shù)學(xué)系，陜西西安 710129）

基于多尺度局部自相似性和鄰域嵌入的超分辨率算法研究

潘璐璐，延偉東，鄭紅嬋

（西北工業(yè)大學(xué)理學(xué)院應(yīng)用數(shù)學(xué)系，陜西西安 710129）

多尺度局部自相似性是指同一幅圖像中存在相同尺度或不同尺度的相似子塊，這種圖像局部結(jié)構(gòu)自相似性廣泛存在于自然圖像中。提出了一種基于多尺度局部自相似性結(jié)合鄰域嵌入的單幅圖像超分辨率算法，該算法不依賴于外界圖像，僅僅在原始圖像的局部子窗口中搜索目標(biāo)圖像塊的相似子塊，并結(jié)合鄰域嵌入算法，進(jìn)一步提高參與重建的圖像塊與目標(biāo)圖像塊的相似性程度。實(shí)驗(yàn)結(jié)果表明，與雙三次插值與傳統(tǒng)鄰域嵌入算法相比，新算法在保證算法效率的前提下，能有效提升超分辨圖像的重建質(zhì)量。

數(shù)據(jù)庫系統(tǒng)；效率；嵌入式軟件；誤差；實(shí)驗(yàn)；濾波器；圖像重構(gòu)；數(shù)學(xué)運(yùn)算符；MATLAB；光學(xué)分解功率；像素；局部自相似性；多尺度；鄰域嵌入；超分辨率

超分辨率（SR）圖像重建是指用圖像處理的方法，通過軟件算法的方式將低分辨率（LR）圖像轉(zhuǎn)換成高分辨率（HR）圖像的技術(shù)。它在醫(yī)學(xué)診斷、模式識(shí)別、視頻監(jiān)控、生物鑒別、高清晰電視成像、遙感圖像解譯、高空對地觀測等領(lǐng)域有著廣泛的應(yīng)用。

現(xiàn)有的圖像超分辨技術(shù)大體可分為3類：基于插值的方法、基于重構(gòu)的方法和基于學(xué)習(xí)的方法。

基于插值的方法［1］是圖像超分辨技術(shù)早期研究的一類主要方法，如雙線性插值、雙三次插值等，它通過設(shè)計(jì)具有局部平滑性的插值核函數(shù)估計(jì)高分辨圖像網(wǎng)格上的未知像素值，從而達(dá)到增加圖像分辨率的目的?；诓逯档姆椒▋?yōu)點(diǎn)在于簡單、快速，便于實(shí)時(shí)應(yīng)用；其缺點(diǎn)在于不能有效恢復(fù)低分辨圖像中丟失的高頻信息，容易導(dǎo)致圖像模糊，滿足不了實(shí)際應(yīng)用要求。

基于重構(gòu)的方法［2-3］是按照圖像退化模型，處理來自同一場景但是彼此之間存在亞像素位移的多幅低分辨圖像，利用一定的數(shù)學(xué)理論對退化圖像進(jìn)行反退化，得到超分辨圖像。其優(yōu)點(diǎn)在于可以保持邊緣細(xì)節(jié)以及抑制人工痕跡；缺點(diǎn)在于當(dāng)放大倍數(shù)比較大時(shí)，超分辨圖像的質(zhì)量不能令人滿意，會(huì)出現(xiàn)圖像細(xì)節(jié)信息丟失，邊緣模糊等情況。

基于學(xué)習(xí)的方法［4-13］借助機(jī)器學(xué)習(xí)，通過學(xué)習(xí)低分辨與高分辨圖像之間的映射關(guān)系，預(yù)測低分辨圖像中丟失的高頻細(xì)節(jié)信息，從而生成超分辨圖像。這種方法由于其現(xiàn)有和潛在的諸多優(yōu)點(diǎn)，近年來受到了專家和學(xué)者的廣泛關(guān)注。Freeman等人［6］使用馬爾科夫隨機(jī)場（MRF）模型，利用圖像局部區(qū)域的兼容關(guān)系來選擇合適的高分辨率圖像塊，繼而生成超分辨率圖像。其后，Sun等人［12］在Freeman方法的基礎(chǔ)上，提出了利用圖像的初始簡圖先驗(yàn)增強(qiáng)圖像邊緣的方法；Wang等人［13］將全局重構(gòu)約束與局部塊的細(xì)節(jié)合成方法組合到一個(gè)統(tǒng)一的概率框架下，通過退火Gibbs采樣算法生成超分辨率圖像。但是，這些方法需要一個(gè)龐大的訓(xùn)練集合，計(jì)算量很大。為了克服這個(gè)缺點(diǎn)，Chang等人［4］借鑒流形學(xué)習(xí)中局部線性嵌入（LLE）的思想，提出了基于鄰域嵌入（NE）的圖像超分辨方法。該方法基于高低分辨率圖像塊組成的流形具

有相似局部結(jié)構(gòu)的假設(shè)，將低分辨率塊使用樣本集合中若干最近鄰的線性組合來表示，通過計(jì)算重建權(quán)值，并將權(quán)值傳遞給高分辨率圖像塊的線性組合，得到待重建的超分辨率圖像。這種方法避免了使用大的訓(xùn)練集合，提高了計(jì)算效率，但是重建超分辨圖像質(zhì)量出現(xiàn)了邊緣模糊、噪聲等問題。近年來，越來越多的學(xué)者指出在圖像中往往包含著大量的冗余信息，圖像的一些結(jié)構(gòu)信息會(huì)在圖像的不同尺度上重復(fù)出現(xiàn)，利用這些信息可以對圖像進(jìn)行更加有效地處理，生成超分辨率圖像。Glasner等人［9］在2009年提出了基于單幅圖像的超分辨率重建算法，該算法主要利用圖像中重復(fù)出現(xiàn)的一些結(jié)構(gòu)信息，采用圖像金字塔模型構(gòu)造一組圖像，這些不同尺度空間內(nèi)的圖像塊之間存在有一定的自相似性，將這種自相似性結(jié)合經(jīng)典的基于重建的方法，實(shí)現(xiàn)對圖像的超分辨率重建，得到了比較理想的結(jié)果。在此基礎(chǔ)上，F(xiàn)reedman等人［10］提出了局部自相似性概念，即圖像塊在不同尺度空間內(nèi)的一個(gè)小范圍內(nèi)具有一定的自相似性，利用這種局部自相似性，建立了不依賴于外界集合的快速圖像超分辨率重建算法，超分辨圖像質(zhì)量方面也取得了不錯(cuò)的效果。但是這兩種方法都依賴于圖像自身具有很強(qiáng)的自相似性前提，當(dāng)圖像本身的自相似性較弱時(shí)，生成的超分辨圖像會(huì)產(chǎn)生邊緣模糊、人工痕跡等問題。

本文針對單幅圖像超分辨率重建問題，提出了一種新的結(jié)合多尺度局部自相似性和鄰域嵌入的超分辨率重建方法。首先，使用雙三次插值方法將原始圖像放大倍；其次，利用提出的圖像降質(zhì)模型，生成原始圖像對應(yīng)的LR圖像；再次，利用圖像自身的局部自相似性，在原始圖像對應(yīng)的LR圖像的一個(gè)小窗口內(nèi)，尋找原始圖像塊的個(gè)相似LR圖像塊，結(jié)合鄰域嵌入方法，計(jì)算其重建系數(shù)，繼而將此重建系數(shù)傳遞給個(gè)對應(yīng)原始圖像中的圖像塊，計(jì)算出重建圖像塊。重復(fù)這個(gè)過程，直至達(dá)到需要的放大倍數(shù)。

1　基于多尺度局部自相似性的超分辨自類推方法

1.1基本思想

圖像的局部自相似性是指在同一幅圖像中存在相同尺度或不同尺度的相似結(jié)構(gòu)，其具體表現(xiàn)為圖像中相同尺度或不同尺度中位于局部鄰域中的相似圖像塊。圖1說明了利用局部自相似性進(jìn)行超分辨率重建的方法原理。訓(xùn)練集合包含3幅圖像，分別是原始圖像I0、原始圖像對應(yīng)的退化圖像I′0以及原始圖像對應(yīng)的插值放大圖像H′0。我們的目標(biāo)是不依賴于任何外界圖像，利用圖像在不同尺度間的自相似性特征，生成超分辨率圖像H0。對于H′0中的圖像塊p，在I′0對應(yīng)位置的一個(gè)窗口（灰色區(qū)域）內(nèi)，通過某種特征，找到與其相似的圖像塊p′，在原始圖像I0中尋找與p′具有相同位置坐標(biāo)的圖像塊q，并將此圖像塊作為LR圖像塊p的HR輸出，放置在SR圖像相應(yīng)的位置中。按照光柵掃描順序，對于H′0中的每一個(gè)圖像塊執(zhí)行此步驟，為了避免人工痕跡，圖像塊采取有重疊劃分，最終得到輸出圖像H0。

圖1　基于局部自相似性的超分辨算法基本思想

1.2濾波器J和D的設(shè)計(jì)

很多方法使用插值方法生成放大的LR圖像，借助于外界圖像來預(yù)測缺失的高頻信息。我們同樣使用插值方法對原始圖像進(jìn)行放大，本文中使用的濾波器J為雙三次插值濾波器，則H′0=J（I0）↑α。

為了預(yù)測LR圖像H′0中缺失的高頻信息，我們需要建立HR-LR圖像對，通過圖像對之間的對應(yīng)關(guān)系，給出HR圖像H0。對于H′0中的每一個(gè)子塊p，需要在I0的退化圖像I′0中尋找與其相似的子塊p′，這就要求I′0應(yīng)該和H′0具有相似的退化效果。為了達(dá)到這個(gè)效果，我們先將原始圖像I0下采樣，下采樣倍率為1/α倍，再將下采樣圖像利用雙三次插值算法放大α倍，即

式中，D為下采樣算子，J為雙三次插值算子，α為放大倍率。

這樣，我們就得到了原始圖像I0所對應(yīng)的退化圖像I′0，以及I0的插值放大圖像H′0，通過學(xué)習(xí)H′0與I′0之間的關(guān)系，將I0中的高頻信息添加給H′0，獲得輸出圖像H0。

1.3鄰域嵌入算法進(jìn)行超分辨率增強(qiáng)

鄰域嵌入（NE）超分辨方法假設(shè)LR圖像塊與對應(yīng)的HR圖像塊構(gòu)成的2個(gè)流形在局部幾何結(jié)構(gòu)上是相似的。根據(jù)該假設(shè)，本文使用鄰域嵌入流形學(xué)習(xí)的思想增強(qiáng)HR圖像合成的效果。

令LR圖像I′0的子塊特征構(gòu)成的訓(xùn)練集為Xs=，HR圖像I的子塊特征構(gòu)成的訓(xùn)練集為Y=0s，LR圖像H′的子塊特征構(gòu)成的測試集X=0t，鄰域個(gè)數(shù)為k。首先從中的子集中查找與最近的k-近鄰樣本，對應(yīng)位置構(gòu)成最近鄰集合N（j）。然后計(jì)算重構(gòu)權(quán)值wip，使得重構(gòu)誤差最小，重構(gòu)誤差表示如下：

為了保證輸出圖像H0的空間連續(xù)性，我們對中的子塊采取了有重疊劃分。當(dāng)所有的HR圖像塊生成之后，通過融合中所有HR圖像塊，相鄰子塊的重疊部分取特征的算術(shù)平均值，最終獲得HR圖像H0。

1.4多尺度框架下超分辨率算法

設(shè)α為每一次迭代時(shí)的尺度因子，M為最終要達(dá)到的放大倍數(shù)。要達(dá)到放大倍數(shù)M，需要迭代［lnM/lnα］次。當(dāng)α選取過小，迭代次數(shù)過多，算法的時(shí)間復(fù)雜度會(huì)受到很大影響；當(dāng)α逐漸增大時(shí)，尋找出的匹配子塊相似度會(huì)下降很快。為此，我們設(shè)計(jì)了一個(gè)實(shí)驗(yàn)，來說明尺度因子α取不同值時(shí)，局部自相似性的效果。其中，子塊大小為3×3個(gè)像素，子窗口大小為7×7個(gè)像素，特征為RGB空間灰度值（0～255）。圖2給出位于中的所有子塊與對應(yīng)子窗口中最相似子塊L1距離的平均值。

圖2　放大因子取不同值時(shí)，子塊的平均L1距離

從圖2中可以很明顯看出，當(dāng)尺度因子α逐漸增大時(shí)，誤差也會(huì)越來越大。假設(shè)我們最終的放大倍數(shù)為4倍，如果我們?nèi)ˇ翞?.05時(shí)，則需要迭代29次，這顯然太費(fèi)時(shí)；如果我們?nèi)ˇ翞?.25，則只需迭代7次。在本文的實(shí)驗(yàn)結(jié)果中，我們最終選取α的值為1.25。

1.5算法實(shí)現(xiàn)

令子塊大小為n×n個(gè)像素，搜索子窗口大小為m×m個(gè)像素，子塊重疊區(qū)域?qū)挾葹閏個(gè)像素，相似子塊個(gè)數(shù)為k，尺度因子為α，最終放大倍數(shù)為M，迭代次數(shù)為t=［lnM/lnα］，LR圖像的子塊特征構(gòu)成的測試集，LR圖像的子塊特征構(gòu)成的訓(xùn)練集為，HR圖像I的子塊特征構(gòu)

0成的訓(xùn)練集為。則本文算法敘述如下：

算法：基于局部自相似性和鄰域嵌入的超分辨率算法

目標(biāo)：估計(jì)HR圖像Ht。

1）計(jì)算I0所對應(yīng)的退化圖像，以及I0的雙三次插值放大圖像

4）計(jì)算重構(gòu)權(quán)值wjp，使得重構(gòu)誤差最小化：

5）線性組合k-近鄰對應(yīng)的HR圖像塊，得到HR圖像塊的估計(jì)，即：

7）令I(lǐng)1=H0，返回步驟1），直至得到最終放大倍數(shù)M。

1.6時(shí)間復(fù)雜度分析

在本文算法中，不依賴于外界圖像，在輸入圖像的不同尺度上使用局部自相似性，迭代生成輸出HR圖像。在迭代過程中，我們的算法消耗主要在3個(gè)部分：①搜索每一個(gè)LR子塊所對應(yīng)的相似結(jié)構(gòu)塊；②計(jì)算重構(gòu)權(quán)值；③逐層迭代最終得到輸出圖像。

搜索子塊的時(shí)間復(fù)雜度主要取決于2個(gè)因素：搜索子窗口大小m×m和子塊大小n×n。假設(shè)每一個(gè)子塊需要和N個(gè)子塊計(jì)算相似性距離，則P=（m -n+1）2，因此，每一個(gè)子塊的搜索過程需要的時(shí)間消耗為O（P）。

計(jì)算重構(gòu)權(quán)值的時(shí)間復(fù)雜度主要取決于2個(gè)因素：子塊大小n×n；相似子塊個(gè)數(shù)為k。則此階段需要的時(shí)間消耗為O（nk3）。

迭代過程的時(shí)間復(fù)雜度主要取決于4個(gè)因素：輸入圖像的大小h×w；最終的放大倍數(shù)M；尺度因子α；子塊大小n×n；重疊區(qū)域?qū)挾萩。令t為迭代次數(shù)，前面已經(jīng)給出t=［lnM/lnα］。令N為計(jì)算過程中需要學(xué)習(xí)的所有LR子塊的個(gè)數(shù)，則

迭代過程需要的時(shí)間消耗為O（N）。

綜上，本文算法需要的時(shí)間復(fù)雜度為O（PN+ nk3N）。對于1幅128×128的圖像，放大3倍，在處理器為Inter Core i5，主頻為2.40 GHz的電腦上，用MATLAB R2012b運(yùn)行，消耗時(shí)間為358.992 s，約合6 min。

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

為驗(yàn)證本文提出的算法有效性，我們采用如圖3所示的9幅圖像，將其長和寬都縮小為原來的1/ 3，作為待超分辨的原始圖像，再對生成的原始圖像進(jìn)行放大3倍的超分辨放大實(shí)驗(yàn)，并與雙三次插值、傳統(tǒng)的NE方法兩種方法進(jìn)行比較。

圖3　測試圖像

由于人類視覺系統(tǒng)對圖像亮度成分的敏感性比色度成分的敏感性更高，因此，先將RGB顏色空間的彩色圖像轉(zhuǎn)換到NTSC顏色空間，僅僅對亮度分量進(jìn)行超分辨放大。在實(shí)驗(yàn)中，參數(shù)值分別取為n =3、c=2、m=7、α=1.25、k=2。

2.1實(shí)驗(yàn)結(jié)果對此

客觀上，本文采用峰值信噪比（PSNR）評價(jià)不同算法的性能。表1是測試圖像在3倍放大情況下的客觀評價(jià)結(jié)果。可以看出，本文提出的方法在所有情況下都比其他2種方法獲得的結(jié)果要好。

為進(jìn)一步評價(jià)不同算法超分辨性能，圖4比較了Parents圖像分別使用3種不同算法重建的結(jié)果?？梢钥闯?，雙三次插值法不能有效恢復(fù)圖像的高頻信息，生成的圖像十分模糊。與雙三次插值結(jié)果相比較，傳統(tǒng)的NE方法通過學(xué)習(xí)HR與LR圖像間的對應(yīng)關(guān)系，在一定程度上能有效恢復(fù)出LR圖像中丟失的高頻細(xì)節(jié)，得到的結(jié)果比較清晰。從視覺質(zhì)量上看，傳統(tǒng)的NE方法能夠得到比雙三次插值方法更多的高頻細(xì)節(jié)，但由于重建過程直接使用1次放大到需要的倍數(shù)，得到的圖像在紋理細(xì)節(jié)區(qū)域仍出現(xiàn)明顯的失真。與上述2種方法得到的結(jié)果相比，本文提出的基于鄰域嵌入的超分辨自類推方法在保持圖像邊緣和恢復(fù)紋理細(xì)節(jié)方面都有不同程度的改善，得到的結(jié)果不僅邊緣更清晰更真實(shí)，而且紋理更加豐富。這是由于圖像的局部自相似特性在小的尺度因子范圍下可以保持良好的特性，在鄰域選擇過程中，結(jié)合局部自相似特性，使得參與重建的圖像塊均與目標(biāo)圖像塊具有相似的結(jié)構(gòu)，因而能獲得較好的重建質(zhì)量。

圖4　Parents圖像結(jié)果比較

3　結(jié) 論

本文針對基于圖像自相似性的超分辨算法中存在的不足，提出了一種基于鄰域嵌入的快速超分辨自類推方法。首先，提出一種圖像退化模型，在此基礎(chǔ)上生成不依賴于外界圖像的訓(xùn)練集合；其次，在一個(gè)小的局部窗口內(nèi)尋找LR子塊的相似圖像子塊；再次結(jié)合鄰域嵌入方法，計(jì)算重構(gòu)權(quán)值，輸出對應(yīng)的HR圖像子塊；然后融合所有HR子塊，得到本層的HR圖像；在多尺度框架內(nèi)多次重復(fù)這個(gè)過程，得到最終的HR圖像。實(shí)驗(yàn)結(jié)果表明，本文提出的方法與現(xiàn)有算法相比，在保證算法速度的前提下，同時(shí)提高了超分辨重建圖像的質(zhì)量。

［1］ Su D，Willis P.Image Interpolation by Pixel-Level Data-Dependent Triangulation［J］.Comput Graph Forum，2004，23（2）：189-202

［2］ Lin Z C，Shum H Y.Fundamental Limits of Reconstruction-Based Superresolution Algorithms under Local Reanslation［J］.IEEE Trans on PAMI，2004，26（1）：83-97

［3］ Ben-Ezra M，Lin Z C，Wilbum B Penrose.Pixels：Super-Resolution in the Detector Layout Domain［C］∥International Conference on Computer Vision，2007：1-8

［4］ Chang H，Yeung D Y，Xiong Y.Super-Resolution through Neighbor Embedding［C］∥Conference on Computer Vision and Pattern Recognition，2004：275-282

［5］ Yang J，Wright J，Ma Y，et al.Image Super-Resolution as Sparse Representation of Raw Image Patches［C］∥Conference on Computer Vision and Pattern Recognition，2008：1-8

［6］ Freeman W T.Jones T R，Pasztor E C.Example-Based Super-Resolution［J］.IEEE Computer Graphics and Applications，2002，22（2）：56-65

［7］ Tang Y，Yuan Y，Yan P，et al.Greedy Regression in Sparse Coding Space for Single-Image Super-Resolution［J］.Journal of Visual Communication and Image Representation，2013，24（2）：148-159

［8］ Kim K，Kwon Y.Example-Based Learning for Single-Image Super-Resolution［J］.Pattern Recognition，Lecture Notes in Computer Science，2008，5096：456-465

［9］ Glasner D，Bagon S，Irani M.Super-Resolution from a Single Image［C］∥International Conference on Computer Vision，2009：349-356

［10］ Freedman G，F(xiàn)attal R.Image and Video Upscaling from Local Self-Examples［J］.ACM Transa on Graphics，2011，30（2）：60-65

［11］ Li J，Qu Y，Li C，et al.Learning Local Gaussian Process Regression for Image Super-Resolution［J］.Neurocomputing，2015，154：284-295

［12］ Sun J，Zheng N，Tao H，et al.Shum.Image Hallucination with Primal Sketch Priors［C］∥Proc IEEE Conference on Computer Vision and Patter Recognition，2003：729-736

［13］ Wang Q，Tang X，Shum H.Patch Based Blind Image Super Resolution［C］∥Proc IEEE International Conference on Computer Vision，2005：709-716

Super Resolution Based on Multi-Scale Local Self-Similarity and Neighbor Embedding

Pan Lulu，Yan Weidong，Zheng Hongchan
（Department of Applied Mathematics，Northwestern Polytechnical University，Xi′an 710129，China）

Multi-scale local self-similarity，which widely occurs in natural images，refers to those similar patches either within the same scale or across different scales coming from the same input image.In this paper，we propose a single image super resolution algorithm based on multi-scale local self-similarity and neighbor embedding；this algorithm does not rely on an external example database nor use the whole input image as a source for example patches.Instead，we extract patches from extremely localized regions in the input image and combine with neighbor embedding algorithm，further increasing the similarity between the patches which take part in reconstruction on the one hand，and the target patch on the other.Experimental results and their analysis demonstrate preliminarily that our method can improve the quality of super resolution image as compared with the bicubic interpolation and traditional neighbor embedding algorithm，thus ensuring the efficiency of the algorithm.

database systems，efficiency，embedded software，errors，experiments，filters，image reconstruction，mathematical operators，MATLAB，optical resolving power，pixels；local self-similarity，multi-scale，neighbor embedding，super resolution

TP391.9

A

1000-2758（2015）06-1014-06

2015-04-28

國家自然科學(xué)基金（61201323）與陜西省自然科學(xué)基金（2014JQ5189）資助

潘璐璐（1981—），女，西北工業(yè)大學(xué)講師，主要從事圖像超分辨率研究。