基于系數復用和字典訓練的圖像超分辨率算法

史國川，龔連友

(陸軍軍官學院 計算中心，安徽 合肥 230031)

0 引 言

作為數字圖像處理領域的熱點之一，圖像的超分辨率[1-2](super resolution，SR)重建一直是廣大研究者的重點研究方向。由于目前軟硬件等條件的限制，得到的圖像分辨率難以滿足實際應用中的要求，這就需要對低分辨率圖像進行SR重建以此來提高圖像的分辨率。Freeman等[3]提出的基于實例進行字典訓練的重建算法是其中的經典算法。該算法通過對圖像塊進行約束，建立高低分辨率圖像塊間的對應關系，但是該過程需要訓練的數據量大、耗時長，而且在重建過程中還需要大量時間對數據庫進行搜索匹配，因此該算法效率不高。Yang等[4]利用稀疏表示對圖像進行SR重建。該算法首先對圖像進行稀疏表示，然后選擇一組特定的稀疏基，使得不同分辨率的圖像塊能用相同的稀疏表示對其進行描述。該算法明顯降低了算法重建過程中的耗時，并且重構圖像的分辨率得到了提高；但是沒有對字典訓練過程進行優化，因此在字典訓練階段仍需大量時間。奇異值分解[5](K-SVD)作為圖像SR重建領域經典的字典訓練算法之一，因其較好的重建結果，自提出以來得到了廣泛的應用。但是K-SVD算法存在字典訓練耗時長，重建恢復的圖像分辨率不高等缺點。Leslie等[6]提出一種改進的復合字典訓練和系數復用算法，但并沒有將其應用到圖像的超分辨率重建中。

在上述研究的基礎上，文中提出一種基于系數復用和稀疏表示[7-14]的改進K-SVD字典訓練算法，在圖像的稀疏表示以及字典更新過程中對算法進行優化改進，在明顯降低算法耗時的同時進一步提高了重建超分辨率圖像的質量。

1 基于稀疏表示的圖像超分辨率重建算法

研究表明，可以通過對一幅高分辨率(HR)圖像進行下采樣和模糊處理來獲取其低分辨率(LR)圖像。當使用狄拉克函數δ作為模糊核時，直接對HR圖像進行下采樣處理即可得到其低分辨率圖像，而不用再進行模糊處理，因此，可以將超分辨率重建問題轉化為圖像插值問題。作為一個典型的逆向問題，圖像超分辨率重建可以用如下公式進行描述：

y=SBx+v

(1)

其中，x表示原始HR圖像；B表示模糊算子；S表示下采樣算子；v表示添加的噪聲；y表示已獲的LR圖像。

將B定義為一個矩陣，同時令v=0，代入式(1)中有y=Sx，因此可以認為y是通過對x進行下采樣得到的。

通過式(1)對x進行重建是一個非唯一解的逆向問題，在稀疏表示過程中，假定在利用字典(D)約束后圖像在某些域內是稀疏的，即在公式x≈Dα中，矩陣α中的絕大多數元素都是接近于0的。因而稀疏表示的正則化矩陣[15-16]可以表示為R(x)=‖α‖0。由于求解過程是非凸的，最優化的稀疏表示結果難以得到，可以采用凸處理對其進行近似求解，公式如下：

(2)

由于求解α過程只考慮了低分辨率情況，而圖像SR重建需要確定高低分辨率圖像在高低分辨率過完備字典的相同稀疏表示，因此DCT就成為利用稀疏表示進行圖像SR重建的重要內容。

2 K-SVD字典訓練算法

K-SVD算法最先由Aharon[5]等提出，該算法在確保不丟失初始字典所有信息的條件下有效減少了生成的過完備字典[15-16](DCT)中原子的數量。

字典訓練實際上是對一個問題進行優化求解，可以用公式表示如下：

‖αi‖0≤t0

(3)

在接收到輸入信號之后，開始進行字典訓練，在訓練過程中，需要確定過完備字典D與其稀疏表示A。但是，在實際操作中對兩個未知參數同時進行優化求解是非常復雜的，因此假設已經確定了字典D，式(3)的優化問題就可以轉化成求解訓練樣本集合X的稀疏表示矩陣A，然后利用Aharon提出的追蹤算法確定稀疏表示的分解因子。

(4)

(5)

3 改進的K-SVD算法

3.1 對字典更新階段的改進

(6)

由于矩陣AAT規模龐大，用常規方法求解計算量大，耗時長，而利用XAT=DAAT對其進行迭代求解，在明顯減小迭代次數的同時可以得到一個理想的近似解。需要注意的是，K-SVD算法不僅對D中的原子進行了更新，而且將A中所有不為0的系數與之相乘。因此，K-SVD在字典更新階段對D和A同時進行了更新。根據K-SVD算法的特點，改進算法的目的是在保證A的完整性條件下找到同時對D和A進行更新的方法，根據式(7)對D和A進行優化。

