基于球形网格划分的二值化点云特征描述子

周唯， 杨东永， 胡国欣， 张国强， 张钰如

(1.91550部队， 辽宁 大连 116023； 2.大连理工大学 物理学院， 辽宁 大连 116024)

局部特征描述子是三维点云特征的局部表达，反映了点云一定邻域范围内的局部表面特征，通常通过将局部表面的几何或空间信息转化为特征向量而得到。由于对遮挡、噪声和点密度变化具有强鲁棒性和强描述性，局部特征描述子在点云配准、三维重构、形状检索、人脸特征识别等计算机三维视觉领域有着广泛的应用。随着低成本传感器和高速计算系统的蓬勃发展，三维数据的获取变得更加便利，这进一步提升了局部特征描述子在计算机视觉领域的重要性。尽管大量优秀的点云局部特征描述子被提出[1-4]，但当这些特征描述子应用于低成本传感器(如Kinect和RealSense)获取的低质量点云数据时，在抗噪性、时间效率和内存占用等方面仍存在一定局限性。例如：维度只有33维的FPFH[1]描述子，具有时间效率高、内存占用少的优势，但由于其构建依赖于法向量，因而对噪声十分敏感；RoPS[2]特征描述子虽然具有极高的鲁棒性和描述性，但它采用基于网格模型的方法进行描述，因此在对散乱点云构建特征描述子时，需提前对点云进行三角网格化，而且还要执行多次旋转操作，增加了算法的时间开销；SDASS[3]描述子具有极强的描述性和极高的时间效率，但在构建描述子之前需要计算点云中每个点的局部坐标轴(local reference axis, LRA)和局部最小轴(local minimum axis, LMA)，这大大增加了额外的时间开销；USC[4]描述子具有较好的性能，但其维度高达1 980，构建的时间和空间开销均较大。

上述描述子均为浮点型，内存占用较大，特征匹配效率较低。然而，按位表示的二值化描述子，使用简单的异或操作即可完成特征匹配，因此可有效解决上述问题。二值化特征描述子在二维图像处理领域应用较多，比如BRIEF[5]、ORB[6]、FREAK[7]和LDB[8]，而针对三维点云提出的二值化特征描述子很少。B-SHOT[9]提出的二值化点云特征描述子，它是由传统的SHOT描述子[10]衍生而来，虽然其构建时间效率很高，且维度仅为352，但由于B-SHOT是对SHOT的直接量化，造成其描述性降低，同时继承了SHOT对网格分辨率变化较为敏感的缺点。Srivastava等[11]提出的基于点签名的三维二值化特征描述子(3DBS)，根据定义的局部参考坐标系(local reference frame，LRF)对局部表面进行对齐，然后用表面法线表征局部点分布，并将其编码为二进制向量。但其计算耗时，而且对噪声、点密度变化较为敏感。杨必胜[12]提出的二进制形状上下文特征描述子(BSC)可用于点云局部特征的刻画，具有极强的描述性和鲁棒性，单个描述子的构建时间极短，且其特征维度仅为48，对于相同数量的特征描述子，BSC的匹配时间要比其他描述子的匹配时间短得多，但为了消除LRF二义性的影响，在点云匹配和目标提取过程中，BSC需要对源点云中的特征点计算4次LRF，这会降低整个点云匹配或目标提取过程的运算效率。权思文等[13]提出的基于立方体体素的二值化特征描述子(LoVS)，对于低成本传感器获取的低质量点云数据具有极强的鲁棒性和描述性，但该描述子在构建过程中需要反复进行不同半径球邻域的最近邻搜索，增加了算法的时间开销，由于在构建描述子的过程中，实际上只用到了球邻域内接立方体中的点，这造成了存储空间和运算时间上的浪费。

本文提出了一种基于球形网格划分的二值化点云特征(spherical grid-based binary，SGB)描述子，该方法首先以特征点为中心构建球邻域，并利用文献[3]中所提的LRA和特征点与球邻域重心连线的投影构建LRF；然后基于构建的LRF，在半径方向、方位角方向和俯仰角方向对球形邻域进行网格划分；最后根据划分的网格内是否包含点将网格标记为1或0，从而生成一个二进制的字符串。由于所提的LRF具有极强的鲁棒性和可拓展性，基于该LRF的SGB具有良好的旋转平移不变性。文中将SGB与B-SHOT、LoVS、TOLDI[14]、FFPF、SDASS几种经典高效的特征描述子进行比较分析。

