Research On Skeleton Extraction From Tree Point Clouds Via K-nearest-neighbors-based Contraction

The point cloud is a set of scattered points which are obtained by sampling on the object surface,usually used for the surface reconstruction of 3d models.For objects with a large number of small branches,like trees,traditional reconstruction method do not work well.A common practice is to first extract the curve skeleton of the tree point cloud,then reconstruct the meth model under the assistance of the skeleton.In addition to assisting reconstruction,the curve skeleton can also be used to generate skeleton animation,analyze the topology of model,etc.Therefore,extracting curve skeleton of point cloud is of great value for research.The challenges in extracting curve skeleton mainly exist in: The raw point clouds have the noise data;the point clouds usually have missing data due to the occlusion effects;the point clouds have the non-uniform density.These problems make it difficult to extract the topological information of point clouds.To solve these challenges,this thesis does the following work:(1)In order to reduce the impact of point cloud noise and non-uniform density on skeleton extraction,a data preprocessing scheme is designed,which first downsamples the point cloud via a grid structure,and then uses the weighted local optimal projection algorithm to resample the point cloud.(2)This method proposes a tree skeleton extraction algorithm that uses the k-nearest-neighbors-based contraction.The algorithm first converts the point cloud into a skeletal point cloud via an iterative k-nearest-neighbors-based contraction,and enhances the robustness to the non-uniform point distribution via an anisotropic weighting of the point displacement at each iteration.The algorithm then extracts graph-structured skeleton branches via farthest point sampling in fixed-size neighborhood,extracts the bifurcation points by using DBSCAN algorithm on the branching region of point clouds,and finally connect the skeleton branches to the bifurcation point to get the skeleton.(3)Considering the missing data caused by the occlusion effects,a skeleton repair algorithm is proposed.The algorithm considers the Euclidean distance between skeleton nodes,the branching angle and the ratio of length of branches,repairs the missing part of the skeleton,to ensure that the skeleton is a connected graph.(4)A post-processing scheme for the curve skeleton is proposed,which uses ellipse-fitting technique to improve the centeredness of skeleton points and uses Cardinal spline interpolation to enhance the smoothness.(5)This thesis devises experiments for quantitative evaluations,which evaluates the accuracy of the algorithm by comparing three distance measurements of the curve skeletons,and evaluates the effectiveness of the algorithm by comparing the mean distance of the mesh models which are reconstructed under the guidance of the extracted curve skeletons.The experimental results show that the proposed algorithm can effectively extract topology-preserving,well-centered curve skeletons from the real tree point clouds,and can effectively assist the reconstruction of trees.