基于BBT的鄰域嵌入單幀圖像超分辨率算法

陳躍輝，黃　淼

(1．內江職業(yè)技術學院，四川 內江 641000；2．平頂山學院 軟件學院，河南 平頂山 467000)

?

基于BBT的鄰域嵌入單幀圖像超分辨率算法

陳躍輝1，黃淼2

(1．內江職業(yè)技術學院，四川 內江 641000；2．平頂山學院 軟件學院，河南 平頂山 467000)

摘要:為了更好地解決基于學習的超分辨率算法的鄰域嵌入問題，提出了一種使用k最近鄰和平衡二叉樹的鄰域嵌入算法，該算法分為訓練階段和測試階段。訓練階段，構建HR圖像塊、LR圖像塊的映射和平衡二叉樹。測試階段，首先將輸入的去噪LR圖像分離高頻成分；然后訓練LR特征空間，利用k最近鄰尋找LR圖像對應的HR圖像塊；最后通過高斯加權重建HR圖像塊，并與先前分離的高頻成分合并。實驗采用峰值信噪比(PSNR)、結構相似性度量(SSIM)和特征相似性度量(FSIM)評估算法的效果。從實驗數據可以看出，提出的算法具有最高的PSNR值，SSIM值和FSIM值在大多數情況下高于其他算法，SSIM最高可達0.95，FSIM最高可達0.94。從實驗結果圖像可以看出，該算法的紋理保留得最好，圖像自然豐富。此外，實驗結果表明，該算法對高斯模糊和高斯噪聲的魯棒性也優(yōu)于其他算法。

關鍵詞:超分辨率重建；k最近鄰；平衡二叉樹；高斯加權；鄰域嵌入；魯棒性

超分辨率(Super-Resolution，SR)[1]技術主要通過非硬件方法提高圖像的分辨率，給用戶更多的圖像細節(jié)和更高的分辨率，SR技術在發(fā)展的三十多年里一直是機器視覺等交叉學科領域的熱門研究課題[2-3]。雖然高清攝像頭的使用比幾年前有較大的普及，但攝像環(huán)境和天氣經常影響成像的質量，利用復雜的傳感器設備獲得高分辨率(High Resolution，HR)圖像很難大面積推廣，而硬件上提高成像分辨率的代價過于昂貴，經驗表明，利用軟件提高分辨率是行之有效的方法[4]。

根據低分辨率(Low Resolution， LR)圖像的幀數，利用軟件提高圖像分辨率的方法可分為單幀SR和多幀SR。SR的核心思想是獲取非冗余的額外信息[5]，例如，單幀SR一般需要額外的數據庫以提供更多有用信息，數據庫中HR圖像塊和LR圖像塊的配對問題是單幀SR需要解決的主要問題。多幀SR中，重建的關鍵點在于獲取多幀具有子像素運動的圖像，研究表明，獲取足夠數量的非冗余圖像是多幀SR的瓶頸[6]。

本文提出了一種單幀SR算法，核心思想是通過平衡二叉樹(簡稱AVL樹)和k最近鄰(KNN)分類器快速實現HR圖像塊和LR圖像塊的映射問題，并重建SR圖像。此外，該算法可獲得明顯的去噪效果。

1相關研究

SR算法可大致分為四類，基于頻域的算法、基于插值的算法、基于重建的算法和基于學習的算法。

基于頻域的算法通過快速傅里葉變換處理圖像偏移走樣問題，例如，文獻[7]提出利用頻域和時域結合的SR算法，頻域作為一個約束條件，定義了兩個不同域的規(guī)則化項，提高了算法的收斂性和準確性，然而，該算法沒有考慮有噪聲情況，頻域對噪聲比較敏感，不能很好地適用于有噪聲的降質模型或其他復雜模型。

基于插值的算法優(yōu)勢在于快速簡單，前提是圖像先驗平滑，例如，文獻[8]提出了基于Contourlet的改進雙線性插值SR算法，增加了雙線性插值的誤差補償項，提高了視覺效果，然而，該算法沒有引入其他非冗余信息。

基于重建的算法一般用于多幀SR，重建目的是將含有不同子像素信息的圖像幀融合到一幀圖像中，利用多個先驗知識進行約束和正則化，從而提高分辨率。例如，文獻[9]提出了一種基于圖像實例的SR重建算法(In-Place Example Regression，IPER)。直接將圖像實例作為先驗知識，無需大量的學習實例，基于實例的回歸提高了運算速度，獲得了較好的重建效果。然而，文中沒有考慮復雜的降質模型，如有噪聲或運動模糊等。

