基本上翻译自[1]:Pointnet: Deep learning on point sets for 3d classification and segmentation，加了一点个人理解。

Introduction

典型的卷积结构需要规则的数据结构，比如图像或者voxel模型。对于点云、mesh这样的非规则数据结构，往往就会将它们转化成voxel模型或多视角下的二维图片，再用卷积进行处理。二维图像损失了部分几何信息，而体素化则引入了人工的误差，因此都不是理想的处理方式。

作者希望发现一种网络结构，可以直接处理点云。点云模型中，点的顺序和结果无关，因此这一模型必须是和顺序无关的（invariant to permutation）。另外，模型也需要对刚性变化保持不变性（invariant to rigid motions）。

作者提出了PointNet，它以点云作为输入，输出模型的类别（对于模型分类问题）或每个点所属的类别（对于模型分割问题）。PointNet的结构非常简单，它先对每个点进行独立相同（identical & independent）处理，再使用一个简单的对称函数（symmetric function，它的性质是，改变输入参数的顺序，不影响最后的结果）得到特征向量。在论文中，这一对称函数非常简单，就是逐元素取最大值（max pooling）。

论文的主要贡献为：

1. 设计了一个处理点云的模型；
2. 验证了模型可以用于模型分类、分割和语义信息提取；
3. 对方法的有效性和稳定性提出了经验和理论的分析
4. 对模型的有效性提出了符合直观的解释

Related Work

• Point Cloud Features
• Deep Learning on 3D Data
  • 体素化CNN（Volumetric CNN）
  • 多视角CNN（Multiview CNN）
  • 谱方法CNN（Spectral CNN）
  • 基于特征的深度网络（Feature-based DNN）：传统方法提取几何特征，再使用全连接。

Problem Statement

• 输入：$N$N个点，每个点3个坐标。
• 输出：对于$k$k模型分类，输出$k$k维向量，分别表示$k$k个类别的概率；对于模型分割，对每个点输出$m$m维向量，表示该点属于$m$m个类别的概率。

Deep Learning on Point Sets

点云的性质

• 无序性。对于$N!$N!种点不同顺序的组合，输出结果都应是一样的。
• 点的互动。点之间满足空间上的度量，邻近的点构成了局部特征。
• 变换不变性。平移和旋转不应改变物体的分类或分割结果。

PointNet的结构

对无序输入的对称函数

处理无序输入往往有三种方式：

• 先排序再输入。它的缺点有：对于高维数据，不存在唯一的排序。
• RNN。在“OrderMatters”论文中，作者论证了RNN中顺序是无法被完全丢弃的。
• 对称函数。PointNet即采用了这种方法。

本文构造的对称函数如下：
$f\left(\left\{ x_1, \cdots, x_N \right\}\right) \approx g\left( h(x_1), \cdots, h(x_N) \right)$f({x1​,⋯,xN​})≈g(h(x1​),⋯,h(xN​))

其中，$f$f是$2^{\mathbb{R}^N} \rightarrow \mathbb{R}$2RN→R的函数，其中$2^{\mathbb{R}^N}$2RN表示$N$N维向量组成的集合作为输入。$h$h是$\mathbb{R}^N \rightarrow \mathbb{R}^K$RN→RK的函数，将原来的$N$N（仅考虑坐标则为3，若另有$c$c维的点上的特征，则为$3+c$3+c）变成$K$K维向量。$g$g是一个$\mathbb{R}^K * \cdots * \mathbb{R}^K \rightarrow \mathbb{R}$RK∗⋯∗RK→R的对称函数。

局部特征和全局特征的整合

对于模型分类问题，对上述的$f$f直接用SVM或者多层感知机（MLP）做分类就好了。

对于模型分割问题，将上述的全局特征向量，分别concatenate到每个点经过$h$h运算后的向量上。对concatenate后的向量，再使用SVM或MLP做分类就好了。使用这样的方法，论文中给出了预测每个点法向量的结果，这说明每个点能通过全局特征感知到自己的邻域。

联合对齐网络

