基于半球形邻域的激光雷达点云局部特征提取

蒋 博 马燕新 万建伟 何 峰 许 可 陈沛铂

（1.中国人民解放军国防科技大学电子科学学院，湖南长沙 410073；2.中国人民解放军国防科技大学气象海洋学院，湖南长沙 410073；3.海洋探测技术湖南省重点实验室，湖南长沙 410073；4.中国人民解放军75833部队，广东广州 510000）

1 引言

三维点云是通过激光雷达等扫描设备对物体表面进行扫描，所采集到的一系列三维坐标的集合。相比于二维数据，三维数据提供了更为丰富的空间、距离、颜色、强度等信息，使得基于三维数据的目标识别精度更高。在三维目标识别过程中，特征描述是其中最为关键的一步，一个好的特征描述子能够以极少的特征维度来最大限度的表征目标，为后续高效准确的特征匹配奠定基础。

基于手工特征的方法主要通过分析提取物体的特征点的几何属性［1］、形状属性［2］、结构属性［3］或者多种属性组合等特征进行对比、学习，从而完成目标的识别与分类［4］。在现有的手工特征描述算法中基于直方图的方法得到了最为广泛地研究。这类方法首先利用点云的某些信息（如点坐标、几何属性）定义直方图的一个或多个维度，然后采用邻域点的几何或拓扑测量值（如点数、网格面积）对直方图中的相应单元格进行累加从而获得直方图统计以实现对局部表面的描述。Zhong［5］首先对邻域点的协方差矩阵进行特征值分解来构建局部参考坐标系（Local Reference Frame，LRF），进而采用离散球面网格将球形邻域空间划分成均匀分布的栅格，并通过统计每个栅格单元内的点密度加权和从而获得内蕴形状特征描述子（Intrinsic Shape Signatures，ISS）。Frome 等［6］采用关键点p的法向量n作为局部参考坐标轴，并将球形邻域空间划分成一系列单元格从而获得三维形状上下文特征描述子（3D Shape Context，3DSC），由于只采用关键点的表面法向量作为参考坐标轴，所以在绕法向量的旋转方向上具有模糊性，因此需要在每个关键点处计算多次特征，使得该特征描述子占用内存大，且特征匹配性能较低。Tombari 等［7］对3DSC 进行了改进，通过给每个关键点赋予一个可重复且唯一确定的LRF以获得单值形状上下文特征描述子（Unique Shape Context，USC），大幅提升了3DSC 特征描述子的效率。Tombari等［8］通过将球形邻域空间进行栅格化，在每个栅格单元上，依据落入该单元的点的法向量与关键点法向量的夹角将这些点累加到一个直方图中，最后将所有栅格单元内的直方图串联起来以获得总的方向直方图签名特征描述子（Signature of Histograms of Orientations，SHOT）。

上述方法通过使用唯一的LRF、不同的邻域划分方法、不同的特征统计量等方式提出了不同的特征描述子。但对于邻域的选取却始终单纯采用以关键点为圆心，一定距离为半径的球形作为邻域。而实际中关键点附近的邻域点仅分布在球形邻域中的少部分区域，这使得在将整个球形进行栅格划分后，其中的栅格会产生许多空置。而这些多余的空置栅格会增加特征描述子的长度和占用内存，此外在特征匹配阶段还会花费更多的时间。

因此本文提出了半球形邻域选取方法并在估计LRF 时，对互相关矩阵增加了密度权重以提升点密度较大区域的权重，以此将注意力放在描述性更强的区域，使描述子鉴别力得到提升。此外，本文基于半球形邻域提出一种新的特征描述子半球单值形状上下文特征描述子（Hemispheric Unique Shape Context，HUSC）描述子。通过在公开数据集上的一系列对比试验表明，HUSC 特征描述子在准确率与其他描述子接近的情况下，计算特征的时间花费和特征的大小，均远远小于其他特征描述子。大幅度降低的特征描述子的维度，使得其在建立特征库时的内存占用大大减少，同时也可减少在后续的特征匹配、识别等任务中花费的时间。

