论文笔记：KD-Net

快来打我* 2021-12-20 16:01 340阅读 0赞

# Escape from Cells: Deep Kd-Networks for the Recognition of 3D Point Cloud Models #

## 1、四个问题 ##

1.  要解决什么问题？
    
     *  3D点云识别任务。
2.  用了什么方法解决？
    
     *  参考KD树的结构，提出了一种新的树形结构的神经网络，用来处理不规则的点云数据。
3.  效果如何？
    
     *  在形状分类任务、形状检索任务以及形状部件分割任务中都取得了领先的效果。
4.  还存在什么问题？
    
     *  如果点云存在旋转，那么KD树在X/Y/Z轴方向进行切分时会得到不同的结果，影响最终的效果。
     *  每次网络做前向操作时，都需要先将输入的点云转为KD树，预处理时必须要占用一定时间。

## 2、论文概述 ##

### 2.1、简介 ###

*  我们都知道，由于点云是非欧式结构的数据，无法对其直接应用CNN。常用的思路是将其转换为体素网格，但是这样会带来额外的内存消耗和很大的计算量。
 *  作者认为：诸如KD树、八叉树等数据结构常被用于表示不规则的数据。那么，是否能将这些数据结构扩展到深度神经网络中呢？这样的网络结构也就能够处理那些不规则结构的数据。
 *  由此，作者提出了KD网络，主要是模仿卷积神经网络的思想，但是又使用KD树的结构来构建计算图。

### 2.2、KD-Networks ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70]

*  图1是KD-Netwoks的示意图。图中只考虑二维的情况。
 *  在一个有8个点的点云上建立KD树，在每一层都从X/Y轴选择一个维度进行划分。
 *  从根节点到叶节点对KD树的每个节点进行编号，根节点编号为0，往后递增。
 *  KD数最左边的8到15号节点实际就是原始点云，右边的0号节点可以看做输出的类别预测 v 0 v\_0 v0。
 *  从左到右，可以看做这个KD-Network的特征前向传播的方向。
 *  图中的圆圈表示的是特征传播并聚合的过程，对应卷积核，其参数是可学习的。相同的颜色表示共享参数，即如果是在相同维度对点集进行划分，认为其卷积参数也应该共享。

#### 2.2.1、输入 ####

*  由于KD-Network每次都要从3D点云构建KD树，而KD树的节点数是 N = 2 D N=2^\{D\} N=2D，因此点云的点数也必须是 2 D 2^\{D\} 2D。如果点云的点数不同，还需要对其做上采样或者下采样。
 *  构建KD树时，我们以自顶向下的方式递归地生成每个树节点。每次都选取能最好地分割整个点集的坐标轴作为划分标准，将点集划分为两个一样大的子集，然后递归生成。
 *  一个深度为 D D D的平衡KD树包含有 N − 1 = 2 D − 1 N-1=2^\{D\}-1 N−1=2D−1个非叶节点。
 *  每个非叶节点 V i ∈ T V\_\{i\} \\in \\mathcal\{T\} Vi∈T都与三个划分方向 d i d\_i di（X/Y/Z轴， d i ∈ \{ X , Y , Z \} d\_i \\in \\\{X, Y, Z\\\} di∈\{ X,Y,Z\}）以及划分位置 t i \\mathcal\{t\}\_i ti有关。
 *  KD树上的节点还与层数 l i ∈ \{ 1 , … , D − 1 \} l\_\{i\} \\in\\\{1, \\ldots, D-1\\\} li∈\{ 1,…,D−1\}有关， l i = 1 l\_\{i\}=1 li=1是根节点， l i = D l\_\{i\}=D li=D是叶节点，也对应着3D点云上的点。
 *  假设KD树是平衡树，那么第 i i i号节点的子节点的编号分别是 c 1 ( i ) = 2 i c\_\{1\}(i)=2 i c1(i)=2i和 c 2 ( i ) = 2 i + 1 c\_\{2\}(i)=2 i + 1 c2(i)=2i\+1。

