基于BBT的邻域嵌入单帧图像超分辨率算法

陈跃辉，黄　淼

(1．内江职业技术学院，四川 内江 641000；2．平顶山学院 软件学院，河南 平顶山 467000)



基于BBT的邻域嵌入单帧图像超分辨率算法

陈跃辉1，黄淼2

(1．内江职业技术学院，四川 内江 641000；2．平顶山学院 软件学院，河南 平顶山 467000)

摘要:为了更好地解决基于学习的超分辨率算法的邻域嵌入问题，提出了一种使用k最近邻和平衡二叉树的邻域嵌入算法，该算法分为训练阶段和测试阶段。训练阶段，构建HR图像块、LR图像块的映射和平衡二叉树。测试阶段，首先将输入的去噪LR图像分离高频成分；然后训练LR特征空间，利用k最近邻寻找LR图像对应的HR图像块；最后通过高斯加权重建HR图像块，并与先前分离的高频成分合并。实验采用峰值信噪比(PSNR)、结构相似性度量(SSIM)和特征相似性度量(FSIM)评估算法的效果。从实验数据可以看出，提出的算法具有最高的PSNR值，SSIM值和FSIM值在大多数情况下高于其他算法，SSIM最高可达0.95，FSIM最高可达0.94。从实验结果图像可以看出，该算法的纹理保留得最好，图像自然丰富。此外，实验结果表明，该算法对高斯模糊和高斯噪声的鲁棒性也优于其他算法。

关键词:超分辨率重建；k最近邻；平衡二叉树；高斯加权；邻域嵌入；鲁棒性

超分辨率(Super-Resolution，SR)[1]技术主要通过非硬件方法提高图像的分辨率，给用户更多的图像细节和更高的分辨率，SR技术在发展的三十多年里一直是机器视觉等交叉学科领域的热门研究课题[2-3]。虽然高清摄像头的使用比几年前有较大的普及，但摄像环境和天气经常影响成像的质量，利用复杂的传感器设备获得高分辨率(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算法，频域作为一个约束条件，定义了两个不同域的规则化项，提高了算法的收敛性和准确性，然而，该算法没有考虑有噪声情况，频域对噪声比较敏感，不能很好地适用于有噪声的降质模型或其他复杂模型。

基于插值的算法优势在于快速简单，前提是图像先验平滑，例如，文献[8]提出了基于Contourlet的改进双线性插值SR算法，增加了双线性插值的误差补偿项，提高了视觉效果，然而，该算法没有引入其他非冗余信息。

基于重建的算法一般用于多帧SR，重建目的是将含有不同子像素信息的图像帧融合到一帧图像中，利用多个先验知识进行约束和正则化，从而提高分辨率。例如，文献[9]提出了一种基于图像实例的SR重建算法(In-Place Example Regression，IPER)。直接将图像实例作为先验知识，无需大量的学习实例，基于实例的回归提高了运算速度，获得了较好的重建效果。然而，文中没有考虑复杂的降质模型，如有噪声或运动模糊等。

基于学习的算法起初是基于稀疏表达的压缩传感模型，将LR图像块和HR图像块映射连接起来。例如，文献[10]提出了一种广义相似最近邻域(Approximate Nearest Neighbor Field， ANNF)，将源图像块与目标图像块周围区域进行匹配，并应用于SR算法中，具有较快的重建速度，然而，随着参数的变化，该算法不能获得稳定的性能。文献[10]实验所用图像均为人工图像，自然图像的复杂性并非总是满足ANNF。文献[11]提出了基于多尺度结构自相似性的单幅图像超分辨率算法(Multi-scale Structural Self-similarity， MSS)，充分利用多尺度结构自相似性，然而，文献[11]使用的k-svd字典库运算效率较低，目前，效率更高的自适应字典库更受欢迎。

本文算法的特点在于HR图像块和LR图像块的映射更加直接快速，利用平衡二叉树加快了最近邻搜索速度，且误差更小。此外，本文算法将降噪后的LR图像高频成分保存下来，用于后续的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是系统加性噪声，一般由高斯噪声代替，大小为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图像块之间的距离，相比传统算法[15]，本文算法采用更多的邻域图像块用于SR重建，其误差也非常小，采用不同图像块尺寸时，knn分类器中k值与重建的SR图像峰值信噪比PSNR的关系如图2所示。从图2可以看出，当图像块尺寸为5×5时，PSNR值最高，效果最好，k值为6时趋于稳定，经验表明，随着k值增大，即最近邻图像块数增加时，相比运用更少的最近邻图像，误差更小。权重的获取有助于HR图像块的重建，而HR的图像块与高频成分合并直接关系到最终的SR图像的重建。本文的权重关联图像块尺寸和测试训练阶段的LR图像块距离，而这些变量直接与重建的图像块关系紧密。

图2　用PSNR度量的knn分类的经验值k

重建后的图像x与2.2.2部分的高频成分yHF叠加，得到最终的SR图像，即

xSR=x+xHF

(14)

测试阶段的流程图如图3所示。

图3　测试阶段流程图

3实验结果与分析

仿真实验在配置为Win7操作系统、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算法的不稳定性造成的。表3为不添加噪声情况下FSIM的结果，本文算法在Leaves和Baboon图像上的FSIM值略低于其他算法，在大多数情况下均为最高。图4为加上高斯噪声后的重建效果，可以看出，本文算法去噪效果非常明显，归功于测试阶段去噪的作用。

表1　分辨率增强因子为2时各算法的PSNR值

表2　分辨率增强因子为2时各算法的SSIM值

3.1.2缩放因子为4时的重建结果

这部分所有图像都放大4倍，更具挑战性，表4为没有添加噪声情况下重建后的PSNR值、SSIM值和FSIM值，加粗的为最大值。从表4可以看出，在3幅图像Wall、Leaves和Baboon上的实验，本文算法3个度量值均达到最高，其次是IPER算法，ANNF算法表现最差。图5所示为放大4倍的Leaves图像，可以看出，本文算法塔的边缘非常清晰，叶子也比较自然。这些现象体现了本文算法在重建较大缩放因子的SR图像方面的优势，运用knn和平衡二叉树的邻域嵌入具有较小的误差和较好的稳定性。

表3　分辨率增强因子为2时各算法的FSIM值

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

3.2噪声和高斯模糊的影响

由于运动模糊的字典训练学习非常困难，没有讨论如文献[12]的几何运动和运动模糊。这部分讨论高斯噪声方差大小及其模糊核尺寸对超分辨率重建效果的影响。

表4　分辨率增强因子为4时各算法评估

图5　放大4倍的重建效果

图6所示为高斯噪声方差与20幅重建图像平均PSNR之间的关系，可以看出，随着噪声方差的增大，本文算法的PSNR值曲线下降得最慢，其他算法受噪声影响较大。图7是高斯卷积核的大小与PSNR的关系，可以看出，随着卷积核尺寸的增大，本文算法的PSNR值下降最慢，ANNF与本文算法非常接近。图8所示为高斯卷积核大小与SSIM之间的关系。可以看出，与图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问题，带有运动模糊的字典将更具有挑战性。

参考文献：

[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]卢振泰，冯衍秋，冯前进，等. 基于主相位一致性的医学图像配准[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.