2 半球形邻域方法

本文所提特征描述子计算过程主要包含两部分：LRF 构建和局部特征描述子计算。首先通过随机采样或者关键点检测方法以获得关键点并得到其局部邻域点，再通过计算关键点局部邻域的互相关矩阵的特征值构建出LRF。特征描述子的实质是对关键点邻域信息的编码［9］。一个好的特征描述子不仅应该具有较高的分辨能力，还应对噪声、网格分辨率变化等鲁棒。本文所提算法构建的关键点的LRF，其z轴为关键点的法向量，xy 平面为关键点的切平面，以此切平面为界，选取包含点较多的一半球形作为邻域，再将该半球按照方位角、极角、径向三个维度划分为多个栅格，统计落入每个栅格中的点数加权和就得到了该关键点处的HUSC特征。

2.1 局部参考坐标系

局部参考坐标系（LRF）是局部表面姿态归一化的核心，它具有可重复性和唯一性［10］。通过将局部表面的点变换到该局部参考坐标系下，可实现旋转不变性。本文在Tombari［8］等人所提出的局部参考系构建方法的基础上，增加了邻域点附近的点密度加权，提升了算法对点云分辨率变化时的鲁棒性。具体而言，通过对关键点局部邻域的互相关矩阵M进行特征值分解，得到LRF 的总体最小二乘估计，其中M可表示为：

式中，k为邻域中点的个数，pi为第i个邻域点的位置坐标，为邻域内所有点的坐标均值。为了增强LRF 在杂乱环境中的可重复性和鲁棒性，根据邻域点相对于关键点的距离进行加权，越远的点分配较小的权重，近的点则分配较大的权重。因此式（1）可改写为：

式中，R为局部邻域半径，p为关键点坐标，di=‖pi-p‖2为邻域点到关键点的欧式距离。Z为权重，可表示为：

由于在实际应用中，相同目标点云的分辨率会因为扫描角度和扫描精度不同而变化，同时在点云密度较大的地方，往往包含更多的信息，因此根据邻域点附近的相对密度进行加权。密度越大的点分配较大的权重，密度越小的点分配较小的权重。这样不仅可以保留更多有用的信息，当分辨率变化时，也可使算法更加稳健，因此式（2）可改写为：

式中，σi为邻域点附近的局部点密度，σ为关键点邻域内的点密度，其中点密度被估计为以邻域点pi为球心一定距离为半径为的球内点的数量。则模糊的LRF 的三个单位向量分别对应M3的三个特征向量，而法向量对应着M3矩阵的最小特征值。为得到唯一的LRF，需要进行符号消歧。具体而言，令LRF的正方向始终指向点数较多的方向。

式中，x+为对M3矩阵进行特征值分解所得到的特征向量，x-为该特征值的相反向量，∧为并逻辑运算。代表对应方向上邻域内点的个数。若大于等于，代表邻域范围内与x+同向的点更多，则取x+的方向为局部参考坐标的正方向，反之取x-的方向为局部参考坐标的正方向。

2.2 半球形邻域

点云是由激光雷达等扫描设备获取的物体表面一系列点的集合，由于光无法穿透物体，其内部并不包含数据点。因此点云可以形容为反映物体表面形状的“空壳”。将球形邻域看作一个球形空壳，让它的球心与点云的某一点重合，以模拟关键点处的球形邻域。由于点云内部没有数据点，因此点云中的每个点都可以视为边缘点，无论该点是处于凹面还是凸面，该点处的切平面总能将该球形空壳划分为两个半球：其中的一个半球在大多数情况下几乎不包含任何邻域点。如图1为球形邻域和半球形邻域的二维示意图。这些空置的栅格不包含任何有效的邻域信息，对特征描述子的识别率几乎无影响，但却会增加计算特征描述子时的时间和特征的内存占用大小，同时也会使得特征匹配的速度大大降低，影响识别效率。而采用切平面划分的半球形邻域，在最大限度保留描述性的同时，可大幅度降低特征的冗余并提高目标识别的效率。