1 二值化点云特征描述子构建

SGB描述子构建主要包括构建LRF、球形网格划分、二值化描述子生成等步骤，构建流程如图1。

图1 SGB构建流程图Fig.1 An illustration of generating the SGB feature descriptor

1.1 局部参考坐标系构建

LRF是一个原点在特征点处且包含了特征点邻域空间信息的坐标系，相当于二维图像领域特征描述子的主方向。良好的LRF可以使特征对刚体变换保持不变性[15]。SHOT、ISS[16]、RoPS、TOLDI、LoVS等众多优秀的点云特征描述子均是基于LRF构建的，LRF的鲁棒性和可重复性直接关系到特征描述子的性能，文献[17]和[18]曾先后对10种LRF进行了性能比较和分析。而由杨佳琪等[14]提出的一种用于构建TOLDI描述子的LRF，其构建方法已被应用于LoVS、BRoPH[19]、LSAH[20]等描述子的构建过程中。文献[3]对该LRF中Z轴的生成方法进行了改进，提出了一种LRA构建方法。由于该LRA对噪声和点密度变化具有极强的鲁棒性，本文借鉴该LRA构建方法确定本文所提LRF的Z轴。

如图2所示，给定点云P中的特征点p以支撑半径r确定球邻域子集Q={qi∣i=1,2,…,s}，则根据Q可确定协方差矩阵Cov(Q)为：

(1)

(2)

图2 LRF构建图Fig.2 An illustration of the proposed LRF

注：为特征点p，和均为p的球邻域点在M平面上的投影点，代表正常的邻域点，代表噪声点，代表根据正常邻域点确定的重心g，代表联合正常邻域点和噪声点而确定的重心g′。图3 LRF的抗噪性原理Fig.3 Anti-noise principle of the LRF

1.2 球形网格划分

首先根据构建的LRF对特征点p的球邻域点集进行坐标转换，使局部点云Q转换到LRF下。设整个点云模型所处的世界坐标系由Xw轴、Yw轴、Zw轴相互垂直组成，其中Xw轴、Yw轴、Zw轴的方向向量分别为(1,0,0)、(0,1,0)和(0,0,1)，坐标系原点为O，如图1中的右上角子图所示。设1.1节中所构建的LRF中各轴的方向向量为X(p)=(x0,y0,z0)、Y(p)=(x1,y1,z1)、Z(p)=(x2,y2,z2)，p点坐标为(xp,yp,zp)，构建LRF到整个点云模型所处的世界坐标系的旋转矩阵R和平移向量t为：

(3)

图1中邻域点坐标转换过程所示，将球邻域点集Q中的每一点qi(xqi,yqi,zqi)转换到1.1节构建的LRF下，使得后续生成的特征描述子具有对刚性变换的不变性，转换后邻域点的集合记为Q′={q′i|i=1,2,…，s}，其中q′i为转换后的邻域点，坐标为(xq′i,yq′i,zq′i)。

(4)

根据LRF对Q′所在的球邻域进行网格划分，以Z轴的正方向和球邻域的交点作为北极，Z轴的逆方向与球邻域的交点作为南极。并借鉴文献[10]的方法，根据构建的LRF，将特征点p的球邻域空间在半径R维度上均分为J部分{R0,R1, …,RJ-1}，在方位角Θ维度上均分为K部分{Θ0,Θ1, …,ΘK-1}，在俯仰角Φ维度上均分L部分{Φ0,Φ1, …，ΦL-1}，其中0

1.3 二值化描述子生成

LoVS在内存占用和时间效率上有待改进，但该算法不需要提取复杂的点云几何属性，将整个体素作为编码单元，仅需根据立方体体素中是否有点，即可对体素进行二值化标定，算法简单有效。因此本文借鉴这种构建描述子的思想，根据分割的球形网格内是否存在邻域点，对J×K×L个网格进行1或0的标记。

(5)

根据式(5)确定q′i所落入的网格Gjkl的序号gid。

Q′内每个点的网格序号确定后，设网格Gjkl内包含的子点集为Q′Gjkl，按以T(Gjkl)对网格Gjkl进行二值化标记：

(6)

从而球形邻域Q′的每个子网格均被标记为0或1，这些标记最终集成为一个J×K×L维的二进制字符串，即SGB描述子：

fSGB={T(Q′0),…,T(Q′jkl),…,T(Q′(J-1)(K-1)(L-1))}

(7)

