【点云局部特征描述子】SHOT

1. 前言

传统的点云局部特征描述子（3D Local Feature Descriptor ）可以分为：

• Signatures

Signatures describe the 3D surface neighborhood (support) of a given point by defining an invariant local reference frame and according to the local coordinates, encoding one or more geometric measurements computed individually at each point of a subset of the support.

Signature 通过定义局部参考坐标系（LRF）来编码局部空间几何信息，由于 LRF 的存在，其局部几何空间的特征值是有序的。

• Histograms

Histograms describe the support by encoding counters of local topological entities (e.g. vertices, mesh triangle areas) into histograms according to a specific quantized domain (e.g. point coordinates, curvatures, normal angles).

Histogram 将特征值进行区间划分，以直方图统计的方式进行编码，统计量是无序的。

SHOT（Signatures of Histograms of OrienTations）描述子是一种混合式的描述子。

• 【网站】http://www.vision.deis.unibo.it/research/80-shot
• 【论文】SHOT: Unique signatures of histograms for surface and texture description. Computer Vision and Image Understanding, 2014.

2. 原理

2.1 Local Reference Frame（LRF）

对于法向量的计算，常规操作是：（1）对查询点（query point）的 k 邻域内的点，通过下式构建协方差矩阵（covariance matrix）；（2）然后通过EVD 或 SVD 求得特征值与特征向量，将特征值最小的所对应的特征向量作为法向量；（3）最后，通过符号一致性（sign consistency）或其他方法消除歧义性。

本文中，作者做了如下改进：

（1）为了提高存在 clutter 时的可重复性，给更远的点赋予更小的权重；

（2）为了改善对 noise 的鲁棒性，将支撑区域（spherical support of radius R）内的所有点都用于计算协方差矩阵；

（3）为了提高效率，直接用特征点 p 代替支撑区域重心。

改进的协方差矩阵计算公式如下：

注意：这里计算的法向量不一定跟上述计算的几何表面法向量相同。

In local surface description, the definition of a highly repeatable and robust triplet of orthogonal directions is more important than its geometrical or topological meaning.

接下来就是 sign disambiguation 了。

（1）将协方差矩阵计算的三个特征向量按照特征值递减的顺序依次作为 x^+, y^+,z^+ 轴，其反方向作为 x^-, y^-,z^- 轴；

（2）计算支撑区域内每个点与特征点的欧式距离，并计算平均距离，将最接近平均距离的 k 个点取出作为集合 M(k) ；

（3）通过下面的公式来首先确定无歧义的 x 轴，具体而言，统计 (p_i-p)\cdot x^+\geq 0 和 (p_i-p)\cdot x^-< 0 点的个数，将点数多的轴作为 x^+ 轴，若两者点数相同，再去比较 \left|\tilde{S_x^+} \right| 和\left|\tilde{S_x^-} \right| 的大小；

（4）用同样的方法确定 z 轴；

（5）y 轴为 x 轴与 z 轴的外积方向。

最终，就可以获得 disambiguated LRF。

2.2 特征矢量

基于上文构建的 LRF，将球形支撑区域划分为 32 个小区域（volumes），具体如下：

• 径向（radial）：2 个，即内球与外球；
• 纬度方向（elevation）：2 个，即北半球与南半球；
• 经度方向（azimuth）：8 个

对于每一个小区域（volume），构建一个局部直方图，根据特征点的法向量与 LRF z 轴夹角的余弦值 cos \theta_q = n_q\cdot z_k 进行投票，若每个局部直方图划分为 11 个 bins，则 SHOT 描述子有 32\times11=352 维。

For each of the local histograms, we accumulate a point into bins according to the cosine of the angle \theta_q between the normal at the point, n_q , and the local z axis at the feature point, z_k .

2.3 四线性插值（Quadrilinear Interpolation）

SHOT 描述子是基于局部直方图，因而会有边缘效应（Boundary Effects ）的影响；此外，局部参考坐标系的扰动（perturbation）也会造成边缘效应。

本文采用四线性插值（Quadrilinear Interpolation）方法来弱化边缘效应，即对每一个点投票时，从四个维度，根据距离权重进行插值投票。首先，对于同一个小区域（volume），划分了11个区间（bins），从 cos\theta 维度进行插值投票，如下图（a）所示；然后，对于其相邻的小区域（volumes）根据权重d（角度距离或欧式距离）进行相应的插值投票，如下图（b,c,d）所示。

也就是说，每个点对 radial, azimuth, elevation 三个维度的 8 个小区域（volume）进行了插值投票，每个小区域（volume）根据 cos\theta 维度对两个区间（bins）进行了插值投票。因而，每个点总共对 16 个区间（bins）进行了插值投票。

（1）法向量余弦插值

假设当前关键点支撑区域内一点的特征值为 cos\theta ，其处于 (cos\theta_i, \ cos\theta_{i+1}) 区间，首先分别计算出 cos\theta 到 cos\theta_i 和 cos\theta_{i+1} 的归一化（除以区间长度 s）距离，记为 d_i 和 d_{i+1} ，然后给 cos\theta_i 区间投票值为 +1-d_i ，给 cos\theta_{i+1} 区间投票值为 +1-d_{i+1} 。线性插值的作用就是把当前值按照线性比例分配到相邻的离散区间上。

（2）经度插值

对于经度和维度，权重 d 为角度距离（angular distance）进行计算。插值的方法与上述相同。

（3）维度插值

（4）径向插值

对于径向这个维度，权重 d 根据欧式距离进行计算。

3. PCL 实现

#include <pcl/impl/point_types.hpp>
#include <pcl/features/shot.h>
#include <pcl/features/shot_omp.h>

{
    // 定义输出数据
    pcl::PointCloud<pcl::SHOT352>::Ptr descriptors (new pcl::PointCloud<pcl::SHOT352>);

    // 定义 shot 描述子对象
    pcl::SHOTEstimation<pcl::PointXYZ, pcl::Normal, pcl::SHOT352, pcl::ReferenceFrame> shot;
    shot.setRadiusSearch (descr_rad);
    shot.setInputCloud (keypoints);
    shot.setInputNormals (normals);
    shot.setSearchSurface (model);
    shot.compute (*descriptors);
}