對LLE圖像超分辨率算法的幾個改進

侯志明 高陽 洪明月

摘? 要： 本文旨在對一種經典的圖像超分辨率方法——LLE算法（局部線性嵌入算法）及其代碼進行一些改進和優化。為提高對大量圖像塊的搜索速度，我們采用kd樹算法整理樣本集;鑒于像素點灰度值的非負性，我們采用非負最小二乘法而不是LLE原來的最小二乘法，確定低分辨率圖像塊與訓練樣本集中k最鄰近圖像塊的回歸系數;最后，考慮到樣本集選取和變換會對實驗結果造成影響，我們對訓練樣本圖像的若干因素進行一系列組合，通過正交實驗設計得出樣本集的最佳選取標準。實驗表明，改進后的LLE圖像超分辨率算法相比傳統的圖像插值算法和原LLE算法，效果有較大的改進。

關鍵詞： 圖像超分辨率;LLE算法;kd樹;非負最小二乘法;正交實驗設計

【Abstract】： This paper concerns of the improvement and optimization of the code of a classical example based single image super-resolution method： LLE algorithm（locally linear embedding algorithm）. For improving the speed of searching large amount of image patches， we employ the kd-tree algorithm to the example patches of? training set; furthermore instead of employing the least square regression method， we apply non-negative version of it to obtain the regression coefficients， based on the factor that the non-negative of pixel gray values of image; at last， considering the important effect of the selection and translation of examples on the results of super-resolution methods， we employ the orthogonal test design to some factors of image affine translation for example selection of training set. Experiments demonstrated that our new LLE algorithm can improve the performance greatly， comparing to conventional image interpolation methods and the original LLE method.

【Key words】： Image super-resolution; LLE algorithm; Kd-tree; Non-negative least square; Orthogonal test design

0? 引言

給定一幅低分辨率的圖像，圖像超分辨率的目的是重建一幅與其對應的高分辨率圖像[1]。是圖像處理[2-6]的一種重要技術。圖像超分辨率算法主要有三種類型：基于插值的算法;基于重構的算法;基于樣本學習的算法。LLE（局部線性嵌入）是一種經典的基于樣本學習的圖像超分辨率方法[7]。它假定圖像低分辨率塊所處的低分辨率流形和相應的圖像高分辨率塊所處的高分辨率流形有類似的幾何特征和結構[8]?；诖思俣ǎ琇LE首先進行樣本集的訓低分辨率圖像塊，并將待提升分辨率圖像塊用其k近鄰線性表示，得到表示系數。然后將表示系數應用到k近鄰相應的k個高分辨率圖像塊上，從而得到待提升分辨率低分辨率圖像塊相應的高分辨率圖像塊。LLE思路簡單，超分辨率效果好，因此經常被為超分辨設計的新算法作為比較對象，具有廣泛的應用。

本文旨在對LLE進行幾個改進，以優化它的代碼質量，提升其效果。

在尋找低分辨率圖像塊k最鄰近過程中，隨著樣本集圖像的不斷增多，圖像塊的數目急劇增多，原始k鄰近搜索算法需要計算樣本集中每個低分辨率圖像塊與待提升分辨率圖像塊的距離，然后排序，因而耗費時間急劇增加。并且這些距離計算和排序都是在線進行，因此也增加了超分辨率的時間。分析樣本集的數據特征，其實例數遠遠大于樣本維數，符合kd樹數據特征[9]，因而采用kd樹算法對樣本集進行離線構建，在提升一幅圖像的分辨率過程中只需要對kd樹進行在線索檢，這可以大大提高超分辨率的速度。

此外，LLE算法求解線性表示系數時用的是原始的最小二乘回歸法，因為圖像灰度值范圍必須非負，我們優化它為約束最小二乘法[10]，利用非負最小二乘實現這一過程[11]。

最后，經驗表明樣本集的選取對超分辨率效果會造成很大的影響。為探索最優的樣本選取標準，我們利用一種正交實驗設計方法——綜合平衡法對樣本來源、是否進行旋轉以及圖片放縮尺寸等因素進行進一步分析，從而找出最佳狀態的水平組合[12]。