与大多数以点为基础编码单元的特征描述子不同，SGB以分割的球形网格为编码单元，且不需要依赖法向量、曲率、点密度等点属性，因此其对噪声和分辨率的变化具有更好的鲁棒性。而且这种二值化编码方式，极大地压缩了存储空间。对于这种二值化特征描述子可以通过计算简单的汉明距离[23]进行特征匹配，避免了最近邻距离比(nearest neighbor distance ratio，NNDR)[24]计算过程中大量欧氏距离的运算，提高特征匹配的时间效率。此外，SGB生成过程中的所有操作均在球邻域Q内进行，且为完成最近邻搜索，仅需对Q内的邻域点集构建一次KD-tree(k维树)，无需像LoVS特征描述子那样需反复构建不同大小搜索半径的球邻域，进一步提高了时间效率。

2 实验环境和评估准则

2.1 实验数据

本文采用Retrieval[22]、Kinect[10]、Space Time[22]3个公共点云数据集作为实验数据。其中Retrieval数据集包含6个模型数据和18个场景数据，其模型数据来源于Stanford 3D Scanning Repository[25]，场景数据由不同模型数据随机平移、旋转后组合而成，且人工增加了标准差为0.1 mr网格分辨率(mesh resolution，mr)、0.3 mr和0.5 mr 3个级别的高斯噪声。为验证所提LRF和SGB的性能，本文在原始Retrieval数据集基础上分别对每一个原始分辨率的无噪声场景数据进行1/2、1/4、1/8 3个级别的降采样，创建了另外3组场景数据。Space Time和Kinect数据集分别采用Space Time立体视觉传感器和微软Kinect一代传感器采集获得，数据质量较低，且存在噪声、遮挡和空洞等干扰。

2.2 实验环境

为验证所提LRF性能，本文选用SHOTL、TOLDIL、RoPSL、BOARD 4种LRF构建方法作为对比算法。为验证SGB性能，本文选用B-SHOT、TOLDI、LoVS、FPFH、SDASS 5种特征描述子作为对比算法。上述LRF和描述子构建方法均通过C++编程实现，且均未采用GPU和并行运算技术，实验环境为Intel Core i7-8559U处理器，主频2.71 GHz，32 GB内存。为体现算法评估的公平性，对于每组数据集，各LRF和描述子构建过程中均采用相同的r。本文参照文献[2]，统一将r设置为20 mr，但为保证提取特征时支撑域内有足够的邻域点，本文参照文献[26]，对于降采样的Retrieval数据集，将r设为35 mr。此外，本文中利用20个最近邻点计算点的法向量。

2.3 评估标准

本文利用坐标轴平均角度偏差MeanCos[17]评估标准LRF的可重复性，MeanCos值越大表明所构建LRF的坐标轴偏差越小，可重复性越好。还利用召回率及精度曲线RPC和精度召回率曲线下面积AUCpr[3]评估特征描述子的性能。一个理想的特征描述子，其RPC曲线应集中于图的左上角区域，其AUCpr值应越接近1，即该特征描述子同时拥有很高的召回率和精度。

从模型点云中随机选取1 000个点作为特征点，根据数据集中提供的模型点云和场景点云之间的旋转矩阵真值，对模型点云和场景点云进行配准，再从场景点云中搜索这1 000个特征点的最近点，从而形成对应点对。通过计算点对中每个点的LRF和特征描述子，生成MeanCos累计直方图和RPC曲线，具体生成过程可参照[2，9，27]等文献的描述，在此不再赘述。

3 局部参考坐标系性能评估

3.1 可重复性评估

本节利用2.1节所提的Retrieval、Kinect、Space Time 3组数据集对比分析2.2节所提的5种LRF的可重复性，采用2.3节所提的MeanCos作为评估标准，实验结果如图4所示。

图4 5种LRF构建方法在Retrieval、Space Time和Kinect数据集上的可重复性表现Fig.4 Repeatability performance of five LRF methods on the Retrieval, Space Time and Kinect datasets

由图4可以看出，除了在1/2和1/4这2种级别降采样的数据集上表现为次优性能外，本文所提LRF在其他6组数据集上均取得可最优的可重复性。对于低级别的降采样，RoPSL具有极高的性能。因为该算法对局部曲面中每个三角面片施加了一个与三角面片面积相关的权重，使算法对数据分辨率变化具有一定鲁棒性[2]。但随着降采样级别的提升，该策略逐渐失效。