本文所提的半球形邻域计算过程如下，首先，使用上一节所提的方法计算关键点P的LRF，而后将局部邻域内点的坐标变化到该局部参考坐标系中。根据局部参考坐标系的建立过程可以分析得出，在以关键点P为原点的局部参考坐标系中，z轴对应着以总体最小二乘估计所得的法向量，而x轴和y轴在以z轴为法线经过关键点P的切平面内，因此无需额外再计算关键点的切平面。又因为z轴的正方向始终指向点多的方向，所以绝大部分邻域点均在切平面以上，因此丢掉那些位于切平面以下的点，对描述子的准确率影响并不大。而后采用方位角、极角、径向半径将该半球形邻域划分为多个栅格：其中方位角[0，360°]被Φ={φ1···φL}均匀划分为L份、极角[0，90°]被Θ={θ1···θK}均匀划分为K份、径向被R={R1···RJ}按照对数距离划分为J份，总共被划分为J×K×L个栅格。其中第一个径向划分刻度R0是最小的径向半径rmin，RJ是最大的径向半径rmax。半径的边界由下面公式求得：

使用对数距离，使得描述子对于距离的变化更加鲁棒。由于越靠近球心的栅格越小，因此采用最小径向半径（rmin＞0）来避免在距离球心较近的地方描述子对于细微的变化过度敏感。此外，对半径区间[Rj，Rj+1]、方位角区间[φj，φj+1]和仰角区间[θj，θj+1]内与P有关的每一点Pi计算一个权重ω(pi)。点Pi的权重由下面公式计算得出：

其中V(j，k，l)表示栅格的体积，ρi表示栅格邻域点的密度。用栅格体积进行归一化降低了栅格尺寸在随着径向和极角方向的变化对算法稳健性的影响。而使用体积的立方根可保留显著的鉴别能力，同时使描述子对噪声具有鲁棒性。局部点密度ρi被估计为以Pi为球心在半径为δ的球内点的数量。最后统计每个栅格中点数的加权和以提取特征直方图并得到HUSC特征。

3 实验结果

为验证所提半球形邻域的有效性和密度加权对描述子鉴别力的提升，本文将半球形邻域应用于传统方法中识别效果较好的USC 描述子中，并称采用半球邻域的描述子为HUSC 描述子。为验证密度加权对描述子鲁棒性的提升，本节将在计算LRF 时将添加密度加权的描述子称为HUSC-W描述子。而后在Bologna 数据集［11］和3DMatch［12］数据集上进行对比实验，并用Precision-Recall 曲线（Precision Recall Curve，PRC）作为局部特征描述子鉴别力的评价标准，其平均精度可通过计算PRC曲线线下面积（AUC）得到［13］，PRC 计算过程如图2。

式中，Nr表示正确的匹配点数，Nm表示匹配点数，NT表示特征总数。

3.1 半球形邻域对噪声的鲁棒性

为分析半球形邻域对噪声的稳健性，本文在Bologna［11］和3DMatch［12］数据集上按照［7］中实验所用参数，在模型上分别添加方差为0.1、0.2、0.3 倍点云网格分辨率的高斯噪声对USC、HUSC 和HUSC-W 特征描述子的PRC 曲线进行对比，验证了半球形邻域对噪声的鲁棒性。实验环境为：CPU 为2.2 GHz 的Core i7-8750H，RAM 为16 GB，计算机系统为Ubuntu18.04，软件为Python和open3d开源库。

Bologna 数据集由六个Stanford 3D Scanning Repository 中的物品模型（Armadillo、Asia Dragon、Bunny、Dragon、Happy Buddha、Thai Statue）以及由原始模型进行旋转、平移等刚性变换后的得到的45个场景组成。场景中包含了背景干扰以及物体的姿态变化。模型与场景之间的真是旋转和平移关系已知。3DMatch 数据集收集了来自于62 个场景的数据，包含8 组由RGB-D 相机重建的室内场景模型，常用于3D 点云的关键点检测、特征描述、点云配准等任务。以上数据集均包含多个不同角度得到的同一物体或场景的数据。

