优化球查询算法的点云分割

王爱兵，杨晓文，韩 燮，郭新东，彭志斌，郭子军，贾彩琴

(中北大学 大数据学院，山西 太原 030051)

0 引 言

3D传感器技术[1]的发展使得人们能够方便地获取大规模点云数据。例如，激光雷达传感器每秒钟可以产生数百万个点，提供所需物体的点云数据。点云数据作为一种3D数据表达形式已成为众多科学邻域诸如计算机视觉[2]、自动驾驶[3]和机器人领域[4]的重要数据资料，是许多场景理解相关应用程序的首选格式，为三维场景分割、多元化视觉、卡通制作、三维模型构建和大众传播工具应用提供多方面的用途。在三维场景分割中，典型的卷积架构需要高度规则的输入数据格式，如2D图像或3D体素的格式，以便执行权重共享和其他内核优化，然而2D图像丢失了现实世界中两个或多个物体之间的深度信息和相对位置，使得它不适合深度和定位信息的应用；3D体素模型[5]是一组将点云转移到空间量化的体素网格并使用体积卷积在网格空间中执行计算的模型，利用网格作为数据结构化方法，将点与网格中的位置相关联，3D卷积核从相邻体素收集信息。尽管网格数据结构是有效的，但仍需要高体素分辨率来保持数据的粒度。由于计算和内存使用量随体素分辨率呈三次方增长，因此处理大型点云的成本很高。此外，由于大多数体素结构中大约90%的体素是没有点云的，因此不处理任何信息但可能会消耗大量的计算能力。这种数据表示会使结果数据量变得不必要的庞大，同时还会引入量化噪声，影响数据模型的鲁棒性。

点云数据处理的另一类模型是基于点的模型。与体素模型相比，它将原始几何信息保留在3D空间中，避免了点云数据体素化过程中的特征损失。例如，2017年Charles团队提出了点云分类和分割网络PointNet[6]，它直接处理点云数据，无需量化，利用多层感知器(Multilayer Perceptron，MLP)[7]提取全局特征向量，并利用对称函数解决无序的问题，取得了不错的目标识别效果和较高的分割精度。然而该网络只能学习到点云全局特征，不能捕捉由点所在的度量空间引起的局部结构，限制了识别细粒度模式的能力和对复杂场景的概括能力，因此该网络对于场景细节的分割精度欠佳。2020年J.Zhao提出了一种基于改进PointNet的端到端自动分割方法[8]，根据不同室内结构元素强度差异较大的特点，将3D坐标、颜色和强度的点云信息输入到点的特征空间中，提高了对墙、门等结构元素的分割精度。2020年东华大学刘训华提出对图像和激光雷达点云数据进行3D目标检测的改进F-PointNet[9]，使用宽阈值掩模处理，增加注意力机制并更换损失函数为Focal Loss可以获得较优的结果，但准确率还有提升的空间。

针对该问题，Charles团队借鉴CNN[10]多层感受野的思想对PointNet进行改进，提出了PointNet++[11]，它在整个点云局部采样并划定范围，用PointNet进行特征提取，并以此方式多次迭代提取，将特征提取集中到少数点上，而每个点都包含上一层点通过PointNet提取出的局部特征。基于此，PointNet++将局部区域划分为多个分区，每个分区被定义为底层欧氏空间中的一个查询球，其参数包括球心位置和距离。为了均匀覆盖整个集合，球心通过最远点采样算法(farthest point sampling，FPS)[12]从输入点集中选择，对于密度不均匀的点云数据，球形邻域范围内局部特征点的选取是具有挑战性的。实验结果表明，采用K-近邻算法[13]对球邻域中局部特征点的选取做进一步的优化，将优化后的算法应用到PointNet++分割网络，丰富了网络的局部特征表征能力，强化了细节特征的表达效果。2020年上海理工大学孙红提出融合MKF的PointNet++优化算法[14]，采用基于深度学习的方法处理点云数据,实现障碍物体的识别分类和环境的局部分割，在点云低密度的环境下仍有良好的效果，但MKF PointNet++算法在每一分层结构中都需要判断是否满足点云密度需求，如果不满足需要重新进行采样，这样会大大增加算法的时间。2021年武汉大学陈阳提出了一种改进的PointNet++网络结构[15]，该结构将单个点的特征和全局特征集中在质心点上，以便于分类。这些改进PointNet++网络结构的出现为之后基于深度学习的点云分割方法指引了方向，具有重要的理论研究价值。

该文在PointNet++研究的基础上，引入K-近邻优化球查询算法，选取球邻域中特征联系更为紧密的点作为局部特征提取点，加强了局部特征的表达效果。

1 优化球查询算法

1.1 球查询算法