基于學習的算法起初是基于稀疏表達的壓縮傳感模型，將LR圖像塊和HR圖像塊映射連接起來。例如，文獻[10]提出了一種廣義相似最近鄰域(Approximate Nearest Neighbor Field， ANNF)，將源圖像塊與目標圖像塊周圍區(qū)域進行匹配，并應用于SR算法中，具有較快的重建速度，然而，隨著參數的變化，該算法不能獲得穩(wěn)定的性能。文獻[10]實驗所用圖像均為人工圖像，自然圖像的復雜性并非總是滿足ANNF。文獻[11]提出了基于多尺度結構自相似性的單幅圖像超分辨率算法(Multi-scale Structural Self-similarity， MSS)，充分利用多尺度結構自相似性，然而，文獻[11]使用的k-svd字典庫運算效率較低，目前，效率更高的自適應字典庫更受歡迎。

本文算法的特點在于HR圖像塊和LR圖像塊的映射更加直接快速，利用平衡二叉樹加快了最近鄰搜索速度，且誤差更小。此外，本文算法將降噪后的LR圖像高頻成分保存下來，用于后續(xù)的SR重建，對改善重建圖像的質量起到了關鍵作用。

2利用k最近鄰和平衡二叉樹的鄰域嵌入

本文算法分為訓練階段和測試階段，訓練階段主要構建一對一的映射和平衡二叉樹，測試階段主要為LR圖像重建對應的SR圖像。

2.1訓練階段

訓練階段使用大量自然的HR圖像，以給定的縮放因子s進行下采樣，產生LR圖像，再以相同的縮放因子s進行上采樣。經驗表明，這個下采樣的降質過程定義了LR圖像和HR圖像的降質估計問題[12]。

(ILR)m=((IHR)↓m)↑m

(1)

式中：ILR是HR圖像通過下采樣后再進行上采樣得到的圖像；m是用于訓練的HR圖像數。將HR圖像塊與LR圖像塊的上采樣圖像差作為重疊圖像塊，并將HR和LR圖像塊保存為一對一映射，通過濾波算子f1=[-1,0,1]對LR圖像塊的向量濾波，獲得x方向的梯度圖像gx，通過濾波算子f2=[1,0,-1]T濾波后獲得y方向的梯度圖像gy。其幅值計算如下

(2)

利用平衡二叉樹進行幅值的分類，本文中，p是LR特征向量的數量，在k維數據中選擇最大方差的維度k，然后選擇中值對數據進行劃分，得到兩個子集，樹葉子結點node如式(3)所示，如果獲得R型子樹就進行R旋轉，如果是L型子樹就進行L旋轉[13]，重復所有的LR圖像塊被插入完畢，即完成了按幅值進行LR圖像塊的分類工作。

MLR_feature=[AFL1,AFL2,…,AFLp]

(3)

式中：p是LR特征向量的數量，其對應的HR圖像塊的向量表示為向量矩陣MHR_feature，數學表達形式如下

MHR_feature=[xH1,xH2,…,xHp]

(4)

訓練階段的流程圖如圖1所示。

圖1　訓練階段流程圖

2.2測試階段

在測試階段，通過訓練和LR圖像的特征重建SR圖像，使用的觀測模型為文獻[12]中的通用模型，形式如下

Yk=DkHkFkX+nk,k=1,…,N

(5)

其中，Fk是X與第k幀Yk的幾何運動算子，大小為r2M2×r2M2。r是分辨率變化因子，X可寫成向量形式，大小為r2M2×r2M2，Yk大小為M2×1。使用模糊矩陣Hk表示點擴散函數，大小為r2M2×r2M2。Dk表示抽樣算子，大小為M2×r2M2。nk是系統(tǒng)加性噪聲，一般由高斯噪聲代替，大小為M2×1。本文中k=1，不存在幾何運動算子和點擴散函數，故式(5)改寫為

y=Dx+n

(6)

在SR圖像的重建過程中，首先LR圖像通過非局部均值NLM濾波去噪，使用立方插值上采樣，Yd=(yd)↑s，然后將放大的去噪圖像Yd分割為圖像塊向量矩陣，Ydi是從Yd中提取的一個圖像塊，滿足Ydi=RiYd，其中，Ri是提取矩陣。接著，這些向量通過梯度濾波器計算其幅值，使用LR特征空間為輸入的LR特征向量矩陣尋找距離最近的k個HR圖像塊，并對其進行加權操作。

