首发于机器学习和深度学习

点云基于图论的处理方法

harrylin

本系列是按照bilibili上刘永成博士的分享课的论文笔记，主要针对点云基于图论的处理方法。这一部分主要讲解的方法包括：DGCNN、RGCNN、Spectral Graph Convolution、DeepGCNs

转自我的个人博客:

DGCNN (TOG 2019)

DGCNN: Dynamic Graph CNN for Learning on Point Clouds

具体思想

改进pointNet方法。主要是pointNet在特征提取中只考虑各个点的特征，未对相邻点进行考虑。PointNet的主要流程是：先单独计算（更新）每个点的feature，更新多次之后，最后用global pool将所有点的feature整合为一个点云的feature。在更新每个点的feature时，只与这个点之前的feature有关，与其它点的feature无关。作者在论文中认为：每个点的feature在计算（更新）过程中彼此独立，每个都相可以看作是一个全局feature。这可能就是一个值得改进的地方。
提出动态图的想法，每经过一次edgeConv之后都要重新提取一次动态图，即knn特征提取。使得特征感受野逐步增加。

核心部分

edgeConv

输入特征维度为$(n,c_1)$，针对每一个点$x_i$计算它的knn，即k个相邻点(使用top-k即升序得到)。
计算每个点的edge特征：$x_{j_{i1}}-x_i,...,x_{j_{ik}}-x_i$
将点的特征和边的特征连接起来。$(x_i, x_{j_{i1}}-x_i),....,(x_i, x_{j_{ik}}-x_i)$
使用共享参数的全连接层来进行特征提取。代码中可以用1x1的卷积来实现。得到k个特征。
用max-pool这种对称函数来提取每个点的特征。输出特征维度为$(n,c_2)$。

这样一来更新权重的时候，每一个点的权重更新不止于这个点的特征有关，还与周边的k个最邻点的特征有关。

动态图

x = get_graph_feature(x, k=self.k)
x = self.conv1(x)
x1 = x.max(dim=-1, keepdim=False)[0]

x = get_graph_feature(x1, k=self.k)
x = self.conv2(x)
x2 = x.max(dim=-1, keepdim=False)[0]

x = get_graph_feature(x2, k=self.k)
x = self.conv3(x)
x3 = x.max(dim=-1, keepdim=False)[0]

x = get_graph_feature(x3, k=self.k)
x = self.conv4(x)
x4 = x.max(dim=-1, keepdim=False)[0]

x = torch.cat((x1, x2, x3, x4), dim=1)

在每一次edgeConv之前要进行新特征的图提取，提取出新特征每一个点的k个相邻特征。这样图结构就变成动态的，能够自适应不同数据。越深的特征感受野也就越大。如代码所示也将不同感受野的特征进行了连接操作。

Regularized GCNN. MM 2018

RGCNN: Regularized Graph CNN for Point Cloud Segmentation

具体思想

用图论的思想处理点云数据，论文中graph中说的是全连接图，即点云中所有点是互通的。然后用正则化的图卷积来进行特征提取。
用切比雪夫多项式拟合$L^k$降低计算复杂度。结构图如下所示：

这篇文章只讲关键部分，具体推导请看我的另外一篇GCN的博客。

核心部分

邻接矩阵A、度矩阵D、拉普拉斯矩阵L

A: 定义的图结构为全连接图，计算点云的A矩阵的公式为：

D: 因为图结构是全连接，所以度矩阵D为对角线为点云总点数的对角阵。
L: 正常L = D - A，归一化的L为: $\boldsymbol{L}=\boldsymbol{D}^{-1 / 2}(\boldsymbol{D}-\boldsymbol{W}) \boldsymbol{D}^{-1 / 2}=\boldsymbol{I}_{n}-\boldsymbol{D}^{-1 / 2} \boldsymbol{W D}^{-1 / 2}$

图卷积

因为点云所在的空间不像图像类似的欧式空间，我们可以建立点云之间的拓扑图，在这个拓扑图上进行特征提取。所以这也是另外一个处理点云数据的方法。
将空域的数据转换为频域上面，用傅里叶变化进行变换计算之后再通过傅里叶逆变换转换回来。$\mathbf{x} *_{\mathcal{G}} \mathbf{y}=\mathbf{U}\left(\mathbf{U}^{T} \mathbf{x}\right) \odot\left(\mathbf{U}^{T} \mathbf{y}\right)$，其中$U^Tx$为傅里叶变换，$Ux$为逆变换，相乘方式为逐点乘。
通过滤波提取有用特征:

切比雪夫多项式

使用切比雪夫截断法来拟合$L^k$降低计算复杂度。

结合代码:

def chebyshev5(self, x, L, Fout, K):
        # If K == 1 it is equivalent to fc layer
        N, M, Fin = x.get_shape()
        N, M, Fin = int(N), int(M), int(Fin)
        x0 = x  # N x M x Fin
        x = tf.expand_dims(x0, 0)

        def concat(x, x_):
            x_ = tf.expand_dims(x_, 0)  # 1 x M x Fin*N
            return tf.concat([x, x_], axis=0)  # K x M x Fin*N

        if K > 1:
            x1 = tf.matmul(L, x0)
            x = concat(x, x1)
        for k in range(2, K):
            x2 = 2 * tf.matmul(L, x1) - x0
            x = concat(x, x2)
            x0, x1 = x1, x2
        # K x N x M x Fin
        x = tf.transpose(x, perm=[1, 2, 3, 0])  # N x M x Fin x K
        x = tf.reshape(x, [N * M, Fin * K])  # N*M x Fin*K
        # Filter: Fin*Fout filters of order K, i.e. one filterbank per feature pair.
        W = self._weight_variable([Fin * K, Fout], regularization=False)
        x = tf.matmul(x, W)  # N*M x Fout
        return tf.reshape(x, [N, M, Fout])  # N x M x Fout