本文所提LRF对噪声、降采样和低质量点云之所以均表现出极强的可重复性，其原因主要：1)所提LRF的Z轴基于文献[3]中LRA构建方法确定，该LRA具有极强的可重复性[3]；2)所提LRF的X轴基于球邻域重心确定，而球邻域重心具有唯一性，避免了坐标轴二义性的问题，而且其较好的抗噪性也提高了LRF整体的可重复性。

3.2 泛化性评估

为进一步评估所提LRF构建方法的有效性，本文将TOLDI和B-SHOT 2种特征描述子中的LRF构建方法替换为本文提出的LRF，通过对比TOLDI和B-SHOT在替换LRF前后的RPC和AUCpr评估所提LRF的泛化能力。采用Kinect数据集进行对比实验，2组描述子的RPC如图5所示，图例方括号内的数值为各描述子的AUCpr。

图5 所提LRF对B-SHOT和TOLDI的RPC的影响Fig.5 The impact of the proposed LRF on the B-SHOT and TOLDI descriptors in terms of RPC

从图5中可以看出，这2种基于LRF的特征描述子将原有LRF替换为本文所提LRF后，特征匹配的效率均有所提高。这说明本文提出的LRF不仅对其他基于LRF的特征描述子具有较好的通用性，而且可以有效提高特征描述子的特征匹配能力。

3.3 时间效率评估

为对比各种LRF的时间效率，本文从添加0.1 mr级别噪声的Retrieval数据集的每组模型和场景数据中随机地选择1 000个点，分别以前文所述的5种算法对这些点构建LRF，并根据运算的点数对运算时间取均值，从而确定每种算法对于单个点构建LRF所需时间。构建LRF的时间和特征点邻域内点数有关，因此本文通过改变r的大小获取各种算法的时间效率随r变化的曲线，如图6所示。图中横轴为r的尺寸，纵轴为单个LRF的构建时间。

图6 LRF的时间效率评估Fig.6 Time efficiency performance of LRF methods

4 二值化点云特征性能评估

4.1 参数分析

SGB在构建过程中需要确定J、K、L和r这4个参数，其中描述子的维度由J、K、L3个参数的乘积决定。这3个参数若其数值较大，则会降低描述子的计算效率，消耗较多的内存；反之，若其数值较小，则描述子将无法充分描述局部点云的细节变化。另一方面，r作为特征描述子的重要参数，其值越大，则描述子的描述性越强，但会降低描述子的计算效率，并增加描述子对噪声、遮挡和空洞等干扰的敏感性；而r过小又会降低描述子的鉴别能力[2]。因此需要对J、K、L、r这4个参数进行最优化。

本文采用Space Time数据集作为测试数据。采用AUCpr来测试J、K、L3个参数的最优值，其中一个参数的选择是在固定其他2个参数的基础上进行的，每个参数的取值范围为5～15，步长为1，图7为不同参数设置条件下AUCpr值的变化图。J、K、L3个参数的最优取值分别为8、11、7。可见方位角维度上的最优区间划分数要明显比俯仰角维度上的多，印证了本文的分析，局部点云中的点多集中于M平面上，在方位角的维度上需采取更精细的划分，方可更详细地描述邻域点的几何分布。根据确定的最优J、K、L取值，SGB的维度数即为8×11×7=616。

图7 SGB描述子的参数设置Fig.7 The parameter settings of the SGB descriptor

在设置J、K、L3个参数为最优值的基础上，采用RPC来测试SGB在r取不同值时的性能，以确定能使SGB获得最优性能的r。图8为r取不同值时SGB的RPC，当r取值为20 mr时，SGB的精度、召回率和AUCpr均达到最高，因此SGB的最优支撑半径选为20 mr。SGB和其他5种对比描述子的参数设置如表1所示，在没有特别说明的情况下，本文所有实验均采用表1的参数设置。

图8 支撑半径变化对SGB描述子的影响Fig.8 Effects of varying the support radius on the SGB descriptor

表1 6种描述子的参数设置表Table 1 Parameter settings for six feature descriptors

4.2 鲁棒性评估

为验证SGB对噪声和分辨率变化的鲁棒性，采用2.1节介绍的数据集作为测试数据，利用RPC和AUCpr作为评估标准，并与2.1节所提的5种描述子进行对比，其中TOLDI、FPFH、SDASS为浮点型描述子，B-SHOT、LoVS和SGB为二值化描述子。实验结果如图9所示。

图9 6种描述子在不同数据集下的特征匹配性能对比Fig.9 The RPC and AUCpr performance evaluation of six descriptors tested on Retrieval, Space time and Kinect datasets