2.2.1非局部均值濾波

輸入的LR噪聲圖像通過NLM濾波器進行濾波[14]，第i個像素的估計值通過式(7)獲得

(7)

(8)

2.2.2高頻分量的分離

LR圖像包含高頻成分和大量的低頻成分，然而，上采樣過程只保留低頻成分，丟失了高頻成分，因此，從LR圖像yd分離得到高頻成分。

yHF=yd-((yd)↓s)↑s

(9)

從式(9)可以看出，高頻成分是LR圖像yd與其上采樣再下采樣變換后的圖像差，此外，高頻成分yHF通過邊緣定向插值進行匹配，獲得最終的SR圖像

xHF=((yHF)↑s)edgeIn

(10)

2.2.3k最近鄰選擇

通過LR特征空間中的向量進行Minkowski距離度量，從而獲得LR特征向量。Minkowski距離度量表示為

(11)

式中：AFLi是從LR 圖像中的第i個圖像塊的特征向量；xHi是從訓練樹中得到的第i個圖像塊特征向量；n是向量中元素的數目，選擇最近的k個鄰域后，使用LR圖像塊的索引即可找到HR圖像塊的索引。

2.2.4HR圖像塊的重建和重加權

采用歸一化的高斯權重，HR圖像塊重建如下

(12)

(13)

式中：h是圖像塊的尺寸，dj表示測試階段的LR圖像塊與訓練階段LR圖像塊之間的距離，相比傳統(tǒng)算法[15]，本文算法采用更多的鄰域圖像塊用于SR重建，其誤差也非常小，采用不同圖像塊尺寸時，knn分類器中k值與重建的SR圖像峰值信噪比PSNR的關系如圖2所示。從圖2可以看出，當圖像塊尺寸為5×5時，PSNR值最高，效果最好，k值為6時趨于穩(wěn)定，經驗表明，隨著k值增大，即最近鄰圖像塊數增加時，相比運用更少的最近鄰圖像，誤差更小。權重的獲取有助于HR圖像塊的重建，而HR的圖像塊與高頻成分合并直接關系到最終的SR圖像的重建。本文的權重關聯(lián)圖像塊尺寸和測試訓練階段的LR圖像塊距離，而這些變量直接與重建的圖像塊關系緊密。

圖2　用PSNR度量的knn分類的經驗值k

重建后的圖像x與2.2.2部分的高頻成分yHF疊加，得到最終的SR圖像，即

xSR=x+xHF

(14)

測試階段的流程圖如圖3所示。

圖3　測試階段流程圖

3實驗結果與分析

仿真實驗在配置為Win7操作系統(tǒng)、Intel酷睿II雙核處理器、2.95GHz主頻、4GbyteRAM的臺式計算機上進行。實驗平臺是MATLAB2011b。訓練階段使用150幅不同HR圖像，有自然圖像和人造圖像，由圖2可知，當尺寸為5×5時，效果最明顯，因此，訓練階段和測試階段的圖像塊尺寸均設為5×5，SR重建中k近鄰采用5NN搜索。使用圖像的峰值信噪比(PeakSignaltoNoiseRatio，PSNR)、結構相似性指標(StructuralSimilarityIndexMeasurement，SSIM)和特征相似性指標(FeatureSimilarityIndexMeasurement，FSIM)評估SR重建圖像的效果，考慮到評估中的計算量問題，實驗中所有彩色圖像均轉換為灰度圖像進行評估。

3.1實驗結果比較

實驗所用圖像大多來自文獻[9]和KoDak數據庫，用于比較的算法是文獻[9]提出的IPER算法、文獻[10]提出的ANNF算法和文獻[11]提出基于MSS算法。

3.1.1縮放因子為2時的重建結果

這部分所有圖像都放大2倍，表1為沒有添加噪聲的重建圖像的PSNR值，加粗的為最大值。從表1可以看出，本文算法重建的SR圖像具有最高的PSNR值，丟失的高頻成分最少，其次是IPER算法。表2為沒有添加噪聲情況下SSIM結果，可以看出，本文算法在大多數情況下SSIM值均保持最高，只在Lena圖像上的結果略低于IPER算法，其中，ANNF算法的最差，這是由于ANNF算法的不穩(wěn)定性造成的。表3為不添加噪聲情況下FSIM的結果，本文算法在Leaves和Baboon圖像上的FSIM值略低于其他算法，在大多數情況下均為最高。圖4為加上高斯噪聲后的重建效果，可以看出，本文算法去噪效果非常明顯，歸功于測試階段去噪的作用。

