本文于2017年发表NIPS（Neural Information Processing Systems），文章链接：

PointNet : Deep Hierarchical Feature Learning on Point Sets in a Metric Space

从文章的题目可以看出这是对的PointNet改进如下：

1. PointNet基本思想是学习每个点的空间编码，然后将所有单独的点特征集成到整个点云特征中。根据其设计，PointNet捕获的局部特征是point-wise由测量引起的局部结构不能捕获。PointNet 先利用Sampling layer和Grouping layer构建局部邻域，再利用PointNet layer局部特征编码(提取)。也就是文章中提到的Hierarchical Point Set Feature Learning
2. PointNet采样密度为uniform的，而PointNet 可以处理non-uniform sampling。也就是文章中的Robust Feature Learning under Non-Uniform Sampling Density。

关于PointNet，可以参考：

PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation 详细说明论文和代码

PointNet该设计不捕获由测量空间引起的局部结构，限制了其识别细粒度模式和泛化复杂场景的能力。

Hierarchical Point Set Feature Learning：本文介绍了一个层次神经网络，其递归地应用于输入点集的嵌套分区PointNet。测量空间距离，PointNet 网络能够在不断增加的上下文尺度下学习局部特征。

Robust Feature Learning under Non-Uniform Sampling Density：点集通常以不同的密度采样，导致均匀密度训练PointNet网络性能大大降低，本文提出了多尺度自适应结合的新学习层。

（1）构建点云网络时应考虑的问题：点云成员的排列顺序不变（无序）；距离定义的局部邻域（局部特征）；点采样不均匀。

（2）PointNet 的general idea：首先，点云根据距离度量分为多个重叠的局部区域（local region）。接下来，类似CNN（Convolution Neural Network，卷积神经网络)从小邻域提取几何结构的局部特征；这些局部特征将被聚集到更大的单元中，并被处理以产生更高层次的特征，重复这一步骤，直到获得所有点集。

（3） 设计PointNet 两个主要问题：1）如何根据距离测量将点集划分为重叠的局部区域；2）如何通过局部特征学习器提取局部点集或局部特征。

(4)局部特征学习器:选择PointNet

(5)将点集划分为重叠区域:每个点用欧氏空间划分 neighborhood ball 定义球的参数只有 centroid location（质心）和 scale（半径）。centroids选择就是利用最远点采样算法（farthest point sampling（FPS）algorithm）；至于scale文章没有说明如何选择，但直接给出了附加材料中的网络结构scale的值。

（6）Significant contribution：PointNet 邻域信息的多尺度利用。

PointNet 网络结构如下图所示：

PointNet 其实是一个 Encoder-Decoder 结构，Encoder是下采样过程，通过 Hierarchical point set feature learning，即多个 set abstraction level，不断获得更大规模区域的特征。Decoder不同的应用程序根据分类和分同。

（1）PointNet整个点云采用单个最大池化操作；PoinNet 建立了一个点的层次聚类，并逐渐沿着分层提取越来越大的局部区域。

（2）PointNet 层次结构由一系列组成 set abstraction level 如结构图所示。

输入: 一堆点，即点集。

输出： 从输入点中选取的一部分点，即输入点集的子集。

目的： 从输入点中选取一部分点，选取的这部分点定义了 local regions 的 centroids。

方法： 给定输入点集 { x 1 , x 2 , ⋯   , x n } \{x_1,x_2,\cdots,x_n\} { x1​,x2​,⋯,xn​}，采用迭代最远点采样来选择一部分点 { x i 1 , x i 2 , ⋯   , x i m } \{x_{i_1},x_{i_2},\cdots,x_{i_m}\} { xi1​​,xi2​​,⋯,xim​​} ，使得 $x_{ij}$ 是距离 { x i 1 , x i 2 , ⋯   , x i j − 1 } \{x_{i_1},x_{i_2},\cdots,x_{i_{j-1}}\} { xi1​​,xi2​​,⋯,xij−1​​} 最远的点。最远点采样和随机采样相比，在相同数目centroid的情况，能够更好地覆盖整个点集。

