这篇文章来自CVPR2019，它的主要内容是通过在点云上构造图，然后在图上进行特征提取，用于点云分割或分类任务。这里用到的是空间域的图卷积方法。整体来看这篇文章，其实与PointNet++（可以参见关于PointNet++的另一篇博客）的处理方法类似: 点云特征下采样，点云数据局部特征提取，点云特征上采样。 主要区别点是通过将点云转换到图之后，提出了文中所称的“Graph Attention Convolution”，用于进一步调整提取的点云数据特征，本质上类似通常CNN中的channel attention。下面来分析这篇文章的主要内容。

1.主要内容

首先，来看一下文中提出的网络的主体结构：

可以看到，该网络主要由: Graph pooling (类似下采样), Graph attention convolution，Feature interpolation (类似上采样)。 下面按照这个顺序进行分析，由于graph pooling涉及到图的稀疏化，先来简单分析下点云图数据的构造以及graph coarsening。

1.1 Graph Pyramid Construction

这个操作类似通常CNN中的层级特征（hierarchical feature）提取, 其主要由下面两个步骤构成：

1） Graph construction on point cloud: 由于点云天然具有空间坐标，所以直接自然的方法就是根据空间相邻关系构造图结构。具体来说，就是把点云中的每个点作为顶点，得到图的顶点集$V$；在以每个顶点为球心，半径为$\rho$的球内选取$K_G$个相邻点（文中使用的是随机选择），然后将该顶点与这$K_G$点分别连一条边，最终得到整个点云数据对应图的边的集合$E$。

2）Graph coarsening: 由于要构造点云图金字塔层级结构，就必须对图结构数据进行下采样。对一般的图结构数据进行下采样本身是一个很难的问题；不过点云数据具有一定的几何特性，文中直接使用farthest point sampling方法，对点云图数据进行下采样（PointNet++中也是这样处理的）。

可以连续进行上面的两个操作，最终得到点云图数据的金字塔层级结构。这样就和通常CNN中的层级特征相对应。

1.2 Graph Pooling

这个操作主要实现在执行graph coarsening时，提取图节点的局部特征（local features），作为graph coarsening之后的顶点的特征，类似通常CNN中的$k\times k$的卷积核（步长>1）或pooling。
具体地，设$H_l^{{}^{\prime }}$ 表示图金字塔第$l$尺度的特征，$H_{l+1}$ 表示图金字塔第$l+1$尺度的特征，那么具体的graph pooling计算如下：
h v = p o o l i n g { h j ′ : j ∈ N l ( v ) } , (1) h_{v}=pooling\{h_{j}^{'}: j\in N_{l}(v)\},\tag{1} hv​=pooling{hj′​:j∈Nl​(v)},(1)
其中$h_v\in H_{l+1}$，而$N_l(v)$表示顶点$v$在第$l$尺度下的领域。注意这里的$pooling$可以是$maxpooling$ 或者 $averagepooling$。

1.3 Graph Attention Convolution (GAC）

首先来看下Graph Attention Convolution 的结构图，

接下来，先给出GAC的最终表达式，然后分析该表达式所包含的内容。 GAC的表达式如下：
$$h_i^{{}^{\prime }}=\sum _{j\in N(i)}{a}_{ij}\ast M_g(h_j)+b_i\text{\hspace{1em}(2)}$$
其中$\ast$表示Hadamard乘积，即逐元素相乘；而
$$M_g:R^F\to R^K\text{\hspace{1em}(3)}$$
是一个特征变换函数（即对每个点特征进行特征变换，可以由多层感知机实现）；
$$a_{ij}=\frac{\exp ({\tilde{a}}_{ij,k})}{{\sum }_{l\in N(i)\exp ({\tilde{a}}_{il,k})}},{\tilde{a}}_{ij}=\alpha (\Delta p_{ij},\Delta h_{ij})\in R^K\text{\hspace{1em}(4)}$$ $$\alpha (\Delta p_{ij},\Delta h_{ij})=M_{\alpha }([\Delta p_{ij}||\Delta h_{ij}]),\Delta h_{ij}=M_g(h_i)-M_g(h_j)\in R^K\text{\hspace{1em}(5)}$$
其中$||$表示concatenation，$\Delta p_{ij}=p_i-p_j\in R^3$, 即顶点$i,j$的坐标差；$M_{\alpha }$表示一个多层感知机。

则这个GAC有如下的特点：
I. 根据上面的公式（4）可知$a_{ij}$已经按邻域进行了归一化，这是由于每个顶点的相邻点个数可能不相同；
II. 根据上面的公式（2），该GAC具有局部特征提取的能力，因为在每个顶点$i$，聚合了整个邻域$N(i)$的特征；
III. 同样根据上面的公式（2），可知权重$a_{ij}$逐元素乘到特征$M_g(h_j)$上，类似通常CNN中的channel attention , 这可能也是 Graph Attention Convolution得名的由来。

直观说来，GAC通过图的邻域关系，进行特征变换，实现类似通常CNN中的$k\times k$ 卷积，提取局部特征；同时通过点特征的差异以及坐标差异，计算特征channel的权重，实现类似通常CNN中的channel attention机制。

1.4 Feature Interpolation

这个操作即实现点特征的上采样，用于恢复经过下采样后特征的空间分辨率。具体如下，假设当前的特征$H_l^{{}^{\prime }}$在图金字塔第$l$尺度，具有空间分辨率$P_l$ (即$l$尺度下点云形成的集合)，注意到空间分辨率$P_l$通过$P_{l-1}$下采样（即graph coarsening）得到，即$P_l\subset P_{l-1}$；为了将$H_l^{{}^{\prime }}$上采样得到具有高空间分辨率$P_{l-1}$的特征$H_{l-1}^{{}^{\prime }}$, 文中通过选择$P_{l-1}$在$P_l$中的3近邻，按逆距离权重插值得到新的插值点的特征值，这与PointNet++中的feature interpolation方法是一样的，可以参考PointNet++博客。

2. 实验结果

这里主要是GACNet在semantic3D数据集上的模型结果（可以从semantic3D的leadboard 看到其他的模型性能）。

总结： 这篇文章对点云数据的操作，本质上和PointNet++类似; 不同的是将点云进行图结构转换，用于记录邻域关系，实现点云特征的下采样，局部点云特征提取，以及点云特征的上采样，实现一个类似通常的Encoder-Decoder网络结构；同时通过GAC，实现一个类似通常CNN中的channel attention操作。