常志國，郭茹俠，李　晶，胡云鷺

（長安大學　信息工程學院，西安　710064）

基于稀疏表示和近鄰嵌入的圖像超分辨率重構(gòu)

常志國，郭茹俠，李晶，胡云鷺

（長安大學信息工程學院，西安710064）

提出基于稀疏表示和近鄰嵌入的單幀圖像超分辨率重構(gòu)算法；為低分辨率和高分辨率圖像塊訓練兩個基于稀疏表示的過完備字典，在訓練的低分辨率圖像塊和高分辨率圖像塊中分別選取與這兩個字典原子最近的圖像塊近鄰，通過圖像塊近鄰來計算構(gòu)圖像塊的權(quán)重；一旦得到權(quán)重矩陣，高分辨率重構(gòu)圖像塊可以由低分辨率圖像塊與相應(yīng)權(quán)重相乘來表示；與之前的算法相比，所提出的算法在計算字典原子與圖像塊距離的時候不是逐個圖像塊進行計算，而是先將圖像塊聚類，計算字典原子與類中心的距離，在距離最近的一類中選取圖像塊；計算權(quán)重矩陣的時間可以大大減少，提高計算效率；所得到的PSNR與其它算法相比，也有一定提高。

超分辨率重構(gòu)；稀疏表示；過完備字典；圖像塊近鄰；權(quán)重

0　引言

圖像超分辨率放大能夠?qū)⒌头直媛蕡D像放大又能夠恢復(fù)圖像的高頻細節(jié)。當然圖像超分辨率放大是一個病態(tài)問題，因為根據(jù)圖像放大的倍數(shù)，會將一個低分辨率像素點映射成多個高分辨率像素點。

近鄰嵌入的方法就是為了降低圖像超分辨率重構(gòu)的時間復(fù)雜度和存儲需求。近鄰嵌入假設(shè)低分辨率塊和高分辨率塊在低維空間具有相似的局部紋理，使用與低分辨率圖像塊相同的插值系數(shù)產(chǎn)生高分辨率輸出塊。NE+LLE［18］對于重構(gòu)的低分辨率圖像塊，在訓練的低分辨率圖像塊集合中尋找K個近鄰，將K個近鄰線性組合來表示重構(gòu)的低分辨率圖像塊，得到這個線性組合系數(shù)即權(quán)重，最小化重構(gòu)誤差，最后使用相應(yīng)的K個高分辨率圖像塊近鄰和權(quán)重計算高分辨率輸出圖像塊。權(quán)重的限制條件一般為近鄰的權(quán)重之和為1，在NE+NNLS［19］中，為了降低算法復(fù)雜度，將權(quán)重的限制條件改為非負數(shù)，即權(quán)重大于零。近鄰嵌入算法與稀疏表示相比可以明顯降低算法的復(fù)雜度和內(nèi)存需求，然而由于缺乏先驗知識，重構(gòu)的效果并不比稀疏表示的好。將稀疏表示模型與近鄰嵌入模型結(jié)合起來，既能夠降低算法復(fù)雜度圖像的重構(gòu)結(jié)果又較好。Timofte提出的ANR［20］結(jié)合了這兩種算法。ANR［20］為每個輸入塊計算它在字典中的最近鄰原子，只使用近鄰的字典原子而不是整個字典，大大降低了計算復(fù)雜度和重構(gòu)時間。為了建立圖像塊與字典之間的聯(lián)系，Timofte提出了A+［21］算法，使用Zedey方法訓練的字典，計算訓練的圖像塊與字典原子之間的近鄰，選擇K個近鄰高分辨率和低分辨率圖像塊計算映射的權(quán)重矩陣。建立在稀疏表示和近鄰嵌入基礎(chǔ)上的算法，能夠減少計算復(fù)雜度，加強圖像的表示能力。

