基于弹性网和直方图相交的非负局部稀疏编码

万源 张景会 陈治平 孟晓静

摘 要：针对稀疏编码模型在字典基的选择时忽略了群效应，且欧氏距离不能有效度量特征与字典基之间距离的问题，提出基于弹性网和直方图相交的非负局部稀疏编码方法（EH-NLSC）。首先，在优化函数中引入弹性网模型，消除字典基选择数目的限制，能够选择多组相关特征而排除冗余特征，提高了编码的判别性和有效性。然后，在局部性约束中引入直方图相交，重新定义特征与字典基之间的距离，确保相似的特征可以共享其局部的基。最后采用多类线性支持向量机进行分类。在4个公共数据集上的实验结果表明，与局部线性约束的编码算法（LLC）和基于非负弹性网的稀疏编码算法（NENSC）相比，EH-NLSC的分类准确率分别平均提升了10个百分点和9个百分点，充分体现了其在图像表示和分类中的有效性。

关键词：稀疏编码;弹性网模型;局部性;直方图相交;图像分类

中图分类号： TP391.4

文献标志码：A

文章编号：1001-9081（2019）03-0706-06

Abstract： To solve the problems that group effect is neglected when selecting dictionary bases in sparse coding models， and distance between a features and a dictionary base can not be effectively measured by Euclidean distance， Non-negative Local Sparse Coding algorithm based on Elastic net and Histogram intersection （EH-NLSC） was proposed. Firstly， with elastic-net model introduced in the optimization function to remove the restriction on selected number of dictionary bases， multiple groups of correlation features were selected and redundant features were eliminated， improving the discriminability and effectiveness of the coding. Then， histogram intersection was introduced in the locality constraint of the coding， and the distance between the feature and the dictionary base was redefined to ensure that similar features share their local bases. Finally， multi-class linear Support Vector Machine （SVM） was adopted to realize image classification. The experimental results on four public datasets show that compared with LLC （Locality-constrained Linear Coding for image classification） and NENSC （Non-negative Elastic Net Sparse Coding）， the classification accuracy of EH-NLSC is increased by 10 percentage points and 9 percentage points respectively on average， proving its effectiveness in image representation and classification.

Key words： sparse coding; elastic net model; locality; histogram intersection; image classification

0 引言

图像分类是计算机视觉领域的一个重要研究方向，广泛应用于生物特征识别、网络图像检索和机器人视觉等领域，其关键在于如何提取特征对图像有效表示。稀疏编码是图像特征表示的有效方法。考虑到词袋（Bag of Words， BoW）模型[1]和空间金字塔匹配（Spatial Pyramid Matching， SPM）模型[2]容易造成量化误差，Yang等[3]結合SPM模型提出利用稀疏编码的空间金字塔的图像分类算法（Spatial Pyramid Matching using Sparse Coding， ScSPM），在图像的不同尺度上进行稀疏编码，取得了较好的分类效果。在稀疏编码模型中，由于1范数在字典基选择时只考虑稀疏性而忽略了群体效应，Zou等[4]提出一种新的正则化方法，将弹性网作为正则项和变量选择方法。Zhang等[5]提出判别式弹性网正则化线性回归（Elastic-Net regularized Linear Regression， ENLR ），引入鲁棒弹性网络正则化方法，以提高学习投影矩阵的紧凑性和有效性。张勇等[6]在目标函数中引入2范数正则项，提出基于非负弹性网的稀疏编码算法（Non-negative Elastic Net Sparse Coding， NENSC），提高了编码的判别性和有效性。Shen等[7]建议在字典原子选择时使用弹性网作为正则项，提出弹性网正则项的字典学习算法（Elastic Net regularized Dictionary Learning， ENDL），这不仅得益于类似1范数的稀疏性，而且还鼓励分组效应，有助于改善图像表示的分类效果。Yu等[8]发现相比于稀疏性，局部性更重要，并且局部性必然推导出稀疏性，但反之未必。Wang等[9]将局部性约束引入到稀疏编码中来代替稀疏性约束，提出局部线性约束的编码算法（Locality-constrained Linear Coding for image classification， LLC），极大地提高了图像的分类性能。但是该方法对近邻数k很敏感，导致编码过程极不稳定，因此刘培娜等[10]在优化问题中引入非负性约束，提出非负LLC算法。在表示特征与码本之间的距离时，欧氏距离应用最多，然而尺度不变特征变换（Scale-Invariant Feature Transform， SIFT）特征是局部图像块梯度方向直方图的统计量，Wu等[11]已经证明直方图相交在具有直方图特征的学习任务中比欧氏距离更有效，提出一种超越欧氏距离的度量方法——直方图相交相似性度量方法来创建有效的可视化码本。为了解决这个问题，Chen等[12]提出了一种改进的LLC算法用于场景图像分类，称为基于直方图相交的局部约束线性编码（Locality-constrained Linear Coding based on Histogram Intersection， HILLC）。

