点云处理学习笔记（四）-- 关键点提取_点云关键点提取

一、关键点，线，面

       三维视觉应同时具备：关键点、关键线以及关键面三种算法，要从n维信息中提取n - 1维信息是简单的，但是n - 2维信息会比n - 1维信息要不稳定且复杂的多，其主要原因是因为降维过大后，特征的定义很模糊，对于三维点云而言，很难去描述什么是关键点。

二、点云降维

       二维图像中的Harris角点算子将图像的边缘交点定义为关键点，Harris算子利用角点在两个方向上响应很大的灰度协方差矩阵来定义角点。在三维点云中，可以将三维的点云投射为二维的图像，这样的方法被称为range_image。

       三维点云的采集过程离不开相机，相机的光心坐标原点Oc以及主光轴方向Z提供了将三维点云映射到二维平面的方式：首先，将某点到光心Oc的距离，映射为深度图的灰度或者颜色（灰度只有256级，但颜色可以接近连续变化）；接着，在定义一下如何将点云映射到图像的横纵坐标上。表示某点到光心Oc的距离的过程可以类似于一个球坐标系。

       通过这样的方式，可以有效地将点云的空间关系表达出来，每个点云都有了横，纵，深三个坐标，且这种坐标原点的设定方式，在理论上不存在干涉，于是点云的空间关系就被编码在深度图中。

三、基于PCL的点云 - 深度图转换

       关键点往往和特征描述联系在一起，NARF算法可以分为两个部分：第一个部分是关键点提取，第二个部分是关键点信息描述。

       1）边缘提取

        在正式开始关键点提取之前，有必要先进行边缘提取。原因是相对于其他点，边缘上的点更有可能是关键点。和图像的边缘不同（灰度明显变化），点云的边缘有更明确的物理意义。对点云而言，场景的边缘代表前景物体和背景物体的分界线。所以，点云的边缘又分为三种：前景边缘，背景边缘，阴影边缘。

        假设在range_image中存在两个相邻点：点a和点b，他们在range_image上离的很近，但在三维距离上却离得很远，那么这两个点之间多半存在边缘。为了适应点云的稀疏性，可以在包含点a的range_image图像取一个边长为s个像素的方窗，分三种情况来讨论边缘：

        1.点a在某个平面上，边长为s的方窗没有涉及到边缘；

        2.点a在某条边缘上，边长为s的方窗一半在边缘的左边，一半在边缘的右边；

        3.点a在两条边缘所构成的角点上，边长为s的方窗只有1/4与点a处于同一个平面。

        将点a与一系列不同的点之间的距离进行排序，记与点a距离最近的点为d0（这个d0很明显是点a自己），与点a距离最远的点为ds（这个点很有可能跨越边缘），记与点a是同平面但与点a距离最远的点为dm。如果d0 ~ ds是一个连续递增的数列，那么dm可以取平均值，如果这个数列存在某个阶跃跳动（可能会形成类似阶跃信号），那么发生跳动的地方应该是有边缘的存在，则dm就是阶跃点。

        对于任意的一个点，通过打分来判断该点作为边缘点的可能性，边缘可能会在点a的上下左右四个方向，所以只需要将点a与点a右边的点求相对距离，并把这个距离和dm进行比较，就可以判断边缘是不是在该点的右边，如果距离大于dm，显然该点右边的邻点与点a就不在同一个平面。

       为了增加对噪声的适应能力，取右边的点为右边几个点的平均数，根据此信息来对该店进行打分。最后再取大于0.8的Sright进行非极大值抑制，就可以得到物体的边缘。

       2）关键点提取

       在提取关键点时，边缘应该作为一个重要的参考依据，但一定不是唯一的依据。对于某个物体来说关键点应该是表达了某些特征的点，而不仅仅是边缘点，所以在设计关键点提取算法时，还需要考虑以下这些因素：

       1.边缘和曲面结构都要考虑进去；

       2.关键点要能重复；

       3.关键点最好落在比较稳定的区域，便于提取法线。

       对于点云构成的曲面而言，某处的曲率无疑是一个非常重要的结构描述因素，曲率越大，则该点处的曲面变化越剧烈。在二维的range_image中，取a点及其周边与之距离小于2deta的点，进行PCA主成分分析，可以得到一个主方向v，以及曲率值lamda（注意主方向v必定是一个三维向量）。

       对于边缘点，可以取其权重w为1，v为其边缘方向；对于其他点，取权重w为1 - (1 - lamda)^3 ，方向为v在平面A上的投影，平面A垂直于点a与原点的连线。因此，每个点都有了两个描述量：权重以及方向。将权重与方向带入下列式子，得出的结果I就是某点是特征点的可能性。最后进行极大值抑制，就可以得到一些特征点。

四、Harris算法

       Harris算法是图像检测识别算法中非常重要的一个算法，其对物体姿态变化鲁棒性好，对旋转不敏感，可以很好地检测出物体的角点，对于标定算法而言，Harris角点检测是使之能成功进行的基础。

       1）算法思想及数学推导如下：

       1.在图像中取一个窗w；

       2.获得在该窗下的灰度i；

       3.移动该窗，则灰度会发生变化，平坦区域灰度变化不大，边缘区域沿边缘方向灰度变化剧烈，角点处各个方向灰度变化均剧烈；

       4.根据第三步选出相应的角点。

       Harris算子的具体实现方法，利用的是图像偏微分方程的思想，首先给出数学表达式：

       其中w代表窗函数，某个x，y为图像的坐标，u，v是一个移动向量（既反映移动的反向，也反映移动的大小）。

       Ix表示图像沿x方向的差分，Iy表示图像沿y方向的差分。

       显然，E(u, v)可以用另一种形式来表示，最终可以表达为协方差矩阵的形式。

       最后可以得出矩阵表达式：

       2）矩阵的方向性

       E(u，v)的数学意义，实际上是先对向量（u，v）进行线性变换，即先进行旋转 + 拉伸，再乘以该向量的转置，即往向量上进行投影，因此E(u，v)的本质是投影的长度。当向量的转置取特征向量方向时，矩阵M只有拉伸作用，没有旋转作用，此时的投影长度是最长的，矩阵的特征值就是放大倍数，特征值越大则E(u，v)也就越大。

       1.两个特征值都很大：角点（存在两个响应方向）；

       2.一个特征值很大，一个很小：边缘（只有一个响应方向）；

       3.两个特征值都很小：平面（响应都很弱）。

       基于这些特征可以设计很多角点的快速判据。

五、3DHarris

       假设在点云中存在一点p：

       1.在p上建立一个局部坐标系，z方向是法线方向，x,y方向和z垂直；

       2.在p上建立一个小正方体；

       3.假设点云的密度是相同的：

       a:如果小正方体位于平面上，那么小正方体沿z方向移动，那么小正方体内的点云数量应该是不变的；

       b:如果小正方体位于边缘上，则沿边缘进行移动，点云数量几乎不变，沿垂直边缘方向移动，点云数量就会发生改变；

       c:如果小正方体位于角点上，则两个方向上的移动都会大幅改变点云数量。

       如果由法向量x,y,z构成协方差矩阵，那么它应该是一个对称矩阵，且特征向量有一个方向是法线方向，另外两个方向与法线垂直，用协方差矩阵替换图像处理中的M矩阵，就得到了点云的Harris算法。算法中的r可以用来控制角点的规模，r越小对应的角点越尖锐（对噪声也更加敏感），r越大越可能在平面区域检测出角点。