本文中采用的算法也是由近鄰嵌入和稀疏表示結(jié)合起來的。我們的算法中先分割圖像塊，使用Zedey訓練字典的方法訓練高分辨率和低分辨率字典，計算切割的圖像塊與字典原子之間的距離。這里與A+算法的不同之處在于圖像塊的選擇。A+算法中逐個計算圖像塊與字典原子之間的距離，選擇K個圖像塊近鄰。然而由于圖像塊過多，在計算歐幾里得距離時花費時間過長，而且很容易導致內(nèi)存溢出。我們的算法先將圖像塊聚類，計算類中心與字典原子之間的距離，在與字典原子最近的類中選擇K個圖像塊。與A+相比計算時間大大減少，而與ANR相比，圖像的PSNR也有所提高。

1　稀疏表示模型

圖像超分辨率型可以表示為y=βx，其中x表示高分辨率圖像，y表示低分辨率圖像，β表示對高分辨率圖像x進行的模糊和下采樣操作，通過這個操作使低分辨率和高分辨率圖像保持一致?，F(xiàn)在已知低分辨率圖像y，為了得到高分辨率圖像x，可以通過最小二乘法來求解此式

為了避免方程出現(xiàn)病態(tài)過擬合問題，加入正則項l1范數(shù)，可以得到（2）式

這是一個稀疏表示模型，式中

x=φα（3）

圖像塊可以表示為過完備字典和稀疏系數(shù)的線性組合［5］，φ是具有K個原子的過完備字典，α是稀疏表示系數(shù)，其大部分元素為0。即在過完備字典中選擇合適的原子可以對圖像塊進行稀疏表示。（2）式求解的方法。字典學習的方法也有很多種，如在線字典學習［25］，K-SVD算法等。一旦得到一對過完備字典，將輸入的低分辨率圖像塊表示為低分辨率字典和稀疏系數(shù)的乘積，則高分辨率圖像塊就可以通過高分辨率字典和稀疏表示系數(shù)重建。

2　圖像塊近鄰嵌入模型

假設(shè)有一組高分辨率圖像x1，x2，x3…xN，使用雙三次插值下采樣再上采樣得到其相應(yīng)的低分辨率圖像y1，y2，y3…yN。將兩組圖像切割成小塊，圖像塊大小為m×M。得到集合Ω=｛~xi，~yi｝，其中~xi，~yi分別表示切割的第i個高分辨率和低分辨率圖像塊，i=1…P，P為圖像切割的總塊數(shù)。將一個低分辨率輸入圖像塊L表示為權(quán)重與圖像塊近鄰的乘積，圖像塊的近鄰是在集合Ω中選取的，通過計算輸入的圖像塊與集合中的圖像塊之間的歐幾里得距離來得到圖像塊的近鄰。假設(shè)在集合中選取了圖像塊的K個近鄰，則權(quán)重的計算方法可以由（4）式給出

j=1…K表示圖像塊的K個近鄰。如果（~yjT~yj）-1存在，則方程的代數(shù)解為（5）式

ω=（~yjT~yj）-1~yjTL（5）

為了避免方程出現(xiàn)病態(tài)過擬合問題，給此權(quán)重加入正則項，可以得到（6）式

由（6）式可以得到權(quán)重的代數(shù)解（7）式

ω=（~yjT~yj+λΙ）-1~yjTL（7）

一旦得到權(quán)重系數(shù)矩陣，則高分辨率圖像塊可以通過（8）式重建

H=~xjω（8）

式中，H表示重建的高分辨率圖像塊，~xj表示集合Ω中相應(yīng)于低分辨率圖像塊~yj的高分辨率圖像塊。

3　基于稀疏表示和圖像塊近鄰的圖像超分辨率重構(gòu)

稀疏表示模型雖然能夠很好地表示圖像塊，但是字典訓練會花費很長時間，內(nèi)存占用過大；近鄰嵌入模型能夠很好地解決圖像超分辨率重構(gòu)的時間復(fù)雜度和存儲需求。將這兩種方法結(jié)合起來。設(shè)第i高分辨率和相應(yīng)的低分辨率圖像塊分別為~xi，~yi，則由公式（2）可以得到公式（9）

αi為低分辨率圖像塊的稀疏表示系數(shù)，使用OMP求解αi，固定αi，對低分辨率字典φy用K-SVD算法進行逐列更新。使用同樣的方法可以得到高分辨率字典φx。

由公式（7）和公式（8）可以得到公式（10）

H=x~j（~yjTy~j+λΙ）-1~yjTL（10）

