基于局部约束编码的稀疏保持投影降维识别方法研究

张　静,杨智勇,王国宏,林洪文,刘晓娣

(1.海军航空工程学院电子信息工程系,山东烟台264001;2.海军航空工程学院7系,山东烟台264001;

3.海军航空工程学院信息融合研究所,山东烟台264001)



基于局部约束编码的稀疏保持投影降维识别方法研究

张静1,杨智勇2,王国宏3,林洪文1,刘晓娣1

(1.海军航空工程学院电子信息工程系,山东烟台264001;2.海军航空工程学院7系,山东烟台264001;

3.海军航空工程学院信息融合研究所,山东烟台264001)

摘要：稀疏表示技术的引入可有效解决降维处理对图参数的依赖,但这类降维方法不能同时兼顾稀疏重构和样本数据的邻近性问题.针对该问题,本文提出了一种基于局部约束编码的稀疏保持投影降维识别方法.通过稀疏表示分类模型构建了图边权矩阵,引入局部约束因子设计了降维投影模型,推导降维求解过程,分析了本文方法与SPP(Sparse Preserving Projections)和SLPP(Soft Locality Preserving Projections)方法之间的共性和区别,最后给出了识别算法流程.采用人脸图像数据集和高分辨SAR(Synthetic Aperture Radar)图像数据集对算法的有效性进行仿真验证,由于考虑了数据间的邻近性,本文方法较传统方法可获得更好的识别性能.

关键词:目标识别;维数约简;稀疏表示;局部约束编码

1引言

现代战争,实现目标精确打击的前提是能够完成对目标的精准判断.随着SAR(Synthetic Aperture Radar)图像数据获取技术的飞速发展,高维数据不断涌现[1].高维数据会导致所谓的“维数灾难”[2],严重影响武器的实时性和打击性,因此在目标识别过程中如何克服“维数灾难”已经成为当前目标识别领域的关键问题和难点问题,亟需解决.

降维是克服维数灾难的重要途径.按照不同标准,降维有线性与非线性、监督与无监督、局部与非局部之分[3,4].在常用的降维方法中,如主成分分析(Principal Component Analysis,PCA)[5,6]、线性鉴别分析(Linear Discriminant Analysis,LDA)[7,8]、局部线性嵌入(Locally Linear Embedding,LLE)[9]、邻近保持嵌入(Neighborhood Preserving Embedding,NPE)[10]和局部保持投影(Locality Preserving Projections,LPP)[11]等,PCA和LDA方法属于全局型降维算法,LLE、NPE和LPP属于局部型降维算法.局部型降维算法的最大特点是在降维过程中考虑数据的分布结构,因此这类算法均可统一在图嵌入框架之下.而图嵌入框架依赖图参数的选择.

针对该问题,国内外很多学者提出了创意性的思想.Qiao等人[12]在研究LLE算法的基础上,提出了一种稀疏保持投影算法(Sparse Preserving Projections,SPP).SPP方法将稀疏表示理论引入图的构造,并将其归结为一个改进的l1最小化问题,因此获得的投影方向不仅保持了数据的一些本质特征,而且包含了一定的判别信息.然而,SPP方法本质上属于一种全局策略建图,算法在降维过程中仅考虑了样本的稀疏重构,而没有涉及数据间的邻近性问题.此外,Qiao等人[3]还在研究LPP算法的基础上,提出了一种软局部保持投影算法(Soft Locality Preserving Projections,SLPP).SLPP方法虽然通过交替优化技术,实现了图的构建与降维过程的同步,但算法的局限性是:(1)图权矩阵没有完全实现在线学习,即矩阵对角线上元素需要人为设置,而该参数对识别性能影响较大;(2)算法引入迭代技术,比较耗时,实时性大大降低.

