PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation
Qi C R, Su H, Mo K, et al. Pointnet: Deep learning on point sets for 3d classification and segmentation[C]//Proceedings of the IEEE conference on computer vision and pattern recognition. 2017: 652-660.
点云是重要的几何数据结构。由于点云的不规则形式，大部分人都将其转化为规则的3D体素网格，或者图像集合。这篇文章定义了一个全新的神经网络类型，其可以直接使用点云格式，并且很好的保持了点云输入中的置换不变性，即PointNet。
PointNet为点云的各种应用如目标识别、部件分割、语义分割等，提供了统一的架构。
PointNet虽然简单，但是十分高效。实验上，它和最先进的模型效果旗鼓相当，甚至更好。理论上，文章分析了网络在学习什么，并且分析了为什么网络对输入的置换和缺失具有很好的鲁棒性。
Introduction
传统的卷积结构为实现权值共享和其他核优化方法，需要高度规则的输入数据格式，因此经常会把点云和网格转化为规则的去做。但是这样会造成数据不必要的冗余，并且引入了人为量化误差而掩盖了数据本身的不变性。
点云十分简单，并且避免了网格的复杂性，因此网络容易从中学习。但是点云仅仅是点集，因此需要在网络计算中进行一些对称化，来保证其排列不变性。更进一步，还应该考虑到刚体运动的不变性。
single symmetric function: max pooling. 网络可以学习到一系列用于筛选出兴趣点的优化方法，并且将其筛选条件进行编码。最后的全连接层收集了学习到的最优特征，整合进整个形状的全局描述子。
空间变换网络：输入数据容易进行刚体变换或仿射变换：因为每一个点的变换是独立的。因此可以在PointNet处理数据之前添加一个数据依赖的空间变换网络，来对数据进行规范化处理，有利于改善结果。
点云数据特征：
- 无序性：点云数据是一个无序的集合，因此网络如果要处理N个3D点的点云集合，需要对N!种不同的排列组合的输入保持不变性。
- 点间联系：点云中的点并不是孤立存在的，一群邻近点可以形成一个有语义的子集。因此，网络必须要能够捕捉到这种邻近点群形成的局部结构特征，以及局部结构特征之间的联系。
- 变换不变性：例如旋转和平移不应该影响点云的分类和分割。
亮点
三个关键点：
- max pooling 层作为对称函数来聚合所有点云信息。
- 一个局部和全局信息的组合结构。
- 两个节点对齐T-net网络。用于对齐输入点和点特征。
针对无序输入的对称函数
两个现有策略：
- 将输入进行规范化排序
虽然排序听起来简单，但实际上无法找到一个在有扰动的情况下，依然稳定的排序顺序。因为这实际上是在把高维数据降维至一维直线，同时还要保证空间上的相似性（spatial proximity），而这是一件无法实现的事。因此排序依然无法解决无序性问题，如图5所示，对排序后的点集使用MLP进行训练效果依然很差，虽然比起不排序的好一点点。
- 将输入看作类似RNN那样的sequence，另外还通过各种排列组合来增强训练数据。
考虑到点集可以看作是一种序列信号，因此引入了RNN的使用。并且期望通过随机排列序列来对RNN进行训练，这样RNN可以对输入顺序保有一定的不变性。然而《OrderMatters》[2]告诉我们RNN的输入顺序会影响网络的学习效果。尽管RNN对小批量序列有一定的顺序鲁棒性，但这很难在点云成千上万的数据批量上成立。从实验上，RNN为基础的模型依然表现的不够好。
PointNet策略： 使用一个简单的对称函数来聚合每一个点的信息。
对称函数：函数接收一系列的向量作为输入，输出一个新的向量。并且该输出不受输入向量间顺序的影响。例如+、*都是对称函数。
本质上是对点集中变换过的每个元素使用一个对称函数，来近似等于一个通用函数(general function):
\[ f\left(\left\{x_{1}, \ldots, x_{n}\right\}\right) \approx g\left(h\left(x_{1}\right), \ldots, h\left(x_{n}\right)\right) \]
\(f: 2^{\mathbb{R}^{N}} \rightarrow \mathbb{R}, h: \mathbb{R}^{N} \rightarrow \mathbb{R}^{K}\) 且 \(g:\) \(\underbrace{\mathbb{R}^{K} \times \cdots \times \mathbb{R}^{K}}_{n} \rightarrow \mathbb{R}\) 为对称函数。
主观上看，这种模型十分简单：h看作MLP，g看作一个一元函数和max pooling的结合体，实验证明这种模型十分有效。通过一系列的h，网络可以学习得到多种多样的f，来描述点云特性。
局部信息和全局信息整合
通过对无序输入的处理，可以得到一个\(f\)的向量\([f_1,...,f_k]\)，即算是一种全局特征描述子。为了进行点云分割，不仅需要全局信息，还需要和局部信息进行结合。
PointNet将先得到的全局特征重新与每个点的特征连接起来，然后计算出新的每个点的特征，即产生局部特征和全局特征的整合。
通过这种整合，PointNet能够给出有关于局部几何信息和全局语义信息的点的数量。例如，PointNet可以精准预测每个点的法线（即证明网络可以整合点的局部信息）。
节点对齐网络
为了让点云经过几何变换后依然有相同的语义标签，一个自然的做法是在特征抽取前将点云对齐到一个规范化空间。PointNet中通过一个小型网络T-net来预测一个仿射变换矩阵，并且直接将这个仿射变换应用在输入点云的坐标数据上，来实现对齐。
在特征空间上也可以这样做，通过一个网络来预测特征的变换矩阵，来实现对不同输入点云的特征的对齐。不过由于特征空间的高纬度，这样的操作极大增加了网络更新的困难。因此PointNet在损失函数中添加了一个正则项，来迫使特征变换矩阵更像一个正交矩阵（正交变换不会损失数据信息）：
\[ L_{r e g}=\left\|I-A A^{T}\right\|_{F}^{2} \]
\(A\)是特征变换矩阵。实验证明，这个正则化可以使网络变得更加稳定，且整体效果更好。
网络详细结构
- 主体每一层都使用了ReLU和Batchnorm，最后一个输出为256的全连接层之后使用了dropout=0.7。
- 一维卷积层（权值共享MLP）： 使用多个大小为1，步长为1的卷积核，对每一个点进行卷积，不涉及到其他点。
- 第一个T-Net：三层共享权值的MLP（64，128，1024）+ max pooling+ 两层全连接（512，256 ），最终输出3X3矩阵。除了最后一层都使用了ReLU和batch normalization。
- 第二个T-Net：结构相同，最后输出64X64矩阵。
- softmax分类损失携带一个一个权重0.001的正则损失，以便于让矩阵接近正交。
理论支撑
证明过程有时间再看，目前先看对网络的理论性支撑。
集合函数万能近似定理
证明了PointNet理论上拟合函数的正确性。
对于 Hausdorff 距离 \(d_{H}(\cdot, \cdot) .\) 假设\(f: \mathcal{X} \rightarrow \mathbb{R}\) 是一个Hausdorff度量的连续集合函数。\(\quad \forall \epsilon>\) \(0, \exists\) 一个连续函数\(h\)和一个对称函数 \(g\left(x_{1}, \ldots, x_{n}\right)=\gamma \circ M A X\), 对于任意 \(S \in \mathcal{X}\)有：
\[ \left|f(S)-\gamma\left(\underset{x_{i} \in S}{\operatorname{MAX}}\left\{h\left(x_{i}\right)\right\}\right)\right|<\epsilon \]
其中 \(x_{1}, \ldots, x_{n}\) 是 \(S\)的无序子集元素 , \(\gamma\) 是连续函数， \(M A X\) 是 vector max operator：输入\(n\)个向量并且输出一个每个元素位置都是最大值的向量.
维度瓶颈和稳定性
证明了PointNet受max pooling层维度影响很大，且其鲁棒性也与max pooling层有关。表现结果是PointNet会学习到一个形状的关键点轮廓来表示这个形状。
定义\(\bold{u}={\operatorname{MAX}}\left\{h\left(x_{i}\right)\right\}\)为最后一层是输出K维的max pooling层的网络。假设有如上定义的\(\mathrm{u}: \mathcal{X} \rightarrow \mathbb{R}^{K}\) 且 \(f=\gamma \circ\) u。那么有：
输入数据是关键点集的超集，则运算不会产生损失：\(\forall S, \exists \mathcal{C}_{S}, \mathcal{N}_{S} \subseteq \mathcal{X}, f(T)=f(S) if \mathcal{C}_{S} \subseteq T \subseteq \mathcal{N}_{S}\)
关键点集元素数不超过K：\(\left|\mathcal{C}_{S}\right| \leq K\)
优缺点
PointNet具有很强的鲁棒性，通过其对关键点集的提取，可以在有较多的点云损失的情况下依然保持分类能力。
PointNet只有全局特征和每个点的特征，丢失了局部点间特征。如网络结构所示，卷积层不涉及到任何点间联系。后续PointNet++[3]有关注点间联系的问题。
参考文献
[2] O. Vinyals, S. Bengio, and M. Kudlur. Order matters: Sequence to sequence for sets. arXiv preprint arXiv:1511.06391, 2015.
[3] Hao C R Q L Y, Guibas S L J. PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space[J]. arXiv preprint arXiv:1706.02413, 2017.