Robust Feature Matching Using Spatial Clustering With Heavy Outliers

作者：Xingyu Jiang; Jiayi Ma; Junjun Jiang; Xiaojie Guo
机构：武汉大学
年份：2019
期刊/会议：IEEE Transactions on Image Processing
原文地址：Robust Feature Matching Using Spatial Clustering With Heavy Outliers

本文侧重于从给定假设特征匹配中去除误匹配点，这些匹配点通常是基于描述符相似性创建的。为了实现这一目标，现有的尝试通常涉及在几何约束下估计图像变换，其中需要预定义的变换模型。这严重限制了适用性，因为转换可能因不同的数据而异，并且在许多实际任务中很复杂且难以建模。从一个新颖的角度，本文将特征匹配转化为具有异常值的空间聚类问题。主要思想是将假定的匹配自适应地聚类为几个运动一致的聚类以及一个异常值/失配聚类。为了实现空间聚类，我们在特征匹配的背景下定制了经典的基于密度的应用程序空间聚类方法（DBSCAN），这使我们的方法能够实现准线性时间复杂度。我们还设计了一种迭代聚类策略，以在数据严重退化的情况下提高匹配性能。对涉及不同类型图像转换的多个数据集进行的大量实验证明了我们的方法优于最先进的替代方法。我们的方法还应用于近似重复的图像检索和共同分割，并取得了可喜的性能。对涉及不同类型图像转换的多个数据集进行的大量实验证明了我们的方法优于最先进的替代方法。我们的方法还应用于近似重复的图像检索和共同分割，并取得了可喜的性能。

Ⅰ 介绍

动机：寻找两幅图像之间的可靠对应关系。通常的方式是构建一组假定匹配，然后移除错误匹配。因此设计一种强大的方法消除异常值提高匹配可靠性至关重要。

现有的方法是通过施加几何约束解决异常值去除问题。这种几何约束需要预定义变换模型，这种需求严重限制了许多视觉任务的适用性。例如可变性物体识别和动态场景匹配，这类场景的变换模型是事先未知的。

在本文中，作者提出了一种空间聚类方法，旨在利用假定匹配之间的运动一致性。这是基于观察到正确的匹配往往具有相似的运动行为，可以将其聚集到几个运动一致的组中，而错误的匹配往往随机分布在可以标记为异常值的图像域中。

提出的方法在 7 个典型图像对上的结果。在每组结果中，为了清晰起见，我们在左侧图像对中最多显示 200 个特征匹配；右侧运动场中每个箭头的头部和尾部对应于左侧图像对中两个对应特征点的位置。不同的颜色表示不同的inlier cluster，黑色表示outlier cluster。

理想情况下，给定聚类的族群数量且特征点对应正确，找到合理聚类结果并不困难。问题在于：一是不确定族群的数量，二是拥有很多假阳性（异常值）。这两个问题为筛选异常值、确定内联点造成困难。

本文中的贡献包括以下三个方面。

提出了一种使用空间聚类进行稳健特征匹配的简单而有效的方法。它不像现有尝试那样需要预定义的变换模型，并且可以利用图像场景中的多种运动模式。
定制了经典的 DBSCAN 来解决匹配问题，并设计了一种通用的迭代聚类策略，可以在数据严重退化的情况下提高基于 DBSCAN 的方法的性能。
将特征匹配方法应用于两个基于视觉的任务，即图像检索和共同分割，并获得令人满意的性能。

Ⅱ 相关工作

A. 特征匹配

图像匹配为从假定集合中去除异常值，大致方法分为三类：重采样方法、非参数插值法、图匹配方法。

重采样方法：例如RANSAC及其变体，当几何约束是参数化时，变现相当好。但如果是非参数化的，暴露局限性。特别是当异常值占主导地位时，性能会急剧退化甚至失败。
非参数方法：识别对应函数 (ICF) 和基于流形正则化的鲁棒点匹配 (MR-RPM) 。ICF 寻找对应函数对，将一幅图像中的点映射到另一幅图像中的对应点。然后可以通过积极检查估计的对应函数中的偏差来踢出异常值。而 MR-RPM 强制运动场在流形正则化下是平滑的，并从鲁棒的运动场插值角度克服了匹配问题。然而，该类别中的方法通常具有三次复杂度，限制了它们对实时任务的适用性。
图匹配：谱匹配、对偶分解、模式搜索、图移位 (GS) 多图匹配。这些方法通常将特征匹配表述为二次分配问题，以根据亲和度矩阵寻找最大内点集。图匹配为转换模型提供了相当大的灵活性，但也存在类似的非多项式难性质的缺点，不适用于大规模视觉任务。

