A Stepwise Minimum Spanning Tree Matching Method For Registering Vehicle-borne And Backpack LiDAR Point Clouds Data

The effective perception of urban three-dimensional space is the key content of digital twin city informatization,and has important significance for the promotion of realistic three-dimensional China.Light Detection and Ranging(LiDAR)is currently one of the mainstream technologies for rapidly and accurately obtaining threedimensional(3D)urban spatial information on a large scale.There are many laser scanning systems,backpack and vehicle-borne mobile laser scanning platform are two emerging mobile point cloud data acquisition devices used to obtain detailed 3D spatial information near-ground in urban environments.Vehicle-borne laser scanning systems are commonly used to obtain three-dimensional point cloud data of ground objects on both side of the road,with the collected data under GPS global coordinate system;The backpack laser scanning system is more flexible and can be used to supplement data in areas where the vehicle-borne laser scanning system cannot reach,typically obtaining point cloud data under a local coordinate system.Therefore,fusing the backpack and vehicle-borne point cloud data of different coordinate systems can provide a more complete 3D description of the urban environment.Due to the complexity of urban street environment and the difference in data acquisition methods,traditional point-to-point registration methods are usually inefficient and difficult to determine the same name points.Therefore,this study proposed a stepwise minimum spanning tree matching algorithm based on the spatial topological relationship between tree locations to achieve automatic registration of vehicle-borne and backpack point cloud data in urban street environments.The main research contents and methods are as follows:1.A point cloud registration algorithm based on stepwise minimum spanning tree matching is proposed in this article.The algorithm mainly includes three key steps:(1)trunk centers extraction: the trunk center is treated as the tree location in this paper,the tree location information is obtained by extracting a point cloud slice 1.2-1.4meters above the ground,and then implement density clustering and circle fitting methods.(2)stepwise minimum spanning tree matching: a stepwise matching method is used to find one-to-one correspondences of tree positions based on the distance and angle similarity between tree positions as well as spatial connectivity.(3)transformation estimation: the 3D rigid body transformation matrix is calculated based on the matching relationship between tree positions to achieve registration of point cloud data.2.Based on the stepwise minimum spanning tree matching algorithm,the registration of backpack and vehicle-borne point cloud data in urban street environment is realized.A total of five research areas with different complexity in Minhang district of Shanghai were selected for the experiment,and the registration of backpack and vehicle-borne point cloud in the five sites achieved good results.The average rotation error of the five sites is less than 0.06 °,and the average translation error is less than 0.05 m.In addition,the average residuals between the matching points of the five sites are 0.112 m,0.144 m,0.176 m,0.148 m and 0.184 m.3.The stepwise minimum spanning tree matching algorithm is comprehensively compared and analyzed.It is compared with the TIN matching based registration method and the deep learning based PointNetLK method.The results show that our method is better than the two comparison methods in registration accuracy.In terms of registration efficiency,our method does not need individual tree segmentation and fine registration process,nor does it need data de-sampling and initial position normalization,which shows a higher registration efficiency.Finally,the influence of parameter setting,tree trunk occlusion and noise points on the node matching results are analyzed respectively.The results show that the proposed stepwise minimum spanning tree matching algorithm achieves good performance both in accuracy and efficiency.The algorithm constructs a minimum spanning tree based on the relative position and spatial topological relationship between trees,converts the selection of same name points into a minimum spanning tree matching problem,and uses a stepwise matching strategy to extract complete same name point pairs,greatly improving the matching efficiency and accuracy.In addition,the algorithm only needs to use tree location information for registration,without other additional auxiliary information,and the extraction of tree location does not rely on the individual tree segmentation process.In summary,the method proposed in this study exhibits good potential in multiplatform point clouds registration,and can provide technical support for many urban applications that need to obtain accurate and comprehensive three-dimensional spatial data.