点云数据在深度学习中表示方法的研究

张 婧，周明全，耿国华

西北大学 文化遗产数字化国家地方联合工程研究中心，西安 710127

1 引言

随着深度学习的发展，在计算机视觉领域中如何将具有无序性的点云数据表示成深度学习网络可以接收的有序数据结构，用于深度学习的训练是亟待解决的问题。现阶段深度学习被广泛地用于2D 图像特征提取，并且在大多数图像分析和理解任务中，已经证明它们优于传统算法的解决方案。在点云的深度学习中，主要的解决方法是将3D模型转换为规则的2D图像表示，将用于2D 图像的深度学习方法应用于不规则3D 模型。如何表达三维模型能够实现点云在深度学习中的端到端的输入而不需要把三维3D数据转换为2D图像，是本文要解决的问题。点云数据的另一个特点是海量性，如何对大规模的无序的点云模型进行有效的三维表示与管理，为后期模型数据的分析提供基础，是另一个亟待解决的问题。

为解决以上问题，本章提出基于八叉树和三维K-D树的集成索引（OctKD）的点云数据表示方法。本文的主要贡献是：

（1）提出一种深度学习卷积神经网络可以接受的，能够端到端表示点云模型的OctK数据结构。

（2）OctKD 的点云模型表示方法，能够真实反映模型本身的细节特征。

（3）提出一种新颖的完全在GPU 端以并行方式构造八叉树的算法，降低了点云模型的构造时间。

（4）针对点云模型的散乱性，采用三维K-D 树索引单个三维空间点，提高点云检索效率。

2 相关研究

点云模型目前常用的表示方法有多视图、体素和点云结构。基于视图的表示方法[1-5]首先从具有固定视点的原始对象获取2D 视图，然后将这些视图作为对象信息，利用图像处理中的一些成熟的方法来处理这些图像，并从中提取特征。基于视图的方法由于其灵活性和良好的性能而引起人们的极大关注。多视图卷积神经网络把三维模型转换为二维图像，然后应用二维卷积网络处理，但3D数据的计算量将会极大的增加，就是所谓的“维数灾难”。目前比较常用的是基于体素的表示，Wu 等人[6]提出ShapeNets，是第一个将卷积神经网络应用于三维表示，将对象的3D数据表示为30×30×30大小的“立体栅格”。Daniel 等人[7]提出 VoxNet，将点云划分为等间距的3D 体素，并通过新引入的体素特征编码层将每个体素内的一组点转换为统一的特征表示，然而这种表示由于数据稀疏性和卷积计算成本的约束，要求其分辨率不能高。Li等人[8]提出一种处理点云数据稀疏问题的方法，但是这种方法是在稀疏模型上进行的，因此还是无法处理大量点云数据。Fang等人[9]和Guo等人[10]提出将三维数据转换为向量矩阵，通过提取特征向量达到特征提取的目的。Wang等人[11]提出将点云模型八叉树表示，该方法将所有三维模型用深度为8的八叉树表示，最后叶节点中的点云用平均法向量表示，这种将点云模型法向量表示的方法，模型表示的精确度不够。在基于点云的表示方法中，Qi等人[12]设计了一种直接消耗点云的新型神经网络，它保证输入点的置换不变性，将网络命名为PointNet，但是PointNet 网络不会捕获由度量空间点所引发的局部结构，从而限制了识别细粒度模式的能力以及对复杂场景的普遍性，之后Qi等人[13]提出了新的集合学习层，以自适应地组合来自多个尺度的特征，该网络命名为PointNet++。山东大学的Li等人[14]为了让卷积神经网络（CNN）更好地处理不规则和无序的点云数据，提出了PointCNN网络。

3 GPU并行生成八叉树算法

3.1 算法步骤概述

采用自顶向下的方式逐层并行构建八叉树，规定根节点层为第0层，一棵深度为L的八叉树其层号最大取值为L-1，算法流程图如图1所示。

图1 算法流程图

步骤1将无组织的点云转换成体素空间。

步骤2在体素空间中对点云模型进行八叉树空间剖分，区分并标记空节点和非空节点，统计非空节点的总数。

步骤3根据八叉树叶节点的数量，为每个叶节点开辟存储空间，对八叉树编码。

步骤4从第0层起，自顶向下逐层构建节点间的关系，每次只处理一层，对每层节点并行处理。

3.2 点云转换成体素空间

