LGSC：基于局部图结构一致性的鲁棒图像匹配

Robust image matching via local graph structure consensus

LGSC：基于局部图结构一致性的鲁棒图像匹配

摘要

图像匹配在许多计算机视觉任务中起着至关重要的作用，本文主要研究基于特征匹配的失配去除问题。通过将整数二次规划与劝阻匹配的补偿项(称为局部图结构一致性(LGSC))相结合，将该问题转化为一个通用而有效的基于图匹配的优化框架。考虑到这些潜在真匹配的局部区域相似性，我们设计了一种保持几何拓扑的局部图结构，该结构包含一个局部指示向量和一个局部亲和向量。利用局部指示向量进行边缘构造，局部亲和向量表示两个图之间节点和边的匹配正确性。特别地，利用具有规模和旋转不变性的排名移位来表示节点的亲和力。最后，我们得到了一个具有线性时间和线性空间复杂度的封闭解。此外，为了提高算法的鲁棒性和有效性，提出了一种多尺度迭代的图构造策略。在各种真实图像数据集上的大量实验表明，我们的LGSC可以取得比目前最先进的方法更好的性能。

关键词：图像匹配、特征匹配、失配去除、离群值、图像配准

1.引言

​ 图像匹配是基于视觉的应用中一个基本而重要的问题，它试图在同一物体或场景的两幅图像之间识别并构建可靠的对应关系。相关的计算机视觉任务包括图像配准[1,2]和融合[3]、三维重建[4]、基于内容的图像检索[5]、全景图像拼接[6]、目标识别与跟踪[7]、同时定位与映射(simultaneous localization and mapping, SLAM)[8]等。一种鲁棒、高效的特征匹配算法可以为这些应用程序的性能提供充分的保障和支持。

​ 针对特征匹配的组合特性，非pareto准则复杂优化算法存在较高的计算复杂度问题。在不考虑异常值的情况下，即使是一个简单的将N个点与另N个点匹配的问题也会伴随着N!排列为[9]。目前已有点集配准和图匹配两种方法来解决这一问题，前者的目标是估计空间变换，如迭代闭点(ICP)方法[10]和使用薄板样条的非刚性配准方法[11]，后者通常通过构造整数规划问题(IQP)来解决对应问题。大多数图匹配方法都是通过放宽严格的约束条件来提供近似解，如保持二值约束的图匹配[12]、通过空间相干通信发现常见的视觉模式[13]和最近的图学习匹配[14]。但这些直接匹配方法存在计算量大、匹配性能不稳定等问题。

​ 为了解决上述问题，现有方法中常用的一种策略是采用间接两步匹配方法。首先根据特征描述符的相似性构造相对可靠的假定匹配，典型的特征描述符包括尺度不变特征变换(SIFT)[15]、面向FAST和旋转BRIEF (ORB)[16]和加速鲁棒特征(SURF)[17]。然而，仅使用局部特征描述符不可避免地会导致图像对中的大量不匹配(即离群值)。因此，在此之后，需要额外的局部和/或全局几何约束来识别正确的匹配(即内层)，并在假定的匹配集中拒绝离群值。尽管最近提出的基于端到端学习的方法[18,19]可以从原始图像对中构造正确的对应，其中内层数和内层率都非常高，因此在很大程度上优于传统的SIFT，一种改进的离群值剔除方法在实际应用中仍具有重要意义。一方面，最近提出的深度特征匹配器在通用性方面可能存在明显的局限性，也会产生大量的异常值和异常值比例，甚至无法处理那些“未见”的数据，如多模型图像[20]。另一方面，这些深度匹配方法本身就包含了失配去除策略和几何验证策略，因此研究有效的失配去除方法既可以进一步提高其匹配性能，又可以为未来的研究提供有用的理论保障。