针对文献[9-12]在字典基的选择时只考虑了稀疏性而忽略了群体效应，及文献[9-10]在局部性约束中利用欧氏距離不能有效地度量特征与字典基的距离的问题，本文提出基于弹性网和直方图相交的非负局部稀疏编码（Non-negative Local Sparse Coding based on Elastic net and Histogram intersection， EH-NLSC）模型。在编码模型中引入了弹性网作为正则项，可以得到类似于1范数约束的稀疏性，而且鼓励分组效应，提高编码的判别性和有效性;并在优化函数中引入局部性约束和非负性约束，有效利用特征之间的局部信息，改善编码的不稳定性并保持相似编码的一致性，并且通过引入直方图相交，重新定义特征向量与字典元素之间的距离。实验表明，相比于其他现有算法，EH-NLSC的分类性能更高。

1 相关工作

1.1 稀疏编码

由于向量量化方法很容易导致量化误差，并且K-means方法可能会使语义信息丢失，因此Yang等结合SPM提出了基于SPM的稀疏编码方法（ScSPM）。其核心问题是学习M空间中的超完备（即M≥D，基向量的个数远大于维数）字典U，并选取其中尽可能少的基向量来表示原始的特征向量。稀疏编码具体的优化模型如下：

1.2 局部约束线性编码

Yu等指出局部性比稀疏性更重要，因为局部性可以推出稀疏性，但稀疏性不能推出局部性。Wang等指出局部非零系数通常被分配给编码特征附近的基。因此，LLC方法用字典中的许多基来表示特征描述子，相似的特征通过共享它们的局部的基来获得相似的编码，从而提高了稀疏编码的不稳定性。局部约束线性编码具体的优化问题如下：

1.3 弹性网模型

2 本文方法

以上这些方法都能在一定程度上减小重构误差，但仍然存在以下几个不足： 1）编码模型中的1范数只考虑了稀疏性，忽略了群体效应，图像特征不能找到与同一类图像对应的字典基;2）特征之间缺乏局部性和非负性约束，相似的特征可能会被编码成不同的码字;3）利用欧氏距离来计算特征描述子和字典之间的距离不够有效。基于以上3个问题，本文提出基于弹性网和直方图相交的非负局部稀疏编码模型。首先，针对第1个问题，将弹性网模型应用到稀疏编码中，即在编码模型中添加2范数，将有效且相关的特征一起选出来，充分考虑了字典基选择时的群体效应，有助于消除字典中所选原子数的限制，保留判别性特征并消除冗余特征（如图1：与SC相比，EH-NLSC选择多个相关的基，虚线箭头为去除的冗余特征），有效提高了编码的有效性;然后，引入局部性和非负性，确保相似特征共享局部的基（如图1：xi，xj共享局部的基），改善编码的不稳定性;最后，通过引入直方图相交，重新定义特征向量与字典基之间的距离，使得图像表示更准确有效。再利用空间金字塔匹配SPM将图像划分为L0、L1和L2三层，并对每层的空间金字塔区域进行最大值融合（Max Pooling， MP），将三层分别得到的编码连接起来，得到图像的最终特征表示。最后利用支持向量机（Support Vector Machine， SVM）进行训练和分类。

图1为本文提出的EH-NLSC模型的框架，其中，在学习字典和编码阶段，图中给出了传统的稀疏编码（Sparse Coding， SC）方法与本文的EH-NLSC的对比，虚线框为传统的稀疏编码方法，实线框为本文学习字典和稀疏编码的核心内容。

2.1 EH-NLSC模型

本文结合弹性网模型，将2范数引入到稀疏编码的目标函数中，并在优化问题中的添加局部性约束，将非负性添加到优化问题的约束条件中，最终形成EH-NLSC，即为图1中实线框内的核心内容。具体的优化问题如下所示：

