随着三维立体相机设备和智能机器人在科学研究与现实生活中的广泛应用，三维点云数据已经成为计算机视觉中常见的数据格式，在机器人构建地图、导航、跟踪定位等方面发挥着重要的作用。机器人在复杂广阔的场景中构建地图时，如果单个机器人来完成此项任务会导致效率低下，此时需要多个机器人共同协作，将彼此的地图拼接、融合来提高效率。点云地图融合将不同视角、不同位置采集的点云地图通过刚体变换融合在一起，目前已经广泛应用于三维重建、智能导航、场景识别等领域，并且随着最近相关的商业产品的推出，使得该问题具有很强的现实意义。

本文对点云地图初始融合阶段和精确融合阶段进行了深入的研究与分析，提出了基于3D-SIFT关键点的特征提取初始融算法和多分辨率的点云近似最近点精确融合算法，主要工作如下：

首先，对于具有大量三维点的点云地图提取几何特征耗时过长，不能适应点云地图视角变化的问题，本文将二维图像中的SIFT扩展到三维点云地图中，在点云中构建尺度空间，通过尺度空间的分层相减构建高斯差分空间以此确定极值点，计算极值点邻域点的方位角和仰角从而确定关键点的方向，通过角度划分生成3D-SIFT关键点描述子。其次，针对FPFH特征提取算法中存在的权重系数溢出、统计区间不够精确导致特征匹配错误的问题提出了IPFH，采用指数函数的形式重新计算权重系数，把权重系数确定在合理的区间范围内，并对统计区间作进一步分割，从而提升特征匹配的精确度。然后，针对传统ICP精确融合算法时间消耗过高，效率低下，本文采用octree重采样的方法对点云地图进行不同程度的下采样，得到多个不同分辨率的点云地图，不同分辨率的点云地图采用不同的迭代次数，以此减少迭代过程中的时间消耗，并且将最近对应点的搜索范围缩小到重叠区域，利用邻近点代替最近点，通过优化改进，大幅度提高了原始ICP算法的效率。

最后，文中采用标准数据集、KINECT采集的实验室数据集对算法的各个阶段进行测试分析。从FPFH与IPFH、原始点云地图初始融合算法与基于3D-SIFT关键点的特征提取初始融算法、传统ICP算法与多分辨率的点云近似最近点精确融合算法这三个方面出发，在时间消耗、精确度两个方面进行对比，并对实验结果以图表的形式进行分析。实验结果表明，本文提出的算法相比于原始算法在效率、精确度等方面都有了很大幅度的提升，证明本文算法的有效性。

With the extensive application of 3D stereo equipment and intelligent robots in scientific research and real life, 3D point cloud data has become a common data format in computer vision. And it has played an significant role in map-building, tracking and navigation. When a robot is building a map in a wide range of scene or complicated indoor environment, if using a single robot to complete the task, the efficiency will be reduced. At this point, we need a number of robots to work together and align these maps. Point cloud fusion uses a rigid body transformation to fuse different maps obtained from different angles and different positions. Point cloud fusion has become a core work in 3D reconstruction, intelligent navigation, scene recognition and so on. Besides the relevant production makes map fusion full of commercial significance in real life.

 

Based on thoroughly analyzing the initial and accurate stage of point cloud map fusion, this paper proposed initial point cloud map fusion algorithm based on feature extraction on 3D-SIFT keypoints and multi-resolution point cloud approximation nearest point accurate fusion algorithm. The main work and achievements are as follows:

 

