局部约束相关自适应子空间分割

汪静，魏莱

（上海海事大学信息工程学院，上海201306）

局部约束相关自适应子空间分割

汪静，魏莱

（上海海事大学信息工程学院，上海201306）

如何利用数据本身相关性以及数据的内部结构来对数据集进行有效的分割是子空间分割的一个重要问题。根据数据集本身的内部结构以及数据之间相关性，提出一种新的基于局部约束的相关性自适应子空间分割方法（LCASS）。为实现良好的子空间分割效果，在基于迹Lasso方法的相关自适应子空间分割方法（CASS）基础上，通过增加局部约束来计算重构系数，并由此构建数据集邻接矩阵。在人脸聚类的实验证明中，此方法构造的邻接矩阵能够更好地表征数据集的内在结构，因此能够得到更好的聚类效果。

子空间分割；局部约束；重构系数

0 引言

子空间分割[1-2]作为图像处理与计算机视觉中的基本问题之一，往往是图像分析的一个关键步骤。子空间分割主要是根据数据的相关特性对数据进行聚类，分割的理想状态是每个集群都对应一个子空间，集群之间的关联是稀疏的，集群之内的关联则相对密切。近二十年以来，人们在子空间分割方面取得了很多进展，根据分割子空间构造的模型的不同，将常用的子空间分割方法分为代数方法、迭代方法、统计学方法和谱聚类[3-4]方法。具有代表性的谱聚类方法包括稀疏子空间聚类（Sparse Subspace Clustering，SCC）[5]、低秩表示（Low Rank Representation，LRR）[6]，最小二乘回归（Least Square Regression，LSR）以及在这些方法基础上扩展的一些方法。谱聚类方法的共性是在假设子空间是独立的情况下，第一步先利用数据点之间的相似性构造一个关联矩阵，第二步利用关联矩阵去构建一个无向图，然后利用谱聚类（Spectral Clustering）方法，如Ncuts[7]来进行分割。这些算法在人脸聚类、运动分割以及图像分割等应用中展示出良好的效果。但是在某些情况下，如当数据样本数比较小，并且有噪声和异常值时，这些算法也很难表现出很好的鲁棒性。

为了获得更好的聚类效果，Lin等人提出了一种能有效的平衡SCC和LRR的新的子空间分割方法，即基于迹Lasso方法的相关性自适应子空间分割方法（Correlation Adaptive Subspace Segmentation by Trace Lasso，CASS）[8]。该方法通过对系数向量及数据集乘积的迹Lasso的最小化约束，不仅保证了重构系数向量的稀疏性，同时也使得向量之间具有一定的组相关性。受此方法的启发，本文提出了局部约束[9]相关性自适应子空间分割算法（Locality-constrained Correlation Adaptive Subspace Segmentation，LCASS），算法通过增加对系数向量的局部约束来保证某一数据点的近邻点能够优先被选中来重构原数据点，从而更为精确的发现数据集的内在结构。实验证明，通过算法得到地系数向量构造而成的系数矩阵，能够有效地揭示数据集的内在结构，在人脸聚类中具有更好的分割效果。

1 相关子空间分割模型概述

（1）SSC（Sparse Subspace Clustering）模型

SSC利用稀疏表示[10-11]算法来计算数据点之间的重构系数，通过重构系数表示数据点之间的相关性。

稀疏表示的目标函数可以表示为下式：

与SSC考虑稀疏性不同的是，LRR[12-13]主要是考虑数据集的低秩表达，目标函数可以表示成如下形式：

其中‖w‖*代表系数矩阵W的核[14]范数，E是误差矩阵，‖E‖2,1（∑ij‖Ej‖2）表示误差矩阵的l2,1范数，ℷ>0是一个参数，用来调节两者效果。通过求解问题（2），LRR可以直接得到重构之后的系数矩阵，相比于SSC，LRR在数据集具有较大噪声时仍然能够发现数据集的全局内在结构，因此在很多子空间分割任务中，表现出了更好的效果。

（3）CASS（Correlation Adaptive Subspace Segmenta⁃tion by Trace Lasso）模型

最近，Lin等人在LRR和SSC的基础上，提出了一种基于迹Lasso[15]的相关自适应子空间分割模型（CASS），它平衡了LRR和SCC算法各自的特点，计算得到的系数向量能够更好的表征数据之间的相关性。CASS主要解决以下优化问题：

