Geometric Estimation via Robust Subspace Recovery

摘要：

1 引言

2 相关工作

3 方法

3.1 DLT 简介

3.2 鲁棒泛化

3.3 线性结构的扩展探索

3.4 实现细节

4 实验结果

4.1 线性嵌入的定性分析

4.2 基本和单应性估计

4.3 对离群值率的敏感性

5 结论

摘要：

根据图像点对应关系进行几何估计是许多 3D 视觉问题的核心过程，通常通过随机采样技术来完成。在本文中，我们从优化的角度考虑该问题，利用点对应的内在线性结构来辅助估计。我们将传统方法推广为鲁棒方法，并扩展了之前对线性结构的分析来开发几种新算法。所提出的解决方案本质上是通过解决子空间恢复问题来识别内点来解决估计问题。对基本矩阵和单应性估计的真实图像数据集进行的实验证明了我们的方法在鲁棒性和准确性方面优于最先进的方法。

关键词：几何估计·鲁棒模型拟合·3D视觉·鲁棒子空间恢复

1 引言

在3D视觉中，绝大多数应用，例如图像拼接[5]、运动结构[17]以及同时定位和映射[26]，都依赖于图像之间的特征点对应关系来进行几何估计。然而，由于局部关键点检测和特征描述技术的不完善，对应关系总是受到噪声和许多异常值的污染。退化的数据对精确估计提出了巨大的挑战。因此，实践中使用最广泛的估计器已成为众所周知的随机样本共识（RANSAC）[15]，尽管其简单且发明时间长。

本质上，RANSAC通过重复采样对应的最小子集来提出假设，例如，单应性对应4个，基本估计对应7个。这个过程不断迭代，直到满足一个收敛准则，该准则提供了一个概率保证到达一个全内嵌子集。然而，随机假设验证搜索策略存在一些根本性的缺陷。其中一个主要的限制在于对主导异常值的性能下降。检索全先验子集所需的时间相对于异常值比呈指数增长，并且估计精度也受到高方差的影响。

为了获得更准确的估计结果和最短的处理时间，几乎对随机采样估计器的所有阶段都进行了研究，从而产生了大量的RANSAC变体。对于加速，一种特别成功的策略是结合额外的先验信息，例如匹配分数 [9] 和对应的空间连贯性 [24,27]，以增加命中全内点子集的概率。验证阶段也进行了修改以避免不必要的计算[10,25]。然而，由于随机性，效率和鲁棒性（或准确性）往往是相互矛盾的。从优化的角度来看，文献中存在一组称为共识最大化的方法，用于精确的几何估计[3,4,18,22]。与随机采样技术相比，这些方法将几何估计问题转化为优化问题，其中技术难度变成了高度非凸的目标。基于不同的理论保证，它们大致可以分为两类：全局方法和局部方法。然而，尽管理论最优性具有良好的特性，但全局方法通常计算量要求较高。虽然本地方法速度更快，但对于实时应用程序来说仍然太耗时。

在本文中，我们还从优化的角度考虑几何估计。不同的是，我们的目标是探索点对应的内在线性结构。这种线性结构实际上之前在文献中已经讨论过，并且可以追溯到经典的直接线性变换（DLT）[17]。正如 DLT 揭示的那样，几何估计任务可以通过求解从内点导出的一组（可能是超定的）线性方程来完成。考虑到噪声，DLT 找到了最小化平方误差的解决方案。在实践中，DLT 总是与随机采样技术结合使用，因为它无法处理异常值。在我们的方法中，我们进一步探索了充分利用线性结构的方向。我们对线性结构进行了更深入的分析，并使用基于 1 的异常稳健目标来挖掘它，该目标显着扩展了 DLT。由此产生的优化问题被证明是鲁棒子空间恢复的特殊形式[20]，它允许应用最近开发的高效且理论基础良好的方法。

总之，我们的贡献包括三个方面。(1)提出了一种新颖的方法，以离群鲁棒目标挖掘点对应的内在线性结构进行几何估计。与目前最先进的方法相比，该方法在优势异常值的情况下具有更好的效率和更好的准确性。（ii）对传统方法中讨论的线性结构进行了推广，并提出了几种基于鲁棒子空间恢复的新算法来利用它。（iii）通过与当前最先进的方法进行比较，我们在现实世界的图像上展示了我们的方法，用于基本和单应性估计任务。

