机器学习中的图匹配问题

机器学习中的图匹配问题—基础学习

机器学习中的图匹配问题

结合导师所给的方向，能否将实例之间的点匹配问题转换为点到实例之间的匹配问题来进行求解呢？这里结合师姐推荐的讲座首先对图匹配的这个方向来进行简单的了解和接触。

图匹配问题概述

图匹配就是：不仅考虑点之间的配准，还考虑边之间的配准 registration。

这里在匹配的时候不仅要考虑到两个点之间的相似度，还要考虑到两个点之间边的一个相似度，从而就可以构成图结构，从而引入了图匹配的问题。

在这里插入图片描述
如上，匹配两个图，一个图有5个点，一个图有4个点，我们要做的就是求解出一个5×4的0-1矩阵（组合优化问题），得到点与点间的匹配关系。

一个很直接的求解方法是：计算点与点之间的相似度，构造Kp矩阵，然后求解这个规划模型。

这里涉及了多目标跟踪领域的一个很常见的二部图关联算法—匈牙利算法， 这里的匹配问题是之前常用的线性指派的问题。 通过计算点和点之间的相似度或者匹配的代价矩阵，来完成相关的一个匹配的问题。

在这里插入图片描述

图匹配问题的难点

这个问题的难点在于，我们不仅仅要考虑点与点之间的相似性，还要考虑边与边之间的相似性。

从而从一个一阶的匹配问题转化为了一个二阶的问题就导致了整个的难度的上升也就出现了图匹配的一个难点问题。

在这里插入图片描述

这里对于边匹配的问题来说，第一个图上有8条边第二个图上有4条边，这里对于的边的矩阵就是8x4的一个规模了。

节点之间的匹配矩阵是一阶的复杂度，因为它只涉及到两个图中节点的两两匹配，而边之间的匹配矩阵是二阶的复杂度，因为它涉及到两个图中所有可能的边对之间的匹配。

在这里插入图片描述
这里自己感觉和GmTracker所说的图匹配中的一个凸二次规划问题是一个意思。可以看到边的数量明显上升。

在这里插入图片描述

之后的图匹配的问题通过引入了affinity matrix矩阵来进一步进行优化求解。

我们可以对点和边的关系进行编码，压缩成一个矩阵：affinity matrix(相似性矩阵) 如上，对于5点对4点的情况，我们需要5乘4等于20规模的方阵，这样就可以两两编码（1a、1b、…、5d，共20个）。如上，3b行与5c列的交点意味着：3和5连成的边与b和c连成的边的相似度。但是这样K矩阵比较稀疏。

有了这个矩阵，我们将其转换为QAP。

在这里插入图片描述
二次分配问题（Quadratic Assignment Problem，简称 QAP）是一种组合优化问题，它涉及将设施分配到位置的最优方案。QAP 的目标是找到最佳分配，以最小化设施对之间的总成本或距离，同时考虑到它们之间的相互作用以及对应位置之间的距离。

在这里插入图片描述
然后我们对这里的公式图来进行一个简单的解释说明。我们在建立完成上文提到的K矩阵的基础上，需要求解的就是X这样一个匹配矩阵。来确定之间的匹配关系，本质上是让求解出来的值最大。

有人证明了这是一个NP难的问题。如上，转化为一个二次问题。注意到，vec 是向量化的意思，就是把 X5×4 转化为 X20×1 这是一个NP-hard问题。

图匹配问题的求解

对于这个NP难的问题该如何进行求解呢？松弛是一个好办法

大部分以前的方法都是通过松弛的方法来进行求解。将约束的问题转化成为一个关于模的问题来进行求解。通过求一些特征值和特征向量的形式来进行完成的。

在这里插入图片描述

考虑高阶的信息在CV领域，3阶代表相似变换的不变性，4阶代表仿射变换的不变性。因此，是否可以将 graph 变为超图（提高阶数）？

但是，这不可行，维度爆炸。

在这里插入图片描述
总结：在传统的机器学习的方法中最常用的两种关于图匹配的形式主要是，通过凸优化松弛的方式，或者说通过矩阵分解的方式来进行求解的。

Existing multiple GM methods

然而，在实际问题中，不仅仅是两张图的匹配，我们需要提取信息，并且能做到，多张图协同匹配。Composition based Affinity Optimization

在这里插入图片描述

这里涉及的多是多图的匹配，自己目前用不上简单了解

有一种思想是，如果G1和G2匹配很难，是否可以通过G3作为中介（比如儿子于父母），分别与G1和G2匹配。
在多图中，我们提出 consistency 的概念，注意，对于i和j，我们引入第三者第四者等等，用于计算 consistency ，这个值越高越接近1，则匹配效果越好。

Background: Learning on Graph Matching

这里根据讲座中的信息建立并且了解可学习的图匹配的相关的背景信息，（机器学习，深度学习相关）

在这里插入图片描述
通过学习的方法建立图匹配的过程是 : 给定两个图之后由机器训练出来的模型来自动的学习出不同的权重从而构建出一个新的图的信息。

这里刚开始节点和边的权重都被初始化为1 这里在图匹配中的pai代表的是它们之间的对应关系。

$S\left(\mathcal{G}, \mathcal{G}^{\prime}, \pi ; \omega\right)=\left\langle\omega, \Phi\left(\mathcal{G}, \mathcal{G}^{\prime}, \pi\right)\right\rangle$

$g_{\omega}\left(\mathcal{G}, \mathcal{G}^{\prime}\right)=\underset{\pi}{\operatorname{argmax}} S\left(\mathcal{G}, \mathcal{G}^{\prime}, \pi ; \omega\right)$

通过引入一个可学习的参数，让我们的图之间对应关系的匹配可以达到最大。

$\begin{aligned} g\left(\mathcal{G}, \mathcal{G}^{\prime}\right) & =\underset{\pi}{\operatorname{argmax}} S\left(\mathcal{G}, \mathcal{G}^{\prime}, \pi ; \mathbf{1}\right) \\ & =\underset{\pi}{\operatorname{argmax}} \sum_{i} \boldsymbol{s}_{V}\left(a_{i}, a_{\pi(i)}^{\prime}\right)+\sum_{i, j^{\circ}} \boldsymbol{s}_{E}\left(a_{i j}, a_{\pi(i) \pi(j)}^{\prime}\right) \end{aligned}$