摘 要

三维点云作为一种三维图像表达方式，在很多领域中都有着十分重要的作用，而三维点云中关键点的提取又是其中最基本最底层的功能。关键点代表的是三维图像中信息量最大最具有特征代表性的点，后续的图像处理可以只通过处理关键点来实现整体图像的处理，提高了处理的效率与准确性。而本次我们研究并实现了利用法向量直方图在三维点云上提取关键点的算法（HoNO，Histogram of Normal Orientation）：该算法的原理是求出点云中点的法向量并计算它们的夹角，并建成新的法向量直方图，通过设立阈值来过滤掉平坦区域的点留下显著区域的点，再通过边界移除步骤与裁剪步骤去除不稳定的点生成独特的关键点。我们不仅通过分析数据来检验该算法的特性，考虑它可能的优缺点，还将该算法应用在点云配准上验证其可行性与正确性。

关键词：PCL，三维点云，关键点，法向量直方图

Abstract

3D Point Cloud is an alternative expression of 3D image, it plays crucial role in a variety of fields, and the extraction of 3D point cloud keypoints is the most fundamental and bottom function. The keypoints contains the most informative and characteristic representative points in the 3D image, subsequent image processing can work effectively and accurately due to the keypoints. This time we actualized a HoNO(Histogram of Normal Orientation) algorithm to extract the keypoints from 3D Point Cloud and we did a research on that algorithm. The principle of the algorithm is to compute the normals of the points in 3D Point Cloud and their angles,we build new Histogram of Normal Orientation, setting threshold to filter the points from plain field and leave the points from salient fields, using boundary removal step and pruning step to wipe off the unsteady points and create unique keypoints. We not only analyzed the data to test the feature of algorithm and consider it’s potential advantages or disadvantages, we also apply it on pointcloud registration to test it’s availability and validity.

Key Words：PCL,3D Point Cloud, Keypoint, Histogram of Normal Orientation

目 录

第1章 绪论 1

1.1 引言 1

1.2 研究目的背景及意义 1

1.3 国内外研究现状 2

1.4课题研究内容与目标 3

第2章 背景知识 4

2.1 PCL库 4

2.1.1 PCL概述 4

2.1.2 PCL功能 4

2.1.3 PCL的应用 5

2.1.4 PCL库的文件格式 6

2.1.5 PCL库的数据结构 7

2.2 临近搜索 7

2.2.1 树状结构 7

2.2.2 二叉查找树 8

2.2.3 Kdtree 9

2.2.4 基于Kdtree的临近搜索 12

2.3 点云法向量估计 12

2.3.1 主成分分析法 13

2.3.2 最小二乘法 15

第3章 HoNO算法 17

3.1 算法原理 17

3.2 伪代码 20

3.3 方案图 21

3.4 具体实现步骤 22

3.4.1 点云预处理 22

3.4.2 法向量计算 24

3.4.3 显著点筛选 25

3.4.4 边界点移除 27

3.4.5 裁剪操作 27

3.5 效果与评价 28

第4章 点云配准 31

4.1计算特征描述子 31

4.2 建立联系 32

4.3 对应分组 32

4.3.1 几何一致性分组 33

4.3.2 霍夫投票分组 33

4.4 配准效果 34

第5章 研究与分析 40

第6章 结论 42

致谢 43

参考文献 44

第1章 绪论

1.1 引言

在目前研究得正火热的人工智能中，机器视觉是快速发展的一个方向。机器视觉的本质就是用机器代替人眼进行测量与判断，通过图像摄取装置将被摄取目标转换为图像目标，传送给专门的图像处理系统，得到被摄目标的形态信息，根据像素分布和亮度、颜色等信息，转变成数字化信号;图像系统对这些信号进行各种运算来抽取目标的特征，进而根据判别的结果来控制现场的设备动作^[1]。

通过研究机器视觉，我们可以实现许多人工观测实现不了的功能：

·机器视觉具有准确性与客观性，对于任一的观测对象，机器能够准确地反映被观测对象的特征，而不会因为观测人员的经验、身体状态等主观因素影响到观测结果。

