[ECCV ] IDAM(Iterative Distance-Aware Similarity Matrix Convolution with Mutual-Supervised ..)

零、概要

• 论文: Iterative Distance-Aware Similarity Matrix Convolution with Mutual-Supervised Point Elimination for Efficient Point Cloud Registration
• tag: ECCV 2020; Registration
• 代码: https://github.com/jiahaowork/idam
• 作者: Jiahao Li, Changhao Zhang, Ziyao Xu, Hangning Zhou, and Chi Zhang
• 机构: Washington University, Xi’an Jiaotong University, Megvii Inc.
• 笔者整理了一个最近几年150多篇点云的论文列表，欢迎大家一块学习交流。

0.0 摘要

论文中提出了一种新的基于学习的用于具有部分重叠(partially overlapping)3D点云配准的流程(pipeline)。该模型包括一个迭代的距离感知相似度矩阵卷积(iterative distance-aware similarity matrix convolution, IDAM)模块，将特征和欧几里得空间的信息整合到点对(pairwise point)的匹配过程中。而且，作者提出了一个两阶段的可学习的点消除技术，以提高计算效率和减少假阳性的对应对(correspondence pairs)。作者提出了一种新的互监督损失模型，在不增加关键点注释的情况下对模型进行训练。整个流程可以很容易地与传统特征(如FPFH)或者基于学习的特征进行集成。在部分重叠和具有具有噪声点的点云数据上的配准实验，表明该方法在提高计算效率的同时，优于现有的配准技术。

一、论文的出发点和贡献

点云配准是计算机视觉中的一项重要任务，它的目的是通过刚体变换将一个(源, source)三维点云与另一个(目标, target)点云对齐。它在计算机视觉、增强现实和虚拟现实等领域有着广泛的应用，如位姿估计和三维重建。

经典的点云配准算法ICP对于初始位置较敏感，一些全局匹配的算法如Go-ICP, FGR等效率较慢，导致在实际应用中都存在问题。

近些年来，基于学习(数据驱动)的配准算法也被提出，如PointNetLK, DCP等算法，但这些算法仍旧有缺点，比如DCP假定源点云中的每个点在目标点云中都有对应(correspondence)关系。

因此，作者提出了迭代的距离感知相似度矩阵卷积网络(Iterative Distance-Aware Similarity Matrix Convolution Network, IDAM)，一种新的用于精确(accurate)、高效(efficient)点云配准的可学习的流程(pipeline)。

• 解决点特征和距离问题

  作者认为，在迭代匹配过程中，结合几何特征和距离特征可以解决模糊性问题，并且比使用其中任何一个都有更好的性能。对于距离，论文提出使用一个学习模块，基于两个点的特征来计算相似性分数(similarity score)。

• 提升配准效率

  为了降低计算复杂度，论文提出了一种新的two-stage的点消除(point elimination)技术，来平衡性能和效率。第一个stage, hard point消除，独立的过滤掉大部分不太可能是匹配点的点; 第二个stage，混合点(hybrid point)消除，消除对应对(correspondence pair)，降低很可能是假阳性对应对(correspondece pair)的权重。

• 提出互监督损失(mutual-supervision loss)

  作者设计了一种新的互监督损失来训练这些点消除模块(point elimination modules)。这种损失使得模型可以进行端到端的训练，而不需要额外的关键点标注。

二、论文的方法

源(source)点云记为 S S S，具有 N S N_S NS​个点; 目标点云记为 T T T，具有 N T N_T NT​个点。 p i ∈ S p_i \in S pi​∈S表示源点云 S S S的第 i i i个点， q j ∈ T q_j \in T qj​∈T表示目标点云 T T T的第 j j j个点。 R ∗ R^* R∗和 t ∗ t^* t∗表示源点云 S S S到目标点云 T T T的真实(Ground Truth)变换(旋转矩阵和平移向量)。

2.1 点对应关系