Firstly, in order to overcome the problem of the existing methods can not adapt to viewpoint change and cast much time extracting geometric features from point cloud map which is full of a large number of three-dimensional points, the paper extends the SIFT operator of 2D images to 3D point cloud maps. We construct scale space in point cloud and build difference of Gaussian space by subtracting adjacent layers in scale space. In difference of Gaussian space, extreme points can be computed. To determine the direction of keypoints, we calculate the azimuth and elevation of extreme points’ neighbors. The 3D-SIFT deor can be computed by angle division. Secondly, the FPFH feature extraction algorithm exists the problem of weight coefficients overflow and the statistic interval is not accurate enough which causes a lot of feature matching errors. So, we propose IPFH using the exponential function to re-calculate the weight coefficient and segmenting the statistical interval to improve the accuracy. What’s more, for the traditional ICP accurate fusion algorithm which has the problem of too high time consumption and low efficiency, we optimize the algorithm using the following strategies: we use the method based on octree to sample the point cloud under different degrees producing several point clouds with different resolutions. Different resolutions of point cloud maps use different iterations while processing And we also narrow search range to overlapping region. After that our method improves the efficiency of the original ICP algorithm greatly.

 

At last, we use standard dataset and point cloud dataset obtained by kinect from the scene of our lab to test our methods in different stage including the comparison of FPFH and IPFH, our initial map fusion method and the original, our accurate point cloud fusion method and traditional ICP. We evaluate the results using table and pictures. The experimental results show that the algorithm proposed in this paper has greatly improved the efficiency and accuracy compared with the original algorithm, which proves the effectiveness of the proposed algorithm. 