表1　分辨率增強因子為2時各算法的PSNR值

表2　分辨率增強因子為2時各算法的SSIM值

3.1.2縮放因子為4時的重建結果

這部分所有圖像都放大4倍，更具挑戰(zhàn)性，表4為沒有添加噪聲情況下重建后的PSNR值、SSIM值和FSIM值，加粗的為最大值。從表4可以看出，在3幅圖像Wall、Leaves和Baboon上的實驗，本文算法3個度量值均達到最高，其次是IPER算法，ANNF算法表現最差。圖5所示為放大4倍的Leaves圖像，可以看出，本文算法塔的邊緣非常清晰，葉子也比較自然。這些現象體現了本文算法在重建較大縮放因子的SR圖像方面的優(yōu)勢，運用knn和平衡二叉樹的鄰域嵌入具有較小的誤差和較好的穩(wěn)定性。

表3　分辨率增強因子為2時各算法的FSIM值

圖4　加高斯噪聲(均值為0，方差為20)后，放大2倍的重建效果

3.2噪聲和高斯模糊的影響

由于運動模糊的字典訓練學習非常困難，沒有討論如文獻[12]的幾何運動和運動模糊。這部分討論高斯噪聲方差大小及其模糊核尺寸對超分辨率重建效果的影響。

表4　分辨率增強因子為4時各算法評估

圖5　放大4倍的重建效果

圖6所示為高斯噪聲方差與20幅重建圖像平均PSNR之間的關系，可以看出，隨著噪聲方差的增大，本文算法的PSNR值曲線下降得最慢，其他算法受噪聲影響較大。圖7是高斯卷積核的大小與PSNR的關系，可以看出，隨著卷積核尺寸的增大，本文算法的PSNR值下降最慢，ANNF與本文算法非常接近。圖8所示為高斯卷積核大小與SSIM之間的關系?？梢钥闯觯c圖6、圖7類似，本文算法的SSIM值下降最慢。從圖7和圖8可以看出，本文算法對于高斯模糊的魯棒性更好，ANNF算法與本文算法非常接近，這是由于ANNF算法只考慮LR和HR圖像塊可能配對的鄰域[16-17]，相比本文算法，條件更加寬松。

圖6　高斯噪聲方差與PSNR關系

圖7　高斯核尺寸與PSNR關系

圖8　高斯核尺寸與SSIM關系

4結論與展望

本文利用平衡二叉樹和k最近鄰解決單幀超分辨率中的HR圖像塊與LR圖像塊的映射問題，使映射更加直接快速，同時在SR算法中將LR圖像的高頻成分保留下來，利用非局部均值濾波去噪。仿真實驗表明，本文算法的結果更接近真實HR圖像，紋理更加清晰自然，且對部分高斯模糊和高斯白噪聲具有較好的魯棒性。

未來將重點研究帶有模糊的字典學習方法，并將其用于處理有一定運動模糊的SR問題，帶有運動模糊的字典將更具有挑戰(zhàn)性。

參考文獻：

[1]洪逸飛，姚琦敏，張貽雄. 一種基于MAP的圖像超分辨率重建算法[J]. 電視技術，2014(7)：20-25.

[2]楊文波. 航空圖像超分辨率重構技術研究[D]. 長春：長春光學精密機械與物理研究所，2014.

[3]MALLATS，YUG.Super-resolutionwithsparsemixingestimators[J].IEEEtransactionsonimageprocessing，2009，19(11)：2889-2900.

[4]HEDDEPN，NIENHAUSGU.Super-resolutionlocalizationmicroscopywithphotoactivatablefluorescentmarkerproteins[J].Protoplasma， 2014， 251(2)： 349-362.

[5]浦劍， 張軍平， 黃華. 超分辨率算法研究綜述[J]. 山東大學學報(工學版)，2009，27(1)：758-763.

[6]張占武， 朱秀昌. 基于自相似性約束的視頻稀疏超分辨率重建[J]. 電視技術， 2014，38(11)：9-14.