PointNet++采用球查询作为点集重叠划分的方法。球查询算法首先获取局部邻域中重要中心点作为球心，为尽可能覆盖局部邻域中的所有点，PointNet++采用最远点采样的方法。最远点采样方法作为点云数据处理常用的采样方法之一，它的核心思想是：首先在输入的点云数据集中随机抽取一个数据点作为起始点，将起始点归入采样点集合，计算所有点到起始点的欧氏距离，从中选择距离最大值对应的点归入采样点集合，依次迭代，直至达到所需数量要求。

将最远点采样获取到的点设为球心划定球形邻域N，在球形邻域中实施球查询算法，选取球形邻域的半径r以及选取的特征点数m，用公式(1)表示为：

q(r,m)={‖s-s0‖≤r,count(s)≤m,

∀s∈N}

(1)

其中，count(s)≤m表示在球邻域中选取前m个距离小于半径r的点。在分割网络中，记录球邻域中的点到中心点的欧氏距离，找到所有距离小于r的点，将这些点根据数据输入时的索引下标排序，选取前m个点作为局部特征提取点。对于特征点m的选取，存在以下两种情况：

(1)如图1所示，在球形邻域a中，当与球形邻域中心点距离小于r的点不足m个时，将索引下标最小的点复制多次，凑足m个点进行局部特征提取；

(2)在球形邻域b中，当与球形邻域中心点距离小于r的点超过m个时，根据索引下标对其切片，选取索引下标最小的前m个点提取局部特征。

图1 球查询算法示意图

球查询对于m个特征点的选取通过索引下标排序，具有随机性，没有选取距离球形邻域中心点最近的m个点提取特征，因此获取到的局部特征表征能力较差，导致网络的分割精度仍存在较大的提升空间。为了丰富局部特征的表征能力，提高分割精度，采用K-近邻优化球查询算法。

1.2 K-近邻优化球查询算法

K-近邻算法是一种出现较早的经典机器学习算法。该算法的核心思想是：在给定的样本特征空间中，如果待预测样本附近的k个样本多数属于某一个样本类别，则该样本也属于该类别。该算法不需要初始训练，仅仅在待预测样本分类时进行预测，如此可以减少模型训练的开销，是一种惰性学习算法，也是分类数据简单并且有效的算法，算法中k值的选择、距离度量和分类决策规则是K-近邻算法的三要素。

为合理优化球查询算法，将K-近邻中的k值作为待测特征点的个数m，设置球邻域中的特征点与中心点距离升序排序函数K(s)，K-近邻优化后的球查询算法用公式(2)表示为：

q(r,k)={‖s-s0‖≤r,count(K(s))≤k,

∀s∈N}

(2)

其中，K(s)表示对球邻域的点与中心点的距离进行升序排序，从距离小于r的点选取前k个点作为局部特征的提取点，对于特征点k的选取，存在以下两种情况：

(1)当球邻域中与中心点距离小于r的点不足k个时，将距离中心点最近的点复制多次，凑足k个，提取局部特征。

(2)当球邻域中与中心点的距离小于r的点超过k个时，选取距离最小的前k个点提取局部特征。

将K-近邻优化的球查询算法应用于PointNet++分割网络并进行对比实验，验证算法的有效性。

2 优化球查询算法应用于PointNet++网络

PointNet网络模型将所有特征点最大池化为一个全局特征，整个网络模型没有考虑局部特征的提取，因此该网络模型对于局部邻域点云特征的描述能力较弱，在分类或单个物体的分割中，缺少的局部特征可以通过中心化物体的坐标轴缓解，但在场景分割中，由于缺乏局部特征细节描述能力，导致点云数据的分割效果较差。

PointNet++通过引入了多尺度分组和多分辨率分组对局部区域采用PointNet提取局部区域的全局特征作为局部特征，最后将不同尺度的特征拼接起来。由于多尺度分组的方法计算量大，PointNet++采用了多分辨率的方法。如图2(a)所示，外围圆代表局部区域，在局部区域中采用最远点采样的方法获取多个重要的中心点s0。将K-近邻优化的球查询算法应用到局部特征点选取，以中心点s0为球心，r为半径划定球形邻域，根据特征点距离中心点的距离，选取最近的k个点提取其局部邻域特征，当某球形邻域中的点少于k个，则复制最近的点进行特征提取。如图2(b)所示，将提取到的局部特征再次提取并与包围这几个交叉球形邻域的局部区域的局部特征连接形成多分辨率局部特征。

图2 局部邻域多分辨率特征提取示意图

3 实验结果与分析

3.1 实验一

将斯坦福大学开发的带有像素级语义标注的语义数据集S3DIS[16]输入优化球查询算法的分割网络和原分割网络进行对比。实验是在处理器为Intel(R) Core(TM)i7-9700 CPU @3.00 GHz，内存为64 GB，显卡为TITAN RTX的工作站上完成的。

