三维配准中FPFH特征提取算法研究毕业设计(论文).docx

北京化工大学毕业设计（论文）诚信声明本人声明：本人所提交的毕业论文是本人在指导老师的指导下独立完成研究，写作的成果。论文中所引用的文献、数据、资料都已经标注；对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式注明并表示感谢。论文中不包含他人已经发表或撰写过的研究成果，也不包含获得其他教育机构的学位或证书而使用过的材料。我承诺，论文中内容真实，可信。本人签名：_ 日期 年 月 日指导老师签字: 本科生毕业设计（论文）任务书设计（论文）题目： 三维配准中FPFH特征提取算法研究 学院： 理学院 专业： 信息与计算科学 班级： 信计1001 学生： 指导教师（含职称）： 专业负责人： 1 设计（论文）的主要任务及目标首先了解图像配准的定义，然后了解点特征直方图（PFH）和快速点特征直方图（FPFH）的三维点云特征提取算法，运用C/C+和Matlab语言对上述特征进行提取实现，得出特征直方图，然后进行比较、分析，最终得出结论。2 设计（论文）的基本要求和内容（1） 查阅和总结文献。（2） 熟悉掌握C/C+和Matlab语言的使用，熟悉对PCL开源库的应用，设计方案实现PFH和FPFH特征提取。（3） 对生成结果进行比较和分析。3主要参考文献1 Rusu R B, Blodow N, Beetz M. Fast point feature histograms (FPFH) for 3D registrationC/Robotics and Automation, 2009. ICRA09. IEEE International Conference on. IEEE, 2009: 3212-3217.2 Besl P J, McKay N D. Method for registration of 3-D shapesC/Robotics-DL tentative. International Society for Optics and Photonics, 1992: 586-606.3 Rusu R B, Marton Z C, Blodow N, et al. Persistent point feature histograms for 3D point cloudsC/Proc 10th Int Conf Intel Autonomous Syst (IAS-10), Baden-Baden, Germany. 2008: 119-128.4 朱德海，郭浩，苏伟. 点云库PCL学习教程M. 北京：北京航空航天大学出版社，2012.10.4进度安排设计（论文）各阶段名称起 止 日 期1文献查阅2014.1.10-2014.2.142阅读文献，翻译外文2014.2.14-2014.3.153撰写文献综述，确定论文方向2014.3.15-2014.4.154分析研究问题2014.4.15-2014.5.205整理结论，书写论文，准备答辩2014.5.20-2014.6.7三维配准中FPFH特征提取算法研究摘要：三维点云配准技术是图像配准技术在三维范畴上的延伸，它广泛应用在逆向工程、机器视觉、激光遥感测量、人机交互、虚拟现实等诸多领域。在三维点云配准中，对特征的描述以及提取是基础也是最为关键的问题。通过对三维点云数据的FPFH特征提取，比较两个数据之间特征的相似度，来估算它们之间的对应关系，最后利用正确的对应关系来估算刚体变换，完成配准过程。快速点特征直方图（FPFH）是一种能够描述三维点云数据的局部几何特征信息的点特征表示方法。本文对三种现有的点特征表示：估计法线、点特征直方图(PFH)和快速点特征直方图（FPFH）的描述以及特征提取的算法进行了阐述，然后对FPFH和PFH进行了计算复杂度、准确性、稳定性以及适用性的分析并归纳总结出FPFH的计算复杂度较低等等的优势，最后通过实验对部分结论进行了验证。关键字：图像配准，点云配准，特征提取，PFH特征，FPFH特征The Algorithm of FPFH Feature Extraction in 3D RegistrationAbstract:：3D point cloud registration technology is image registration technique on 3D category, which is widely used in reverse engineering, machine vision, laser remote sensing measurement, human-computer interaction, virtual reality and many other fields. In the 3D point cloud registration field, description of the characteristics and the extraction are the foundation as well as the critical steps. 3D registration includes following steps: Through FPFH of 3D point cloud data feature extraction and comparison of characteristics of similarity between two data, to estimate the corresponding relationship between them, finally correct corresponding relation is used to estimate the rigid body transformation, to complete the registration process. Fast point feature histogram (FPFH) is a way to describe three-dimensional point cloud data of the point feature representation of local geometry characteristic information. In this paper, firstly, three kinds of existing point feature are provided: estimated normal, point feature histogram (PFH) and fast point feature histogram (FPFH) including feature extraction algorithms, then the FPFH and PFH computational complexity, accuracy, stability and applicability to analysis, next sum up the advantages of low computational complexity, and so on FPFH, at last some conclusions are verified by experiments.Keywords: Image registration，point cloud registration，feature extraction，PFH feature，FPFH feature目录前言1开题报告2第1章 图像配准简介及点云配准7第1.1节 图像配准的定义7第1.2节 图像配准中的几何变换7第1.3节 图像配准方法简介9第1.4节 点云配准101.4.1 点云简介101.4.2 点云配准的定义101.4.3 点云配准方法简介11第2章 点云特征的描述及提取13第2.1节 法线估计13第2.2节 点特征直方图（PFH）14第2.3节 快速点特征直方图（FPFH）16第3章 点特征提取实验及结果展示18第3.1节 实验一：估计法线的提取18第3.2节 实验二：PFH提取19第3.3节 实验三：FPFH提取20第4章 论文总结与展望22第4.1节 论文总结22第4.2节 论文的展望24参考文献25致谢27附录（一）28附录（二）3334前言图像处理是对图像信息进行加工处理，以满足人的视觉、心理和实际应用的要求。图像配准技术是图像处理问题中的基础，图像配准技术主要用于将两幅或多幅来自不同时间、不同传感器、不同视角以及不同拍摄条件下的图片，使其进行匹配，最终的目的在于建立两幅图像之间的对应关系。三维点云数据的配准技术使图像配准的应用领域更加的完善。三维点云数据处理技术的应用十分广泛，主要作用在机器人领域、CAD/CAM、逆向工程领域、激光遥感测量领域、以及虚拟现实、人机交互领域等等。在机器人领域中，移动机器人对其工作环境的感知、辨识和认知的功能都是基于三维视觉图像的处理技术达成的。三维点云配准技术可以帮助机器人完成对周围环境的完整模型的识别。在CAD/CAM和逆向工程领域中，通过逆向工程三维测绘出庞大点云数据后，通过点云配准技术提取重建模型的几何参数，获得完整的几何模型，对工业产品制造或者对几何模型的理论研究都有着巨大帮助。在激光遥感测量领域中，三维点云处理技术可以对测量得到的数据进行高效快速的处理，进而获取可以表现三维空间信息的完整几何模型。在虚拟现实、人机交互领域，三维点云配准技术可以帮助模拟周围环境的几何模型，使人能够沉浸在计算机生成的虚拟环境中，建立一个适人化的多维信息空间。点云数据的点特征的描述与提取是三维点云配准技术的基础，也是最为关键的步骤。本篇论文着重介绍了点特征的描述以及提取的算法。具体的安排如下，第一章内容是对图像配准技术以及三维点云配准技术的定义和方法的简单介绍，第二章内容主要介绍了点云数据中的点的估计法线特征、点特征直方图（PFH）特征以及快速点特征直方图（FPFH）特征这三种点特征表示方法的描述以及提取的算法，第三章通过实验得到了具体的点云数据的三个特征图像并做了展示，第四章通过PFH和FPFH特征提取算法的理论分析FPFH和PFH特征的功能以及缺陷，并通过对实验结果的分析验证结果，最后还对论文未来的研究方向提出了自己的见解。开题报告一、 题目背景和意义 图像配准技术是图像处理的基本前提，这项技术的产生源自于很多领域的不同应用要求，这些领域包括模式识别、自动导航、医学诊断、计算机视觉、遥感图像处理等等。由于图像配准时图像的多样性，不同领域对配准的要求不同性，影响配准的因素的多样性，配准的复杂性使得配准技术不断地被研究，不断地进步。对于3D图像配准的引入可改善很多领域在应用上的完成情况，如3D图像配准可以降低微创手术，放射治疗等医疗技术上的实现难度，减少介入性治疗的创伤并提高手术精度。快速点特征直方图描述了三维点云数据集的一个点p周围的局部几何特征，有利于通过局部解决全局的方案，帮助将各种重叠的三维点云数据视图一致对准，在刚性意义上形成一个完整的模型，也就是三维配准问题。一、二、 国内外研究现状图像配准技术的提出最早是在军事方面，在美国七十年代从事的飞行器辅助导航系统、武器投射系统的末制导和寻地等应用研究中提出。但直到八十年代才开始引起学者们的重视，在很多不同领域渐渐出现了图像配准技术的研究，如遥感领域，模式识别，自动导航，医学诊断，计算机视觉等。在王蕾的介绍中，从上世纪70至90年代，图像配准技术不断被研究，包括了使用FFT进行互相关图像检测计算的图像配准技术，利用模板子图像的差值相似性测度的图像配准技术，基于自回归模型的动态程序设计方法用于几何畸变较大的图像的配准技术等等。W.K.Pratt研究了图像配准的互相关技术；M.Svedlow等对图像配准相似性测度和预处理方法进行了比较分析；Flussr针对变形图像间的匹配又提出了一个将两幅遥感图像自动分割，得到相似度很大的相应子块，根据这些子块的空间位置关系对原图像进行匹配的自适应映射方法。90年代以后,单模图像配准问题已基本解决，人们渐渐把关注放在多模图像配准上。国内也开始涉足此领域，李智等提出了基于轮廓相似性测度的图像配准方法，郭海涛等提出了一种将遗传算法（Genetic Algorithm，简称GA）用于图像配准的算法。王小睿等提出并实现了一种使用互相关函数作为相似性测度的半自动的图像配准方法；熊兴华等提出了将遗传算法和最小二乘法结合用于图像的子像素级配准。可见不论是国内还是国外，图像配准技术都发展的非常迅速，目前3D数据的配准成为了学术界的研究热点之一。Rusu R B等根据点云数据中点邻域环境研究实现了点特征直方图（PFH）以描述几何特征，以此根据来进行匹配，随后又对其在计算复杂度方面进行了改进和简化工作。图像配准的高精度、算法的强鲁棒性和配准速度以及图像配准的自动化都是图像配准领域不断追求的目标。二、三、 主要内容与待解决的问题点特征表示指出，某个点周围的几何特征是由表面法线和曲率估计表示的，但是无法获得太多信息。点特征直方图（PFH）的提出改善了这一点，PFH计算的方式是通过参数化查询点与邻域中点之间的空间差异，形成一个多维直方图，对点周围k邻域几何属性进行描述。当点云中有n个点时，PFH的理论计算的复杂度则较高，对于实时应用或接近实时应用中，密集点云中PFH会遇到重复计算的问题。一种PFH计算的简化形式快速点特征直方图（FPFH）被提出来，FPFH相对于PFH来说既有优势也有劣势，它简化了计算的复杂度，仍然保留了PFH大部分的辨别能力，但由于忽略部分点对的计算，可能导致了部分细节的丢失。 四、 设计方法与实施方案点特征直方图是基于点与其k邻域之间的关系以及它们的估计发现，它考虑的是估计法线方向之间所有的相互作用，捕获样本的表面变化情况，以描述样本的几何特征。一个查询点与其k邻域中一个点形成点对，两点和它们法线相关有12个参数，为了简化这些数据首先定义一个局部坐标系（u=ni,v=(pj-pi) u,w=uv），法线和之间的偏差用一组角度表示这样计算k邻域内每一点对的（）三组值，将参数减少到个。将数据中点和邻域内点形成点对，计算其三个角度特征值，将所有结果统计到一个输出直方图中。对于快速点特征直方图（FPFH），对数据中一点p，首先计算这个点和邻域点之间的三个角度特征值，得到简化的点特征直方图(称为SPFH)，再重新确定每个点的k邻域，使用邻近SPFH和一个权重计算公式，计算得出最终的输出直方图。五、 进度计划设计（论文）各阶段名称起 止 日 期1文献查阅2014.1.10-2014.2.142阅读文献，翻译外文2014.2.14-2014.3.153撰写文献综述，确定论文方向2014.3.15-2014.4.154分析研究问题2014.4.15-2014.5.205整理结论，书写论文，准备答辩2014.5.20-2014.6.7六、 参考资料1 Brown L G. A survey of image registration techniquesJ. ACM computing surveys (CSUR), 1992, 24(4): 325-376.2 Maintz J B, Viergever M A. A survey of medical image registrationJ. Medical image analysis, 1998, 2(1): 1-36.3 Besl P J, McKay N D. Method for registration of 3-D shapesC/Robotics-DL tentative. International Society for Optics and Photonics, 1992: 586-606.4 刘斌,彭嘉雄. 图像配准的小波分解方法J. 计算机辅助设计与图形学学报,2003,09:1070-1073.5 Rusu R B, Marton Z C, Blodow N, et al. Learning informative point classes for the acquisition of object model mapsC/Control, Automation, Robotics and Vision, 2008. ICARCV 2008. 10th International Conference on. IEEE, 2008: 643-650.6 Rusu R B, Blodow N, Beetz M. Fast point feature histograms (FPFH) for 3D registrationC/Robotics and Automation, 2009. ICRA09. IEEE International Conference on. IEEE, 2009: 3212-3217.7 Zhang Z. Iterative point matching for registration of free-form curvesJ. 1992.8 Rusu R B, Marton Z C, Blodow N, et al. Persistent point feature histograms for 3D point cloudsC/Proc 10th Int Conf Intel Autonomous Syst (IAS-10), Baden-Baden, Germany. 2008: 119-128.9 朱德海，郭浩，苏伟. 点云库PCL学习教程M. 北京：北京航空航天大学出版社，2012.10.10 王蕾. 图像配准技术及应用研究D.西安电子科技大学,2007.11 刘松涛,杨绍清. 图像配准技术研究进展J. 电光与控制,2007,06:99-105.12 郭海涛,刘智,张保明. 基于遗传算法的快速影像匹配技术的研究J. 测绘学院学报,2001,S1:20-22.13 王小睿,吴信才. 遥感多图象的自动配准方法J. 中国图象图形学报,1997,10:39-43.14 熊兴华, 钱曾波, 王任享. 遗传算法与最小二乘法相结合的遥感图像子像素匹配J. 测绘学报,2001,01:54-59.15 彭景林. 基于互信息和离散小波帧分解的医学图像配准研究D.湖南大学,2006.16 常学义,孙秋冬,任煜,陈玮. 基于MATLAB的图像配准方法J. 上海第二工业大学学报,2006,04:303-308.17 吴嘉. 基于特征点空间信息分布直方图的匹配方法研究D.南京理工大学,2012.18 赵辉. 基于点特征的图像配准算法研究D.山东大学,2006.19 苑津莎,赵振兵,高强,孔英会. 红外与可见光图像配准研究现状与展望J. 激光与红外,2009,07:693-699.20 Rusu R B, Blodow N, Marton Z C, et al. Aligning point cloud views using persistent feature histogramsC/Intelligent Robots and Systems, 2008. IROS 2008. IEEE/RSJ International Conference on. IEEE, 2008: 3384-3391.21 Rusu R B, Marton Z C, Blodow N, et al. Towards 3D point cloud based object maps for household environmentsJ. Robotics and Autonomous Systems, 2008, 56(11): 927-941.第1章 图像配准简介及点云配准第1.1节 图像配准的定义什么是图像配准？上世纪九十年代Brown给出了令大家认可的定义：图像配准技术是将同一场景（或物体）在不同时刻，不同传感器，不同视角以及不同拍摄条件下得到的两幅或多幅的图像进行匹配的过程1。可以简单地将图像配准理解成两幅图像之间一对一的映射过程。我们分别用矩阵来表示两幅图像，矩阵中的元素表示相应位置图像的灰度值，则映射的表示为： (11)为一个二维空间的坐标变换： (12)为一个一维的灰度变换，但灰度变换一般是不必要的。因此图像配准的关键在于寻找最优的空间或几何变换，通常将映射函数参数化为两个单值函数： (13)第1.2节 图像配准中的几何变换上文讲到图像配准的关键问题在于寻求最优的几何变换，下文将介绍一下几种常用的几何变换类型。图像配准中常用的图像几何变换模型包括：刚体变换（Rigid body transformation）、仿射变换（Affine transformation）、射影变换（Projective transformation）、和非线性变换（Nonlinear transformation）。2这四种变换可用数学语言描述为：（1） 刚体变换定义：图像中两点之间的距离在变换前后保持不变，该变换称为刚体变换。满足条件：平移、旋转数学表达：二维空间中，点变换到的公式为： (14)其中指旋转角度，指平移量。（2） 仿射变换定义：图像中一条直线经变换后仍为一条直线，且变换前后直线保持平行关系的变换称为仿射变换。满足条件：平移、旋转、缩放数学表达：二维空间中，点变换到的公式为： (15)其中为实数矩阵，指平移量。（3） 射影变换定义：图像中一条直线经变换后仍为直线，但变换前后的两条直线基本不保持平行关系的变换称为射影变换。满足条件：平移、旋转、缩放、投影数学表达：高维空间中，变换到的变换公式为： (16)其中为实数矩阵。（4） 非线性变换定义：图像中一条直线经变换后不再是直线的变换称为非线性变换。满足条件：平移、旋转、缩放、投影、扭曲数学表达：二维空间中，点变换到的变换公式为： (17)其中指任意函数形式。第1.3节 图像配准方法简介图像配准作为图像处理的基础，源自于许许多多不同领域的实际问题，应用领域的不同也导致了图像配准方法的多种多样。如何对各种各样的配准方法分类？Brown根据变换模型的复杂程度提出了三个范畴：搜索空间类型、特征空间类型、搜索策略类型1，用三个类型来对图像配准方法分类。搜索空间类型是指图像配准过程中可以配准图像的变换操作的集合，其中几何变换为主要的因素。配准图像的变换操作一般可以分为：全局与局部。全局的变换一般可以通过一个参数矩阵来描述。局部的变换一般对变换参数有位置的依赖性，不同的位置计算不同的变换参数。特征空间类型是指图像配准过程中需要使用的具有重要实际意义的图像特征。一般用空间坐标对同种属性的图像进行特征表示。搜索策略类型是指图像配准过程欧诺个需要运用的一些优化准则和优化算法的策略集合。常用到的策略如：松弛匹配、最速下降法、牛顿法、共轭梯度法等等。Paul J.Besl等人根据利用图像中的信息配准将图像配准方法分为两大类：基于像素的图像配准和基于特征的图像配准。3（1） 基于像素的图像配准方法基于像素的图像配准方法是根据两幅图像的像素信息，直接计算图像之间的相似程度。首先选定一个与图像特点相应的相似度量函数，采用适当的搜索算法，找到使其相似度最大的几何变换参数，达到配准的目的。这类方法的优点在于实现简单，缺点在于应用面比较狭窄。（2） 基于特征的图像配准方法基于特征的图像配准方法是指通过对两幅图像中的相同、重要的特征进行匹配来确定配准映射变换。首先对两幅图像进行特征提取，这些特征可能是：点、线、边缘、闭合区域等等，再建立特征之间的对应关系，最后估计出两幅图像间的几何变换参数，完成图像配准。这类方法的优点在于计算复杂度比较低，可适用的范围广。缺点在于相比较于基于像素的图像配准方法，配准的精度较低。这样的分类包含了大部分的图像配准方法，下文中介绍的点云配准方法思想上也属于基于特征的图像配准方法。图像配准的方法还有很多，像文献4介绍的图像配准的小波分解方法就是以后总基于变换域信息的图像配准方法。更加简单、便捷的图像配准方法还等待着后人去探索。第1.4节 点云配准1.4.1 点云简介上文主要对图像配准的定义和图像配准的方法作了简单的介绍。当参考图像和配准图像变成了三维空间中的点云数据的时候，配准的方法和过程是否会变得不同呢？本节给出了答案。文献5中告诉我们，点云数据是指通过激光或者雷达扫描、立体摄像机等设备三维测量出的海量的表现出目标表面特征的点的集合。点云的处理技术广泛应用于立体3D影响、虚拟现实、CAD/CAM、逆向工程等领域。举个简单的例子，在汽车制造业中，零件的生产制造是根据于三维CAD模型，但可能由于设计多次更改或者数据丢失等原因无法获得零件的要生产的零件的几何模型，这时可以通过逆向工程技术对油泥模型或者其他实物进行测绘，获取庞大的点云数据，从而提取重建的模型的几何参数，或者从点云数据中获取模型的曲面模型，最终完成零件的生产。1.4.2 点云配准的定义点云配准技术的产生来源于实际问题，如上小节例子中提到的逆向工程技术，对实物模型进行三维测绘产生，获得庞大的点云数据，但得到的点云数据可能由于平移错位或旋转错位等原因不完整，无法获得想要得到的完整的数字模型。为了使点云完整，就必须对局部点云数据进行图像配准。点云配准问题可以简单地概括成将各种重叠的三维点云数据视图一致对准，形成一个完整的模型（在一个刚性的意义上）的问题6。点云配准技术是通过一定的算法来计算两块点云之间的错位，从而达到配准的效果。它的实质在于确定一个合适的坐标变换，将从不同视角获得的点云数据合并到一个统一的坐标系中，形成完整的点云。解决问题的关键在于找到最优的坐标变换参数（旋转矩阵R以及平移向量T），使两个点云数据经坐标变换后重叠区域对应点之间的距离最小。1.4.3 点云配准方法简介点云配准的方法思想上都属于基于特征的图像配准方法。下图简单介绍了一堆点云数据配准时的主要步骤：图11 点云配准流程至今比较流行的配准方法为迭代最近点算法（Iterative Closest Point，简称ICP算法）37和采样一致性初始配准算法（简称SAC-IA算法）6,下面对两种算法进行简单介绍：（1） 迭代最近点算法（ICP算法）对两个含有重叠区域的点云数据使用ICP算法配准的主要步骤为： 对两个点云数据进行采样。 根据一定准则确定对应点集P和Q，其对应点对的个数为n 去除错误的对应点对 通过最小二乘法迭代计算得出最优的坐标变换（旋转矩阵R和平移向量T），使得误差函数最小。ICP算法的优点在于计算简单直观，具有较好的精度。它的缺点在算法对于初始变换估计和迭代过程中确立的对应关系具有较大程度的依赖性，影响算法的收敛和运行速度。（2） 采样一致性初始配准算法（SAC-IA算法）SAC-IA算法在精度上属于一种初始的变换矩阵的粗略估计的方法，相比于ICP算法的拥有精确的变换矩阵估计，这类算法需要查看所有可能的对应点对关系，计算复杂度较高。所以SAC-IA算法采用了采样一致性方法，可以不必查看有限对应关系的所有组合，并保持相同的对应点对的几何关系。主要步骤为： 从点集P中选择s个样本点，确定其成对的距离大于用户给定的最小值。 对每个样本点，在Q中找到特征描述与样本点特征描述相似的点组成集合，从集合中随机选择点与样本形成点对代表样本点对的对应关系。 计算通过样本点定义的刚体变换及其对应变换，通过计算误差度量评价变换质量。 重复上述3个步骤得出误差度量最佳的变换，最后使用一个Levenberg-Marquardt算法惊醒非线性局部优化。SAC-IA算大相比贪婪的初始配准方法大大降低了计算的复杂度。第2章 点云特征的描述及提取引言3D点云的特征描述及提取是三维点云配准技术的基础，同时也是最关键的一部分。点云配准必须根据相似的点特征描述正确的估计其对应关系，从而估算刚体变换公式完成配准。同时点云特征描述及提取也在点云信息处理其他方面发挥着巨大的作用，如：点云的识别、点云的分割、点云的曲面重建等算法都以来提取的特征描述结果。原始的表示形式中，一个点是通过笛卡尔坐标系的坐标X,Y,Z来表示的，但是三维映射系统中，假设给定一个原点，这个原点是不随时间而改变的。若分别在时间捕获点云数据中点和，且点和拥有相同的坐标，但他们取样于模型的不同表面，所以当把他们和邻近环境中的点放在一起时，他们表达的几何信息故不相同。因此单一的实体三维点概念和笛卡尔坐标在描述局部特征时被淘汰了，一个新的概念出现并取其位置：点特征表示5。点特征表示能够表现出采样表面的几何性质特征，帮助解决估算对应关系的问题。本章介绍了三个点特征表示以及分别提取其点特征的方法。第2.1节 法线估计点云数据中点所在处的相关法线是表现这一点所在表面的几何性质的重要属性。对一个已知的几何表面来说，一个点的法线方向即为垂直于点表面的矢量，计算比较简单，而在点云数据中不存在真实的表面，它的表现仅仅是一组点。因此想要得到点的法线方向可以通过下面两种方法：（1） 通过曲面重建技术得到样本点对应的曲面，计算垂直于曲面的矢量。（2） 直接从点云数据中近似估算表面法线。本节主要对第二种方法进行介绍。估计发现的方法有很多，其中比较简单的一个表述如下：想要求得一个点的表面法线，即要求得点所在的近似估计表面的相切面的法线，所以我们可以把这一问题转换成一个最小二乘法的平面拟合的问题，因此求解估计法线的过程可归纳为：（1） 对样本点进行邻近元素查询，搜索确定样本点的k邻域。（2） 估计样本点邻近元素的三维质心坐标。（3） 利用公式计算样本点以及邻近点组成点集对应的协方差矩阵，并计算协方差矩阵的特征值和特征向量： (21)其中是点邻近点的数目，表示邻近元素的三维质心，是协方差矩阵的第个特征值，是第个特征向量。（4） 分析协方差矩阵的特征值和特征向量，将最大的特征值对应的特征向量作为样本点的估计法线。查看通过上述步骤得到的法线向量后，我们会发现法线向量的方向有正有负，无法保证同一表面的点的法线方向朝向同一个方向。为了解决这一问题，我们还需要进行一个同一法线方向的操作。统一法线方向的操作原理十分简单。单一的点云数据是从一个单一的视角获得的，因此我们可以定义一个视点，令其为，只要令所有法线朝向视点方向即可做到方向一致，故只需满足方程： (22)可得到方向一致的法线向量。对一个点云数据分别对个点求得估计法线的结果将会在下一章展示。第2.2节 点特征直方图（PFH）对一个复杂的几何表面来说，单单给出一个样本点的估计法线无法很准确地描述这一样本点周围的局部几何特征信息，因此Radu等人提出了点特征直方图（Point Feature Histograms，简称PFH）8，它可以作为一个点特征来描述这一点周围的局部几何特征。什么是点特征直方图呢？我的理解点特征直方图是将一个样本点邻近的局部区域的几何特征信息以统计分布的形式展示在一个直方图中。可以、比较两个点云数据中点的PFH，然后通过相似度确定点云之间的点对的对应关系。PFH描述周围几何特征的方法是考虑样本点与其k邻域之间的关系和他们之间的估计法线之间的关系。下图中展示的是一个样本点与其k邻域内所有点（与的距离小于半径r的点）之间互相连接在一起的网络图。6图21 点的PFH计算影响区域具体的计算方法如下：（1） 对样本点，查询其邻域内所有邻近点。（2） 对点邻域中每对点和（）和他们对应的估计法线,定义一个固定的局部坐标系： (23) 来计算和以及他们对应的估计法线和之间的偏差。可以用下面一组角度来表示法线和之间的偏差： (24)下图可以直接地看出所代表的角度：9图22 和之间的局部坐标系这样可以将k邻域内的一对点之间的关系用三个值表示，当计算出所有点对的三个特征值之后再以某一种统计方式放进直方图中。本文应用了Pcl（Point Cloud Library）中的Pcl-features模块9实现了对PFH的计算。将每个特征值的取值区间分别分割成5个小区间，这样三个特征值的取值区间就变成了125()个小区间，使每一个点对可以落入符合三个特征值取值范围的区间中，然后对所有点对进行统计，最终得到可以描述样本点周围局部几何特征的点特征直方图（PFH）。Pcl是一个吸收了前人点云的相关研究，在这基础上建立起来的跨平台的开源库。其中实现了大量通用算法和数据结构。Pcl在3D信息处理的地位等同于OpenCV在2D信息处理上的地位。第2.3节 快速点特征直方图（FPFH）上节中的PFH点特征要计算样本点的k邻域中任意两点组成点对的三个特征值，因此计算的复杂度即为。为了使计算更加简洁,Radu等人有提出了一种点