Research On Point Cloud Data Processing Based On K Nearest Neighbor

Terrestrial Laser Scanner(TLS) is a new kind of technology to get surveying and mapping data, which can rapidly obtain high density and high-accuracy point cloud data from surface information of objects. And it has been widely used in reverse engineering, cultural relic protection, digital city, deformation monitoring and some other fields. But there is no topological information in the point cloud acquired by TLS in most time. And the spatial relationship among points need to be constucted by K nearest neighbours, and many followed work is based on K nearest neighbours, the main tasks of this paper are listed as follow:In the first chapter, the paper introduces state-of-the-art of TLS technology, including some main kind of laser scanners in the market and their operating principles, then generalizes the current situation of K nearest neighbours searching, researching progress which based on intensity of point cloud, the key points and difficulties of normal estimation and orienting, and the current situation of point cloud registration.In the second chapter, the paper analyses two kind of K nearest neighbours, introduces the necessity for building the spatial index of scatter point cloud data, elaborates spatial partition algorithm and K-d tree searching algorithm and analyses their advantages and disadvantages. Then the K-d tree searching algorithm has been determined to seek K nearest neighbours in point cloud. And an experiment has been designed to verify the validity of K-d tree searching algorithm.In the third chapter, the paper studies the defination of intensity and the major applying fields of intensity in current, analyses the mearsure error of pulsed surveying principle. And studies the influence of intensity for mearsure error from optics theory. Using K nearest neighbours to caculate local outlier factor, which is based on surface variation, local outlier factor reflects the distances between each point and main body of point cloud. Local outlier factor can be used to caculate mearsure error quantitatively. At last an experiment has been designed to disscuss the connection between intensity and measure. The experiment shows that the smaller the itensity the larger mearsure error of a kind of point cloud.In the fourth chapter, the paper introduces normal estimation algorithms based on Voroni diagram and local plane fitting, and studies how to handle the noise and outlier, choose reasonable K nearest neighbours, estimate normal in sharp feature robustly. At the end, some commonly used algorithms of normal orienting have been analysed, and verifies the necessity to orient normal direction.In the fifth chapter, the paper presents the method of point cloud registration and how to caculate transformation matrix, studies the methods of extracting matching point based on target and geometrical characteristic. And proposes a new algorithm to extract accurate matching point based on curvature information. And the experiment showed is reasonable.