Feature Lines Extraction And Segmentation On Meshes Via Sparse Optimization

With the rapid development of 3D digital scanning and printing techniques,the discipline of digital geometry processing has opened up a relatively new field of mathe-matical science and computer science that is concerned with representation,manipula-tion and analysis of geometric data.The main research topics include mesh denoising,feature extraction,segmentation,parameterization,simplification,remeshing,editing,deformation,model repair and so on.In this paper,using recently developed sparse representation and optimization techniques,we present effective methods for feature lines extraction and segmentation on meshes to tackle several drawbacks of existing methods.Aiming at improving the robustness of feature lines extraction on noisy meshes,we propose a new algorithm based on the observation that the edges located in feature lines compared to the whole edges are very sparse.For a given mesh,our algorithm firstly computes a scalar or a vector for each triangle as the input u0,e.g.,normal,color,mean curvature.Then we optimize u0 to obtain a new measurement u such that the whole number of jumps of u across all edges of mesh is minimized.The approximation error between u0 and u is also required to be as small as possible.Put them all together,we formulate feature lines extraction as a l0 gradient minimization problem.To solve it efficiently,we provide an alternating direction algorithm based on the penalty,approach with variable splitting technique.In addition,we introduce a heuristic strategy to im-prove the sparsity of the solution resulted from the l0 gradient minimization problem for achieving high quality feature lines.Numerous experimental results demonstrate that our method can extract feature lines effectively.Compared with some state-of-the-art methods,our approach can produce results with higher quality and is more robust to the noisy data.For mesh segmentation,one of the most popular methodologies is spectral analy-sis,which has achieved better performance and been investigated by many authors re-cently.However,existing spectral mesh segmentation algorithms often leads to jaggy boundaries between different parts,over-segmentation and are sensitive to the choice of parameters.From sparsity representation point of view,the segment boundary edges compared to the whole edges in the given mesh are very sparse.Inspired by this obser-vation,we introduce a new mesh segmentation method via l0 gradient minimization.Based on the local geometric and topological information of a given mesh,we build a Laplacian matrix and compute its Fiedler vector which is used to characterize the uniformity among elements of the same segment.By analyzing the Fiedler vector,we reformulate the mesh segmentation problem as a l0 gradient minimization problem.To solve this problem efficiently,we adopt a coarse-to-fine strategy.A fast heuristic algo-rithm is firstly devised to find a rational coarse segmentation,and then a new algorithm based on the alternating direction method of multiplier(ADMM)is proposed to refine the segment boundaries within their local regions.To extract the inherent hierarchical structure of the given mesh,our method performs segmentation in a recursive way.Ex-perimental results demonstrate that the presented method outperforms the state-of-the-art segmentation methods when evaluated on the Princeton Segmentation Benchmark,the LIFL/LIRIS Segmentation Benchmark and a number of other complex meshes.