綜上，我們主要做了如下三處改進：樣本集的存儲與搜索采用kd樹算法、回歸系數使用非負最小二乘法求解、樣本集來源進行多層篩選。

實驗結果表明，通過以上的改進和優化，LLE算法的性能有較大的提升。

下面我們分別對現有LLE圖像超分辨率算法的基本理論，以及我們對算法的改進進行具體說明，并在文章末尾得出最優化的樣本集選取方案。

1? LLE圖像超分辨率算法的基本理論

將低分辨率的圖像作為待提升分辨率的輸入圖像，我們通過訓練一幅甚至多于一幅的低分辨率圖像以及對應的高分辨率圖像來估計目標高分辨率圖像。每個低分辨率圖像及對應的高清晰度的圖像表示為一組小的重疊圖像補丁。和有相同數目的補丁，中每個低分辨率的補丁以及對應的在中高分辨率的補丁數目也相同。針對，以及，相應分別對應的的補丁集設為，，，。

根據LLE算法基于圖像塊流形的假定，我們希望我們的方法具有以下屬性：中的每個補丁都與從訓練集中得到的多個小補丁轉換相關聯，同時相鄰的補丁通過重疊來限制從而加強局部兼容性和平滑性。特別的，在處理重疊補丁時，我們采用均值對其進行估計，代替部分數值結果。最后我們可以得到結合kd樹以及非負最小二乘算法得到的超分辨結果。

為了對圖像超分辨率重建的結果進行質量評價，基于S-CIELAB色差模型提出的色差公式，計算均方誤根以及峰值信噪比。

其中分別為圖像行、列像素數，和分別為待比較圖像和比較圖像在位置的灰度值，通常是圖像的灰度級。

2? kd樹選取最鄰近樣本集

kd樹適用于訓練實例數遠大于空間維數時的k近鄰搜索。該算法采用一定的標準對k維空間的每一維進行二分。構造kd樹相當于不斷地用垂直于坐標軸的超平面對k維空間進行二分，從而形成一系列的k維超矩形區域，其中每一個節點對應一個k維超矩形區域。隨后基于劃分好的區域，通過目標點與劃分標準之間的比較縮小搜索區域，進而大大提高搜索效率。

2.1? 建樹過程

為直觀說明kd樹分割區域的思想，以二維數據7個樣本點為例，首先以建樹為基礎給出建樹的示意圖，如圖1所示。

根據圖1所示二叉樹，對7個樣本點每一維求方差，方差最大一維的列向量找到中位數，該列數據與中位數大小進行比較，劃分7個點為根節點（中位數所在點）、左子樹（對應列大于中位數點）、右子樹（其余點），遵循建樹過程對2維平面逐步二分，最終將7個點建成kd樹。其中點A、B、C為分割點，根節點A對X維劃分，子樹根節點B、C對Y維劃分，圖2為空間的分割面分割圖。

2.2? 搜索過程

從根節點開始，循環下列操作：

Step1當前點未被標記時執行以下循環：

（1）求其與目標點歐式距離，標記該點，若距離小于第k個近鄰點與目標點距離則更新k近鄰點;

（2）比較目標點與當前點劃分子樹維度數值大小，如果對應一邊不存在子樹則停止循環，否則將對應一邊子樹的根節點作為當前點。

Step2如果當前點為根節點則結束循環，否則執行以下操作：

（1）計算目標點與當前點父節點對應劃分維度的數值間距離;

（2）若該距離大于第k近鄰距離數值，則考慮當前點父節點是否存在另一子節點;

（3）若存在則令其為當前點，否則令當前點父節點為當前點。

下面根據上述過程對前面7個點對搜索點進行最搜索（k近鄰搜索過程類似）。

2.2.1? 確定搜索路徑

（1）計算目標點到根節點A的距離并更新當前最小距離的點為A;圖3為目標點距離更新示意圖。

（2）當目標點比A所指分割維度數值小，移動當前點至A的左子節點B;如圖4所示。

（3）重復（1）（2）直至當前點為葉子節點，即當前點移至E，因此當前搜索路徑為A→B→E。圖5為葉子節點和搜索路徑的確定示意圖。