给定 p i ∈ S p_i \in S pi​∈S的几何特征为 u S ( i ) ∈ R K u^S(i) \in \mathbb R^K uS(i)∈RK， q j ∈ T q_j \in T qj​∈T的几何特征为 u T ( j ) ∈ R K u^T(j) \in \mathbb R^K uT(j)∈RK，论文中将第n次迭代的距离增强特征张量(distance-augmented feature tensor)表示为:

T ( n ) = [ u S ( i ) ; u T ( j ) ; ∣ ∣ p i − q j ∣ ∣ ; p i − q j ∣ ∣ p i − q j ∣ ∣ ] T^{(n)} = [u^S(i); u^T(j); ||p_i - q_j||; \frac{p_i - q_j}{||p_i - q_j||}] T(n)=[uS(i);uT(j);∣∣pi​−qj​∣∣;∣∣pi​−qj​∣∣pi​−qj​​]

[ ⋅ ; ⋅ ] [\cdot ; \cdot] [⋅;⋅]表示concatenation。 T ( n ) ( i , j ) T^{(n)}(i, j) T(n)(i,j)是一个(2K+4)维的向量，表示 p i p_i pi​和 q j q_j qj​几何特征和欧几里得特征的组合。这样就构造了一个 ( N S , N T , 2 K + 4 ) (N_S, N_T, 2K+4) (NS​,NT​,2K+4)的张量(distance-augmented feature tensor)。接下来，对每一个位置 ( i , j ) (i, j) (i,j)处的特征，进行多次MLP(2K+4, 32, 32, 32, 32, 1)生成(N_S, N_T)的特征，并在最后一个维度上经过softmax操作 S ( n ) S^{(n)} S(n)，生成相似度矩阵(similarity matrix)。 S ( n ) ( i , j ) S^{(n)}(i, j) S(n)(i,j)表示 q j q_j qj​是 p i p_i pi​对应点的概率。通过在 S ( n ) S^{(n)} S(n)的每一行上寻找arg max，可以构造对应对(correspondence pairs) { ( p i , p i ′ ) ∣ ∀ p i ∈ S } \lbrace (p_i, p_i') | \forall p_i \in S \rbrace {(pi​,pi′​)∣∀pi​∈S}，接下来通过SVD方法求解R, t。

但有两个地方需要注意:

• IDAM是一个迭代算法，在第n次迭代时求解的R, t，将作用于第i次源点云，作为第i+1次的迭代，几何特征不变，只改变了距离特征；最终求解的R, t是n次迭代求解 R ( n ) , t ( n ) R^{(n)}, t^{(n)} R(n),t(n)的组合。
• 效率问题: 在产生相似度矩阵时，利用了 ( N S , N T , 2 K + 4 ) (N_S, N_T, 2K+4) (NS​,NT​,2K+4)的张量， N S , N T N_S, N_T NS​,NT​一般会超过1000，计算量是庞大的。为了提升效率，作者提出了2阶段点消除(two-stage point elimination)流程: 包括hard point消除(elimination)和混合点消除(hybrid point elimination)，分别被用来提高效率和精度。

2.2 hard point 消除

为了减少相似度矩阵卷积的负担，作者首先提出了hard point 消除。设输入点云的数量是N，hard point消除的结果是保存M个点，M = N // 6。此过程在训练集和测试集的处理流程是不一样的。

• 测试集

  在测试集hard point的消除如Fig. 2(left)所示，输入点集特征 F ∈ R N × C F \in \mathbb R^{N \times C} F∈RN×C，对每个点进行参数共享的MLP(C, 64, 64, 1)，得到每个点的重要性得分significance score，选择Top K 个点进入到下一阶段。对于源点云 S S S和目标点云 T T T，经过hard point 消除后的点云，分别记为 B S B_S BS​和 B T B_T BT​。

• 训练集

  首先，在源点云中定义S正样本和负样本。

  p pos ( i ) = 1 [ min ⁡ q ∈ T ∣ ∣ R ∗ p i + t ∗ − q ∣ ∣ 2 ≤ r 2 ] + ϵ p_{\text{pos}}(i) = 1[\min_{q \in T} ||R^*p_i + t^* - q||^2 \leq r^2] + \epsilon ppos​(i)=1[q∈Tmin​∣∣R∗pi​+t∗−q∣∣2≤r2]+ϵ
  p neg ( i ) = 1 [ min ⁡ q ∈ T ∣ ∣ R ∗ p i + t ∗ − q ∣ ∣ 2 > r 2 ] + ϵ p_{\text{neg}}(i) = 1[\min_{q \in T} ||R^*p_i + t^* - q||^2 > r^2] + \epsilon pneg​(i)=1[q∈Tmin​∣∣R∗pi​+t∗−q∣∣2>r2]+ϵ

  ϵ = 1 0 − 6 \epsilon = 10^{-6} ϵ=10−6是某个比较小的数。在训练时，对于源点云选择 M//2个正样本，选择N//2个负样本，形成了大小是M的集合 B S B_S BS​。对于目标的点云，作者选择距离 B S B_S BS​最近的点:

  B T = { arg ⁡ min ⁡ q ∣ ∣ R ∗ p i + t ∗ − q ∣ ∣ ∣ i ∈ B S } B_T = \lbrace \arg \min_{q}||R^*p_i + t^* - q|| | i \in B_S\rbrace BT​={argqmin​∣∣R∗pi​+t∗−q∣∣∣i∈BS​}

2.3 混合点消除

虽然hard point 消除显著提高了效率，但对模型的性能有负面影响，比如，目标点云中的对应点可能被消除，对于局部overlap的点云组也会出现这样的找不到对应点的情况，这些"negative point pairs"可以使得输出的R, t不精确。因此，作者提出了混合点消除(hybrid point elimination)。混合点消除模块是在相似度矩阵模块后面的，它不同于hard point 消除，混合消除模块是作用于点对(point pairs)的。

设相似度矩阵为F，其维度为M x M x K’，混合点消除模块首先计算它的有效性分数:

v ( i ) = σ ( f ( ⨁ j ( F ( i , j ) ) ) ) v(i) = \sigma(f(\bigoplus_j(F(i, j)))) v(i)=σ(f(j⨁​(F(i,j))))

σ ( ⋅ ) \sigma (\cdot) σ(⋅)是sigmoid函数， ⨁ \bigoplus ⨁是池化方法(均值或最大值)， f f f是一个多层感知机(32, 32, 1)，混合点消除模块的结果如Fig2.(right)所示。这样就有了源点云中每个点的有效性分数，也就是每个点对的有效性分数。

有了这个有效性得分，我们然后可以计算混合消除的权重，第 i i i个点对的权重为:

w i = v ( i ) ⋅ 1 [ v ( i ) ] ≥ median k ( v ( k ) ) ] Σ i v ( i ) ⋅ 1 [ v ( i ) ] ≥ median k ( v ( k ) ) ] w_i = \frac{v(i) \cdot 1 [v(i)] \geq \text{median}_k(v(k))]}{\Sigma_i v(i) \cdot 1 [v(i)] \geq \text{median}_k(v(k))]} wi​=Σi​v(i)⋅1[v(i)]≥mediank​(v(k))]v(i)⋅1[v(i)]≥mediank​(v(k))]​

