论文阅读02 PVCNN

本文是MIT HAN Lab的工作，通过结合点云的两种表述方式，来设计一种Point + Voxel的融合框架。

简介

• 论文：《PVCNN: Point-Voxel CNN for Efficient 3D Deep Learning》
• 作者：Zhijian Liu，Haotian Tang，Yujun Lin，Song Han
• 机构：MIT && SJTU
• 论文水平：NIPS19 spotlight
• 关键词：PointCloud DeepLearning && Point-Voxel
• 论文链接：paper | code

1. 速览

针对问题：

1. 基于体素的点云深度学习方法，虽然体素化相对于最远点采样更快，但是如果想要获得高分辨率的体素化结果，其内存占用和计算耗时会 cubically 增长

2. 基于点的点云深度学习方法，虽然内存占用很少，但受点云稀疏性的影响，大概有 80% 的时间都消耗在点云计算的准备工作中，所以直接处理点云可能比较耗时

解决方案：

1. 提出了 Point-Voxel 的方式来实现高效又轻量化的点云深度学习
   1. 以点的形式存储数据，减少内存占用
   2. 以体素化形式进行卷积，避免处理点云的不规则、稀疏性带来的数据访问耗时，提高局部感知能力

效果量化：

1. 相同精度下，相比于体素化方法节省10倍GPU内存开销
2. 相比于基于点的方法平均速度提升了7倍
3. narrower version PVCNN在分割的 benchmarks中达到了2倍于PointNet的速度，且精度更高
4. F-PVCNN相对于F-PointNet++，有2.4%的mAP提升以及1.5倍的加速以及GPU内存节省

2. 简介

来自于激光雷达等传感器的3D数据，通常以点云的形式表述，目前对于3D点云的研究，大概分为两个方向，基于体素或是基于点云

Voxel-Based：

体素化方法是通过划分网格，将点云均匀的分成若干网格，这样就可以将不规则的点云表述转变成规则的体素网格，进而应用3D CNN等深度学习方法。但是划分体素化的算法，其时间复杂度一般是和体素网格的尺寸成正比的，较大的体素网格带来的体素化结果也就意味着低分辨率，等价于信息的丢失，想要解决，就需要提高体素化的分辨率，而这时，对应的内存占用是随着尺寸的增加呈立方级别的增长的。这里作者举了例子，3D-UNet的网络输入 batch-size为16，体素化大小为64 x 64 x 64，需要至少10GB的显存占用，这样的内存资源消耗让我们很难提升体素化结果的分辨率

Point-Based：

基于点的方法是直接对输入的点进行处理，由于点云具有稀疏的特性，所以相比于体素化，基于点的方法占用的GPU内存资源更少。但是同样因为点云的稀疏性，输入点云的顺序是紧密排列的，但是并不代表其在三维空间上是紧密的，这样使得算法的执行时间有 80% 以上都用在了对无序点云的内存访问上，真实的算法处理时间不到 20%。

这里所谓的 Random Memory Access其实之的是点云搜索的过程，索引无序又不规则的点云需要很高昂的时间代价，而这是体素化方法不需要承受的。目前大多基于点的方法都是通过聚合每个点的相邻特征来提高感受野，拿PointNet++来举例，PointNet++中需要对点云做若干次的FPS最远点采样，这个过程相比于体素化，是更为耗时的，所以基于点的方法从运行时间来看，也可以进行优化

Point-Voxel：

将以上两种方法相融合，设计一种新方法，其具有基于点的方法的低内存占用，也拥有基于体素的方法的低时间复杂度，对规则体素进行卷积，省略了点级别的内存访问以及动态卷积核，这种方法被作者称为 PVConv，融合CNN之后就是PVCNN

3. Motivation

对于三维数据，可以表示成下面的形式，三维坐标加上对应的特征

基于体素和基于点的卷积都可以概括成下侧的公式，首先对于当前点 xk，索引其周围的点 xi，然后通过核滤波 K 与其周围点的特征进行卷积，得到对应的 yk

3.1 Voxel-Based Models：Large Memory Footprint

前文提过，体素化方法如果想要做到不丢失信息，就需要达到特别高的分辨率。当分辨率较低时，意味着有很多点会同时存在于同一个体素网格中，也就是说经过体素化后丢失的信息就越多。

上图可以看到，当显存为11G时，对应的体素化的分辨率会导致42%的信息丢失，如果想要保留90%以上的信息，需要对应GPU的显存为 83GB，实际工程应用中很难在处理平台上部署这种内存爆炸的方法。

3.2 Point-Based Models: Irregular Memory Access and Dynamic Kernel Overhead

基于点的方法中，作者列举了两类，一类是PointNet，因为PointNet是针对每个点做特征提取的，并没有关注点与点之间的局部特征，而PointNet中使用的就是MLP，通过多次的MLP学习其不变性，并且通过最大池化，处理点云的无序性。PointNet的内存访问是极其高效的，因为不涉及到对无序点的索引遍历。第二类就是对PointNet的改良，在PointNet之后，为了改善PointNet的局部感知能力，在PointNet之前先用特征聚合的方法将局部信息聚合到一起，再通过PointNet提取特征，这些方法之一就是我们所熟悉的PointNet++