在上述数据集上，三种描述子的PRC 如图3、图4所示。

由图3、图4，可得到以下结论：

（1）在无噪声的情况下，三种特征描述子性能相当，均具有较高的召回率和精度，如图3（a）和图4（a）所示。

（2）在噪声环境下，三种特征描述子的精度均出现了下降，其平均精度如表1、表2 所示，三种描述子对噪声均非常稳健。HUSC 特征描述子在采用半球形邻域仍然对噪声稳健是因为它所去掉的邻域基本为不包含信息的空置部分，而包含信息的邻域却完整地保留了下来，因此其鉴别力几乎未受影响。需要指出的是：当关键点位于某些特殊的复杂曲面上时，半球形邻域会出现模糊的情况，如当切平面两边的点数相近时。此外，由于LRF 的估计不可避免存在一定偏差，也会导致半球形邻域在某些关键点处会丢失部分信息，这也是基于半球形邻域的描述子精度有所下降的主要原因，但在一副点云中这样的特殊关键点相对较少，且单个特征点的失效不会影响整个情况，因此对精度的影响有限。

表1 不同噪声中3种特征提取算法平均精度比较（Bologna）Tab.1 The comparison of average precision of 3 feature extraction methods in different noise(Bologna)

表2 不同噪声中3种特征提取算法平均精度比较（3DMatch）Tab.2 The comparison of average precision of 3 feature extraction methods in different noise(3DMatch)

（3）具有密度加权的HUSC-W 特征描述子比HUSC 特征描述子拥有更高的精度和召回率。这是因为密度加权会为密度较大的区域分配更高的权重，而密度较大的部分往往包含更多信息，可以对局部邻域进行更为细致的描述，因此密度加权会提升描述子的鉴别力。

3.2 半球形邻域对数据分辨率变换的稳健性

为测试特征描述子在数据分辨率变化下的稳健性，将Bologna和3DMatch数据集中的无噪声场景点云降采样至原分辨率的1/2、1/4、1/6 和1/8，得到特征描述子在不同数据分辨率下的RPC 曲线如图5、图6 所示，平均精度如表3、表4 所示。可以看出随着分辨率下降，三种特征描述子精度均保持在较高的水平，这是因为两种描述子在特征计算时均根据邻域点密度进行了加权和归一化处理。此外，HUSC-W 描述子由于在计算LRF 阶段时对互相关矩阵加入了密度加权，使得包含信息更丰富的大密度区域更多地被计入互相关矩阵中，使得其鉴别力更强。同时，当点云分辨率变化时，该密度加权也会相应的变化，因此HUSC-W 描述子较HUSC 描述子更为稳健。

表4 不同数据分辨率下2种特征提取算法平均精度比较（3DMatch）Tab.4 The comparison of average precision of 2 feature extraction methods in different mesh resolutions（3DMatch）

表3 不同数据分辨率下2种特征提取算法平均精度比较（Bologna）Tab.3 The comparison of average precision of 2 feature extraction methods in different mesh resolutions（Bologna）

3.3 半球形邻域的高效性

为验证半球形邻域对运算效率和存储空间的优化，本文对Bologna 数据集中的六个原始模型建立特征库，分别测试USC 和HUSC 两种特征描述子建立特征库所占用的内存，而后再利用该模型库进行特征匹配比较两种描述子所花费的时间。具体而言，对于一个模型，首先对该模型点云进行均匀采样以获得一系列种子点，由于空间上邻近的关键点具有相似的特征描述子，因此采用分辨率控制策略对种子点做进一步筛选以获得最终的关键点［14］。对于每一个关键点Pm，计算其LRF 以及特征描述子fm。最后，将所有模型特征描述子fm存储在模型库中。该模型库的内存占用大小便可反应特征描述子的大小。而后，将噪声、旋转分别加入原始模型后再次按照上述步骤计算得到场景特征描述子fs，并进行局部特征匹配。用六个模型完成特征匹配的平均时间来反应特征描述子的效率。两种特征描述子分别建立的模型特征库大小以及特征匹配花费时间如表5所示。