• 最远点采样算法如下：
  记初始点集为 $A$ ，要选取的 $m$ 个点所构成的集合为 $B$ 。
  1，初始化 $B=\varnothing$ 。随机从 $A$ 中选取一个点作为初始点 $x_1$ ，并将其加入到 $B$ 中；
  2，对于 $A/B$ 中的点 $x$ ，计算其到 $B$ 中每个点的距离，并将最小值作为 $x$ 到 $B$ 的距离，即 $d(x,B)={\min }_{y\in B}d(x,y)$ ，然后选取 $A/B$ 中距离 $B$ 最远的点加入 $B$ 中，即 B = B ∪ { x ∣ max ⁡ x ∈ A / B min ⁡ y ∈ B d ( x , y ) } B=B\cup\{x|\max_{x\in A/B}\min_{y\in B}d(x,y)\} B=B∪{ x∣maxx∈A/B​miny∈B​d(x,y)} ;
  3，重复上述步骤，直到 $|B|=m$ 。

注：从上述算法描述来看：这一层没有需要学习的参数（权重）；输入的点集是带有特征的（虽然只用到了点的位置来计算距离，但是可以带有其它特征维度）并且没有对特征进行升维和降维。所以，这也是为什么在网络结构中把 Sampling layer 和 Grouping layer 合并到一起。

输入：大小为 $N\times (d+C)$ 的点集和大小为 $N^{{}^{\prime }}\times d$ 的 centroids。其中 $N^{{}^{\prime }}$ 是Sampling layer得到的centroid的数目。

输出：大小为 $N^{{}^{\prime }}\times K\times (d+C)$ 的 groups of point sets（ $N^{{}^{\prime }}$ 组点集，每组点集中含有 $K$ 个点）。

方法：在找 $K$ 个最近点（距离对应的centroid最近）时，采用的是 Ball query，而非 $kNN$ （ $K$ nearest neighbor）。与 $kNN$ 相比，Ball query 的局部邻域保证了一个固定大小的区域，因此使得局部区域特征在空间上更具有泛化性。也就是 Ball query 更加适合于应用在局部/细节识别的应用上。

Ball query算法：在球内按照距离找 $K$ 个点，如果不满 $K$ 个，则取第一个点补充。

scale的大小：文章中没有给出scale选择的标准，但是附加材料里直接给出了具体的值。

输入：大小为 $N^{{}^{\prime }}\times K\times (d+C)$ 的 $N^{{}^{\prime }}$ 个局部区域的点集。

输出：大小为 $N^{{}^{\prime }}\times (d+C^{{}^{\prime }})$的数据。

目的：输出中的每个局部区域由其 centroid 和编码 centroid 邻域的局部特征抽象出来。即提取每个局部区域的特征，该特征由 centroid 的位置和其余特征编码而成。

方法：首先，一个局部区域的点集的坐标被变换到一个相对于 centroid 的局部坐标系（相对坐标）： $x_i^{(j)}=x_i^{(j)}-{\hat{x}}^{(j)}fori=1,2,\cdots ,K$ and $j=1,2,\cdots ,d$ ，其中 $\hat{x}$ 是 centroid 的坐标。然后，利用 PointNet 作为local pattern learning的基本构架。通过使用相对坐标和点特征来获取局部区域的 point-to-point 关系。

点云分布不一致，即采样密度是non-uniform时，每个子区域中如果在生成的时候使用相同的半径，会导致有些区域采样点过少。

为了解决不同的采样密度问题，本文提出了 density adaptive PointNet layer，learn to combine features from regions of different scales when the input sampling density changes.。Hierarchical Point Set Feature Learning + density adaptive PointNet layer就构成了PointNet++。

在3.2节，每个 set abstraction level 包含单个尺度的分组和特征提取。在pointnet++中，每个set abstraction level提取多个尺度的局部模式，并根据局部点密度进行智能组合。也就是说，3.2节讨论的是对于单个尺度的处理方式；3.3节是同时给多个尺度，每个尺度按照3.2节的方式处理，最后把这些尺度的特征结合起来。

在分组局部区域和结合不同尺度的特征方面，我们提出了以下两种类型的密度自适应层。示意图如下所示：

捕获多尺度模式的一种简单而有效的方法是应用具有不同尺度的分组层，然后根据PointNets提取每个尺度的特征。将不同尺度的特征串联起来形成一个多尺度特征（就是直接拼接在一起，不做任何额外的处理，相当于拼接两个vector）。也就是，对于每一层，给多个scale，然后对这些scale都利用set abstraction layer提取特征，然后把这些多个scale的特征拼接起来，就形成了所谓的multi-scale特征。然后将 multi-scale特征作为centroid的特征。

MSG方法计算成本很高，因为它对每个 centroid 在大规模的邻域上运行局部Poin