基于双权重约束的判别字典学习算法∗

李争名1，2杨南粤1

（1.广东技术师范学院工业中心广州510665）（2.哈尔滨工业大学深圳研究生院生物计算研究中心深圳518055）

为了提高字典学习算法的分类性能，提出基于编码系数和原子的双权重约束判别字典学习算法（DWCDL）。利用编码系数矩阵的行向量（Profiles）构造原子权重约束项，促使相似的原子重构同类训练样本，并减少原子间的自相关性。利用训练样本的类标设计编码系数的权重，促使同类的训练样本有相似的编码系数。实验结果表明DWCDL算法比七个稀疏编码和字典学习算法取得更高的分类性能。

字典学习；权重约束；图像分类

Class NumberTP391

1 引言

基于稀疏表示的分类算法（Sparse Representa⁃tion based Classification，SRC）［1］和基于协同表示的分类算法（Collaborative Representation based Classi⁃fication，CRC）［2］在人脸识别等领域中取得较好的分类性能。然而，研究结果表明利用从训练样本中学习的字典比直接利用训练样本能够取得更好的性能［3～5］。因此，作为稀疏理论中的一个重要研究分支，判别字典学习受到越来越多研究者的关注。判别字典学习的主要目的是从训练数据中学习字典，使其能够尽可能地保持训练数据的特征，同时又具有一定的判别性。判别字典学习算法的核心问题是如何设计判别式约束项，增强字典的判别性。

由于类标特征在模式分类中起到非常重要的作用，研究者利用训练样本或原子类标设计了许多判别式约束项。Zhang等［6］利用训练样本类标与编码系数构造误差分类项作为判别式约束项，在K奇异值分解（K-means-based Singular Value Decompo⁃sition，K-SVD）［7］字典学习算法的基础上提出判别

综上所述，为了提高字典学习算法的分类性能，提出同时考虑原子和编码系数的权重约束判别字典学习算法。双重构约束判别字典学习算法不仅促使同类的训练样本有相似的编码系数，也鼓励同类的原子尽量重构某一类训练样本，增强字典的判别性能。

2 DWCDL算法

假设Y=[y1,…,yn]∈ℜm×n是训练样本集合，n是训练样本个数，m是训练样本的维数，D=[d1,…,dk]T∈ℜm×k是字典，k是原子个数，di是字典D的第i个原子，X=[x1,…,xn]T∈ℜk×n是编码系数矩阵。

2.1原子的权重约束模型

根据文献［12］，理想情况下字典学习模型如图1所示。

图1 理想情况下的字典学习模型

其中，yi=[y1i,…,ymi]T是第i个训练样本，xi=[x1i,…,xki]T是训练样本yi对应的编码系数，di=[d1i,…,dmi]T是第i个原子。根据profiles的定义，原子di对应的profile为pi=[xi1,…,xin]T，图1中每个长方形框表示一个profile。因此，profiles矩阵可以定义为P=[p1,p2,…,pk]∈ℜn×k，其是编码系数矩阵X的转置矩阵，也即P=XT。从图1中可以看出同一个profile中的元素都对应字典中的一个原子。因此，profiles与字典中的原子是一一对应关系。

由于profile是一个矢量，可以有很多种方法衡量它们的相似性。为了更好地反映profiles间的关系，利用profiles为顶点构造图G。图G的权重利用式（1）计算：

其中，U(i,j)表示profilespi和pj间的相似性。δ是参数，kNN(pi)表示profilepi的K近邻。

根据文献［13］，相似的profiles对应的原子也相似。因此，可以利用profiles衡量原子间的相似性，构造原子的权重约束项如式（2）：

为了更好地表示字典学习中原子间的权重关系，式（2）可以转换为式（3）

其中，Wij表示编码系数xi和xj对应训练样本yi和yj的特征。

为了选择合适的方法构造自适应的权重系数Wij，文献［9］利用训练样本的类标构造自适应引导支持矢量模型如式（6）。

其中，L为拉普拉斯图，构造方法如式（4）：

2.2编码系数的权重约束模型