·机器视觉能够在高重复性的环境下稳健工作，而人可能会因为大量的重复而产生疲倦的感受而影响观测结果。

·机器视觉能够更快的检测物体，提高了检测的效率，特别是当观测物体处于高速运动的过程中时，机器视觉能准确快速地将被观测物体的关键信息提取出来。

·将机器视觉应用于生产生活中可以降低成本，一台检测仪器可以完成多个人员的检测工作，而且机器能够连续工作，不会因为主观的原因而停顿。

而在过去的几十年间，2D的物体识别被广泛的研究，已经成为了一个较为成熟的领域，但随着近些年来计算机硬件的不断增强与软件技术的不断发展，对于3D数据的处理能力也与日俱增。由于3D数据相比2D具有更多的优点，3D点云在物体识别领域也展现出了一些优势：

1、3D数据提供了比2D数据更多的几何信息（深度）。

2、从点云中提取到的特征不会受到尺度、旋转、光照的影响。

3、3D点云在估计物体姿态方面比2D更加准确。

1.2 研究目的背景及意义

作为一个新兴的领域，3D点云图像识别具有非常好的前景，但目前这个领域的研究并不十分成熟。例如，如何精准高效地探测出3D点云数据的信息与特征的问题依然没有完全解决，国内外很多研究者们给出了他们自己的解决方案，提出了很多理论与思路。本文立足于利用“法向量直方图来探测三维点云数据中的关键点”这一思路编写出一套算法系统，通过对实例的处理来验证该算法思路的正确性与可行性，并且将此系统应用于实际，为这个领域的发展做了一份小小的贡献，这是非常具有意义的。

1.3 国内外研究现状

迄今为止，国内外的许多研究人员提出并实现了多个三维点云中关键点提取的算法，常用的关键点算法有以下几种：

HKS（热核特征/Heat Kernel Signature）：HKS热核特征是一种特征描述子，它被用来分析三维形状形变，因为一个三维的图像上面点的分布是不一样的，每个点所在位置的特性也不一样。HKS利用了这个不一样的特性，对三维模型进行热量计算，通过对每个点施加相同的热量，再在一段时间后获取每个点剩余的热量，由于实际中三维物体的热量损失不一样，通过模拟获取的三维物体模型上得到的热量损失也不一样，将热量扩散损失的过程记录下来，将这个热量下降的曲线离散化，就可以获得这个点的热核特征。设立特定的过滤方式就可以获得想获取的热核特征关键点了。

3DHarris：Harris算子在2D图像处理中是通过在图像中设立一个窗，通过移动窗来获取灰度变化，平坦的位置灰度变化不大，边缘位置只有在边缘位置方向移动才会有灰度变化，而关键点位置的窗无论什么方向移动灰度变化都很剧烈。而在三维图像中我们很难获取灰度，所以我们使用另一个特征值来代替灰度进行harris算法中窗移动的参考值。在点云中选取任意一个点p，在点p的表面建立局部坐标系，坐标系的z轴指向表面法向量的方向，在p上建立一个小的立方体，且物体表面点云密度相同。如果在法向量z轴方向上面移动立方体，立方体内部的点数量不会变；如果立方体在边缘上，沿着边缘方向立方体内部点数不会变，而沿垂直边缘方向移动，立方体内部点数会变，如果立方体在关键点上，那么立方体向除了垂直法向量的方向移动，内部点数都会变。

ISS(内部形状特征/Intrinsic Shape Signatures):对在全局坐标下运动的点周围建立局部坐标，保证该坐标系跟随运动点旋转运动，接着将观测点pi与周围的点pj的坐标进行相减，进行奇异值分解求出pi点的法向量，最终会形成三个互相垂直的向量，其中一个为法线向量，另外两个构成观测点的局部坐标系。这个坐标系处于一个椭圆之中，所以也称作椭圆内部坐标系，三个特征值的大小分别为椭圆的三个轴的长度。在此坐标系建模实现特征旋转不变的目的。建立出的模型可以通过利用特征值之间的关系来形容该点的特征关系。