#### 2.2.2、KD-Networks的数据处理 ####

*  给定一个输入的KD树 T \\mathcal\{T\} T，KD-Network会计算KD树的每个节点上的特征向量 v i \\mathbf\{v\}\_i vi。
 *  叶节点即输入是一个 k k k维向量，由输入点云的维度确定。
 *  第 l ( i ) l(i) l(i)层上的非叶节点 i i i，其子节点 c 1 ( i ) c\_1(i) c1(i)和 c 2 ( i ) c\_2(i) c2(i)在第 l ( i ) + 1 l(i) + 1 l(i)\+1层，其特征向量 v c 1 ( i ) \\mathbf\{v\}\_\{c\_\{1\}(i)\} vc1(i)和 v c 1 ( i ) \\mathbf\{v\}\_\{c\_\{1\}(i)\} vc1(i)已经计算好了。那么当前节点 i i i的特征向量 v i \\mathbf\{v\}\_i vi的计算公式如下：
    
     *   v i = \{ ϕ ( W x l i \[ v c 1 ( i ) ; v c 2 ( i ) \] + b x l i ) , i f d i = x ϕ ( W y l i \[ v c 1 ( i ) ; v c 2 ( i ) \] + b y l i ) , i f d i = y ϕ ( W z l i \[ v c 1 ( i ) ; v c 2 ( i ) \] + b z l i ) , i f d i = z \\mathbf\{v\}\_\{i\}=\\left\\\{\\begin\{array\}\{l\}\{\\phi\\left(W\_\{\\mathrm\{x\}\}^\{l\_\{i\}\}\\left\[\\mathbf\{v\}\_\{c\_\{1\}(i)\} ; \\mathbf\{v\}\_\{c\_\{2\}(i)\}\\right\]+\\mathbf\{b\}\_\{\\mathrm\{x\}\}^\{l\_\{i\}\}\\right)\}, if \\ d\_i = x \\\\ \{\\phi\\left(W\_\{\\mathrm\{y\}\}^\{l\_\{i\}\}\\left\[\\mathbf\{v\}\_\{c\_\{1\}(i)\} ; \\mathbf\{v\}\_\{c\_\{2\}(i)\}\\right\]+\\mathbf\{b\}\_\{\\mathrm\{y\}\}^\{l\_\{i\}\}\\right)\}, if \\ d\_i = y \\\\ \{\\phi\\left(W\_\{\\mathrm\{z\}\}^\{l\_\{i\}\}\\left\[\\mathbf\{v\}\_\{c\_\{1\}(i)\} ; \\mathbf\{v\}\_\{c\_\{2\}(i)\}\\right\]+\\mathbf\{b\}\_\{z\}^\{l\_\{i\}\}\\right)\}, if \\ d\_i = z \\end\{array\}\\right. vi=⎩⎨⎧ϕ(Wxli\[vc1(i);vc2(i)\]\+bxli),ifdi=xϕ(Wyli\[vc1(i);vc2(i)\]\+byli),ifdi=yϕ(Wzli\[vc1(i);vc2(i)\]\+bzli),ifdi=z
     *  或简写为： v i = ϕ ( W d i l i \[ v c 1 ( i ) ; v c 2 ( i ) \] + b d i l i ) \\mathbf\{v\}\_\{i\}=\\phi\\left(W\_\{d\_\{i\}\}^\{l\_\{i\}\}\\left\[\\mathbf\{v\}\_\{c\_\{1\}(i)\} ; \\mathbf\{v\}\_\{c\_\{2\}(i)\}\\right\]+\\mathbf\{b\}\_\{d\_\{i\}\}^\{l\_\{i\}\}\\right) vi=ϕ(Wdili\[vc1(i);vc2(i)\]\+bdili)
     *   ϕ ( ⋅ ) \\phi(\\cdot) ϕ(⋅)是非线性单元（ReLU）。
     *  第 l i l\_i li层的可学习的参数是 \{ W x l i , W y l i , W z l i , b x l i , b y l i , b z l i \} \\left\\\{W\_\{\\mathrm\{x\}\}^\{l\_\{i\}\}, W\_\{\\mathrm\{y\}\}^\{l\_\{i\}\}, W\_\{\\mathrm\{z\}\}^\{l\_\{i\}\}, \\mathbf\{b\}\_\{\\mathrm\{x\}\}^\{l\_\{i\}\}, \\mathbf\{b\}\_\{\\mathrm\{y\}\}^\{l\_\{i\}\}, \\mathbf\{b\}\_\{\\mathrm\{z\}\}^\{l\_\{i\}\}\\right\\\} \{ Wxli,Wyli,Wzli,bxli,byli,bzli\}。
     *  根据KD树的划分方向 d i d\_i di，选取上面三组参数中的一组进行计算。
 *  每层的矩阵 W W W和 b b b的维度为 m 1 , m 2 , … , m D m^\{1\}, m^\{2\}, \\ldots, m^\{D\} m1,m2,…,mD。
 *  第 l l l层的 W x l W\_\{\\mathrm\{x\}\}^\{l\} Wxl、 W y l W\_\{\\mathrm\{y\}\}^\{l\} Wyl、 W z l W\_\{\\mathrm\{z\}\}^\{l\} Wzl维度是 m l × 2 m l + 1 m^\{l\} \\times 2 m^\{l+1\} ml×2ml\+1（因为每个非叶节点有两个子节点），而 b x l \\mathbf\{b\}\_\{\\mathrm\{x\}\}^\{l\} bxl、 b y l \\mathbf\{b\}\_\{\\mathrm\{y\}\}^\{l\} byl、 b z l \\mathbf\{b\}\_\{\\mathrm\{z\}\}^\{l\} bzl的维度是 m l m^l ml。

#### 2.2.3、分类网络结构 ####

*  对于分类网络来说，只要让根节点输出的特征向量的维度数为类别数，即可得到分类结果。
    
     *   v 0 ( T ) = W 0 v 1 ( T ) + b 0 \\mathbf\{v\}\_\{0\}(\\mathcal\{T\})=W^\{0\} \\mathbf\{v\}\_\{1\}(\\mathcal\{T\})+\\mathbf\{b\}^\{0\} v0(T)=W0v1(T)\+b0
     *   W 0 W^0 W0和 b 0 \\mathbf\{b\}^\{0\} b0是最后的分类层的参数。

#### 2.2.4、形状检索网络结构 ####

*  与分类网络类似，但是最后的根节点输出的不是分类预测结果而是一个描述子（特征向量）。训练时加上度量学习的损失函数：histogram loss，siamese loss，triplet loss等，来约束输出的特征向量，使得同类形状的特征向量之间距离更小，不同类的特征向量之间距离更大。

#### 2.2.5、分割网络结构 ####

*  在部件分割任务上，KD-Network参考了卷积神经网络对结构进行了更改，也使用了编码器-解码器（encoder-decoder）的结构，并加入了跳跃连接（skip connections）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 1]

*  上图是分割网络的示意图。
 *  这里的分割网络可以看成是将两个KD树拼接在了一起，左半边与分类网络和检索网络结构一样，是encoder；右半边是decoder，也就是倒过来的KD树，将根节点的特征传播到所有的叶节点上。
 *  设右半部分的KD树的根节点为 v 1 \\mathbf\{v\}\_\{1\} v1，而节点 i i i上的特征向量为 v i \\mathbf\{v\}\_\{i\} vi。
 *  特征传播时的更新公式如下：
    
     *   v ~ c 1 ( i ) = ϕ ( \[ W ~ d c 1 ( i ) l i v ~ i + b ~ d c 1 ( i ) l i ; S l i v c 1 ( i ) + t l i \] ) v ~ c 2 ( i ) = ϕ ( \[ W ~ d c 2 ( i ) l i v ~ i + b ~ d c 2 ( i ) l i ; S l i v c 2 ( i ) + t l i \] ) \\begin\{aligned\} \\tilde\{\\mathbf\{v\}\}\_\{c\_\{1\}(i)\} &=\\phi\\left(\\left\[\\tilde\{W\}\_\{d\_\{c\_\{1\}(i)\}\}^\{l\_\{i\}\} \\tilde\{\\mathbf\{v\}\}\_\{i\}+\\tilde\{\\mathbf\{b\}\}\_\{d\_\{c\_\{1\}(i)\}\}^\{l\_\{i\}\} ; S^\{l\_\{i\}\} \\mathbf\{v\}\_\{c\_\{1\}(i)\}+\\mathbf\{t\}^\{l\_\{i\}\}\\right\]\\right) \\\\ \\tilde\{\\mathbf\{v\}\}\_\{c\_\{2\}(i)\} &=\\phi\\left(\\left\[\\tilde\{W\}\_\{d\_\{c\_\{2\}(i)\}\}^\{l\_\{i\}\} \\tilde\{\\mathbf\{v\}\}\_\{i\}+\\tilde\{\\mathbf\{b\}\}\_\{d\_\{c\_\{2\}(i)\}\}^\{l\_\{i\}\} ; S^\{l\_\{i\}\} \\mathbf\{v\}\_\{c\_\{2\}(i)\}+\\mathbf\{t\}^\{l\_\{i\}\}\\right\]\\right) \\end\{aligned\} v~c1(i)v~c2(i)=ϕ(\[W~dc1(i)liv~i\+b~dc1(i)li;Slivc1(i)\+tli\])=ϕ(\[W~dc2(i)liv~i\+b~dc2(i)li;Slivc2(i)\+tli\])
     *   W ~ d c ∗ ( i ) l i \\tilde\{W\}\_\{d\_\{c \*(i)\}^\{l\_\{i\}\}\} W~dc∗(i)li和 b ~ d c , ( i ) l i \\tilde\{\\mathbf\{b\}\}\_\{d\_\{c,(i)\}\}^\{l\_\{i\}\} b~dc,(i)li分别是网络中的权重和偏置参数。
     *   S l i S^\{l\_\{i\}\} Sli和 t l i t^\{l\_\{i\}\} tli分别是跳跃连接上的权重和偏置参数。
 *  整个网络的结构类似U-Net，在encoder-decoder结构的基础之上加入了shortcut，避免一些信息的损失。

#### 2.2.6、实现细节 ####

*  预处理，所有点云都事先归一化到 \[ − 1 ; 1 \] 3 \[-1 ; 1\]^\{3\} \[−1;1\]3。

### 2.3、实验 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 7]

## 3、参考资料 ##

1.  [Escape from Cells: Deep Kd-Networks for the Recognition of 3D Point Cloud Models][Escape from Cells_ Deep Kd-Networks for the Recognition of 3D Point Cloud Models]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70]: /images/20211220/f372a343718d4bd2a951b6a15b7a9242.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 1]: /images/20211220/116e97be07be4de4a5b1973265d289e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 2]: /images/20211220/118139646f6d4126b93ac93f25451bc4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 3]: /images/20211220/25bdcb81a934409780f8920107a510ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 4]: /images/20211220/7186d6b83fdf41c1b4df247cc7ddd033.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 5]: /images/20211220/f75b1845e59044aca00acb625ba47d15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 6]: /images/20211220/4c3f755f6a054dfd821f0a249de1dd0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 7]: /images/20211220/85dcaf77e24b4f6c9a6b05926abe48ea.png
[Escape from Cells_ Deep Kd-Networks for the Recognition of 3D Point Cloud Models]: https://ieeexplore.ieee.org/document/8237361/