在最近的过去，特征匹配已经使用分段平滑约束来解决，例如基于相干性的决策边界、基于网格的运动统计 (GMS) 、学习不匹配去除和学习一个寻找良好对应关系的深层网络（LFGC），在准确性和效率方面都取得了可喜的表现。此外，还研究了几种技术来解决特定的匹配问题，例如大规模变化的图像匹配、3D 点云配准以及语义区域对应。

B. 空间聚类

空间聚类是将一组样本分组的任务，使同一聚类中的样本彼此之间比其他聚类中的样本更相似。

基于连通性的方法：层次聚类
基于质心的方法：K-means
基于分布的方法：高斯混合模型

然而上述方法对样本异常值并不稳健，由于没有设置特殊的离群点簇，离群点通常被归类到与它们最相似的正常簇中。此外，这些方法有时要求数据库满足特定的分布，计算复杂度也比较高，限制了它们解决特征匹配问题的能力。

能处理异常值的最具代表性的空间聚类算法之一是 DBSCAN ，与许多其他聚类方法相比，它对异常值具有鲁棒性，并且具有相对较低的复杂性。

然而，DBSCAN 有一个关键的缺点，比如对参数设置的敏感性，这在解决复杂的特征匹配问题时会出现问题。

在本文中，作者设计了一种自适应参数估计方法和一种迭代聚类策略，以 DBSCAN 作为基本模型来解决这些挑战。

C. DBSCAN

DBSCAN的基本原理是：对于族群内每一点，在给定半径 $\varepsilon$ 的范围内必须至少包含给定数量 $MinPts$ 的采样点，半径 $\varepsilon$ 和最小采样点数量 $MinPts$ 有下列定义实现：

定义1： $\varepsilon$ 近邻采样点

采样点 ${\bf p}$ 半径为 $\varepsilon$ 的近邻点集合为 $\mathscr N_\varepsilon({\bf p})$ ，定义如下：
${\mathscr N}_\varepsilon({\bf p}) =\{{\bf q}\in D|d({\bf p},{\bf q}\leq\varepsilon)\}$
其中 $D$ 为所有采样点， $d$ 表示距离度量。

如果采用上述定义，那么族群中的边缘点很容易被判断为外点，因为边缘点的近邻点较少。为了防止将边缘点误判为外点，DBSCAN将 $|{\mathscr N}_\varepsilon({\bf p})| \geq MinPts$ 这些满足内点要求的点作为核心样本，通过下述定义召回边缘点。

定义2：直接密度可达

对于 $\varepsilon$ 和 $MinPts$ ，若 ${\bf p}\in{\mathscr N}_\varepsilon({\bf q})$ 且 ${\bf q}$ 为核心样本，则样本 ${\bf p}$ 从样本 ${\bf q}$ 直接密度可达。

定义3：密度可达

对于 $\varepsilon$ 和 $MinPts$ ，若存在一系列样本 ${\bf p}_1, {\bf p}_2,\cdots,{\bf p}_n$ ，其中 ${\bf p}_1={\bf q}$ ， ${\bf p}_n ={\bf p}$ ，且 ${\bf p}_{i+1}$ 从 ${\bf p}_i$ 直接密度可达，则样本 ${\bf p}$ 从样本 ${\bf q}$ 密度可达。

定义4：密度连接

对于 $\varepsilon$ 和 $MinPts$ ，若给定样本 ${\bf o}$ ， ${\bf p}$ 和 ${\bf q}$ 从 ${\bf o}$ 密度可达，则样本 ${\bf p}$ 和样本 ${\bf q}$ 密度连接。

边界点误判的问题可以用密度连接的定义来描述，族群可以由一系列密度连接样本定义。

定义5：族群

对于 $\varepsilon$ 和 $MinPts$ ，族群 $C$ 为 $D$ 非空子集，满足以下条件：

极大值：给定 $\varepsilon$ 和 $MinPts$ ，对 $\forall{\bf p},{\bf q}$ ，如果 ${\bf p}\in C$ ，且 ${\bf q}$ 从 ${\bf p}$ 密度可达，则 ${ \bf q} \in C$ ；
连接性：给定 $\varepsilon$ 和 $MinPts$ ，对 $\forall{\bf p}, {\bf q} \in C$ ，则 ${\bf p}$ 和 ${\bf q}$ 密度连接。

定义6：外点