这个加权过程的作用是，给那些有效性得分小于均值的点对赋予0权重(hard elimination)，其余的与有效性得分成比例的加权(soft elimination)。接下来通过SVD求解一个加权的优化函数，来获得R, t:

R , t = arg ⁡ min ⁡ R , t Σ i w i ∣ ∣ R p i + t − p i ′ ∣ ∣ R, t = \arg \min_{R, t}\Sigma_iw_i||Rp_i + t - p_i'|| R,t=argR,tmin​Σi​wi​∣∣Rpi​+t−pi′​∣∣

2.4 整体框架

在了解了上述三个子模块之后，接下来看一下IDAM网络的整体架构，如Fig.1所示。网络的输入是N x 3的源点云S和M x 3的目标点云T，网络的输出是使得源点云和目标点云对齐的R, t。

1. 首先，源点云S和目标点云T分别经过一个特征提取模块(GNN或FPFH)，分别得到 N x K 和 M x k 的特征。
2. 通过 hard point 消除模块，从S和T中采样得到M个点集
3. 生成相似度矩阵，维度为(M, M, 32)，从而得到相似度分数S，来构成对应点(correspondence points)关系
4. 混合点消除模块，生成每个点对的有效性分数，从而得到每个点对的权重 w i w_i wi​
5. 利用加权SVD求解R, t
6. 迭代3, 4, 5。

