图匹配经典论文（三）Deep Learning of Graph Matching—CVPR2018图匹配

图匹配经典论文（三）Deep Learning of Graph Matching—CVPR2018图匹配

在学习这篇论文之前，因为上次的组会没细讲因此又重新的将之前学过的图匹配的经典论文（综述性质）的复习了一下其中的基本的流程。自己数学基础一般，推导只能稍稍理解一点

在学习完师兄推荐的图匹配经典论文系列12的基础上，在学习一下cvpr的最佳论文师姐推荐的（掌握一下可学习的图匹配的过程。之后在理论基础上有机会打算重新看一遍GMTracker）慢慢尝试入门一下图匹配作于在多目标跟踪的领域。为写第一篇论文的工作做个铺垫。 也是为了方便简单看看师兄的论文。

自己看完之后只能说自己不是纯搞数学的，只能大题理解一下流程，原理论文讲了什么。深究实力不太够所以尽量写清楚一下流程，可以为后面看一些图匹配网络的简单公式有一定理论基础。

就像看完综述文章之后，看这一篇的简单概念就可以完全理解了

摘要概括

CVPR2018最佳论文提名的工作Deep Learning of Graph Matching首次将端到端的深度学习技术引入图匹配，提出了全新的深度图匹配框架。

我们提出了一种端到端模型，可以学习图匹配过程的所有参数，包括一元和成对节点邻域，表示为深度特征提取层次结构。

相比于只考虑节点与节点之间一阶相似度关系的点匹配，图匹配还考虑了图结构中，边到边的二阶相似度，实际上，在图匹配算法中，任意一对顶点、任意一对边之间，都存在相应的相似度度量。由于额外考虑了图结构中的二阶相似度信息，图匹配通常比简单的一阶点匹配更加精确和鲁棒。

导言介绍

图匹配问题——在以局部节点结构和成对关系表示的两个图之间建立对应关系，无论是视觉的、几何的还是拓扑的——在组合优化、机器学习、图像分析或计算机视觉等领域非常重要。

1. 图匹配使用亲和力矩阵（相似性矩阵进行操作，亲和矩阵对两个图中的一元和成对节点（点）集之间的相似性进行编码。

2. 通常，它在数学上被表述为二次规划问题（QAP），受到一对一映射约束，即第一组中的每个点必须在第二组中具有唯一的对应关系。 众所周知，这是 NP-hard问题，因此通常通过放宽约束并寻找局部最优来近似解决它

3. 最近，人们对使用深度特征进行几何和语义视觉匹配任务越来越感兴趣，要么通过训练网络直接优化匹配目标，要么使用预先训练的深度特征在已建立的匹配架构中，都取得了相当大的成功。

本文首次提出一种基于深度学习的图匹配方法（GMN），提出了从特征提取，仿射矩阵构建，幂迭代，双随机矩阵生成，投票法到损失计算的完整可微分的图匹配流程，并给出了相应的反向传播的导数计算方法。

过去的计算机视觉图匹配研究工作，研究者们大多使用SIFT等描述子或是手工定义的特征。这些人为构建的特征容易受样本噪声的影响，研究者们往往忽视了机器学习尤其是深度学习在图匹配问题上的巨大潜力。这篇工作将深度学习与图匹配结合，使用卷积神经网络CNN提取图像特征，同时学习构建相似度的匹配函数，通过反向梯度传播以及标准的深度学习梯度优化算法，实现端到端的训练。

问题表述—数学表达

基本形式

在这一部分主要解释一下，其中的公式符号，和推导公式论文给出的一些理论基础。

1. 输入图一，图二：图1有n个顶点V. 图二有m个顶点V。

$${\mathcal{G}}_1=\left(V_1,E_1\right)$$

$${\mathcal{G}}_2=\left(V_2,E_2\right),\text{ with }\left|V_1\right|=n\text{ and }\left|V_2\right|=m$$

2. 我们的目标是在两个图的节点之间建立分配以便优化相应节点和边的标准

图匹配相关部分

1. 定义一个指示向量，也就是将连接关系矩阵展开为向量得到的形式。

 Let  v ∈ { 0 , 1 } n m × 1 \text { Let } \mathbf{v} \in\{0,1\}^{n m \times 1}  Let v∈{0,1}nm×1

2. 如果 i ∈ V1 与 a ∈ V2 匹配，则 via = 1，否则为 0，同时遵守一对一映射约束

$${\mathbf{v}}_{ia}=1$$

