BTDGCNN：面向三维点云拓扑结构的BallTree动态图卷积神经网络

张学典，方 慧

(上海理工大学 光电信息与计算机工程学院，上海 200093)

1 引 言

三维激光扫描、二维影像的三维重建、三维模型逆向点云获取点云数据的方法不断发展，三维成像技术日趋成熟，三维点云运用场景越来越广泛，如室内导航[1]、机器人[2]、自动驾驶[3]、三维重建[4]，均需要对点云进行高级处理和分析.最近，学者们发布了一系列深度学习架构应用在点云上的相关研究，主要分为以下三类深度学习方法：基于多视图的方法、基于体素网格的方法和基于三维几何数据的方法.在多视图中，Wei等[5]通过将多个视图视为grpah节点，在View-GCN中使用了有向图.然后将由局部图卷积、非局部消息传递和选择性视图采样组成的核心层应用于所构建的图.所有级别的最大集合节点特征的连接最终用于形成全局形状描述符，但得到的结果丢失了大量的空间几何信息.为了解决点云稀疏、无结构、无序的缺陷，OctNet[6]采用位串表征进行编码，通过简单的算法索引每个体素的特征向量，文献[7-11]也对体素网格进一步改进，但都存在大量的无效、冗余的信息，大大增加了计算量，空间复杂度高.

所以精确地分类和分割点云仍然是一个挑战.已有的PointNet[12]、PointNet++[13]模型均是直接对点云数据进行处理，注重独立提取点云特征而忽略了点之间的几何关联，从而丢失了许多局部特征.同样地，PAConv[14]利用了PointNet++的点云预处理模块，仍存在局部特征丢失的缺陷.因此，DGCNN[15]和LDGCNN[16]提出了相关的边卷积来解决这个问题，然而，在实验过程中发现，这两种方法仍丢失了边缘向量.

为了解决这些问题，本文提出了面向三维点云拓扑结构的BallTree动态图卷积神经网络，意在探索一种深度学习架构，以便能够有效地提取三维点云的拓扑结构信息.由于本文的方法利用balltree[17]图来寻找邻点，生成动态图，所以称之为BTDGCNN.为了捕捉特征之间的几何关联，本文提出了BAT边卷积用于捕获局部几何结构，同时保持不变性.为了提高非结构化点云的处理效率，提出了Bat-Net模块，实现点云空间对齐.在实验中，本文在ModelNet40[18]以及ShapeNet[19]两个公开数据集上评估BTDGCNN网络.实验结果表明，本文的方法有效提升了点云分类分割性能，三维点云拓扑结构的信息提取能力得到增强.

2 本文方法

PointNet是第1个直接处理原始点云的深度学习网络，该网络直接将点云作为输入，连接逐点特征和聚集的全局特征，以进行逐点预测，进而实现对三维数据的分类与分割，但其不能捕捉到由度量空间所产生的局部结构，限制了PointNet识别细粒度模式的能力以及对复杂场景的泛化能力.而分层神经网络PointNet++，一种新的集合学习层来自适应地组合多尺度特征，但该网络的卷积不适用于具有距离度量的无序点集.尽管PCNN[20]应用于点云中的每个点，以学习逐点特征，利用点云中表示的数据的空间局部相关性，将三维点云运用到大规模物体检测，但固有地缺乏点云拓扑结构信息.而用来恢复拓扑结构的DGCNN和LDGCNN虽然可以丰富点云的表示能力，但在实验的过程中，丢失了距离向量.

因此，本文提出了一种面向三维点云拓扑结构的BallTree动态图卷积神经网络，并不是像PointNet和PointNet++逐点提取点云特征，也与PCNN逐点卷积不同，是结合DGCNN的边卷积，同时利用相邻节点对之间的边以及该节点共同的作用，通过图神经网络构建局部有向图.与DGCNN不同之处在于，其对每对点进行pairwise的距离计算找出K最近邻点，所以速度比较慢，无法对高维数据进行处理，并且在实验过程中丢失了距离向量.类似地，杨永涛等利用曲率和立方体素栅格计算点云的距离无法在曲率较小的点云上表现.而本文通过balltree在一系列嵌套的超球体上分割数据，在三维数据上表现很高效.此外，本文只利用3个边卷积层进行点云的分割与分类，实现轻量级网络，利用PointNet与LDGCNN的分类和分割思路，构建了面向三维点云拓扑结构的BallTree动态图卷积神经网络(BTDGCNN)，在ModelNet40与ShapeNet 数据集上表现了较好的分类与分割结果，提升了三维点云的拓扑结构信息获取能力.在下文中，将讨论相关研究问题及相应的解决方案.

