论文精读（十一）DGCNN

Dynamic Graph CNN for Learning on Point Clouds

论文地址：1801.07829] Dynamic Graph CNN for Learning on Point Clouds

博客参考：https://blog.csdn.net/hongbin_xu/article/details/85258278

Acm Transactions On Graphics 2019(IF 7.8 引用7000+)

论文背景（AI）

点云是计算机图形学中一种基本的几何表示形式，由散乱的2D或3D点组成。点云数据通常由3D扫描设备直接获取，如LiDAR扫描仪和立体重建技术。由于点云数据的不规则性（点的位置在空间中连续分布，且点的排列顺序不影响其空间分布），传统的深度学习方法难以直接应用于点云处理。近年来，随着深度学习在图像分析领域的巨大成功，研究者们开始探索将卷积神经网络（CNN）的思想应用于点云数据的处理。

摘要

使用提出的神经网络对点云进行分割。底部：示意图神经网络架构。顶部：在网络的不同层次产生的特征空间的结构，可视化为从红点到其他所有点的距离（从左到右显示输入和层1-3；最右边的图显示了结果分割）。观察深层中的特征空间结构如何捕捉语义上相似的结构，如机翼、机身或涡轮，尽管在原始输入空间中它们之间存在很大距离。

点云提供了一种灵活的几何表示，适用于计算机图形学中无数的应用程序；它们也包含大多数3D数据采集设备的原始输出。尽管在图形和视觉方面长期以来一直提出了在点云上手动设计的特征，但是，卷积神经网络（CNNs）在图像分析方面的最近压倒性成功表明了从CNN中获取洞察力对点云世界的价值。点云固有地缺乏拓扑信息，因此设计一个模型来恢复拓扑可以丰富点云的表示能力。为此，我们提出了一个新的神经网络模块，名为EdgeConv，适用于基于CNN的点云上的高级任务，包括分类和分割。EdgeConv在网络的每一层动态计算的图上起作用。它是可微的，并可以插入到现有的架构中。与操作在外部空间或独立处理每个点的现有模块相比，EdgeConv具有几个吸引人的特性：它包含局部邻域信息；它可以堆叠应用以学习全局形状属性；在多层系统中，特征空间中的亲和性捕捉了原始嵌入中潜在的长距离上的语义特征。我们展示了我们模型在标准基准测试中的性能，包括ModelNet40，ShapeNetPart和S3DI。

核心与贡献

最近的算法倾向于搜索点云中的语义线索和一致性，而不是像角点和边缘点这样显著的几何特征。仅仅通过传统方法如计算或者微分这类的方法提取的几何信息显然不够用，所以现在更多地需要基于学习的方法（源自于通过对有标签或无标签的数据集的统计分析得到的相关信息）。文中主要考虑点云分类和分割任务。传统的解决办法是，提取handcrafted的特征来获取点云的几何信息。近来，深度学习在图像处理领域的大获成功，催化了使用数据驱动方法来从点云学习特征的研究。由于常规的深度网络的输入都是规则结构的数据，而点云则是不规则的数据：每个点在空间中都是连续分布的，并且任何点在顺序上的置换都不会改变空间分布。
一类常用的方法是，将点云转换为volumetric representation（体表示），也就是3D网格，随后便可以采用3D的CNN网络来提取特征。然而，这种方法会造成quantization artifacts，和额外的内存占用，导致难以提取高分辨率或者细粒度特征。
另一类方法，则是可以直接将不规则的点云作为输入的深度网络，即PointNet系的网络。PointNet，通过独立地处理每个点，能实现置换不变性（permutation invariance）。随后使用一个对称函数（symmetric function）来聚合特征。之后，一些基于PointNet的改进网络会考虑点的局部特征，而不是分开处理。这样可以让网络提取到局部特征，提高模型的性能。然而这类算法，在处理局部区域的点的时候为了保证置换不变性，而导致过于独立。这样会忽视点之间的几何相关信息，导致丢失一部分局部特征信息。

我们提出了一种新颖的简单操作，称为EdgeConv，它在保持排列不变性的同时捕获局部几何结构。EdgeConv不是直接从嵌入中生成点特征，而是生成描述点与其邻居之间关系的边特征。EdgeConv设计为对邻居的排序不变，因此是排列不变的。由于EdgeConv明确构建了一个局部图并学习了边的嵌入，该模型能够在欧几里德空间和语义空间中对点进行分组。EdgeConv易于实现并集成到现有的深度学习模型中，以提高其性能。

在我们的实验中，我们将EdgeConv集成到PointNet的基本版本中，而不使用任何特征转换。我们展示了所得网络在多个数据集上实现了最先进的性能，尤其是在ModelNet40和S3DIS上进行的分类和分割任务。

我们提出了一种新颖的操作EdgeConv用于学习点云，以更好地捕获点云的局部几何特征，同时保持置换不变性。

我们展示了模型可以通过动态更新从层到层的关系图来语义地分组点。
我们证明了EdgeConv可以集成到多个现有的点云处理流程中。
我们对EdgeConv进行了广泛的分析和测试，表明其在基准数据集上实现了最先进的性能。
我们发布我们的代码以促进可重现性和未来研究。