参考文献
[1] How google’s self-driving car works, IEEE Spectrum 18 (Online, October)(2011).
[2] Benavidez P, Jamshidi M. Mobile robot navigation and target tracking system[C]// System of Systems Engineering (SoSE), 2011 6th International Conference on. IEEE, 2011:299-304.
[3] Hosseinyalamdary S, Balazadegan Y, Toth C. Tracking 3D Moving Objects Based on GPS/IMU Navigation Solution, Laser Scanner Point Cloud and GIS Data[J]. ISPRS International Journal of Geo-Information, 2015, 4(3):1301-1316.
[4] Liang C, Song Y, Zhang Y. Hand gesture recognition using view projection from point cloud[C]// IEEE International Conference on Image Processing. IEEE, 2016:4413-4417.
[5] Schönauer C, Pintaric T, Kaufmann H, et al. Chronic pain rehabilitation with a serious game using multimodal input[C]// International Conference on Virtual Rehabilitation. IEEE, 2011:1-8.
[6] Bailey T, Durrant-Whyte H. Simultaneous localization and mapping (SLAM): Part II[J]. IEEE Robotics & Automation Magazine, 2006, 13(3): 108-117.
[7] Klasing K, Althoff D, Wollherr D, et al. Comparison of surface normal estimation methods for range sensing applications[C]// IEEE International Conference on Robotics and Automation, ICRA 2009, Kobe, Japan, May. DBLP, 2009:3206-3211.
[8] Liu M, Pomerleau F, Colas F, et al. Normal Estimation for Pointcloud using GPU based Sparse Tensor Voting[C]// IEEE Int. Conf. on Robotics and Biomimetics. IEEE, 2012:91-96.
[9] Daniel J, Lee and Mark E, Campbell. An Efficient Probabilistic Surface Normal Estimator[C]// IEEE International Conference on Robotics and Automation, ICRA 2016, Stockholm, Sweden, May 16-21,2016
[10] Sipiran I, Bustos B. Harris 3D: a robust extension of the Harris operator for interest point detection on 3D meshes[J]. The Visual Computer, 2011, 27(11):963.
[11] 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. IEEE, 2008:3384-3391.
[12] Rusu R B, Blodow N, Beetz M. Fast point feature histograms (FPFH) for 3D registration[C]// IEEE International Conference on Robotics and Automation. IEEE Press, 2009:1848-1853.
[13] Aiger D, Mitra N J, Cohen-Or D. 4-points congruent sets for robust pairwise surface registration[C]// ACM SIGGRAPH. ACM, 2008:85.
[14] Fischler M A, Bolles R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[M]// Readings in computer vision: issues, problems, principles, and paradigms. Morgan Kaufmann Publishers Inc. 1987.
[15] Chen Y, Medioni G. Object modeling by registration of multiple range images[C]// IEEE International Conference on Robotics and Automation, 1991. Proceedings. IEEE, 1991:145-155.
[16] Nurunnabi A, Belton D, West G. Robust Segmentation in Laser Scanning 3D Point Cloud Data[C]// International Conference on Digital Image Computing: Techniques and Applications. 2012:1-8.
[17] Lópezfernández L, Lagüela S, Picón I, et al. Large Scale Automatic Analysis and Classification of Roof Surfaces for the Installation of Solar Panels Using a Multi-Sensor Aerial Platform[J]. Remote Sensing, 2015, XL-5/W4(9):171-178.
[18] Ueno K, Katayama T. Incremental RANSAC for online relocation in large dynamic environments[C]// IEEE International Conference on Robotics and Automation. IEEE Xplore, 2015:68-75.
[19] Besl P J, Mckay N D. A method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1992, 14(2):239-256.
[20] Liu B, Guo J, Deng X. A point cloud registration method based on Octree and ICP[J]. Science of Surveying & Mapping, 2016.
[21] Chen Y, Medioni G. Object modeling by registration of multiple range images[C]// IEEE International Conference on Robotics and Automation, 1991. Proceedings. IEEE, 1991:145-155.
[22] Segal A, Hähnel D, Thrun S. Generalized-ICP[C]// DBLP, 2009.
[23] Romeil Sandhu S D A T. Point Set Registration via Particle Filtering and Stochastic Dynamics[J]. Pattern Analysis & Machine Intelligence IEEE Transactions on, 2010, 32(8):1459-1473.
[24] Donoso F A, Austin K J, Mcaree P R. How do ICP variants perform when used for scan matching terrain point clouds?[J]. Robotics & Autonomous Systems, 2016, 87:147-161.
[25] Zeisl B, Köser K, Pollefeys M. Automatic Registration of RGB-D Scans via Salient Directions[C]// IEEE International Conference on Computer Vision. IEEE, 2013:2808-2815
[26] Klasing K, Althoff D, Wollherr D, et al. Comparison of surface normal estimation methods for range sensing applications[C]// IEEE International Conference on Robotics and Automation, ICRA 2009, Kobe, Japan, May. DBLP, 2009:3206-3211.
[27] Jordan K, Mordohai P. A quantitative evaluation of surface normal estimation in point clouds[C]// Ieee/rsj International Conference on Intelligent Robots and Systems. IEEE, 2014:4220-4226.
[28] Holzer S, Rusu R B, Dixon M, et al. Adaptive neighborhood ion for real-time surface normal estimation from organized point cloud data using integral images[C]// Ieee/rsj International Conference on Intelligent Robots and Systems. IEEE, 2012:2684-2689.
[29] Lorusso A, Eggert D W, Fisher R B. A comparison of four algorithms for estimating 3-D rigid transformations[C]// British Conference on Machine Vision. BMVA Press, 1998:237-246.
[30] Lowe D G. Lowe, D.G.: Distinctive Image Features from Scale-Invariant Key-points. Int. J. Comput. Vision 60(2), 91-110[J]. International Journal of Computer Vision, 2004, 60(2).
[31] Muja M, Lowe D G. Scalable Nearest Neighbor Algorithms for High Dimensional Data[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2014, 36(11):2227.
[32] Sproull R F. Refinements to nearest-neighbor searching ink-dimensional trees[J]. Algorithmica, 1991, 6(1):579-589.
[33] Jia Y, Wang J, Zeng G, et al. Optimizing kd-trees for scalable visual deor indexing[C]// Computer Vision and Pattern Recognition. IEEE Xplore, 2010:3392-3399.
[34] Rusinkiewicz S, Levoy M. Efficient Variants of the ICP Algorithm[C]// International Conference on 3-D Digital Imaging and Modeling, 2001. Proceedings. IEEE, 2001:145-152.
[35] Chen Y, Medioni G. Object modeling by registration of multiple range images[C]// IEEE International Conference on Robotics and Automation, 1991. Proceedings. IEEE, 1991:145-155.
[36] Mitra N. Algorithms for Comparing and Analyzing 3D Geometry[J]. 2006.
[37] Yang J, Cao Z, Zhang Q. A fast and robust local deor for 3D point cloud registration[J]. Information Sciences, 2016, s 346–347:163-179.