(7)

在滿足條件A?M=0的同時還要保證A中所有0系數的完整性，其中A?M表示兩個相同大小矩陣之間的乘法，M表示只含0、1元素的掩碼矩陣，M={|A|=0}，其值由式(8)確定。

(8)

求解過完備字典是一個非凸問題，直接計算難度較大。首先，將DA分解成秩為1的矩陣之和，然后代入式(7)中得到：

n,mj?αj=0

(9)

基于式(10)中的SVD矩陣，采用塊坐標下降法對(dj,αj),j=1,2,…,n進行逐項優化。

(10)

傳統K-SVD字典訓練算法通常只進行一次(j=1,2,…,n)字典更新計算，而改進算法為了獲得更接近式(7)所描述的整體解決方案，會進行多次(j=1,2,…,n)更新計算。

盡管改進算法在某種程度上增加了計算復雜度，但是這種新增的復雜度在整個字典更新過程中幾乎可以忽略不計，這是因為在絕大多數情況下，字典訓練的計算量集中于稀疏編碼階段，即表明所增加的額外計算量在整體運行時幾乎保持不變，因此改進前后的K-SVD算法在計算復雜度方面基本相等。

3.2 正交匹配追蹤中的系數復用

假設給定一個已經更新的字典，K-SVD算法能夠對其進行搜索，然后根據得到的稀疏表示結果對數據進行訓練。如果選擇先前計算的表示，使目標函數保持在相同的高度。這表明，可以使用給定的表示，作為追蹤階段的良好開始，然而，這并不意味著能夠改進結果。

利用該方法對追蹤算法中的系數進行初始化時，可能會陷入各種松弛或貪心的稀疏編碼[17-18]方法中。文中專注于貪心追蹤算法中一個特定的變量，它建立在CoSaMP[10]和Subspace Pursuit[11]的追蹤算法之上，與這些方法不同的是，改進算法中有k/3個最大系數的初始值來自于前期的追蹤階段，然后像CoSaMP和SP算法一樣進行一個系數增大和修剪的過程，這就是正交匹配追蹤中的系數復用算法(CoefROMP)。

CoefROMP算法流程如下：

輸入：D，x，α0(初始值)和k(目標基數)。

初始化(n=0)：從α0中取最大的k/3個元素，T0:=(|α0|,k/3)；r0:=x-DT0αT0；ε0:=‖r0‖2。

從n=1開始進行如下迭代計算，直到達到最大迭代次數結束循環：

(1)從預計剩余中取值最大的k/3個元素，Sn:=(|DTrn-1|,k/3)；

(5)更新稀疏表示：αn:=(DTn)+x；

(6)更新剩余值：rn:=x-DTnαn，εn:=‖rn‖2；

(7)當滿足條件εn>εn-1時，退出循環。

輸出：更新后的稀疏表示α。

4 實驗結果與分析

4.1 字典更新階段

實驗中選擇了一組被廣泛用于字典訓練的圖片集合作為標準圖像庫，從這些圖片中提取50 000個圖像塊用于訓練更新。減去所有圖像塊的平均值，用以消除需要使用的數據矢量的常數偏移系數，稀疏表示的質量高低取決于字典中原子的數目n和其中的非0系數數量k。假設信號的維度為d，那么有n=3d，k=round(d/10)，同時，利用訓練樣本得到的數據對字典進行初始化。

實驗在Matlab R2014a，CUP為雙核2.3 GHz，內存為4 GB，操作系統為Windows7的手提計算機上進行。將傳統的K-SVD作為基準算法，采用8×8的圖像塊(d=64)和64×192大小的字典，因此，稀疏表示基數k=6。通過圖1可知，訓練數據可以從幾次更新周期中獲益，并且每一個更新周期計算成本小；另外，大部分的增益發生在前幾次迭代過程中。

圖1 不同次數字典更新對比

4.2 系數復用階段

將傳統正交匹配追蹤算法與改進后的正交匹配追蹤算法進行比較。實驗中，仍然選擇50 000個圖像塊用于字典訓練，利用15×15大小的圖像塊進行實驗，因此與之對應的向量長度為225，被訓練的字典大小為225×675，稀疏表示基數k=23。實驗結果如圖2所示。分析圖2可知，與傳統的OMP[12]算法相比，CoefROMP算法在降低均方根誤差和計算耗時方面有明顯的提高。

圖2 兩種正交匹配追蹤對比

4.3 重建結果比較