尽管，CASS表现出了良好的性能，但是其没有考虑数据集的局部结构，很多算法已经证明，通过考虑数据集的局部结构，增加局部结构约束，能够有效提高算法的性能。针对这个问题，本文提出了局部约束相关性自适应子空间分割方法（Locality-constrained Correla⁃tion Adaptive Subspace Segmentation，LCASS）。

单支烟重量主要取决于卷入烟条的烟丝量和紧头位置偏差。所以重量控制系统应该确保卷入烟条烟丝量的稳定，可通过调节平准盘高度实现；同时应该有效控制紧头位置偏差，可通过调节平准盘相位实现。

2 局部约束相关自适应子空间分割

2.1 目标函数

所谓的局部约束，在这里指的是在进行某一数据重构时，希望尽可能的选择其局部数据点[16]来进行重构，因此局部约束相关自适应子空间分割的目标函数可以定义成：

其中⊙表示Hadamard乘积，公式（4）可以转换成如下等式：

d∈RN是用来描述不同数据点之间的相似度的一种局部约束符，定义如下：

其中dist(xi,X)=[dist(xi,x1),…,dist(xi,xN)]T，dist(xi,xj)是xi和xj之间欧式距离，σ是用来调节局部约束符的权值的递减速度。

2.2 算法流程

求解局部约束相关自适应子空间分割的算法可以描述如下：

算法1：采用迭代算法估计局部约束参数c*

输入：数据矩阵X∈RD×N,参数σ，d0=0，c0=0，μ

步骤1：采用欧氏距离计算出数据点之间的相似度度量参数d

步骤4：通过解决线性模型(XTX+ℷD) c*=XTy得到局部约束参数ci

通过算法1，可以计算得到所有ci，将其组织构造成系数矩阵C=[c1,c2,…,cn]。再令最后使用Normalized Cuts进行得到最终的分割结果。

3 实验分析

在本节之中，我们主要是通过对不同的人脸数据库中的人脸进行分割实验，用以对比本文的算法与现存的算法之间的优劣。

3.1 实验数据集和实验设置

我们主要使用三个人脸数据库中的人脸图像来进行分割实验，包括ORL[17]、Extended Yale B[18]以及AR[19]人脸数据库。

ORL人脸数据库包含40个对象，每个对象有10幅图像，共计400幅灰度图像，包含不同的光照、表情。图像的原始尺寸是92×112，我们分别选取其中l（l=10,20,40）个人的图像作为分割样本，我们将其正规化到32×32。图1是ORL数据库的一些图片样本。

Extended Yale B人脸数据库是由38个对象共2432幅图像组成，其中每个对象64幅灰度图像，同样，这些照片也是在不同的光照、表情下拍摄的。我们分别选取其中的l（l=5,10,20）个人的图像用于实验。我们也将这些图像大小正规化到32×32，图2是Extended Yale B人脸数据库的一些图片样本。

AR人脸数据库是由50位男性和50位女性在不同的光照和表情下拍摄的照片组成，每个人26幅图像共计2600幅灰度图像。我们分别选取其中l（l=10,20,30）个人的图像，同样，我们也将其正规化到32×32，图3是AR人脸数据库的一些图片样本。

表1 各种算法进行子空间分割的最优分割准确率（%）

3.2 实验结果

我们通过分别在三个人脸数据库上选择不同角度不同光照下的人脸上进行几个算法的分割对比实验，根据自身经验选择相对比较好的数值来设置相关的参数ℷ和μ的值，得到相关的分割准确率。表1是各个算法得到的最优分割准确率，通过表1很明显的可以看到本文所提出的LCASS方法要明显优于其他的几个算法。

图1 ORL人脸数据库的图片样本

图2 Extended Yale B人脸数据库的图片样本

图3 AR人脸数据库的图片样本

4 结语

本文提出了一种新的子空间分割方法局部约束相关自适应子空间分割方法LCASS。通过局部约束优先地选择相关数据点的近邻点，来重构原有的数据点，更好地表征了数据点的内在结构。从而从很好地利用了数据本身的内在结构以及数据点对之间的相关性，因而大大的提高了子空间分割的准确率。同时，在ORL、Extended Yale B、AR等三个人脸数据库上进行了分割实验，证明本文提出的算法的有效性。