本文借鉴局部约束线性稀疏编码(Locality-constrained Linear Coding,LLC)[13～16]思想,提出了一种基于局部约束编码的稀疏保持投影降维方法(Sparsity Preserving Projections based on Locality-Constrained Coding,LCC-SPP).该方法既借鉴了稀疏表示理论建图的优点——减少降维对图参数的依赖,同时在降维的过程中考虑数据的局部邻近性,因此可获得更强的识别能力或判别能力.论文用人脸图像数据[17]和高分辨SAR图像数据[18]对算法进行仿真验证,仿真结果表明:对于两种图像数据,本文方法较SPP方法和SLPP方法都有着明显的优势.

2基于局部约束编码的稀疏保持投影降维方法

2.1稀疏表示建图

Qiao等人借鉴基于稀疏表示的识别器方法(SRC)提出了稀疏表示构图的思想,利用数据的稀疏性自动获取“邻近”图[3,12].假设X=[x1,x2,…xi,…,xn]∈RM×n为一组训练样本集,其中xi∈RM×1.利用l1最小化问题计算某一样本xi对应的稀疏表示系数αi[19,20].即,

(1)

(2)

而稀疏表示重建矩阵A作为图的“邻接”权矩阵.

2.2模型建立

2.1方法仅考虑用稀疏表示方法构建图边权矩阵,没有考虑数据的内部邻近关系,如果在降维的同时,考虑样本间的“邻近”信息,那降维的特征向量中会体现出更多反映目标类别的信息,这对目标识别是有利的.在这种研究动机的基础上,下面给出基于局部约束编码稀疏保持投影降维方法对应的目标函数为:

(3)

Di=[‖WTxi-WTx1‖2,‖WTxi-WTx2‖2,…,

‖WTxi-WTxn‖2]T

=[‖WTdi1‖2,‖WTdi2‖2,…,‖WTdij‖2,…,

‖WTdin‖2]T

(4)

下面给出求解过程的具体推导.为了推导方便,分别定义

(5)

(6)

则

(7)

定义一个n维向量ui,该向量第i个元素值为1,其余元素均为0,则式(7)可进一步化简为:

(8)

其中,I为n×n的单位矩阵.

(9)

同理,定义一个n维向量ui,该向量第i个元素值为1,其余元素均为0,则式(9)可表示为:

(10)

将式(10)代入式(9)得

(11)

其中,V∈n×n的矩阵,其形式如下

(12)

将式(12)和式(8)代入式(3)得

(13)

同文献[3],为了避免退化解,这里也对式(13)增加约束条件:

trace(WTXXTW)=1

(14)

则式(3)目标函数可以变成如下形式:

(15)

由此令Sβ=(A+AT-ATA-ηV),St=(XXT),则式(15)的最小化问题可以转换为求解的最大化问题,即

(16)

则求取式(16)对应的最优特征矢量就变成求取广义线性方程,其解决思路同其它各种子空间方法:

XSβXTW=λStW

(17)

假设λ1,λ2,…,λd为广义特征方程的前d个非零最大特征值(按从大到小的顺序排列),对应的特征矢量为ω1,ω2,…,ωd,则W=(ω1,ω2,…,ωd)就构成最终的特征向量集.

2.3与SPP与SLPP方法的分析比较

下面根据式(8)、(9)和(13),对比本章所提出方法与传统的SPP、SLLP方法之间的关系.为了对比方便,将SPP方法相关表达式表示如下[12]:

=trace(WTX(I-S-ST+SST)XTW)

(18)

其中,S=[s1,s2,…,sn]∈n×n为利用2.1方法获得的边权矩阵,同2.2中的A.

将SLPP方法相关表达式表示如下[3]:

(19)

可推出

(20)

这里,

(21)

其中,S=(Sij)n×n为图的邻接权矩阵,同本文2.2中的A,Sij≥0表示其所有元素非负,1代表全1列向量,t为不确定性参数,用以控制当前邻接权Sij的不确定性.