2.2 EH-NLSC算法的求解

对于式（4），由于同时优化目标函数中的U和V，该问题是非凸的，这样很难找到一个全局最小值，但当分别优化U或V是凸的，交替优化U和V就会存在全局最优解。

首先，固定X和V，优化非负字典U，优化问题转化为：

3 实验结果及分析

本章设计了两组仿真实验来验证EH-NLSC算法的性能和效果，其中3.1节给出实验所用数据集和实验设置，实验设置包括本文所对比的方法以及参数设置;3.2节介绍本文的两组实验设计内容及结果分析。

3.1 实验数据集和实验设置

本文选择4个数据集对EH-NLSC方法进行验证，分别为Corel-10、Scene-15、Caltech-101、Caltech-256，表1给出了所选数据集的信息。

为了验证本文方法的有效性，将本文方法与以下几种方法进行对比分析：

1） ScSPM。利用稀疏编码的空间金字塔匹配的图像分类算法[3]，在图像的不同尺度上进行稀疏编码，并结合空间金字塔匹配方法进行图像表示。

2） LLC。利用局部约束将每个特征描述符投影到其局部坐标系中，并通过最大池融合投影坐标以生成最终表示[9]。

3） ENDL。使用弹性网作为正则项来选择特征编码中的原子，这不仅可以得到类似于1范数的稀疏性，而且还鼓励群体效应，有助于改善图像表示[7]。

4） NENSC。利用非负稀疏编码算法和弹性网模型，在稀疏编码优化模型中引入2范数作为正则项，增加编码系数的非负性约束[6]。

5） LScSPM。LScSPM（ScSPM based on Laplacian）[14]利用局部特征之间的依赖关系，使用Laplacian矩阵较好地刻画局部特征的相似性;此外，将拉普拉斯矩阵合并到稀疏编码的目标函数中，以保持编码的一致性。

6） Lap-NMF-SPM。Lap-NMF-SPM（NMF and graph Laplacian based on Spatial Pyramid Matching）[15]使用非负矩阵分解来约束码本和相应的编码系数的非负性，利用图拉普拉斯正则化方法保持局部和相似特征之间的依赖性。

7） HILLC。使用直方图相交来描述特征向量与码本之间的距离。对于每个特征向量，搜索K最近邻（K-Nearest Neighbor， KNN）來构造一个局部码本[12]。

在特征提取阶段，利用16×16的滑动窗口，步长为8进行SIFT特征提取，每个局部特征描述子均为128维，即D=128;在字典训练阶段，固定字典的大小为M=1024，然后对于4个数据集，选取不同的训练样本和测试样本。对于Corel-10和Scene-15两个数据集，从每类中分别随机选择50和100幅图像作为训练样本，剩余的作为测试样本。而对于Caltech-10和Caltech-256数据集，从每类分别随机选择15、30和15、30、45、60幅图像作为训练样本，剩余的作为测试样本。关于优化问题中涉及的参数λ、 β以及σ，分别设置 λ∈[0.1，0.4]， β∈[0.1，0.4]，σ=100。

3.2 实验设计及结果分析

3.2.1 实验1：三种方法所得字典比较

首先，对SC、LSC以及本文方法EH-NLSC训练所得到的字典图予以显示，如图2所示。为了提高字典的表示能力，必须保证字典原子能够合理地遍布于潜在的子空间，并且原始的训练样本具有大量的冗余信息和噪声干扰，因此需要采用精简且具有区分度的字典来提高识别精度。由灰度图可以看出，本文方法EH-NLSC学习到的字典具有更多的可判别属性，其中灰色像素反映图像中原始特征的更多特性，比如EH-NLSC方法学习到的字典具有更好的局部性、非负性、带通性和方向性（图2（a）、（b）来自文献[16]）。

为了更好地说明本文算法的有效性，选取Yale数据集[17]对图像进行重建，随机选取部分图像。在训练阶段，利用EH-NLSC算法交替优化目标函数，得到完备字典U和稀疏编码矩阵V;在测试阶段，对于新的单幅输入图像，利用训练得到的字典U及式（12）计算其稀疏系数vi;在重建阶段，利用完备字典U和稀疏系数vi对图像进行重建。如图3所示，从图像的视觉效果来看，重建的图像比较清晰，但得到的结果局部细节边缘模糊，这是由于在EH-NLSC优化函数中添加了局部性约束，使得图像的重建系数是稀疏的，同时在图像重建时也造成图像信息的损失，因此重建图像的部分局部细节模糊。

