图匹配（Graph Matching）入门学习笔记——以《Factorized Graph Matching》为例（三）

本文主要介绍了与图匹配问题非常相似的点配准（Point Registration）问题，分析了二者之间的区别和联系。原文作者没有提点配准问题，而是用了ICP(Iterative Closest Point)的说法，但我个人认为ICP只是求解三维点配准的一种方法，使用点配准这个概念应该更加准确。最后介绍了如何将几何约束引入FGM中来求解可变形图（Deformable Graph）的匹配问题。

点配准与图匹配

  与图匹配问题类似，点配准问题是指给定两组点集$P_1=[p_1^1,p_2^1,...p_{n_1}^1]\in {\mathbb{R}}^{d\times n_1}$和$P_2=[p_1^2,p_2^2,...p_{n_2}^2]\in {\mathbb{R}}^{d\times n_2}$，点配准的目标就是寻找两个点集中点和点之间的对应匹配关系，并获得两个点集之间的几何变换关系。该目标是通过最小化两个点集中点和点之间的距离之和来实现的：
$$\underset{X\in \Pi ,\mathcal{T}\in \Psi }{\min }{J}_{icp}(X,\mathcal{T})=\sum _{i_1,i_2}{x}_{i_1{i}_2}\Vert p_{i_1}^1-\tau (p_{i_2}^2){\Vert }_2^2+\psi (\mathcal{T})(22)$$
X ∈ { 0 , 1 } n 1 × n 2 X\in\{0,1\}^{n_1\times n_2} X∈{0,1}n1​×n2​表示点和点之间的对应关系。在点配准问题中，点和点之间可以是一对一，也可以是多对一，本文只关注一对一的情况，也就是说$X$与图匹配中的要求一致，仍是一个置换矩阵。$\tau (\cdot )$是一个用参数$\mathcal{T}$描述的几何变换。$\psi (\cdot )$是一个用于约束变换参数$\mathcal{T}$的惩罚函数。由上式可以看到，点配准问题和图匹配问题相比，其优化目标都需要寻找点和点之间的对应关系，而不同之处在于点配准中两组点之间存在某种特定的几何变换关系，图匹配中没有这种约束条件。但图匹配除了关注点和点之间的匹配关系，还会关注边和边之间的匹配关系，这一点是点配准问题所不具备的。
  为了将点配准与图匹配问题联系起来，我们定义节点关联矩阵$K_p(\mathcal{T})\in {\mathbb{R}}^{n_1\times n_2}$，其中的每一个元素为$k_{i_1{i}_2}^p(\mathcal{T})=-\Vert p_{i_1}^1-\tau (p_{i_2}^2){\Vert }_2^2$，表示节点之间欧式距离的负值。则原目标函数（公式(21)）可以改写为$$J_{icp}(X,\mathcal{T})=-tr(K_p(\mathcal{T}{)}^{T}X)+\psi (\mathcal{T})(23)$$
给定变换参数$\mathcal{T}$，最小化上述目标函数就等价于最大化公式(7)中的节点相似度，这个优化问题可以看作是线性匹配问题。

因为只关注节点相似性，而不考虑边的相似性，所以是线性匹配问题

如果$X$是一对一的匹配，可用Hungarian算法求解，如果$X$是多对一的匹配，可采用赢家通吃策略求解。通常$X$和$\mathcal{T}$都是未知的，需要进行联合优化，该问题是一个非凸问题，无法求得闭式解。通常采用迭代的交替最小化算法进行求解，如EM算法。简单来说，就是固定$\mathcal{T}$，优化$X$；然后再固定$X$，优化$\mathcal{T}$，交替进行直至两者都收敛。

几何变换

  上文中提到，点配准中两组点之间存在特定的几何变换关系，下面简要介绍三种常见的变换：

1.相似变换（Similarity Transformation）

  给定一个点$p\in {\mathbb{R}}^2$或一个点集$P\in {\mathbb{R}}^{2\times n}$，相似变换的计算过程为$\tau (p)=sRp+t$或$\tau (P)=sRP+t{1}_n^T$，其中$s,R,t$分别表示放缩系数、旋转矩阵和平移向量。对旋转矩阵$R$有一个约束条件$\Psi$：$R$必须是单位正交阵，即 Ψ = { R ∣ R T R = I 2 , ∣ R ∣ = 1 } \Psi=\{R|R^TR=I_2, |R|=1\} Ψ={R∣RTR=I2​,∣R∣=1}

2.仿射变换（Affine Transformation）

  给定一个点$p\in {\mathbb{R}}^2$或一个点集$P\in {\mathbb{R}}^{2\times n}$，仿射变换的计算过程为$\tau (p)=Vp+t$或$\tau (P)=VP+t{1}_n^T$，其中$V\in {\mathbb{R}}^{2\times 2}$，$t\in {\mathbb{R}}^2$分别表示仿射矩阵和平移向量。