初始时求出点云模型中顶点的最大、最小值顶点(xmax,ymax,zmax)和(xmin,ymin,zmin)。以这两点为对角顶点构成空间包围盒，并将其作为数据点云拓扑关系的根模型。包围盒沿x、y、z轴的长度分别为：Lx=|xmax-xmin|、W y=|ymax-ymin|、H z=|zmax-zmin|。在顶点(xmin,ymin,zmin)上固定一坐标系，方向与欧氏空间的x、y、z方向相同，坐标为整数坐标，构成一空间，称为空间Z3。该空间是3D离散空间，是三维欧氏空间的子空间(Z⊂R3)，在逻辑上该空间为根节点。

3.3 八叉树空间剖分

在Z3空间中，以深度优先的方式递归细分包围模型的立方体，将外部立方体划分为相同大小的8 个子类，每个子立方体被视为根节点的8个叶节点。当立方体被剖分成8个小的立方体时，空间物体分别位于这些子立方体的不同部分。若模型的点云在该节点或者立方体上，则该节点标记为FULL，否则该节点标记为NULL，同时该节点无需进行剖分，如公式（1）所示：

在每个步骤中，对于当前深度l遍历被三维模型曲面占据的非空的节点，并在下一个l+1 深度将它们分别细分为8 个孩子节点。重复这个过程直到达到终止条件，终止条件为预定义深度或者叶子节点的大小。图2（a）所示为点云模型的八叉树空间剖分，图2（b）为其对应的八叉树表示。分割的每个单元格的大小为Δx=Lx/l、Δy=Wy/l、Δz=HZ/l，其中l为分割的层数。

图2 八叉树剖分与表示

3.4 改进的八叉树编码方式

在本节中，描述如何从给定的一组点云数据集Q={qi|i=0,1,…,N} 构建具有最大深度D的八叉树O。（1）按照3.2节中的方式先把点云模型转化为体素空间，并对体素空间进行八叉树剖分。（2）按照文献[11]的思想设计八叉树的存储方式，引入一个索引数组和哈希函数用于寻找不同深度的节点对应关系以进行下采样，同时为父节点的8 个子节点构造邻域，用于邻域快速计算。

八叉树节点的表示。记录八叉树节点较复杂，主要包含三条信息：

（1）向量sl：记录八叉树叶节点的三维空间坐标。

（2）点集t：记录每个节点所封闭的点。

（3）索引p：标记父节点与子节点，及子节点之间的邻域关系。

向量sl：为了记录八叉树l层的n个节点，用一个维一的 3n长的字符串key(Ο)=i1j1k1i2j2k2…in jnkn表示。in jnkn可以由任意一点坐标计算所得到，具体计算方法是已知任意一点P的坐标为(x,y,z)，则点P所在的单元格坐标为：

in=(x-xmin)/Δx，jn=(y-ymin)/Δy，kn=(z-zmin)/Δz in jnkn即八叉树分割中每个点所在单元格的三维空间坐标(i,j,k)，是3D立方体中的单元格的相对位置。

按照in jnkn升序的方式对八叉树空间的位置排序并将八叉树第l层排序好的空间位置存储在sl向量中。sl之后用于构建三维卷积的八叉树的邻域。在实现中，每个空间位置存储在32位整数中。图3列举八叉树节点的二维空间位置，图4显示每层对应的排序。

图3 二维空间中图像的四叉树构造

图4 每层节点对应的排序

4 构建八叉树

4.1 构建节点间的邻接关系

对于每个节点，需要记录其父节点、8个子节点，相邻节点。在一般的八叉树数据结构中使用指针来表示节点间的相互关系，但本文中，为了节省内存空间，加速计算，丢弃从父节点到子节点的指针，并引入一个哈希函数，用于寻找不同深度的父子节点间的对应关系。

在计算中，需要快速找到相邻层上八叉树上的父子的相邻关系。为l层的非空节点指定一个索引p，表示它是第l层排序节点中第p个非空节点。对于空节点，把它的索引设置为零。l层的所有索引存储在索引向量Ll中。图5 表示二维空间中每个深度的索引向量。对于非空节点，在图5 中被标记成蓝色的节点，其索引为3(L1[2]=3)，因为它是第一层的第三个非空的节点。

图5 索引向量

4.2 逐层并行构造八叉树

在确定一个节点是非空节点后，用原子计数器为其分配一个索引，作为节点在索引向量中的存储位置。从根节点开始，每次只处理一层，每层节点并行处理。再处理第l层时(i＞0)，需要获取第l-1 层即其父节点的索引位置，以构建父子关系。