3. 我们构建一个方形对称正矩阵 M ∈ Rnm×nm，使得 Mia;jb 测量每对 (i, j) ∈ E1 与 (a, b) ε E2 的匹配程度。 对于不形成边的对，它们在矩阵中的相应条目设置为 0。

这里的M就是因式分解图匹配综述里面的那个12x12的矩阵。主对角线代表节点相似度，其他不为零的代表的是(i,j)和(a,b)的匹配的置信度

$$\mathbf{M}\in {\mathbb{R}}^{nm\times nm}，{\mathbf{M}}_{ia;jb}$$

对角线条目包含节点到节点分数，而非对角线条目包含边到边分数。

4. 最优分配 v* 可以表示为（v这里就代表的是综述文章中的置换矩阵）

v ∗ = argmax ⁡ v v ⊤ M v , s.t.  C v = 1 , v ∈ { 0 , 1 } n m × 1 \mathbf{v}^{*}=\underset{\mathbf{v}}{\operatorname{argmax}} \mathbf{v}^{\top} \mathbf{M v} \text {, s.t. } \mathbf{C v}=\mathbf{1}, \mathbf{v} \in\{0,1\}^{n m \times 1} v∗=vargmax​v⊤Mv, s.t. Cv=1,v∈{0,1}nm×1

• 二元矩阵 C ∈ Rnm×nm 编码一对一映射约束
• 每一行和每一列都只有一个分配。（两个约束条件）

$$\forall a\sum _i{\mathbf{v}}_{ia}=1\text{ and }\forall i\sum _a{\mathbf{v}}_{ia}=1$$

5. 已知是 NP 难的，因此我们通过删除二进制和映射约束来松弛问题，并求解（通过最大特征值的形式来进行求解）

$${\mathbf{v}}^{\ast }=\underset{\mathbf{v}}{\mathrm{argmax}}{\mathbf{v}}^{\top }\mathbf{Mv},\text{ s.t. }\Vert \mathbf{v}{\Vert }_2=1$$

应该就是对应后面的双随机矩阵进行松弛求解的。

然后，最优 v* 由矩阵 M 的前导特征向量给出。由于 M 具有非负元素，通过使用 Perron-Frobenius 参数，v* 的元素位于区间 [0, 1] 中，我们将 v 解释为 * ia 为 i 与 a 匹配的置信度。

补充

1. 主要挑战是通过亲和力矩阵 M 的分解来传播损失函数的导数，然后进行匹配。

2. （在我们的公式中，这是一个优化问题，使用特征分解来解决），最后是用于计算一元和成对点表示的完整特征提取层次结构

3. 构建了一个端到端的深度网络，该网络集成了一个特征提取组件，该组件输出构建矩阵 M 所需的描述符 F。

这里的描述符可以简单的理解成U F是提取出来的节点和边的特征向量的信息。

4. 我们解决分配问题（2）并计算解 v* 和真实值之间的匹配损失 L(v*)要求每一层就是可微的，论文中在每一个部分都给出了严格的证明。

$$\partial \mathbf{L}/\partial \mathbf{M}\text{ and }\partial \mathbf{L}/\partial \mathbf{F}$$

其中 “：”表示矩阵的内积（对应元素相乘）。（4）式表示函数的偏导数

实现过程

首先，输入两幅图像I 1 , I 2 使用CNN，如VGG-16，分别对图像进行特征提取，其中relu5-1层输出的特征向量F 作为边特征，r e l u 4 2层输出的特征向量U 作为节点特征。如果图像带有标记好的关键点则直接采用关键点进行构图，否则通过均匀采样的方式进行关键点提取。得到两幅图对应的关键点集后，对于图像I1采用Delaunay三角剖分的方式构建图G 1，图像I 2 采用全连接方式构建图G完成图构建后，可以得到邻接矩阵A 1，A 2，为方便后续采用因式分解图匹配的形式，将邻接矩阵转化成节点-边指示矩阵(node-edge incidence matrix)的形式G 1 , G 2 , H 1 , H 2 然后计算关联矩阵M。

整个网络流程的总结：按照顺序介绍下面的图

1. （预处理）：将上文提到的数据集（比如鸟：①姿态一致②两图15个关键点）通过vgg16提取特征。一阶特征代表点的特征信息，二阶特征代表边的特征信息，分别使用浅层的relu4_2激活信息和relu5_1的激活信息，分别记作F和U，下图的U，F的上标表示两个图。输入二个图，输出F，U

2. 输入的F，U构建二个图的相似度矩阵。输入上一层的F，U，输出相似度矩阵M