对比式(18)与式(8),LCC-SPP方法中的第一部分与SPP方法表达式的形式完全一样,说明本文提出的方法具有与SPP方法相同的稀疏保持投影思想.

对比式(19)、(21)与(9)、(12)可以看出,LCC-SPP的第二部分与t=2时的SLPP在表达式的构建思想上存在一定的相近之处,但两者的区别在于以下方面:

(1)本文方法提前设置了邻接权矩阵;而SLPP中Sij是通过近邻方法得到,并利用迭代法更新.

(2)SLPP边权结构受参数t控制,虽然文献[3]通过对Wine数据的仿真实验指出SLPP对t值的选择不具敏感性,但t参数仍存在一定的人为干预性,这个问题在本文方法中不存在.

(3)SLPP每次迭代时所求得的边权矩阵都是通过归一化逆欧几里德距离获得的,逆欧几里德距离在i=j条件时是不存在的.该问题文献[3]并没有给出具体说明.

(4)SLPP存在多次迭代优化,因此算法的耗时性较本文方法时间长.

(5)SLPP仅考虑样本在低维空间中的邻近问题,未涉及重构问题,而本文方法考虑了这两个方面.

由以上分析可以看出,本文提出的方法实际上是将SPP方法与SLPP方法在思想上进行了部分融合.

3基于局部约束编码的稀疏保持投影识别方法

将本文提出的降维方法应用于目标识别中,其识别流程如图1所示.其中,预处理指的是对原始图像进行归一化处理,以减少奇异点对整体数据的影响.论文采用传统的最近邻1NN分类器和SVM分类器[21]完成分类任务.

本文的算法采用两类数据对算法进行仿真验证.ORL人脸库共包含了40个人,每人10幅图像,所有图像均为灰度图像,图像分辨率为112×92大小.MSTAR高分辨SAR图像数据是美国DARPA/AFRL MATAR项目组利用X波段、HH极化方式、0.3m×0.3m高分辨聚束式SAR采集而得的实测地面静止军用目标数据,数据主要有三类目标:BMP2、T72和BTR70,图像大小均为128×128.

3.1人脸图像仿真分析

从每类人中随机选择m个数目的人脸图像作为训练样本,剩余部分用于测试.实验重复执行10次,以平均识别率作为最终性能的衡量指标.对于SPP,子空间维数设为Dim;对于SLPP,参数设置同文献[3],包括图的近邻数k=2,热核参数经验型设置为l2范数,迭代终止条件ε=10-4;对于LCC-SPP,折衷参数η=106.此外,在进行各种降维算法之前对ORL图像数据进行了PCA特征提取.

3.1.1不同训练样本数、不同特征维数条件下的仿真

选择每类训练样本数m={4,7}情况下,研究不同维数Dim条件时,三种方法获得的平均识别率,如图2所示,分类器选择最近邻1NN分类器.

由仿真结果可以看出:

(1)三种方法中LCC-SPP方法性能最好,说明本文方法较其它方法体现出良好的识别性能.

(2)随着维数增加,LCC-SPP获得的平均识别率呈提高趋势,其原因是可用于目标识别的有用信息增多为目标的正确判别提供依据.

(3)随着每类训练样本数m的增多,人脸图像的识别性能提高.由此可见,三种方法对训练样本的个数存在一定的依赖性.

(4)对比SPP和SLPP方法,前者的识别性能要优于后者.这与仿真时人为设置Sii参数有关.

3.1.2不同算法耗时性的比较实验

对比各种算法的计算时间,综合分析最优识别方法.表1给出m=6,Dim=70,分类器选取1NN时各种算法对应的运行时间.

SLPP运行时间最长,因为迭代优化在获取边权矩阵的同时牺牲了运行时间,这显然不适用于对算法实时性要求高的环境.SPP方法耗时最少,本文提出的方法居中,但两者差异不大,而后者拥有更好的性能.

表1　SPP、SLPP和LCC-SPP方法运行时间对比