3.RBF非刚性变换（RBF Non-rigid Transformation）

  RBF非刚性变换的参数化取决于基点的选择，本文选择第二个点集中的点作为基点。给定一个点$p\in {\mathbb{R}}^2$或一个点集$P\in {\mathbb{R}}^{2\times n}$，RBF非刚性变换计算点与其初始位置之间的位移，$\tau (p)=p+W\varphi (p)$或$\tau (P)=P+W{L}_p$，其中$W\in {\mathbb{R}}^{2\times n_2}$表示权重矩阵，$\varphi (p)=[{\varphi }_1(p),{\varphi }_2(p),...{\varphi }_{n_2}(p){]}^T\in {\mathbb{R}}^{n_2}$表示与基点相对应的$n_2$个位移函数。${\varphi }_i(p)=exp(-\Vert p-p_i^2{\Vert }_2^2/{\sigma }_w^2)$表示点$p$和基点$p_i$之间的位移函数，${\sigma }_w$表示带宽。$L_p=[\varphi (P_1^2),\varphi (P_2^2),...\varphi (P_{n_2}^2){]}^T\in {\mathbb{R}}^{n_2\times n_2}$是定义在所有成对基点上的RBF核函数。本文对位移场的非光滑性进行正则化，即$\psi (\mathcal{T})=tr(W{L}_p{W}^T)$.

   上述变换关系整理如下表所示，关于更多有关几何变换的介绍我将单开一篇文章来介绍。

可变形图匹配

  图匹配是一种广泛应用于具备相似结构点集匹配的工具。但在很多计算机视觉任务中，匹配的两个点集之间需要满足一定的几何约束。目前尚不清楚如何将几何约束统一到图匹配的方法中。本文介绍了一种可变形图匹配（Deformable Graph Matching, DGM）方法能够将刚性和非刚性变换引入到图匹配中。

目标函数

  根据前文中对于图的定义， G = { P , Q , G , H } \mathcal{G}=\{P,Q,G,H\} G={P,Q,G,H}，为了简化问题并且尽量与点配准问题保持一致，此处选择节点的坐标作为节点特征$P=[p_1,...,p_n]$，选择边所连接的两个节点的坐标差值$q_c=p_i-p_j$作为边的特征$Q=[q_1,...,q_m]$。在这种情况下，边的特征可以用矩阵形式计算$Q=P(G-H)$。给定两幅图 G 1 = { P 1 , Q 1 , G 1 , H 1 } , G 2 = { P 2 , Q 2 , G 2 , H 2 } \mathcal{G}_1=\{P_1,Q_1,G_1,H_1\},\mathcal{G}_2=\{P_2,Q_2,G_2,H_2\} G1​={P1​,Q1​,G1​,H1​},G2​={P2​,Q2​,G2​,H2​}，两组点之间的几何变换为$\tau (\cdot )$，计算节点关联矩阵$K_p(\mathcal{T})$和边关联矩阵$K_q(\mathcal{T})$
$$k_{i_1{i}_2}^p(\mathcal{T})=-\Vert p_{i_1}^1-\tau (p_{i_2}^2){\Vert }_2^2(24)$$ $$k_{c_1{c}_2}^q(\mathcal{T})=\beta -\Vert (p_{i_1}^1-p_{j_1}^1)-(\tau (p_{i_2}^2)-\tau (p_{j_2}^2)){\Vert }_2^2(25)$$
$\beta$选择一个较大的数以保证边的相似性为非负值。与点配准问题相似，为了让图匹配对于几何变换更加鲁棒，DGM不仅要找到最优的对应关系$X$还要找到最优的变换参数$\mathcal{T}$，则优化的目标函数为
$$\underset{X\in \Pi ,\mathcal{T}\in \Psi }{\max }{J}_{dgm}(X,\mathcal{T})=tr(K_p(\mathcal{T}{)}^{T}X)+\lambda tr(K_q(\mathcal{T}{)}^{T}Y)-\psi (\mathcal{T})(26)$$
$\lambda >0$用于平衡节点和边的重要性。当$\lambda =0$时，上述目标函数等价为点配准问题，当$\lambda >0$但$\mathcal{T}$已知时，上述目标由等价为图匹配问题。

优化策略

  由于目标函数的非凸属性，本文采用与点配准相似的优化策略，交替优化$X$和$\mathcal{T}$。对DGM问题而言，初始化非常重要，但如何选择一个好的初始化参数已经超过本文的范畴。本文简单地将变换参数初始化为同等变换，即$\tau (p)=p$。给定$\mathcal{T}$时，上述优化问题变成图匹配问题，可以采用前文介绍的路径跟随算法求解最优的$X$。给定$X$时，可参考点配准方法求解最优的$\mathcal{T}$。针对上文所述的几种常见几何变换，均可求得闭式解。

