Large-scale Point-clouds Data Organization And Management Method Based On Octree,Hilbert Curve And R-tree

The three-Dimensional Laser Scanning Technology which widely use in many fields such as mapping, traffic and film, rise in the 90 years of 20 century. along with the improving of the hardware-updating, The Management and analysis algorithm of LiDAR(Light Detection And Ranging) data mature increasingly. But the high density characteristics of point cloud has been the important bottleneck for its popularization. So an efficient index method and excellent sampling strategy for large scale point cloud is badly needed.For the management of large scale 3D laser Scanning point cloud, this paper propose an R-tree Index which called 3DOHR-tree based on octree and Hilbert curve,and come up with a sampling method based on Gaussian kernel Density estimation.To build the 3DOHR-tree index, First of all, Divide points into leaf nodes which has the same scale using octree for each sampling file. Then, sort those nodes in one-dimensional by space filling line(Hilbert curve), Finally, each leaf node as a R-tree leaf, build the one level R-tree index structure button-top, each one level R-tree root node as a leaf node of the two level R-tree leaf and Build it top-button dynamically.After the 3DOHR-tree completed, based on hierarchy features of R-tree, Sampling the points in child node as the parent node's points by the method based on Gaussian Kernel Density Estimation recursively. The sampling process as follows: 1) build the construction of the point cloud by the minimum spanning tree; 2) calculate the geodesic distance between any two points in the point cloud; 3) estimate the point density value by Gaussian Kernel Function with geodesic distance; 4) Get the weight between any two points by point density value; 5) according to the weight, calculate point feature vector;6) define invariant function and calculate point invariant with point feature vector; 7)sampling the point cloud with point invariant according to the size of preset threshold,and choose the points which has larger invariant.Experiment shows that the 3DOHR-tree not only show better time efficiency on the index creation, but also has good performance on query efficiency, the sampling method based on Gaussian Kernel Density Estimation can reserve the characteristic information better. The method for large-scale point-clouds' application this paper put forward has practical guiding significance.