2.1 问题描述

在本节中，对图生成、图特征提取、balltree与Bat-Net、边卷积模块以及BTDGCNN架构进行详细阐述.

本文方法中，以一组三维点云作为输入：

pi={(xi，yi，zi)|i=1，2，…，n)}

(1)

其中，pi是点云中的一个点，由(xi，yi，zi)这3个表示位置信息的坐标组成，i和n分别表示点的索引下标与点个数.

本文主要研究任务为：点云的分类与分割.对于点云分类，本文需要对点云进行处理，通过BTDGCNN模型找到了一个分类函数fc，从而对整个点云进行分类，将输入点云转换为每个类别上的概率分布pθ：

pθ=fc({p1，p2，…，pn})

(2)

对于点云分割，每个点都可以归为一个特定的类别.因此通过BTDGCNN模型找到了一个分割函数fs，以计算每个点pi的类别的每种类别pθi的概率分布：

{pθi|i=1，2，…，n}={fs(pi)|i=1，2，…，n}

(3)

2.2 图生成

图神经网络适用于处理点云，正是因为其可以独立地在每个节点上传播，节点输入顺序不受影响，并且可以通过提取边以学习两节点之间的依赖信息.为了将图神经网络应用在点云上，首要的是需将点云转换成有向图.图G包括顶点V和边E：

G=(V，E)

(4)

其中顶点V={1，…，n}和边E⊆V×V.

由于会消耗大量内存，所以本文不为点云构建完全连接的边，如图1所示，本文利用balltree图构造一个局部有向图，

图1 Balltree图搜索最近邻

在该图中，搜索点p的半径为r的最近邻，即满足‖p-pt‖≤r(其中pt是搜索的目标点)，从根节点p开始从上至下递归遍历每个可能包含最终近邻的子空间pc，如果子空间的半径radius(pc)与r之和小于或等于pc中心点center(pc)到目标点p的距离，即(radius(pc)+r)≤‖center(pc)-p‖，就在满足该条件的子空间样本点内递归搜索满足‖p-d‖≤r的点即为本文所需最近邻点，对于目标空间(p，r)，遍历搜索所有被该超球体截断的子超球体内的所有子空间，由于子超球体Ⅰ与Ⅱ被p所截，而对于Ⅰ与Ⅱ内的子空间，Ⅳ，Ⅷ，Ⅵ，又被p所截，所以接下来就会在Ⅳ，Ⅷ，Ⅵ内进行线性搜索，诸如Ⅲ，Ⅴ，Ⅶ这些距离太远的子空间将被舍去，最终得到最近邻为[p4，p6]，接下来，就可以在欧氏空间和特征空间中构造局部图.其中，Ⅰ～Ⅷ为子空间，p为根节点，pi(i=1，…，n)为空间中的点.

算法1说明了balltree图的邻域搜索神经网络算法，其中pn表示到目前为止找到的一系列可以作为目标点pt的最近邻点，ds是目标点与之前发现节点的最小距离(ds=maxp∈pn|p-pt|)，dc表示目标点pt与当前节点pcn间的距离(dc=max{dR·Parent|pt-center(R)|-radius(R)})，R是整个搜索区，K是限定的列表大小.

算法1.balltree图邻域搜索神经网络算法

1.程序开始 搜索(pn，pcn，r，K)

2.如果满足(dc>=ds∧dc>r)

3. 则返回pn

4.如果pcn是一个叶子节点

5. 则pout=pn