如果給輸入的低分辨率圖像塊L乘以一個矩陣，就可以得到要重構(gòu)的高分辨率圖像塊。這個矩陣是由圖像塊近鄰構(gòu)成的，將其稱為映射矩陣，乘以這個矩陣就可以將低分辨率圖像塊映射為高分辨率圖像塊，即公式（11）

Pj=xj~（~yjTyj~+λΙ）-1yj~T（11）

由于映射矩陣Pj是在未知低分辨率圖像塊L的情況下事先計算好的，要得到低分辨率圖像塊的近鄰y~j和相應(yīng)的高分辨率近鄰x~j就不能使用近鄰嵌入的方法。Timofte在ANR［20］中結(jié)合了字典訓練［12］的思想，為事先訓練好的低分辨率字典φy和高分辨率字典φx中的每個原子計算K′個近鄰，用字典原子近鄰來代替圖像塊近鄰，得到每個字典原子的映射矩陣Pl，l =1…K′表示計算的K′個近鄰。最后通過為每個輸入塊計算它在字典中的最近鄰原子，使用這個原子對應(yīng)的映射矩陣將其映射到高分辨率空間。

為了加強圖像塊與映射函數(shù)之間的聯(lián)系，Timofte在A+中同樣使用了Zedey訓練的高分辨率和低分辨率字典。計算圖像塊集合Ω=｛x~i，~yi｝中，低分辨率圖像塊y~i與每個低分辨率字典原子之間的歐幾里得距離，在低分辨率圖像塊中選擇與字典原子最近的K個低分辨率圖像塊，和相應(yīng)的高分辨率圖像塊，可以得到公式（11）中的映射函數(shù)。

由于要計算每個圖像塊與字典原子之間的距離，當圖像塊數(shù)量較大時，計算這個距離所花費的時間較長。本文中為了降低算法的運行時間同時保證重構(gòu)圖像塊的PSNR不會驟降，事先將切割的高分辨率和相應(yīng)的低分辨率圖像塊使用k—means進行聚類，聚類之后我們只計算聚類中心與字典原子之間的歐幾里得距離，最后在距離字典原子最近的一類中選擇K個低分辨率和相應(yīng)的高分辨率圖像塊，這將會大大降低算法復(fù)雜度，減少運算時間。

4　算法流程

基于稀疏表示和圖像塊近鄰的單幀圖像超分辨率重構(gòu)算法流程如圖1所示。

圖1　基于稀疏表示和圖像塊近鄰的圖像超分辨率重構(gòu)算法流程圖

算法步驟如下。

輸入：高分辨率訓練圖像和低分辨率待重構(gòu)圖像；

輸出：高分辨率重構(gòu)圖像。

1）將高分辨率訓練圖像雙三次插值下采樣再上采樣得到其相應(yīng)的低分辨率圖像，

兩組圖像切割成m×M的小塊，得到高分辨率和低分辨率圖像塊集合Ω=｛~xi，~yi｝。

2）使用Zedey的算法分別對圖像塊訓練高分辨率字典φx和低分辨率字典φy

3）將集合Ω中的高分辨率和低分辨率圖像塊分別聚類，聚類個數(shù)為~K。我們使用K-means聚類，首先初始化~K個聚類中心，計算圖像塊與聚類中心的距離，圖像塊聚類后，求得每類的均值，作為新的聚類中心，不斷重復(fù)迭代，直到均方差收斂。

4）使用歐幾里得距離公式計算每個聚類中心與低分辨率字典φy中的每列字典原子之間的距離。

5）將計算的距離按從小到大順序排序，選擇距離字典原子最近的一類C。

6）在最近的一類C中選取K個低分辨率近鄰圖像塊和相應(yīng)的高分辨率圖像塊。

7）使用公式（11）計算映射函數(shù)Pj。

8）將輸入的低分辨率圖像轉(zhuǎn)化到Y(jié)CbCr空間，對亮度圖像進行雙三次插值放大，

用f1=［-1，0，1］，fT1=［-1，0，1］'，f2=［1，0，-2，0，1］，fT2=［1，0，-2，0，1］'特征算子與亮度圖像卷積，得到一階二階水平和垂直梯度圖，將梯度圖切割成m×m的小塊，重疊像素為ω。