3.2.2 实验2：不同方法平均分类准确率比较

表2，3分别为EH-NLSC算法与ScSPM、LLC、ENDL、HILLSC和NENSC五种方法在Scene-15，Caltech-101两个数据集上的分类效果;表4，5分别为EH-NLSC算法与ScSPM、LLC、LScSPM和Lap-NMF-SPM四种方法在Corel-10和Caltech-256数据集上的分类效果。

从表2的结果可以看出，本文的EH-NLSC算法取得了更好的效果。与LLC方法相比，EH-NLS的分类准确率提高了10个百分点，与HILLSC方法相比，分类准确率提高了5.5个百分点，原因是对Scene-15场景分类，每个局部图像块包含丰富的纹理和轮廓，虽然这三种方法都可以对特征进行局部约束，但是在本文方法中，通过使用弹性网模型作为正则项，在稀疏编码的优化函数中引入2范数，鼓励字典基选择时的群体效应，将高度相关且判别性很高的特征一起选出来，也将冗余特征去除掉，有效控制了特征描述子的敏感性。另外，EH-NLSC与HILLSC均优于LLC，由于在局部性约束中通过引入直方图相交来代替原来的特征向量与码本之间的欧氏距离，与SIFT特征是基于直方图的统计量保持一致，因此取得较好的分类效果。

表3显示了本文方法EH-NLSC和几种方法在Caltech-101数据集上的性能比较。

同样地，EH-NLSC方法的分类准确率比其他几种方法效果都要好，首先相比于ScSPM、ENDL和NENSC，本文方法在优化问题中引入局部性约束，确保相似的特征共享其局部的基，使得编码过程更加稳定。另外，添加对字典和编码的非负性约束，使优化问题只涉及加法运算，从而保留更多的有效特征。相比于LLC方法，EH-NLSC在计算特征描述子与码本之间的距离时，利用的是直方图相交相似性度量，因此可以更好地保留局部信息;同时在稀疏编码模型中引入了弹性网正则项，鼓励分组效应，选择具有判别信息的特征，更加有利于特征表示。

为了充分证明EH-NLSC方法在图像分类中的有效性，本文在Corel-10和Caltech-256数据集上设计了另外一组实验，对比方法为ScSPM、LLC、LScSPM和Lap-NMF-SPM。对比结果如表4和表5，从实验结果可以看出，EH-NLSC方法在两个数据集上的分类准确率均优于其他方法，尤其优于ScSPM。ScSPM、LScSPM和Lap-NMF-SPM这三种方法，由于局部信息的缺失，导致图像的特性不能被准确且有效地表示出来。由于EH-NLSC在优化函数中引入了局部性约束，确保相似的特征具有相似的编码，保留更多局部信息。与LLC方法相比，EH-NLSC算法的分类准确率提升了6个百分点，这是因为LLC虽然考虑到了局部性约束，但是在衡量特征向量和码本之间的相似性时用的是欧氏距离，而SIFT特征本是直方图统计的结果，因此利用直方图相交代替欧氏距离更为准确。另外，EH-NLSC将弹性网模型用作正则项，使得具有判别信息的特征均被选出，并且将多余无关的特征去除，有效提高了图像表示的准确性。

3.2.3 实验3：参数灵敏度分析

本实验研究了不同的参数设置在4个标准数据集上对分类效果的影响，将λ和β分别设为0.1，0.15，0.2，0.25，0.3，0.35，0.4，其分类结果变化如图4所示。从图4中可以看出：在Scene-15和Corel-10两个数据集上，当λ=0.3，β=0.2时，分类效果达到最优;而在Caltech-101和Caltech-256数据集上，λ=0.3， β=0.1时效果最佳。

4 结语

本文提出一种新的稀疏编码框架，称为基于弹性网和直方图相交的非负局部稀疏编码，并将其与空间金字塔和最大池融合相結合来获得用于图像分类的编码模型。通过将弹性网引入到稀疏编码模型中，本文的EH-NLSC在保持稀疏性的基础上，鼓励分组效应，可以有效地选择判别性特征，并将冗余特征去除，因此EH-NLSC比普通稀疏编码方法具有更好的鉴别能力。另外，在图像分类中，局部性约束已经被证明是非常重要的，本文利用局部性约束编码，使得相似的特征共享局部的基，并保持相似特征具有相似编码。并通过引入直方图相交重新定义特征向量与字典元素之间的距离，与通过直方图统计的特征保持一致。已经评估了所提方法在几个公共数据集上的分类效果，实验证明了EH-NLSC算法的有效性。