6.对于∀p∈points(pcn)，如果满足(|p-pt|

7. 则将p添加到pout

8.如果满足(|pout|==K+1)

9. 则从pout移除离它最远的节点，并更新ds

10.否则dr=以childr为中心的距离

12.dl=以childl为中心的距离

13.ptemp=pn

14.如果(dr<=radius(childr(pcn))+r)

15. 则ptemp=搜索(pn，childr，r)

16.如果(dl<=radius(childl(pcn))+r)

17. 则pout=搜索(ptemp，childl，r)

2.3 balltree与Bat-Net变换网络

为了改进KDtree的二叉树树形结构，并且沿着笛卡尔坐标进行划分的低效率，balltree将在一系列嵌套的超球体上分割数据，使用超球面而不是超矩形划分区域.虽然在构建数据结构的花费上大过于KDtree，但是在三维甚至很高维的数据上都表现的很高效.球树递归地将数据划分为由质心p和半径r定义的节点，使得节点中的每个点都位于由r和p定义的超球内.通过使用三角不等式来减少邻居搜索的候选点数量.如图1所示，选择一个距离当前圆心最远的观测点i1，和距离i1最远的观测点i2，将圆中所有离这两个点最近的观测点都赋给这两个簇的中心，然后计算每一个簇的中心点和包含所有其所属观测点的最小半径，不断递归得到最近邻点，最终构建balltree.

当使用balltree查询时，如图2所示，先自上而下找到包含目标的叶子结点(p，r)，从此结点中找到离它最近的观测点，该距离即为最近邻的距离的上界.检查它的兄弟结点中是否包含比这个上界更小的观测点，方法是：如果目标点距离兄弟结点的圆心的距离>兄弟节点所在的圆半径+前面的上界的值，若满足上述条件，则这个兄弟结点不可能包含所要的观测点.否则，检查这个兄弟结点是否包含符合条件的观测点.

图2 balltree树查询过程

本文设计的Bat-Net变换网络就是利用balltree图为每个点云估计特定的矩阵，首先无序点云以n×3矩阵形式输入到对齐空间，然后利用balltree图搜索最近邻，连接每个点的坐标与其最近邻点之间坐标的半径r的张量，形成一个3×3的矩阵，最终通过矩阵乘法，产生一个已经由Bat-Net变换网络处理过的n×3的输入点云(矩阵M)，可以偏置点云P：

(5)

其中，mij是旋转矩阵中第i和第j列的值，xi，yi，zi是点云P的其中一个点云pi的坐标.

2.4 BAT边卷积模块

一个C维n点云，P={p1，…，pn}⊆RC，在最简单的三维设置中，每个点都包含三维坐标pi={(xi，yi，zi)|i=1，2，…，n)}，还可以包括表示颜色、表面法线等附加坐标.在深度神经网络架构中，每个后继层都是在前一层输出结果的基础上进行操作，因此，进一步推广到一般情境中，C代表给定层的特征维度.

与DGCNN中边卷积模块不同的是，本文计算表示局部点云结构的有向图G，在最简单的C=3的情况下，构造G作为点云P的balltree图，包括自循环，图中的每个节点V也都会指向节点本身.在第i个顶点处的边卷积输出见式(6)：

p′i=△hθ(pi，pj)

(6)

如上所述，定义边缘特征为eij=hθ(pi，pj)，其中hθ：RC×RC→RC′是带有一组可学习参数Θ的非线性函数，pi，pj则是有向图中的两个节点.然后，定义边卷积操作△，通过从每个顶点发出的所有边相关联的边特征上应用通道对称聚集操作来进行定义，p′i表示在第i个顶点处的边卷积.

BAT边卷积可以很好地获取输入点云的局部特征，然而，如果在BTDGCNN中单纯地增加BAT边卷积层数，经实验验证，并不能提高对点云的分类与分割效果，反而伴随着BAT边卷积层数的增加出现较差的分类与分割效果的现象，该内容将会在本文的第4节实验中详细阐明.

3 BTDGCNN架构

本文的BTDGCNN架构如图3所示，可以分为两部分，即分类和分割，它们共享很大一部分结构.

分类部分包括：

1)输入层：具有n个点的n×3点云模型作为输入，每个点由坐标组成，还可以有表示颜色、表面法线等附加坐标.

2)Bat-Net转换层：如果点云在经历某些几何变换后必须是不变的，那么本文期望，输入点云可以通过Bat-Net转换层学习后的表征对于这些变换是不变的.Tong等[21]利用空间转换器思想，通过采样和插值来对齐二维图像，从而将点云对齐到一个规范空间中，以便于提取特征.本文通过一个Bat-Net小型网络来预测仿射变换矩阵，并将该变换用于输入点云坐标.在该网络中，首先利用balltree图连接每个点的坐标及其相邻点之间坐标差的张量，经估计后将3×3矩阵将输入点集对齐到规范空间，最终输出一个经过对齐空间的n×3点云.