9）為輸入的圖像塊計算其在字典中的最近鄰原子，找到此原子對應(yīng)的映射矩陣，與圖像塊相乘得到重建的高分辨率圖像塊。

10）所有高分辨率圖像塊恢復(fù)后，使用重疊像素ω重建高分辨率圖像。

5　實驗結(jié)果分析

5.1參數(shù)設(shè)置

試驗中我們將低分辨率圖像放大3倍?；谌搜蹖α炼刃畔⒚舾羞@個條件，我們將待重構(gòu)的圖像轉(zhuǎn)化到Y(jié)CbCr空間，只對亮度通道進行超分辨率放大。為了能夠更好地求得圖像塊與字典原子之間的最近鄰，圖像塊要盡可能多地切割。對25幅圖像進行大小為3×3的塊切割，重疊像素為2。字典的大小設(shè)置為1 024，圖像塊聚類個數(shù)~K為50，選取K為1 024個與字典原子近鄰的圖像塊。公式（11）中λ的值是為了平衡公式之間的關(guān)系，防止出現(xiàn)奇異值。這里λ的值與A+設(shè)置相同為0.1。

5.1.1圖像塊大小以及重疊像素的影響

對于近鄰嵌入來說，圖像塊的大小有著很重要的影響。因為要在切割的圖像塊庫中選擇與字典原子的近鄰圖像塊。如果圖像塊過大，則選擇的圖像塊多樣性會變少，不能保障選取的圖像塊就是距離原子最近的圖像塊，圖像塊切割過小重構(gòu)會引入人工痕跡。實驗中分別采用3×3，5×5，7×7的圖像塊，由圖2可以看出，隨著圖像塊的增大，重構(gòu)圖像的PSNR會減小。重疊像素越大，重構(gòu)圖像越平滑，圖像PSNR越大。因此實驗中選擇大小為3×3，重疊像素為2的圖像塊。

圖2　不同圖像塊大小對圖像PSNR的影響

5.1.2近鄰數(shù)目K的影響

近鄰個數(shù)的選取對實驗結(jié)果也具有很大的影響。給字典原子在圖像塊中選擇近鄰，選擇的近鄰與字典原子越接近，近鄰個數(shù)越多，圖像的重構(gòu)效果越好。圖3分別是給字典選擇1 024和2 048個圖像塊近鄰，重構(gòu)圖像的PSNR。雖然字典原子的圖像塊近鄰越多，重構(gòu)效果越好，但是圖4可以看出圖像塊越多，在計算映射函數(shù)時花費的時間也越長，為了平衡PSNR與時間復(fù)雜度之間的關(guān)系，我們在實驗中選擇1 024個圖像塊近鄰。

5.1.3字典大小的影響

實驗中將字典的大小分別設(shè)置為256，512，1024，以評估字典大小對實驗數(shù)據(jù)的影響。由圖5可以看出字典越大，重構(gòu)圖像的PSNR越好。這是因為字典原子越多，對圖像的表示越準確，字典原子的關(guān)系與圖像塊的關(guān)系也越密切。然而隨著字典原子的增大，所占的內(nèi)存空間也會增加，影響計算時間。由于圖像塊聚類減少了計算時間，這里不將犧牲字典原子作為節(jié)省時間的代價，因此設(shè)置字典的大小為1 024。

圖3　圖像塊近鄰大小對圖像PSNR的影響

圖4　圖像塊近鄰大小對計算映射函數(shù)時間的影響

圖5　字典大小對圖像PSNR的影響

5.2實驗結(jié)果對比