[7]楊欣，費樹岷，周大可. 基于頻域、時域相結合的自適應圖像超分辨率重建[J]. 控制與決策，2012，27(9)： 869-875.

[8]蔡念，張海員，張楠. 基于Contourlet的改進雙線性插值圖像超分辨率算法[J]. 傳感技術學報，2011，24(1)：59-64.

[9]YANGJ，LINZ，COHENS.Fastimagesuper-resolutionbasedonin-placeexampleregression[J].IEEEconferenceoncomputervision&patternrecognition，2013，9(4)：1059-1066.

[10]RAMAKANTHSA，BABURV.FeatureMatch：ageneralANNFestimationtechniqueanditsapplications[J].IEEEtransactionsonimageprocessingapublicationoftheIEEEsignalprocessingsociety，2014，23(5)：2193-2205.

[11]潘宗序，禹晶，胡少興，等. 基于多尺度結構自相似性的單幅圖像超分辨率算法[J]. 自動化學報，2014，40(4)：594-603.

[12]FARSIUS，ROBINSOND，ELADM，etal.Fastandrobustmulti-framesuper-resolution[J].IEEEtransactionsonimageprocessing，2003，13(10)：1327-1344.

[13]BEISJS，LOWEDG.Shapeindexingusingapproximatenearest-neighboursearchinhigh-dimensionalspaces[C]//Proc. 1997IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition. [S.l.]：IEEE，1997，31(12)：1000-1006.

[14]BUADESA，COLLB，MORELJM.Anon-localalgorithmforimagedenoising[C]//IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition. [S.l.]：IEEE，2005，17(2)：60-65.

[15]GAOX，ZHANGK，TAOD，etal.Imagesuper-resolutionwithsparseneighborembedding[J].IEEEtransactionsonimageprocessing，2012，21(7)：3194-3205.

[16]盧振泰，馮衍秋，馮前進，等. 基于主相位一致性的醫(yī)學圖像配準[J]. 電子學報，2008，36(10)：1974-1978.

[17]褚江，陳強，楊曦晨. 全參考圖像質量評價綜述[J]. 計算機應用研究，2014，31(1)：13-22.

責任編輯：閆雯雯

Single frame super resolution algorithm based on neighborhood embedding using k-nearest neighbor and balanced binary tree

CHEN Yuehui1，HUANG Miao2

(1．ComputerManagementCenter，NeijiangVocationalandTechnicalCollege，SichuanNeijiang641000，China；2．CollegeofSoftware，PingdingshanUniversity，HenanPingdingshan467000，China)

Abstract:In order to better solve the issue of neighborhood embedding in learning-based super-resolution algorithm， the neighborhood embedding algorithm using k-nearest neighbor and balanced binary tree is proposed. The algorithm is divided into training phase and testing phase， the training phase mainly deals with the mapping of HR patches to LR patches and builds the balanced binary tree. In the testing phase， the high-frequency of the input de-noised LR images is separated firstly. Then， LR feature space is trained， and HR patches corresponding to the LR patches are searched with k-nearest neighbor. Finally， HR patches are reconstructed by Gaussian weighting， and merged with the separated high-frequency component. In this paper， PSNR， SSIM and FSIM are used to measure the results of the algorithms. The data results show that the proposed algorithm has the highest PSNR value， and the SSIM and FSIM values are highest in most cases. The SSIM value can be up to 0.95 at most， and the FSIM value can be up to 0.94.The experimental image results show that the image’s texture can be reserved best， the reconstructed images are very natural. In addition， the experimental results show the robustness to Gauss blur and Gauss noise of the proposed algorithm is much better than other algorithms.

Key words:super resolution reconstruction； k-nearest neighbor； balanced binary tree； Gaussian weighting； neighborhood embedding； robustness

中圖分類號：TP391

文獻標志碼：A

DOI：10.16280/j.videoe.2016.05.027

作者簡介：

陳躍輝(1982— )，碩士，講師，主要研究領域為圖像處理、智能算法等；

黃淼(1982— )，碩士，講師，主要研究領域為圖形圖像處理、模式識別等。

收稿日期：2015-09-17

文獻引用格式：陳躍輝，黃淼. 基于BBT的鄰域嵌入單幀圖像超分辨率算法[J].電視技術，2016，40(5)：129-135.

CHEN Y H， HUANG M. Single frame super resolution algorithm based on neighborhood embedding using k-nearest neighbor and balanced binary tree [J].Video engineering，2016，40(5)：129-135.