从表5 可知，HUSC 和USC 特征描述子在分别对相同目标进行特征提取建立模型库，HUSC 特征描述子所需空间为8.6 MB，较USC 特征描述子的17.3 MB 节省50.3%的内存。且在特征匹配时，HUSC 特征描述子花费时间比USC 特征描述子缩短48.3%。另外，在建立模型特征库时，HUSC 特征描述子花费时间71.86 s，USC 特征描述子花费时间91.54 s。HUSC 特征描述子之所以如此高效，是因为半球形邻域较球形邻域减少了一半几乎不包含信息的空间，使得它的冗余栅格较USC描述子大幅度减少，并让特征维度得以降低。更低的特征维度意味着更快的特征运算和匹配速度，同时内存占用也相应减少。而随着三维数据采集设备的精度的提高和场景的不断扩大，点云的数据量也会剧增，本文所提方法将节省巨大的内存和算力资源。

表5 2种特征提取算法建立模型特征库占用内存、特征匹配花费时间Tab.5 The runtime of feature matching and memory occupied by feature library of 2 feature extraction methods

3.4 HUSC与PCA特征压缩算法对比

为比较改进邻域的HUSC算法与直接对特征进行压缩的经典特征压缩算法的性能，本文将原始USC描述子通过PCA 算法进行降维，并绘制PRC曲线。其在不同噪声和点云分辨率的条件下与HUSC描述子的实验对比结果如图7、图8所示。

由图可知：

（1）HUSC 与PCA 两种算法随着噪声增加和点云分辨率的下降，精度均呈下降趋势，但HUSC的精度始终比PCA更高。

（2）PCA 算法在有噪声的环境中，精度出现劣化较之分辨率变化的情况更为严重，这是由于PCA算法采用l2范数平方作为距离度量准则，导致算法的鲁棒性差，对噪声敏感。

HUSC 和经过PCA 降维后的特征占用内存，以及特征匹配时间如表6 所示，由该表可以看到PCA算法能够对特征进行有效的降维，其特征内存降至6.4 MB。同时特征匹配的时间较HUSC 有进一步降低，这是由于PCA 降低了特征维度，使得特征匹配的总量减少。

表6 2种算法建立模型特征库占用内存、特征匹配花费时间Tab.6 The runtime of feature matching and memory occupied by feature library of 2 methods

4 结论

本文通过将半球形邻域应用在USC 描述子中提出了更具效率的HUSC 特征描述子。在Bologna数据集上进行的实验结果为：在有噪声干扰时，HUSC 特征描述子的平均精度为92.2%，USC 特征描述子的平均精度为94.9%。在分辨率变化时，HUSC 特征描述子的平均精度为93.0%，USC 特征描述子的平均精度为94.8%。在3DMatch数据集上的实验结果为：在有噪声干扰时，HUSC 特征描述子的平均精度为92.4%，USC 特征描述子的平均精度为95.4%。在分辨率变化时，HUSC 特征描述子的平均精度为92.8%，USC 特征描述子的平均精度为94.3%。而在建立特征库时，HUSC 特征描述子内存占用为8.6 MB，USC 特征描述子内存占用为17.3 MB，HUSC 较USC 特征描述子内存占用减少50.3%。在进行特征匹配时，HUSC 特征描述子所用时间为257.26 s，USC 特征描述子所用时间为497.76 s，HUSC 较USC 特征描述子花费时间减少48.3%。由此可知基于半球形邻域的HUSC 特征描述子具有与USC 描述子相当的鉴别力，同时特征匹配的速度更快，占用内存更小。随着三维数据采集设备精度不断增加，三维点云的数据量也大幅增加。本文所提算法为三维目标检测、识别、重建等任务提供了一种更高效的特征描述子，也为特征描述子开发，提供了新的邻域选取思路。