根据文献［15］，同类的训练样本对应的编码系数也相似。因此，可以利用训练样本的特征设计编码系数的权重，其公式如下

其中，U=[u1,u2,…,uC]是SVM分类器的基准超平面b=[b1,b2,…,bC]是对应的误差。C是训练样本的类数。h=[h1,h2,…,hn]是训练样本的类标集合，hj=[,,…,]是第i个训练样本的类标，如果hi=j，则=1，否则=-1。

2.3DWCDL算法的目标函数

根据上述分析，为了提高字典学习算法的分类性能，构造双权重约束的判别字典学习算法的目标函数如式（7）：

其中，第一项表示字典的重构性能，第二项表示原子的权重约束项，第三项表示编码系数的权重约束项，第四项是编码系数的正则项。α，β和γ是参数。

根据文献［12～13］，如果两个profiles相似，它们对应的原子被训练样本集合使用的情况也是一样的。因此，它们对应的原子也是相似的。此外，minTr(DLDT)=minTr(DTDL)，表明原子的权重约束项还能减少原子间的自相关性，进一步增强字典的判别性能。根据文献［9］，利用训练样本的类标构造自适应的编码系数权重约束项，能够促使同类的训练样本对应的编码系数相似，增强字典学习算法的分类性能。同时，为了减少算法的计算复杂度，利用l2范数约束编码系数。

3 DWCDL算法的求解及分类方法

根据文献［9］，DWCDL算法不是一个全局凸优化问题，但是对于各个变量则是凸优化问题。因此，可以采取交替约束的方法对DWCDL算法求解。DWCDL算法利用主成元素分析（Principal Component Analysis，PCA）方法为每类样本初始化一个特定类字典，并形成初始化的字典D。编码系数矩阵X和U初始化为零矩阵，b初始化为零矢量。

3.1基准超平面U和对应的误差b的求解

假设字典D，编码系数矩阵X和拉普拉斯图L是常量，则式（7）可转换为一个多类线性支持向量机（Support Vector Machine，SVM）问题。根据文献［9］，利用式（8）所示的二次铰链损失函数更新基准超平面U和对应的误差b。

3.2编码系数矩阵X和拉普拉斯图L的求解

假设字典D，基准超平面U和对应的偏差b及拉普拉斯图L是常量，编码系数矩阵X的求解可以转换为对每个编码系数逐一求解。根据文献［9］，第i个编码系数xi的求解如式（9）：

如果获得了编码系数矩阵X，则可以利用式（4）更新拉普拉斯图L。

3.3字典D的求解

假设编码系数X，基准超平面U和对应的偏差b及拉普拉斯图L是常量，字典D的求解可以转换为式（10）：

根据文献［15］，其可以利用拉格朗日函数进行求解，于是式（10）转换为式（11）：

其中λ=[λ1,…,λi,…,λk]（i∈[1,…,k]），λi是第i个等式约束（‖di‖2=1）的拉格朗日乘子。定义对角矩阵Λ∈ℜk×k，其对角元素Λii=λi。式（11）可以转换为式（12）：

为了获得最优的字典D，对式（12）求一阶导数并令其等于零，可得式（13）：

Λ的最优求解过程见文献［15］。为了减少计算复杂度，利用ηI代替Λ获得最优的字典D*为式（14）：

其中，η是参数，I是单位矩阵。

3.4分类方法

根据文献［9］，一旦获得字典D和基准超平面U和对应的误差b，利用SVM方法对测试样本进行分类的方法。DWCDL算法的分类过程如下：

1）对于测试样本y，利用式（15）获得其编码系数x：

4 实验及结果分析

为了验证DWCDL算法的性能，本节给其与SRC［1］，CRC［2］，K-SVD［7］，D-KSVD［6］，LC-KSVD［8］，FDDL［10］和SVGDL［9］算法在AR（Aleix Martinez and Robert Benavente）［16］和LFW（Labeled Faces in the Wild）［17］人脸数据库以及Caltech 101［18］数据库中的实验结果。SRC算法利用l1_ls方法获得测试样本的表示系数。CRC，K-SVD，D-KSVD，LC-KSVD，FDDL和SVGDL算法的代码均由作者提供。由于LC-KSVD2比LC-KSVD1取得更好的分类性能，LC-KSVD算法的实验结果指的是LC-KSVD2算法。在所有实验中，DWCDL算法的参数α=1和η=1。参数β=0.05，θ=5和γ=0.002与SVGDL算法中的一样。另外，构造拉普拉斯图L的参数δ=4和K=1。

