Curve skeleton extraction by coupled graph contraction and surface clustering

Jiang, Wei, Xu, Kai, Cheng, Zhi-Quan, Martin, Ralph Robert and Dang, Gang 2013. Curve skeleton extraction by coupled graph contraction and surface clustering. Graphical Models 75 (3) , pp. 137-148. 10.1016/j.gmod.2012.10.005

Full text not available from this repository.

Abstract

In this paper, we present a practical algorithm to extract a curve skeleton of a 3D shape. The core of our algorithm comprises coupled processes of graph contraction and surface clustering. Given a 3D shape represented by a triangular mesh, we first construct an initial skeleton graph by directly copying the connectivity and geometry information from the input mesh. Graph contraction and surface clustering are then performed iteratively. The former merges certain graph nodes based on computation of an approximate centroidal Voronoi diagram, seeded by subsampling the graph nodes from the previous iteration. Meanwhile, a coupled surface clustering process serves to regularize the graph contraction. Constraints are used to ensure that extremities of the graph are not shortened undesirably, to ensure that skeleton has the correct topological structure, and that surface clustering leads to an approximately-centered skeleton of the input shape. These properties lead to a stable and reliable skeleton graph construction algorithm. Experiments demonstrate that our skeleton extraction algorithm satisfies various desirable criteria. Firstly, it produces a skeleton homotopic with the input (the genus of both shapes agree) which is both robust (results are stable with respect to noise and remeshing of the input shape) and reliable (every boundary point is visible from at least one curve-skeleton location). It can also handle point cloud data if we first build an initial skeleton graph based on k-nearest neighbors. In addition, a secondary output of our algorithm is a skeleton-to-surface mapping, which can e.g. be used directly for skinning animation.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Additional Information:	Curve skeleton; Voronoi; Graph contraction; Surface clustering; Deformation
Publisher:	Academic Press
ISSN:	1524-0703
Last Modified:	04 Jun 2017 04:49
URI:	https://orca.cardiff.ac.uk/id/eprint/45391

Citation Data

Cited 19 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item