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

潘璐璐，延偉東，鄭紅嬋

（西北工業大學理學院應用數學系，陜西西安 710129）

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

潘璐璐，延偉東，鄭紅嬋

（西北工業大學理學院應用數學系，陜西西安 710129）

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

數據庫系統；效率；嵌入式軟件；誤差；實驗；濾波器；圖像重構；數學運算符；MATLAB；光學分解功率；像素；局部自相似性；多尺度；鄰域嵌入；超分辨率

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

現有的圖像超分辨技術大體可分為3類：基于插值的方法、基于重構的方法和基于學習的方法。

基于插值的方法［1］是圖像超分辨技術早期研究的一類主要方法，如雙線性插值、雙三次插值等，它通過設計具有局部平滑性的插值核函數估計高分辨圖像網格上的未知像素值，從而達到增加圖像分辨率的目的。基于插值的方法優點在于簡單、快速，便于實時應用；其缺點在于不能有效恢復低分辨圖像中丟失的高頻信息，容易導致圖像模糊，滿足不了實際應用要求。

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

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

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

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

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

1.1基本思想

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

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

1.2濾波器J和D的設計

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

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

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

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

1.3鄰域嵌入算法進行超分辨率增強

鄰域嵌入（NE）超分辨方法假設LR圖像塊與對應的HR圖像塊構成的2個流形在局部幾何結構上是相似的。根據該假設，本文使用鄰域嵌入流形學習的思想增強HR圖像合成的效果。

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

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

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

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

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

從圖2中可以很明顯看出，當尺度因子α逐漸增大時，誤差也會越來越大。假設我們最終的放大倍數為4倍，如果我們取α為1.05時，則需要迭代29次，這顯然太費時；如果我們取α為1.25，則只需迭代7次。在本文的實驗結果中，我們最終選取α的值為1.25。

1.5算法實現

令子塊大小為n×n個像素，搜索子窗口大小為m×m個像素，子塊重疊區域寬度為c個像素，相似子塊個數為k，尺度因子為α，最終放大倍數為M，迭代次數為t=［lnM/lnα］，LR圖像的子塊特征構成的測試集，LR圖像的子塊特征構成的訓練集為，HR圖像I的子塊特征構

0成的訓練集為。則本文算法敘述如下：

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

目標：估計HR圖像Ht。

1）計算I0所對應的退化圖像，以及I0的雙三次插值放大圖像

4）計算重構權值wjp，使得重構誤差最小化：

5）線性組合k-近鄰對應的HR圖像塊，得到HR圖像塊的估計，即：

7）令I1=H0，返回步驟1），直至得到最終放大倍數M。

1.6時間復雜度分析

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

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

計算重構權值的時間復雜度主要取決于2個因素：子塊大小n×n；相似子塊個數為k。則此階段需要的時間消耗為O（nk3）。

迭代過程的時間復雜度主要取決于4個因素：輸入圖像的大小h×w；最終的放大倍數M；尺度因子α；子塊大小n×n；重疊區域寬度c。令t為迭代次數，前面已經給出t=［lnM/lnα］。令N為計算過程中需要學習的所有LR子塊的個數，則

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

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

2　實驗結果及分析

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

圖3　測試圖像

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

2.1實驗結果對此

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

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

圖4　Parents圖像結果比較

3　結 論

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

［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，Fattal 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

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

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