[1]Parsons L,Haque E,Liu H.Subspace Clustering for High Dimensional Data:a Review[J].ACM SIGKDD Explorations Newsletter,2004, 6（1）:90-105.

[2]Vidal,René.Subspace Clustering[J].IEEE Signal Processing Magazine,2011,28（2）:52-68.

[3]Lauer F,Schnorr C.Spectral Clustering of Linear Subspaces for Motion Segmentation[J].Proceedings,2009,30（2）:678-685.

[4]Donoho D L.Compressed Sensing[J].IEEE Transactions on Information Theory,2006,52（4）:1289-1306.

[5]E.Elhamifar and R.Vidal.Sparse Subspace Clustering[C].IEEE Computer Society.DC,Washington:IEEE,2009:2790-2797.

[6]G.Liu,Z.Lin,and Y.Yu.Robust Subspace Segmentation by Low-rank Representation[C].International Conference on Machine Learning,New York:ICML,2010:663–670.

[7]Shi J,Malik J.Normalized Cuts and Image Segmentation[C].IEEE Transactions on Pattern Analysis and Machine Intelligence.Washington:IEEE,1997:888-905.

[8]Lu C,Feng J,Lin Z,et al.Correlation Adaptive Subspace Segmentation by Trace Lasso[J].2013,49:1345-1352.

[9]Wang J,Yang J,Yu K,et al.Locality-Constrained Linear Coding for Image Classification[C].IEEE Computer Society Conference on Computer Vision&Pattern Recognition IEEE Computer Society Conference on Cvpr.Washington:IEEE,2010:3360-3367.

[10]Wright J,Yang A Y,Ganesh A,et al.Robust Face Recognition via Sparse Representation[J].IEEE Transactions on Pattern Analysis& Machine Intelligence,2009,31（2）:210-227.

[11]Elhamifar E,Vidal R.Clustering Disjoint Subspaces Via Sparse Representation[C].Acoustics Speech and Signal Processing（ICASSP）,2010 IEEE International Conference on IEEE.Washington:IEEE,2010:1926-1929.

[12]Vidal R,Favaro P.Low Rank Subspace Clustering（LRSC）[J].Pattern Recognition Letters,2014,43（1）:47-61.

[13]Liu G,Lin Z,Yan S,et al.Robust Recovery of Subspace structures by Low-Rank Representation[J].Pattern Analysis&Machine Intelligence IEEE Transactions on,2013,35（1）:171-84.

[14]Zhang K,Wang Q,Lan L,et al.Sparse Semi-Supervised Learning on Low-Rank Kernel[J].Neurocomputing,2014,129（4）:265-272.

[15]Grave E,Obozinski G,Bach F.Trace Lasso:a Trace Norm Regularization for Correlated Designs[J].Advances in Neural Information Processing Systems,2011:2187-2195.

[16]Gui J,Sun Z,Jia W,et al.Discriminant Sparse Neighborhood Preserving Embedding for Face Recognition[J].Pattern Recognition, 2012,45（8）:2884-2893.

[17]Cambridge University Engineering Department.ORL.http://www.uk.research.att.com/facedatabase[DB].html,1992,4.

[18]Georghiades A S.YALE.http://cvc.yale.edu/projects/yalefaces/yalefaces[DB].html,1997,10.

[19]AR Face Database（AR）.http://rvl1.ecn.purdue.edu/～aleix/aleix_face_[DB].html.

Locality-Constrained Correlation Adaptive Subspace Segmentation

WANG Jing，WEI Lai

（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

It is an important problem of subspace segmentation that how to segment the data sets effectively by using the correlation of the data points and the internal structure.Proposes the Locality-constrained Correlation Adaptive Subspace Segmentation which based on the Correlation Adaptive Subspace Segmentation by Trace Lasso,calculates the reconstructed coefficients by adding local constraints and constructs a adja⁃cency matrix of data sets.The contrastive experiments on several benchmark face database show the effectiveness of proposed method.

1007-1423（2017）21-0031-05

10.3969/j.issn.1007-1423.2017.21.005

汪静（1993-），女，安徽安庆人，硕士研究生，研究方向为信息处理与模式识别；

2017-04-21

2017-07-12

Subspace Segmentation;Locality-Constrained;Reconstructed Coefficients