侯志明 高陽 洪明月

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

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

【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? 引言

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

本文旨在對LLE進行幾個改進，以優(yōu)化它的代碼質(zhì)量，提升其效果。

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1? 建樹過程

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

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

2.2? 搜索過程

從根節(jié)點開始，循環(huán)下列操作：

Step1當前點未被標記時執(zhí)行以下循環(huán)：

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

（2）比較目標點與當前點劃分子樹維度數(shù)值大小，如果對應(yīng)一邊不存在子樹則停止循環(huán)，否則將對應(yīng)一邊子樹的根節(jié)點作為當前點。

Step2如果當前點為根節(jié)點則結(jié)束循環(huán)，否則執(zhí)行以下操作：

（1）計算目標點與當前點父節(jié)點對應(yīng)劃分維度的數(shù)值間距離;

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

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

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

2.2.1? 確定搜索路徑

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

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

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

2.2.2? 回溯至根節(jié)點

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

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

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

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

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

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

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

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

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

4? 樣本集選取優(yōu)化

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

4.1? 樣本來源分析

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

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

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

4.2? 插值法對比分析

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

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

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

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

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

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

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

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

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

5? 結(jié)論與展望

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

參考文獻

[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]尹宗天， 謝超逸， 劉蘇宜， 等. 低分辨率圖像的細節(jié)還原[J]. 軟件， 2018， 39（5）： 199-202.

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

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

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

[6]宋婷婷， 徐世許. 基于全采樣和 L1 范數(shù)降采樣的卷積神經(jīng)網(wǎng)絡(luò)圖像分類方法[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樹和機器學(xué)習(xí)的時空數(shù)據(jù)檢索-預(yù)測系統(tǒng)[J]. 軟件， 2018， 39（08）： 215-218.

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

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

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