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

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

　　圖像方向投稿知識：評職稱發表計算機圖像處理方向的論文

　　計算機方向技術人員在評定職稱時會發表圖像處理的論文，也有很多高校老師咨詢我們的編輯，覺得評職稱難度太大，要求也高，小編介紹其實發表計算機圖像處理類的論文并沒有大家想象中的那么難，在我們編輯老師的指導下，幫助大家安排論文，并且推薦合適的期刊，這樣就可以節省大家的時間精力，具體計算機論文發表相關知識，您可以咨詢我們的編輯老師，一對一解答更加方便快捷。

　　0引言

　　給定一幅低分辨率的圖像，圖像超分辨率的目的是重建一幅與其對應的高分辨率圖像[1]。是圖像處理[2-6]的一種重要技術。圖像超分辨率算法主要有三種類型：基于插值的算法;基于重構的算法;基于樣本學習的算法。LLE(局部線性嵌入)是一種經典的基于樣本學習的圖像超分辨率方法[7]。它假定圖像低分辨率塊所處的低分辨率流形和相應的圖像高分辨率塊所處的高分辨率流形有類似的幾何特征和結構[8]。

　　基于此假定，LLE首先進行樣本集的訓低分辨率圖像塊，并將待提升分辨率圖像塊用其k近鄰線性表示，得到表示系數。然后將表示系數應用到k近鄰相應的k個高分辨率圖像塊上，從而得到待提升分辨率低分辨率圖像塊相應的高分辨率圖像塊。LLE思路簡單，超分辨率效果好，因此經常被為超分辨設計的新算法作為比較對象，具有廣泛的應用。本文旨在對LLE進行幾個改進，以優化它的代碼質量，提升其效果。在尋找低分辨率圖像塊k最鄰近過程中，隨著樣本集圖像的不斷增多，圖像塊的數目急劇增多，原始k鄰近搜索算法需要計算樣本集中每個低分辨率圖像塊與待提升分辨率圖像塊的距離，然后排序，因而耗費時間急劇增加。并且這些距離計算和排序都是在線進行，因此也增加了超分辨率的時間。

　　分析樣本集的數據特征，其實例數遠遠大于樣本維數，符合kd樹數據特征[9]，因而采用kd樹算法對樣本集進行離線構建，在提升一幅圖像的分辨率過程中只需要對kd樹進行在線索檢，這可以大大提高超分辨率的速度。此外，LLE算法求解線性表示系數時用的是原始的最小二乘回歸法，因為圖像灰度值范圍必須非負，我們優化它為約束最小二乘法[10]，利用非負最小二乘實現這一過程[11]。

　　最后，經驗表明樣本集的選取對超分辨率效果會造成很大的影響。為探索最優的樣本選取標準，我們利用一種正交實驗設計方法——綜合平衡法對樣本來源、是否進行旋轉以及圖片放縮尺寸等因素進行進一步分析，從而找出最佳狀態的水平組合[12]。綜上，我們主要做了如下三處改進：樣本集的存儲與搜索采用kd樹算法、回歸系數使用非負最小二乘法求解、樣本集來源進行多層篩選。實驗結果表明，通過以上的改進和優化，LLE算法的性能有較大的提升。下面我們分別對現有LLE圖像超分辨率算法的基本理論，以及我們對算法的改進進行具體說明，并在文章末尾得出最優化的樣本集選取方案。

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

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

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

　　2kd樹選取最鄰近樣本集

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

　　2.1建樹過程

　　為直觀說明kd樹分割區域的思想，以二維數據7個樣本點為例，首先以建樹為基礎給出建樹的示意圖，對7個樣本點每一維求方差，方差最大一維的列向量找到中位數，該列數據與中位數大小進行比較，劃分7個點為根節點(中位數所在點)、左子樹(對應列大于中位數點)、右子樹(其余點)，遵循建樹過程對2維平面逐步二分，最終將7個點建成kd樹。其中點A、B、C為分割點，根節點A對X維劃分，子樹根節點B、C對Y維劃分。

　　2.2搜索過程

　　從根節點開始，循環下列操作：Step1當前點未被標記時執行以下循環：(1)求其與目標點歐式距離，標記該點，若距離小于第k個近鄰點與目標點距離則更新k近鄰點;(2)比較目標點與當前點劃分子樹維度數值大小，如果對應一邊不存在子樹則停止循環，否則將對應一邊子樹的根節點作為當前點。Step2如果當前點為根節點則結束循環，否則執行以下操作：(1)計算目標點與當前點父節點對應劃分維度的數值間距離;(2)若該距離大于第k近鄰距離數值，則考慮當前點父節點是否存在另一子節點;(3)若存在則令其為當前點，否則令當前點父節點為當前點。下面根據上述過程對前面7個點對搜索點進行最搜索(k近鄰搜索過程類似)。

　　3非負最小二乘法確定

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

　　4樣本集選取優化

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

　　5結論與展望

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

　　參考文獻

　　[1]JianchaoYang,JohnWright,ThomasS.Huang,YiMa.ImageSuper-ResolutionViaSparseRepresentation[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,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.