3. 输入M，输出v*。主要求解相似度矩阵的最大特征向量，当作近似的图匹配的解。

4. 输入v*，输出排列阵S。主要将排列阵按行、列 归一化，归一化成双随机矩阵

5. 对排列阵S，按概率选择每一个点对应的匹配结果

6. 求loss，并反向传播

Affinity Matrix Factorization（亲和力矩阵的分解）

这里的深度图匹配的计算思想也是同样的参考了之前看的那篇综述文章

$$\mathbf{M}=\left[\mathrm{vec}\left({\mathbf{M}}_p\right)\right]+\left({\mathbf{G}}_2\otimes {\mathbf{G}}_1\right)\left[\mathrm{vec}\left({\mathbf{M}}_e\right)\right]{\left({\mathbf{H}}_2\otimes {\mathbf{H}}_1\right)}^{\top }$$

• 其中 [x] 表示对角矩阵，x 在主对角线上，⊗ 是克罗内克积。

• Mp ∈ Rn×m 表示一元项，测量节点到节点的相似度，而 Me ∈ Rp×q 测量边到边的相似度； p, q 是每个图中的边数。

• 为了描述每个图的结构，将节点边关联矩阵定义为 G,H ∈ {0, 1}n×p

这里的G H和综述中的GH的含义是相同的。其中，如果第 c 条边从第 i 个节点开始并在第 j 个节点结束，则 gic = hjc = 1。

2. 构建 Me 和 Mp 的一种简单方法是：

• 构建相似度矩阵: 论文中使用了深度学习提取的特征向量，基于人工指定的图结构，构建图匹配的相似度矩阵。其中，一阶相似度矩阵直接由一阶特征点乘得到

$${\mathbf{M}}_p={\mathbf{U}}^1{\mathbf{U}}^{2\top }$$

为获得二阶相似度，首先将每条边对应的两个节点的连接，构建两个图的二阶特征矩阵（特征维度1024）

$${\mathbf{X}}_c=\left[{\mathbf{F}}_i^1\mid {\mathbf{F}}_j^1\right],{\mathbf{Y}}_c=\left[{\mathbf{F}}_i^2\mid {\mathbf{F}}_j^2\right]$$

将连接得到的X和Y参与计算就可以得到边相似度的一个矩阵了。

$${\mathbf{M}}_e=\mathbf{X\Lambda }{\mathbf{Y}}^{\top }$$

这是是要训练的对象。

Affinity matrix layer（亲和力矩阵层）

在这一个部分引入的A1和A2矩阵在综述文章的分解部分也是提到过的。(通过邻接矩阵比通过节点边关联矩阵更容易描述图的连通性)。

定义节点到节点的邻接矩阵 A1 ∈ {0, 1}n×n,A2 ∈ {0, 1}m×m

$${\mathbf{A}}_1={\mathbf{G}}_1{\mathbf{H}}_1^{\top },{\mathbf{A}}_2={\mathbf{G}}_2{\mathbf{H}}_2^{\top }$$

亲和矩阵层接收所需的特征层次结构作为输入，以及用于重建最佳 G1,H1,G2,H2 矩阵的邻接矩阵 A1 和 A2.

Forward pass-该层前向传播的一个流程。

1. 根据构造出来的图结构得到A1和A2，根据A1 A2根据下面的公式得到 G1 H1 G2 H2

2. 根据提取出来的边特征 F1 和 F2构建X和Y结合上面的公式。

3. 计算得到边的ME分解的相似度矩阵’

4. 根据提取的节点特征U1和U2得到节点的矩阵 MP

5. 根据分解合并公式得到最后的M亲和力矩阵

同时它通过下面的两个公式证明了该层是可微的可以进行反向传播。

Power Iteration Layer—幂迭代层

通过幂迭代层求解图匹配问题，也就是通过幂迭代的方法得到闭式解V（也就是之前提到的置换矩阵）

1. 计算亲和力矩阵 M 的前导特征向量 v* 可以使用幂迭代来完成。

$${\mathbf{v}}_{k+1}=\frac{\mathbf{M}{\mathbf{v}}_k}{\Vert \mathbf{M}{\mathbf{v}}_k\Vert }$$

2. 其中M为上文的相似度矩阵，为了使上式最大化，可使用M的最大特征向量来近似，所以这层先使用幂迭代方法，求出M的最大特征向量。（通过闭式解方法）

$${\mathbf{v}}^{\ast }=\underset{\mathbf{v}}{\mathrm{argmax}}{\mathbf{v}}^{\top }\mathbf{Mv},\text{ s.t. }\Vert \mathbf{v}{\Vert }_2=1$$