2.5 损失函数

有了网络架构，也知道了网络的输入和输出，那么损失函数是什么呢，论文中的损失函数主要包括3个:

• 负熵损失(Negative Entropy Loss)

  此损失用于训练hard point消除，因为没有关键点标注的直接信息，作者提出使用互监督(mutual supervision)技巧来监督hard point消除。

  L hard ( S , T , R ∗ , t ∗ ) = 1 M Σ i = 1 M ∣ s ( i ) − Σ j = 1 M S ( i , j ) log S ( i , j ) ∣ L_{\text{hard}}(S, T, R^*, t^*) = \frac{1}{M}\Sigma_{i=1}^M|s(i) - \Sigma_{j=1}^MS(i, j)\text{log}S(i, j)| Lhard​(S,T,R∗,t∗)=M1​Σi=1M​∣s(i)−Σj=1M​S(i,j)logS(i,j)∣

  s ( i ) s(i) s(i)是点云中第 i i i个点的重要性，而负熵看做重要性的监督信息。对于源点云和目标点云都使用了负熵损失。而且，负熵损失在第一次迭代中被累加，因为作者认为，在配准的早期阶段，形状特征比欧几里得特征更重要，作者希望基于形状信息过滤掉hard point。

• 混合消除损失(Hybrid Elimination Loss)

  类似的互监督思想也可以用于混合点消除训练。

  L hybrid ( S , T , R ∗ , t ∗ ) = 1 M Σ i = 1 M − I i ⋅ l o g ( v ( i ) ) − ( 1 − I i ) l o g ( 1 − v ( i ) ) L_{\text{hybrid}}(S,T,R^*, t^*) = \frac{1}{M}\Sigma_{i=1}^M-I_i \cdot log(v(i)) - (1 - I_i)log(1-v(i)) Lhybrid​(S,T,R∗,t∗)=M1​Σi=1M​−Ii​⋅log(v(i))−(1−Ii​)log(1−v(i))

  其中 I i = 1 ∣ ∣ R ∗ p i + t ∗ − q arg ⁡ max ⁡ j S ( i , j ) ∣ ∣ 2 ≤ r 2 I_i = 1||R^*p_i + t^* - q_{\arg \max_jS(i, j)}||^2 \leq r^2 Ii​=1∣∣R∗pi​+t∗−qargmaxj​S(i,j)​∣∣2≤r2

  这种损失为 B S B_S BS​中找到正确匹配的点分配一个正标签1，否则分配一个负标签0。

• 点匹配损失(Point Matching Loss)

  点匹配损失用来监督相似度矩阵的卷积。它是一个标准的交叉熵损失。

  L match ( S , T , R ∗ , t ∗ ) = 1 M Σ i = 1 M − log ( S ( i , j ∗ ) ) ⋅ 1 [ ∣ ∣ R ∗ p i + t ∗ − q j ∗ ∣ ∣ 2 ≤ r 2 ] L_{\text{match}}(S, T, R^*, t^*) = \frac{1}{M}\Sigma_{i=1}^M-\text{log}(S(i, j^*)) \cdot 1[||R^*p_i + t^* - q_{j^*}||^2 \leq r^2] Lmatch​(S,T,R∗,t∗)=M1​Σi=1M​−log(S(i,j∗))⋅1[∣∣R∗pi​+t∗−qj∗​∣∣2≤r2]

  其中， j ∗ = arg ⁡ min ⁡ 1 ≤ j ≤ M ∣ ∣ R ∗ p i + t ∗ − q j ∣ ∣ 2 j^* = \arg \min_{1 \leq j \leq M}||R^*p_i + t^* - q_j||^2 j∗=argmin1≤j≤M​∣∣R∗pi​+t∗−qj​∣∣2。如果 p i p_i pi​与 q j q_j qj​的距离大于 r r r，这就不能成为一个对应关系，也不会对他们施加监督信息。