（1）只有第l深度的非空节点被细分。

（2）根据属性的升序排序节点。一个节点的8个孩子被顺序存储。

（3）父节点和孩子节点的属性向量都遵循相同的顺序。如图5所示，第2层的最后4个节点是第1层的第3个非空节点创建。

5 点云数据组织

文献[11]提出了既节省内存空间，又可以快速进行邻域搜索的八叉树存储方式，但该方法对八叉树叶子节点内的点云仅做了平均法向量处理，并没有提出具体每个点云的组织方式。针对该问题本文结合三维K-D 树的空间索引单个三维空间点云，使大规模点云直接端到端输入深度学习网络成为可能。

5.1 基于K-D树的点云组织

通过八叉树剖分后的点云数据被分到若干个规则节点中，其二维平面结构如图6所示。这种方法采用规则格网剖分，易于实现，具有较好的可操作性，在点云数据的空间分布比较均匀的，且数据量不是很大时也可以达到快速检索的目的，但是当海量数据，且点云数据的空间分布不均匀（如存在局部点云密集）时，这种单一组织方式存在的弊端就会显现。比如叶子节点中点云数据量的不均衡，在数据密集的叶节点中进行坐标点的二次查询仍然是很耗时，难以提高点云数据的检索效率。如果大量增加八叉树的深度，不仅会给数据结构的实现带来困难，也会造成大量“无点”空间的浪费，降低检索效率[15]。

今年云南省局部地区，在授粉阶段成片发生高温热害，造成缺粒减产，产量可能降低30%-50%。主要原因是开花抽丝期间，当温度高于32-35℃，空气湿度低于30%，田间水量低于70%，雄穗开花的时间会显著缩短。因高温干旱，花粉粒在1-2 h内失水干枯，丧失发芽能力，花丝延期抽出，造成花期不遇；或花丝过早枯萎，严重影响授粉结实，形成秃尖、缺粒，产量降低。如能及时浇水，改善田间小气候，可减轻高温干旱的影响。

图6 点云数据的规则间组织二维结构示意图

基于此，文中对存储于叶子节点中的点云数据采用K-D 树进行二次组织。要求存入的数据能够按照一定的规则进行排序，并且按照此规则进行的排序结果必须遵循两个原则：

（1）唯一性。即坐标不同的三维点坐标的排序结果一定不同。