2 相关工作

文献中提出了大量的方法来解决几何估计问题。由于涵盖所有分支的全面审查是详尽无遗的，超出了本文的范围，因此在本节中，我们仅总结与本文相关的密切相关的工作。

由于几何估计鲁棒性的实际需求，随机抽样技术仍然是最流行的范例。在过去的几十年里，人们提出了大量的创新来提高普通 RANSAC 的效率和准确性。为了加速，已经提出了许多有效的采样技术，利用特征对应中可用的先验信息。例如，作为先验，NAPSAC [31] 和 GroupSAC [27] 中利用空间相干性，EVSAC [16] 和 PROSAC [9] 中利用匹配分数。此外，改进模型验证阶段也被证明对于效率问题至关重要[10,25]。还有一些努力已被证明能够获得更准确的估计结果。这些方法包括 MLESAC [32] 和 MSAC [30]，其中模型质量通过最大似然过程进行评估。局部优化 RANSAC (LO-RANSAC) [11,19] 提出了一个更具启发性的想法，其中引入局部优化步骤来完善迄今为止最好的模型。通过引入更多的内点进行估计，可以减少噪声引起的偏差，并且可以期望得到更准确的模型。最近 Graphcut RANSAC [1] 扩展了这个想法。值得注意的是，通过结合最有希望的改进，USAC [29] 被认为是最先进的 RANSAC 变体。

从不同的角度来看，几何估计问题可以并且已经在优化框架中通过共识最大化的概念得到解决。共识最大化目标源于RANSAC的模型质量评估策略，即计算残差低于给定阈值的对应数量。在这方面，RANSAC 可以被视为一种随机求解器，无法保证解的质量。因此，各种方法试图开发算法来搜索具有全局最优性保证的解决方案[3,4,6,8,14,22]。然而，由于问题的根本棘手性，这些方法的计算复杂度通常过高。最近开发了更快的基于优化的方法，但没有全局最优性[7,18,28]，但与随机采样技术相比仍然需要过多的时间。

我们的方法遵循与上述两类工作不同的观点。我们专注于探索 DLT 中已使用了数十年的内在线性结构。 DLT算法广泛用于几何估计，其无异常值数据仅受噪声污染。但实际情况并非如此，因此 DLT 总是与随机抽样技术结合使用。此外，正如将要证明的，探索线性结构所产生的问题与鲁棒子空间恢复有关。该领域的最新进展[21,23,33]在处理更多退化案例（例如显性异常值）方面显示出巨大潜力。我们建议感兴趣的读者参考最近的调查[20]以获得全面的了解。

3 方法