3)BAT边卷积层：本文的BTDGCNN网络共有3个BAT边卷积层，这3个BAT边卷积层输入通道数分别为3、128、128，输出通道数分别为128、128、256.

4)最大池化层：该网络输出为每个通道的前k个最大值，然后将其一维化，从而得到一维张量(k×1024).

分割部分包括局部特征与全局特征聚合器：点云分类与分割需要结合局部以及全局特征，本文通过PointNet中的简单且高效的方式实现.如图3中分割模块所示，计算点云的全局特征向量后，将全局特征向量与每个点的特征向量连接，然后反馈给每个点特征.接下来，通过这些组合的点特征，提取新的每个点特征，这个新的点特征即为局部和全局信息.依赖这种方式，本文网络能够预测每点数量.本文将会在分割实验部分进行详细展示.

图3 BTDGCNN网络架构

4 实 验

为了验证BTDGCNN优化网络的可行性和优越性，本文选用ModelNet40数据集和ShapeNet Parts数据集这两个数据集来进行分割与分类实验验证.并与其他已有的网络模型，如PointNet、PointNet++、PCNN、DGCNN、LDGCNN进行性能比较，实验分为以下4个模块：点云可视化、点云分类实验、点云分割实验、BTDGCNN模型复杂度分析.

4.1 点云可视化

本文使用T分布随机邻域嵌入(T-SNE)来显示特征提取器的性能，减少高维特征的维度来可视化特征.如图4所示，每种颜色代表一个类别，对于不相似的点，用一个较小的距离产生较大的梯度来让这些点排斥开来，而这种排斥又不会无限大，避免不相似的点距离太远.通过图4可以直观地看到提取特征后的点云分别按照颜色分类并且以较小距离排斥开，比原始点云更具区分性，显示了较强的提取拓扑结构信息能力.

图4 原始点云和特征提取的T-SNE可视化

4.2 点云分类实验

4.2.1 数 据

本文在ModelNet40数据集上进行点云分类实验，包括40类CAD模型，将其中9843个形状用于训练，2468个形状用于测试，在该数据集中采样1024个点，并且预测之前从未见过的形状的类别.另外，为了提高网络的泛化能力，对于每一批次的点云模型都需要对其进行旋转操作，随机缩放点云以及丢弃点云中不需要的点.并且在训练过程中，通过随机缩放对象和点的位置来增加数据.

4.2.2 架 构

如图3中分类网络所示，本文使用3层BAT边卷积层来提取点云的几何特征，基于每个BAT边卷积层提取的特征进行计算，并将计算得到的新图用于下一层卷积层.利用MLP得到n×1024的高维特征采样点，以保证动态图更新的同时，可以将语义上特征相近的点聚合，来提取不同层级的点云的局域特征信息.然后，将全局特征与各个BAT边卷积层中提取的局部特征信息进行拼接，以聚合多尺度要素.通过最大池化操作获得1×1024的全局特征.最终通过一个3层的MLP将所有特征信息融合，并对高维特征降维，输出分类分数p.

4.2.3 训 练

本文模型进行训练的实验参数设置如表1所示，硬件环境为dellt640-PowerEdge-T640电脑、英特尔Intel® Xeon(R)Silver 4210 CPU@2.20GHz×40处理器、30.9 GiB运行内存.

表1 实验参数设置

4.2.4 结 果

由表2和图4可知，本文模型在ModelNet40数据集上取得了最好的分类结果.对于相同的输入点云(1024点)，在同一软硬件环境下，BTDGCNN的整体分类准确率(OA)为93.6%，相比PointNet高出了4.4个百分点，比PointNet++高出了2.9个百分点，比PCNN高出了1.3个百分点，这充分说明了本文的BTDGCNN网络可以很好地实现三维点云的分类任务.比DGCNN高出2个百分点，表明网络深度合适时(本文卷积层为3层)，点云分类才能达到最好的效果.比LDGCNN高1.4个百分点，更加展现了本文的BTDGCNN模型在提升网络精度上的极佳能力.