令族群 $C_1,C_2,\cdots,C_k$ ，定义外点为集合 $D$ 中包括但任意族群 $C_i$ 都不包括的点，即 $outliers =\{{\bf p}\in D|\forall i:{\bf p}\notin C_i\}$ .

DBSCAN可以通过两步发现族群。

首先给定 $\varepsilon$ 和 $MinPts$ ，从 $D$ 中选择任意满足核心样本的样本；

然后计算所有样本到核心样本的密度到达，判断所有样本与其他样本的密度连接。

下图总结了这一过程。

DBSCAN算法

Ⅲ 方法

作者的方法专注于去除外点，并将其看作是空间聚类问题。

A. 问题描述

如前所述，两个相邻的特征点应该具有相似的运动属性，例如运动矢量的方向和长度。因此，由假定匹配引起的运动场矢量通常由一个或多个运动一致的簇和异常值组成。特别是，运动一致约束可能涉及旋转和缩放变化，并且来自同一类的匹配通常来自图像场景中的相同对象或相同的景深。因此，离群点去除问题可以看成是一个有离群点的空间聚类问题，本质上是为了解决以下两个问题：

将每个假定匹配表征为聚类样本，例如，构建用于相似性度量的每个假定匹配的属性，并设计特定于匹配问题的距离度量。
在特征匹配的上下文中设计聚类规则，该规则应该对参数变化具有适应性和鲁棒性，将假定的匹配划分为几个运动一致的集群和一个异常值集群。

假定有 $N$ 对特征匹配 $S=\{({\bf x}_i,{\bf y}_i)\}$ ，其中 ${\bf x}_i$ 和 ${\bf y}_i$ 为二维向量，代表特征点在两幅图像上的空间位置。令 ${\bf m}_i={\bf y}_i-{\bf x}_i$ 代表匹配点 $({\bf x}_i,{\bf y}_i)$ 的运动向量，可以将假定匹配点 $S$ 转化为包含噪声的数据 $D$ ，即
$\begin{equation*} D = \{\mathbf {p}_{i}=(\mathbf {x}_{i}^{\mathrm{ T}},\mathbf {y}_{i}^{\mathrm{ T}},\mathbf {m}_{i}^{\mathrm{ T}})^{\mathrm{ T}},i=1,2,\cdots,N\}, \tag{1}\end{equation*}$
其中 ${\bf p}_i$ 表示假定匹配点对 $({\bf x}_i,{\bf y}_i)$ 的性质。为了增强运动关联，定义权重距离 $d({\bf p}_i,{\bf q}_i)$ 为
$\begin{equation*} d(\mathbf {p}_{i},\mathbf {p}_{j}) =\phi (\mathbf {x}_{i},\mathbf {x}_{j})+\phi (\mathbf {y}_{i},\mathbf {y}_{j})+w_{i,j}\cdot \phi (\mathbf {m}_{i},\mathbf {m}_{j}), \tag{2}\end{equation*}$
权重参数 $\omega_{i,j}$ 表示为：
$\begin{equation*} w_{i,j} =1+\gamma \cdot e^{-\min \{\phi (\mathbf {x}_{i},\mathbf {x}_{j}),\phi (\mathbf {y}_{i},\mathbf {y}_{j})\}},\tag{3}\end{equation*}$
其中 $\phi(\cdot)$ 表示距离度量函数，例如欧氏距离、高斯核距离等。本文中采用的是欧氏距离。参数 $\gamma$ 是增强相邻特征点运动关联的正值。因此可以根据 ${\mathbb D}_{i,j}=d({\bf p}_i,{\bf p}_j)$ 计算 $N\times N$ 的距离矩阵 ${\mathbb D}$ ，利用算法1中的DBSCAN可以从假定匹配点对中找出外点。

值得注意的是，与传统的匹配方法相比，本文提出的基于聚类的匹配策略更具通用性。特别是，与通常依赖预定义变换模型的传统方法不同，本文方法可以处理经历任何变换模型的图像对。

B. 自适应参数估计

确定权重距离计算 $d$ 后，DBSCAN的主要为不同事故如何选择参数去除误匹配点。下图展示了 $\varepsilon$ 和 $MinPts$ 合适的参数值在30次随机选择图像对上的分布。

涉及不同类型变换的30个随机选择的图像对上的参数分布图。左：最佳参数值（ε，MinPts）；右：最佳参数值（μ，Pct）。每个散射点表示特定图像对上的最佳参数值。

匹配性能以精度、召回率和F分数为特征，其中精度（P）定义为识别的内联数与保留的匹配数之比，召回率（R）定义为识别的内联数与整个内联数之比，F分数定义为2PR与P+R之比。