但是与此同时，采样算法以及特征聚合过程就涉及到了对无序点云的索引，作者称为 Irregular Memory Access，在这一环节通常引入 dynamic kernel computation，而这就是限制Point-Based方法效率的瓶颈所在。

• 对 Irregular Memory Access 的解释

  基于点的方法不像体素化方法，体素化得到的是规则的体素网格，对于周围信息的聚合操作，只需要索引周围体素网格的 id 即可，但是基于点的方法是对无序点云的直接处理，而点云在三维空间中是不规则分布的，我们并不能通过索引点的 id 的方式找到某一个点的若干邻近点，所以只能通过类似KNN的算法，用高昂的访问时间来换取邻近点的搜寻。

  如上图所示，作者对比了三个较为先进的Point-Based方法，指出其在不规则点云索引上消耗的时间占比分别为36%，52%，57%（PointCNN，DGCNN,SpiderCNN）

• 对 Dynamic Kernel Computation 的解释

  上述步骤后，已经得到了邻近区域的点，接下来就是对这个区域进行卷积，Point-Based的卷积与规则的Voxel-Based卷积方式不同，仍然是由于点云的分布不规则，邻居点的位置并不是固定不变的，所以就需要一个动态计算每个邻近区域的核，上图也可以看到，PointCNN的核计算开销是最大的，甚至超过了50%！

总之，不规则内存访问和动态内核计算的总开销在55％（对于DGCNN）到88％（对于PointCNN）之间，这表明大多数计算都浪费在处理基于点的表示的不规则性上!

4. PVConv

PVConv由低分辨率的基于体素的分支和高分辨率的基于点的分支组成。 基于体素的分支提取粗粒度的邻域信息，并从基于点的分支中对单个点的特征进行细粒度的补充。

上部的基于体素的分支首先将点转换为低分辨率的体素网格，然后通过基于体素的卷积将相邻点聚合在一起，然后将其转换回点。 体素化或反体素化都仅需要对所有点进行一次索引，从而降低了内存成本。 基于点的分支则对每个单独的点提取特征。 由于它不聚合邻居点的信息，因此能够提供非常高的处理速度并且保持高分辨率。

4.1 Voxel-Based Feature Aggregation

前面已经分析了，Point-Based方法在特征聚合时由于点云的不规则分布，特征聚合的耗时明显高于Voxel-Based方法，所以特征聚合是转换为体素进行的。

• 尺度归一化

  这一步是为了处理不同尺寸的输入点云，注意只是对坐标归一化，特征并没有！

  归一化过程如下：

  1. 平移所有点到以中心为原点的局部坐标系中
  2. 所有点除以坐标二范数的最大值，坐标就缩放到了 [-1, 1] 之间
  3. 将 [-1, 1] 的坐标线性映射到 [0, 1]（平移和缩放）

• 点云体素化

  得到范围在 [0, 1] 的体素坐标后，对坐标以及体素分辨率 r 进行计算，得到每个点对应的体素编号，这里对于体素中多个点的特征处理，是仿照PointNet做了平均池化，以平均特征作为当前体素的特征

• 体素卷积、信息聚合

  使用3D体素卷积做特征聚合

• 反体素化

  因为需要将体素化的结果与Point-Based结果做融合，所以需要将体素网格做去体素化处理，这里作者提到一种最近邻插值的方法，但是这种方法是将体素网格与点做映射，反推点的坐标之后，同一个体素网格中的点对应的特征都是一样的。所以作者用了三线性插值上采样，保证每个点都有属于自己的独特的特征。

4.2 Point-Based Feature Transformation

到这里已经完成了网络图中上面分支的学习，而实际上在体素分支将点周围的信息进行特征聚合，得到的只是低分辨率的特征，因为体素的方法注定很难得到较高的分辨率，所以作者就将Point-Based的方法融合到Voxel-Based方法输出的聚合特征中，这样可以增加最终结果的细粒度特征。

具体的操作就是借鉴PointNet的思想，针对每个点提取特征，而仅需使用MLP就可以较好的完成这一工作，并且能够保证较少的算法耗时

4.3 Feature Fusion

将两个分支的结果直接相加，就得到了最终结果

4.4 Discussions

• 关于如何高效运行的细节部分：

  相比于Point-Based的方法，Point-Based提升了 K 倍的速度

  对于PointNet++，在N个点中取其聚合特征，需要找到每一个点周围的 K 个点，对应的时间复杂度是 Kn，而这里的 K 一般为 36/64。在PointCNN中， K 一般为16。

  而Point-Voxel由于在体素中进行聚合，只需要遍历N个点对应哪一个体素即可，故作者提到时间复杂度为 n

• 关于保持点云高分辨率的细节部分：

  作者将PVConv与PointNet++中的SA Module做了对比，输入是[16, 2048, 64] 时，采样临近点数量为125，SA Module需要75.2ms，3.6G显存占用，而PVConv需要25.7ms，1.0G显存占用。但是这里没说SA下采样的数量，作者只是给出，如果SA Module也想达到25.7ms，那么必须下采样到685个点，而这无疑会损失信息。并且这时PVConv的内存占用仍然低于SA Module。

5. Experiments

作者将PVCNN在很多任务上做了测试， 包括3D分割、3D检测等，效果均不错

值得一提的是，PVCNN可以部署在 Jetson Nano上并且达到实时的效果，并且其速度与精度都明显高于PointCNN和PointNet