点云的语义信息应该不随点云的刚性几何变换（旋转或平移）而变化。一种自然的想法是在特征提取之前先做一次对齐。我们可以设计一个小网络（mini-network）来学习一个$3*3$3∗3的变换矩阵，并对$N*3$N∗3的点云做变换。

这样的想法可以进一步用于特征空间的对齐，因此在上方的流程图中，还有一个$64*64$64∗64的变换矩阵，对特征空间做对齐。特征空间的变换矩阵维度（$64*64$64∗64）要远大于几何空间（$3*3$3∗3），因此避免变换矩阵太难优化，在损失函数部分加上一个正则项，即
$L_{reg} = || I - AA^T ||_{F}^{2}$Lreg​=∣∣I−AAT∣∣F2​

理论分析

全局估计能力

首先证明PointNet这样的设计可以逼近连续集合函数（continuous set function）。之所以要求集合函数的连续性，这样我们给输入点加上一个小误差时，不会给分类或分割结果带来明显的变化。

令$\mathcal{X} = \{ S: S \subseteq [0,1]^m and |S|=n \}$X={S:S⊆[0,1]mand∣S∣=n}，即$\mathcal{X}$X是一个有$n$n个元素的集合，其中每个元素都是一个$m$m维，在$[0,1]$[0,1]上的向量。$f : \mathcal{X} \rightarrow \mathbb{R}$f:X→R，$f$f是一个集合函数，它的连续性定义在集合的Hausdorff距离上，即
$\forall \varepsilon &gt; 0, \exists \delta, \text{ for any } S, S&#x27; \in \mathcal{X}, \text{ if } d_H(S,S&#x27;)&lt;\delta, \text{ then } |f(S)-f(S&#x27;)|&lt;\varepsilon$∀ε>0,∃δ, for any S,S′∈X, if dH​(S,S′)<δ, then ∣f(S)−f(S′)∣<ε
即如果集合上的差异（Hausdorff距离）足够小，那么通过$f$f运算后的结果也差异足够小。

定理1

假设$f: \mathcal{X} \rightarrow \mathbb{R}$f:X→R是定义在Hausdorff距离$d_H(\cdot, \cdot)$dH​(⋅,⋅)上的一个连续集合函数，$\forall \varepsilon &gt; 0$∀ε>0，则存在一个连续函数$h$h和一个对称函数$g(x_1, \cdots, x_n) = \gamma \circ \text{MAX}$g(x1​,⋯,xn​)=γ∘MAX，使得对于任意的$S \in \mathcal{X}$S∈X，
$\left| f(S) - \gamma \left(\text{MAX}_{x_i \in S} \{h(x_i)\}\right) \right| &lt; \varepsilon$∣f(S)−γ(MAXxi​∈S​{h(xi​)})∣<ε
其中，$\gamma$γ是一个连续函数，$\text{MAX}$MAX是一个逐元素取最大值的操作。

证明

由于$f$f的连续性，取一个$\delta_{\varepsilon}$δε​，有对任意的$S,S&#x27; \in \mathcal{X}$S,S′∈X且$d_H(S,S&#x27;)&lt;\varepsilon$dH​(S,S′)<ε，都有$|f(S)-f(S&#x27;)|&lt;\varepsilon$∣f(S)−f(S′)∣<ε。

令$K=\lceil 1/\delta_\varepsilon \rceil$K=⌈1/δε​⌉，我们将$[0,1]$[0,1]区间分成$K$K等分（每等分大小都小于$\delta_\varepsilon$δε​），并将$S$S中的每一个点都映射到自己所处的那一份的左边界，即进行一个如下的变换：
$\sigma(x) = \frac{\lfloor Kx \rfloor}{K}$σ(x)=K⌊Kx⌋​

令经过变换后的集合为$\tilde{S}$S~，由于每一等分都小于$\delta_\varepsilon$δε​，显然有$|f(S)-f(\tilde{S})|&lt;\varepsilon$∣f(S)−f(S~)∣<ε。

