【作者】 张涛；

【导师】 唐振民；

【作者基本信息】 南京理工大学 ， 模式识别与智能系统， 2018， 博士

【摘要】 近年来,随着计算机和互联网技术的快速发展,人们可以很容易地获取海量的数据。这些数据往往是高维的、复杂的,并且包含了大量的噪声和冗余信息。因此,如何实现高维数据的低维表示并探索其本质结构,是十分具有挑战性的问题。低秩表示(LRR)算法作为模式识别、机器学习、计算机视觉等领域的重点研究课题,能够有效地发现高维数据的低维子空间结构和数据中噪声的结构特点,目前已被广泛应用于子空间聚类、半监督学习、目标跟踪等多种应用场景。低秩表示算法的基本思想是将数据矩阵表示成在字典矩阵下的线性组合,并通过求解秩最小化问题使得该线性组合的系数矩阵是最低秩的。其中,约束低秩表示算法通过对系数矩阵设计不同的约束项,可以进一步揭示数据的结构信息,是目前的研究重点。现有的约束低秩表示算法从其定义、发展过程以及具体的应用方向上考虑,可分为基本约束LRR、稀疏约束LRR和流形约束LRR。但无论哪一类方法,由于不同应用场景的数据复杂多变、低秩结构信息挖掘不准确、其他结构信息利用不全面以及不确定数据噪声的干扰,其揭示数据本质结构的能力有待改善,在各种量化性能评价指标上的表现都需要进一步提升。本文正是基于这一目标,在对国内外一些具有代表性的约束LRR方法深入研究的基础上,提出了几种改进的约束LRR方法。论文的研究成果主要体现在以下几个方面:(1)提出一种基于加权Schatten-p范数和Lq范数的鲁棒低秩表示(RLRR)算法,并应用于子空间聚类问题。为了更好地估计秩函数和描述不同的噪声,RLRR算法在LRR算法的基础上引入加权Schatten-p范数和Lq范数以实现性能提升。一方面,将LRR算法中的核范数推广到Schatten-p范数并对系数矩阵的奇异值分配不同的权重,从而更准确地估计秩函数。另一方面,使用Lq范数代替LRR算法中的L2,1范数来描述噪声,进一步提升算法鲁棒性。最后,采用非精确的增广拉格朗日乘子方法(IALM)求解所提出的目标函数。该方法与几种具有代表性的子空间聚类算法相比,鲁棒性更好,聚类指标得到提升,在受光照变化、高斯噪声、块状遮挡干扰下的Extend Yale B数据集上的平均聚类错误率均低于SPN算法,分别低出2.42%、5.10%和4.30%。(2)提出一种基于L2,p范数的快速低秩表示(FLRR)算法,并应用于子空间聚类问题。针对LRR算法在求解过程中需要计算多次奇异值分解(SVD),计算效率低的缺陷,提出一种改进的算法,旨在保证算法准确率和鲁棒性的同时,提高算法的计算效率。具体来讲,分别使用Schatten-p范数和L2,q范数代替LRR算法中的核范数和L2,1范数,从而使模型更具一般性和鲁棒性。然后对数据矩阵进行QR分解,将原问题转化为小尺度的L2,p范数最小化问题。在该问题的求解过程中不需要计算SVD,从而降低了计算成本。在人工数据集、公共图像数据集和运动分割数据集上的实验结果表明,本文提出的FLRR算法的聚类错误率和算法运行时间指标优于其它几种具有代表性的对比方法,特别是在公共图像数据集上,FLRR算法的运行时间比LRR算法快2～4倍。(3)提出一种基于平滑秩估计和加权稀疏约束的半监督低秩表示(SSLRR)算法,并应用于半监督学习问题。SSLRR算法分别对非负低秩稀疏图(NNLRS)算法的低秩项和稀疏项进行改进,从而准确地描述数据的全局子空间结构和局部线性结构。在构建目标函数时,使用对数函数代替核范数平滑地估计秩函数,同时利用形状交互信息和有标签样本的类别信息构造加权稀疏约束正则项。然后通过带有自适应惩罚的线性交替方向法(LADMAP)求解目标函数并重构数据的图结构,最后利用基于局部和全局一致性(LGC)的半监督分类框架完成学习任务。当有标签样本的数量为10%时,SSLRR算法在ORL、Extend Yale B、PIE和USPS数据集上的分类准确率分别达到82.94%、93.50%、83.97%和92.99%,超过12种具有代表性的基于低秩表示和经典图的半监督学习算法,验证了算法的有效性。(4)提出一种融合矩阵低秩表示和稀疏流形约束的目标跟踪(LRSMT)算法。为了挖掘基于粒子滤波的目标跟踪算法中粒子样本间的全局和局部结构信息,LRSMT算法将粒子样本用字典模板表示,并对表示系数加以低秩、稀疏和流形约束。具体来讲,对系数矩阵的奇异值进行弹性网正则化来捕获粒子样本间的低秩结构,并构造一个拉普拉斯图来捕获粒子样本间的流形结构。同时,利用时间一致性自适应的裁剪和选择候选粒子,并动态地更新字典模板以进一步提高算法性能。最后,在粒子滤波框架下利用LADMAP方法对算法进行优化。在OTB目标跟踪数据集的50个具有挑战性的视频序列上同14种有代表性的跟踪方法进行定性和定量比较,LRSMT算法的AUC值和准确率指标分别达到53.8%和71.7%,均高于其他比较方法,表明所提算法的跟踪性能更好。综上所述,本文的第一项研究成果是针对约束LRR算法中基本的低秩约束情况,通过准确地挖掘数据的低秩结构信息和处理不同的噪声,提高了子空间聚类算法的鲁棒性;第二项研究成果是在保证算法鲁棒性的同时,进一步提高了算法的计算效率;第三项研究成果是探讨了算法的低秩和稀疏约束,通过同时利用数据的全局子空间结构信息和局部线性结构信息,提高了半监督学习算法的性能;第四项研究成果是将基于低秩、稀疏和流形约束的LRR算法应用于目标跟踪领域,提高了传统算法的跟踪效果。从模型的复杂程度考虑,四项研究成果的模型从简单到复杂,呈现出一种递进关系。从模型的实用角度考虑,前三项研究成果偏重于算法研究,第四项研究成果偏重于实际应用,实现从理论到应用的过渡。更多还原