實驗以雙三次插值算法為基準，對改進后的K-SVD算法與傳統K-SVD的實驗結果進行比較，判斷三種重建算法的優劣。在三種重建算法的基本參數與字典訓練過程均相同的情況下，其中圖像塊數量為50 000個，字典大小為64×192，分別使用標準圖像中Raccoon(109×100)、Girl(85×86)和Flower(110×57)圖像進行重建實驗，結果如圖3～5所示。

圖3 三種算法的重建結果比較(Raccoon)

圖4 三種算法的重建結果比較(Girl)

根據圖3～5的觀察，并將三種算法所得結果與原始高分辨率圖像對比可知，在三種重建算法中，文中算法在Raccoon的毛皮、Girl鼻翼的雀斑以及Flower的葉莖等細節上具有更好的表現，重建獲得的圖像質量最高，與原高分辨率圖像最為接近，說明改進后的K-SVD算法是最優的。

圖5 三種算法的重建結果比較(Flower)

5 結束語

通過對基于稀疏表示的經典K-SVD字典訓練算法中字典更新階段的改進，結合正交匹配追蹤中的系數復用算法，設計了一種新的超分辨率重建算法。該算法極大地降低了重建過程中字典訓練所消耗的時間，只需幾分鐘對原有的字典進行更新即可。將新算法得到的字典采用稀疏表示對不同圖像進行超分辨率重建，提高了重建圖像的質量。

[1] 蘇 衡，周 杰，張志浩.超分辨率圖像重建方法綜述[J].自動化學報,2013,39(8):1202-1213.

[2] YANG J,LIN Z,COHEN S.Fast image super-resolution based on in-place example regression[C]//Computer vision and pattern recognition.Washington,DC,USA:IEEE Computer Society,2013:1059-1066.

[3] FREEMAN W T,PASZTOR E C,CARMICHAEL O T.Example-based super resolution[J].IEEE Computer Graphics and Applications,2002,22(2):56-65.

[4] YANG J,WRIGHT J,HUANG T,et al.Image super-resolution via sparse representation[J].IEEE Transactions on Image Processing,2010,19(11):2861-2873.

[5] AHARON M,ELAD M,BRUCKSTEIN A.K-SVD:an algorithm for designing of complete dictionaries for sparse representation[J].IEEE Transactions on Signal Processing,2006,54(11):4311-4322.

[6] LESLIE N S,ELAD M.Improving dictionary learning:multiple dictionary updates and coefficient reuse[J].IEEE Signal Processing Letters,2013,20(1):79-82.

[7] 張 瑞,馮象初,王斯琪,等.基于稀疏梯度場的非局部圖像去噪算法[J].自動化學報,2015,41(9):1542-1552.

[8] 徐國明,薛模根,崔懷超.基于過完備字典的魯棒性單幅圖像超分辨率重建模型及算法[J].計算機輔助設計與圖形學學報,2012,24(12):1599-1605.

[9] 徐國明,薛模根,袁廣林.基于混合高斯稀疏編碼的圖像超分辨率重建方法[J].光電工程,2013,40(3):94-101.

[10] NEEDELL D,TROPP J A.CoSAMP:iterative signal recov-

ery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis,2008,26:301-321.

[11] DAI D,MILENKOVIC O.Subspace pursuit for compressive sensing[J].IEEE Transactions on Information Theory,2009,55(5):2230-2249.

[12] 李少東,裴文炯,楊 軍,等.貝葉斯模型下的OMP重構算法及應用[J].系統工程與電子技術,2015,37(2):246-252.

[13] LIU D,WANG Z,WEN B,et al.Robust single image super-resolution via deep networks with sparse prior[J].IEEE Transactions on Image Processing,2016,25(7):3194-3207.

[14] TIMOFTE R,DE V,GOOL L V.Anchored neighborhood regression for fast example-based super-resolution[C]//IEEE international conference on computer vision.Washington,DC,USA:IEEE Computer Society,2013:1920-1927.

[15] 李 娟,吳 謹,陳振學,等.基于自學習的稀疏正則化圖像超分辨率方法[J].儀器儀表學報,2015,36(1):194-200.

[16] 孫玉寶,費 選,韋志輝,等.基于前向后向算子分裂的稀疏性正則化圖像超分辨率算法[J].自動化學報,2010,36(9):1232-1238.

[17] 沈 輝,袁曉彤,劉青山.基于預測稀疏編碼的快速單幅圖像超分辨率重建[J].計算機應用,2015,35(6):1749-1752.

[18] 潘宗序,禹 晶,肖創柏,等.基于自適應多字典學習的單幅圖像超分辨率算法[J].電子學報,2015,43(2):209-216.