代码中的3个loss的实现还是很巧妙的，一开始没有看懂(以为代码写错了)，后来才发现作者利用srg和gt的产生方式，src和gt是一一对应的。

三、论文的实验

作者在实验部分使用了ModelNet40数据集(9843训练集, 2648测试集)。

对于一个原始点云，作者随机采样1024个点作为源点云S，随机产生一个旋转[0, 45°]和平移[-0.5, 0.5]作用于源点云，产生目标点云T。对于局部重叠(partially overlap)的点云，作者采用PRNet中的方法: 固定一个距离这源点云和目标点云都很远的点A，对于这两个点云均采样距离点A最近的768个点。

评估指标和DCP、PRNet一样，RMSE®, MAE®, RMSE(t)和MAE(t)。

作者展示了三个不同实验的结果，来证明提出方法的有效性和鲁棒性。

3.1 Unseen Shapes

作者在训练集上训练，在测试集上测试，训练集和测试集均包括40类样本。实验结果如Table 1所示，局部匹配ICP算法较差(因为初始旋转角度较大)；FPFH + RANSAC是传统算法中最好的，和许多基于学习的方法相当；作者的方法FPFH + IDAM 或 GNN + IDAM 均好于其它的方法，而且令人惊讶的是FPFH + IDAM的效果好于GNN + IDAM 的结果。作者认为是GNN在训练集上过拟合了，在测试集上泛化的没有那么好。下面的实验中，作者也证明了GNN + IDAM对噪声也更加鲁棒，并且比FPFH + IDAM更加高效。

重复上述实验，在数据集中增加随机高斯噪声，传统的方法和FPFH + IDAM算法比在无噪声的数据上性能低了很多。这说明了FPFH对噪声特别不敏感。由于强大的特征提取网络，数据驱动方法的性能与无噪声时相当。与其他方法相比，论文中基于GNN的方法具有最好的性能。

3.2 Unseen Categories

作者在前20类数据集上进行训练，在后20类数据上进行评估，实验结果如Table 2所示。从Table 2可以看到，没有在测试集的类别上进行训练，所有基于学习的方法一致表现得较差。基于不同的评估指标，FPFH + RANSAC 和 FPFH + IDAM是性能最好的办法。

3.3 Efficiency

作者对配准的速度进行了评估，分别评估1024， 2048和4096个点，实验结果如Table 4所示，可以看到基于学习的方法普遍比传统方法快。当点的数量较少时，GNN + IDAM方法只慢于DCP，但随着点的数量增多， GNN + IDAM方法明显快于其它方法。

3.4 Ablation Study

作者研究了模型的三个关键组成部分的有效性：距离感知相似度矩阵卷积(distance-aware similarity matrix convolution, SM),hard point 消除(elimination, HA)和混合点消除(Hybrid point elimination, HB)。作者使用BS表示不包括上述三个模块的基于GNN的模型，采用了Unseen Category的方式进行了评估，实验结果如Table 5所示。可以看到，即使在随机抽样的情况下，相似度矩阵的性能已经远远超过BS。两阶段点消除进一步提升了网络的性能。

四、对论文的想法

最早看到这个论文题目的时候，被题目吓到了，迟迟没有阅读。这两天读了一下这篇文章，发现文章还是很好懂的，开源的代码也很简洁，结合代码可以很清楚地理解论文中的模型。

• 跑了一下Unseen Shapes的结果，如下图所示。在第9个epoch的时候，实验性能已经高于了论文中的结果， 另外当迭代次数增加到30时，在测试集的性能明显低于训练集，且低于论文中的结果，应该是过拟合了。

• 优点:
  • Loss: 互监督学习
  • 提取特征GNN或FPFH
• 缺点:
  • 实验不充分，只在ModelNet40简易数据集上进行了实验，在真实数据集上的效果待验证。