Structure Guided Low-rank Representation And Its Applications In Digital Geometry

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.