4.1AR数据库中的实验结果

AR数据库中具有不同的表情、亮度和遮挡的采集于两个阶段的超过4，000幅彩色人脸图像。根据文献［19］，选择120个人作为子集合，图像被调整为40×50像素大小的灰度图像，图2显示AR数据库中的部分图像。

图2 AR数据库中的部分图像

在本实验中，每类第一阶段的13幅图像作为训练样本，第二阶段的13幅图片作为测试样本。字典大小为1560，实验结果如表1所示。

4.2LFW人脸数据库中的实验结果

LFW数据库中的图像来自于互联网，共计有1，680个人的13，000多幅人脸图像。根据文献［20］，本实验用LFW数据的裁剪版本（LFW crop）为实验所用数据。根据文献［21］，从LFW crop数据库中选择每类图像个数为11～20的人脸图像作为数据集合，则一共有86人共计1，215幅图像，并把图像调整为32×32像素大小。图3显示LFW crop数据库中的部分图像。

表1 AR数据库中的识别率以及训练字典和分类样本的平均时间

图3 LFW crop数据库中的部分图像

在实验中，每个人随机选择5幅图像作为训练样本集合，剩下的作为测试样本。字典的大小为430。重复运行WDCDL算法和7个对比算法10次，实验结果如表2所示。

表2 LFW数据库中的识别率以及训练字典和分类样本的平均时间

4.3Caltech 101数据库中的实验结果

Caltech 101数据集合包括有动物、花和汽车等物体，共计102类图像，每类图像的数目为40～800不等。图4显示Caltech 101数据集合中的部分图像。

图4 Caltech 101数据库中的部分图像

根据文献［8］，利用从Caltech 101数据集合中提取的金字塔特征，并利用PCA方法降维到3000作为实验数据。在本实验中，每类随机选择5个作为训练样本，剩余的作为测试样本。字典大小设为510。重复运行DWCDL算法和七个对比算法10次，实验结果如表3所示。

表3 Caltech101数据库中的识别率

4.4实验结果分析

1）从表1～3中可以看出DWCDL算法比SVG⁃DL算法取得更高的识别率。SVGDL算法利用训练样本的类标设计自适应的编码系数权重，促使同类训练样本对应的编码系数尽可能地相似。但是忽略了原子的特征，特别是理想情况下某些原子应该仅仅重构同类训练样本。DWCDL算法利用Pro⁃files构造自适应原子权重约束，不仅能够促使相似的原子尽可能地重构同类训练样本，而且能够减少原子间的自相关性，增强了字典的判别性能。因此，DWCDL算法比SVGDL算法取得更好的分类性能。

2）表1～3表明DWCDL算法比FDDL算法取得更高的识别率。虽然两种算法都同时考虑了编码系数和原子的特征。不同点主要是FDDL算法考虑了不同类原子的重构性能，而DWCDL算法不仅考虑了原子间的相似性，促使同类原子尽可能重构某一类训练样本，而且还能够减少原子间的自相关性特征。因此，DWCDL算法比FDDL算法取得更好的识别率。

3）从表1～3中可以看出，DWCDL算法比K-SVD，D-KSVD和LC-KSVD算法取得更高的识别率。K-SVD，D-KSVD和LC-KSVD算法在字典学习中都忽略了自相关性及权重等原子特征，降低了字典的判别性能。而DWCDL算法通过构造双权重约束判别式项能够克服上述算法存在的问题，提高了字典学习算法的分类性能。

4）当原子个数等于训练样本个数时，表1～3表明DWCDL算法取得比CRC和SRC算法更高的识别率。主要原因是利用学习得到的字典比直接利用原始的训练样本具有更好的分类性能。