$${\mathbf{v}}_{k+1}=\frac{\mathbf{M}{\mathbf{v}}_k}{\Vert {\mathbf{Mv}}_k\Vert }$$

分配运行 N 次迭代，并输出向量 v* = vN

查阅相关的资料给出幂迭代方法的简单介绍

图匹配的求解可以近似为求解相似度矩阵最大特征值所对应的特征向量（即leading eigenvector，以下简称最大特征向量）。幂迭代（Power Iteration）即是一种求解最大特征向量的迭代算法。初始化V0=1，通过不断迭代，Vk收敛到矩阵M的最大特征向量

这时候就得到了一个解然后在对这个解来进行处理。

最后证明了这一层的反向传播也是成立的，也就是该层是可微的。

并且可以得到简化的形式。

Bi-Stochastic Layer（双随机层）

松弛为双随机矩阵的原因：经过证明双随机矩阵可以显著的提高性能。

$$\forall a,\sum _i{\mathbf{v}}_{ia}=1$$

$$\forall i,\sum _a{\mathbf{v}}_{ia}=1$$

这层就是将上一层输入的vk向量变成双随机矩阵。分别进行行、列的归一化。

双随机矩阵的定义如下：对于一个方阵X∈[0,1]n x n，若其每行、每列的求和均为1，则该矩阵称为双随机矩阵。在图匹配问题中，使用双随机矩阵表示匹配结果，可以直观地体现任意一对节点建立匹配关系的可能性，所以图匹配问题经常约束其结果为双随机矩阵。由Power Iteration算法求解出的匹配结果不满足双随机性，因此需要将其进行双随机化。我们使用迭代算法将矩阵双随机化：首先将矩阵按列归一化，随后将矩阵按行归一化。通过不断迭代，即可得到双随机矩阵。该步骤的数学表示为：

$${\mathbf{S}}_0={\left({\mathbf{v}}^{\ast }\right)}_{n\times m}$$

经过多次迭代过程：

$${\mathbf{S}}_{k+1}={\mathbf{S}}_k{\left[1_n^{\top }{\mathbf{S}}_k\right]}^{-1},{\mathbf{S}}_{k+2}={\left[{\mathbf{S}}_{k+1}{1}_m\right]}^{-1}{\mathbf{S}}_{k+1}$$

最后就可以得到该层的输出双随机矩阵S

经过证明同样满足反向传播的条件。

Converting Confidence-maps to Displacements（将置信图转化为位移投票机制）

我们使用一个称为投票层的特殊层，将由 BiStochastic 层传递的置信图 S ∈ Rn×m 转换为距离向量。

输入时上一层的s双随机矩阵，所以只要选出概率最大的点就代表这两个点互相匹配，这里的loss函数就是计算匹配的点和真实点的物理位置。

设计基本按照softmax函数的思想而来

同一行、同一列的元素的值相差不大。为了使差异明显，并为后续计算损失函数提供方便，作者将上一步得到的双随机矩阵乘以一个大常数（论文中），随后进行softmax处理，得到每个候选节点匹配的“可能性”矩阵。投票步骤输出的矩阵，仍然满足双随机的性质。

$${\mathbf{d}}_i=\frac{\exp [\alpha \mathbf{S}(i,1\dots m)]}{{\sum }_j\exp [\alpha \mathbf{S}(i,j)]}\mathbf{P}-{\mathbf{P}}_i$$

使用数据集的标注信息，可以计算真实的偏移向量。随后，根据投票步骤获得的可能性矩阵，通过加权求和，可以得到模型预测的偏移向量。论文中采用了如下的损失函数，最小化模型预测的偏移向量与真实的偏移向量之间的差.

$$L(\mathbf{d})=\sum _i\varphi \left({\mathbf{d}}_i-{\mathbf{d}}_i^{gt}\right)$$

总结

之前写的图匹配经典论文系列（一）（二）—因式分解的图匹配问题。是师兄的推荐，这一篇Deep Learning of Graph Matching深度可学习的图匹配是师姐推荐的论文。是导师之前带毕业的师兄师姐做的创新型的工作。

然后通过这一段时间和师兄师姐的学术交流和师姐对师兄的评价，我感觉师兄师姐的合作以及学术精神和努力的程度，应该是我学习坚持的动力。

最后明天也是到了考研的时候了，也曾想起了去年的自己，我想说我自己应该要记得自己当时考研的目的。更要明白读研的过程中要改变自己，人相处的永远要是自己。