相似变换

  根据公式(25)，边特征的相似变换为$\tau (q)=sRq$或$\tau (Q)=sRQ$，由于平移变换$t$只会影响节点特征，不会影响边的特征，因此当最优旋转矩阵$R^{\ast }$和最优放缩系数$s^{\ast }$已知时，最优平移向量$t^{\ast }$可得
$$t^{\ast }={\bar{p}}_1-s^{\ast }{R}^{\ast }{\bar{p}}_2,{\bar{p}}_1=\frac{P_{1}X{1}_{n_2}}{1_{n_1}^{T}X{1}_{n_2}},{\bar{p}}_2=\frac{P_{2}X{1}_{n_1}}{1_{n_1}^{T}X{1}_{n_2}}(27)$$
经过数据中心化操作${\bar{P}}_1=P_1-{\bar{p}}_1{1}_{n_1}^T$，${\bar{P}}_2=P_2-{\bar{p}}_2{1}_{n_2}^T$，最优的旋转矩阵$R^{\ast }$和最优放缩系数$s^{\ast }$为
$$R^{\ast }=Udiag(1,...,|U{V}^T|)V^T(28)$$$$s^{\ast }=\frac{tr(\Sigma )}{tr(1_{n_1\times 2}({\bar{P}}_2\circ {\bar{P}}_2)X^T+{\lambda }_{q}tr(1_{m_1\times 2}({\bar{Q}}_2\circ {\bar{Q}}_2)Y^T))}(29)$$
其中$U\Sigma V^T={\bar{P}}_{1}X{\bar{P}}_2^T+{\lambda }_q{Q}_{1}Y{Q}_2^T$

仿射变换

  与相似变换接近，边特征的仿射变换为$\tau (q)=Vq$或$\tau (Q)=VQ$。最优平移向量为
$$t^{\ast }={\bar{p}}_1-V^{\ast }{\bar{p}}_2,{\bar{p}}_1=\frac{P_{1}X{1}_{n_2}}{1_{n_1}^{T}X{1}_{n_2}},{\bar{p}}_2=\frac{P_{2}X{1}_{n_1}}{1_{n_1}^{T}X{1}_{n_2}}(30)$$
最优的仿射变换为
$$\begin{gathered} V^{\ast }=A{B}^{-1},A={\bar{P}}_{1}X{\bar{P}}_2^T+{\lambda }_q{Q}_{1}Y{Q}_2^T \\ B={\bar{P}}_{2}diag(X^T{1}_{n_1}){\bar{P}}_2^T+\lambda Q_{2}diag(Y^T{1}_{m_1})Q_2^T(31) \end{gathered}$$

RBF非刚性变换

  边特征的非刚性变换为$\tau (q_c)=q_c+W(\varphi (p_i)-\varphi (p_j))$或$\tau (Q)=Q+W{L}_q,L_q=L_p(G-H)$，最优的权重矩阵$W^{\ast }=A{B}^{-}1$
$$\begin{gathered} A=P_{1}X-P_{2}diag(X^T{1}_{n_1})+{\lambda }_q{Q}_{1}Y(G_2-H_2{)}^T-{\lambda }_q{Q}_{2}diag(Y^T{1}_{m_1})(G_2-H_2{)}^T \\ B=L_{p}diag(X^T{1}_{n_1})+{\lambda }_w{I}_{n_2}+{\lambda }_q{L}_{q}diag(Y^T{1}_{m_1})(G_2-H_2{)}^T(32) \end{gathered}$$

实验

  图(a)中展示了三种不同程度的相似变换（由蓝色到红色），图(b)中展示了ICP算法在迭代24次时，在不同程度的变换作用下，目标函数值得情况。目标函数值越接近于0，表示匹配效果越好，可以看到在旋转角度为$\frac{1}{3}\pi$时，ICP算法陷入了局部最优，无法得到最优得匹配结果。图( c)中展示了DGM算法在不同迭代次数下，不同程度得变换作用下，目标函数值得情况。可以看到虽然在迭代初期，在大部分得变换条件下，匹配效果不尽人意。但随着迭代次数增加，匹配效果越来越好，当迭代24次时，在所有得变换条件下均能达到最优匹配。

总结

  本文是图匹配（Graph Matching）入门学习笔记——以《Factorized Graph Matching》为例系列文章的最后一篇，总结了图匹配和点配准问题之间区别与联系，介绍了三种常见的几何变换，并几何变换引入图匹配构成可变形图匹配问题。最后提出了在三种变换条件下，如何优化求解DGM问题。关于图匹配的研究和应用都浩如烟海，这系列文章只是对图匹配问题有一个初步的介绍，更多更新的算法还需要进一步的学习与探索。

1. 图匹配（Graph Matching）入门学习笔记——以《Factorized Graph Matching》为例（一）
2. 图匹配（Graph Matching）入门学习笔记——以《Factorized Graph Matching》为例（二）
3. 图匹配（Graph Matching）入门学习笔记——以《Factorized Graph Matching》为例（三）