摘 要

三维点云的匹配技术是三维模型重建的基础，在很多领域都有应用，随着三维扫描技术的逐渐进步，得到三维点云变得越来越容易，由于对物体进行扫描的同时，相应的灯光的亮暗，拍摄的角度，拍摄的精度等都会对扫描的点云产生影响，因此，在扫描时，通常多角度的对一个三维物体进行扫描，通过匹配，复原三维物体。正是由于三维点云的匹配技术的重要性和复杂性，越来越多的学者投入到三维点云算法的研究中，近十年来相应的匹配算法也随之得到了快速的发展。

点云匹配是通过坐标变换和刚体平移把相同物体的点云进行匹配，并且可以得出相应的变换矩阵,并得到三维点云的完整信息，还原三维物体。点云匹配的算法有很多，根据有无特征可以分为基于特征点提取的三维点云匹配算法和无特征点的三维点云匹配算法。

目前，使用最为普遍的算法就是ICP(Iterative Closest Point)算法,它是一种迭代最近点算法，但是它存在两个问题，一个问题是当使用欧式距离进行最近点匹配的时候，容易出现错配的情况，影响匹配的精度；另一方面，由于算法是基于迭代的方式，来更新点云的位置，因而计算量会比较大。本文针对ICP算法存在的第二个问题，通过探究一种新的基于奇异值分解的算法，来帮助减小计算量。

本文详细介绍了点云的基本概念，点云匹配算法的相关理论，ICP算法的证明并提出了一种新的用于点云匹配的ICP算法，新的算法可以在很短的时间内对相似的点云进行匹配，并且精确性并不比原算法低，最后，本文把算法用于图像补齐的相关研究中，并取得了不错的效果。

关键词：奇异值；ICP；点云匹配；三维点云；PCL(Point Cloud Library)

Abstract

The matching technology of 3D point cloud is the foundation of 3D model reconstruction, and it is applied in many fields.With the gradual improvement of the 3D scanning technology, it is becoming more and more easy to get the three dimensional point cloud.With the object is scanned, the corresponding light's brightness, the angle of the shot and the accuracy of the shooting will affect the scanning point cloud.Therefore, during scanning, a 3D object is usually scanned by multiple angles, and the object is restored by matching.Because of the importance and complexity of 3D point cloud matching technology, more and more scholars have put into the research of 3D point cloud algorithm, and the corresponding matching algorithms have also developed rapidly in the last ten years.

The point cloud matching is to match the point cloud of the same object through coordinate transformation and rigid body translation, and the transformation matrix can be gotten.Using matching algorithm,the complete information of the three dimensional point cloud is obtained, and the 3D object is reduced.There are many algorithms for point cloud matching, which can be divided into three dimensional point cloud matching algorithm and 3D point cloud matching algorithm without feature points based on feature point extraction.

At present, the most widely used algorithm is the ICP (Iterative Closest Point) algorithm. It is an iterative nearest point algorithm, but it has two problems. One problem is that when the Euclidean distance is used to match the nearest point, it is easy to mismatch and affect the accuracy of matching.On the other hand, because the algorithm is based on iterative way to update the location of the point cloud, the computation will be relatively large.Aiming at the second problems of ICP algorithm, a matching algorithm of 3D point cloud based on singular value decomposition is explored to help reduce reduce computational cost.

This paper introduces the basic concept of point cloud, the related theory of point cloud matching algorithm, the proof of the ICP algorithm and a new ICP algorithm for point cloud matching. The new algorithm can match the similar point clouds in a very short time, and the accuracy is not lower than the original algorithm.Finally, the algorithm is applied to the research of image completion and achieves good results.

Key Words：singular value;ICP;3D point cloud matching; PCL

目 录

第1章 绪论 1

1.1 课题的研究背景及意义 1

1.2 国内外研究的现状 1

1.3 研究的基本内容，各章节结构布置 2

1.4 小结 3

第2章 三维点云的匹配技术 4

2.1 点云概念及匹配原因 4

2.2 点云匹配的理论基础 4

2.2.1 刚体变换矩阵 4

2.2.2 点云匹配的目标函数 7

2.2.3 奇异值分解算法 8

2.3 传统的ICP点云匹配算法 9

2.4 基于k-d tree的最近邻域搜索算法 10

2.5 基于奇异值分解的新算法 12

2.6 小结 13

第3章 PCL库介绍以及ICP算法的实现 16

3.1 PCL库简介 16

3.2 PCL库安装与环境配置 16

3.3 PCL编程规范 17

3.4 传统ICP算法与新ICP算法实现 19

3.5 算法的比较 21

3.6 算法在实际生活中的应用 25

第4章 总结与展望 28

4.1 总结 28

4.2 展望 28

致谢 29

参考文献 30

第1章 绪论

1.1 课题研究的背景及意义