表2 对于相同的输入点云(1024点)，不同模型在ModelNet40上的分类结果

通过实验可以发现，在图5中，当迭代次数增加，模型在ModelNet40数据集上分类的精度拟合程度越来越好，可以达到93.6%，但随着迭代次数持续增加，过拟合问题随之而来，导致模型的泛化能力下降.通过对比实验发现，当迭代次数为250时，模型的分类能力最强，高于其他4类方法.

图5 分类训练、测试精度曲线

4.3 点云分割实验

4.3.1 数 据

本文基于ShapeNet Parts数据集评估点云分割模型，该数据集中共由16881个形状，包括16个类别以及50个部件，其中16个类分别为飞机(2690个)、背包(76个)、帐篷(55个)、汽车(898个)、椅子(3758个)、电话(69个)、吉他(787个)、小刀(392个)、台灯(1547个)、手提电脑(451个)、摩托车(202个)、茶杯(184个)、手枪(283个)、火箭(66个)、滑板(152个)、桌子(5271个).此外，在ShapeNet Parts数据集上采样2048个点用于分割实验.

4.3.2 架 构

点云分割架构如图3中分割网络所示，分割网络是分类网络的扩展，本文将各层提取的局部特征与全局特征叠加，并使用MLPs来计算每个点的割分数.最后，在每一层中应用RELU和Batchnorm，以实现对点云的归一化操作，并且在MLP层后面设置值为0.5的Dropout层，以达到可以比较有效的缓解过拟合的发生，在一定程度上达到正则化的效果.

4.3.3 训 练

点云分割实验的设置采用与分类实验相同的训练设置.

4.3.4 结 果

本文使用所有类的均交并比(mIoU)来对语义分割结果进行评估，其中，所有类的交并比(IoU)按照下式进行计算：

(7)

其中，TP(真正)，预测正确，预测结果是正类，真实是正类；FP(假正)，预测错误，预测结果是正类，真实是负类；FN(假负)，预测错误，预测结果是负类，真实是正类；TN(真负)，预测正确，预测结果是负类，真实是负类.

将本文的分割结果与PointNet、PointNet++、PCNN、DGCNN、LDGCNN进行比较，由表3可知，本文的语义分割的平均交并比相比PointNet高出1.7个百分点，比PointNet++高出0.3个百分点，说明本文的BTDGCNN网络对输入无序点云进行处理，可以提高网络整体效率.相比PCNN，DGCNN和LDGCNN均高出0.3个百分点，表明通过3层轻量级BAT边卷积模块，可以获得更佳的点云特征用于分割.

表3 ShapeNet数据集上分割的结果.表中的值是points的mIoU(%)

4.4 BTDGCNN复杂度分析

本文使用ModelNet40分类实验来比较模型的复杂度，表4表明，相比PointNet++与LDGCNN，本文的BTDGCNN网络参数数量分别多了0.3MB，0.7MB，主要是因为本文相比其增加了Bat-Net输入点云转换模块.与PointNet和DGCNN比较，本文提出的网络参数数量分别少了1.7MB，0.06MB，主要在于本文减少了卷积层(本文仅3层BAT边卷积模块)，最终使得本文的BTDGCNN模型结果在分类精度上达到了最佳平衡.

表4 不同模型的参数数量、转发时间以及精确度度

5 结 论

针对三维点云在进行分类分割任务时，对拓扑结构信息提取能力弱以及数据无序且庞大的缺陷，本文提出了一种面向三维点云拓扑结构的BallTree动态图卷积神经网络.通过增加一个Bat-Net转换模块来对输入无序点云进行处理，提高网络整体效率，以及设计3层BAT边卷积模块，简化了网络的复杂程度，以获得的更佳的点云特征用于三维点云的分类及分割.在ModelNet与ShapeNet数据集上的实验表明，本文的BTDGCNN网络已经达到了较好的三维点云拓扑结构的信息提取能力.此外，本文还提供了网络的理论分析以及可视化的分类和分割结果.

未来，本文将考虑把BTDGCNN网络应用于更抽象的点云以及实时环境理解，通过对本文网络的进一步改进，使其能够对更高维的点云进行实验，并且将其适用于现实点云场景的语义分割.