3.1.3不同分类器性能的比较实验

分别使用1NN分类器和SVM分类器对数据进行测试,其中,SVM分类器选择高斯核,核函数参数为4.7,见表2.需要说明的一点,对于SLPP方法没有给出SVM分类器对应的识别结果,这是因为SLPP方法在寻优求逆过程中,产生复数数值,这些数值不适用于SVM分类器,而文献[3]中也只使用了1NN分类器.

表2　基于不同降维方法和分类器组合的识别率

分类器对识别率具有重要的影响,不管用何种降维方法,SVM分类器比1NN分类器具有更好的识别结果;从仿真上可以看出LCC-SPP+SVM可以获得更高的识别率.

3.2SAR图像仿真分析

以17°下的BMP2-sn9563、T72-sn132和BTR70-snc71为训练集,以15°下的BMP2-sn9563、BMP2-sn9566、BMP2-snc21、T72-sn132、T72-sn812、T72-sns7、BTR70-snc71作为测试集.为了提高计算效率,这里对所有的SAR目标图像数据首先进行核主成分分析(Kernel Principal Component Analysis,KPCA)[22]特征提取,然后执行其他降维算法.KPCA方法中核函数选择高斯型核函数,函数中参数σ=50,KPCA特征提取维数设置为100.对于SLPP方法,图的近邻数k=5,热核参数经验性地设置为l2范数,迭代终止条件ε=10-4.此外,为了能够完成各种方法的比较,这里选取1NN分类器.

3.2.1特征维数Dim设置不同情况下的实验

受篇幅所限,图3仅给出部分目标识别结果,可得出以下结论:

(1)三种降维方法都能实现SAR图像目标的识别.从平均识别率上看,识别性能最好的是LCC-SPP.该方法不仅对同类型同型号的目标可获得较高的识别率,而且对同类型不同型号的目标也能获得较好的识别率.

(2)较SPP和SLPP,LCC-SPP方法最大的特点是:曲线比较平缓,即对降维维数具有较好的鲁棒性.例如,当维数Dim=10时,SPP和SLPP方法的识别性能都比较低,其平均识别率分别为61.84%和50.66%.

(3)从平均识别率上看,LCC-SPP方法随着维数的增加先增长后趋于平缓,在维数Dim=30时可获得最优的识别结果.

3.2.2不同SAR图像识别方法比较实验

表3给出本文方法与常用的SAR图像识别方法进行对比分析结果.在分析过程中,选用SAR图像方法主要有模板匹配法[23]、几何散列表法[24]以及KPCA+SVM法[25].这里的平均识别率为七个目标的平均识别结果,运行时间表示以BMP2-sn9563为例所运行的时间.

表3　不同SAR图像识别方法的比较

对比表3各种方法的平均识别率,LCC-SPP获得的识别效果最高,为95.56%,优于模板匹配法、几何散列表法和核KPCA方法.对比各种方法的运行时间,运行时间最短的是模板匹配法,其次是核KPCA方法,本文方法排第三.模板匹配法虽然运行时间短,但识别效果很差;KPCA方法虽然在识别时间和识别效果都体现出较良好的性能,但该方法有个重要前提是:假设已知目标的姿态角.众所周知,目标的姿态估计是存在一定的误差的[26],姿态误差的引入不仅影响识别精度,而且会增加运行时间.因此综合比较可以得出,本文方法性能最为优越.

4结论

本文在分析传统SPP方法和SLPP方法的基础上,结合样本图像数据之间的邻近关系,提出了基于局部约束编码的稀疏保持投影降维方法,给出了详细的推导过程和具体步骤,并根据特征提取的特点利用两种分类器实现分类.本章对算法进行了大量的仿真实验,得出结论:本章方法不仅适用于人脸图像数据,而且也适用于SAR图像数据且该方法对两种图像数据均能够得出较SPP和SLPP方法性能更好的识别结果,是一种普适性较好的方法.