5）表1和2表明，DWCDL算法的训练字典和测试样本的时间与SVGDL算法基本上相等。主要是它们都采取相同的分类方法。DWCDL算法在训练阶段增加了原子权重约束项，由于原子权重约束项可以直接求导，因此DWCDL算法的训练时间和SVGDL算法基本相等。此外，DWCDL训练字典的时间比K-SVD，D-KSVD，LC-KSVD算法都大，比FDDL算法小。主要原因是DWCDL算法采取逐个对编码系数进行求解，导致时间增加。由于采取SVM方法对测试样本进行分类，DWCDL算法的分类时间比SRC，CRC，K-SVD，D-KSVD，LC-KSVD和FDDL算法都小。

5 结语

本文提出一种新的原子权重约束模型，不仅能够使得相似的原子尽可能重构同类样本，还能减少原子间的自相关性。并在SVGDL算法的基础上，提出双重构约束的判别字典学习算法，增强字典学习算法的分类性能。实验结果表明DWCDL算法比直接利用原始训练样本的SRC和CRC算法以及LC-KSVD，FDDL和SVGDL等字典学习均取得更高的分类性能。

［1］Wright J，Yang A Y，Ganesh A，et al.Robust face recogni⁃tion via sparse representation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31（2）：210-227.

［2］Zhang L，Yang M，Feng X.Sparse representation or collab⁃orative representation：which helps face recognition［C］// IEEEInternationalConferenceonComputerVision（CVPR），2011：471-478.

［3］谢勤岚，丁晶晶.基于改进的字典学习算法的图像去噪方［J］.计算机与数字工程，2014，42（6）：1071-1074.

XIE Qinlan，DING Jingjing.Image denoising method based on modified dictionary learning algorithm［J］.Com⁃puter&Digital Engineering，2014，42（6）：1071-1074.

［4］Xu Y，Li Z，Zhang B，et al.Sample diversity，representa⁃tion effectiveness and robust dictionary learning for face recognition［J］.Information Sciences，2017，375：171-182.

［5］Huang K，Dai D，Ren C，et al.Learning kernel extended dictionary for face recognition［J］.IEEE Transactions on Neural Networks and Learning Systems，2016，DOI：10.1109/TNNLS.2016.2522431.

［6］Zhang Q，Li B.Discriminative K-SVD for dictionary learn⁃ing in face recognition［C］//IEEE Conference on Comput⁃er Vision and Pattern Recognition（CVPR），2010，pp.2691-2698.

［7］Aharon M，Bruckstein M E.K-SVD：an algorithm for de⁃signing of over-complete dictionaries for sparse represen⁃tation［J］.IEEE Transactions on Signal Processing，2006，54（11）：4311-4322.

［8］Jiang Z，Lin Z，Davis Larry S.Label consistent K-SVD：learning a discriminative dictionary for recognition［J］. IEEE Transactions on Pattern Analysis and Machine Intel⁃ligence，2013，35（11）：2651-2664.

［9］Cai S，Zuo W，Zhang L，et al.Support vector guided dic⁃tionary learning［C］//European Conference on Computer Vision（ECCV），2014：624-639.

［10］Yang M，Zhang L，Feng X，et al.Sparse representation based fisher discrimination dictionary learning for image classification［J］.International Journal of Computer Vi⁃sion，2014，109（3）：209-232.

［11］Sadeghi M，Babaie-Zadeh M，Jutten C.Learning over⁃complete dictionaries based on atom-by-atom updating［J］.IEEE Transactions on Signal Processing，2014，62（4）：883-891.

［12］Lu C，Shi J，Jia J.Scale adaptive dictionary learning［J］. IEEE Transactions on Image Processing，2014，23（2）：837-847.

［13］Li Z，Lai Z，Xu Y，et al.A locality-constrained and label embedding dictionary learning algorithm for image classi⁃fication［J］.IEEE Transactions on Neural Networks and LearningSystems，2015，DOI：10.1109/ TNNLS.2015.2508025.

［14］Zhang Y，Jiang Z，Davis Larry S.Learning structured low-rank representations for image classification［C］// IEEE Conference on Computer Vision and Pattern Recog⁃ nition（CVPR），2013：676-683.