由图9可以看出，对于各种数据集，SDASS描述子的性能明显优于其他5种描述子。由于该描述子利用具有极高鲁棒性的LRA和LMA之间的夹角来对点云的局部信息进行编码[3]。FPFH和B-SHOT对于各数据集的性能均不理想，主要是由于这2种描述子的构建均依赖于法向量，而法向量对于噪声、降采样和遮挡等干扰较为敏感。

SGB对于各数据集均能取得次优的性能，虽与SDASS描述子的性能差距较大，但SGB无论是对于存在高斯噪声和降采样的高质量Retrieval数据集，还是对于存在遮挡、空洞、背景干扰和真实噪声的低质量Kinect、Space Time数据集均表现出较强的鲁棒性。原因为：1)本文所提的LRF具有较好的性能，不依赖于法向量，而SGB基于该LRF构建，因此SGB对噪声和分辨率变化表现出较好的性能；2)由于本文将球形网格划分后的“体素”作为一个整体处理单元，而非将单个点作为最小处理单元，这种处理方式可降低点级扰动对描述子性能的影响。

4.3 时间效率评估

为评估SGB的时间效率，本节采用添加了0.1 mr级别噪声的Retrieval数据集作为实验数据，从数据集中的每个模型数据中随机选取1 000个特征点，共选取18 000个点，分别利用2.1节所提5种算法对这些点构建特征描述子，并统计每种算法对这些点构建描述子所用的计算时间。其中B-SHOT、FPFH和SDASS 3种描述子在构建过程中需要计算点云中每个点的法向量、LRA或LMA，因此应将法向量、LRA和LMA的计算时间计入描述子的构建时间中。由于描述子的构建时间和特征点邻域内点数有关，本节通过计算各种算法的时间效率随r变化的曲线，来测试不同描述子对不同密度点云数据进行特征提取的时间效率。我们将描述子的r以5 mr为间隔，从5 mr增加至40 mr来产生不同尺度的局部点云，如图10所示。

图10 特征描述子在不同支撑半径下的时间性能对比Fig.10 Computational time of feature descriptors with respect to varying support radius

SDASS方法时间效率最低，与SGB算法的时间效率相差一个数量级，主要是由于该方法需要对点云中每个点构建LRA和LMA，对于庞大的点云数据，对应时间也其巨大的。可见，该方法虽然在4.2节中表现出极强的鲁棒性，但其时间效率较低，无法满足实时响应的应用场景需求。LoVS方法的时间效率也并不理想，同引言中关于该方法反复进行最近邻搜索会降低算法效率的观点。

SGB具有最高的时间效率，主要原因为：1)SGB所依赖的LRF具有极高的时间效率；2)SGB仅需计算距离、方位角和俯仰角3个属性，这3个属性计算简单，且在描述子构建过程中充分利用了球邻域内所有的点，不存在内存空间和运算浪费的问题；3)SGB在构建过程中仅需对局部点云构建LRF，无需计算整个点云模型中每个点的法向量或LRA，这大大降低了算法的时间和空间开销；4)SGB维度适中，虽比B-SHOT和FPFH维度高，但比TOLDI、LoVS和RoPS的维度要小很多。

在兼顾了鲁棒性和描述性的基础上，SGB具有极高的时间效率，这使其更适用于自动驾驶、人脸识别和目标检测等需要实时响应的应用场景。

5 结论

1)基于去除二义性的法向量和特征点球邻域重心在法平面上的投影构建了一种具有极佳时间效率的LRF，其不仅对噪声、降采样和低质量点云具有极强的可重复性，而且对其他基于LRF的特征描述子具有较好的泛化性。

2)基于所提LRF构建了一种时间和空间开销极小的二值化点云特征描述子SGB，其对高质量模拟数据和低质量实测点云都具有较好的描述性。

3)所提的LRF构建方法和SGB特征描述子可以应用于自动驾驶、人脸识别和目标检测等需要实时响应的场景。

4)与SDASS这种高性能特征描述子相比，SGB在对不同类数据的鲁棒性方面仍存在一定差距。

下一步工作将充分利用低成本传感器所采集数据中的RGB信息，将其整合到SGB描述子中，以提高其描述性和鲁棒性，并利用公路或室内导航等现实应用场景的数据对算法的性能进行进一步验证。将在SGB基础上尝试融入并行计算技术和GPU资源，以进一步提高算法效率。