参考文献

[1]李娜,刘方.基于模糊聚类视区划分的SAR目标识别方法[J].电子学报,2012,40(2):394-399.

LI Na,LIU Fang.A SAR target recognition method based on view-aspects parititioned by fuzzy clustering[J].Acta Electronic Sinica.2012,40(2):394-399.(in Chinese)

[2]LU CY,HUANG D S.Optimized projections for sparse representation based classification[J].Neurocomputing,2013(113):213-219.

[3]乔立山.基于图的降维技术研究及应用[D].南京:南京航空航天大学,2009.

QIAO Li-shan.Research on Graph-Based Dimensionality Reduction and Its Applications[D].Nanjing:Nanjing University of Aeronautics and Astronautics,2009.(in Chinese)

[4]SUN T,JIAO LC,LIU F,WANG S,FENG J.Selective multiple kernel learning for classification with ensemble strategy[J].Pattern Recognition,2013,46(11):3081-3090.

[5]TURK M A,PENTLAND A P.Eigenfaces for recognition[J].Journal of Cognitive Neuroscience,1991,3(1):71-86.

[6]TIPPING M,BISHOP C.Probabilistic principal component analysis[J].Jounrnal of the Royal Statistical Society,Series B,1999,61:611-622.

[7]SWETS DL,WENG J.Using discriminant eigvenfeatures for image retrieval[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1996,18(8):831-836.

[8]WANG Meng-zuo,WANG Kuan-quan,ZHANG David,Hongzhi ZHANG.Combination of two novel LDA-based methods for face recognition[J].Neurocomputing,2007,70(46):735-742.

[9]FU Y,HUANG T S.Locally linear embedded eigenspace analysis[J/OL].BMC Bioinformatiocs,2005.http:www.ifp.uiuc.edu/～yunfu2/papers/LEA-Yun05.pdf,2005.

[10]HE X F,CAI D,YAN S C,H J Zhang.Neighborhood preserving embedding[A].IEEE International Conference on Computer Vision[C].Beijing:IEEE,2005.1208-1213.

[11]HE X,NIYOGI P.Locality preserving projections[A].Proceedings of Conference on Advances in Neural Information Processing Systems[C].Washington DC:IEEE,2003.

[12]QIAO Li-shan,CHEN Song-can,TAN Xiao-yang.Sparsity preserving projections with applications to face recognition[J].Pattern Recognition,2010,43(1):331-341.

[13]WEI Chia-po,CHAO Yu-wei,YE Yi-ren,et al.Locality-sensitive dictionary learning for sparse representation based classification[J].Pattern Recognition,2013,46(5):1277-1287.

[14]WANG J,YANG J,et al.Locality-constrained linear coding for image classification[A].Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition[C].San Francisco:IEEE,2010.3360-3367.

[15]ZHANG X R,YANG Y,et al.Manifold constrained coding and sparse representation for human action recognition[J].Pattern Recognition,2013,46(7):1819-1831.

[16]SHEN Fu-min,TANG Zhen-min,XU Jing-song.Locality constrained representation based classification with spatial pyramid patches[J].Neurocomputing,2013,101:104-115.

[17]Olivetti Research Laboratory.The Olivetti & Oracle Research Laboratory Face Database[DB/OL].http://www.cam-orl.co.uk/faceddatabase.html,2013-03-13.

[18]Air Force Research Laboratory.Model Based Vision Laboratory.Sensor Data Management System[DB/OL].http:// www.Mbvlab wpafb af.mil/publica/sdms/datasets/mstar,2010-01-10.

[19]J Wright,A Yang,S Sastry,Y Ma.Robust face recognition via sparse representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(2):210-227.

[20]A Yang,J Wright,et al.Feature selection in face recognition:a sparse representation perspective[J/OL].BMC Bioinformatiocs,2007,08.http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-99.html,2007-08-17.

[21]Corinna Cortes,Vladimir Vapnik.Support-vector network[J].Machine Learning,1995,20(3):273-297.

[22]贾世杰,孔祥维.一种新的直方图核函数在图像分类中的应用[J].电子与信息学报,2011,33(7):1738-1742.

JIA Shi-jie,Kong Xiang-wei.A new histogram-based kernel function designed for image classification[J].Journal of Electronics & Information Technology,2011,33(7):1738-1742.(in Chinese)

[23]Novak L M,Owirka G J,et al.Performance of 10-and 20-traget MSE classification[J].IEEE Transactions on Aerospace and Electronic Systems,2000,36(4):1279-1289.

[24]韩萍,王蕴红,吴仁彪,等.一种有效的SAR自动目标识别方法[J].模式识别与人工智能,2003,16(2):208-212.

HAN Ping,WANG Yun-hong,WU Ren-biao,et al.An efficient SAR automatic target recogntion approach[J].PR & AI,2003,16(2):208-212.(in Chinese)

[25]BHANUB.Recognition of articulated and occluded objects[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1999,21(7):603-613.

[26]辛宁,王国宏,张静.改进的SAR图像车辆目标姿态角估计方法[J].火力与指挥控制,2008,33(5):57-60.

XIN Ning,WANG Guo-hong,ZHANG Jing.An improved synthetic pose estimation of SAR image[J].Fire Control and Command Control,2008,33(5):57-60.(in Chinese)

张静女.1976年2月出生,山东潍坊人.1999年、2003年和2008年分别在东北大学和海军航空工程学院获得工学学士、工学硕士和工学博士学位.现为海军航空工程学院电子信息工程系副教授.主要研究方向为雷达目标识别、图像处理.

E-mail:yzy913@sina.com

杨智勇男.1977年9月出生,河南洛阳.2000年、2004年和2009年海军航空工程学院分别获得工学学士、工学硕士和工学博士学位.现为海军航空工程学院讲师.主要研究方向为机器学习.

E-mail:yzy913@sina.com

Sparsity Preserving Projections Based on Locality Constrained Coding with Applications for Targets Recognition

ZHANG Jing1,YANG Zhi-yong2,WANG Guo-hong3,LIN Hong-wen1,LIU Xiao-di1

(1.DepartmentofElectronicandInformationEngineering,NavalAeronauticalandAstronauticalUniversity,Yantai,Shandong264001,China;2.SevenDepartment,NavalAeronauticalandAstronauticalUniversity,Yantai,Shandong264001,China;3.ResearchInstituteofInformationFusion,NavalAeronauticalandAstronauticalUniversity,Yantai,Shandong264001,China)

Abstract:Constructing graph by sparse representation (SP) can reduce the dimensionality reduction (DR) which relies on neighborhood parameter selection.However,these DR algorithms are usually unable to take sparse reconstruction into consideration while preserving local data structure.This paper presents a sparsity preserving projections based on locality-constrained coding (LCC-SPP) algorithm.Firstly,an “adjacent” weight matrix of dataset is constructed by sparse representation based classification (SRC).Then,a locality adaptor is introduced and the dimension reduction is modeled.We derive the solution of objective function.The similarities and differences are presented with sparse preserving projections (SPP) and soft locality preserving projections (SLPP),respectively.At last,the recognition flow is given.We conduct experiments on databases designed for face and synthetic aperture radar (SAR) images recognition.Considering the data locality,the proposed method has better recognition performance than SPP and SLPP.

Key words:target recognition;dimensionality reduction;sparse representation;locality constrained coding

作者简介

DOI:电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.025

中图分类号:TP751

文献标识码：A

文章编号：0372-2112 (2016)03-0658-07

基金项目:国家自然科学基金(No.61102167,No.61302008,No.61179016,No.61102165)

收稿日期:2014-06-19;修回日期:2014-12-17;责任编辑:覃怀银