2.2.2? 回溯至根節點

（1）由于目標點到當前點E的父節點B分割面

的距離大于最小距離，故無需搜索B的另一子節點D所在區域，故令當前點父節點B為當前點;圖6為搜索區域和父節點的確定示意圖。

（2）以目標點為圓心最近距離為半徑的圓，越過當前點B的父節點A所在分割面，故需要搜索A的另一子節點C所在區域，重新確定搜索路徑為C→G，更新最小距離;如圖7所示。

（3）重新向上回溯，由于目標點到當前點G的父節點C的分割面的距離小于最小距離，故需要搜索C的另一子節點F所在區域，令當前點為F，更新最小距離;圖8為搜索路徑的重新回溯。

（4）回溯至父節點C，令當前點為C，更新最小距離;如圖9所示。

（5）由于C的父節點A的另一子節點B所在

區域已被標記，故直接回溯至根節點A，更新最小距離搜索結束。最終得到點即為A最近鄰點。如圖10所示。

3? 非負最小二乘法確定k近鄰回歸系數

在kd樹搜索算法得到k最鄰近樣本集的基礎上，計算目標函數的最佳重構造權重，將所得的最佳重構造權重用于計算代表目標圖像的數值，其目標圖像的數值為正，因此在求權重系數時，所求的線性方程組的解出現負數是沒有意義的。雖然方程組可能得到精確解，但卻不能取負值解。如果所求的權重系數為負值，在這種情況下， 其非負最小二乘解比方程的精確解更有意義。下面我們首先利用傳統的最小二乘法求解權重系數，這就要求解下面的優化問題：

4? 樣本集選取優化

為了追求較高的樣本分辨率，檢測我們實驗的結果，不妨假設已有大的分辨率較高的目標圖像A，隨后將A縮小二倍得到輸入的小圖樣本A，然后針對小圖樣本集A進行樣本集的篩選，最后利用LLE算法進行超分辨率重建，將得到的結果與圖像A得到的結果的信噪比進行對比，旨在篩選出最好的樣本搜索方案。

4.1? 樣本來源分析

考慮到LLE算法需要構建訓練的樣本集，我們選取5幅作為A的小圖樣本集圖像輸入如圖11所示。

分別以單幅圖像形式與累加圖像形式訓練這5個樣本集，分別測得PSNR如表1所示。

根據實驗結果我們可以看到，在提高信噪比為主要目的的前提下，所有LLE算法得出結果好于插值法得到結果，同時選用自身為樣本訓練集的實驗效果明顯優于搜索其他訓練樣本得到的結果。隨著樣本集個數的增加，信噪比雖逐漸接近自身為樣本集的效果，甚至當累計5幅圖像時已經略微超過其大小，但時間上卻高了一倍之多。綜上分析，選用待放大圖像自身進行樣本集擴充可快速達到較好的效果。

4.2? 插值法對比分析

為了進一步說明用自身圖像信息作為樣本與插值法對比效果，我們隨機篩選五幅圖片進行超分辨率重建，分別采用LLE算法以及插值法進行實驗。

對于LLE算法，我們對A利用插值法進行放縮得到A、1/2 A、2 A，分別作為樣本集，隨后利用LLE算法進行超分辨率重建，分別測得PSNR如表2所示。

因此根據上述結果，分別以自身圖片信息A或2A作為樣本訓練得到PSNR平均分別比插值法高0.58466、0.39396，均優于傳統插值法的效果。而以1/2 A為樣本卻平均比插值法低0.2366，可見對A放縮后再作為樣本集會對圖像信息造成一定損失，因而直接選取A本身作為樣本集進行訓練的效果，會穩定且明顯的好于插值法。

4.3? 正交實驗確定最佳組合水平

考慮到訓練樣本的效率以及質量直接影響到超分辨率圖像重建的效率以及清晰程度，因此根據主要影響樣本集訓練導致分辨率重建性能優劣的3個因素，即訓練樣本的來源、是否對樣本集進行鏡像旋轉以及篩選好樣本后是否進行放縮進行分析。