［15］Zheng M，Bu J，Chen C，et al.Graph regularized sparse coding for image representation［J］.IEEE Transactions on Image Processing，2011，20（5）：1327-1336.

［16］Martineza M，Benavente R.The AR face database［J］. CVC Technical Report，1998，24.

［17］Huang G B，Ramesh M，Berg T，et al.Labeled faces in the wild：a database for studying face recognition in un⁃constrained environments［J］.University of Massachu⁃setts，Amherst，Technical Report 07-49，Oct.2007.

［18］Li F，Fergus R，Perona P.Learning generative visual models from few training samples：an incremental Bayes⁃ian approach tested on 101 object categories［C］//Confer⁃ence on Computer Vision and Pattern Recognition Work⁃shop（CVPRW），2004，pp.178-178.

［19］Yang J，Zhang D，Yang J，et al.Globally maximizing，lo⁃cally minimizing：unsupervised discriminant projection with applications to face and palm biometrics［J］.IEEE Transactions on Pattern Analysis and Machine Intelli⁃gence，2007，29（4）：650-664.

［20］Sanderson C，Loverll Brain C.Multi-region probabilistic histograms for robust and scalable identity inference［C］// International Conference on Biometrics（ICB），2009：199-208.

［21］Wang S，Yang J，Sun M，et al.Sparse tensor discriminant color space for face verification［J］.IEEE Transactions on Neural Networks and Learning Systems，2012，23（6）：876-887.

Discriminative Dictionary Learning Based on the Double Weighted Constraints

LI Zhengming1，2YANG Nanyue1
（1.Industrial Training Center，Guangdong Polytechnic Normal University，Guangzhou510665）（2.Bio-Computing Research Center，Shenzhen Graduate School，Harbin Institute of Technology，Shenzhen518005）

In order to improve the classification performance of dictionary learning algorithms，a double weighted constraints discriminative dictionary learning algorithm（DWCDL）is proposed.The weighted constraint of atoms is constructed by using the pro⁃files，and it not only encourages the similar atoms to reconstruct training samples of the same class，but reduces the coherence of at⁃oms.The weighted constraint of coding coefficients is constructed by using the label information of training samples，and it can en⁃courage the training sample of the same class to have similar coding coefficients.Experimental results show that the proposed algo⁃rithm can achieve better classification performance than seven sparse coding and dictionary learning algorithms.

dictionary learning，weighted constraint，image classification

TP391

10.3969/j.issn.1672-9722.2017.05.004

2016年11月17日，

2016年12月23日

国家自然科学基金项目（编号：61370613，61573248）；广东省普通高校青年创新人才项目（编号：2015KQNCX089）资助。

李争名，男，博士研究生，高级实验师，研究方向：字典学习。杨南粤，女，硕士，讲师，研究方向：图像处理，虚拟现实。K-SVD字典学习算法（Discriminative K-SVD，D-KSVD）。为了进一步增强字典的判别性能，Ji⁃ang等［8］在D-KSVD算法的基础上，利用原子的类标构建判别稀疏编码错误项作为判别式约束项，提出类标一致的判别字典学习算法（Label Consistent K-SVD，LC-KSVD）。Cai等［9］利用训练样本的类标特征设计编码系数的权重，并在此基础上构造支持矢量引导字典学习（Support Vector Guided Diction⁃ary Learning，SVGDL）算法。Yang等［10］提出Fisher判别字典学习算法（Fisher Discrimination Diction⁃ary Learning，FDDL），同时利用编码系数特征和原子的重构性能设计判别式约束项。然而上述算法均忽略了原子间的特征，降低了字典的判别性能。最近，Sadeghi等［11］把编码系数矩阵中每个行向量定义为一个profile，并利用其设计原子更新算法。Lu等［12］利用profile衡量原子重构训练数据的贡献，并提出自适应原子个数选择算法。在此基础上，Li等［13］提出利用原子衡量对应profiles的局部特征约束模型，增强了字典的判别性能。根据文献［8，14］，理想情况下，同类训练样本应该由某些原子单独重构，而且这些原子应该属于同一类。然而，上述算法均忽略了原子的权重约束。