Research And Realization Of Skeleton Extracting Algorithm For3D Point Cloud Model

The extraction of curve skeleton for3D models is a fundamental problem in the field of computer graphics and visualization. Curve skeleton, widely applying in virtual reality, computer animation, model segmentation, virtual navigation, shape matching,3D printing and other fields, is a one-dimension representation of3D model. The three-dimensional models applied in the existing skeleton extraction methods are mostly expressed in the forms of discrete voxel or surface mesh, but the documents published about directly extracting skeleton curve on point cloud are quite rare. Most voxel data and mesh data, however, are obtained from laboratory by modeling, while it is convenient for point clouds data to express real world objects, which is worth paying more attention to extract curve skeleton from point cloud. Although recently some research on skeleton extraction from point clouds have appeared, they mostly focus on the complete point clouds.With the development of scan devices, it is more convenient to obtain point cloud. But the data of real model, including huge missing data, are likely to lead to obtain incorrect skeleton, which will hinder further applications. Consequently, it is inevitable to find a robust algorithm which is able to extract skeleton from point cloud directly. In view of this, we propose a kind of skeleton extraction algorithm based on local spatial medial and graph reduction. Firstly, the algorithm simplify input data which contain much noise and extract spatial median by using local spatial median operator. These median points have been the final skeleton points for fine branch areas, but efficient points, having removed noise and discrete points, for connected region. Then we construct Octree directed graph for these efficient points and use a novel graph reduction method to reduce the Octree directed graph. The vertices of the graph are emerged into new ones during the reduction periods, which produce1D curve skeleton point sets. Eventually, the curve skeleton of original model will be acquired by connecting each point in fine branch and connected region.The proposed algorithm can directly extract efficient curve skeleton from point cloud, and what is more, it can greatly improve the robustness, reliability and applicability for extracting curve skeleton from point cloud model. It is proved that the proposed algorithm can get expected results by the experiment about various kinds of point cloud data and the comparison with other algorithms.