The Research Of Point Cloud Data Registration Technique Based On Kd-tree Acceleration

In recent years, with the continuous development of science and technology, the questions of how to virtually reproduce the real world efficiently and establish the three-dimensional model for the real objects have a great significance on the establishment of a digital and visual community. The related technology has also become the hotspot in the study of scholars around the world.Three-dimensional laser scanning technology plays an important role in the three-dimensional reconstruction. In the fields such as reverse engineering and industrial measurement, three-dimensional information of the object can be acquired fast through three-dimensional laser scanning technology. The relevant technical processing can reproduce the three-dimensional model of the object, which describes its properties clearly and lays the foundation for further research and use of the measured object. The technology is mainly concentrated on the data pre-processing and data registration.At present, different kinds of data pre-processing technology has developed very mature, but how to improve the speed and accuracy of data registration is still a hotspot in the aspect of registration techniques.A large number of the three-dimensional data of the objects can be obtained through the three-dimensional scanning technology. As a result, the distribution of these point cloud data is irregular. Effective organization and management of these scattered data can improve the search efficiency of data. The kd-tree is a new hotspot among numerous study of data organization. The kd-tree is similar to the general tree structure and it can store, manage and search data efficiently. The difference between them is that the kd-tree is more suitable for the scattered point cloud data. Therefore, in the field of point cloud data obtained by the three-dimensional scanning technology, the application of data organization based on kd-tree becomes more and more wide. Massive point cloud data has brought a great number of troubles to the data registration method, such as the slow registration and low registration accuracy. According to the problems encountered in the point cloud data organization and management, this thesis mainly studies how to improve the search efficiency and the registration speed by organizing and managing data.Firstly, the point cloud data can be obtained through the three-dimensional laser scanner technology. Comparing with other three-dimensional data, we find the problems existed in the data organization methods currently are used to manage the scattered point cloud data. The thesis also proposes the use of kd-tree structure to organize and manage the point cloud data.Then the thesis explores the organization and management methods and the use of kd-tree to do the query, insert and delete operations of point cloud data. It also studies the advantages of kd-tree organization especially on the point cloud neighborhood search. The experiments show that using kd-tree to store and manage point cloud data can not only organize the scattered data effectively, but also improve the efficiency of data search.Finally, the thesis introduces the basic knowledge of the three-dimensional data registration. It also analyzes the data registration mechanism of the traditional ICP registration algorithm and points out the problems of the ICP algorithm on the massive point cloud data registration. Combining kd-tree for the data organization and management algorithms with the traditional ICP data registration algorithm, instead of the traditional ICP algorithm, the ICP algorithm can be improved based on the advantages of iterative search process for the point cloud data by using kd-tree structure. The simulation results show that accelerated ICP algorithm improves the speed and accuracy of registration, which makes the algorithm application stronger. In the last part, the thesis designs the system of the point cloud data registration to obtain point cloud data through the three-dimensional laser scanner used in this thesis. The registration results are similar to the simulation experiments.