【Abstract】 In recent years,with the rapid development in computer and Internet technology,people can easily access massive amounts of data.The data is high-dimensional,complicated,and usually contains large amounts of noise and redundant information.How to achieve the low-dimensional representation and explore the underlying structure of high-dimensional data is a very challenging problem.As an important research topic in pattern recognition,machine learning and computer vision,low rank representation(LRR)can effectively capture the low-dimensional subspace structure of high-dimensional data and reveal the structural characteristic of data noise.Due to its effectiveness and practicability,low rank representation has been widely applied in subspace clustering,semi-supervised learning,and visual tracking,etc.The main idea of LRR is to represent the data matrix as a linear combination of the bases in a given dictionary matrix and let the rank of the coefficient matrix of the linear combination to be the lowest by solving the rank minimization problem.Constrained low rank representation algoritllm can further reveal the structural information of the data by designing different constraints on the coefficient matrix,which is the focus of current research.From the perspective of definition,development process and the specific application direction,exisiting constrained LRR methods can be divided into three classes:basic constraint LRR,sparse constraint LRR and manifold constraint LRR.Due to the data in different application scenes is complex,the low rank structure information is inaccurate,the other structural information is not fully utilized and the interference of data noise is uncertain,the ability to reveal the essential structure of data of the methods belonging to the three classes should be improved,and the results of the quantitative performance evaluation of these methods need to be enhanced.To achieve this goal,this paper proposes several novel constrained LRR methods based on studying many state-of-the-art LRR methods.Generally,the main contributions of this thesis are as follows:(1)A robust low rank representation algorithm based on weighted Schatten-p norm and Lq norm(RLRR)is proposed for subspace clustering.In order to better approximate the rank function and describe different noises,RLRR achieves low rank property via the new formulation with weighted Schatten-p norm and Lq norm.Specifically,the nuclear norm is generalized to be the Schatten-p norm and different weights are assigned to the singular values,and thus it can approximate the rank function more accurately.In addition,Lq norm is further incorporated into RLRR to model different noises and improve the robustness.An efficient algorithm based on the inexact augmented Lagrange multiplier method is designed for the formulated problem.Compared with several state-of-the-art subspace clustering methods,the robustness of the proposed method is better and the clustering performance is enhanced.The average clustering error rates on Extend Yale B dataset under illumination variation,Gauss noise and block occlusion are lower than those of SPN,which are 2.42%,5.10%and 4.30%lower respectively.(2)A fast low rank representation algorithm based on L2,p norm(FLRR)is proposed for subspace clustering.LRR requires to calculate multiple singular value decomposition in calculation process,which leads to low computational efficiency.Therefore,we propose an improved algorithm to not only ensure the accuracy and robustness,but also improve the computational efficiency.Speciflcally,the nuclear norm and L2,1 norm in LRR are generalized to be the Schatten-p norm and L2,q norm,respectively.The new model is more general and robust than LRR.Then,we decompose the data matrix by QR decomposition and convert the new model into a small-scale L2,p norm minimization problem,which requires no SVD and thus has low computational cost.Experimental results on synthetic dataset,public image dataset and motion segmentation dataset demonstrate the superiority of the proposed method in terms of clustering error rate and running time.Especially,the running time of FLRR is faster than that of LRR 2～4 times on the public image dataset.(3)A semi-supervised low rank representation algorithm based on smooth rank approximation and weighted sparse constraint(SSLRR)is proposed for semi-supervised learning.SSLRR improves the low rank and sparse term in the nonnegative low rank sparse graph respectively,so that it can capture both the global subspace structure and locally linear structure exactly.When building the objective function,the logarithm function instead of the nuclear norm is used to approximate the rank function smoothly.Meanwhile,the shape interaction information and the label information of labeled samples are used to build the weighted sparsity constraint term.The objective function is solved by a linearized alternating direction method with adaptive penalty and the graph construction can be restructured.Finally、a semi-supervised classification framework based on local and global consistency is used to finish the learning task.When the number of label samples is 10%,the classification accuracy of SSLRR on ORL,Extend Yale B,PIE and USPS datasets can reach 82.94%,93.50%,83.97%and 92.99%respectively,and more than 12 state-of-the-art semi-supervised learning algorithms based on low rank representation and classical graph,which verify the validity of SSLRR.(4)A visual tracking algorithm based on low rank representation and sparse manifold constraint(LRSMT)is proposed.In order to find the global and local structure information of the particles in the visual tracking algorithm based on particle filter,LRSMT represents particles by dictionary templates,and adds low rank,sparse and manifold constraints on the representation coefficient.Specifically,we utilize an elastic net regularizer over singular values of coefficient matrix to capture the low rank structures of particles,and build a Laplacian graph to capture the manifold structure of particles.Meanwhile,we prune and select candidate particles by exploiting temporal consistency,and dynamically update the dictionary template to further improve the performance of LRSMT.Finally,we use the LADMAP method to optimize the algorithm in the particle filter framework.Compared with 14 state-of-the-art tracking methods in the 50 challenging video sequences of the OTB target tracking dataset qualitatively and quantitatively,the AUC value and the accuracy index of LRSMT are 53.8%and 71.7%respectively,which are higher than those of the other comparison methods.It shows that the tracking performance of the proposed algorithm is better.To sum up,the first work of this paper studies the basic low rank constraint of the constrained LRR algorithm.By accurately capturing the low rank structure information of the data and processing the different noise,we can improve the robustness of the subspace clustering algorithm.The second work not only ensures the robustness,but also improves the efficiency of the algorithm.The third work discusses the low rank and sparse constraints of the algorithm and improves the performance of semi-supervised learning by using the global subspace structure inf’ormation and local linear structure information.The fourth work discusses the application of algorithm in visual tracking by considering the low rank,sparsity and manifold constraints,which improves the tracking results of the traditional algorithms.Considering the complexity of the model,the four works present a progressive relationship,from simple to complex.Considering the practicability of the model,the first three works are focused on the algorithm research,while the fourth work is focused on the practical application.Thus,this paper realizes the transition from theory to application.更多还原