1.简介
传统的卷积框架严格要求规则的点云/网格数据格式，但是现在格式变得不规则，这就使得很多学者将这些数据变换成常规的三维体素网格或图像的集合，但是这样做会扩充数据量同时会引入量化伪影，掩盖住数据的自然不变性（增加了数据自身不具备的某些性能）。
点云数据是一种简单并且同一的结构，避免了网格的组合不规则性和复杂性，更容易学习。但是点云归根结底还是一些点的集合，如果要保持点的排列不变，要进行一些对称，刚性运动还要考虑不变性。
本设计的PointNet网络直接输入点云数据集输出每一个类别的标签，或者每类别中的部件分割的标签。基本框架使用的是三维的坐标数据或者添加额外的法向量信息。
本设计的突出亮点是使用了对称函数
最大值池化
，网络有效的学习一组优化函数/标准，来选择点云数据的感兴趣区域（特征值），然后使用softmax函数计算得分进行编码。网络最后的全连接层将学习到的最优值变为整个形状的特征值进行分类，或者预测每点的标签值进行分割。
输入的数据格式易于修改（刚体和仿射变换），因为每个点云集是独立的。于是作者在输入PointNet前
加入了与数据相关的空间变形网络将数据规范化
。
本设计可以接近任何集合函数，在插入异常值和缺失数据时有较好的鲁棒性，在多个数据集下测试结果又快又好，有以下特点：
1.设计了一种三维的无序点集训练的深度网络；
2.进行分类、部件分割和语义分割；
3.对鲁棒性和高效性进行理论和实例分析；
4.对三维神经网络的计算结果进行分析解释；
2.相关工作
a.点云特征
现有的点云特征是针对特定的任务手工标注的，点特征是编码某些点的统计特征，并设计为某些变换不变，这些变换分为内部变换和外部变换。也可以分为局部特征和全局特征。对于一个特定的任务找到最优的特征组合并不简单。
b.三维数据的深度学习
三维数据由于数据的稀疏性和三维卷积计算的成本，限制了他的分辨率。FPNN和Vote3D为了缓解数据稀疏性但还是避免不了稀疏数据；Multiview CNNs将三维点云数据映射为二维图像进行二维卷积运算，在分类和检索任务上得到了很好的性能，但是对于场景理解和三维任务实现不了；Spectral CNNs在网格上使用光谱CNN，这种方法不适用于多形状网格上，如器官，非等距形状等；Feature-based DNNs首次将三维数据转换为一个向量，通过提取传统形状特征，利用全连接网络进行形状分类，作者认为受限于特征提取表达能力的约束。
c.无序数据集的深度学习
现在绝大多数深度学习网络的输入都是有序的，如语音和语言中的因果关系、视频和三维图像中的图像和体积。点云数据集是无序的，有学者 读-处理-写网络和注意力机制解决无序问题，表明他们的网络有能力对数字进行排序，适用于NLP和其他一些普通的数据集并不适用于图形集。
3.网络简介
本设计提出的网络框架可以直接输入无序的点集，这些点包括
{
x
,
y
,
z
}
\{x,y,z\}
{
x
,
y
,
z
}
坐标和其他的信息，如颜色信息和矢量信息。
对于分类任务，输入的点云数据要么直接从形状中采样（直接输入点云数据采样），要么从场景点云中预先分割。对于
k
k
k
个类别输出
k
k
k
个得分情况。对于分割来说，输入可以是用于部分区域分割的单个对象（选取点云数据集中的某个个体的数据入队飞机分割各零部件），或者是用于对象区域分割的一部分数据（某一场景中各物体分割）。最终输出一个
n
∗
m
n*m
n
∗
m
的得分值，
n
n
n
表示输入点的个数，
m
m
m
表示类别数。
4.点集的深度学习
4.1点集
R
n
\mathbb{R}^n
R
n
的性质（其中n表示点的个数）
输入主要是欧几里得空间的子集，有以下几点性质：
a.无序：点云数据是无序排列的，也就是说输入N个三维点云数据，网络需要保证
N
!
N!
N
!
的输入排列顺序结果一致（因为无序）；
b.点之间的相互作用：点集来自同一测度空间，意味着点不是孤立的，相邻的点可以构成有意义的子集，这就要求网络可以在相邻点上捕获局部结构，并且捕获局部结构间的组合相互作用；
c.变换的不变性：学习到的特征对于某些变换应该是不变的，如平移和旋转变换不应改变结果；
4.2PointNet网络框架
分类的网络框架
对输入进行变换和特征变换，然后进行最大池化聚合特征，输出是k个类别的得分。‘mlp’代表多层感知机（multi-layer perceptron）,括号内的值表示网络层的大小（多层），对所有层进行Relu激活和批归一化操作，并且使用Dropout增强网络的鲁棒性。
分割的网络框架
在分类框架的基础上，将全局特征值与前面网络得到的局部特征进行拼接，最后输出一个
n
∗
m
n*m
n
∗
m
的得分值，
n
n
n
表示输入点的个数，
m
m
m
表示点的类别数。
三个主要的框架是：1）最大池化层用作对称函数综合所有点的信息；2）局部和全局特征拼接结构；3）两个联合对齐网络对齐输入点和点的特征；
1）.使用对称函数处理无序输入：
为了使模型对输入的排列顺序（不敏感）采用三种策略：a.将输入排序维规范顺序；b.将输入视为一个序列来训练一个RNN，并通过变换排列顺序增强训练数据；c.使用对称函数综合每点的信息；涉及的最大池化函数输入n个矢量，输出一个对输入张量顺序不变（不敏感）的新张量。例如+和*是对称的二进制函数（我理解 对称意思是对顺序无要求）。
（排除a方法）
由于高维空间存在点扰动所以不存在稳定的排序，将高维与一维双向映射就是在降维时保持空间的接近性，难以实现。故排序并不能完全解决顺序问题，并且由于排序问题一直存在网络中，网络很难学习有输入到输出的一致映射。直接对排序的数据集应用MLP效果会很差。
（排除b方法）
使用RNN的想法是认为点集是有序的信号，并且使用随机排列的序列训练RNN，这样RNN就不要求输入的顺序了。但是有研究表明顺序也十分重要不能完全省略，RNN对短的序列有较好的鲁棒性，很难处理成千上万个数据（点云数据的常规大小）。
c方法使用最大池化对称函数
定义函数
f
(
{
x
1
,
.
.
.
,
x
n
}
)
≈
g
(
h
(
x
1
)
,
.
.
.
,
h
(
x
n
)
)
(1)
f(\{x_1,…,x_n\})\approx g(h(x_1),…,h(x_n)) \tag1
f
(
{
x
1
,
.
.
.
,
x
n
}
)
≈
g
(
h
(
x
1
)
,
.
.
.
,
h
(
x
n
)
)
(
1
)
其中，
f
f
f
是
2
R
N
2^{\mathbb{R}^N}
2
R
N
到
R
\mathbb{R}
R
的映射，
h
h
h
是
R
N
\mathbb{R}^N
R
N
到
R
K
\mathbb{R}^K
R
K
的映射，
g
g
g
是
n
n
n
个
R
K
\mathbb{R}^K
R
K
到
R
\mathbb{R}
R
的映射。
h
h
h
函数通过多层感知网络去逼近，
g
g
g
由单变量函数和最大池化函数组成。
这种实验结果最好，通过h集合辅助获取f集合的不同属性。
2）.局部和全局信息整合：
上面的网络输出一个
[
f
1
,
.
.
.
f
K
]
[f_1,…f_K]
[
f
1
,
.
.
.
f
K
]
的向量，是输入数据集的全局特征。然后训练一个SVM或多层向量感知分类器在全局特征的基础上进行分类，但是分割需要结合全局和局部的特征进行。如上图所示，提取出全局特征后将之前获得的局部特征与之拼接，然后获取新的点的特征，这些特征包括全局的特征和局部的特征。
这样该网络可以依赖全局语义和局部几何学预测每个点的类别。如可以准确预测每个点的法线，验证网络可以结合点的邻域信息进行验证。
================== 下面是重大特点=======================================
3）.联合对齐网络
：如果点云经历了一定的几何变换，如刚性变换，那么要求点云的语义必须是不变的（刚性变换不改变物体的类别）。因此希望该网络学习得到的结果对于刚性变换也是不变的结果（有较强的鲁棒性）。一个自然的解决方法是在特征提取之前将所有数据集对齐到一个规范空间内，有学者使用空间变换器，设计了一个专门的层，使用采样和插值法对齐二维图像；由于使用点云数据集，所以不需要设计一个单独的层并且并不需要像图像那样引入别名。使用了一个mini网络构造了仿射变换矩阵（
3
∗
3
3*3
3
∗
3
的T-NET）直接作用于输入图像上。该网络类似大网络，由点特征提取、最大池化和全连接层等模块组成。该模块可以延伸到特征提取网络（64*64的T-NET），可以在点特征上插入另一个对齐网络，并预测一个特征变换矩阵来对齐不同输入点云的特征。由于输入点云是三维或六维的所以第一个形变矩阵是较低维的，而特征值类别较多，所以是高维矩阵。因此增加了优化的难度，于是在softmax训练中引入一个正则化项，约束变换矩阵接近一个正交矩阵
L
r
e
g
=
∣
∣
I
−
A
A
T
∣
∣
F
2
(2)
L_{reg} = ||I – AA^T||^2_F \tag2
L
r
e
g
=
∣
∣
I
−
A
A
T
∣
∣
F
2
(
2
)
A
A
A
是特征对齐的矩阵，正交变换不会损失输入信息，加入正则化项后，优化变得更为顶，网络性能更好了。
4.3理论分析
普适性逼近能力
神经网络对连续集合函数有普适的逼近能力，连续集合函数，一个点集的小扰动不应该极大的影响函数值。
设
X
=
{
S
:
S
⊆
[
0
,
1
]
m
a
n
d
∣
S
∣
=
n
}
\mathcal{X}=\{S:S\subseteq [0,1]^m and |S| = n \}
X
=
{
S
:
S
⊆
[
0
,
1
]
m
a
n
d
∣
S
∣
=
n
}
，函数f是
X
\mathcal{X}
X
到
R
\mathbb{R}
R
的映射函数，在
X
\mathcal{X}
X
上，相对于豪斯多夫距离是一个连续的集合函数，
∀
ϵ
>
0
,
∃
δ
>
0
,
\forall\epsilon >0,\exist\delta >0,
∀
ϵ
>
0
,
∃
δ
>
0
,
对任意的
S
,
S
′
∈
X
,
S,S’\in\mathcal{X},
S
,
S
′
∈
X
,
如果豪斯多夫距离
d
H
(
S
,
S
′
)
<
δ
,
且
∣
f
(
S
)
−
f
(
S
′
)
∣
<
ϵ
d_H(S,S’) < \delta,且|f(S) – f(S’)| < \epsilon
d
H
(
S
,
S
′
)
<
δ
,
且
∣
f
(
S
)
−
f
(
S
′
)
∣
<
ϵ
（求极限的定义，证明了是连续函数
X
\mathcal{X}
X
是归一化后的坐标值）。设计的网络可以近视任意f函数，只要有足够的神经元，即（1）中的K值足够大。
定理一、假设f：
X
\mathcal{X}
X
到
R
\mathbb{R}
R
的映射相对于豪斯多夫距离是连续的集合函数
∀
ϵ
>
0
\forall\epsilon >0
∀
ϵ
>
0
，存在一个连续函数h和一个对称函数。例如，
g
(
x
1
,
.
.
.
,
x
n
)
=
γ
∘
M
A
X
g(x_1,…,x_n)=\gamma\circ MAX
g
(
x
1
,
.
.
.
,
x
n
)
=
γ
∘
M
A
X
,因此对任意
S
∈
X
S\in \mathcal{X}
S
∈
X
,都有
∣
f
(
S
)
−
γ
(
M
A
X
x
i
∈
S
{
h
(
x
i
)
}
)
∣
<
ϵ
|f(S) – \gamma(\mathop{MAX}_{
{x_i}\in S}\{h(x_i)\})| < \epsilon
∣
f
(
S
)
−
γ
(
M
A
X
x
i
∈
S
{
h
(
x
i
)
}
)
∣
<
ϵ
,其中
x
1
,
.
.
.
x
n
x_1,…x_n
x
1
,
.
.
.
x
n
是S中完整元素的任意排列，
γ
\gamma
γ
是一个连续函数，MAX是向量最大算子（以n个向量为输入，返回一个新的元素最大的向量（与输入向量类似的））
{x_i}\in S}\{h(x_i)\})| < \epsilon
维度和稳定性的讨论
：理论和实践双重验证最大池化的维度严重影响着网络的性能。定义
u
=
M
A
X
x
i
∈
S
{
h
(
x
i
)
}
\mathbf{u}=MAX_{x_i \in S}\{h(x_i)\}
u
=
M
A
X
x
i
∈
S
{
h
(
x
i
)
}
为f函数的子网络，将点集
[
0
,
1
]
m
[0,1]^m
[
0
,
1
]
m
映射到K维向量，接下来的定理验证了少量数据缺失和噪声不会影响网络性能。
定理二、假设
u
\mathbf{u}
u
是
X
\mathcal{X}
X
到
R
K
\mathbb{R}^K
R
K
的映射，
u
=
M
A
X
x
i
∈
S
{
h
(
x
i
)
}
\mathbf{u}=MAX_{x_i \in S}\{h(x_i)\}
u
=
M
A
X
x
i
∈
S
{
h
(
x
i
)
}
，则
f
(
{
x
1
,
.
.
.
,
x
n
}
)
≈
g
(
h
(
x
1
)
,
.
.
.
,
h
(
x
n
)
)
=
γ
∘
u
f(\{x_1,…,x_n\})\approx g(h(x_1),…,h(x_n))=\gamma\circ\mathbf{u}
f
(
{
x
1
,
.
.
.
,
x
n
}
)
≈
g
(
h
(
x
1
)
,
.
.
.
,
h
(
x
n
)
)
=
γ
∘
u
且
∀
S
,
∃
C
S
,
N
S
∈
X
,
f
(
T
)
=
f
(
S
)
…
…
当
C
S
∈
T
∈
N
S
\forall S,\exist \mathcal{C_S},\mathcal{N_S}\in \mathcal{X},f(T)=f(S)……当\mathcal{C_S}\in T\in \mathcal{N_S}
∀
S
,
∃
C
S
,
N
S
∈
X
,
f
(
T
)
=
f
(
S
)
…
…
当
C
S
∈
T
∈
N
S
∣
C
S
∣
≤
K
|\mathcal{C_S}|\le K
∣
C
S
∣
≤
K
其中，
C
S
\mathcal{C_S}
C
S
为关键点，f(S)为全局特征，
N
S
\mathcal{N_S}
N
S
式预测的最大可能形状值，K是最大池化的输出维数。
若
C
S
\mathcal{C_S}
C
S
中所有点都保留，则f(S)直到输入损坏和引入噪声都保持不变；K决定了
C
S
\mathcal{C_S}
C
S
只包含有限个点。换句话说就是，f(S)的元素个数是一个小于等于K个元素的有限子集
C
S
∈
S
\mathcal{C_S}\in S
C
S
∈
S
决定的。称
C
S
\mathcal{C_S}
C
S
为S的关键点集，K是f的瓶颈维度。结合h函数的连续性，解释了模型对点缺失和噪声干扰的鲁棒性。
总而言之，本设计的网络通过一些关键点学习一些形状，从而进行分类和分割。
5.实验
5.1实现多重三维识别任务
5.1.1三维目标检测
之前使用的方法是基于体积和多视图的。本设计直接对点云数据进行处理，使用ModelNet40数据集进行训练，获取全局特征后进行分类，该数据集油人工标注的40类物体，分为9843：2468的训测比。
均匀采集网格面上1024个点，然后将他们归一化到一个单位球内，并且通过沿z轴随即旋转和高斯噪声抖动点来增强数据集。
实验结果如图所示，PointNet得到的结果接近甚至超过较高水平，各类别平均准确率低于MVCNN（基于多视图）框架，猜测彩色图像可能对数据有补充作用。
5.1.2三维目标部件分割
部件分割是一项具有挑战的精密三维识别任务，给定一个点云数据，需要得到每一部件的标签（如椅子腿、杯子等）。使用ShapeNet数据集进行训练16881个点云集，16个类别，50个部件，每个类别包含2-5个部件不等，数据带有标准信息。把部件分割问题转换成每个点的分类问题，使用点的平均交并比进行判断，对于每个形状S的部件类别C，
计算形状的平均交并比：
种类C中的每个部件，计算真实值与预测值之间的交并比，如果真实值与预测值交集为空，则记交并比为1。计算所有类别的交并比后求平均值。
实验结果：
整体的分割结果比较理想，存在某些类别分类率低的情况。
左边是微软提出的体感遥感技术，分割效果缺失部分结构，右侧为本设计设计的分割方法，分割较合理，且分割部分整体完整，没有明显的缺失。
5.1.3场景中语义分割
设计的网络很容易可以拓展到语义场景分割，只需要将点标签变为语义对象标签。使用斯坦福大学三维语义解析数据集（Stanford 3D semantic parsing data set）包括271个房间的三维扫描数据，每个点都用13个类别的语义标签注释（桌子、椅子、地板和杂物等）。先按房间划分点，然后将房间分割成1m×1m的块。每个点都是九维的信息（XYZ、RGB和标准化位置信息（0-1）），训练时随机选取每个区块中4096个点，测试时使用所有的点，并使用K-拆运算（常见十拆：就是将数据集等分十份，依次选取一份作为测试集，其余为训练集，共进行十次）进行训练和测试。
并且与使用手工标注的点特征
基线法
（baseline：我理解这个意思为 ’方法‘就是处理策略，这里应该是网络结构一样，都是用MLP网络）进行了对比试验，基线法在上述的九维信息的基础上还添加了局部点密度、局部曲率和发法线信息。使用标准MLP作为分类器。
结果为：
可以看出，平均交并比优于基线法，正确率也高于基线法。
具体的分割效果：
可以明显看出基本可以正确划分每个部件。
作者又基于语义分割构建了一个基于连接组件（有重叠的结构，例如椅子在桌子下）的三维目标检测系统，结果如下：
前一种方法是使用华东形状方法(使用CRF后处理：对FCN处理后的图像进行优化)，再体素网格中使用局部集合特征和全局上下文特征训练支持向量机。结果作者提出的方法明显优于前一个方法。
5.2结构设计分析
5.2.1与其他顺序不变方法的比较
如上文4.2所描述，有三种方法适用于无序输入，使用ModelNet40数据集进行分类。将无序和有序点变为n×3的数组，RNN模型将输入点看成序列，并使用一个基于对称函数的模型的多层感知网络进行比较。使用的对称函数包括：最大池化、平均池化和一个基于注意力的加权和函数。加权函数对提取每个特征点的标量分数，然后使用softmax函数进行归一化。然后根据归一化分数和点特征计算加权和。
由图可知，最大池化获得了较高的准确率。
5.2.2输入变换和特征变换的有效性
使用上述方法对齐（将输入点云数据放置在同一坐标系中），正则化像是高维变换必须的。
对比实验结果可知，这些对齐变换对准确率的影响还是很大的。
5.2.3鲁棒性测试
使用最大池化网络进行测试，实验结果如下图，左图进行了最远采样点和随机采样点的数据缺失对比验证，二者接近在缺失80%的情况下依旧又不错的效果；中间是以点密度为变量进行验证（横坐标为异常比：异常值均匀地分布在单位球内），加入点密度反而降低了准确率；右边是验证高斯噪声标准差对实验的影响，随着标准差的增加准确率下降。
5.3PointNet可视化
将关键点
C
S
\mathcal{C_S}
C
S
和样本形状S的上界形状（upper-bound shapes：是由前向传播的边界长为2的立方体内所有的点和
点函数值
(
h
1
(
p
)
,
.
.
.
,
h
K
(
p
)
)
(h_1(p),…,h_K(p))
(
h
1
(
p
)
,
.
.
.
,
h
K
(
p
)
)
不大于全局形状描述符的点p
共同构成）
N
S
\mathcal{N_S}
N
S
进行可视化，两个类别间的点将会得到全局形状特征f(S)。最大池化获得的关键点完全构成了类别的骨架，上界形状表明了与输入点云S具有相同全局特征的最大可能点云f(S)。关键点和上界形状也反映了PointNet的鲁棒性，意味着损失一些非关键点也不会改变全局特征形状。可视化结果如下：(颜色表示深度信息)
5.4时空复杂性分析
将PointNet与以前的网络进行对比结果如下（FLOPs：每秒浮点运算数量）：
由上述的结果可知，对比的实验准确率略优于PointNet，但是在网络参数和运算量上大大减少，PointNet分类时可以处理100万点每秒；场景分割时可以处理每秒约两个房间。多视图方法（MVCNN）复杂度随图像分辨率提高升高，基于体积卷积的方法随体积增加呈指数增长。（第一行数据是未经过输入和特征变换的PointNet）