本文最核心的创新就是设计了EdgeConv这一效果不错的表征模块，并且可以将其运用到坐标空间和特征空间（实现动态更新图结构）。

EdgeConv

左：从一个点对xi和xj（底部）计算边特征eij（顶部）。在这个例子中，hΘ()使用全连接层实例化，可学习参数是其关联的权重。右：EdgeConv操作。EdgeConv的输出是通过聚合与每个连接顶点发出的所有边相关的边特征来计算的。

根据图结构计算edge feature。

聚合edge feature，对其对应的中心点表征新的特征。

方案：

hθ(xi,xj)=hθ(xi,xj−xi)

EdgeConv选择的就是这个方案，既考虑了局部邻域的global信息 xi ，又考虑了local neighborhood信息 xj−xi 。

接着再送入一个感知机，即得到了edge feature：

eijm′=ReLU(θm⋅(xj−xi)+ϕm⋅xi)

其中： Θ=(θ1,…,θM,ϕ1,…,ϕM) 为可学习参数

关于聚合操作：

xim′=maxj:(i,j)∈Ωeijm′

EdgeConv在网络的每一层上动态构建图结构，将每一点作为中心点来表征其与各个邻点的edge feature，再将这些特征聚合从而获得该点的新表征。

EdgeConv实现的实际就是通过构建局部邻域（这种局部邻域既可以建立在坐标空间，也可以建立在特征空间），对每个点表征。

由上面的介绍我们不难想到，将多个EdgeConv模块首尾相接不断堆叠也就是为了获得多层次、具有更加丰富语义的表征。

也就是：EdgeConv输入 N∗F ，输出 N∗F′

图结构动态更新

我们的实验表明，在每一层产生的特征空间中使用最近邻重新计算图是有益的。这是我们的方法与在固定输入图上工作的图 CNN 的重要区别。这种动态图更新正是我们的架构名称 "动态图 CNN（DGCNN）"的由来。有了动态图更新，感受野就会像点云的直径一样大，同时又是稀疏的。在每一层，我们都有一个不同的图 G(l) = (V(l), E(l))，其中第 l 层的边的形式为 (i, ji1), ., (i, jikl ) 这样，x(l) ji1 , ., x(l) jikl 是最接近 x(l) i 的 kl 个点。换句话说，我们的架构会学习如何构建每层使用的图 G，而不是将其作为网络评估前构建的固定常数。在我们的实现过程中，我们会计算特征空间中的成对距离矩阵，然后为每个单点提取最接近的 k 个点。

不断重新计算各个点在每一层特征空间的近邻是recompute graph的关键。注意：这一点很重要。这是DGCNN和GCN的最大不同，GCN是在坐标空间构建好图结构后整体图结构就固定了，没有动态更新的过程！

具体来说，每经过一个EdgeConv层后，模型会根据该层的输出特征重新计算成对距离矩阵，并基于新的距离矩阵重新构建图的邻接关系。这种动态更新机制使得模型能够更好地捕捉点云数据中的语义信息和局部几何结构。

特点

排列不变性Permutation Invariance

xi′=maxj:(i,j)∈Ωhθ(xi,xj)

输出的 xi′ 对 xj 的任意排布是保持不变的。

因为聚合操作这里用的是channel wise的max pooling

平移不变性Translation Invariance

这里只是一种“局部的”平移不变性

考虑对 xi 和 xj 平移 T ，则：

eijm′=θm⋅(xj+T−(xi+T))+ϕm⋅(xi+T)=θm⋅(xj−xi)+ϕm⋅(xi+T)

后一项不是平移不变的，因此这里是“局部的”平移不变的。

任务架构

点云变换块：点云变换块的设计目的是通过应用一个估计的 3 × 3 矩阵，将输入点集对齐到一个标准空间。要估算 3 × 3 矩阵，需要使用一个张量，该张量包含每个点的坐标和 k 个相邻点的坐标差。

边缘转换模块：EdgeConv 模块将形状为 n × f 的张量作为输入，通过应用多层感知器（mlp）（神经元层数定义为 {a1，a2，…，an }）计算每个点的边缘特征，并在汇集相邻边缘特征后生成形状为 n × an 的张量。

本质上都是分类，Loss用的交叉熵。

与现有方法比较

DGCNN将现有的点云处理两大流派：PointNet和Graph CNN关联了起来

PointNet可以看成是在KNN时设置k=1的情况：即 hθ(xi,xj)=hθ(xi) ，只考虑单个点信息的情况。因此PointNet可以看成是DGCNN的特殊版本。

PointNet++：虽然是使用PointNet的方式考虑了局部结构，但是：

in each layer applies a graph coarsening operation. For each layer, some points are selected using farthest point sam- pling (FPS); only the selected points are preserved while others are directly discarded after this layer.（PN++有降采样过程，DGCNN没有）
PointNet++ computes pairwise distances using point input coordinates, and hence their graphs are fixed during training.（PN++构建的图结构是固定的，基于坐标空间构建的）
PointNet++本质还是没有跳脱PointNet的圈子，使用的edge feature仍是 hθ(xi,xj)=hθ(xj) ，然后聚合操作使用了个max pooling