7、关键点
关键点也称为兴趣点，它是 2D 图像或 3D 点云或曲面模型上，可以通过定义检测标准来获取的具有稳定性、区别性的点集。 从技术上来说，关键点的数量相比于原始点云或图像的数据量减小很多，与局部特征描述子结合一起，组成关键点描述子常用来形成原始数据的紧凑表示，而且不失代表性与描述性，从而加快后续识别、追踪等对数据的处理速度。 固而，关键点提取就成为 2D 与 3D 信息处理中不可或缺的关键技术。
NARF(Normal Aligned Radial Feature, 归一化对齐径向特征）关键点是为了从深度图像中识别物体而提出的，关键点探测的重要一步是减少特征提取时的搜索空间，把重点放在重要的结构上，对NARF关键点提取过程有以下要求：①提取的过程必须考虑边缘以及物体表面变化信息在内；②关键点的位置必须稳定的可以被重复探测，即使换了不同的视角；③关键点所在的位置必须有稳定的支持区域，可以计算描述子和进行唯一的估计法向量。为了满足上述要求，提出以下探测步骤来进行关键点提取：
(1)遍历每个深度图像点，通过寻找在近邻区域有深度突变的位置进行边缘检测。
(2)遍历每个深度图像点，根据近邻区域的表面变化决定——测度表面变化的系数，以及变化的主方向。
(3)根据第二步找到的主方向计算兴趣值 ，表征该方向与其他方向的不同，以及该处表面的变化情况，即该点有多稳定。
(4)对兴趣值进行平滑过滤。
(5)进行无最大值压缩找到最终的关键点，即为 NARF 关键点。
8、采样一致性算法
在计算机视觉领域广泛应用各种不同的采样一致性参数估计算法用于排除错误的样本，样本不同对应的应用则不同，例如剔除错误的配准点对、分割出处在模型上的点集等。 PCL中以随机采样一致性算法（RANSAC）为核心，同时实现了五种类似于随机采样一致性估计参数算法的随机参数估计算法，例如随机采样一致性估计(RANSAC）、最大似然一致性估计（MLESAC）、最小中值方差一致性估计（LMEDS) 等，所有的估计参数算法都符合一致性准则。 本章涉及的基于采样一致性算法的应用主要是对点云进行分割，根据设定不同的几何模型，估计对应的几何模型的参数，在一定允许误差范围内分割出在模型上的点云，但本章并非讲述点云分割，而是主要对采样一致性相关的介绍，关于分割的详细内容见点云分割部分，目前PCL中支持的几何模型分割有空间平面、直线、二维或三维圆周、圆球、锥体等。随机采样一致性估计的另一应用就是点云的配准对的剔除，可参考点云配准部分。
（1）RANSAC随机采样一致性算法简介
RANSAC是一种随机参数估计算法。 RANSAC从样本中随机抽选出一个样本子集，使用最小方差估计算法对这个子集计算模型参数，然后计算所有样本与该模型的偏差，再使用一个预先设定好的阀值与偏差比较，当偏差小于阀值时，该样本点属于模型内样本点（inliers），文中简称局内点或内点，否则为模型外样本点（outliers) 一次文中简称局外点或外点，记录下当前的inliers的个数，然后重复这一过程。每一次重复都记录当前最佳的模型参数，所谓最佳即是inliers的个数最多，此时对应的inliers个数为best_ninliers。每次迭代的末尾都会根据期望的误差率、best_ninliers、总样本个数、当前迭代次数，计算一个迭代结束评判因子，据此决定是否迭代结束。迭代结束后，最佳模型参数就是最终的模型参数估计值。
RAN SAC 理论上可以剔除 outliers 的影响，并得到全局最优的参数估计。 但是RAN SAC 有两个问题，首先在每次迭代中都要区分 inliers 和 outlieres，因此需要事先设定阀值，当模型具有明显的物理意义时，这个阀值还比较容易设定，但是若模型比较抽象时，这个阀值就不那么容易设定了，而且固定阀值不适用于样本动态变化的应用；第二个问题是，RANSAC 的迭代次数是运行期决定的，不能预知迭代的确切次数（当然迭代次数的范围是可以预测的）。 除此之外，RANSAC 只能从一个特定数据集中估计一个模型，当两个（或者更多个）模型存在时，RANSAC 不能找到别的模型。
下图展示了 RANSAC 算法在二维数据集中的简单应用。
（a）的图像形象地表示了一组既包含局内点又包含局外点的数据集。
（b）的图像中所有的局外点都表示为红色，局内点表示为蓝色，蓝色线就是基于 RANSAC 得到的结果，此例中我们尝试适应数据的模型就是一条线。
（2）LMedS最小中值方差估计算法
LMedS 也是一种随机参数估计算法。 LMedS 也从样本中随机抽选出一个样本子集，使用最小方差估计算法对子集计算模型参数，然后计算所有样本与该模型的偏差。 但是与 RANSAC 不同的是， LMedS 记录的是所有样本中偏差值居中的那个样本的偏差，称为 Med 偏差（这也是 LMedS 中 Med 的由来），以及本次计算得到的模型参数。 由于这一变化，LMedS 不需要预先设定阀值来区分 inliers 和 outliers. 重复前面的过程N次，从中N个 Med 偏差中挑选出最小的一个，其对应的模型参数就是最终的模型参数估计值。 其中迭代次数N是由样本子集中样本的个数、期望的模型误差、事先估计的样本中 outliers 的比例所决定。
LMedS 理论上也可以剔除 outliers 的影响，并得到全局最优的参数估计，而且克服了 RANSAC 的两个缺点（虽然 LMedS 也需要实现设定样本中 outliers 的比例，这个数字比较容易设定〉。但是当outliers在样本中所占比例达到或超过50%时，LMedS就无能为力了！这与LMedS每次迭代记录的是Med偏差值有关！
（3）几何模型
除了RANSAC以外，还有模型比如平面和圆柱体，它们可以自由组合。模型包括：线，面，圆柱和球。平面用于室内平面如墙，地板和桌面；其他几何模型能用于检测和分割物体如用圆柱体模型分割马克杯。
9、点云特征描述与提取
其实就是点云是个什么东西即特征，有很多办法来说明或描述。
3D点云特征描述与提取是点云信息处理中的最基础也是最关键的的一部分，点云识别、分割、重采样、配准、曲面重建等处理大部分算法，都严重依赖特征描述与提取的结果。从尺度上来分，一般分为局部特征描述和全局特征描述，例如局部的法线、等几何形状特征的描述，全局的拓扑特征描述，都属于3D点云特征描述与提取范畴。在PCL中，目前已有很多基本的特征描述子与提取算法，相信在社区的快速增长下会集成和添加更多特征描述子和提取算法。
（1）30形状内容描述子（3D shape contexts)
利用描述子建立曲面间的对应点在 3D 物体识别领域有广泛应用 。采用一个向量描述曲面上指定点及其邻域的形状特征，通过匹配向量的值来建立不同曲面间点的对应关系，此向量即为指定点的描述子，经典描述子 3D 形状内容描述子构造简单，辨别力强，且对噪声不敏感。
点云是一个球
旋转图像最早是Joh ns on提出的特征描述子，主要用于3D场景中的曲面匹配和模型识别。 如下图所示，在模型表面上，存在顶点p和其法向量n定义的二维基，以及切平面P，假设模型上任意顶点x，现定义α 为x在平面P上投影点与p点 的距离，规定其值取大于零的实数，β为x与其在平面P上投影点之间的距离，按照向上或向下规定其有正负之分。 点p的旋转图像则为，将除p点外其他模型上的顶点在P上的投影（αi，βi），其中i表示顶点的一维索引，将（αi，βi）统计得到二维直方图,即为点p的旋转图像，图像的坐标由α和β而定，强度为（α，β）落在同一统计区间的点的统计个数，图中有所示模型表面三个点的旋转图像。
这是点云某个面的投影形状
在原始表示形式下，点的定义是用笛卡尔坐标系坐标 x, y, z 相对于一个给定的原点来简单表示的三维映射系统的概念。假定坐标系的原点不随着时间而改变，这里有两个点p1和p2分别在时间t1和t2捕获，有着相同的坐标，对这两个点作比较其实是属于不适定问题（ill-posed problem），因为虽然相对于一些距离测度它们是相等的，但是它们取样于完全不同的表面，因此当把它们和临近的其他环境中点放在一起时，它们表达着完全不同的信息，这是因为在t1和t2之间局部环境有可能发生改变。一些获取设备也许能够提供取样点的额外数据，例如强度或表面反射率等，甚至颜色，然而那并不能完全解决问题。单从两个点之间来，对比仍然是不适定问题。由于各种不同需求需要进行对比以便能够区分曲面空间的分布情况，应用软件要求有更好的特征度量方式，因此作为一个单一实体的三维点概念和笛卡尔坐标系被淘汰了，出现了一个新的概念取而代之：局部描述子（local descriptor）。文献中对这一概念的描述有许多种不同的命名，如：形状描述子（shape descriptors）或几何特征（geometric features），文本中剩余部分都统称为点特征表示。通过包括周围的领域，特征描述子能够表征采样表面的几何性质，它有助于解决不适定的对比问题，理想情况下相同或相似表面上的点的特征值将非常相似（相对特定度量准则），而不同表面上的点的特征描述子将有明显差异。下面几个条件，通过能否获得相同的局部表面特征值，可以判定点特征表示方式的优劣：
平移选转不变性（刚体变换）：即三维旋转和三维平移变化 不会影响特征向量F估计，即特征向量具有
抗密度干扰性（改变采样密度）：原则上，一个局部表面小块的采样密度无论是大还是小，都应该有相同的特征向量值
对噪声具有稳定性（噪声）：数据中有轻微噪声的情况下，点特征表示在它的特征向量中必须保持相同或者极其相似的值
通常，PCL中特征向量利用快速 kd-tree 查询 ，使用近似法来计算查询点的最近邻元素，通常有两种查询类型：K邻域查询，半径搜索两中方法
②估计一个点云的表面法线
表面法线是几何体表面一个十分重要的属性，例如：在进行光照渲染时产生符合可视习惯的效果时需要表面法线的信息才能正常进行，对于一个已经知道的几何体表面，根据垂直于点表面的的矢量，因此推断处表面某一点的法线方向比较容易，然而由于我们获取的点云的数据集在真实的物体的表面表现为一组定点的样本，这样就会有两种方法解决：
使用曲面重建技术，从获取的点云数据中得到采样点对应的曲面，然后从曲面模型中计算出表面法线
直接从点云数据中近似推断表面法线
在确定表面一点法线的问题近似于估计表面的一个相切面法线的问题，因此转换过来就是求一个最小二乘法平面拟合的问题
③使用积分图进行法线估计
使用积分图进行法线估计，使用积分图计算一个有序的点云的法线，注意此方法只适用有序点云。
有序点云是什么
一帧扫描数据是一副深度图，属于灰度图。像素的灰度值代表的是深度信息，可以通过相机参数把每个像素点变换到世界坐标系，这样每个像素就对应一个三维点，有些点是无效的，一般用(0, 0, 0)来代替。下图是一个典型的深度点云。假设深度图的分辨率是ResX * ResY，那么有序点云按照图方阵一行一行的，从左上角到右下角排列。
④点特征直方图（PFH）描述子
正如点特征表示法所示，表面法线和曲率估计是某个点周围的几何特征基本表示法。虽然计算非常快速容易，但是无法获得太多信息，因为它们只使用很少的几个参数值来近似表示一个点的k邻域的几何特征。然而大部分场景中包含许多特征点，这些特征点有相同的或者非常相近的特征值，因此采用点特征表示法，其直接结果就减少了全局的特征信息。那么三维特征描述子中一位成员：点特征直方图(Point Feature Histograms)，我们简称为PFH，从PCL实现的角度讨论其实施细节。PFH特征不仅与坐标轴三维数据有关，同时还与表面法线有关。
PFH计算方式通过参数化查询点与邻域点之间的空间差异，并形成一个多维直方图对点的k邻域几何属性进行描述。直方图所在的高维超空间为特征表示提供了一个可度量的信息空间，对点云对应曲面的6维姿态来说它具有不变性，并且在不同的采样密度或邻域的噪音等级下具有鲁棒性。点特征直方图（PFH）表示法是基于点与其k邻域之间的关系以及它们的估计法线，简言之，它考虑估计法线方向之间所有的相互作用，试图捕获最好的样本表面变化情况，以描述样本的几何特征。因此，合成特征超空间取决于每个点的表面法线估计的质量。如下图所示，表示的是一个查询点(Pq) 的PFH计算的影响区域，Pq 用红色标注并放在圆球的中间位置，半径为r， (Pq)的所有k邻元素（即与点Pq的距离小于半径r的所有点）全部互相连接在一个网络中。最终的PFH描述子通过计算邻域内所有两点之间关系而得到的直方图，因此存在一个O(k) 的计算复杂性。
计算k邻域内的每一对点的 （α，Φ，θ，d）四组值，这样就把两点和它们法线相关的12个参数（xyz坐标值和法线信息（旋转参数））减少到4个，如上图。
为查询点创建最终的PFH表示，所有的四元组将会以某种统计的方式放进直方图中，这个过程首先把每个特征值范围划分为b个子区间，并统计落在每个子区间的点数目，因为3/4的特征在上述中为法线之间 的角度计量，在三角化圆上可以将它们的参数值非常容易地归一到相同的区间内。 一个统计的例子是：把每个特征区间划分成等分的相同数目，为此在一个完全关联的空间内创建有b4个区间的直方图。 在这个空间中，一个直方图中某一区间统计个数对应一个点的4个特征值。 如下图所示，就是点云中不同点的点特征直方图表示法的一个例子，在某些情况下，第4个特征量 d在通常由机器人捕获的2. 5 维数据集中的并不重要，因为临近点间的距离从视点开始是递增的，而并非不变的，在扫描中局部点密度影响特征时，实践证明省略d是有益的。
白话理解：每个点都有1个直方图，统计某个半径内邻域所有点对的特征值。PCL默认每个特征值是5个区间，那么将有53（125）个特征向量空间，落在这125个特征向量空间的个数，不同的物体那么直方图不同，相同物体的直方图是相同或近似的，见上图圆柱体和小平板的点云特征直方图。
⑤快速点特征直方图(FPFH)描述子
已知点云P中有n个点，那么它的点特征直方图（PFH）的理论计算复杂度是O（nk2），其中k是点云P中每个点p计算特征向量时考虑的邻域数量。对于实时应用或接近实时应用中，密集点云的点特征直方图（PFH）的计算是一个主要的性能瓶颈。此处为PFH计算方式的简化形式，称为快速点特征直方图FPFH（Fast Point Feature Histograms），计算复杂度降为O（nk）。
它与PFH的主要区别为：
(1) FPFH没有对全互连Pq 点的所有邻近点的计算参数进行统计，从下图中可以看到，因此可能漏掉了一些重要的点对，而这些漏掉的对点可能对捕获查询 周围的几何特征有贡献。
(2) PFH特征模型是对查询点周围的一个精确的邻域半径内，而FPFH还包括半径r范围以外的额外点对（不过在2r内 ）。
(3） 因为重新权重计算的方式，所以FPFH结合SPFH值，重新捕获邻近重要点对的几何信息。
(4）由于大大地降低了PFH的整体复杂性，因此FPFH有可能使用在实时应用中。
(5）通过分解三元组简化了合成的直方图。 也就是简单生成d分离特征直方图，对每个特征维度来单独绘制，并把它们连接在一起。
⑥估计一点云的VFH特征
视点特征直方图（或VFH）是源于FPFH描述子（见Fast Point Feature Histograms (PFH) 描述子）。由于它的获取速度和识别力，我们决定利用FPFH强大的识别力，但是为了使构造的特征保持缩放不变性的性质同时，还要区分不同的位姿，计算时需要考虑加入视点变量。我们做了以下两种计算来构造特征，以应用于目标识别问题和位姿估计：1.扩展FPFH，使其利用整个点云对象来进行计算估计（如下图所示），在计算FPFH时以物体中心点与物体表面其他所有点之间的点对作为计算单元。2.添加视点方向与每个点估计法线之间额外的统计信息，为了达到这个目的，我们的关键想法是在FPFH计算中将视点方向变量直接融入到相对法线角计算当中。
通过统计视点方向与每个法线之间角度的直方图来计算视点相关的特征分量。注意：并不是每条法线的视角，因为法线的视角在尺度变换下具有可变性，我们指的是平移视点到查询点后的视点方向和每条法线间的角度。第二组特征分量就是前面PFH中讲述的三个角度，如PFH小节所述，只是现在测量的是在中心点的视点方向和每条表面法线之间的角度。
视点分量+FPHF分量
因此新组合的特征被称为视点特征直方图（VFH）。下图表体现的就是新特征的想法，包含了以下两部分：
1.一个视点方向相关的分量
2.一个包含扩展FPFH的描述表面形状的分量
视点特征直方图在PCL中的实现属于pcl_features模块库的一部分。对扩展的FPFH分量来说，默认的VFH的实现使用45个子区间进行统计，而对于视点分量要使用128个子区间进行统计，这样VFH就由一共308（45*4+128）个浮点数组成阵列。
最后推荐国防科技大学郭裕兰博士的《点云局部特征描述与三维目标重建识别技术研究》，将特征描述的本质说出来了：
一个良好的特征描述子应能包含所在局部表面的主要形状信息以提供足量的 鉴别力。此外，一个良好的特征描述子还应对噪声、遮挡、背景干扰、点密度变 化以及视点变化等稳健。现有的局部特征描述算法可以分为基于点特性、基于直方图以及基于变换的算法三类。
基于变换的算法首先将点云从空间域变换到其它域（比如谱域），进而采用该变换域 中的信息实现对关键点局部邻域的描述。
论文已经上传至CSDN，欢迎下载。