经过一周的综述和写作，我深深感受到云算法的广泛应用，只能依靠前辈的文章进行整理：
点云硬件：
点云获取技术可分为接触式扫描仪、激光雷达、结构光、三角测距（Triangulation）、以及立体视觉等。近二十年来，点云获取设备发展迅速。
经过20多年的发展，三维激光扫描硬件在稳定性、精度、可操作性等方面取得了巨大进展，特别是在机载/车载/地面三维激光扫描方面具有代表性的三维激光扫描硬件开发商包括：Riegl、Leica、Optech、Velodyne、北科测绘、海达数云等。还有美国NASA的ICESat激光雷达与中国资源302星搭载。
点云软件：
目前，工业和学术界已经开发了各种针对点云处理的商业软件和开源软件。商业软件主要包括TerraSolid公司的TerraSolid（基于Microstation平台开发，功能强大）、Trimble公司的Realworks、Leica公司的Cyclone、Bentley公司的Pointtools、Orbit GT公司的Orbit Mobile Mapping以及国内科研院所和公司开发的一些工具软件，比如武汉天擎LiDAR Suite、西安煤航的LiDAR-DP北京数字绿土LiDAR 360等。其重点主要集中在点云数据的管理上DEM生产的滤波[1]、三维建筑的提取和重建[2]、森林垂直结果参数提取[3]等方面。
此外，还有一些开源、自由的点云数据处理软件，包括以下几种：
- Lastools：国际知名度高，C 编写、分模块、开源部分模块、底层IO压缩库开源。
- OPALS：维也纳技术大学摄影测量研究小组开发的软件是学术界最好的。它也是底层库 几乎任何激光雷达数据都可以支持功能模块的结构，处理效率很高。C /Python二次开发。
- BCAL LiDAR tools：一个ENVI插件，支持LiDAR可视化、处理格式点云，IDL编写。
- CloudCompare：C 依赖于开发QT和OPENGL。支持基于插件的扩展机制。可拔插操作，可二次开发，不影响源程序。充满活力，经常更新。
- FUSION：开源软件，功能很多，在forestry和ecology学术界比较有名，可以计算多种LiDAR metrics。
与三维激光扫描硬件设备的快速发展相比，三维点云的智能处理发展相对落后，需要提高点云处理的智能水平、软件界面友好性和专业应用数据接口。
点云算法：
点云处理可分为低、中、高三个层次。低层次处理主要包括滤波器和关键点的检测；中层处理包括点云特征描述和分类；有高层处理配准、SLAM图纸优化，三维重建等等。与传统的测量方法相比，三维激光扫描数据采集速度快，采样频率高，但也导致点云数据冗余高、误差分布非线性、不完整，给大量三维点云的智能处理带来了巨大的困难。
滤波：
常用的滤波方法主要包括直接滤波、体素法滤波、统计滤波、半径滤波、条件滤波、双边滤波、高斯滤波、随机采样一致性滤波和基于频率的滤波。
除上述常见的滤波算法外，从LiDAR去除点云中的地物点，保留地形点是点云滤波的重要组成部分。算法可分为以下几类：
⑴布料模拟滤波器
布料模拟滤波器（Cloth Simulation Filtering，CSF）是物理模拟算法。该算法首先将地表点云翻转，然后将由网格组成的虚拟织物放置在翻转点云表面的最高点，使其自由落下。织物节点在重力和相邻节点的相互作用力的影响下产生位移，并附着在地形表面上。操作完成后，当布料上某个节点的高程小于或等于相应点的高程时，将点云的高程作为节点标记为不可移动点。最后，计算密集匹配点云与织物节点之间的高差，大于阈值的被视为非地面点高差，相反，被视为地面点[5-6]。
⑵滤波算法基于坡度
Vosselman [7]提出地点之间的坡度值较小，计算每个点与周围相邻点之间的坡度值，并根据阈值判断是否为地点；Sithole[8]根据地形坡度的变化，坡度阈值不再是固定常量；张浩[9]采用坡度、坡度增量、最小坡度、最大坡度四个参数进行滤波判断。
问题:计算量大，占内存；依赖阈值。
⑶基于形态学的滤波算法
形态学滤波原理：形态学开操作前后非地面点高程变化较大，形态学开操作前后地面点高程变化较小。非地面点可以通过设定阈值(形态学腐蚀再膨胀)去除。
关键在于滤波窗的选择，Zhang[10]提出经典的渐进式滤波器，窗口变小变大，对应不同的高阈值；然后学者在此方法的基础上进行改进，Hui[11]等结合克里金插值计算各层级局部区域的地形起伏度，以此为滤波准则进行优化。
问题：滤波窗口不好选取，渐进变化窗口效果不错，但大窗口易将地形起伏点误判为地物点。
⑷基于曲面拟合的滤波算法
原理：通常采用一定的插值拟合方法建立一个粗糙地形曲面，设定滤波准则，如点到曲面的距离，将不满足条件的点逐步剔除。持续迭代，直到所有的地形曲面的精度达到所需的分辨率。
Kraus和Pfeifer[12]采用线性预测的方法，设定权重函数，在森林区域效果良好；Mongus和Zalik[13]提出了一种无参数的多层级渐进加密点云滤波法；Hu[14]等同样采用TPS插值法，但在各层级进行拟合曲面时，计算各层级局部区域的弯曲能量，实现滤波阈值的自动计算。
优缺点：不需要过多的参数设置，自适应能力强，但多层级迭代，每一层级的滤波结果都会受到上一层的影响，初始地面不准确，就会出现误差的传递与累积。内插方法也有很大影响。
⑸基于不规则三角网的滤波算法
原理：利用TIN模型中的地物临近点云高程突变关系，研究利用高差临界值条件和满足该条件的临近点数量等参数来过滤地物点。
Axelsson[15]提出经典的渐进加密不规则三角网（PTIND）滤波算法，简称PTD算法：首先获取地面种子点，建TIN并进行迭代加密。在每次迭代过程中，都对其余各点到所在三角形的反复角和反复距离进行阈值判断，满足条件的点加入TIN，迭代至无点。Zhang和Lin[16]将光滑约束分割法与PTD方法相结合，减少地形凸起区域的细节误差。隋立春[17]等首先对各个格网内的点云按升序进行排序，然后按照排序顺序再对TIN进行加密，有效减小Ⅱ类误差；吴芳等[18]在选择地面种子点之前首先去除非地面点的影响，保证契合原有地形。
渐进加密不规则三角网算法近年来表现最为稳健。在复杂地形中效果良好，误差低；但处理时间稍长，初始TIN对后续滤波影响很大；PTD算法对低位噪声敏感，极易将低位噪声点或低势地物点误判为地面点。
⑹基于分割的滤波算法
通常包含两步，一是采取某种分割方法对点云进行分割，二是基于分割结果按照某种设定的规则进行点云滤波。
点云聚类分割的方法有很多：扫描线、Mean Shift分割法、区域生长法、、随机抽样一致等。滤波判断的标准大多为地面点聚类区域低于地物点聚类区域。Lin和Zhang[19]首先采用区域生长法将点云分割成不同的部分，再设定规则选择地面种子点，建TIN，PTD算法迭代；Tovari和Pfeifer[20]首先对点云进行分割，对分割后的每一部分计算残差值，并根据残差值对属于同一部分的点云设置相同的权重，再按照Kraus和Pfeifer提的方法进行迭代滤波。
优缺点：能获得更好的点云滤波效果，原因在于点云聚类分割，点云块能够提供更多的语义信息，更有利于后续的滤波判断；分割后的点云能准确地到达地形断裂线或者高程跳跃边缘。但过分依赖聚类分割的结果。
⑺基于机器学习的滤波算法
基于机器学习的滤波算法将点云滤波视为二分类问题。采用某种机器学习算法，如条件随机场、支持向量机、Adaboost等对训练样本进行训练获取训练模型，然后采用此训练模型对点云进行0（地面点），1（非地面点）标记。
Lu等[21]建立了一种基于离散和连续隐含随机变量的条件随机场模型，以区分地面点和非地面点；Jahromi等[22]提出了一种基于人工神经网络（ANN）的算法：分别采用半自动化获取训练样本和人工获取训练样本两种策略。Hu和Yuan[23]采用卷积神经网络（CNN）通过对点云进行深度学习实现滤波，该方法将点云滤波问题转化为图像的分类问题，通过对1.728*10的7次方个标记的点云进行训练学习，可以获得1.5*10的八次方个参数的深度卷积神经网络模型，现有滤波算法中精度最高。
缺点：需要大量的标记点云作为训练样本，耗费大量人力，占用大量计算机资源，耗时；训练样本要求覆盖所有地形特征，很难实现。
⑻基于伪扫描线的滤波算法
伪扫描线：指将水平面上二维离散分布的激光点重新组织成一堆线状连续分布点序列的一种数据结构。基本思想：两点之间的高度差是由自然地形的起伏和地物的高度共同引起的。若两个邻近点之间的高度差越大，那么这个高度差是由自然地形引起的可能性就越小，更有可能是较高点位于地物上而较低点位于地面上。
优点：算法简单，有效减少计算量并且保证了准确性，同时只需两个滤波参数，较容易实现自动化；总能保证每个滤波窗口都包含有地面点，准确地提取出地形点；在平坦区域，效果非常好，在地形陡峭地区，误差控制在较小范围。
缺点：当地面点较少的时候，这类方法会失效；滤波窗口大小的选取还不能完全自动化，尤其在高程变化剧烈的区域和城市地区。
⑼基于多分辨率方向预测的滤波算法
方向预测法的思想：对于某一距离范围，若当前点与所有方向预测值的差值均大于该距离条件下的最大高差限差，则该点为地物点，否则为地面点。
优缺点：此算法可以实现复杂尺寸的地物目标的剔除处理，由于数据集再数据量上的减少，地面点提取的效率有很大提高。对于附属在斜坡上的建筑物会出现滤除不完全的情况，需要结合航片等辅助数据源来提高滤波精度。多分辨率平滑处理可以得到格网数据集，但格网之间存在缝隙，降低了精度，需要利用点云数据和格网数据集进一步做点云滤波处理。
总体而言，在训练样本足够多的情况下基于深度学习的点云滤波算法能获得最好的滤波效果，但其较为复杂的样本标记和较长的处理时间会限制算法进一步发展；相较而言，基于分割的滤波算法因为能获得更多聚类后的语义信息可以获得更高的滤波精度，此外渐进迭代方式的算法也有较好的结果。
关键点\特征线提取
点云数据的几何特征主要是指对反映被测物体三维形态和纹理特征有关键性影响的点、线、面。不同的对象需要的特征提取方式不同，即便是同一对象也需要依照不同需求提取不同的特征。
在点云特征提取方式上，现有算法可以分为基于全局特征的方法和基于局部特征的方法两类，全局特征利用点云上所有点的信息构建特征描述子。然而由于复杂场景下的物体遮挡、数据分辨率变化、噪声干扰、背景影响以及视点变化等，使得获取的点云具有显著的多样性。这些多样性使得局部特征比全局特征更加胜任现实世界中的点云表示。局部特征提取通常包括关键点检测和局部特征描述两个步骤，其构成了三维模型重建与目标识别的基础和关键。
本节主要阐述关键点和特征线的提取算法。
3.2.1 点云的关键点提取算法
点是三维点云数据中最基本的几何形状的特征基元，将三维模型模型表面具有代表性和描述性的点集定义为特征点，例如边界点、尖锐点，以及相邻曲面的公共点。关键点的数量相比于原始点云或图像的数据量减小很多，与局部特征描述子结合在一起，组成关键点描述子，常用来表示原始数据，而且不失代表性和描述性。
利用协方差矩阵建立模型：把pi和周围点pj的坐标相减：本质上这生成了许多从pi->pj的向量，理想情况下pi的法线应该是垂直于这些向量的。利用奇异值分解求这些向量的空间，拟合出一个尽可能垂直的向量，作为法线的估计。
利用特征值之间关系来形容该点的特征程度。显然这种情况下的特征值是有几何意义的，特征值的大小实际上是椭球轴的长度。椭球的的形态则是对邻近点分布状态的抽象总结。 试想，如果临近点沿某个方向分布致密则该方向会作为椭球的第一主方向，稀疏的方向则是第二主方向，法线方向当然是极度稀疏（只有一层），那么则作为第三主方向。如果某个点恰好处于角点，则第一主特征值，第二主特征值，第三主特征值大小相差不会太大。如果点云沿着某方向致密，而垂直方向系数则有可能是边界。总而言之，这种局部坐标系建模分析的方法是基于特征值分析的特征点提取。
角点的一个重要特征就是法线方向和周围的点存在不同，而此算法的思想就是和相邻点的法线方向进行对比，判定法线方向差异的阈值，最终决定某点是否是角点。并且需要注意的是，本方法所针对的点云应该只是有序点云。本方法的优点是快，缺点是对噪声敏感。
在二维中是取一个窗口，然后移动窗口：
1.两个特征值都很大，则为角点（两个响应方向）。
2.一个特征值很大，一个很小，则为边缘（只有一个响应方向）。
3.两个特征值都小，则为平原地区（响应都很微弱）。
在点云中是建立一个方块体，以体内数量变化确定角点。如果在点云中存在一点p：
1、在p上建立一个局部坐标系：z方向是法线方向，x,y方向和z垂直。
2、在p上建立一个小正方体。
3、假设点云的密度是相同的，点云是一层蒙皮，不是实心的。
a、如果小正方体沿z方向移动，那小正方体里的点云数量应该不变。
b、如果小正方体位于边缘上，则沿边缘移动，点云数量几乎不变，沿垂直边缘方向移动，点云数量改变。
c、如果小正方体位于角点上，则两个方向都会大幅改变点云数量。
NARF 全称 normal aligned radial feature(法线对齐的径向特征) 。是一种3D特征点检测和描述算法。能提取到 borders points 和其对应的 shadow points，提取到的特征点都是位于物体的外轮廓(边缘)上，更加具有稳定性和可重复性。对特征点Normal的估计只使用共面点，因而对Normal的估计更加稳定。所有操作都是基于2D的range image，计算量相比于直接操作点云要小。
对点云而言，场景的边缘代表前景物体和背景物体的分界线。所以，点云的边缘又分为三种：前景边缘，背景边缘，阴影边缘。三维点云的边缘有个很重要的特征，就是点a 和点b 如果在 rang Image 上是相邻的，然而在三维距离上却很远，那么多半这里就有边缘。
1.这个点在某个平面上，边长为 s 的方窗没有涉及到边缘。
2.这个点恰好在某条边缘上，边长 s 的方窗一半在边缘左边，一半在右边。
3.这个点恰好处于某个角点上，边长 s 的方窗可能只有 1/4 与点处于同一个平面。
将该点与不同点距离进行排序，得到一系列的距离；若这个数列存在某个阶跃跳动（可能会形成类似阶跃信号），那么发生阶跃的地方应该是有边缘存在。
尺度不变特征转换(Scale-invariant feature transform,SIFT)是David Lowe在1999年发表，2004年总结完善。该算法通过求一幅图中的特征点（interest points,or corner points）及其有关scale 和 orientation 的描述子得到特征并进行图像特征点匹配。
首先构建尺度空间，目的是为了模拟图像数据的多尺度特征；为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。一个点如果在尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点；然后去除不好的特征点：本质上要去掉尺度空间局部曲率非常不对称的像素；上一步中确定了每幅图中的特征点，为每个特征点计算一个方向，依照这个方向做进一步的计算， 利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。
3.2.2 点云的特征线提取算法
在特征线提取方面，大部分学者主要针对网格模型进行相关特征线提取方法的研究，对点云模型的特征线提取研究相对而言较少，主要原因在于点云数据量大，本身没有自然拓扑连接关系，而且还可能存在噪声、数据缺失等问题，所以在点云数据上提取特征线比较困难。但是，利用点云数据提取特征线，由于不需要重建网格数据，具有所需时间少，而且数据容易获取的优势。
目前，基于点云模型的特征线提取的方法可以分为基于几何特征、基于协方差分析和基于投影映射的三类方法。
⑴基于几何特征的方法
此方法是利用点云的几何信息，比如法向量、曲率、Voronoi图等来提取特征曲线。Demarsin[1]等首先利用法向量估计的而信息对点云数据进行分割，对于每个分割后的区域内的点集，利用最小生成树的算法进行特征曲线的提取。Yang B[2]等提出的方法首先将根据曲率选择视觉突出点进行聚类，并未每个点赋予权重，然后提出描述点云形状特征的波峰线。刘倩[3]等提出的方法在高斯映射的基础上，对曲率值进行分析，主要是用来提取模型中较为尖锐部分的特征曲线，对于模型中的一些细微特征没有办法识别出。Merigot[4]等通过计算本地 Voronoi 图获得邻域信息，然后计算曲率，但是 Voronoi 图容易受到噪声点的影响。
⑵基于协方差分析的方法
基于协方差分析的方法是根据协方差矩阵的特征值，通过对特征值进行计算分析，可以用来表示模型局部曲面的弯曲程度。Gumhold等[5]对局部邻域构建协方差矩阵，计算得到特征值，根据其比例关系，将特征点分为边界点，棱点，角点，构建最小生成树，提取出特征曲线。上述方法需要高质量的点云，而且对细微特征不敏感。Nie J[6-7]等首先利用 PCA 计算曲面变化度，并根据符号曲面变化度绝对值识别潜在特征点，对其进行分割, 然后根据曲面变化度与设置的距离权重不断将边界点进行细化，最终采用最小生成树的算法将特征点进行连接，得到特征曲线。但该方法随着噪声程度增加，特征线易出现断裂和缺损。
⑶基于投影映射的方法
基于投影映射的方法是经过拟合得到模型的局部曲面，并将特征点投影在该曲面上。Daniels[8]等利用鲁棒移动最小二乘法，拟合每个点邻域的曲面，再将特征点投影到不同曲面的交线上，以提取特征线。但是因为该方法是在移动最小二乘的基础上实现的，算法运行的时间过长，代价略高。庞旭芳[9]等通过拟合局部二次曲面计算曲率，然后找到与特征点距离最短的潜在特征线，并把特征点投影在该条线上，得到增强后的特征点。这种方法可以提取到模型上平缓和细微的特征，但是最终得到的特征曲线中有部分特征线之间有裂缝。
点云特征描述
一个良好的特征描述子应能包含所在局部表面的主要形状信息以提供足量的鉴别力。此外，一个良好的特征描述子还应对噪声、遮挡、背景干扰、点密度变化以及视点变化等稳健。 现有的局部特征描述算法可以分为基于点特性、 基于直方图以及基于变换的算法三类。
3.3.1 基于点特性的方法
这类方法直接采用关键点局部邻域内部分或全部点上的几何属性集合对其局部邻域进行描述[45]。
Stein和Medioni [1]采用关键点的测地邻域点法向量分布构建splash特征描述子。给定关键点p，首先采用测地半径r获得网格上的一个环状切线，进而采用点p处的曲面切平面及法向量n构建一个局部参考坐标框架（Local Reference Frame，LRF）。采用该LRF，将点p的法向量与环状切线上点的法向量的关系（即角度距离）采用一个三维矢量进行表示。接着，采用直线段对该三维曲线进行拟合，并以三维直线段的曲率和扭转角（torsion angle）构建特征描述子。实验结果表明，该算法对噪声稳健。
Chua和Jarvis[2]提出了point signature特征描述子。Sun和Abidi[3]受人类指纹的启发，提出了一种 point’s fingerprint 特征描述子。给定关键点p，首先以与点 p的测地距离相同的点构成一个测地圆（geodesic circle），采用一系列不同的测地距离从而获得一个测地圆集合。进而采用点p的法向量和切平面构建一个LRF，并将这一系列测地圆投影到切平面上以获得一组二维等值线。采用这些二维等值线以及测地圆上的法向量和半径变化量等构成特征描述子。Sun和Abidi认为该算法优于 point signature 和 spin image 特征，且其计算量相对较小。
Malassiotis和Strintzis [4]通过对关键点p的邻域点散布矩阵进行特征值分解从而构建一个LRF，然后在z轴方向与点p距离为d的位置放置一个虚拟针孔相机。该相机朝向点p，且该相机坐标系的x轴和y轴分别与点p处局部参考坐标系的x轴和y轴对齐。进而将局部邻域点投影到虚拟相机的成像平面并记录这些点到成像平面的距离从而获得 snapshot 特征描述子。snapshot 特征描述子对自遮挡稳健且易于计算，其获得了比 spin image更好的成对点云配准结果。类似的，文献[5]首先定义一个LRF并采用一个规则的栅格对局部表面进行拟合，并采用局部表面在该栅格上的深度值作为局部特征描述子。最后，采用主成分分析（Principle Component Analysis，PCA）对该特征描述子做进一步压缩。
Castellani等[6]通过顺时针地将关键点p的一环（1-ring）邻域点连接起来，接着将二环及三环邻域点连接，不断重复该过程直到测地半径达到阈值r为止，从而获得关键点p周围的一个顺时针回形线。在该螺旋线上提取采样点的显著级别、最大曲率、最小曲率以及表面法向量变化量等属性，进而采用离散时间隐马尔科夫模型（Hidden Markov Model， HMM） 记录该螺旋线上的信息，从而获得 HMM 特征描述子。该 HMM 描述子对旋转、非均匀采样以及网格分辨率变化等十分稳健。实验结果表明其匹配性能优于spin image和3D shapecontext 特征描述子。
Steder 等[7, 8]首先将关键点p的邻域表面与该点的法向量对齐，然后采用一个星状模式图（star pattern）放置到该对齐的表面上。该星状模式图的每个束线即对应于Normal Aligned Radial Feature（NARF）特征描述子的一个值。NARF描述子记录了每个束线上的点变化量。为使得该特征描述子具有对旋转的不变性，该算法从特征描述子中提取一个唯一确定的方向并依据该方向对特征描述子进行移位操作。该 NARF 特征描述子的特征匹配性能优于spin image 特征描述子。
3.3.2 基于直方图的方法
这类方法首先利用点云的某些信息（如点坐标、几何属性）定义直方图的一个或多个维度，然后采用邻域点的几何或拓扑测量值（如点数、 网格面积）对直方图中的相应单元格进行累加从而获得直方图统计以实现对局部表面的描述[9]。这类方法可进一步细分为基于空间分布直方图、 基于几何属性直方图以及基于方向梯度直方图的方法。
这类方法依据局部邻域点的空间分布（如点坐标）获取直方图统计以实现局部表面描述。 这类方法首先在关键点上定义一个局部参考坐标框架或参考坐标轴，然后在该坐标系下将三维邻域空间划分成多个单元格，通过统计每个单元格上的空间分布测量值（如点数、网格面积）获得特征描述子。这类算法主要需解决两个问题，一是如何构建 LRF，二是如何对邻域空间进行划分。
spin image特征描述子对刚性变换、 背景干扰以及遮挡稳健[10]，且在点云配准、三维目标识别以及三维模型重建等多个场合得到了广泛应用。spin image已成为了三维局部特征描述子评估的事实基准[11-15]。但是，spin image依然存在许多缺陷：首先，spin image 特征对数据分辨率变化和非均匀采样敏感；其次，由于该特征的计算过程需要将三维点云投影到二维空间，因而维度信息的丢失使得其鉴别力有限。后续有大量算法对 spin image 特征描述子的各个方面进行改进，典型例子如基于面的 spin image[16]、spin image signature [17] 、多分辨率 spin image[18]、球形 spin image [19]、尺度不变 spin image [20]、以及颜色 spin image [21]。
Frome 等[22]将二维 shape context 特征描述子扩展到三维点云，从而获得三维形状上下文（3D Shape Context， 3DSC）特征描述子。该算法采用关键点 p 的法向量 n 作为局部参考坐标轴，并将球形邻域空间划分成一系列单元格。为获得对旋转的不变性， Tombari 等[23]对 3DSC 进行了改进，通过给每个关键点赋予一个可重复且唯一确定的 LRF 以获得单值形状上下文（Unique Shape Context， USC） 特征描述子。 实验结果表明， 相比于 3DSC， USC 对存储的要求显著降低，且特征匹配的性能有所提高。此外，Sukno 等[24]亦提出一种对水平面旋转具有不变性的非对称模式形状上下文（Asymmetry Patterns Shape Context，APSC）。实验结果表明 APSC 获得了与 3DSC 相当的性能。对二维 shape context的另一种改进是内蕴形状上下文（Intrinsic Shape Context， ISC）特征描述子， 该描述子具有对等距形变的不变性。
Mian 等[25]提出了一种 3D tensor 特征描述子。该算法首先选择一对满足特定几何约束的点构建局部参考坐标系，进而在该坐标系下进行空间三维栅格划分，并计算点云网格与每个栅格单元的相交面积从而得到 3D tensor 特征描述子。由于该算法采用表面面积而非点个数来获得直方图， 因此其对噪声和分辨率变化较为稳健。 实验结果表明该算法优于 spin image，其缺陷之一在于 LRF 的构建过程涉及网格顶点对的组合爆炸问题，因此运算量较大。
Zhong[26]提出了一种内蕴形状特征（Intrinsic Shape Signature， ISS）描述子。该算法首先对邻域点的协方差矩阵进行特征值分解从而构建 LRF， 进而采用离散球面网格将球形邻域空间划分成均匀分布的栅格。通过统计每个栅格单元内的点密度加权和从而获得 ISS 特征描述子。车辆识别实验结果表明，该算法在存在噪声、遮挡和背景干扰时的性能优于 spin image和3DSC。
这类算法依据关键点局部邻域的几何属性（如法向量及曲率）进行直方图统计从而获得特征描述子。
Yamany 和 Farag[14]采用单形角近似估计自由形状表面上的曲率，将关键点邻域的单形角累加到一个二维直方图中，从而得到 surface signature 特征描述子。实验结果表明 surface signature 优于splash、 point signature 和 spin image 特征描述子。
Chen 和 Bhanu[27]通过将关键点邻域的点数累加到一个二维直方图中从而获得 Local Surface Patches（LSP）特征描述子。LSP 特征描述子直方图的一维为邻域点的形状指数值， 另一维为关键点 p 法向量与邻域点法向量的夹角。实验结果表明 LSP 在三维目标识别应用中能获得与 spin image 相当的性能，但 LSP 的计算效率更高。
Flint 等[28]通过将关键点邻域的点数累加到由表面法向量夹角定义的一维直方图中从而获得 THRIFT 特征描述子。Flint 等在其后续工作[29]中对该算法进行了改进， 改进的算法采用关键点法向量与邻域点法向量的夹角计算加权直方图。 实验结果表明THRIFT 对噪声和点密度变化较稳健。
Taati等[30]对点云上每个点q的邻域点协方差矩阵进行主成分分析从而获得该点的 LRF 及三个特征值。在此基础上，利用每个点 q 的 LRF 和特征值获得一系列位置属性值、 方向属性值和散布属性值，进而采用特征选择算法从这些属性中选取部分属性，并将关键点 p 的邻域点属性值累加到一个直方图中，从而得到可变维度局部形状描述子（Variable Dimensional Local Shape Descriptor，VD-LSD）。Taati 和 Greenspan[31]亦给出了基于模型几何形状和传感器特性实现最优特征描述子选择的方法。实验结果表明，VD-LSD 在多个数据集上的识别率优于 spin image特征描述子。
Rusu 等提出了一种用于局部表面描述的 Point Feature Histograms（PFH） 特征描述子。 对于关键点 p 邻域内的一个点对，首先计算其 Darboux 框架，进而采用文献[32]的方法计算由法向量以及点对距离向量等得到的四个测量值。最后，将所有点对的测量值累加到一个长度为16的直方图中，即得到 PFH 特征描述子。 为提高 PFH 的计算效率， Rusu 等[33] 仅将兴趣点与其邻域点之间（而非所有邻域点对） 的四个测量值累加到一个直方图中，从而得到 Simplified Point Feature Histogram（SPFH）。最后将关键点 p 的所有邻域点 SPFH 进行加权求和得到 Fast Point Feature Histograms（FPFH） 特征描述子。 FPFH 保留了 PFH 中的绝大部分鉴别信息，且其计算复杂度明显降低。
Tombari 等[9]首先为关键点 p 构建一个 LRF， 进而在该坐标系下将球形邻域空间进行栅格化以获得多个三维栅格单元。 在每个栅格单元上， 依据落入该单元的点的法向量与关键点法向量的夹角将这些点累加到一个直方图中。最后，将所有栅格单元内的直方图串联起来以获得总的 Signature of Histograms of Orientations（SHOT）特征。SHOT 特征描述性强，计算效率高，且对噪声稳健。实验结果表明在各种噪声强度下的 SHOT 性能均优于 spin image 及 point signature 特征描述子。然而，该算法对数据分辨率变化较为敏感。 此后，Tombari 等[34]结合形状信息和颜色信息提出了Color-SHOT（CSHOT）特征描述子。 实验结果表明，将颜色（纹理）信息融合到几何特征描述子中有利于进一步提高其性能。
这类方法依据关键点的邻域点梯度方向构建直方图从而获得特征描述子。
Hua等[35]将三维点云网格映射到二维规范化域中，并将表面的平均曲率和保角因子投影到一个两通道的形状矢量图像中。对于每个通道，采用与尺度不变特征变换（Scale Invariant Feature Transform， SIFT）类似的方法提取特征描述子。首先将每个二维平面划分成 16个子区域，并在每个子区域中依据梯度方向获得一个八单元的直方图。最后，将两个通道中的所有直方图串联起来便得到最终的描述子。实验结果表明，该特征描述子较为稳健且可良好应用于点云匹配。
Zaharescu 等[36]首先在点云网格的顶点上定义一个标量函数 f 并计算该函数的梯度 ∇f ，该标量函数可以为曲率、法向量、密度以及纹理（强度）等。进而在每个关键点 p 处计算一个 LRF并将梯度向量投影到该坐标系三个相互正交的平面上，并将每个平面划分成四个子区域。在每个子区域中，依据梯度方向 ∇f 构建一个八单元的直方图。最后，将三个平面上所有子区域中得到的直方图连接起来便得到最终的网格方向梯度直方图（Mesh Histograms of Oriented Gradients，MeshHOG）特征描述子。MeshHOG 的有效性已通过刚性和非刚性物体的特征匹配得到验证。但是，MeshHOG 并不能应用于存在较大形变的物体。
Hou 和Qin[37]首先在点云网格的每个点上定义一个标量函数 f 并计算其梯度∇f。进而采用极坐标系 [d(q) , θ (q)] 对每个邻域点q进行表示，其中 d(q) 为从点p 到 q 的测地距离，θ (q) 为在局部切平面上从点 q 到 p 的主方向的极坐标角。接着，将该二维参数化平面分成九个子区域，并在每个子区域中依据梯度 ∇f 的方向构建一个八单元的直方图。最后将九个子区域中得到的直方图串联起来便得到了最终的特征描述子。匹配结果表明，该方法能获得比 MeshHOG更高的召回率和精度，且对存在较大等距形变的物体亦能得到较好的结果。
3.3.3 基于变换的方法
这类方法首先将点云从空间域变换到其它域（比如谱域），进而采用该变换域中的信息实现对关键点局部邻域的描述。
Hu 和 Hua[38]首先对局部表面点进行Laplace-Beltrami 变换从而获得局部表面的谱， 进而依据其谱分布构建直方图作为特征描述子。实验结果表明该特征描述子可很好地实现相似形状的匹配。此外，该特征描述子亦对刚性变换、等距形变以及尺度变化等具有不变性。Sun 等[39]提出了一种热核特征（Heat Kernel Signature，HKS）描述子。该算法将网格M当做一个黎曼流形，并将热核 K t (p, q) 限制在时域，即 K t (p, p) 。K t (p, p) 即为所求的 HKS 特征描述子。该特征描述子可看做是多尺度的高斯曲率，其中时间参数 t 给出了尺度信息。 HKS 是三维形状的内蕴属性， 其对等距形变具有较好的不变性。 在后续研究中， Bronstein 和 Kokkinos[40]提出了一种尺度不变 HKS 特征描述子用于非刚性形状检索，Kovnatsky等 [41]提出了一种包含光度信息的 HKS 特征描述子。
Knopp等[42]将二维图像中的加速稳健特征（Speeded Up Robust Feature，SURF）描述子推广到三维点云领域，得到 3D SURF 描述子。该算法首先将点云体素化以得到三维体图像， 并对该体图像进行Haar小波变换，并采用关键点p邻域的 Haar小波响应获得关键点 p 的局部参考坐标系。接着，将关键点邻域划分成N b × N b × N b个单元，在每个单元中提取向量 v =( ∑ h x ,∑h y ,∑h z ) ，其中h x、h y和h z分别为沿 x、y和z轴的 Haar小波响应。最后，将 N b × N b × N b个单元中的所有向量串联起来以获得 3D SURF 描述子。
综上所述，可得到如下简要结论：
①在三大类局部特征描述算法中，基于直方图的方法得到了最广泛地研究。在基于直方图的方法中，基于几何属性直方图和基于梯度方向直方图的方法均依赖于曲面的一阶或者二阶微分，因此这些方法对噪声较为敏感。
②为获得对刚性变换的不变性，大部分算法借助于 LRF 构建。这些算法首先在关键点上构建局部参考坐标系，进而将局部邻域点转换到该坐标系下。因此，LRF 的可重复性及稳健性对特征描述子的性能有很大的影响。
③为获得对等距形变的不变性，部分算法采用测地距离（或其 k 环近似）代替欧氏距离，另有部分算法则通过将点云变换到某个特定的域中以获得不变性，如 Laplace-Beltrami 谱域或时域。
④邻域大小对特征描述子的性能有较大影响。一个大的邻域半径可使特征描述子记录更多的形状信息，但同时也使特征描述子对遮挡和背景干扰更加敏感。部分算法为其特征描述子配置了相应的自适应关键点检测子。但事实上，可将任意两个关键点检测子和局部特征描述子进行搭配以寻找具有最优性能的组合。
⑤现有特征描述子难以同时获得高鉴别力、对噪声/数据分辨率/逸出噪声等干扰的强稳健性以及高计算效率。
点云分割与分类
点云分割与分类识别是三维目标检测的基础，也是目前的研究热点。三维点云分割是分类识别的基础。点云的分割与分类有一定区别，点云分割是根据空间，几何和纹理等特征点进行划分，使同一划分内的点云拥有相似的特征。点云分割的目的是分块，从而便于单独处理。点云的分类是为每个点分配一个语义标记，将点云分类到不同的点云集，同一个点云集具有相似或相同的属性，如法向量、曲率、树木、人等。
3.4.1 点云分割
三维点云的分割方法有很多种，一般主要有四种：基于边缘、区域增长、聚类、颜
色RGB值的分割方法，以下分别介绍。
Milroy[1]提出了一种新的确定边界方式，即首先确定边界点然后用能量等高线将各适界点连接起来即为边界，其中将正交截面模型中曲率最大值点作为边界点。刘胜兰[2]提出了利用三角网格模型中主方向上主曲率为极值的顶点为特征点并且以此为起点做出特征线的提取方法。张强[3]将局部临近点网格化，先将三角面片顶点的法向量调整为同一个方向，点的法向量是用加权平均相邻三角面片的法向量替代的，然后利用平面点云的同向性和共面性对点云数进行分割。龚友平通过估算曲率的极值寻找边界点，把边界点连线从而构建边界。Woo[4]使用八叉树对空间网格进行细分和法矢标准差的提取，实现了三维点云的分割。
基于边缘的分割方法速度快，对尖锐的边界比较敏感，但确定边界仅使用局部数据，所对于散乱的三维点云不能准确找到其边界，分割结果达不到一定标准。
该种分割方法实质是把相同特征的点划分为一个区域，而区域主要通过自上而下、自下而上两种方式不断迭代增长。自上而下方法是先选择种子片面或种子点，并且按一定准则向外延伸，确定邻近点是否在相同面，持续到邻域巧不存在连续点集，形成连接集合。而自下而上方法是先假设所有的点都在同一个面，拟合过程中误差不符合要求时，就把原集合分为两个集合。Kuo[5]等提出的DBRB（Delaunay-based Region-growing Algorithm）算法，该算法同时有Delaunay和区域增长的优点，先利用Delaunay构建三角片，角片为种子，不断扩大，其实质是通过迭代不断扩大三角片区域直到区域的边界。梁学章[6]等提出一种三角网络曲面的区域增长算法，先对点云进行预处理以达到数据精简的目的，然后在点云中选择新的匹配点构成新的三角形并连续更新边界以达到分割区域的不断增长。
基于区域增长的分割方法对由多项式表达的二次曲面分割更加有效。但在使用基于区域增长的分割方法时，由于需要选择种子点或者种子片面，很难选择合适的种子，并且很难区分光滑边界，而且由于很难选择合适的生长准则，受给定阀值影响大。其中自上而下的方法比较适用规则曲面的区域分割，自上而下的方法适用于数据点较少的。由于三维点云，往往场景很大，比较复杂，所以基于区域增长的分割方法适用情况有限。
该种分割方法属于多元统计分析，根据样本空间的特征，按照相似性和相似性测量准则对数据进行分类，使得同一类中的点有相同或者近似的属性，不同类别的点的属性不同。基于聚类的分割方法中常用的算法有：k-means算法，k-medoids算法，OPTIC算法，DENCLUE算法，STING算法，WAVE-CLUSTER算法，模糊聚类FCM。郭瑞[7]提出一种基于点的邻域信息（灰度值、邻域均方差、邻域均值、B值、熵值）的FCM分割算法。针对渐进式聚类，时收敛速度加快，抗噪性增强。Jean Koh[8]利用数据点的特征权值构成八维特征向量，其包括：数据点的坐标、法矢量、高斯曲率和平均曲率，利用多层自组织特征映射网络SOFM对八维特征向量来聚类，达到了区域分割的目的。刘雪梅[9]则添加法矢量、平均曲率以及高斯曲率来构成八维向量作为特征向量。
对于具有明显的曲面类型的数据进行分割，基于聚类的分割方法效果比较好，然而对于复杂环境和结构复杂的物体中，很难直接确定曲面的分类个数和曲面类型。
为了丰富分割方法，提高分割品质，万燕[10]等提出了一种基于HSV颜色空间的区域增长算法。该算法先求得区域增长的种子点同时确定分割的阈值，然后利用网格信息找到种子点的邻近点集，最后根据H分量的相似程度分割点云。Zhuo[11]提出了一个无监督分割算法平衡RGB-D图像中颜色和深度特性。输出部分包含可大可小的分割部分正确地表示了实物在场景中的位置，并且时间小于监督分割算法。Steven Hickson[12]提出一种无监督分层的分割算法，该算法对深度和颜色的结合体进行过分割，再用一棵树去合并过分割的区域。该方法准确地分割，并且质量得到一定提高。卢良锋[13]将深度学习和RGB、深度进行有效的结合，该方法提离了物体的识别准确率。
3.4.2 点云分类
依据获取特征的方式不同，本文将三维点云分类方法分为三大类：基于点的分类，基于传统机器学习方法的分类和基于深度学习的分类，并对各方法进行了详细地总结。
点签名法[14](Point Signature)，由 Chua 等人于 1994年提出。该方法根据每个点的球半径邻域与物体的交线 C 所拟合平面的法向量与参考矢量定义旋转角，从而计算签名距离，即每个点的签名，通过匹配签名实现分类。该方法消除了一阶导数的计算过程，但对噪声数据的处理效果较差。也有一些学者利用形状特征对点云进行识别，如旋转图像[15-16]和体素网格[17]