对LLE图像超分辨率算法的几个改进

　　摘要:本文旨在对一种经典的图像超分辨率方法——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.