我們從客觀和主觀方面對圖像的重構(gòu)結(jié)果進行評估?？陀^方面通過峰值信噪比（PSNR）和時間復(fù)雜度對所提出的算法進行評估。PSNR越大，說明圖像恢復(fù)的越好。主觀方面可以從重構(gòu)圖像的紋理恢復(fù)程度，邊緣恢復(fù)程度以及引入人工痕跡的程度進行評估。表1分別將所提出的算法與雙三次插值，楊的算法，Zedey的算法，ANR算法，NE+LLE，NE+NNLS，A+算法作比較。從表1和圖6，圖7可以看出，近鄰嵌入較稀疏表示而言，具有更好的重構(gòu)效果；A+算法與其它算法比較具有更好的重構(gòu)效果。我們的算法是在A+的基礎(chǔ)上改進了計算映射函數(shù)的時間。從表1和表2（選擇1024個圖像塊近鄰，A+算法與我們算法在計算映射函數(shù)時間上的比較）看出，雖然和A+相比，PSNR并沒有提升，但是在保證PSNR不會明顯下降的情況下，減少了運行時間，這對于實際的工程應(yīng)用來說是很重要的。從視覺角度來看，圖像重構(gòu)后的效果也比較好。

表1　三倍超分辨率放大結(jié)果比較

圖6　嬰兒圖像放大三

圖7　蝴蝶圖像放大三

表2　計算映射函數(shù)所用時間

6　結(jié)論

本文提出基于稀疏表示和圖像塊近鄰的單幀圖像超分辨率重構(gòu)算法，這個算法是在已有的算法基礎(chǔ)上為了節(jié)省運行時間而提出來的。實驗結(jié)果表明，所提出的算法在減少計算時間的情況下對圖像的恢復(fù)程度也具有較好的效果。未來圖像超分辨率放大技術(shù)不僅可以用于圖片的超分辨率放大，也可以用于對視頻圖像的處理，然而如何降低學習的算法復(fù)雜度使其能夠更好地適應(yīng)環(huán)境變化以及實時處理圖片和視頻仍然是一個待解決的問題。

［1］Sun J，Xu Z，Shum H-Y.Image super-resolution using gradient profile prior［A］.IEEE Computer Society Conference on Computer Vision and Pattern Recognition （CVPR）［C］.Anchorage：IEEE，2008：1-8.

［2］D G，S B，Michal I.Super-resolution from a single image［A］.The 12th International Conference on Computer Vision［C］.Kyoto：IEEE，2009：349-356.

［3］Jianchao Y，John W，Thomas H，Yi M.Image super-resolution as sparse representation of raw image patches［A］.IEEE Conference on Computer Vision and Pattern Recognition（CVPR）［C］.Anchorage：IEEE，2008：1-8.

［4］Sun J，Zhu J，F(xiàn) TM.Context-constrained hallucination for image superresolution［A］.IEEE Conference on Computer Vision and Pattern Recognition（CVPR）［C］.San Francisco：IEEE，2010：231-238.

［5］Jianchao Y，John W，Thomas H，Yi M.Image Super-Resolution Via Sparse Representation［J］.IEEE Transactions on Image Processing，2010，19（11）：2861-2873.

［6］Jianchao Y，Zhaowen W，Zhe L，Xianbiao S，Thomas H.Bilevel sparse coding for coupled feature spaces［A］.IEEE Conference on Computer Vision and Pattern Recognition（CVPR）［C］.Providence：IEEE，2012：2360-2367.

［7］Jianchao Y，Zhaowen W，Zhe L，Scott C，Thomas H.Coupled Dictionary Training for Image Super-Resolution［J］.IEEE Transactions on Image Processing，2012，21（8）：3467-3478.

［8］Shenlong W，Lei Z，Yan L，Quan P.Semi-coupled dictionary learning with applications to image super-resolution and photo-sketch synthesis［A］.IEEE Conference on Computer Vision and Pattern Recognition（CVPR）［C］.Providence：IEEE，2012：2216-2223.

［9］Elad M，Aharon M.Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries［J］.IEEE Transactions on Image Processing，2006，15（12）：3736-3745.

［10］Weisheng D，Lei Z，Guangming S，Xin L.Nonlocally Centralized Sparse Representation for Image Restoration［J］.IEEE Transactions on Image Processing，2013，22（4）：1620-1630.

［11］Sulam J，Ophir B，Elad M.Image Denoising Through Multi-Scale Learnt Dictionaries［A］.IEEE International Conference on Image Processing［C］.Paris：IEEE，2014：808-812.

［12］Zeyde R，Elad M，Protter M.On Single Image Scale-Up Using Sparse Representations［C］.Curves and Surfaces Avignon，2010：711-730.

