侯志明 高陽(yáng) 洪明月

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1? 建樹過程

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

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

2.2? 搜索過程

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

Step1當(dāng)前點(diǎn)未被標(biāo)記時(shí)執(zhí)行以下循環(huán)：

（1）求其與目標(biāo)點(diǎn)歐式距離，標(biāo)記該點(diǎn)，若距離小于第k個(gè)近鄰點(diǎn)與目標(biāo)點(diǎn)距離則更新k近鄰點(diǎn);

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

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

（1）計(jì)算目標(biāo)點(diǎn)與當(dāng)前點(diǎn)父節(jié)點(diǎn)對(duì)應(yīng)劃分維度的數(shù)值間距離;

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

（3）若存在則令其為當(dāng)前點(diǎn)，否則令當(dāng)前點(diǎn)父節(jié)點(diǎn)為當(dāng)前點(diǎn)。

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

2.2.1? 確定搜索路徑

（1）計(jì)算目標(biāo)點(diǎn)到根節(jié)點(diǎn)A的距離并更新當(dāng)前最小距離的點(diǎn)為A;圖3為目標(biāo)點(diǎn)距離更新示意圖。

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

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

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

（1）由于目標(biāo)點(diǎn)到當(dāng)前點(diǎn)E的父節(jié)點(diǎn)B分割面

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

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

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

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

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

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

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

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

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

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

4.1? 樣本來源分析

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

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

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

4.2? 插值法對(duì)比分析

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

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

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

4.3? 正交實(shí)驗(yàn)確定最佳組合水平

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

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

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

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

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

5? 結(jié)論與展望

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

參考文獻(xiàn)

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

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

[4]謝佩軍. 基于復(fù)Contourlet 和各向異性擴(kuò)散的圖像降噪算法[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樹和機(jī)器學(xué)習(xí)的時(shí)空數(shù)據(jù)檢索-預(yù)測(cè)系統(tǒng)[J]. 軟件， 2018， 39（08）： 215-218.

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

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

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