######################################################################
############################################################################
关键点也称为兴趣点，它是2D图像或是3D点云或者曲面模型上，
可以通过定义检测标准来获取的具有稳定性，
区别性的点集。
我们都知道在二维图像上，
有
Harris、
SIFT、
SURF、
KAZE
这样的关键点提取算法，
这种特征点的思想可以推广到三维空间。
关键点的数量相比于原始点云或图像的数据量减小很多，与局部特征描述子结合在一起，
组成 关键点描述子 常用来形成原始数据的表示，而且不失代表性和描述性，
从而加快了后续的识别，追踪等对数据的处理了速度，
故而，关键点技术成为在2D和3D 信息处理中非常关键的技术。
ISS3D、
Harris3D、
NARF、
SIFT3D
这些算法在PCL库中都有实现，其中NARF算法是博主见过用的比较多的。
关键点检测往往需要和特征提取联合在一起，
关键点检测的一个重要性质就是旋转不变性，
也就是说，物体旋转后还能够检测出对应的关键点。
不过说实话我觉的这个要求对机器人视觉来说是比较鸡肋的。
因为机器人采集到的三维点云并不是一个完整的物体，没哪个相机有透视功能。
机器人采集到的点云也只是一层薄薄的蒙皮。所谓的特征点又往往在变化剧烈的曲面区域，
那么从不同的视角来看，变化剧烈的曲面区域很难提取到同样的关键点。
想象一下一个人的面部，正面的时候鼻尖可以作为关键点，但是侧面的时候呢？
会有一部分面部在阴影中，模型和之前可能就完全不一样了。
也就是说现在这些关键点检测算法针对场景中较远的物体，
也就是物体旋转带来的影响被距离减弱的情况下，是好用的。
一旦距离近了，旋转往往造成捕获的仅有模型的侧面，关键点检测算法就有可能失效。
PCL中keypoints模块及类的介绍:
（1）class pcl::Keypoint<PointInT,PointOutT> 类keypoint是所有关键点检测相关类的基类，
定义基本接口，具体实现由子类来完成，
其继承关系时下图：
pcl::PCLBase<PointInT>
|
|___-> pcl::Keypoint<PointInT,PointOutT>
|
|
|
|___->pcl::AgastKeypoint2DBase<PointInT,PointOutT, pcl::common::IntensityFieldAccessor<PointInT >>
->pcl::AgastKeypoint2DBase<PointInT,PointOutT, IntensityT >
->pcl::BriskKeypoint2D<PointInT,PointOutT, IntensityT >
->pcl::HarrisKeypoint2D<PointInT,PointOutT, IntensityT >
->pcl::HarrisKeypoint3D<PointInT,PointOutT, IntensityT >
->pcl::HarrisKeypoint6D<PointInT,PointOutT, IntensityT >
->pcl::ISSKeypoint3D<PointInT,PointOutT, IntensityT >
->pcl::SIFTKeypoint<PointInT,PointOutT >
->pcl::SUSANKeypoint<PointInT,PointOutT, NormalT, IntensityT >
->pcl::TrajkovicKeypoint2D<PointInT,PointOutT, IntensityT >
->pcl::TrajkovicKeypoint3D<PointInT,PointOutT, IntensityT >
方法：
virtual void setSearchSurface (const PointCloudInConstPtr &cloud)
设置搜索时所用搜索点云，cloud为指向点云对象的指针引用
void setSearchMethod (const KdTreePtr &tree)
设置内部算法实现时所用的搜索对象，tree为指向kdtree或者octree对应的指针
void setKSearch (int k)
设置K近邻搜索时所用的K参数
void setRadiusSearch (double radius)
设置半径搜索的半径的参数
int searchForNeighbors (int index, double parameter, std::vector< int > &indices, std::vector< float > &distances) const
采用setSearchMethod设置搜索对象，以及setSearchSurface设置搜索点云，进行近邻搜索，返回近邻在点云中的索引向量，
indices以及对应的距离向量distance其中为查询点的索引，parameter为搜索时所用的参数半径或者K
类HarrisKeypoint2D实现基于点云的强度字段的harris关键点检测子，其中包括多种不同的harris关键点检测算法的变种，其关键函数的说明如下：
HarrisKeypoint2D (ResponseMethod method=HARRIS,
int window_width=3,
int window_height=3,
int min_distance=5,
float threshold=0.0)
重构函数，method需要设置采样哪种关键点检测方法，有HARRIS，NOBLE，LOWE，WOMASI四种方法，默认为HARRIS，
window_width window_height为检测窗口的宽度和高度
min_distance 为两个关键点之间 容许的最小距离，
threshold为判断是否为关键点的感兴趣程度的阀值，小于该阀值的点忽略，大于则认为是关键点
void setMethod (ResponseMethod type)
设置检测方式
void setWindowWidth (int window_width)
设置检测窗口的宽度
void setWindowHeight (int window_height)
设置检测窗口的高度
void setSkippedPixels (int skipped_pixels)
设置在检测时每次跳过的像素的数目
void setMinimalDistance (int min_distance)
设置候选关键点之间的最小距离
void setThreshold (float threshold)
设置感兴趣的阀值
void setNonMaxSupression (bool=false)
设置是否对小于感兴趣阀值的点进行剔除，如果是true则剔除,否则返回这个点
void setRefine (bool do_refine)
设置是否对所得的关键点结果进行优化，
void setNumberOfThreads (unsigned int nr_threads=0)
设置该算法如果采用openMP并行机制，能够创建线程数目
类HarrisKeypoint3D和HarrisKeypoint2D类似，但是没有在点云的强度空间检测关键点，
而是利用点云的3D空间的信息表面法线向量来进行关键点检测，
关于HarrisKeypoint3D的类与HarrisKeypoint2D相似，除了
HarrisKeypoint3D (ResponseMethod method=HARRIS, float radius=0.01f, float threshold=0.0f)
重构函数，method需要设置采样哪种关键点检测方法，有HARRIS，NOBLE，LOWE，WOMASI四种方法，
默认为HARRIS，radius为法线估计的搜索半径，
threshold为判断是否为关键点的感兴趣程度的阀值，小于该阀值的点忽略，大于则认为是关键点。
类HarrisKeypoint6D和HarrisKeypoint2D类似，只是利用了欧式空间域XYZ或者强度域来候选关键点，
或者前两者的交集，即同时满足XYZ域和强度域的关键点为候选关键点，
HarrisKeypoint6D (float radius=0.01, float threshold=0.0)
重构函数，此处并没有方法选择的参数，而是默认采用了Tomsai提出的方法实现关键点的检测，
radius为法线估计的搜索半径，
threshold为判断是否为关键点的感兴趣程度的阀值，小于该阀值的点忽略，大于则认为是关键点。
##4. pcl::SIFTKeypoint< PointInT, PointOutT >
类SIFTKeypoint是将二维图像中的SIFT算子调整后移植到3D空间的SIFT算子的实现，
输入带有XYZ坐标值和强度的点云，输出为点云中的SIFT关键点，其关键函数的说明如下：
void setScales (float min_scale, int nr_octaves, int nr_scales_per_octave)
设置搜索时与尺度相关的参数，
min_scale在点云体素尺度空间中标准偏差，点云对应的体素栅格中的最小尺寸
int nr_octaves是检测关键点时体素空间尺度的数目，
nr_scales_per_octave为在每一个体素空间尺度下计算高斯空间的尺度所需要的参数
void setMinimumContrast (float min_contrast) 设置候选关键点对应的对比度下限
pcl::UniformSampling<PointType> uniform_sampling;//下采样滤波模型
uniform_sampling.setInputCloud (model);//模型点云
uniform_sampling.setRadiusSearch (model_ss_);//模型点云搜索半径
uniform_sampling.filter (*model_keypoints);//下采样得到的关键点
我们都知道在二维图像上，有Harris、SIFT、SURF、KAZE这样的关键点提取算法，
这种特征点的思想可以推广到三维空间。
关键点的数量相比于原始点云或图像的数据量减小很多，与局部特征描述子结合在一起，
组成 关键点描述子 常用来形成原始数据的表示，而且不失代表性和描述性，
从而加快了后续的识别，追踪等对数据的处理了速度，
故而，关键点技术成为在2D和3D 信息处理中非常关键的技术。
这些算法在PCL库中都有实现，其中NARF算法是博主见过用的比较多的。
PCL—低层次视觉—关键点检测
关键点检测往往需要和特征提取联合在一起，关键点检测的一个重要性质就是旋转不变性，
也就是说，物体旋转后还能够检测出对应的关键点。不过说实话我觉的这个要求对机器人视觉来说是比较鸡肋的。
因为机器人采集到的三维点云并不是一个完整的物体，没哪个相机有透视功能。
机器人采集到的点云也只是一层薄薄的蒙皮。所谓的特征点又往往在变化剧烈的曲面区域，
那么从不同的视角来看，变化剧烈的曲面区域很难提取到同样的关键点。
想象一下一个人的面部，正面的时候鼻尖可以作为关键点，但是侧面的时候呢？
会有一部分面部在阴影中，模型和之前可能就完全不一样了。
也就是说现在这些关键点检测算法针对场景中较远的物体，
也就是物体旋转带来的影响被距离减弱的情况下，是好用的。
一旦距离近了，旋转往往造成捕获的仅有模型的侧面，关键点检测算法就有可能失效。
---------------------------------------------------------------------------
说内部，那必然要有个范围，具体是什么东西的范围还暂定。
如果说要描述一个点周围的局部特征，而且这个物体在全局坐标下还可能移动，
那么有一个好方法就是在这个点周围建立一个局部坐标。
只要保证这个局部坐标系也随着物体旋转就好。
协方差矩阵的思想其实很简单，实际上它是一种耦合，把两个步骤耦合在了一起
1.把pi和周围点pj的坐标相减：本质上这生成了许多从pi->pj的向量，
理想情况下pi的法线应该是垂直于这些向量的
2.利用奇异值分解求这些向量的0空间，拟合出一个尽可能垂直的向量，作为法线的估计
协方差矩阵本质是啥？就是奇异值分解中的一个步骤。。。。
奇异值分解是需要矩阵乘以自身的转置从而得到对称矩阵的。
当然，用协方差计算的好处是可以给不同距离的点附上不同的权重。
1.把点的坐标转为齐次坐标
2.对其次坐标进行奇异值分解
3.最小奇异值对应的向量就是拟合平面的方程
4.方程的系数就是法线的方向。
显然，这种方法更加简单粗暴，省去了权重的概念，但是换来了运算速度，不需要反复做减法。
其实本来也不需要反复做减法，做一个点之间向量的检索表就好。。。
但是我要声明PCL的实现是利用反复减法的。
都会有三个相互垂直的向量，一个是法线方向，另外两个方向与之构成了在某点的局部坐标系。
在此局部坐标系内进行建模，就可以达到点云特征旋转不变的目的了。
1.利用方法1建立模型
2.其利用特征值之间关系来形容该点的特征程度。
显然这种情况下的特征值是有几何意义的，特征值的大小实际上是椭球轴的长度。
椭球的的形态则是对邻近点分布状态的抽象总结。
试想，如果临近点沿某个方向分布致密则该方向会作为椭球的第一主方向，
稀疏的方向则是第二主方向，法线方向当然是极度稀疏（只有一层），那么则作为第三主方向。
如果某个点恰好处于角点，则第一主特征值，第二主特征值，第三主特征值大小相差不会太大。
如果点云沿着某方向致密，而垂直方向系数则有可能是边界。
总而言之，这种局部坐标系建模分析的方法是基于特征值分析的特征点提取。
-----------------------------------------------------------------------
角点的一个重要特征就是法线方向和周围的点存在不同，
而本算法的思想就是和相邻点的法线方向进行对比，判定法线方向差异的阈值，
最终决定某点是否是角点。并且需要注意的是，本方法所针对的点云应该只是有序点云。
本方法的优点是快，缺点是对噪声敏感。
手头没有有序点云，不做测试了。
除去NARF这种和特征检测联系比较紧密的方法外，一般来说特征检测都会对曲率变化比较剧烈的点更敏感。
Harris算法是图像检测识别算法中非常重要的一个算法，其对物体姿态变化鲁棒性好，
对旋转不敏感，可以很好的检测出物体的角点。
甚至对于标定算法而言，HARRIS角点检测是使之能成功进行的基础。
HARRIS算法的思想还是很有意思的。很聪明也很trick.
--------------------------------------------------------------------
其思想及数学推导大致如下：
1.在图像中取一个窗 w (矩形窗，高斯窗，XX窗，各种窗，
某师姐要改标定算法不就可以从选Harris的窗开始做起么）
2.获得在该窗下的灰度 I
3.移动该窗，则灰度会发生变化，平坦区域灰度变化不大，
边缘区域沿边缘方向灰度变化剧烈，角点处各个方向灰度变化均剧烈
4.依据3中条件选出角点
1.两个特征值都很大==========>角点（两个响应方向）
2.一个特征值很大，一个很小===>边缘（只有一个响应方向）
3.两个特征值都小============>平原地区（响应都很微弱）
---------------------------------------------------------------------------
在2DHarris里，我们使用了 图像梯度构成的 协方差矩阵。
图像梯度。。。嗯。。。。每个像素点都有一个梯度，
在一阶信息量的情况下描述了两个相邻像素的关系。显然这个思想可以轻易的移植到点云上来。
想象一下，如果在 点云中存在一点p
1、在p上建立一个局部坐标系：z方向是法线方向，x,y方向和z垂直。
2、在p上建立一个小正方体，不要太大，大概像材料力学分析应力那种就行
3、假设点云的密度是相同的，点云是一层蒙皮，不是实心的。
a、如果小正方体沿z方向移动，那小正方体里的点云数量应该不变
b、如果小正方体位于边缘上，则沿边缘移动，点云数量几乎不变，沿垂直边缘方向移动，点云数量改
c、如果小正方体位于角点上，则有两个方向都会大幅改变点云数量
如果由法向量x,y,z构成协方差矩阵，那么它应该是一个对称矩阵。
而且特征向量有一个方向是法线方向，另外两个方向和法线垂直。
那么直接用协方差矩阵替换掉图像里的M矩阵，就得到了点云的Harris算法。
其中，半径r可以用来控制角点的规模
r小，则对应的角点越尖锐（对噪声更敏感）
r大，则可能在平缓的区域也检测出角点
----------------------------------------------------------------------
1. 边缘提取
对点云而言，场景的边缘代表前景物体和背景物体的分界线。
所以，点云的边缘又分为三种：
前景边缘，背景边缘，阴影边缘。
三维点云的边缘有个很重要的特征，
就是点a 和点b 如果在 rangImage 上是相邻的，然而在三维距离上却很远，那么多半这里就有边缘。
由于三维点云的规模和稀疏性，“很远”这个概念很难描述清楚。
到底多远算远？这里引入一个横向的比较是合适的。这种比较方法可以自适应点云的稀疏性。
所谓的横向比较就是和 某点周围的点相比较。 这个周围有多大？不管多大，
反正就是在某点pi的rangeImage 上取一个方窗。
假设像素边长为s. 那么一共就取了s^2个点。
接下来分三种情况来讨论所谓的边缘：
1.这个点在某个平面上，边长为 s 的方窗没有涉及到边缘
2.这个点恰好在某条边缘上，边长 s 的方窗一半在边缘左边，一半在右边
3.这个点恰好处于某个角点上，边长 s 的方窗可能只有 1/4 与 pi 处于同一个平面
如果将 pi 与不同点距离进行排序，得到一系列的距离，d0 表示与 pi 距离最近的点，显然是 pi 自己。
ds^2 是与pi 最远的点，这就有可能是跨越边缘的点了。
选择一个dm，作为与m同平面，但距离最远的点。
也就是说，如果d0~ds^2是一个连续递增的数列，那么dm可以取平均值。
如果这个数列存在某个阶跃跳动（可能会形成类似阶跃信号）
那么则发生阶跃的地方应该是有边缘存在，不妨取阶跃点为dm(距离较小的按个阶跃点）
原文并未如此表述此段落，原文取s=5, m=9 作为m点的一个合理估计。
-------------------------------------------------------------------------------
在提取关键点时，边缘应该作为一个重要的参考依据。
但一定不是唯一的依据。对于某个物体来说关键点应该是表达了某些特征的点，而不仅仅是边缘点。
所以在设计关键点提取算法时，需要考虑到以下一些因素：
1.边缘和曲面结构都要考虑进去，提取的过程考虑边缘以及物体表面变化信息；
2.关键点要能重复,在不同视角关键点可以被重复探测；
3.关键点最好落在比较稳定的区域，方便提取法线，关键点所在位置有足够的支持区域，可以计算描述子和进行唯一的估计法向量。
其对应的探测步骤如下：
(1) 遍历每个深度图像点，通过寻找在近邻区域有深度变化的位置进行边缘检测。
(2) 遍历每个深度图像点，根据近邻区域的表面变化决定一-测度表面变化的系数，及变化的主方向。
(3) 根据step(2)找到的主方向计算兴趣点，表征该方向和其他方向的不同，以及该处表面的变化情况，即该点有多稳定。
(4) 对兴趣值进行平滑滤波。
(5) 进行无最大值压缩找到的最终关键点，即为NARF关键点。
对于点云构成的曲面而言，某处的曲率无疑是一个非常重要的结构描述因素。
某点的曲率越大，则该点处曲面变化越剧烈。
在2D rangeImage 上，去 pi 点及其周边与之距离小于2deta的点，
进行PCA主成分分析。可以得到一个 主方向v，以及曲率值 lamda.
注意， v 必然是一个三维向量。
那么对于边缘点，可以取其 权重 w 为1 ， v 为边缘方向。
对于其他点，取权重 w 为 1-(1-lamda)^3 ， 方向为 v 在平面 p上的投影。
平面 p 垂直于 pi 与原点连线。
到此位置，每个点都有了两个量，一个权重，一个方向。
将权重与方向带入下列式子 I 就是某点 为特征点的可能性。
点云的特征点提取应该与后面的特征描述是松耦合的。
确实不得不承认，针对不同的点云：稀疏的，致密的，有序的，无序的，有遮挡的，高精测量的.......
设计不同的关键点提取算法也无可厚非。
总结出的关键点提取算法原则就是要尺度不变，鲁棒性好，至于是否一定要存在于平坦区域，我觉得并不一定。
不同的关键点提取算法可以和不同的特征描述算法进行组合，最终得到一个较好的效果。
如果非要把关键点提取算法和特征描述算法紧耦合，那势必会失去一部分灵活性。