Spectral Mesh Segmentation via l₀ Gradient Minimization

Mesh segmentation is a process of partitioning a mesh model into meaningful parts - a fundamental problem in various disciplines. This paper introduces a novel mesh segmentation method inspired by sparsity pursuit. Based on the local geometric and topological information of a given mesh, we build a Laplacian matrix whose Fiedler vector 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 l₀ gradient minimization problem. To solve this problem efficiently, we adopt a coarse-to-fine strategy. A fast heuristic algorithm is first devised to find a rational coarse segmentation, and then an optimization 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. Experimental 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.