随着计算机的发展和三维技术图形技术的提高，物体在扫描并转换后，能够利用计算机对物体的三维特征进行存储，并转化为点云。现实生活中，可以通过接触式测量，如用接触性探针采集物体的一些区域，把物体转化为三维点云^[1]。但是在扫描和拍摄的过程中，使用的摄像头的位置不同，角度不同，所得到的同一物体的点云集合也不同，如何判断点云是否属于同一个物体，是近年来研究的课题之一。

目前，点云数据由于其独特的优势，应用的领域越来越广泛，在医疗领域，文物修复领域，建筑学领域均有的应用。在通过激光扫描或者其他方式获得点云的过程中，可能由于被测物体尺寸过大，表面被遮挡，扫描角度和光照范围等因素的影响，三维点云之间存在一定的平移和旋转误差^[2]，而点云的匹配是解决这种问题的一个有效途径，目前，解决点云匹配最广泛使用的算法为ICP(the Iterative Closest Point Algorithm)算法，然而随着点云中点的数量的增多，传统的ICP算法计算量比较大，因而本文通过探究一种基于奇异值分解的三维点云ICP匹配算法来减少计算量，从而更好的适应于大量点云的匹配问题。

1.2 国内外的研究现状

近年来，学者对点集的匹配进行了多次而又详细的研究，1987年，Horn，Arun运用四元数法对点集与点集进行匹配得出了最初的点集和点集的匹配算法(PSTPS)^[3]，通过实践证明，这种方法比较高效，1992年，ICP算法被提出^[4]，它利用最小二乘法的思想，通过多次迭代就能获得较好的刚体变换，进而对点云进行匹配。这种方法可以满足当时的需求，并且通过实践证明这种方法应用起来效果很好，因此成为了点云匹配的主流算法，但是ICP算法也存在不足。一方面，如果初始值选取的不够好，对收敛的精度和时间都有一定的影响;另一方面，由于ICP利用了迭代的思想，因而其运算量会比较大，因此需要通过某些方式减小计算量。ICP经过十多年的发展，针对上述的各种问题，多种优化方法相继被提出，例如有些学者结合了一些其他算法，如Granger等人在2002年提出了与EM算法结合的EM-ICP算法^[5]，随后，Dewaele等^[6]人将此算法应用于实践，证明了此算法的健壮性；在20世纪初，随着智能算法的提出，模拟退火算法和蚁群算法^[22]也被应用在ICP算法之中^[7]，同时因为ICP 算法很大程度上依赖于输入的初始值，研究人员提出了精确匹配前进行点云的粗略配准^[11],如基于投票策略的RANSAC^[12]算法,此类算法首先通过计算改变位置姿态，再使用ICP算法进行精准匹配。

国内高校如北京大学重离子物理研究所，华中科技大学图像识别与人工智能实验室也对三维点云进行了详细的研究并取得了一定的成果^[11]。

总而言之，三维图形的匹配已经被越来越广泛的应用于日常生活中，改变着人们的生活，因而越来越多的研究人员关注这个领域，但至今还没有出现一种普适的算法，能够从精确度和运算量上交一个满意的答卷。本文针对ICP算法进行了一些改进，利用矩阵论的知识，通过奇异值分解来降低运算量。

1.3 研究的基本内容，各章节结构布置

本文通过分析三维点云的特征，利用PCL库函数，编写C 程序来对点云进行匹配，本文首先综述了ICP算法的发展以及ICP算法的原理，探究并得出基于奇异值分解的ICP匹配算法的算法流程图，并以此为基础编写出相应的算法并且进行点云匹配，之后，改进原算法，得出新的奇异值分解的算法，减小计算量。

本文的研究思路见图1.1。

本文分为几个部分：

第一章介绍本文的选题以及研究背景和意义，以及国内外研究的现状。

第二章深入介绍点云的概念，给出了ICP算法的原理以及其证明，探究如何通过奇异值分解来减少计算代价，并给出算法模型。

第三章深入介绍如何实现上述相应的ICP算法，介绍PCL的一些知识，对算法进行实践并对算法进行改进。

第四章总结了本文的工作并给出展望。

图1.1 本文整体框架

1.4 小结

本章主要阐述了ICP算法研究的目的和意义，国内外的研究现状以及本文的组织结构，提出了本文的研究思路以及每一章节所涉及的内容， 阅读本章能够比较好的认识到ICP算法的发展现状以及研究趋势，从而能够获得本文的研究框架以及点云配准算法的发展。

第2章 三维点云的匹配技术

2.1 点云的概念及匹配原因

点云是人们使用各种扫描设备扫描获取到的离散的点的集合，它包含了物体的形状，物体的颜色，物体的大小以及几何坐标，一般地，点云可以分为三类^[14]：

散乱点云：点云没有明显的几何分布特征，呈现为无序的状态^[34]。主要由一些仪器随机扫描获得。

网格化点云：此类点云上的每个点均存在一个网格点与之对应，点云整体分布呈现出网格化形式。

扫描线点云：这种点云中的点形成一组组扫描线，且这些点都在扫描平面内部，因而这种点云被称为扫描线点云。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：