令$h_k(x) = e^{-d(x,[\frac{k-1}{K}, \frac{k}{K}])}$hk​(x)=e−d(x,[Kk−1​,Kk​])，其中，$d(x,I)$d(x,I)表示点$x$x到区间$I$I的距离。令$h(x) = [h_1(x); \cdots; h_K(x)]$h(x)=[h1​(x);⋯;hK​(x)]，那么$h: \mathbb{R} \rightarrow \mathbb{R}^K$h:R→RK。

令$v_j(x_1, \cdots, x_n) = \text{ max } \{ h_j(x_1), \cdots, h_j(x_n)\}$vj​(x1​,⋯,xn​)= max {hj​(x1​),⋯,hj​(xn​)}，若第$j$j区间中有点，则$v_j$vj​就为1，否则小于1。令$v = [v_1; \cdots; v_K]$v=[v1​;⋯;vK​]，则$v: \mathbb{R} * \cdots * \mathbb{R} \rightarrow [0,1]^K$v:R∗⋯∗R→[0,1]K是一个对称函数，表示每个区间中是否有点。

令$\tau(v) = \left\{ \frac{k-1}{K}: v_k=1 \right\}$τ(v)={Kk−1​:vk​=1}，可以看到，$\tau$τ将向量转化为点集，即$\{0,1\}^K \rightarrow \mathcal{X}${0,1}K→X。

容易证明$\tau(v(x_1,\cdots,x_n)) \equiv \tilde{S}$τ(v(x1​,⋯,xn​))≡S~。令$\gamma(v) = f(\tau(v))$γ(v)=f(τ(v))，则$\gamma(v) = \gamma(\text{MAX}(h(x_1), \cdots, h(x_n)))$γ(v)=γ(MAX(h(x1​),⋯,h(xn​)))，证毕。

说明

上面的一些步骤，似乎将$x_i$xi​视为了标量，不过很容易看出，变成向量并不会影响结论。上述证明的直观理解是，在最差的情况下，我们将点云变成voxel，然后按voxel的方式进行处理。

维度瓶颈和稳定性

通过理论和实验，作者发现网络的表达力和最大化层的维度$K$K非常相关。令$u=\text{ MAX }_{x_i \in S} \{h(x_i)\}$u= MAX xi​∈S​{h(xi​)}，则有定理2成立。定理2告诉我们，只要关键点（critical points，对应$C_S$CS​）不变，增加一些小误差（noise，对应$N_S$NS​），不会改变最终结果。

定理2

令$u: \mathcal{X} \rightarrow \mathbb{R}^K$u:X→RK满足$u=\text{ MAX }_{x_i \in S} \{h(x_i)\}$u= MAX xi​∈S​{h(xi​)}，且$f = \gamma \circ u$f=γ∘u，则
$\begin{aligned} \text{(a) } &amp; \forall S, \exists C_S, N_S \subseteq \mathcal{X}, f(T) = f(S) \text{ if } C_S \subseteq T \subseteq N_S \\ \text{(b) } &amp; |C_S| \leq K \end{aligned}$(a) (b) ​∀S,∃CS​,NS​⊆X,f(T)=f(S) if CS​⊆T⊆NS​∣CS​∣≤K​

证明

显然，$\forall S \in \mathcal{X}$∀S∈X，$f(S)$f(S)都是由$u(S)$u(S)决定的，$u(S)$u(S)一共有$K$K维，每一维最多新增一个点到$C_S$CS​，所以(b)显然成立。在$C_S$CS​的基础上，增加其他点，都不改变$u(S)$u(S)，因此(a)也显然成立。证毕。

说明

我个人的理解是，$C_S \subseteq \mathcal{X}$CS​⊆X，但$\mathcal{X} \subseteq N_S$X⊆NS​，所以，只要在变换后，不超出$C_S$CS​边界的噪声点，都不会影响最终的结果。定理2说明了PointNet的稳定性。

一些impressive的结果

对部分可见的模型的分类和分割

对部分可见的模型的正确率

参考文献

[1] Qi, Charles R., et al. “Pointnet: Deep learning on point sets for 3d classification and segmentation.” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2017.