近年来，随着激光扫描技术的日趋成熟，基于激光点云数据的三维数字化场景重构逐渐成为计算机视觉领域的研究热点。地面激光雷达可快速、精准地捕捉地理空间信息，已成为地形勘测和城市重建等应用的重要技术手段。然而，单个地面激光雷达存在仪器量程和视线遮挡等限制，三维场景重建往往需要通过获取多站激光扫描点云数据来实现。多站点云数据处理的关键步骤之一是将它们融合到同一坐标系，即点云配准问题。地面激光扫描点云数据存在数据量大，密度分布不均匀等特性，对自动配准的效率有较大影响。同时人造环境存在大量重复和对称结构，如建筑物、街道等，在配准时容易出现错位等配准失败情况。以上问题已经成为当前激光扫描在工程应用中的瓶颈。本研究针对上述存在的难点，做出如下研究：

(1)针对地面激光点云数据量大、密度不均而影响配准效率的问题，本文提出了基于体素网格的Harris点云关键点提取算法。对原始点云建立体素网格，均匀化点云密度；同时计算点云的关键点，以替代原始点云，从而降低计算量提高配准效率。本研究对原始点云数据建立体素网格，根据每个体素网格中点的分布情况，为体素网格赋予密度值，用体素网格作为计算点，使得计算数据分布均匀，可解决原始点云中的噪点与离群点的问题。在带有密度值网格计算点的基础上，本文基于二维Harris角点检测算法思想，针对点云数据改进新的角点响应函数，得到三维关键点。由于所求关键点是离散的，存在位置不够精确、质量欠佳等问题，本研究运用泰勒公式和高斯牛顿法，对关键点位置进行优化，提高关键点位置的精确性。通过实验数据的验证，本文关键点提取方法产生的关键点分布均匀，且时间开销是SIFT3D算法的48%~81%，Harris3D算法的28%~52%。

(2)针对场景中大量重复和对称结构导致配准失败的情况，本研究利用体素网格对经典Super4PCS算法改进。利用体素网格索引筛选Super4PCS算法中的四元基底，提高配准成功率。利用体素网格索引，对四元基底边上的十等分点进行查询，通过查询结果得到一个十维度编码，来判断此边是否存在于一个物体表平面上，通过四元基底上的多条边进行判断此基底是否在一个物体表平面上，如果此四元基底在一个物体表平面上就舍弃。通过对四元基底的约束筛选，过滤掉在同一物体表平面的四元基底(如墙面、地面等)，可减少候选集的数量，提高候选集质量，有效减少错位等配准失败情况，提高配准成功率和配准效率。此外利用体素网格索引替代原始KD树索引，提高Super4PCS算法中最大公共点集Largest Common Pointset (LCP)查询的效率。通过体素网格索引在随机点云中查询时间复杂度为 ，与时间复杂度为 的传统KD树索引查询相比，时间消耗降低50%~74%。在室内和室外不同数据集上验证，并与其他四点一致集方法比较分析，本文算法与经典Super4PCS算法相比，时间效率上提高70%以上，配准成功率提高8%以上。

Congruent Sets[J]. ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2013, 1(2): 283-288.

[15] Zhong Y. Intrinsic Shape Signatures: A Shape Descriptor for 3D Object Recognition[C]. IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops, 2009 : 689-696.

[16] Steder B, Rusu R B, Konolige K, et al. NARF: 3D Range Image Features for Object Recognition[C]. Workshop on Defining and Solving Realistic Perception Problems in Personal Robotics at the IEEE/RSJ Int Conf on Intelligent Robots and Systems (IROS), 2010 .

[17] Qi C R, Yi L, Su H, et al. PointNet++ Deep Hierarchical Feature Learning on Point Sets in a Metric Space[C]. Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017 : 5105-5114.

[18] Yew Z J, Lee G H. 3DFeat-Net: Weakly Supervised Local 3D Features for Point Cloud Registration[C]. Proceedings of the European Conference on Computer Vision (ECCV), 2018 : 607-623.

[19] Wu W, Zhang Y, Wang D, et al. SK-Net: Deep Learning on Point Cloud Via end-to-end Discovery of Spatial Keypoints[C]. Proceedings of the AAAI Conference on Artificial Intelligence, 2020 : 6422-6429.

[20] Rusu R B, Blodow N, Marton Z C, et al. Aligning Point Cloud Views Using Persistent Feature Histograms[C]. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2008 : 3384-3391.