S3DIS数据集由6个大型室内区域组成，总共包括544个房间，超过了2.15亿个点，包括办公区域、教育和展览空间，以及会议室、个人办公室、卫生间、开放空间、大堂、楼梯和走廊。每个点包含坐标信息XYZ、归一化坐标和颜色信息RGB，同时还附加了所属的13个语义标签类别信息(桌子、椅子、沙发、书架和木板等)。

S3DIS数据集常用的数据形式有三种：原数据集、Stanford3dDataset_v1.2_Aligned_Version和indoor3d_sem_seg_hdf5_data。该文选取indoor3d_sem_seg_hdf5_data作为研究对象，该数据集格式是对原始数据场景的切割，把大场景切割成1mx1m的block，完整数据集被切割成了23 585个block,每个block是4 096个点,每个点对应9个维度，具体表达为{X,Y,Z,R,G,B,X0,Y0,Z0}。其中X,Y,Z为目标物表面点云的空间坐标信息，是用来描述点云信息必不可少的特征，R,G,B为目标物体影像在点云上的颜色纹理映射，X0,Y0,Z0为输入点云的归一化坐标。

为了验证K-近邻优化球查询算法k值对分割结果的影响，将每个block的4 096个点作为一个局部领域样本数N，设置训练次数epoch为300，邻域点数k分别取64、128、256、512、1 024情况下，获取场景分割mIoU的评估结果。如图3所示，经过多次实验得出，当k为512时得到了较好的分割评估结果。

图3 原网络与优化球查询算法网络分割精度对比

如图4所示，为验证优化球查询算法的PointNet++分割网络可以获得比原分割网络更高的交并比，同时为去除偶然性将k为512的优化球查询分割网络与原分割网路执行三次对比实验。将优化球查询算法PointNet++分割网络得出的训练结果命名为improve ball query1、improve ball query2和improve ball query3；另外ball query1、ball query2和ball query3为原PointNet++分割网络的三次训练结果。三次对比实验均证实采用优化球查询算法具有更加丰富的局部特征表征能力。

图4 原网络与优化球查询算法网络分割精度对比

为进一步验证优化算法的鲁棒性，从三次实验结果中选取improve ball query1与原网络实验结果ball query1损失函数(loss function)[17]进行对比。在机器学习中，损失函数是用来估量模型的预测值f(x)与真实值Y的不一致程度，损失函数越小，一般代表模型的鲁棒性越好。如图5所示，优化球查询算法PointNet++分割网络的实验结果improve ball query1在相同训练次数的情况下损失函数低于原分割网络结果ball query1。

图5 原网络与优化球查询算法网络损失函数对比

优化球查询算法的PointNet++分割网络虽然在分割精度和损失函数上取得了不错的成效，但在每次球查询时需要对球邻域中的特征点根据欧氏距离进行排序，因此相比于原分割网络时间复杂度更高。如图6所示，优化球查询算法PointNet++分割网络的实验结果improve ball query1比原网络实验结果ball query1在相同训练批次的情况下所需时间更多。

图6 原网络与优化球查询算法网络训练所需时间对比

选取S3DIS数据集Area_5，将优化球查询算法PointNet++分割网络在测试时所需时间与原分割网络进行对比，如图7所示，优化球查询算法PointNet++分割网络实验结果improve ball query与原网络测试结果ball query在相同测试数据集的情况下，所需时间相差很小。

图7 原网络与优化球查询算法网络

3.2 实验二

将优化球查询算法后的分割网络应用到ShapeNetPart数据集[18]作为可视化分割样本与原网络对比。ShapeNet是普林斯顿大学、斯坦福大学进行计算机图形学[19]，计算机视觉，机器人技术和其他相关学科的研究开发的数据集。它由16种对象类型的16 881个计算机辅助设计模型组成，对象中的每个点对应一个零件标签，共有50个类别，每个对象类型有2到6个零件类别。从每个3D模型中抽取1 024个点进行训练和测试。

如图8所示，左边为点云数据对应的图像类型，中间为原PointNet++对点云数据的可视化分割结果，右边为优化球查询算法后PointNet++分割网络获取的可视化分割结果，框选部分为原分割网络与优化球查询算法分割网络可视化结果对比区域。实验结果表明，优化后的球查询算法更易捕捉精细几何结构的局部特征，强化了局部特征的表征能力，对细节特征的表达展示了更好的效果。

图8 ShapeNetPart可视化分割结果

4 结束语

采用K-近邻优化球查询算法，选取球邻域中特征联系更为紧密的点作为局部特征提取点，加强了局部特征的表达效果。将优化后的球查询算法应用于PointNet++分割网络，通过多次实验表明优化后球查询算法更加丰富了网络局部特征的表征能力，强化了细节特征的表达效果，获得了更高的分割精度；但是增加了球邻域选取局部特征点的时间复杂度，因此在丰富局部特征表征能力的情况下，降低算法的时间复杂度是需要进一步研究的内容。