本文采用正交實驗設計的方法，針對目標圖像的信噪比以及運行時間，利用三因素三水平正交實驗表進行實驗設計?？紤]到不同因素水平數較多，且一般情況下個水平交互作用的影響較弱，因此在不考慮交互作用的前提下進行正交實驗設計。

首先考慮第一個因素即樣本是否來自于自身信息擴增以及是否來自于隨機搜索，由于只有兩個水平我們采取虛擬水平的方法，根據樣本來源分析部分得到的結論我們可以看到，對自身進行樣本擴充的效果優于隨機搜索，因此我們將其作為第三水平。如表3所示。

隨后根據實驗設計的方法，通過求解各水平對應的平均水平，我們可以得到以信噪比為最優方案的參數組合為1，2，1，即將自身圖像加上自身水平旋轉圖像作為樣本效果最好?？紤]到第三水平恰好為第一水平，因此正交實驗表中的第8組恰好為該組合，其PSNR為25.9993比插值法要高出0.6371。得到超分辨率圖像如圖14所示。

綜上所述，在訓練樣本集時選取自身圖片信息加以旋轉，在此基礎上擴充樣本集可以較好的提高信噪比。

5? 結論與展望

為改進LLE算法的性能，我們利用kd樹搜索，以加快在訓練大規模樣本時找到最近鄰的圖像補丁。同時考慮圖像信息特點，利用非負最小二乘進行超分辨率重建，化簡算法流程。最后在改進后的算法基礎上引入實驗設計的思想，給出訓練模型時較好的樣本集篩選組合方案，為進一步提升圖像的信噪比提供可能。今后的工作聚焦于利用集群計算或云計算的工具在更大規模訓練圖像集上驗證和提升算法的性能，并尋求算法在遙感圖像處理[8]等方面的應用。

參考文獻

[1]Jianchao Yang， John Wright， Thomas S. Huang， Yi Ma. Image Super-Resolution Via Sparse Representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2010， 19（11）： 2861-2873.

[2]尹宗天， 謝超逸， 劉蘇宜， 等. 低分辨率圖像的細節還原[J]. 軟件， 2018， 39（5）： 199-202.

[3]劉鑫淼， 康朝紅， 薛樂樂. 基于ICA 的遙感圖像去噪融合研究[J]. 軟件， 2015， 36（7）： 53-56.

[4]謝佩軍. 基于復Contourlet 和各向異性擴散的圖像降噪算法[J]. 軟件， 2016， 37（4）： 35-39.

[5]曹妍， 陳偉， 徐森. 圖像去噪方法研究與仿真[J]. 軟件， 2015， 36（4）： 33-36.

[6]宋婷婷， 徐世許. 基于全采樣和 L1 范數降采樣的卷積神經網絡圖像分類方法[J]. 軟件， 2018， 39（2）： 75-80.

[7]HongChang， Dit-Yan Yeung， Yimin Xiong. Super-Resolution Through Neighbor Embedding[J]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Department of Computer Science. Hong Kong University of Science and Technology. Clear Water Bay， Kowloon， Hong Kong. 1063-6919/04.2004. pp： 1063-6919.

[8]Huihui Song， Bo Huang. Spatiotemporal Satellite Image Fusion Through One-Pair Image Learing[J]. IEEE Transactions on Geoscience and Remote Sensing. VOL. 51， NO. 4， APRIL 2013. pp： 1883-1896.

[9]張蓬郁， 王煜， 江旻宇， 邵嘉琳， 等. 基于K-D樹和機器學習的時空數據檢索-預測系統[J]. 軟件， 2018， 39（08）： 215-218.

[10]楊幸彬， 呂京國， 張丹璐，等. Dense SIFT與改進最小二乘匹配結合的傾斜航空影像匹配方法[J]. 測繪通報， 2018（10）： 32-36+70.

[11]齊永鋒， 楊樂， 火元蓮. 基于稀疏非負最小二乘編碼的高光譜遙感數據分類方法[J]. 農業機械學報， 2016， 47（07）： 332-337.

[12]張東明， 張曉云， 楊小波， 等. 基于正交實驗和多項式回歸分析方法的非典型接觸狀態車人碰撞事故參數分析[J]. 上海交通大學學報， 2019， 53（01）： 55-61.