A Laplacian Based Method For Extraction Curve-Skeleton From Point Cloud

Extraction of curve-skeletons is a fundamental problem with many applications in computer graphics and visualization.Curve-skeletons are 1D representation of 3D objects, which are useful commonly for many visualization tasks including animation,virtual navigation,segmentation,shape match,etc.Most existing curve-skeleton extraction methods make use of a volumetric discrete representation or mesh surface representation.But methods for extraction curve-skeletons from point clouds are seldom relatively.In this paper,we proposed an effective and robust algorithm for extraction curve-skeletons fi'om point clouds.Firstly,we setup neighborhoods of scattered points,and constructed a Laplace matrix.We treated all points as positional constraints.We solved and updated the discrete Laplace system iteratively,until all points contracted to the positions we needed.Then we employed the Principle Component Analysis(PCA) to differentiate between joints and branches of the contracted points.We clustered the two kinds of regions separately to get the key nodes.Then we connected these key nodes by the connection surgery we proposed to get a raw curve-skeleton of the given point cloud.We constructed a graph on the curve-skeleton,and computed the Minimum Spanning Tree(MST).Finally,we refined the MST and gained the final curve-skeleton.The point clouds which acquired by the 3D scanner are usually noisy.We added Gauss noise on the sampled points of manifold surfaces,and extracted the curve-skeleton using our algorithm.The results showed that our algorithm can be applied on noisy point clouds.That is the algorithm has good robustness.The algorithm can also be applied on point clouds of arbitrary topology.The experiments showed that we can extract curve-skeletons of different genus point cloud models.