点击上方“CVPaper”，选择加"星标"或“置顶”
顶刊论文解读，第一时间分享
题目：Accelerating Globally Optimal Consensus Maximization in Geometric Vision加速几何视觉中全局最优共识最大化
作者：X. Zhang; L. Peng; W. Xu; L. Kneip
摘要
在几何计算机视觉领域，基于分支定界的共识最大化（Consensus Maximization, CM）因其能够检索到受异常值影响的几何问题的全局最优解而脱颖而出。然而，尽管发现此类解具有很高的科学价值，但由于其计算复杂性随着问题维度的增加而呈指数级增长，其在实际场景中的应用常常受到限制。在这项工作中，我们提出了一种新颖的通用技术，允许我们在处理n维问题时，在n-1维空间上进行分支。通过应用高效的区间刺探技术，可以在全球最优解中解决剩余的自由度。尽管由于额外需要解决排序问题，每个单独的界限推导计算起来更加困难，但实际上减少的区间数量和更紧的界限导致所需迭代次数显著减少。除了对方法的抽象介绍之外，我们还展示了它在四个基本的几何计算机视觉问题上的应用：相机重投影、相对相机姿态估计、点集配准和旋转与焦距估计。通过我们详尽的测试，我们展示了在某些情况下超过两个数量级的显著加速因子，从而增加了全局最优共识最大化器在在线应用场景中的可行性。
关键词
I. 引言
共识最大化（Consensus Maximization, CM）在几何计算机视觉领域扮演着重要角色。给定一系列成对的对应关系，任务是找到一个几何上一致的解决方案。这包括相机重投影和双视图几何等重要例子，其中我们有3D世界点与2D图像点之间的输入对应关系，或者简单地说，是来自两个不同图像的2D图像点。
本文中，我们提出了一种新颖的通用技术，允许我们在n维问题的n-1维空间上进行分支。剩余的自由度可以通过应用高效的区间刺探技术，在每个界限计算中全局最优地解决。尽管由于额外需要解决排序问题，每个单独的界限推导计算难度较大，但在实践中，减少的区间数量和更紧的界限导致所需的迭代次数显著减少。除了对方法的抽象介绍外，我们还展示了其在四个基本的几何计算机视觉问题上的应用：相机重投影、相对相机姿态估计、点集配准和旋转与焦距估计。通过我们详尽的测试，我们展示了在某些时候超过两个数量级的显著加速因子，从而增加了全局最优共识最大化器在在线应用场景中的可行性。
在数据中存在异常值的情况下，几何计算机视觉问题通常变得更加复杂。大多数求解器采用最小二乘目标，这些目标很容易受到异常值的干扰。在受异常值影响的情况下，目标因此变为最大化误差低于预定义误差阈值的对应关系数量，该阈值通常选择为数据自然噪声的函数。我们称这为共识最大化（CM）问题。
数学上，我们可以如下表述CM问题。设 是从待解决问题推导出的残差函数。 表示包含所需解变量 的约束集，而 是包含数据样本 的数据域。样本数据的整个腐败集合由 给出。给定某个阈值 ，如果 ，则样本 被称为内点，否则为异常点。CM的一般形式随后由优化问题给出：这里 表示集合中元素的数量（基数），而 可以视为相对于 的内点集。鉴于CM的基于计数的性质，目标通常是离散的，并且不能再使用传统的优化方法来解决。相反，多年来提出了两种CM方法：随机化和确定性。随机化共识最大化通过迭代随机抽样小的子集来生成最小二乘求解器的模型假设。在每次迭代中，我们找到所有满足的对应关系，从而确定与计算出的假设一致的内点子集I的基数。如果采样到一个无异常值的子集，我们倾向于找到一个良好的假设和一个接近真实内点比率的内点比率。终止标准通常取决于期望的和当前最佳的内点比率。该方法返回在迭代过程中找到的最大基数内点子集对应的解。尽管随机化CM方法（如RANSAC [1]）听起来很简单，但它们已成为鲁棒几何模型估计的里程碑，并且至今仍被广泛使用。然而，随机化CM无法保证在有限次数的迭代中获得全局最优解。RANSAC达到预定义置信水平所需的迭代次数随着异常值比率的增加而显著增加。这就轮到确定性CM发挥作用了 [2], [3], [4]。与通过随机化寻求共识不同，确定性方法穷尽地搜索整个解空间，从而保证全局最优性。存在几种全局搜索范式，例如分支定界（Branch and Bound, BnB）[2]、A*树搜索[3]和二分法[4]，仅举几例。全局搜索提供了一个准确的解决方案，并且能够处理极端的异常值比率。尽管计算量大，但确定性CM仍然具有关键的科学价值，特别是作为在没有真实解可用的场景中测试替代方法（例如随机化CM方法）的参考实现。我们通过引入一种新方法——加速确定性共识最大化（Accelerated Consensus Maximization, ACM），来提高确定性CM的计算效率，这种方法可以广泛应用于加速基于BnB的全局最优CM，而不必太依赖于所解决问题的具体性质。这一贡献很重要，因为随着问题维度的增加，全局最优的确定性方法很快变得计算上不可行。本文的详细贡献和结构如下。贡献
- 我们提出了ACM，一种通用且灵活的技术，用于加速确定性共识最大化。该方法通过在BnB分支的空间上执行1自由度（1-DoF）减少。剩余维度使用区间刺探技术高效且全局最优地解决。
- 通过这种技术获得的界限不仅计算速度更快，而且更紧。
- 我们将ACM应用于5个不同的问题，涵盖了从1维到4维的场景，并获得了2倍至100倍的速度提升（有时甚至超过300倍）。
论文结构
本文的其余部分组织如下：第II节回顾了关于随机化和确定性共识最大化方法以及提高其计算效率的现有方法的重要相关文献。第III节回顾了计算机视觉中的分支定界方法和区间刺探的关键技术。第IV节包含我们的核心贡献：加速共识最大化。它介绍了1自由度降维的主要技术、方法适用性的要求以及计算复杂度等重要属性。接下来，第V、VI、VII和VIII节分别介绍了1维IMU支持的相机定位问题、2维平面运动假设下的相对姿态问题、3维基于对应关系和无对应关系的点集配准问题以及4维旋转和焦距估计问题的应用。我们在第IX节以讨论结束。III. 预备知识
在介绍我们加速的共识最大化方法之前，需要涵盖一些预备知识：区间映射、分支定界算法以及区间刺探。通过纳入这些基础知识，我们旨在为我们的发现建立一个基础。在讨论分支定界算法中用于共识最大化问题的推导时，区间映射始终是一个有用的工具。处理区间可以使约束放松。另外两个预备部分集中在分支定界算法上。前者提供了主要的算法结构，后者提供了使搜索空间减少1维的核心技术：区间刺探。定义1 (区间映射 [47])：设 是一个区间。那么区间操作定义为：A. 分支定界
如文献 [28] 所示，分支定界（Branch and Bound, BnB）是一种确定性范式，通常用于最大化共识并找到几何计算机视觉问题的全局最优解。BnB 的主要思想是递归地在解空间上进行分支，并计算所有候选子区域上内点子集最大基数的界限，然后剪枝那些上界小于当前最大下界的立方体。算法持续分割立方体，直到界限足够锐利，即下界接近上界。一般来说，BnB 的最优性源于它是一种穷尽搜索方法，使用界限操作来剪枝无用的分支。然而，BnB 通过早期剪枝无用的分支（即潜在的大子区域）而不是检查所有子区域到叶级别，从而比蛮力搜索获得效率。算法1提出了一种使用Best-FirstSearch的基本BNB流水线。它有几个组成部分：立方体初始化(第1行)、立方体细分(第16行)、下界操作(第3行和第8行)和上界操作(第4行和第17行)。下面将介绍这些步骤中的每个步骤。立方体初始化：立方体初始化（算法1的第1行）指的是构建一个初始的立方体或超立方体 ，在该立方体上BnB算法搜索共识最大化目标（1）的全局最优解。因此， 应该被选择为确实包含全局最优解。通常，这可以通过考虑解决的问题的性质或数据分布来相对容易地完成。例如，对于角度搜索，可以设置[−π, π]作为初始1维立方体。立方体分割：在每次迭代中（算法1的第6行），BnB从优先队列（第7行）中取出一个立方体或超立方体 并将其分割成更小的立方体（第16行）。分割规则通常选择将立方体分成 个全等的子立方体。在实践中，为了平衡精度和运行时间，使用额外的停止条件，例如限制最大分割深度 或设置容差 来限制子立方体的最小直径。BnB - 下界：给定当前从优先队列中取出的立方体 ，我们将其中心点定义为 。然后，在 上的（1）的一个平凡下界就出现了，作为满足 的点的数量，因为对于任意的 和全局最优解 成立：下界计算发生在第8行。注意，立方体 中的任何点都定义了一个有效的下界，中心点被选择出于方便。BnB - 上界：上界通常是通过放松约束获得的。设 是一个给定的立方体，设 是约束函数，其在 上的界限可以通过区间映射（定义1）计算。注意，与通常不同，我们考虑区间的输入，这意味着区间的映射仍然是一个区间。不失一般性，记 在 上的下界和上界分别为 和 ，即回想一下（1）中的约束和残差的特征，即 。然后，当没有有效的解 在立方体 中时，情况是 或 。
因此，通过计算提供可能包含解的区间的点，我们可以得到一个有效的上界，如下所示：放松是通过这样一个事实实现的，即所有有效的解区间都有助于内点计数，尽管在现实中它们可能不会相互交叉。注意，一旦为每个 推导出上界和下界 和 ，上界（5）就可以在线性时间内计算。B. 区间刺探
假设我们有一个区间集合 。区间刺探问题的目标是找到可以被刺穿器 相交或以更形象的方式，可以被刺穿的区间的最大子集。它可以表述如下：区间刺探问题（IS）（6）可以简单地在 时间和 空间内解决，如算法2所示。它在 [48] 中作为窗口查询的子问题被研究，可以确定性地并高效地使用高级数据结构解决，例如区间树、段树和优先树。自适应投票从直方图投票中推广而来，具有类似的想法，但其时间复杂度为 [25], [27], [33], [34]。在最近的实践中，IS被发现是优化中一个强大的工具 [20], [22], [35], [36]。特别是，[20], [35], [36] 使用区间刺探来高效解决内部问题，这是区间刺探如何帮助加速算法的一个指示性示例。IV. 加速共识最大化 (ACCELERATED CONSENSUS MAXIMIZATION)
在本节中，我们介绍了我们的方法——加速共识最大化（Accelerated Consensus Maximization, ACM）。与在原始的n维空间中搜索不同，ACM在n-1维空间中进行搜索和分支，并使用区间刺探（Interval Stabbing）处理剩余的变量。从实现的角度来看，ACM使用与算法1相同的分支定界（Branch and Bound, BnB）图，但与普通的BnB不同，在第1行中，ACM初始化一个(n-1)维的立方体。在第8行和17行中，它设计了ACM的界限操作。ACM的主要修改在于将界限操作调整为适应(n-1)维立方体。接下来，我们将首先介绍ACM的一般思想，然后展示其全局最优性。最后，我们将分析其时间复杂度。为了更直观的理解，我们使用普通BnB来指代上文中提到的标准BnB。请注意，这里的一般思想是为特定问题提供基本的直觉，细节可能因具体问题而异。A. 方法的核心
对于每个样本，适当定义的约束函数f可以用来反向找到b的所有可能区间的并集：图1给出了一个视觉示例。注意，样本在右侧表达式中是缺失的，因为我们使用索引i来表示si和区间并集之间的隐含依赖关系。换句话说，的确切形式取决于si和约束函数f。虽然在我们的一般讨论中，很难明确算法化这种依赖性，但我们将看到一旦f和si在具体应用中被指定，如何计算（见第五、六、七和八节）。假设所有区间在(8)中是分离的，我们可以通过合并区间来考虑。利用(8)中的等价关系，每个约束最终变为某种区间约束，因此一维CM问题(7)归结为区间刺探问题，如(6)所示。通过这种方式，我们得到了关键的观察结果：一维共识最大化可以直接通过区间刺探来解决，它找到了全局最优解，而不需要像普通BnB那样迭代搜索解空间。请注意，为了方便讨论，在下面，我们将假设f(b, s_i) < ε的解只导致一个区间而不是像(8)中所示的区间并集。请注意，这种概念上的简化并不影响实现。如果有区间并集，那将意味着区间刺探必须在额外的区间上执行。让我们通过将上述观察结果推广到n维共识最大化问题来进行。回想一下一般的共识最大化问题(1)。普通BnB通过在n维空间中搜索b来解决它。我们提出加速共识最大化（ACM），在(n-1)维空间中搜索n-1个变量，并使用区间刺探来解决剩余的1个变量。如图2所示，由于搜索空间的降低维数，ACM分支到的数量可能更少的子立方体，这使得它比普通BnB显著更快地收敛。记。不失一般性，我们假设ACM在b的前个变量上进行分支，我们将它们记为。设Cplain表示n维空间中的普通BnB立方体，CACM表示相应的ACM立方体在维空间中。如图2所示，CACM可以被视为Cplain减去最后一个维度。接下来，让我们引入一个通用的函数表示，其中bn方便地从中分离出来。它由下式给出：- (ACM - 联合) 一旦给定，如何反向约束函数f以获得类似于(8)中的区间？
- (ACM - 界限) 如何推导出ACM的目标的上下界限（回想一下，ACM是一种基于BnB的方法）？
对于(ACM - 联合)，我们原则上可以使用数值方法找到的所有根，然后从这里恢复区间。然而，在大多数实际场景中，我们可以封闭形式地解这个方程。这种封闭形式是问题特定的，所以我们现在不会讨论它，而是稍后给出具体的例子。计算(ACM - 界限)稍微复杂一些。然而，正如我们将要展示的，对函数的形式的温和假设将使我们能够再次使用区间刺探，并在分支剩余的n-1个变量的同时，一维最优地解决。ACM - 下界：如上所述，对于任何给定的 ∈ CACM，我们可以设法找到每个数据样本si的bn区间：因此，可以通过在上执行区间刺探来找到一个有效的下界：这里的不等式是由这样一个事实推导出来的：随机选择的b1:n-1总是比最佳解b*1:n-1差或相等。注意，有趣的是，对于相同的问题，ACM的下界比普通BnB的平凡下界更紧，如图3所示。ACM - 上界：接下来，让我们假设所有的在上都是单调递增的。这是一个温和的假设，因为1) 单调性只需要在CACM中的b1:n-1的区间上，而该区间随着分支的进行而逐渐减小；2) 如果一些或全部的在上单调递减，推导同样简单，因此事实上，单调性本身是推导的充分条件。在适当地使用区间算术对内部函数hj在CACM上进行界限之后，我们可以得到：对于每个样本si。然后，在CACM上，一般约束(1)以及残差的基本情况转化为：再次考虑到前n-1个变量是给定的，区间(14)可以这样放松：并且使用数值或封闭形式的解析解，这些不等式可以再次解决，以识别每个样本si的有效区间bn ∈ [b_l_ni, b_r_ni]。通过在这些区间上执行区间刺探，可以找到ACM的有效上界，从而得到以下上界：再次，单调性的要求并不是一个严格的限制。单调性仅在当前界限评估的子区域上需要。实际上，即使对于更复杂、非线性的函数，在实践中通常也可以实现至少是片段的单调性。为了更好地说明，我们提供了两种约束函数f的例子，并介绍了如何分离bn。然后，如普通BnB的共同上界所讨论的，我们可以通过计算可能的区间来放松CM的目标：其中我们可以为每个数据样本si推导出bn在CACM上的区间。因此，可以通过在{[b_l_ni, b_r_ni]}上执行区间刺探来找到一个有效的上界，即：示例2:假设f(b, s_i)可以分解为两部分的乘积：对于任何给定的CACM，我们可以设法找到h_1(CACM|s_i)的区间：并假设g_1(bn|s_i)的有限范围区间是大于或等于零的。不失一般性，假设g_1(bn|s_i)大于或等于零。同样，我们可以通过计算可能的区间来放松CM的目标：再次，通过在{[b_l_ni, b_r_ni]}上执行区间刺探，可以找到一个有效的上界。接下来的第五、六和七节将应用ACM解决具体的几何问题，这将进一步解释其实际应用。B. 时间复杂度分析
既然普通BnB和ACM都是全局最优的，让我们继续比较它们的计算效率，并分析哪一个可能更快地收敛到全局最优解。注意，为了在每次迭代中计算上下界限，普通BnB使用O(M)时间，而ACM调用了区间刺探子程序，因此消耗O(M log M)时间。额外的log M因子对ACM来说似乎是一个轻微的劣势，但实际上这是ACM为了巨大好处而付出的代价：ACM被要求在一个更小的空间上分支，并且产生更紧的界限，从而在显著较少的迭代次数内收敛。以下基本命题从数学上巩固了我们的主张：命题1:运行普通BnB（分别ACM）算法，使用将立方体分割成2^n （分别2^(n-1)）个全等子立方体的分割规则，并使用在最大分割深度d处终止的停止准则。那么以下成立：- （完美界限）如果在每次迭代中，ACM和普通BnB都修剪掉除了包含全局最优解的一个子立方体外的所有子立方体，那么ACM需要O(2^(n-1)) 次迭代才能终止，而普通BnB需要O(2^n)。
- （无效界限）如果ACM和普通BnB在每次迭代中都不修剪任何子立方体，那么ACM需要O(2^(n-1)d) 次迭代才能终止，而普通BnB需要O(2^nd)。
这里我们给出了命题1的数值感觉：示例3（无效界限）：假设ACM和普通BnB的界限在命题1的意义上是无效的。如果n=3且d=10，那么ACM在大约220次迭代中终止，而普通BnB在230次。我们进一步有230/220 = 1024，这意味着ACM可以比普通BnB快1024倍（忽略了ACM由于每次迭代调用区间刺探而产生的额外log M因子）。命题1表明，如果两种算法的上下界限都是完美的，ACM比普通BnB有轻微的优势，加速因子为2，这将被每次迭代调用区间刺探的额外log M因子所削弱。另一方面，如果界限是无效的，以至于没有任何立方体被排除，那么ACM将比普通BnB快得多地终止，加速因子为2d；ACM的这种优势使其额外的log M项变得不重要。命题1中的完美和无效界限场景是理想的；在实践中，界限既不是完美的也不是无效的。即便如此，出于两个原因，ACM是首选的：- 众所周知，推导紧的上下界限对于基于BnB的方法至关重要，但也很困难，许多现有的界限倾向于是“无效的”而不是“完美的”[47]，[49]。因此，基于ACM的全局优化通常会加速。
- 如图3所示，我们为ACM推导的界限基于区间刺探，并且在修剪次优立方体方面比普通BnB的通常界限更有效。
图4展示了ACM的实际好处。图4(a)显示ACM的最大下界比普通BnB紧得多；这是ACM下界限操作更紧的理论结果，如前所述（见图3）。有趣的是，图4(a)显示ACM的最大上界也是更紧的，尽管ACM的上界限操作并不一定更好（图4(b)）。虽然这种现象乍一看似乎矛盾，但它归因于两个因素：ACM由于其更紧的下界而在分支空间上修剪了更多的立方体；ACM在早期阶段修剪了更高比例的立方体（图4(c)）。换句话说，ACM基本上是在显著较少的剩余立方体上计算最大的上界（图4(d)），这就是为什么它的最大上界也是更紧的原因。备注1:我们使用最大深度作为实际的停止准则。直观地说，设置子立方体最小直径的容差在比较普通BnB和ACM时似乎更合理。然而，可以证明相同的直径容差大致意味着相同的最大深度。有关更详细的解释，请参见在线提供的附录。V. ACM-0: 3D-2D 注册 (3D-2D REGISTRATION)
首先，我们通过解决一个一维共识最大化问题来具体介绍ACM：即视觉惯性定位问题。这个问题在导航系统中自然出现，目标是基于一组3D-2D对应关系解决绝对相机姿态问题，给定由惯性测量单元（IMU）提供的角度信息。Jiao 等人 [27] 提出了一种一维普通BnB算法来全局最优地解决这个问题。问题表述：考虑一组3D-2D对应关系集合 ，其中 是世界坐标系中的3D点， 是2D图像点。这些对应关系遵循一个基于绝对姿态变换约束的底层模型，该模型依赖于旋转矩阵 ，平移向量 ，以及相机投影函数 ；具体地：当相机校准已知时， 仅表示归一化的图像坐标，并且使用齐次表示 ——（24）变为齐次等式约束（忽略噪声）其中 分别是绕 z、y 和 x 轴的旋转角度。假设 和 可以从惯性测量（即 IMU）中估计出来，那么线性方程组（26）中只剩下 4 个未知数。因此，利用 2 对对应关系 和 ，我们可以得到 4 个方程来得到唯一解。使用 Jiao 等人 [27] 提出的平移不变测量（TIM），我们可以简化上述 4 个方程，消除平移并得到一个只与未知角度 相关的单一方程：其中 是从对应关系计算出的系数。因此，共识最大化问题可以表述为：平原 BnB [27]：记 为子立方体 上 的下界， 为上界。 可以通过立方体的中心点简单地计算出来。在立方体 上，我们可以得到 ，因此上界可以从以下观察中得出：ACM-0: 区间刺探：考虑到ACM可以用以替代n维普通BnB，通过在(n-1)维空间上分支，我们为特定n维问题提出的解决方案命名为ACM-(n-1)。例如，在目前解决的一维CM问题中，该方法被称为ACM-0。对于由基本函数如正弦和余弦组成的不等式 ，我们可以反向解出 的区间，假设 。附录中提供了有关如何从类似(28)的约束中得出角区间的更多详细信息。每对数据对 () 导致一个 的区间，记为 。因此，区间刺探可以直接用于求解最优 ，而无需使用BnB，如下所示：A. 合成实验 (Synthetic Experiments)
设置: 我们使用以下合成实验来验证ACM-0相对于一维普通BnB的优势。为了生成合成图像对应关系，我们随机采样200个3D点，这些点距离世界坐标系原点在4到8之间，然后从指向同一3D点的射线生成对应关系。为了添加噪声，我们首先从每个承载向量提取一个正交平面，并假设正交平面的焦距为800像素，添加随机噪声。平面上的扰动点被重新归一化以获得扰动的承载向量[5]。平移向量t的元素和旋转角度随机生成在区间[−1, 1]和[−π/2, π/2]内。我们还为图像点添加了从[−2, 2]像素随机采样的噪声，将代数约束（29）中的内点阈值设置为0.2，并采用10作为普通BnB的最大深度。所有算法都用C++实现，并在不同的随机数据上重复100次以获得稳定结果。角度误差以度为单位测量，表示为 |αgt − ˆα|，其中αgt和ˆα分别是真实角度和估计角度。结果: 正如所讨论的，虽然普通BnB在一维上迭代分支，但ACM-0直接使用区间刺探，因此问题（29）可以更有效地解决。接下来，我们研究了普通BnB和ACM-0的运行时间，并验证了区间刺探的性能。图5(a)显示了我们改变异常值比例从10%到90%，步长为10%，以及从91%到95%，步长为1%时，普通BnB和ACM-0的平均结果。表I呈现了在大异常值比例条件下，普通BnB的平均迭代次数。总的来说，ACM-0始终比普通BnB快，并且享有200到300倍的加速比，同时导致类似的角误差。更重要的是，ACM-0可以在极端异常值情况下（异常值比例超过80%）在大约10^-2 秒内收敛，而普通BnB需要超过1秒和超过10^3次迭代才能完成。正如图5(b)进一步所示，我们获得了与Jiao等人[27]的方法一致的角误差。VI. ACM-1: 2D-2D 注册 (2D-2D REGISTRATION)
接下来，我们考虑一个二维共识最大化问题，并展示ACM如何通过仅在一个一维搜索空间上分支，再次实现显著的加速。我们考虑安装在平面地面车辆（例如在平坦道路上行驶的汽车）上的前视相机的情况。相机的运动将被限制在一个平面内，因此帧到帧的视觉里程计可以通过找到一个由二维平移和一维平面旋转位移组成的三维欧几里得变换来解决。请注意，这与一般的校准相对姿态场景中的五个自由度形成对比。通过使用角度加视差参数化并代入极线约束，可以轻松地消除不可观测的视差，从而得到一个可以全局最优地使用普通BnB解决的双角度问题。问题表述：考虑一对2D-2D对应关系 ，源自图6所示处于平面运动中的车辆上的前视相机，其中 和 分别表示第一视图和第二视图的归一化图像坐标。并记对应的齐次坐标为 ， 。对应关系遵循一个基于相对姿态变换约束的底层模型，该模型依赖于旋转矩阵 和平移向量 。具体地：且 是由相机旋转 和平移 组成的从第二视图到第一视图的本质矩阵。不失一般性，我们假设相机的y轴指向下方，主轴向前。给定车辆在水平平面上的平面运动，从第二视图到第一视图的旋转矩阵 由单角度参数矩阵给出：其中 是关于y轴的偏航角。记 为平移向量的长度， 为相对于原始位置的平移方向角，平面平移 由下式给出：其中平移的长度 已被消除，只剩下两个未知角度 和 需要找到。为了分离未知参数，我们可以重新表述 (36) 为：普通 BnB [26]：注意，第III节中通常描述的界限通常用于界定 。给定子立方体 及其中心点 和 ，下界 和上界 由下式给出：ACM-1：不失一般性，假设ACM-1用于在 的空间上分支，并通过区间刺探搜索 。首先，考虑ACM-1估计的下界。正如普通BnB所讨论的，可以通过中心点 获得子立方体 的平凡下界。记由 反向导出的 区间为 （见附录，在线提供详细信息），则子立方体 上的ACM-1下界可以通过解决区间刺探问题获得：如第IV节介绍的，ACM-1的上界可以通过解决区间刺探问题获得：A. 合成实验 (Synthetic Experiments)
设置: 我们使用与上一节中提到的相同设置和噪声，但现在相机进行平面旋转和平移以在第二视图中生成坐标。我们随机采样偏航角在区间[−π/3, π/3]内，同时保持俯仰角和横滚角为0。平移角从[−π/3, π/3]区间中采样，平移范数ρ从[−2, 2]区间中采样。我们仍然使用10作为普通BnB [26]和ACM-1的最大深度，并为两者都设置0.02作为内点阈值。结果: 我们基于前面定义的界限函数实现了普通BnB [26]和ACM-1，并研究了它们的相对性能。我们无法运行[26]中的代码，因此我们实现了自己的普通BnB版本。在[26]中，他们提到他们的实现在具有10^−4 内点阈值的两个连续KITTI图像的50个对应关系上需要18秒。另一方面，我们的实现在相同的内点阈值10^−4下处理200个SIFT对应关系少于1秒。这验证了我们普通BnB实现的正确性和效率作为基线。我们改变了异常值比例，从10%变化到90%，步长为10%，然后从91%变化到95%，步长为1%。平均结果如图7所示。正如预期的那样，显然ACM-2比普通BnB需要更少的时间来收敛，并且实现了2倍到20倍的加速比（图7(a)）。同时，ACM-2在θ1和θ2上保持与普通BnB相似的低角度误差（图7(b)）。仔细查看图7(a)中的运行时间，ACM-2稳定地在大约0.03秒内平均对于广泛的异常值比例。这与普通BnB形成对比，后者的运行时间对异常值比例更为敏感，从0.0615秒增加到0.5833秒。考虑到图7(c)中显示的迭代次数的显著差异，这个结果也证实了我们的声明，即实践中每次迭代中用于区间刺探的额外log M复杂度是微不足道的。B. 真实实验 (Real Experiments)
为了验证我们算法在全球最优2D-2D注册中的有效性，我们使用KITTI数据集进行了真实世界实验。设置: 我们处理包含地面真实数据的所有11个序列（00-10）。我们为每张图像提取SIFT特征，将保留的最佳特征数量设置为1000，并在连续帧的点特征上执行暴力匹配。最后，使用已知的内在相机矩阵对获得的像素对应关系进行归一化。通过连接相应的绝对姿态，提取R和t的地面真实相对姿态参数，然后提取θgt和φgt的真实值。将代数误差的阈值ϵ设置为10^−4，并将普通BnB和ACM-1的最大深度设置为20，以获得更精确的解。普通BnB和ACM-1的初始立方体分别定义为[−π/2, π/2]^2和[−π/2, π/2]。误差以估计和地面真实角度θ和φ之间的绝对差表示。结果: 在KITTI数据集上的结果再次证明了ACM-1相对于普通BnB的预期加速。表II总结了每个序列中所有图像对的中位数结果。总体而言，ACM-1获得了约2倍的加速，并且误差几乎相同。ACM-1更快的运行时间再次是由于显著减少的迭代次数。请注意，尽管SIFT特征相当陈旧，但它仍然返回了高质量的视图对之间的对应关系，从而导致异常值较少的情况，在这种情况下，ACM相对于普通BnB的优势不太明显。备注2 (Remark 2):：可能有人担心在第V和VI节的几何视觉问题中使用的代数约束会导致比执行几何约束更不准确的结果。我们想指出，在共识最大化或鲁棒估计问题中使用代数误差是常见的，并且，正如先前的工作所证明的，代数误差度量在大多数情况下足够强大，至少可以对异常值进行分类。此外，将基于几何误差的细化添加到ACM识别的解决方案中将是直接的。VII. ACM-2: 3D-3D 注册 (3D-3D REGISTRATION)
在本节中，我们将ACM应用于3D点集注册问题（即Procrustes对齐），该问题的目标是通过刚体变换对齐两个点集。问题表述：考虑两个重叠的无噪声3D点集 和 。每对重叠的点 满足以下关系：而不是直接解决6自由度问题，已经证明可以使用代数运算消除3个自由度，并通过分支定界解决剩余的3自由度问题。此外，ACM可以将自由度再减少1个，通过在2维搜索空间上分支来解决它。类似于图像配准问题，可以在点集上提取3D特征并匹配对应关系，这导致基于对应关系的3D-3D配准。另一方面，也可以同时搜索变换和对应关系，从而导致所谓的无对应关系配准。以下，我们为这两种3D点集配准变体分别介绍ACM-2。我们将基于对应关系的3D-3D配准问题命名为ACM-2 Corr，并为无对应关系3D-3D配准命名为ACM-2 Corrless。A. 基于对应关系的配准
给定一组3D点对应关系集合 ，其中 ，点集配准问题可以被理解为寻找满足关系的旋转 和平移 ：这里我们为了简化省略了噪声。取两边的范数，旋转不变性容易得到约束：未知的旋转 因此被消除，未知的平移 可以通过以下共识最大化问题解决：平原 BnB：定义 。给定子立方体 及其中心点 ，我们可以记在这个体积上的 区间为 。同样，一个平凡的下界和直观的上界结果为：ACM-2 Corr：写翻译 和点 分别为 和 。不失一般性，让 ACM-2 在平移空间的前两个维度上分支，并使用区间刺探全局最优地解决 。ACM-1的上界，可以类似地从示例1推导出来（见附录，在线提供详细信息）：B. 对应关系无关的注册
由于点云特征描述符的质量和可区分性的限制，匹配对应关系可能是个问题。这激发了研究者设计无需对应关系的方法。例如，在[34]中考虑了使用所有对所有匹配列表进行注册。通过观察到点集内部距离在刚性变换下是不变的（参见图8），Liu等人[32]提出过滤掉大部分无用的对应关系，然后将它们提供给一个名为GoTS的纯BnB算法，以同时搜索变换和对应关系。正式地，使用(43)中的一般问题公式，假设点对(qi1*, qi2*)是从集合Q的重叠部分中随机选取的，而对(pj1*, pj2*)是来自参考点集P的相应真实对应对。一个关键的观察是：其中R ∈ SO(3)是任意旋转，t ∈ R3是任意平移。对于真实对应对(qi1*, qi2*)和(pj1*, pj2*)，距离预期是很小的，因此，通过适当的阈值τ，我们可以只保留满足：对于每一个i1, i2 ∈ {1, ..., M1}和每一个j1, j2 ∈ {1, ..., M2}（i1 ≠ i2, j1 ≠ j2），并移除所有其他对。剩下的点对((qi1, qi2), (pj1, pj2))被称为旋转不变(RI)对。接下来，观察到进一步为RI对提供了约束。使用ℓ∞范数，我们有：其中m := (i1, i2), n := (j1, j2)。然后我们可以将共识最大化问题表述为：注意，约束——旨在检查||和||中的最大元素是否小于ϵ——也可以被解释为同时检查|| ≤ ϵ和|| ≤ ϵ。备注 3：问题(58)中的公式与[32]中的公式不完全相同，他们在解决：如上所见，(58)和(59)之间的主要区别在于计数的内点数。可以证明，尽管(59)为每个m寻找一个独特的对应关系，但(58)的解也是(59)的解（见在线附录）。平BnB算法的上界和下界：给定中心点为 且直径为 的立方体 ，下界同样可以通过使用 来简单获得。为了清晰解释上界，让我们使用新的索引符号 ， 。对于立方体 中的任何平移 和 ，我们有一个基本的几何不等式：ACM-2Corrless: 对应关系无关的注册算法：不失一般性，假设ACM-2 Corrless在平移空间的前两个维度上进行分支，并使用区间刺探（Interval Stabbing）来寻找 。给定中心点为 且半直径为 的立方体 ，考虑每对 的以下子约束：同样，ACM-2 Corrless的下界是从平BnB中的对应部分修改而来的。给定 ，将 代入(66)，可以很容易地通过函数反演找到 的区间 。同样，在相同的立方体上，我们可以从 的子约束中导出 的另一个区间 。因此，ACM-2 Corrless的平凡下界给出为：ACM-2 Corrless的上界以与示例1相同的方式导出。注意，我们也可以获取(60)的二维版本，记 在 上的区间为：类似地，我们也可以导出 上 的放松区间，并记为 。最后，通过在问题上执行区间刺探，可以找到ACM-2 Corrless的有效上界：一旦找到最优平移 ，未知旋转 可以通过现有算法有效估计。例如，[31]提出了一个具有快速搜索的三维BnB，[36]提出了一种同时搜索旋转和平应对的高效准确方法。C. 合成实验
设置：3D-3D注册的合成数据生成与第V-A节类似，只是我们这里不将它们转换为2D特征。为了引入离群点，我们随机生成3D点在相同的范围内，将它们转换到一个坐标系中，并使用它们替换原始的内点。相对平移和旋转轴在单位立方体中随机生成。旋转角度在区间[−π, π]内随机采样。对于基于对应关系的设置，我们首先生成3D-3D对应关系，然后给两个坐标系中的3D点添加均值为0，方差为0.01的高斯分布噪声。对于无需对应关系设置，我们生成两个相同大小的无噪声点集。在两种设置中，我们将阈值ϵ设为0.001，基于对应关系的设置中匹配阈值τ设为0.1ϵ，每组中的对应关系/点数设为1000，并运行100次试验以获得稳定结果。将平BnB和ACM-2 Corr的最大深度设为10。正如[32]所建议的，我们在无需对应关系设置的实际实现中，保留每个点集中点对间距离最大的1000个点对。为了测量平移误差，我们定义相对平移误差为 (\frac{| \hat{t} - t_{\text{gt}} |2}{| t{\text{gt}} |_2})，其中tgt是真实平移，(\hat{t}) 是估计的平移。结果：对于基于对应关系的设置，离群点比率从10%变化到90%，步长为10%，然后从91%到95%，步长为1%。平均结果展示在图9中。对于无需对应关系设置，重叠比率从10%变化到70%，步长为10%，然后从81%到90%，步长为1%。图9(a)和(d)清楚表明，在两种设置中都取得了显著的改进。如图所示，ACM-2比平BnB快了一个数量级，并且ACM-2的迭代次数大约是平BnB的两个数量级。在所有情况下都观察到类似的误差。当处理更极端的离群点比率（大于90%）或极端的重叠比率（大于80%）时，ACM-2 Corr和ACM-2 Corrless分别比平BnB快大约18倍和40倍。这些观察结果与之前讨论的ACM的优势一致，即较少的一维搜索空间有助于ACM更快地收敛。D. 实验
这里我们使用斯坦福兔子点云[52]来比较ACM-2 Corrless和平BnB。设置：按照[32]，我们使用MATLAB中的pcdownsample函数对原始点云进行下采样。然后我们根据特定的重叠比率随机切割原始兔子，从而获得原始点集的一个片段。最后，我们随机变换这个小片段。平移在[−1, 1]^3内随机生成，旋转角度从[−π, π]内随机采样。图8显示了一个通过CM识别的内点和外点的示例实验设置。为了获得RI对，我们遵循[32]中的相同策略。我们将阈值设为10^-4，最大深度设为10。平BnB的初始立方体设为[−1, 1]^3，ACM-2 Corrless设为[−1, 1]^2。结果：图10展示了平BnB和ACM-2 Corrless之间的比较，我们变化重叠比率从10%到90%（第一行），然后从1%到9%（第二行）以检查极端情况。ACM-2 Corrless在整体上显示出显著的速度提升，与平BnB相比，平移误差仍然可比。具体来说，ACM-2 Corrless平均在不到0.5秒内收敛，而平BnB需要超过10秒。因此，ACM-2 Corrless的速度提升因子约为40倍。有趣的是，两种方法即使在重叠比率低至4%的极端情况下也能提供准确的估计。正如图10(b)所识别的，两种方法在大多数情况下都能工作。备注 4：请注意，本工作的主要贡献是加速共识最大化问题的求解，我们测试的是[32]中讨论的无噪声、无需对应关系的场景。尽管这已经很好地展示了我们方法的优势，我们还是想引用Zhang等人[54]的工作，他们通过初始状态估计引入了一种扩展方法来处理噪声。VIII. ACM-3: 旋转和平移估计
在这一部分，我们提供了一个四维应用来进一步展示ACM的性能。考虑一个相机围绕其光心旋转（例如全景拼接）；此外，在两个视图中，焦距是唯一的但未知。因此，自然出现了一个四维问题，我们需要找到一个3D旋转和一个未知的焦距参数。这种四维问题在[55]中被研究过，可以通过RANSAC解决。在[56]中，Bazin等人提出了一种平BnB方法来全局最优地解决这个四维问题。问题表述：记 为一对中心化的2D图像点， 为如第六节所述的相应同质化坐标。当相机围绕其光心旋转时，不涉及平移，未知变量由一个3D旋转矩阵 和一个校准矩阵 组成。如果 是一对无噪声的内点对，它们通过无限远的单应性关系相关联，如 。由于图像点是中心化的， 可以写成对角矩阵形式 ，其中 表示未知的焦距。因此，共识最大化问题可以表述为：回想一下，与第五部分类似，旋转矩阵 可以由3个未知角度参数化，如 。因此，可以在 和 的四维空间中搜索，并全局最优地解决这个共识最大化问题。我们可以参考Bazin等人[56]的详细BnB方法，他们设计了一个适当的双曲线来开发上界。我们在他们工作的基础上[56]，开发了ACM-3，这是一种加速的共识最大化方法，它在 的3D空间中分支以寻找最优解。如常，剩余的自由度 是使用区间刺探确定的。虽然我们需要为ACM-3再次派生定制的上下界，但推导与第五和第六节相对相似。因此，为了简洁起见，我们在这里省略了推导。A. 合成实验
设置：我们在合成数据上比较了平BnB和ACM-3，并进一步包括MLESAC作为比较，因为它被认为比普通的RANSAC对噪声更鲁棒（在我们的实验中RANSAC的性能与MLESAC相当，因此没有显示）。如果达到一定的置信度，比如说90%，95%，99%，我们就终止MLESAC。为了生成合成数据，我们首先随机采样100个3D点，这些点与世界坐标系原点的距离在4到8之间，然后将它们投影到相机坐标系上。我们均匀采样焦距在[200,1500]范围内，并相应地设置画布大小为1480×2160像素。旋转角度均匀采样自[−π/2, π/2]。像素噪声，从均值为0，方差为0.5的高斯分布N(0, 0.5)中随机采样，添加到图像点的两个坐标上。我们将内点阈值设为1像素。旋转误差以arccos((tr(R_T^g R̂) − 1)/2)来衡量，其中R_T^g和R̂分别是真实和估计的旋转矩阵。焦距误差定义为估计焦距与真实焦距的绝对差，除以真实焦距。结果：图11展示了运行时间和估计误差的比较结果。可以观察到，ACM-3始终比平BnB快，大约有4倍的加速，并且在旋转和平移误差方面提供了与平BnB相当的低误差。具体来说，当离群点比率是90%时，平BnB需要大约41.33秒才能收敛，而ACM-3平均只需要10.78秒。正如预期的那样，作为一种基于BnB的方法，ACM-3即使在离群点比率高于90%的情况下仍然表现良好，而MLESAC开始失败（见图11(b)和(c)）。为了进一步比较ACM-3和MLESAC，我们报告了它们的成功率（如果旋转误差小于或等于1度，焦距误差小于或等于5%，则试验成功）。注意，即使在离群点比率高达94%的极端情况下，ACM-3和普通BnB在超过80%的试验中都提供了小于1度的误差。与此同时，MLESAC只能在大约40%的试验中成功（见图11(d)）。在图11(e)中可以观察到类似的结果。因此，直观地看，对于这样的高离群点比率情况，当MLESAC达到置信度时，鲁棒解几乎无效。注意，置信度设置为99%，因为这对于如此极端的离群点场景，执行时间与我们的算法相当。总之，我们的方法在具有挑战性的场景中最终优于MLESAC，无论是在准确性还是计算效率方面都表现更好。IX. 结论
在这项工作中，我们介绍了一种加速求解全局最优共识最大化的通用策略，该策略通过分支定界实现。提出策略包括——对于一个n维问题——简单地在(n-1)维空间上进行分支，然后使用区间刺探全局最优地求解剩余的变量。尽管后一步具有O(log M)复杂度，但其成本通常被补偿，因为通过在较小维度空间上分支，创建的体积要少得多。此外，嵌入全局最优区间刺探机制通常会导致更紧密的下界，从而引起早期对次优分支的剪枝。我们在四个基本的几何注册问题上验证了我们的方法，包括相机重投影、相对相机姿态估计、点集注册和旋转和平移估计。在点集注册的情况下，我们进一步将应用扩展到无需对应关系的情况，通过在详尽的匹配列表上运行优化来解决。由于算法对极端离群点比率的强大处理能力，这种无需对应关系的注册变体得到了成功的解决。所达到的执行时间常常隐藏在潜在的实时应用中，从而将全局最优共识最大化的相关性从纯粹的验证工具提升为在线处理的可行解决方案。声明
本文内容为论文学习收获分享，受限于知识能力，本文对原文的理解可能存在偏差，最终内容以原论文为准。本文信息旨在传播和学术交流，其内容由作者负责，不代表本号观点。文中作品文字、图片等如涉及内容、版权和其他问题，请及时与我们联系，我们将在第一时间回复并处理。
