Research On Skeleton Extraction From Point Clouds Via Graph Contraction

The skeleton of the 3D point cloud model,as a dimensionality reduction expression of 3D data,has been widely used in the fields of shape understanding,object recognition,movies,and 3D reconstruction.How to extract high-quality point cloud skeletons from 3D point cloud data has become a topic worth further research.However,point cloud models derived from the real world are extremely diverse,and some of them have complex branch structures.And due to the defects of technology and equipment,the extracted point cloud data always has problems such as noise and missing data.The complex branch structure,diverse point cloud types,and data defects make the study of3 D point cloud skeleton extraction extremely challenging.This thesis first introduces a novel contraction method called ?graph contraction?.While contracting the point cloud,graph contraction method can well reduce the impact of data defects.Moreover,the graph contraction method is not only robust to complex branch structures,but also can be widely used in various point cloud models.The main tasks are as follows:(1)In this thesis,a geodesic distance metric is proposed to search the nearest neighbor.Based on the characteristics of Riemannian manifold,the nearest neighbor graph is constructed on the point cloud,and the geodesic distance on the graph is obtained to approximate the Riemannian distance.In the subsequent graph contraction process,the clear boundaries between branches are kept.(2)The calculation formula of graph contraction is proposed.The formula is set as the minimum of an energy function.The computation of the graph contraction is formulated as the minimization of an energy function that consists of a contraction term that minimizes the sum of the graph geodesic distances of the 6)-nearest geodesic neighbors and a topology-preserving term that prevents point clouds from shrinking in the local principal direction.(3)A contraction strategy combining the geodesic distance and Euclidean distance is proposed.By switching to use different distance measurements to achieve the purpose of capturing a lot of geometric details in the early stage and accelerating the contraction in the later stage.Ultimately,the universality of the graph contraction algorithm can be guaranteed.(4)A skeleton point connection algorithm is proposed.The initial skeleton is divided into octrees and downsampled to get the final skeleton points.Then,the distance and main direction information are combined to calculate the confidence to connect the skeleton points to generate the final skeleton.(5)The data set of contrast experiment is designed.The data set includes not only the real-world point cloud data obtained by 3D laser scanning and multi-view stereo technology,but also the artificially generated tree point cloud data.These data,with various types and complex topological structures,can well verify the effect of the skeleton extraction algorithm.This thesis uses quantitative evaluation based on chamfer distance for the skeleton extraction results of point clouds with standard skeletons(Ground Truth),and uses visual evaluation for the skeleton extraction results of real-world point clouds without standard skeletons.In this way,the effectiveness of the algorithm is evaluated as scientifically and rigorously as possible.