PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation [CVPR 2017]
论文解读系列第①篇
今天带来的是 CVPR 2017 的一篇文章 PointNet。这片文章可以说是深度学习直接处理原始点云数据 (raw point cloud) 的开篇之作。目前在 Google Scholar 上面查到的引用量已经超过了 2000 次。
一、背景
先来看一看点云与深度学习结合的问题。近年来，深度学习方法取得了广泛的关注和应用，在图像、语音、文字等领域都取得了很好的应用成果。而点云是一种新型的 3D 空间的数据表示格式。它一般以一个四维向量 (x, y, z, i) 表示一个点。其中， (x, y, z) 是空间中的三维坐标，而 i 表示的是该点的反射强度。
当 2D 图像输入到深度学习的网络中时，它是规则的数据，每个像素值的位置都可以以一个二维坐标来表示，且它在空间上是连续的表示，即相邻像素就是在图像中相邻的。而点云的表示方法有所不同。它是无序且非结构化的表示，只是一个由点的坐标构成的集合，而相邻点之间并没有这种空间的相邻关系。这就会造成如下面这样的结果：
如上图：一副点云由若干的点构成，但是同一副点云图像其中点的排列顺序可能会不同，当以两者分别输入卷积网络中时，无论对于分类任务还是对于目标检测任务来讲，会带来不同的结果。然而实际上二者表示的是同一个物体或内容。这显然不是我们想要的结果。
卷积网络需要结构化的输入，而点云的输入是非结构化的，这样就会导致卷积网络并不适用于点云数据，基于此，人们想出了两种预处理方式，来使点云成为结构化的输入。
第一种方法是 multi-view 投影的方法。即以点云在多个视角的投影作为输入，用原来的 2D 图像的卷积网络来处理。
第二种方法是 voxelization 的方法，即把空间划分成离散的体素 (3D voxel)， 然后每个点按照坐标位置决定落到那个体素单元中。这样，就可以把原来无序的点云输入规则化。
但是这种预处理的方式肯定会造成一定的信息损失。
基于此问题，本文的作者就提出了 PointNet 神经网络来处理点云数据。设计了一种直接处理点云来提取特征的新型网络，很好地考虑了对于输入点排列顺序的不变性。以及网络对于输入点集小的扰动和数据破坏（丢失）也具有很好的鲁棒性。
二、网络结构
首先来总结一下点云数据的三个特征以及由此带来的问题：
- Unordered ：点云在采集和存储是都是无序的，因此要求网络必须对一副点云所有可能的输入保持结果不变。
- Interaction among points ：点云中每个点都与其周围的若干点表示了一定的空间结果，但是在存储来讲，并不能表示出这种结构。
- Invariance under transformation ：点云表示了一定的三维结构，这要求网络的处理结果对于点云的旋转、转换等必须保持结果不变性。
针对以上的问题，本文采取的方法是：在初始阶段，对点云中每个点都单独进行相同的处理，然后再应用一个对称函数(MaxPooling)来解决点集的无序性问题。
PointNet 的网络结构如下：
网络的输入即为一个 nx3 的向量，表示 n 个点的三维坐标。可以用于分类任务与分割任务。对于分类任务，输出结果为 k 个分类类别的得分；对于分割任务，输出结果为 n 个点逐个的所属分割部分的得分。
最重要的三个部分已在图中圈出：
- 两个小型的 T-Net 网络用于学习一个坐标变换矩阵，并应于该坐标变换矩阵增强输入数据，使得网络对于输入的旋转等操作具有一定的不变性。
- MaxPooling 操作，以对称函数解决点云输入的不变性。
- Aggregation 操作，将全局特征拼接到每个点的特征后面，用于分类任务。
首先，对于 nx3 的输入数据，先经过一个两层的 MLP ，提取得到每个点的 64 维特征，此外输入数据与特征数据分别经过 input transform 和 feature transform 操作进行增强。这样我们就得到了一个 nx64 的特征，每个点的特征以一个 64 维的向量表示。在此之后，再经过一个三层的 MLP 将 64 维的特征升到 1024 维。 然后经过 maxpooling 操作提取得到一个全局的 1024 维特征。然后输入到分类网络中用以分类。
对于如何解决无序性问题，使得模型能够不受输入的排列顺序的影响。那么作者提出了三种可能的解决方法：(1)是将输入按一个规范顺序排序。这个很显然是不可行的。(2)是将输入作为一个连续的序列来训练一个RNN，并通过所有可能的排序来增加训练数据。一方面，有研究表明在RNN中顺序确实是有影响的，不能被忽略；另一方面，当point clouds 数据集很大的时候，对所有的N!个排列都处理一次也是不现实的。(3)是采用对称函数。
下面来介绍一下对称函数。所谓对称函数，通俗来讲就是参数的输入顺序不会影响函数的结果。如加法、乘法等，都是非常常见且明显的对称函数，可以任意改变参数的顺序。对于 maxpooling 操作来讲，它当然也是对称函数，无论输入的 n 个点的排列顺序如何，在对 nx1024 维的特征应用 maxpooling 操作时，得到的结果永远都是一样的。
这样借用 maxpooling 函数的对称性，我们就可以无视输入的无序性。先对每个点单独地进行相同的操作，然后再应用对称函数提取全局特征就好了。形式上来讲，可以表示为： \[ f(x_1, x_2,...x_n)=g(h(x_1), h(x_2),...h(x_n)) \] 函数 \(f\) 是作用在点集上的函数，函数 \(h\) 是作用在单个点上的函数，而函数 \(g\) 是一个作用在经过处理的点 \(h(x)\) 上的对称函数，这样我们就可以用函数 \(g\) 和 \(h\) 来得到关于点集的操作 \(f\) 。而相关的理论证明，将会在第四部分给出。
对于分割任务来讲，既要考虑全局的特征，又要考虑全局特征，所以做法便是将 1024 维的全局特征聚合到每一个 64 为的点特征之后，这样得到的特征就既包含了全局的信息，也包含了点的局部信息了，从而用于分割任务。
三、结果
在论文中，作者给出了 PointNet 网络在分类、部分分割与场景语义分割三项任务上的结果。
3.1 分类
在 ModelNet40 数据集上分类的准确率如下：
在这项任务中，与 multi-view 与 voxel 的方法进行了对比。
3.2 部分分割
所谓部分分割，就是对每个点生成一个类别标记：
在 ModelNet40 部分分割结果如下，评价指标为 IoU:
3.3 场景语义分割
场景语义分割任务与部分分割任务类似，也是为每个点分配一个类别标记，判断每个点属于哪个物体。数据集为 Stanford 3D semantic parsing data Set.
在这一项任务中，输入不在是三维向量，而是九维，包括 (三维坐标，RGB值，归一化后的三维坐标)。得到的结果如下：
四、理论分析
在这一章节中，给出一些理论上的分析。
4.1 近似逼近性
首先，给出为什么可以用 \(g\) 和 \(h\) 来近似逼近函数 \(f\)。
对于定义在集合上的连续函数 \(f\) , 有如下的性质：
\[ \begin{align} &\chi = \{S:S\subseteq[0,1]^m and\; |S|=n \}\\ &f:\chi \to \mathbb{R},\mbox{ 是一个连续的集合函数。}\\ &\mbox{Hausdorff distance } d_H(.,.) \mbox{ 定义元素之间的距离。}\\ & \forall\, \theta>0, \exist \,\delta>0, for\;any\;S_1,S_2\in\chi:\\ &if\;\;d_H(S_1,S_2)<\delta, then\;|f(S_1)-f(S_2)|<\theta \end{align} \]
由于连续函数 \(f\) 有了这个性质，那么我们就可以定义一个对称函数 \(g\) ，是一个\(\gamma\) 和 max的复合函数。使得函数 \(g\) 作用于 \(h(x)\) 之上的函数值与 \(f(S)\) 之间的数值足够小。
换句话说，我们可以用这样一个作用于每一元素的函数 \(h\) 以及一个对称函数 \(MAX\) 来近似集合函数 \(f\) 。
\[ \begin{align}&\forall \theta>0,\;\exist \mbox{ 一个连续函数 }\;h\\&\mbox{ 和一个对称函数 }\;g(x_1,...,x_n)=\gamma\circ MAX:\\&\mbox{such that for any }\; S\in \chi :\\&\bigg|f(S)-\gamma\bigg(MAX_{x_i\in S}\{h(x_i)\}\bigg)\bigg|<\theta\\& (x_1,...,x_n \mbox{ 是 }S\mbox{ 中的元素。})\end{align} \]
4.2 稳定性分析
第二是全局特征维度的维度K对结果的影响，以及整个网络的鲁棒性分析。
首先令 \(u\) 是由一个点集经过 \(h\) 计算每个点，再进行最大池化，得到一个 k 维向量的函数，那么 \(f\) 可以表示为 \(\gamma\) 和 \(u\) 的复合函数。
那么，对于任意一个点集 S，都存在另外两个点集 C 和 N ，使得在任意一个不小于 C 且不大于N 的点集 T，\(f(S) = f(T)\)。即对于一个集合 \(S\), \(f(S)\) 的函数值，只受到这个集合 \(C\) 的影响，更多的点对于函数的结果并不起到作用。
b)说明C中点的个数不大于K。这个K就是特征的维度。因为我们在用 \(u\) 做最大池化操作时，对于 K 维中的每一个，只会选择来自一个点的特征作为该位的最大值，也就是说 MAXPOOLING 操作只会选择 K 个起作用的点。
因此，maxpooling 时候的特征维度K会影响C，进而影响分类的准确率。
$$ \[\begin{align} & 令\; u: \chi\to\mathbb{R}^K\\ &u=MAX_{X_i\in S}\{h(x_i)\}\;\;即u由一组点生成一个K维的向量。\\ &f=\gamma\circ u,则有：\\ &(a)\;\forall S,\; \exist \mathcal{C}_s \,\mathcal{N}_S\subseteq\chi,\, f(S)=f(T)\;if\;\mathcal{C}_s\subseteq T\subseteq \mathcal{N}_S\\ &(b)\; |\mathcal{C}_S|\leq K \end{align}\] $$
\[ \begin{align} &(a)式说明\;f(S)\;的函数值由一组关键点\mathcal{C}_S 决定\\ &且添加的噪声点只要不超过\mathcal{N}_S,对函数值不会产生影响。\\ &(b)式说明关键点的个数 |\mathcal{C}_S|存在上界,\\ &不大于K，即最大池化时特征的维数。 \end{align} \]
\[ 称 \mathcal{C}_S 为\; critical\; point\; set,K\;为\;bottleneck\; dimension \]
上述证明说明了此网络对于输入中一些微小的扰动与离群点具有很好的鲁棒性，并不会很大程度上影响结果。
下面给出了一些点云输入的 $_S $ 和 \(\mathcal{C}_N\) 集合可视化例子。可以看出经过这个网络提取出的 \(\mathcal{C}_S\) 集合，大体上描绘了这个物体的大致轮廓。
下图是 maxpooling 的维度 K 对准确率的影响。横坐标是 K 设置的数值，纵坐标是分类的准确率。每条线是每个输入中点的数量。可以看到随着 K 的增加，准确率有所上升，但是当 K 到达 1000 左右时基本上就不再变了，所以本文中 K 的取值就是选择 1024 ，以达到效率与精确度的最好权衡。
4.3 设计分析
在之前，提到过有三种方法解决无序性问题：排序、RNN、对称函数，现在给出这三种设计方法的效果对比：
可以看到对称函数操作的准确性最高，而在所考虑的三种对称函数中，maxpooling 的准确性又是其中最高的。
此外，我们提到过 T-Net 对齐网络的作用，在这里给出它的实际效果，可以看出它可以在一定程度上提高分类的准确率。