参考文献 （References）

[1] SIVIC J， ZISSERMAN A. Video Google： a text retrieval approach to object matching in videos [C] // ICCV '03： Proceedings of the 9th International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2003， 2： 1470-1477.

[2] LAZEBNIK S， SCHMID C， PONCE J. Beyond bags of features： spatial pyramid matching for recognizing natural scene categories [C]// CVPR '06： Proceedings of the 2006 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE， 2006： 2169-2178.

[3] YANG J C， YU K， GONG Y H， et al. Linear spatial pyramid matching using sparse coding for image classification [C]// CVPR '09： Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE， 2009： 1794-1801.

[4] ZOU H， HASTIE T. Regularization and variable selection via the elastic net [J]. Journal of the Royal Statistical Society， 2005， 67（2）： 301-320.

[5] ZHANG Z， LAI Z H， XU Y， et al. Discriminative elastic-net regularized linear regression [J]. IEEE Transactions on Image Processing， 2017， 26（3）： 1466-1481.

[6] 张勇，张阳阳，程洪，等.基于非负弹性网稀疏编码算法的图像分类方法[J].计算机工程，2017，43（7）：239-243.（ZHNAG Y， ZHANG Y Y， CHENG H， et al. Image classification method based on non-negative elastic net sparse coding algorithm[J]. Computer Engineering， 2017， 43（7）： 239-243.）

[7] SHEN B， LIU B D， WANG Q F. Elastic net regularized dictionary learning for image classification [J]. Multimedia Tools and Applications， 2016， 75（15）： 8861-8874.

[8] YU K， ZHANG T， GONG Y. Nonlinear learning using local coordinate coding [C]// Proceedings of the 2009 Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009， 31： 927-936

YU K， ZHANG T， GONG Y. Nonlinear learning using local coordinate coding [EB/OL]. [2018-06-12]. http：//www.doc88.com/p-6971813767934.html.

[9] WANG J， YANG J， YU K， et al. Locality-constrained linear coding for image classification [C]// CVPR '10： Proceedings of the 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE， 2010： 3360-3367.

[10] 刘培娜，刘国军，郭茂组，等.非负局部约束线性编码图像分类算法[J].自动化学报，2015，41（7）：1235-1243.（LIU P N， LIU G J， GUO M Z， et al. Image classification based on non-negative locality constrained linear coding[J]. Acta Automatica Sinica， 2015， 41（7）： 1235-1243.）

[11] WU J， REHG J M. Beyond the Euclidean distance： creating effective visual codebooks using the Histogram intersection kernel [C]// ICCV '09： Proceedings of the 2009 IEEE 12th International Conference on Computer Vision. Piscataway， NJ： IEEE， 2009： 630-637.

[12] CHEN H， XIE K， WANG H， et al. Scene image classification using locality-constrained linear coding based on histogram intersection [J]. Multimedia Tools and Applications， 2018，77（3）：4081-4092.

[13] LEE H， BATTLE A， RAINA R， et al. Efficient sparse coding algorithms [C]// NIPS '06： Proceedings of the 19th International Conference on Neural Information Processing Systems. Cambridge， MA： MIT Press， 2006： 801-808.

[14] GAO S， TSANG I W-H， CHIA L-T， et al. Local features are not lonely-Laplacian sparse coding for image classification [C]// CVPR '10： Proceedings of the 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2010： 3555-3561.

[15] HAN H， LIU S， GAN L. Non-negativity and dependence constrained sparse coding for image classification [J]. Journal of Visual Communication and Image Representation. 2015， 26（C）： 247-254.

[16] 史瑩.基于Laplacian稀疏编码的图像分类研究[D].武汉：武汉理工大学，2016：30-31.（SHI Y. Image classification based on Laplacian sparse coding[D].Wuhan： Wuhan University of Technology， 2016：30-31.）

[17] CAI D. Four face databases in matlab format [DB/OL]. [2018-03-29]. http：//www.cad.zju.edu.cn/home/ dengcai/Data/FaceData.htm.