（2）传递性。如果Pn1＞Pn2,Pn2＞Pn3,则Pn1＞Pn3(Pn3为三维坐标点）。

在每个八叉树叶子节点内构建K-D树的步骤为：

（1）将八叉树叶子节点作为K-D 树的根节点，该节点内包含的点{P}作为预分割点集。

（2）将叶节点进行“分维”处理，在一维空间中进行排序操作。首先将坐标点投影到x轴上进行比较，如果相同，再投影到y轴上比较，依次拓展到z轴进行判断。对于任意两个点Pn1和Pn2，其对应的坐标点为(x1,y1,z1)和 (x2,y2,z2)，那么

if(x1≠x2)，以x轴为法向平面将点集{P}分割为2 个集合，设P1为左集合，P2为右集合。

if(x1=x2)and(y1≠y2)，以y轴为法向平面将点集{P}分割为2个集合，设P1为左集合，P2为右集合。

if(x1=x2)and(y1=y2)and(z1≠z2)，以z轴为法向平面将点集{P}分割为2个集合，设P1为左集合，P2为右集合。

（3）更新点集{P}，在P1和P2中分别执行构建K-D树。

5.2 点云数据组织结构设计

通过上述分析，三维点数据以坐标为关键字直接存储在K-D树中，而K-D树作为二级组织结构关联存储于空间八叉树的叶子节点中。这种结构的内存实现比较容易（其数据结构如图7所示）。

图7 点云数据组织的结构图

6 实验结果与分析

6.1 实验环境

算 法 在 一 台 Intel Core i7，3.30 GHz 的 CPU 和GeForce GTX 1080 的GPU（8 GB显存）的台式机上完成点云模型的表示。本文使用Visual studio 2013环境下进行CPU 编程，使用OpenGL 进行GPU 编程，并使用OpenGL实现三维模型加载表示。

6.2 实验数据

实验数据以在兵马俑一号坑第三次发掘中扫描的模型数据为例，这些模型经过除噪，孔洞修复后的点云模型如图8 所示，（a）为 10 号坑 4 号俑（G10-4）的手，（b）为9号坑3号俑（G9-3）的头，（c）为9号坑7号俑（G9-7）的腿。

图8 碎片的原始点云模型

6.3 实验分析

实验1 实验结果的可视化

利用本文提出的构造八叉树的算法对图8 中的模型分别进行八叉树剖分，点云模型经过八叉树剖分（深度分别为5和7）后的可视化图如图9至图11所示。

图9 G10-4俑手的可视化表达

图10 G9-3俑头的可视化表达

实验2 与已有方法比较

图11 G9-7俑腿的可视化表达

图12 为将文献[11]的点云模型八叉树表示与本文点云模型八叉树表示方法的比较，其中（a）为G9-3俑头的原始模型，含有46 919 个点云，（b）为使用文献[11]将点云模型用八叉树方法表示，（c）为使用本文提出算法将点云模型用八叉树方法表示。比较图（b）和图（c）可以明显地看出本文提出的算法将点云模型八叉树表示后保留了佣头的眉毛、眼睛、鼻子和嘴巴等细节，而文献[11]提出的八叉树体表示方法模型的细节特征表示模糊。这是因为本文的方法在将模型八叉树化后点云模型使用K-D树的方法进行了组织，能够真实表达模型特征，如图（c）所示，而文献[11]将叶节点中的点云用平均法向量表示，所以文献[11]中看到的特征是平均法向量特征，如图（b）所示。

图12 文献[11]与本文点云模型八叉树表示方法的比较

表1展示了G9-3俑头的原始模型（含有46 919个点云），分别在CPU 端使用文献[11]的方法构建八叉树所耗费的时间与在CPU端使用本文的算法构建八叉树所耗费的时间。其中CPU端采用传统的递归分割根节点的方法构建八叉树，八叉树的深度为5、6 和7。通过比较可知，本文所提出的GPU并行构建八叉树的方法，较传统的CPU 算法速度可以提高一个数量级，且构造八叉树的深度越大加速比越高。

表1 八叉树生成算法在CPU和GPU上耗时对比

实验3 点云查找耗时分析

为了验证八叉树与K-D树混合的索引效率，本实验利用图8 的点云模型，其中俑手含有16 274 个点云，俑头含有46 916 个点云，俑腿含有226 792 个点云。分别利用改进八叉树，K-D树和改进八叉树与K-D树的混合索引对点云进行组织，并对指定的同一个点进行查询，查询的时间统计如表2所示，从表中可以看出利用单一的八叉树进行点云的查找的时消耗时间最多，这是由于随着八叉树深度的变大，导致了查询的效率明显下降。而K-D树组织的点云明显可以改善查询的效率，但是随着点云数量的增大其效率降低相对也比较明显。而利用混合结构的索引方式可以大大地改善查询点的效率，非常有利于对点云数据的分析、可视化与交互。

表2 三种不同的算法点云查找耗时对比表

实验4 OctKD混合索引在深度学习中的应用

将本文提出的OctKD混合索引结构应用于文献[11]提出的三维模型分割的卷积神经网络。文献[11]提出的深度分割网络为：

其中Ul表示为convolution+BN+Relu+pooling，DUl表示为unpooling+deconvolution+BN+Relu，d为八叉树的深度。图13为将OctKD混合索引结构应用于深度网络所得到的特征提取图和模型分割图。黄色、绿色、紫色来表示该碎块被分割出的不同面，红色表示粗分割线，桔黄色表示精细分割结果。

图13 OctKD在深度学习中的应用

7 结束语

对于机器学习任务，模型表示是至关重要的一步。发现和表达原始数据的能力是决定算法整体性能的重要因素。因此，本章的目标是寻找能够代表3D 对象而且能够用于深度学习的表达方式。针对海量散乱点云数据不能直接输入深度学习网络进行学习的问题，提出基于八叉树和三维K-D 树的集成索引（OctKD）的点云数据的表示方法。该方法即克服传统八叉树编码浪费空间的问题，又实现层与层之间以及八叉树节点的邻域信息之间的快速访问。实验表明这种新的点云模型的OctKD数据结构优化模型在卷积神经网络上的训练，是一种深度学习能够处理点云数据的数据结构。最后按层构造八叉树，在同一层上的所有八叉树节点并行处理的，实现点云数据在GPU上的并行处理。