NARF(Normal Aligned Radial Feature)：NARF关键点在PCL库中应用较多，特别是深度图中。提取NARF关键点需要考虑关键点有足够的空间计算特征描述子，可以重复地被探测，且考虑表面变化信息。NARF关键点的提取思路是遍历点云找出存在点的邻域在深度上存在变化的点，求出表面变化的系数，找出主方向，计算关键点特征的值，对该值进行平滑滤波，最后用非最大值抑制（NMS）操作找出NARF关键点。

1.4课题研究内容与目标

本次毕业设计我将使用C 编程语言，引入PCL库，在Visual Studio上实现一套算法系统，利用法向量直方图（HoNO）的思想检测三维点云数据中的关键点。 并将算法应用在实际的配准中来分析算法的特性。

第2章 背景知识

2.1 PCL库

2.1.1 PCL概述

PCL（Point Cloud Library）是一个可供开源的C 库^[2]，它经过多年的壮大，依据前人们的经验与研究成果上不断进步，在如今已经发展出了不错的规模。自从PCL在2011年被独立出来，数不胜数的研究者们贡献自己的研究结晶为它的发展提供帮助，并且随着近年来硬件水平的不断提高，获取能够运行点云库的设备变得更加容易，并且能够支持多种操作系统平台，可在Windows、Linux、Android、Mac OS X、部分嵌入式实时系统，所以现在在3D领域的PCL库就如同在2D领域的OpenCV库一样，具有流行的地位。

PCL库的主要处理数据是点云数据，点云数据通常是使用逆向工程获得的实际物体表面的点数据集合，这些点数据集合能够反映物体表面的特性，通过分布在表面的点集合的每个点的坐标，颜色，激光反射强度等信息来储存处理图像。

2.1.2 PCL功能

总的来说，PCL库提供了许多的函数与类，便于使用者们完成以下功能的使用与开发：

1、点云的获取（IO模块）：PCL库所能进行读/写的文件格式主要是PCD格式，除开对已有的PCD文件进行操作，PCL库还能直接和能产生点云数据的设备进行连接，特别是在PCL1.0版本之后，PCL集成了一个通用接口，其中最常用的数据获取模块是OpenNI Grabber。硬件方面，常用的设备有Microsoft的Kinect传感器，Hokuyo的UTM-30LX激光扫描仪，富士w3数码相机，Minolta的Range 5 3D摄像头等。丰富的数据采集来源为点云数据的获取增添了不少的便利。

2、点云的特征描述与提取（Features模块）：对于点云数据的大部分操作，都严重依赖特征提取的结果，只有经过特征提取的点云数据才能获取其中所想要进行操作的点。从尺度上来说，特征分为全局特征与局部特征描述，使用适当的尺度才能更有效地完成特征提取与描述。

3、点云的关键点提取（Keypoints模块）：关键点在点云中亦可称作兴趣点，作为关键点的点在点云中是稳定，明显，且可作为检测依据的，所以关键点的数量在点云中是远远小于整体点云点的数量的。将每一个关键点所具备的特征描述子结合，可以形成紧凑且具有描述性的数据集合。

4、点云的配准（Registration模块）：点云的配准是将多个数据集组合成一个全局且一致的模型的技术，配准的关键在于识别点云之间的对应点，并找到对应点之间距离（对准误差）的转化，不断地重复配准过程，将配准误差降到给定的阈值以下，则配准是完整的。

5、点云的检索（kdtree和octree模块）：点云的搜索模块常常由kd树搜索和八叉树octree搜索完成。kdtree和octree都能完成条件为半径r内和条件为最近的k个点的搜索方式，但octree还能能进行体素内的搜索。

6、点云的分割（Segmentation模块）：点云的分割模块用于将点云分割为不同的聚类，PCL库的分割算法最适用于处理多个空间上孤立的区域组成的点云，为了配合这些算法的特质，常常用聚类将点云分解成它的组成部分，然后独立地处理。

7、点云的采样一致性（Sample_Consensus模块）：机器视觉领域的采样一致性算法通常用来排除错误的样本，PCL的Sample_Consensus库是以随机采样一致性（RANSAC）算法为核心，借此可以实现五种类似于RANSAC参数算法的随机参数估计算法^[3]。这些算法可用来探测点云中特殊的模型和参数。

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

相关图片展示：