Research On 3D Point Cloud Data Compression Algorithm Based On Minimum Spanning Tree

With the great improvements in the speed and accuracy of 3D scanning system, the amount of point cloud is very large, making the calculation and storage of meshing point cloud data more difficult. Compared with mesh models, those point-based models have more obvious advantages, but the mass point cloud data still put a heavy burden on computer storage and transmission, so the compression of point cloud data plays a very important role in research and application. Many domestic and foreign scholars have had a deep research on point cloud data compression, and have achieved some great achievements. This paper puts forward some feasible ideas and methods on the basis of the achievements of the predecessors. The main idea is to improve the traditional minimum spanning tree algorithm for a better prediction, benefiting the subsequent processing of point cloud data, which achieves a good result. In this paper, the main work is as follows:Firstly, a fast lossy point cloud compression algorithm based on data type conversion is proposed. As different float have a different precision, this could cause the waste of precision. In order to solve the problem, a data type conversion rule called Ftol rule is designed relying on the fact that transforming the whole model into integer with the same precision can avoid precision waste. Then the difference of integer coordinates is encoded by arithmetic coding with local minimum spanning tree. Experiments show that this compression algorithm has a nice compression speed and compression rate without losing the quality of point-based model.For the fact that some projects require high quality point cloud, a lossless point cloud compression algorithm based on minimum spanning tree is proposed. The Improved traditional minimum spanning tree algorithm is not only based on the actual point cloud data, but also the corresponding predictive values generated when the tree structure is constructed. The predictive values will make a guiding difference on the minimum spanning tree, which makes the improved minimum spanning tree achieve a better prediction effect and a higher compression rate. Meanwhile, the calculation unit structure is established, which can benefit the search of the nearest point and improve the efficiency of algorithm. The experimental results show that this algorithm has a good performance in the compression speed and compression rate.In order to further ease the pressure of computer storage, a point cloud simplification algorithm based on minimum spanning tree is proposed. Firstly, the vector relation between father and son nodes is computed based on the structure of minimum spanning tree. Then, the nodes are classified according to the size of the angle, and the grades represent the importance of point cloud. Finally, the point cloud models are simplified according to the grades, and the maximum limit tree length is also set to prevent the simplified point cloud models from having big holes. Therefore, the combination of point cloud grades and the maximum limit tree length contributes to the final point cloud simplification algorithm. Experiments show that this algorithm can not only preserve the details of point cloud models, but also has better computation efficiency and a higher simplification rate.