结果显示，不同选择合适参数差异非常大，因此使用事先确定的固定参数实现精确匹配性能存在问题。显然，在处理现实世界或大规模匹配任务（如图像检索、SLAM和3D重建）时，不可能手动确定每个图像对的参数。尽管DBSCAN开发了一种基于搜索数据库中“最薄”簇的拐点来确定参数的简单启发式方法，但如果数据库 $D$ 中存在多个拐点或异常值（这在特征匹配问题中经常发生），则该方法通常会失败。因此，研究一种自适应参数估计方法具有重要意义。

为了解决上述问题，定义 $K-dist$ 的概念如下：

定义7：样本的K-dist

对于任意正整数 $K$ ，样本点 ${\bf p}$ 的K-dist记为 $K-dist({\bf p})$ ，若样本 ${\bf p}$ 和样本 ${\bf q} \in D$ 的距离 $d({\bf p},{\bf q})$ 满足：

至少 $K$ 个样本 ${ \bf o} \in D$ ，有 $d({\bf p}, {\bf o}) \leq d({\bf p}, {\bf q})$ ；
最多 $K-1$ 个样本 ${ \bf o} \in D$ ，有 $d({\bf p},{\bf o})<d({\bf p},{\bf q})$ .

$\varepsilon$ 和 $MinPts$ 的最佳参数取决于 $D$ 的密度。换个角度来说，选取核心样本的判决条件可以由 $|{\mathscr N}_\varepsilon({\bf p})| \geq MinPts$ 更改为 $K-dist({\bf p})\leq\varepsilon$ ，相当于 $K$ 扮演了和 $MinPts$ 相同的作用。

不失一般地，假设 $K$ 取决于 $N$ 的一个固定比例 $Pct$ ，即 $K=[N\cdot Pct]$ ，其中 $[\cdot]$ 表示取整（round）操作。此外，将这个值限制在 $B_L$ 和 $B_U$ 之间，则 $K$ 定义为：
$\begin{equation*} K=\max \{ \min \{ [N\cdot Pct], B_{U} \}, B_{L}\}. \tag{4}\end{equation*}$
参数 $K$ 用于限制族群的尺度，例如，一个族群在半径 $\varepsilon$ 内至少需要 $K$ 个样本，即一个核心样本族群。在本文中， $B_L=3$ ， $B_U=30$ ，适用于各种匹配问题。

接下来自适应估计参数 $\varepsilon$ ，给定数据 $D$ ，我们用(4)式估计 $K$ ，并且计算每个样本的 $K-dist$ ，得到集合 $d_K$ ：
$\begin{equation*} \mathbf {d}_{K} = \{\textit {K-dist}(\mathbf {p})| \mathbf {p}\in D \}. \tag{5}\end{equation*}$
显然，半径 $\varepsilon$ 应该在 $d_K$ 的最大值和最小值之间，不失一般地，可以定义参数 $\mu\in[0,1]$ ，令
$\begin{equation*} \varepsilon =\mu \cdot \big (\max \{\mathbf {d}_{K}\}-\min \{\mathbf {d}_{K}\}\big) + \min \{\mathbf {d}_{K}\}.\tag{6}\end{equation*}$
至此，估计 $\varepsilon$ 和 $MinPts$ 变为了估计 $Pct$ 和 $\mu$ ，事实上，在不同图像匹配场景中， $Pct$ 和 $\mu$ 具有全局最优解，见图2.

进一步地，为了找到 $Pct$ 和 $\mu$ 以及权重参数 $\gamma$ 的最优解，将其中一个以最优参数固定，改变另两个的值寻找最优解，可以发现当 $Pct=5%$ ， $\mu=0.1$ 以及 $\gamma=10$ 时，达到最优的F分数。结果如下：

不同参数设置下的F分数

作者为了验证式(1)中采用 $({\bf x}_i,{\bf y}_i,{\bf m}_i)$ 而不是 $({\bf x}_i,{\bf m}_i)$ 或者 $({\bf y}_i, {\bf m}_i)$ 或 $({\bf x}_i,{\bf y}_i)$ 来表示 ${\bf p}_i$ ，分别进行了测试，发现采用 $({\bf x}_i,{\bf y}_i,{\bf m}_i)$ 进行表示效果最好。

C. 迭代聚类