假设给定一组对应关系 S = {(xi, x′i)}iN=1，其中有多个异常值，其中 xi = (xi, yi, 1)T 且 x′i = (x′i , yi', 1)T 是表示两幅图像中特征点的齐次坐标的列向量。我们的目标是恢复底层的几何结构，例如对于许多 3D 视觉应用至关重要的基本矩阵 F ∈ R3×3 或单应矩阵 H ∈ R3×3。

3.1 DLT 简介

我们首先简要回顾一下经典的 DLT 算法，该算法通过挖掘数据中内在的线性结构，为几何估计提供了一种有效的解决方案。点对应的线性结构表明，可以通过求解由数据导出的线性系统来估计几何模型。下面我们将分别讨论基础矩阵F和单应性变换H的DLT解。基本矩阵 F 控制两个摄像机视图中最一般的极线约束。该约束可以表示为：

当特征点靠近平面或相机运动为纯旋转时，适用于单应性变换。这个变换可以用向量叉乘来表示：

对于估计 F 和 H 的两种情况，它都简化为求解 DLT 中的超定线性系统：

其中 M ∈ RK×D 表示从对应关系导出的数据矩阵，z ∈ RD 表示参数的列向量。对于基本矩阵估计，我们有 M = [a1, a2, . 。。 , an]T 且嵌入为

解是M的最小奇异值对应的右奇异向量。

3.2 鲁棒泛化

在无异常值的情况下，DLT 能够给出接近最优的结果。因此，很自然地要问：我们能否扩展 DLT 的框架来应对异常值？在本节中，我们尝试给出肯定的答案。

首先，我们考虑估计的理想情况，其中对应关系不存在噪声。在这种情况下，我们可以通过考虑异常值来重新表述 DLT：

基于 0 的函数 ‖Ez‖0 只是计算有多少点不符合线性结构。由于异常值不存在线性结构，因此（6）的解通常是地面实况估计。然而，已知 0 最小化在计算上很困难，因此我们将其替换为以下 1 最小化问题：

从这个意义上说，几何任务变得可以数值求解，并且也适用于受噪声污染的数据。 (7) 和 DLT 之间的关系很清楚，即 DLT 解决方案等于对 (7) 使用基于 2 的目标。这解释了 DLT 的局限性，因为已知 2 目标对异常值很敏感。

从数学上讲，（6）和（7）可以看作是一个超平面拟合问题。事实上，(7) 的确切形式最近在鲁棒子空间恢复的文献中得到了研究[33,35]，其中超平面拟合是当数据的内在维度 d = D − 1 时的特殊情况。鲁棒性具有已经从理论上证明了，它粗略地表明，在对离群值分布的某些假设下，式（7）的估计任务甚至可以容忍 O(m2) 个离群值，其中 m 表示离群值数量。

请注意，(7) 是非凸的（因为可行区域是球体）并且是非光滑的（由于基于 1 的目标），因此解不是平凡的，需要额外小心。幸运的是，已经提出了对（7）的数值求解器的一些努力。在[33]中，（7）被放松为一系列线性规划，这保证了对全局最优的有限收敛。然而，这种方法的计算成本很高。或者，[33]提供了一种基于迭代重新加权的最小二乘方法，该方法更有效，但没有理论保证。 [35]中提出了一种基于投影次梯度下降的算法。该算法甚至更高效，仅涉及矩阵向量乘法。

由于对低计算时间的需求通常主导几何估计的最优性保证的需求，因此我们采用基于投影次梯度下降的算法。此外，需要澄清的是，由于松弛策略的原因，(7) 的（全局）解在噪声下可能并不理想。事实上，已经证明，全局最小化器会受到与噪声水平成正比的扰动（同时仍然容忍 O(m2) 异常值）[13]。因此，解决方案通常是粗糙的，需要通过后处理进行细化，正如我们将在第 4 节中讨论的那样。 3.4.我们用算法 1 中的 (7) 概述了所提出的几何估计方法。

3.3 线性结构的扩展探索

尽管（7）中的稳健公式鼓励了几种有效的几何估计算法，但在处理现实世界的损坏数据时仍存在一些关键问题。由于问题固有的非凸性，局部收敛算法很容易陷入弱局部最优，无法给出有意义的结果，尤其是当数据存在强噪声或严重异常值时。这些促使我们重新思考这个问题，以应对实际应用带来的巨大挑战。

具有仿射相机的线性结构。首先，让我们从仿射相机模型的简单案例开始，展示如何利用其线性结构。如果假设两个视图都是由仿射相机拍摄的，则两个匹配的特征点通过仿射变换相关：

affine(仿射的)

类似于 DLT 的单应性估计情况，利用该结构的一个直接解决方案是将其转换为超平面拟合问题，具有以下嵌入：

给定 n ≥ 3 个对应关系，使用 (7) 即可轻松解决该问题，其中 M = [c1T , c2T , . 。。 , cTn ]T 和 z = [a11, a12, a13, a21, a22, a23, 1]T 编码仿射参数。

请注意，使用（7）的几何估计实际上提出了子空间恢复问题，数据被噪声和异常值损坏。从子空间学习理论来看，众所周知，相对维度，即d/D，数据d的固有维度与环境空间D的维度的商，对学习任务的难度起着重要作用。一般来说，当相对维度较小时，子空间学习问题明显更容易。为此，我们接下来提出了一种利用线性结构的替代公式，需要处理较低的相对维度。

由于仿射变换仅涉及对应数据的线性项，因此我们考虑以下嵌入

由于 A' 显然是 2 阶，这表明 5 维嵌入 d1, d2,... 。。 , dn 存在于维度不超过 3 的线性子空间中。

上述观察表明解决以下 3 维子空间恢复问题：

由于 A' 显然是 2 阶，这表明 5 维嵌入 d1, d2,... 。。 , dn 存在于维度不超过 3 的线性子空间中。上述观察表明解决以下 3 维子空间恢复问题：其中 M = [d1, d2, . 。。 , dn]T , v = [v1, v2] 表示两个正交单位向量的矩阵，I 表示单位矩阵，‖ · ‖1,2 表示输入矩阵各行的欧氏范数之和。 (14) 的相对尺寸为 3/5，远小于超平面拟合情况 (10) 所示的 6/7。这使得这个问题变得更容易学习。

(14) 背后的基本原理是找到由内点嵌入跨越的线性子空间的正交补的两个基。这可以通过标准的鲁棒子空间恢复方法来解决，例如[21]，正如综合调查[20]中所讨论的。在本文中，我们采用更有效的策略来迭代搜索两个碱基。在第一次迭代中，进行超平面拟合算法来找到第一个基础。在第二次迭代中，该过程与超平面拟合类似，但具有额外的投影步骤来找到第二个基础。额外的投影步骤保证第二个基础与第一个基础正交。具体来说，如果我们获得第一个基 v1，其正交补集的投影应该是 I − v1v1T ，那么第二个基 v2 应该投影到它上面，为 v2 = (I − v1v1T )v2 = v2 − v1v1T v2 。算法 2 概述了求解 (14) 的算法。

扩展线性结构。从上面的讨论中，我们可以得出结论，对于仿射相机，该问题允许利用线性嵌入 di 的更简单的解决方案。因此，一个自然的问题是，算法 2 是否可以扩展到不严格满足仿射相机假设的更一般场景？接下来，我们尝试正面回答这个问题。

回答这个问题，首先要回答的是，在一般场景下我们可以从算法2中得到什么？可以从不同的角度来分析，下面我们会详细解释。

第一个讨论是基于《Sect.》中的一些重要结论。 [17] 的 6.3。我们将 xp 表示来自一般有限投影相机的测量图像特征点，将 xa 表示同一 3D 点的虚拟图像特征点，但来自无穷远的虚拟相机。可以推导出 ̃xp 和 ̃xa 之间的关系如下：

其中x0表示主点，̃xa、̃xp和̃x0表示非均匀化坐标的行向量，Δ和d0可以理解为给定成像场景的深度浮雕和平均深度。假设我们给定两个通用相机的对应关系 (xp, x′p)，则对应的线性嵌入为 d = [ ̃xp, x ̃′p, 1]T 。根据(15)中的观察，d可以从另一个角度理解： d = [ ̃xa + , x ̃′a + ′, 1]T ，其中 = Δ d0 ( ̃x0 − ̃xp) 且'= Δ d0 ( ̃x'0 - ̃x'p) 表示与 Δ d0 成比例的噪声。由于 xa 和 x′a 通过仿射模型相关，如果 Δ d0 足够小，由于基于 1 的目标的抗噪声特性，我们仍然可以使用具有简单线性对应关系嵌入的算法 2 来利用该结构。在这种情况下，如果相机远离场景（d0 大），则大多数内点可以通过算法 2 检测到。否则，检测到的内点通常会靠近呈现小深度浮雕（Δ 很小）的平面，并且可能仅包括真实内点的子集。

从不同的角度来看，我们也可以从模型本身来解释结果。虽然仿射模型不能准确描述透视平面的平面变换，但它可以看作是非线性单应性模型的线性近似。这表明仿射模型至少可以局部应用于对应关系。在这种情况下，可以通过算法2来检测一幅图像中空间相邻的内点。

从上面的讨论得出结论，我们可以看到，在一般场景下，算法2可以用于检测至少一部分内点。这是因为基于 1 的目标对近似引起的误差更不敏感。然而，检测到的内点与高质量模型之间仍然存在差距。在本文中，我们表明可以通过应用局部细化技术来找到最佳模型来填补这一空白。这导致了以下扩展。

(1)单应性估计。如上所述，当场景符合更一般的单应变换时，算法 2 不是理想的选择。然而，我们可以预期算法 2 至少可以检测到内点的子集。在这种情况下，我们选择随后运行局部优化步骤以包含更多内点并恢复真实的单应性。详细信息将在我们的后处理过程中讨论。 3.4.一些说明性的例子在第 3 节中给出。 4.1.该算法在算法 3 中概述。

(2) 基本矩阵估计。对于基本矩阵估计任务，如果我们只有一组仿射或单应性相关对应关系，通常是无法解决的[12]。为此，我们建议检测两组不相交平面的内点，如顺序 RANSAC 方法 [34]。在第一次迭代中，通过算法2检测到一组内点，随后排除第一组内点以检测第二组内点。最后，可以根据两组组合的内点来实现基本矩阵估计。一些说明性的例子在第 3 节中给出。 4.1.算法 4 概述了该算法。

图1：我们的 SRE 的一些说明性示例。对于图像对，为了可见性，仅显示 100 个对应关系的子集。每对还显示一个运动场，其中每个箭头的头部和尾部对应于两个图像中特征点的位置。识别出的内部值用蓝色绘制，异常值用黑色绘制。（网上彩图）

3.4 实现细节

为了提高数值稳定性，对应数据被映射到嵌入中，然后在由我们的算法处理之前标准化为单位范数。

后处理。获得内点集 I 后，由于检测到的内点可能仍包含大量异常值，为了获得更好的精度，我们从 I 中运行固定的 100 个样本，并使用 DLT 从中导出模型（单应性、基本矩阵）。每个模型都在原始对应集上进行评估，并且每个迄今为止最好的模型都通过局部优化步骤进行细化[19]。最后，我们取共识最大的最佳模型作为输出估计结果。请注意，与随机采样技术一样，该策略也需要预定义的异常值阈值。

4 实验结果

在本节中，我们研究了所提出的方法在几何估计任务的真实图像数据上的性能。我们将我们的方法命名为子空间恢复估计器（SRE）。一些说明性示例如图 1 所示

图2：用于单应性估计的 SRE 的homogr 的说明性示例。第一行表示通过算法 2 检测到的内点，第二行表示经过后处理以查找单应性之后的内点。

单应性估计。采用广泛使用的homogr1和EVD2数据集。 homogr 数据集包含 16 个基线相对较短的图像对，而 EVD 数据集包含 15 个经历极端视图变化的图像对，即宽基线。两个数据集都提供了许多手动选择的真实对应关系，用于模型评估。此外，我们还收集了 20 对遥感图像来创建 RS 数据集。由于遥感中成像设备距离场景很远，因此几乎完全符合仿射相机模型。 RS数据集具有较高的异常值比例（平均在80%以上）的特点，可以检验每种方法在极端异常值下的稳健性。该数据集的内点是手动标记的。

基本矩阵估计。采用广泛使用的kusvod23和AdelaideRMF4数据集。 kusvod2包含16个弱视角和强视角的图像对，并为模型评估提供了许多真实的对应关系。 AdelaideRMF 数据集包括一组配备了手动标记的关键点对应关系的校园建筑图像对，我们使用其中仅经历一次运动的 19 对子集。由于相机距离建筑物较远，图像对通常透视较弱。

4.1 线性嵌入的定性分析

我们的 SRE 涉及几种几何估计策略，基于不同对应嵌入的利用，即（4）、（5）和（11）。虽然（4）和（5）是有根据的，因为它们是经典 DLT 的衍生物，但线性嵌入（11）的功效需要针对一般场景进行进一步研究。

使用线性嵌入进行单应性估计（即算法 3）的说明性示例如图 2 所示。可以看出，检测到的inlier可能只是真实inlier的一个子集，甚至包括一些异常值。然而，经过涉及局部优化步骤的后处理，可以找到所有的内层，然后恢复真正的单应性。图 3 显示了使用线性嵌入的基本矩阵估计（即算法 4）的说明性示例。显然，对于算法 2 的单次运行，检测到的内点通常靠近平面。然而，通过迭代运行算法 2 来找到第二组内点并合并两组，内点集就足够多样化，从而在后处理后获得准确的估计结果。请注意，检测到的内点不一定靠近 3D 对象的自然平面，实际上，它们也可以按 3D 空间中的虚拟平面进行分组。

图3：用于基本矩阵估计的SRE的kusvod2的示例。前两行表示算法2检测到的第一组和第二组内线。最后一行表示后处理后找到基本矩阵的内线。

4.2 基本和单应性估计

在我们的 SRE 中，基于 DLT 中的基本矩阵和单应性估计的嵌入，即（4）和（5），可以像算法 1 一样使用。线性嵌入，即（11），可以用于算法 2。另一个有趣的嵌入是 (10)，它的使用方式与算法 1 类似。我们将这些变体分别表示为 SRE-F、SRE-H、SRE-A 和 SRE-At。对于SRE-F，检测到的内点直接用于单应性和基本矩阵估计。对于SRE-H、SRE-A和SRE-At，进行单次运行以进行单应性估计，并进行两次运行以找到两组内点以进行基本矩阵估计。

我们将我们的 SRE 与基线 RANSAC [15]、最先进的方法 USAC [29] 和 MAGSAC [2] 进行比较。参数根据原论文设置。 RANSAC、MAGSAC 和 USAC1 的最大试验次数设置为 5, 000，USAC2 的最大试验次数设置为 50, 000。对于我们的 SRE，我们根据经验将阈值设置为平均残差的 1/5 以识别内点。所有方法的异常值阈值均设置为 2 个像素。

我们使用给定内层的平均几何误差w.r.t.估计模型作为评价指标。由于失败的模型会导致不可靠的统计数据，我们排除失败的情况来计算平均误差(e)，并报告失败的比例(f)。几何误差计算为桑普森距离。为了确定失败的模型，我们使用两个阈值，即5像素（e1, f1）和10像素（e2, f2）。如果估计模型的平均几何误差大于阈值，则认为该模型失败。对于每种方法，我们报告在每个图像对上运行100次的统计数据。

表 1. 定量评估。数据集、问题、图像对的数量和指标显示在前三列中。其他列显示 100 次运行的平均几何误差 (e) 和失败比例 (f)，其中下标 1 和 2 分别表示以 5 和 10 像素作为确定失败模型的阈值的结果。给出了平均处理时间（以毫秒为单位），即 t，以及所有数据集的汇总统计数据，即全部。粗体表示最好的结果。

评价结果见表1。可以看出，RANSAC相对于USAC和MAGSAC具有很强的鲁棒性，故故率较低。然而，对于几何估计任务来说，它通常不太准确并且非常耗时。 USAC 统一了基于随机抽样的估计器的许多重要进步，并在准确性和效率方面实现了显着改进。然而，鲁棒性似乎受到损害，并且其在具有挑战性的数据集（即 EVD 和 RS）上的性能非常有限。 MAGSAC 的提出是为了消除指定异常值阈值的需要。它在 EVD 数据集上表现良好，但是，其鲁棒性在其他数据集上并不一致，并且无法处理具有挑战性的 RS。对于我们的 SRE 的所有四种变体，效率都具有优势并且可与 USAC 相媲美。具体来说，SRE-F和SRE-H往往更准确，但鲁棒性并不占优势。 SRE-A 的性能大大优于 SRE-At，因为诱导子空间恢复问题更容易解决。总的来说，我们的 SRE 最有效的变体是 SRE-A。平均而言，它是最稳健的，并且相对于 USAC 来说效率更高，精度更高。

总而言之，SRE-A 是我们 SRE 的所有变体中表现最好的。与当前最先进的几何估计算法相比，它是最稳健且具有最佳精度的算法。效率可与最快的 USAC 相媲美。 SRE-A 的一个很好的特性是它对异常值的鲁棒性，正如 RS 数据集所证明的那样，它显示出明显更好的结果。

4.3 对离群值率的敏感性

由于我们算法的目标是在存在离群值的情况下进行几何估计，所以一个简单的问题是它对离群值率的敏感性。为了进行调查，我们使用 AdelaideRMF 数据集，因为内部对应关系已注释。我们通过匹配两个图像中的两个随机点来生成异常值对应，并通过向内部值添加一些随机生成的异常值来控制异常值率。在实验中，每种算法在每个实例上运行 100 次，以得出平均性能。我们使用性能最好的 SRE-A 和最大试验次数为 50, 000 次的 USAC 算法 (USAC2) 进行比较。采用失败比例（以5个像素为阈值）和运行时间进行评估，结果如图4所示。

从图 4 的结果中，我们可以看到我们的 SRE-A 在鲁棒性（故障比例较小）和效率方面都优于 USAC。我们的方法在极端异常值（高达 95%）下仍然可以工作，而 USAC2 在这种情况下往往会失败。此外，我们方法的效率不受异常值率的影响。这是一个显着的优势，因为 USAC 的运行时间随着异常值率的增加呈指数增长，直到接近最大试验次数。