［13］X J.Image Super-resolution by Mid-Frequency Sparse Representation and Total Variation Regularization［J］.Journal of Electronic Imaging，2015，24（1）：13-39.

［14］Pati Y C，Rezaiifar R，Krishnaprasad P S.Orthogonal matching pursuit：recursive function approximation with applications to wavelet decomposition［A］.Conference Record of The Twenty-Seventh Asilomar Conference on Signals，Systems and Computers［C］.Asilomar：IEEE，1993：40-44.

［15］Mallat S G，Zhang Z.Matching pursuits with time-frequency dictionaries［J］.IEEE Transactions on Signal Processing，1993，41（12）：3397 -3415.

［16］Aharon M，Elad M，Bruckstein A.K-SVD：An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation［J］. IEEE Transactions on Signal Processing，2006，54 （11）：4311-4322.

［17］Rubinstein R，Zibulevsky M，Elad M.Efficient implementation of the K-SVD algorithm using batch orthogonal matching pursuit［R］.2008.

［18］Hong C，Dit-Yan Y，Yimin X.Super-resolution through neighbor embedding［A］.IEEE Computer Society Conference on Computer Vision and Pattern Recognition （CVPR）［C］.New York：IEEE，2004：275-282.

［19］Bevilacqua M，Roumy A，Guillemot C，Alberi M.Low-Complexity Single-Image Super-Resolution based on Nonnegative Neighbor Embedding［A］.The British Machine Vision Conference（BMVC）［C］.Guildford 2012：1-10.

［20］Timofte R，De Smet V，Van Gool L.Anchored Neighborhood Regression for Fast Example-Based Super Resolution［A］.International Conference on Computer Vision（ICCV）［C］.Sydney：IEEE，2013：1920-1927.

［21］Timofte R，De Smet V，Van Gool L.A+：Adjusted Anchored Neighborhood Regression for Fast Super-Resolution［A］.Asian Conference on Computer Vision（ACCV）［C］.Singapore，2014：111-126.

［22］Daubechies I，Defrise M，Mol CD.An Iterative Thresholding Algorithm for Linear Inverse Problems with A Sparsity Constraint［J］.Communications on Pure and Applied Mathematics，2004，57（11）：1413-1457.

［23］LCombettes P，Wajs VR.Signal Recovery by Proximal Forwardbackward Splitting［J］.Soc Ind Appl Math J Multiscale Model Simul，2005，4（5）：1168-1200.

［24］Zibulevsky.M，Elad.M.L1-L2 Optimization in Signal and Image Processing［J］.IEEE Signal Processing Magazine，2010，27（3）：76-88.

［25］Julien Mairal，F(xiàn)rancis Bach，Jean Ponce，Sapiro G.Online dictionary learning for sparse coding［A］.Proceeding of the 26th International Conference on Machine Learning（ICML）［C］.Montreal ACM，2009：689-696.

Image super-resolution Reconstruction Based on Sparse Representation and Neighbor embedding

Chang Zhiguo，Guo Ruxia，Li Jing，Hu Yunlu
（School of Information Engineering，Chang'an University，Xi'an710064，China）

A single frame image super-resolution reconstruction algorithm based on sparse representation and neighbor embedding was proposed.Two complete dictionaries based on sparse representation were trained for low and high resolution image patches，in which the closest image patches to the two dictionary atoms were chosen.The weight of reconstructed image patches was represented by image patches neighbor.Once weight matrix was gotten，High resolution image patch can be expressed as low resolution image patch multipling by the corresponding weight.Compared with previous algorithms，when calculating the distance between the dictionary atoms and image patches，the proposed algorithm is not each image patch to calculate.Instead image patches are clustered，and calculate the distance between dictionary atoms and the clustering center，then select image patches in the closest category.Calculated time of weight matrix can be greatly reduced，and improve the computational efficiency.The resulting PSNR compared with other algorithms，there are also improved obviously.

super-resolution reconstruction；sparse representation；complete dictionaries；neighbor embedding；weight

1671-4598（2016）05-0173-05

10.16526/j.cnki.11-4762/tp.2016.05.050

TP3

A

2015-10-21；

2015-12-08。

常志國（1976-），男，漢，山西，博士，副教授，主要從事視頻圖像處理方向的研究。