在DBSCAN算法中，一个关键步骤是使用 $\varepsilon$ 邻域 ${\mathscr N}_\varepsilon$ （或 $K-dist$ ）来识别核心样本和检索边界内线。 ${\mathscr N}_\varepsilon$ 是在整个数据 $D$ 上定义的，该数据还涉及噪声样本/异常值。通常情况下，噪声样本可能导致误判，并且当 $D$ 被特征匹配中经常出现的大量异常值污染时，该问题将被放大。因此，需要在inlier集合 ${ \mathscr I}$ 上定义 ${\mathscr N}_\varepsilon$ ，如下所示：
$\begin{equation*} \mathcal {N}_{\varepsilon }(\mathbf {p})=\{\mathbf {q}\in \mathcal {I} |d(\mathbf {p},\mathbf {q})\leq \varepsilon \}. \tag{7} \end{equation*}$
然而，内联集 ${ \mathscr I}$ 在本文中是要解决的，并且是事先未知的。为了解决这一困境，本文提出了一种简单而有效的迭代聚类策略。首先基于整个数据 $D$ 构造 ${\mathscr N}_\varepsilon$ 并得到聚类结果。然后，根据聚类结果提取内联点，并将其用作 ${ \mathscr I}$ 的近似值，并为下一轮聚类构造等式（7）中的 ${\mathscr N}_\varepsilon$ 。此过程可以继续，直到收敛。

作者发现两次迭代足以产生令人满意的结果，因此采用两次迭代作为效率的默认设置。通过使用这种迭代聚类策略，内部样本的 ${\mathscr N}_\varepsilon$ 计算将较少受到异常值的影响，这有利于消除不匹配，尤其是在输入数据严重退化时。

为了验证可靠性，归一化式(5)得到
$\begin{equation*} \mathbf {d}_{K}^{*} = \frac {\mathbf {d}_{K}-\min \{\mathbf {d}_{K}\}}{\max \{\mathbf {d}_{K}\}-\min \{\mathbf {d}_{K}\}}. \tag{8} \end{equation*}$
以此得到新的 $K-dist$ ，由下图可知，内点有较小的K-dist值而外点的K-dist值很大，可以找到合适的阈值将这两者分开。

K-dist分布∗ 图2中30个图像对的假定匹配。左：使用假定集D构造邻域；右图：使用假定的inlier集构造邻域。对于每个箱子，我们将重叠内点概率和离群概率，其中概率较小的箱子显示在外层。

包含噪声样本的空间聚类方法，作者称之为RFM-SCAN，这一过程可以被总结为算法2。

RFM-SCAN算法

D. 计算复杂度

作者提出的RFM-SCAN算法包括三步：K-dist的估计、自适应参数估计以及利用DBSCAN外点去除。

从 $D$ 中寻找K近邻：（使用K-D Tree）时间复杂度： $O(N\log N)$
每个样本构建 ${\mathscr N}_\varepsilon$ ，并判断核心样本：时间复杂度： $O(N\log N)$
追回边界点，并为族群打标签：时间复杂度： $O(\sum_{i=1}^N|{\mathscr N}_\varepsilon({\bf p})_i|)\approx O(KN)$

总的时间复杂度为 $O(N(K+\log N))$ ，空间复杂度为 $O(KN)$ 。通常 $K$ 是远小于 $N$ 的常数，时间和空间复杂度可以表示为：

时间复杂度： $O(N\log N)$
空间复杂度： $O(N)$

Ⅳ 实验结果

四个数据集的定量比较。从上到下：Daisy、DTU、Retina和RS。从左到右：假定集中内点比率的累积分布、精确召回统计和运行时的累积分布。

在图1中具有相对复杂转换的两个典型对上的不同方法的稳健性测试，例如Book（顶部）和Church（底部）。从左到右：20 次试验中不同异常值比率下的平均准确率、召回率和 F 值。

准确率（左）和召回率（右），即为给定图像检索所需的图像数量。

图 1中我们的 RFM-SCAN 在Book（左）上的共同分割结果的定性说明，CBTC（中）取自AdelaideRMF，Pyramid（右）取自iCoseg

共同分割的平均精度 (%) 和标准偏差 (±%)

Ⅴ 结论

在本文中，我们提出了一种基于空间聚类的方法，称为RFM-SCAN，用于稳健的特征匹配。它能够自适应地将一组假定的匹配聚类到几个具有运动一致性的内部组以及线性时间复杂度的异常组中。主要参数是自适应估计的，簇数是自动确定的。一般特征匹配以及两个基于视觉的任务的定性和定量结果证明了我们的策略优于最先进的方法。

大量外点存在情况下使用空间聚类的鲁棒特征匹配