[21] Rusu R B, Cousins S. 3D is here: Point Cloud Library (PCL)[C]. IEEE International Conference on Robotics & Automation, Shanghai, China , 2011: 9–13.

[22] Rusu R B, Holzbach A, Beetz M, et al. Detecting and segmenting objects for mobile manipulation[C]. IEEE 12th International Conference on Computer Vision Workshops 2009 : 47-54.

[23] Rusu R B, Bradski G, Thibaux R, et al. Fast 3d recognition and pose using the viewpoint feature histogram[C]. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2010 : 2155-2162.

[24] Aldoma A, Vincze M, Blodow N, et al. CAD-model recognition and 6DOF pose estimation using 3D cues[C]. IEEE International Conference on Computer Vision Workshops (ICCV workshops), 2011 : 585-592.

[25] Aldoma A, Tombari F, Rusu R B, et al. OUR-CVFH–oriented, unique and repeatable clustered viewpoint feature histogram for object recognition and 6DOF pose estimation[C]. Joint DAGM (German Association for Pattern Recognition) and OAGM Symposium, 2012 : 113-122.

[26] Frome A, Huber D, Kolluri R, et al. Recognizing objects in range data using regional point descriptors[C]. European Conference on Computer Vision. Springer, Berlin, Heidelberg, 2004 : 224-237.

[27] Marton Z C, Pangercic D, Rusu R B, et al. Hierarchical object geometric categorization and appearance classification for mobile manipulation[C]. 10th IEEE-RAS International Conference on Humanoid Robots, 2010 : 365-370.

[28] Grundmann M, Meier F, Essa I. 3D shape context and distance transform for action recognition[C]. 19th International Conference on Pattern Recognition, 2008 : 1-4.

[29] Tombari F, Salti S, Di Stefano L. Unique shape context for 3D data description[C]. Proceedings of the ACM Workshop on 3D Object Retrieval, 2010 : 57-62.

[30] Salti S, Tombari F, Di Stefano L. SHOT: Unique signatures of histograms for surface and texture description[J]. Computer Vision and Image Understanding, 2014, 125: 251-264.