​ 为此，设计了多种算法。最具代表性的方法是随机样本共识(RANSAC)[21]，它试图在假设-验证范式和随机重采样策略下找到一个最小的内层集合来拟合给定模型。大量的后续研究提高了plain RANSAC的效率和准确性[22-25]。具体来说，这一流程中的一个通用框架，即USAC[23]，将多个进度组合成一个统一的框架，并表现出卓越的性能。MAGSAC++[25]应用了δ-consensus与新的评分功能，并在速度和鲁棒性方面有改进。但随着离群值的增加，这些方法的运行时间呈指数增长，甚至在处理非刚性情况时失败。这可以通过一些专门设计的非刚性方法来缓解，如通过对应函数(ICF)[26]识别点对应，或对重构核Hilbert空间进行Tikhonov调节，如向量场一致性(VFC)[27]和局部线性变换[28]。这些方法对任意几何变形的特征匹配都有较好的效果。但对于宽基线图像对或图像场景中的多个独立运动，它们的影响仍然很大，因为它们使用的缓慢平滑的假设会在一定程度上违背。此外，在放宽方法方面也有了明显的发展，放宽方法对各种场景的几何约束不那么严格，但却很普遍。这类方法的代表性方法有:考虑分段仿射变换求变形一致性[29]、似然函数估计[30]、局部保持一致性[31]及其改进方法[32,33]、基于网格的运动统计(GMS)[34]、聚类实现运动一致性聚类[35-37]。然而，这些方法非常有效，但高度依赖于良好的初始化来保证局部结构的精确构建，因此结果显示粗糙。

​ 近年来，学习方法越来越多地应用于内层和离群值的分类，取代了传统的对应检验或模型回归方法。[38]在输出摄像机运动参数的同时，训练包含内禀成像和极线几何约束的网络，以将对应标记为内层或离群值，学习寻找良好的对应。然而，在某些匹配困境中，该算法的有效性有待提高，而且它倾向于牺牲正确的匹配来估计运动参数。为了提高性能，人们提出了对LFGC的各种改进，例如使用顺序感知策略[39]、注意上下文规范化策略[40]或图注意策略[41]。本文创新性地提出了一种用于失配去除的两类分类器LMR[42]，该分类器在线性时间复杂度下表现出良好的匹配性能。但由于其匹配表达式有限，仍可能局限于具有挑战性的数据或场景。基于学习的方法在基于深度学习模块的几何估计和特征对应分类方面显示了巨大的潜力。

​ 失配去除问题虽然在过去的几年里有了很大的发展，但仍需要一种准确、健壮、高效的算法用于实际应用，其中主要存在以下三个方面的挑战。首先，图像对之间的几何变换通常是未知的，因此迫切需要一种能够处理各种变换的通用算法。其次，真实计算机视觉任务中的特征匹配问题通常存在物体变形、成像质量低、结构重复等问题，导致大量的不匹配，从而增加了建立准确对应关系的难度。第三，实际应用中的图像对通常不是简单的参数化模型变换，而是相当复杂的非刚性模型，容易产生较高的计算量和较差的匹配结果。

​ 针对上述问题，本文提出了一种鲁棒且有效的图像特征匹配算法，即局部图结构一致性(Local Graph Structure Consensus, LGSC)，该算法不依赖于任何预定义的转换模型，能够从假定的特征对应集中消除不匹配。首先，根据具有假定特征集的图像对构造两个图。通过引入抑制匹配的补偿项，失配去除被表示为全局目标函数的最大化。我们观察到，对于同一物体或场景的图像对，在缩放和旋转，甚至是非刚性变形下，真实对应的局部邻域结构通常保存得很好，如图1所示。

​ 因此，我们设计了一个局部图结构来表示局部拓扑信息，从而在保持局部图结构一致性的原则下解决目标问题。该模型的容忍度允许它处理刚性和非刚性转换，即使当图像遇到严重变形时。通过定性和定量实验证明，我们的LGSC在对大几何变形的鲁棒性、对各种描述符的通用性和应用便利性等方面具有令人满意的特性。

​ 具体来说，我们在这方面的贡献包括以下三个方面:

• 针对鲁棒图像匹配问题，提出了一种基于图匹配的数学优化模型。与现有的大多数方法相比，该方法利用局部几何信息的一致性，不需要特定的参数或非参数模型来解决全局图像变换，因此对包括复杂非刚性在内的各种图像变换具有鲁棒性。
• 从局部图结构一致性的角度推导出一个封闭解，具有线性时间和线性空间复杂度，从而保证了该方法在特征匹配方面的效率。
• 我们进一步提出了一种多尺度迭代的局部图构造策略，使我们的方法能够高效地过滤不匹配和保留正确的匹配，具有较高的鲁棒性。

本文的其余部分组织如下。在第2节中，我们详细描述了用于鲁棒特征匹配的LGSC。随后，我们在第3节中介绍了关于特征匹配和基于视觉的应用的各种定性和定量的比较实验。最后，第四部分是本文的结束语。

2. 方法

本节将详细描述我们提出的鲁棒图像特征匹配算法。首先，基于特征描述符的相似性构造一组假定匹配(如SIFT[15])，其中过滤掉描述符向量明显不同的匹配。随后，我们需要额外的几何约束来去除假设集合中的不匹配。接下来，我们的重点是使用基于局部图结构一致性的方法去除不匹配阶段。

