【作者】 张杰；

【导师】 刘秀平；

【作者基本信息】 大连理工大学 ， 计算数学， 2015， 博士

【摘要】 根据数据的内在结构对数据进行分类是数据分析的一个重要问题.由于大量的数据(例如：运动轨迹,人脸,纹理)都可以被线性子空间近似的刻画,所以基于线性结构的数据分类问题在数据分析中得到了广泛关注-这就是子空间聚类问题.受到压缩感知技术的启发,稀疏性表示在子空间聚类中得到了成功的应用.该类方法首先利用1-维或2-维稀疏性表示获得观测数据的关系图.然后,通过谱聚类或规范化切割得到最终的聚类结果.其中,2-维稀疏性表示(低秩表示,LRR)提供了一种挖掘数据全局结构的方法.在数据所在的子空间互相独立的假设条件下,LRR可以在理论上确保获得完全正确的类别关系.本文通过进一步分析发现,数据所在的子空间为互相独立的子空间,不仅是LRR可以获得完全正确的类别关系的充分条件,同时也是其必要条件.然而,在实际应用中存在大量的数据无法保证满足这一假设条件,例如图形处理中的3维网格的分割与标注问题.这局限了LRR在图形处理中的应用.本文主要针对这一问题对模型进行改进,并将其应用到图形处理中.本文主要工作包括：1.将采样数据的自身特点与表示矩阵的全局先验相结合,提出结构引导的低秩表示模型(SGLRR)该模型可以有效的结合数据的全局结构,局部信息及多种先验的标签信息.即使当数据所在的子空间不满足互相独立的条件时,SGLRR也能对其进行高质量的分割.而且,本文将SGLRR应用到三维网格的语义分割和标注中.通过将特征相似性和特征空间结构有效的结合起来,该方法不仅移除了以往算法中冗长的离线学习过程,而且当已知标注模型的个数很少时也可以对测试模型进行正确的标注.2.基于SGLRR,提出了鲁棒的保特征的三维点云法向估计算法.在点云的法向估计中,如何准确的估计尖锐特征附近的法向是一个十分困难的问题.这主要是因为当一个点位于尖锐特征附近的时候,其邻域一般是由多个光滑曲面拼接而成的,位于不同光滑曲面上的点会影响法向的估计.为了克服这一问题,本文利用点云数据中平坦区域中可靠的局部结构信息作为引导,通过SGLRR将邻域分割成多个光滑的区域,再从中选择最合适的光滑区域进行法向估计.该方法将数据分析的整体框架与点云数据处理的自身特点相结合,从本质上解决了点云数据分析中遇到的噪声、离群点、采样点不均匀、尖锐特征等问题,提高了点云数据的法向估计、特征提取等工作的正确性及稳定性.3.提出以有引导的最小二乘表示(SGLSR)为基础的子空间聚类模型.当数据所在的子空间不满足互相独立的条件时,SGLSR与SGLRR都可以得到高质量的子空间聚类效果,但SGLSR的求解速度更快.针对SGLSR,本文给出了快速的数值解法.由于该解法易于实现并行计算,因此为高效的处理大规模的数据提供了可能性.针对点云的法向估计提出子空间结构传播算法.将该传播算法与SGLSR相结合,提出一种快速有效的点云法向估计算法.4.将核化的思想和低秩表示技术相结合,提出了一般化低秩表示方法(GLRR).在该框架之下,可以根据观测数据的内部结构(包括具有复杂结构的非线性数据),构造不同的核函数实现其聚类.本文证明了LRR是GLRR的一种特殊情况.针对子空间分割问题,本文提出了子空间分割核函数.在该核函数的作用下,即使数据所在的子空间不满足互相独立的条件,GLRR亦能够准确的恢复数据间的子空间结构.而且,该一般化方法具有普适性,可以推广到其它的基于表示的子空间分割方法中(例如,1-维稀疏性表示).对仿真数据和视觉数据精确分割的结果表明我们的算法是有效的.更多还原

【Abstract】 Data clustering is a fundamental problem in data analysis. Since the well known linear subspace is easy to compute, using this model to characterize a given set of data is a common choice. This is the problem of subspace clustering. Inspired by the idea of compressed sensing, the representation based on sparsity has achieved success in subspace clustering. These methods obtain the affinity matrix by solving the 1D or 2D sparsity representation. Then the final segmen-tation result is completed by applying the NCut method or spectral clustering. Especially, the 2D sparsity representation (Low-Rank Representation) is a powerful tool to recover the relationship between data globally. A great deal of theoretical analysis has been made about LRR. When the subspaces are independent and the data sampling is sufficient, LRR exactly recovers the true subspace structures. However, it requires that the subspaces be independent. The assumption is so strong that it will be violated in many computer graphics problems. In this paper, we improve LRR to overcome this problem and employ the improved models into computer graphics. The main contributions of this article are as follows:1. We provide a new low-rank subspace clustering framework with structure guiding (S-GLRR) for more general subspace clustering. This framework combines the global structure of feature space and the prior from local similarity seamlessly and can exactly recover the subspace structure even if the given data is drawn from some subspaces which are not independent. Fur-thermore, we introduce this framework into 3D mesh segmentation and labeling. By introducing structure guidance to incorporate label information into low-rank representation, the tedious of-f line pre-training process which is usually employed by conventional data driven approaches is successfully eliminated. Our method generates correct labeling, even when the set of given examples are few.2. We introduce the SGLRR into point cloud normal estimation. It is challenging to ex-actly estimate the normal near sharp feature. When a point is near sharp features, its neigh-borhood maybe sampled from several piecewise surfaces. In such case, the estimated normals tend to smooth sharp features, since the normal estimation of the point maybe influenced by its neighbors lying on some other surfaces. In order to over come this problem, an unsupervised learning process is designed to estimate the prior knowledge from reliable regions, which are utilized in SGLRR to classify unreliable regions close, even extremely close to sharp features. Then the accurate normal of each candidate point is estimated using a selected proper sub-neighborhood. Our method is capable of estimating normals accurately even in the presence of noise and anisotropic samplings, while preserving sharp features within the original point data. We demonstrate the effectiveness and robustness of the proposed method on a variety of examples.3. A novel linear subspace segmentation model, a structure guided least squares representa-tion (SGLSR), is proposed. Even if the subspaces are not independent, it can exactly recover the subspace structure as well as LRRSG with less runtime. A rapid algorithm to solve SGLSR is devised and the algorithm has a natural parallelism. Large-scale dataset can be handled efficient-ly using the parallel implementation. A subspace structure propagation algorithm is proposed for normal estimation. Combining LSRSG and the subspace structure propagation algorithm, we devise a fast and robust feature preserving normal estimation method.4. Inspired by the kernel method, we propose the generalized low-rank representation. We prove that LRR is a special case of GLRR. With the appropriate kernel GLRR can handle different problems, so it has the potential to deal with some complex problems. We further propose the subspace segmentation kernel which can enhance the linear structure of the data for subspace segmentation. With subspace segmentation kernel GLRR can recover the structure of data extractly, even if the given data is drawn from some subspaces which are not independent. It is worth noticing that the method which extends LRR to GLRR can also be used for ID sparsity representation. We demonstrate the effectiveness of our method by comparing it with other state-of-the-art methods on several experiments.更多还原