[31] Bonato V, Marques E, Constantinides G A. A Parallel Hardware Architecture for Scale and Rotation Invariant Feature Detection[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2008, 18(12): 1703-1712.

[32] Dong Z, Yang B S, Liang F X, et al. Hierarchical registration of unordered TLS point clouds based on binary shape context descriptor[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2018, 144: 61-79.

[33] Dong Z, Yang B S, Liu Y, et al. A novel binary shape context for 3D local surface description[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2017, 130: 431-452.

[34] Besl P J, Mckay N D. A method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.

[35] Censi A. An ICP variant using a point-to-line metric[C]. IEEE International Conference on Robotics and Automation, 2008 : 19-25.

[36] Low K L. Linear least-squares optimization for point-to-plane icp surface registration[R]. University of North Carolina Chapel Hill, 2004.

[37] Gelfand N, Ikemoto L, Rusinkiewicz S, et al. Geometrically stable sampling for the ICP algorithm[C]. Fourth International Conference on 3-D Digital Imaging and Modeling, 2003 : 260-267.

[38] Segal A, Haehnel D, Thrun S. Generalized-ICP[C]. Robotics: Science and Systems, 2009 : 435.

[39] Mohammadzade H, Hatzinakos D. Iterative closest normal point for 3D face recognition[J]. IEEE Transactions on Software Engineering, 2012, 35(2): 381-397.

[40] 杨小青, 杨秋翔, 杨剑. 基于法向量改进的ICP算法[J]. 计算机工程与设计,2016, 37(01): 169-173.

[41] Halber M, Funkhouser T. Fine-to-coarse global registration of rgb-d scans[C]. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017 : 1755-1764.

[42] Granger S, Pennec X. Multi-scale EM-ICP: A fast and robust approach for surface registration[C]. European Conference on Computer Vision, 2002 : 418-432.

[43] Fitzgibbon A, Pilu M, Fisher R B. Direct least square fitting of ellipses[J]. IEEE Transactions on Pattern Analysis Machine Intelligence, 1999, 21(5): 476-480.

[44] Pottmann H, Huang Q X, Yang Y L, et al. Geometry and convergence analysis of algorithms for registration of 3D shapes[J]. International Journal of Computer Vision, 2006, 67(3): 277-296.

[45] Yang J, Li H, Jia Y. Go-icp: Solving 3d registration efficiently and globally optimally[C]. Proceedings of the IEEE International Conference on Computer Vision, 2013 : 1457-1464.

[46] Rusinkiewicz S. A Symmetric Objective Function for ICP[J]. ACM Transactions on Graphics, 2019, 38(4): 1-7.

[47] Fischler M A, Bolles R C. Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J]. Readings in Computer Vision 1987: 726-740.

[48] Chen C S, Hung Y P, Cheng J B. A Fast Automatic Method For Registration of Partially-Overlapping Range Images[C]. Sixth International Conference on Computer Vision (IEEE Cat No 98CH36271), 1998 : 242-248.

[49] Ambühl C, Chakraborty S, G?rtner B. Computing Largest Common Point Sets under Approximate Congruence[C]. European Symposium on Algorithms, 2000 : 52-64.

[50] Mellado N, Aiger D, Mitra N J. Super4PCS: Fast Global Pointcloud Registration via Smart Indexing[C]. Computer Graphics Forum, 2014 : 205-215.

[51] Mohamad M, Rappaport D, Greenspan M. Generalized 4-points Congruent Sets for 3D Registration[C]. 2nd International Conference on 3D Vision, 2014 : 83-90.

[52] Mohamad M, Ahmed M T, Rappaport D, et al. Super Generalized 4PCS for 3D Registration[C]. International Conference on 3D Vision, 2015 : 598-606.

[53] Huang J, Kwok T H, Zhou C. V4PCS: Volumetric 4PCS Algorithm for Global Registration[J]. Journal of Mechanical Design, 2017, 139(11).

[54] Zhang R, Li H, Liu L, et al. A G-Super4PCS Registration Method for Photogrammetric and TLS Data in Geology[J]. ISPRS International Journal of Geo-Information, 2017, 6(5): 129.

[55] Theiler P W, Wegner J D, Schindler K, et al. Keypoint-based 4-Points Congruent Sets–Automated Marker-less Registration of Laser Scans[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 96: 149-163.

[56] Theiler P W, Wegner J D, Schindler K. Fast Registration of Laser Scans with 4-Points Congruent Sets-What Works and What Doesn't[J]. ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2014, 2: 149-156.

[57] Ge X. Automatic Markerless Registration of Point Clouds with Semantic-Keypoint-Based 4-Points Congruent Sets[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2017, 130(aug.): 344-357.

[58] Xu Z, Xu E, Zhang Z, et al. Multiscale Sparse Features Embedded 4-Points Congruent Sets for Global Registration of TLS Point Clouds[J]. IEEE Geoscience and Remote Sensing Letters, 2018, 16(2): 286-290.

[59] Lu J, Wang W, Shao H, et al. Point Cloud Registration Algorithm Fusing of Super4PCS and ICP Based on the Key Points[C]. Chinese Control Conference, 2019.

[60] Xu Y, Boerner R, Yao W, et al. Pairwise Coarse Registration of Point Clouds in Urban Scenes Using Voxel-Based 4-Planes Congruent Sets [J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2019, 151: 106-123.

[61] Bueno M, Bosche F, Gonzalez-Jorge H, et al. 4-Plane Congruent Sets for Automatic Registration of as-is 3D Point Clouds with 3D BIM Models[J]. Automation in Construction, 2018, 89(MAY): 120-134.

[62] 张立亭，黄晓浪， 鹿琳琳，等 相似像素的Harris角点检测改进算法[J] 测绘科学. 2019, 44(07): 111-115.

[63] 陈全. 基于激光雷达的三维地面目标检测与识别方法研究[D]. 武汉: 华中科技大学, 2019.

[64] Hunter G M. Efficient Computation and Data Structures for Graphics[D]. Princeton, New Jersey: Princeton University Electrical Engineering Computer Science Department, 1978.

[65] 李强. 基于多约束八叉树和多重特征的点云配准算法[D]. 太原: 太原理工大学, 2019.

[66] Kanopoulos, N, Vasanthavada, et al. Design of an Image Edge Detection Filter using The Sobel Operator[J]. Solid-State Circuits, IEEE Journal of Solid-State Circuits, 1988, 23(2): 358-367. .

[67] Girardeau-Montaut, Daniel. CloudCompare-Open Source project[CP]. [2016-08-01]. http://www.cloudcompare.org/ .

[68] Dong Z, Liang F, Yang B, et al. Registration of Large-Scale Terrestrial Laser Scanner Point Clouds: A Review and Benchmark [J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2020, 163: 327-342.

[69] 邵红旭. 低重叠率点云配准技术研究[D]. 哈尔滨: 哈尔滨工程大学, 2018.