2.1 问题描述

​ 给定N个假定的图像特征点对应集合$T=\{(y_i,z_i\}_{i=1}^N$，其中$y_i$和$z_i$是表示一对对应特征点的空间位置的属性向量，适用于二维和三维匹配问题。我们的任务是从假定的对应集$T$中去除不匹配。

​ 对于由图像对的两个特征点集组成的两个图，我们引入一个目标$S$，使目标$S$最大化，得到未知内层集$\mathcal{I}$的最优解，即:

​ 目标$S$定义如下：

​ 式中，第一项为内层图匹配表示IQP，由指示向量$x\in\{0,1\}^{N\times 1}$表示$\mathcal{I}$的对应解和描述节点与边匹配度的亲和矩阵W组成。第二个补偿项不鼓励匹配，并可以避免allinlier（全内点）的琐碎解决方案(即，$x=1^{N\times 1}$)，其中参数$\lambda> 0$控制与第一项的权衡，|·|表示集合的基数。

​ 为了定义亲和性矩阵W，我们基于假定的特征对应集T构造了两个赋值关系图$G(V,E)$和$G'(V',E')$，其中每个节点$v_i\in V$指向点$y_i\in T$，对于点$z_i\in T$， $v'_i\in V'$也是相似的，并且每个边$e_{ij}=(v_i,v_j)\in E$连接图$G$中的节点$v_i$到节点$v_j$,$e'_{ij}=(v'_i,v'_j)\in E'$连接图$G'$中的节点$v'_i$到节点$v'_j$。与图匹配中的一对一或多对一编程问题不同，我们的最终目标是求出$\{(v_i,v'_i)\}_{i=1}^N$的内层。

​ 对于每个节点对应$(v_i,v'_i)$，定义一个节点亲和度得分$s(v_i,v'_i)$来衡量节点$v_i$与节点$v'_i$的匹配程度。同样地，对于每个对应对$(v_i,v'_i)$和$(v_j,v'_j)$，我们定义了一个边亲和度得分$s(e_{ij},e'_{ij})$，它表示边$e_{ij}=(v_i,v_j)\in E$与边$e'_{ij}=(v'_i,v'_j)\in E'$的兼容程度。因此，可以构造一个亲和度矩阵W，其中对角线项$W_{ii}$表示节点亲和度得分$s(v_i,v'_i)$，非对角线项W ij表示边缘亲和度得分$s(e_{ij},e'_{ij})$。也就是

​ 确定一个二进制向量$x$作为该匹配问题的解，表示为$x=(x_1,...,x_i,...,x_N)^T,x_i\in\{0,1\}$，$x_i=1$表示对应$(v_i,v'_i)$被归为内层，对于离群值，反之亦然。显然，$\mathcal{I}=x^Tx$，因此我们推导并得到了错配去除问题的简洁公式，即:

​ 其中$\lambda N$为可省略的预定常数项，$I$为N维单位矩阵。

​ 我们将目标分解，创新性地求解每个节点对应，得到:

​ 其中$w_i$是$W$的第$i$列。

2.1.1 局部图结构

​ 在观察到内层的局部拓扑结构即使在非刚性变换下也能很好地保持不变的基础上，我们设计了一种描述拓扑信息的局部图结构来求解每个对应关系。首先，在欧几里德距离下，通过搜索K个最近邻(K- nn)构造邻域，这是一种有效的距离度量方法，足以用于特征匹配问题。然后，通过对K邻域施加物理约束构造两个局部图。因此，目标$\tilde{S}$转化为$\tilde{S}_K$，即:

​ 其中，$w_i^K$和$x_i^K$描述了以对应$(v_i,v'_i)$为中心的局部图结构，它们分别被称为局部亲和力向量和局部指示向量。

​ 局部指示向量$x_i^K$被构造为每个对应$(v_i,v'_i)$的二元向量，表示局部图的边缘构造。$x_i^K\in\{0,1\}^{(K+1)\times 1}$，其第一项设为1，其他K项表示相邻节点是否连接到中心节点$v_i$从而形成图边。换句话说，Eq.(7)中的$x_{ij}^K=1$表示从两个对应的邻居$(v_{i_j},v'_{i_j})$到它们的中心对应$(v_i,v'_i)$的两条边分别构造在两个局部图$G_{v_i}$和$G_{v'_i}$中。

​ 为了使局部拓扑结构的一致性最大化，指标向量$x_i^K$由:

​ 其中

​ $\mathcal{N}_{v_i}^K$表示节点$v_i$的K近邻。也就是说，利用局部指示向量来确定两个邻域$\mathcal{N}_{v_i}^K$和$\mathcal{N}_{v'_i}^K$的公共对应元素，从而确定两个局部图结构$G_{v_i}$和$G_{v'_i}$的边。

​ 局部亲和力向量A局部亲和力向量$w_i^K$包含阳极亲和力得分和K个边缘亲和力得分，为$w_i$的K + 1个非零项的组合，即:

​ 接下来，我们考虑节点亲和度评分$s(v_i,v'_i)$和边缘亲和度评分$s(e_{ii_j},e'_{ii_j})$的定义。

​ 节点亲和度评分$s(v_i,v'_i)$表示每个通信$(v_i,v'_i)$之间的一致性。仅考虑邻域内交叉口的保存是不够的，因此我们使用排序结构来衡量两个对应节点之间的匹配程度，因为与传统描述符相比，排序信息更适合于失配去除问题。

​ 我们观察到，与不匹配相比，正确匹配的排名变化(即$\mathcal{N}_{v_i}^K$和$\mathcal{N}_{v'_i}^K$中相邻点的排名变化)惊人地稳健，如图2所示，这意味着正确匹配的K个相邻点的相对位置变化很小。例如，在$(v_i,v'_i)\in\mathcal{I}$的情况下，节点$v_i$经过图像变换后，其邻居倾向于保持在其周围。因此，我们使用排名移位来表示节点亲和度得分。

​ 为了简化算法，我们使用一个二进制序列$\phi_{v_i}$来定量地表示节点$v_i$周围邻居的排序移位。$\phi_{v_i}$的第k项(即$\phi_{v_ik}$)表示第k个邻居的排序移位。例如，在一个图像对的左图像中，节点$v_j$是节点$v_i$的第k个(k≤K)邻居，其对应的节点$v'_j$以$v'_i$为中心的排序用$r_{v'_ik}$表示，如图3所示，则$\phi_{v_ik}$定义如下:

​ 图像对之间的排序移位应该是对称的，因为从左到右与从右到左的意义相等，因此需要计算$\phi_{v'_i}$。因此，节点亲和度得分的定义如下:

​ 其中$\|\cdot\|$是$l_1$正则，用$\frac{1}{2K}$进行归一化。

​ 对于边的亲和度分数，字面上表示两个局部图$G_{v_i}$和$G_{v'_i}$中对应的两条边$e_{ii_j}=(v_i,v_{i_j})$和$e'_{ii_j}=(v'_i,v'_{i_j})$之间的亲和度。上面介绍的节点亲和度得分利用了排序移位，但没有充分利用局部几何信息。因此需要边缘亲和度，用距离差表示，即

​ 其中，设置系数$\frac{1}{K}$来平衡K条边的亲和度得分与上述节点亲和度得分，d(·)表示距离度量，如欧几里德距离，即$d(e_{ii_j}=\|y_i-y_{i_j}\|_2)$。

​ 值得注意的是，我们的度量两个局部图结构相似性的排序转移策略可以看作是子图同构的一种松弛形式。其中，子图同构是图论中的一个经典主题，它是用来度量目标中是否存在子图或模式图，且该子图或模式图的节点和边属性与给定图相同。而我们提出的排序移位是通过度量相似性来解决特征匹配问题。排序移位具有良好的尺度和角度不变性几何特性，充分利用了坐标空间中的局部拓扑，因此更适合和灵活地处理假定匹配集和筛选特征对应。

2.1.2 多尺度策略

​ 在我们的公式中，局部图结构是由基于K-NN的邻域得到的。但是，一个固定的K不可避免地会遇到以下两个问题:不同的特征对应集通常具有不同的内层比和内层数，从而导致节点之间的关联度不同;即使在一个单一的特征对应集中，所有局部图的内层和离群值的分布通常也不是均匀的。

​ 为了解决上述问题，我们采用了一种多尺度策略，在多尺度下构造局部图，其集合为$K=\{K_m\}_{m=1}^M$。在这种情况下，$\mathcal{N}_{v_i}^{Km}$通过搜索$K_m$近邻来表示以节点$v_i$为中心的邻域结构，$G_{v_i}^{Km}$为相应的局部图结构。而式(6)的目标为:

​ 其中1 /M作用于归一化不同级别局部图的贡献。显然，最终目标函数在尺度和旋转不变性以及不依赖于图像变换模型方面都具有优异的性能。

2.2 解决问题

​ 为了求解目标函数Eq.(13)，对其形式进行了调整，即:

​ 其中

​ 表示第i个对应$(v_i,v'_i)$满足局部图结构一致性的程度。一般来说，潜在的真正匹配具有高值$s_i$，因此能够对目标函数产生实质性的贡献，而不匹配具有低值$s_i$，因此不鼓励。

​ 在失配去除问题中，对于给定的N个特征对应集，可以预先确定$\{s_i\}_{i=1}^N$。由于$\lambda$是预定义的，在式(14)中需要解决的唯一变量是$x=\{x_i\}_{i=1}^N$。显然，$s_i$大于$\lambda$的对应将产生一个正项，从而增加目标函数，而$s_i$小于$的值将产生一个负项。因此，为了使式(14)最大化，x的最优解可以表示为:

​ 然后最佳的内部设置$\mathcal{I}^*$是由下面的公式确定的:

​ 根据式(16)，参数$\lambda$有能力评估每个对应的匹配正确性作为一个阈值。因此，方程式的目标。将(1)和(2)简化为每个对应的二元分类问题，并得到一个封闭解。

​ 此外，为了验证多尺度策略的有效性，我们随机收集了总共30对图像作为测试集，这些图像对来自各种类型的变换，包括片线性、宽基线、非刚性等。SIFT匹配后的平均内层数和内层百分比分别为425和59。分别为8%。评估我们方法性能的指标是F1-score，定义为F1-score = 2 × Precision × Recall / (Precision + Recall)，其中Precision定义为识别的正确匹配数与总保留匹配数的比值，Recall定义为识别的正确匹配数与实际正确匹配数的比值。图4报告了我们方法的f1得分性能，这清楚地证明了多尺度策略的有效性。

2.3 迭代图的构造

​ 局部图结构$\{(G_{v_i}^{Km},G_{v'_i}^{Km})\}_{m=1,i=1}^{M,N}$基于邻域$\{(N_{v_i}^{Km},N_{v'_i}^{Km})\}_{m=1,i=1}^{M,N}$，邻域由包含一定百分比的离群值的整个假定对应集构造。显然，这对于节点亲和度和边亲和度的相似性度量可能会产生较差的参考值。理想情况下，局部图结构是由仅由内层集合$\mathcal{I}$形成的邻域建立起来的。

​ 基于不可能预先获得真实内层集$\mathcal{I}$的事实，我们提出了一种迭代的局部图构造策略，以提高失配去除的有效性。虽然一开始只有整个特征集，但在我们的目标最大化之后，生成的对应集可以被认为是真内联集$\mathcal{I}$的理想近似，命名为$\mathcal{I}_1$，即$\mathcal{I}=\arg \max_{\mathcal{I}}\tilde{S}(\mathcal{I;T,\lambda})$，其中局部图是由整个特征集T构造的。

​ 随后，$\mathcal{I}_1$被用来为T中的每个对应构造邻域局部图结构。图5中，根据$\mathcal{I}_0=T$和迭代集$\mathcal{I}_1$形成的局部图，显示了$s_i$对于内层和离群点的分布。显然，迭代图构造策略有助于区分离群值和内层值。因此，$\mathcal{I}^*$的最佳解决方案就解决了，即

​ 这可以看作是一种迭代的方式，以逐渐接近最优解。在我们的实验中，我们发现两次迭代在经验上是足够的。

​ 考虑到我们的特征匹配算法是根据局部图结构的一致性来定制的，因此我们将其命名为局部图结构一致性。整个过程总结在算法1中。

​

2.4 与LPM的区别

​ 这项工作与我们之前开发的LPM[31]有关。受到LPM的启发，我们通过保持局部拓扑一致来解决每个对应。然而，基于图匹配理论，本文提出了一种不同的优化框架来解决匹配问题。

​ 首先，在IQP的基础上，将失配消除问题构建为一个图匹配模型，并引入补偿项来抑制匹配。与LPM中基于测点距离的启发式建模不同，我们的LGSC具有一种新颖的模型形式。其次，我们提出通过设计和构造局部图结构来表示拓扑信息。与LPM只计算K-NN内的交点相比，我们对局部图的节点和边缘的亲和度得分施加了更严格的物理约束，以保持拓扑结构的一致性。第三，引入秩转移，将假设的特征集从二维几何空间转化为具有尺度和旋转不变性的秩转移空间，从而使LGSC更加稳定。

​ 总之，我们的LGSC提出了一个创新的优化框架，能够更严格地表达局部拓扑共识，具有更鲁棒和更准确的特征匹配性能。这将在后续的实验结果中得到验证。