共识最大化树搜索中的关键贡献和加速策略

1637i=1共识最大化树搜索再探蔡志鹏阿德莱德大学陈达俊阿德莱德大学VladlenKoltun IntelLabs摘要一致性最大化被广泛用于计算机视觉中的鲁棒拟合。然而，精确地解决它，即，找到全局最优解是棘手的。一个 * 树搜索，已被证明是固定参数易处理的，是最有效的精确方法之一，虽然它仍然限于小的输入。我们对改进A* 树搜索做出了两个关键贡献首先，我们证明了以前使用的共识最大化树结构实际上包含连接相邻和非相邻级别节点的至关重要的是，连接非相邻层的路径对于树搜索来说是冗余的，但它们并没有被刻意避免。我们提出了一个新的加速策略，避免这种冗余路径。在第二个贡献，我们表明，现有的分支修剪技术也迅速恶化的问题的尺寸。然后，我们提出了一个新的分支修剪技术，是不太维度敏感，以解决这个问题。实验表明，这两种新技术可以显着加速A* 树搜索，使其在以前无法达到的输入上相当有效 。 演 示 代 码 可 以 在 https ： //github 上 找 到 。com/ZhipengCai/MaxConTreeSearch.1. 介绍离群值的普遍存在使得鲁棒的模型拟合在许多计算机视觉应用中至关重要。最流行的鲁棒拟合准则之一是共识最大化，因此，给定离群污染数据S={si}N，我们寻求与数据的最大子集一致的模型θ∈Rd形式上，我们解决了ΣN共识最大化是NP难的[4]，因此，次优但有效的方法通常更实用。可以说，这种类型的最流行的方法是RANSAC [11]及其变体[8，26，7，24]，它们在随机采样（最小）数据子集上迭代拟合模型，并返回具有最高一致性的模型。然而，它们固有的随机性使得这些方法往往远离最优，有时甚至不稳定.为了解决这个问题，已经提出了确定性优化技术[23，14，2]，其具有良好的初始化，通常优于RANSAC变体。然而，一个好的初始解决方案并不总是容易找到的。因此，这些方法仍然可能返回不令人满意的结果。次优方法的弱点促使研究者研究全局最优方法;然而，到目前为止，它们仅对小输入大小（小d、N和/或离群值的数量o）有效。最有效的精确方法之一是树搜索 [15 ， 5 ， 6] （ 其 他 人 在 第 二 节 中 进 行 了 调 查 。1.1），它适合（1）到LP型方法的框架[25，18]。通过使用启发式来指导树搜索并进行分支修剪，A* 树搜索[5，6]已被证明比广度优先搜索（BFS）和其他类型的全局最优算法快得多。事实上，树搜索是可证明的固定参数易处理（FPT）[4]。然而，正如在[6]和后来我们的实验中所证明的那样，A* 树搜索可能非常低效对于中等d（≥6）和o（≥10）的挑战性数据。我们的贡献。本文分析了A* 树搜索效率低下的原因，并提出了改进算法。具体而言：• 我们证明，以前的树搜索算法并没有避免所有冗余路径，即路径，连接来自非相邻级别的节点根据这份ob-最大θc（θ|S）=i=1I{r（θ|si）≤n}，（1）在此基础上，提出了一种新的加速策略，避免了这种非相邻（冗余）路径。其中c（θ| S）称为θ的一致性。0/1值指示器函数I{·}仅在si与θ一致时返回1，这在残差r（θ）不一致时发生。|si）≤10。r（θ）的形式|si）将在后面的章节中定义。2. 常数预定义的内点阈值，并且d被称为“问题维度”。给定（1）的最优解θ∈，si是内点，如果r（θ∈|si）≤1，否则为离群值。• 我们表明，在[6]中的分支修剪技术并不总是有效的，有时可能会减慢树搜索由于其敏感性的d。为了解决这个问题--lem，我们提出了一个分支修剪技术，是不太维度敏感，因此更有效。实验证明，使用我们的新技术可以实现显著的加速（3个数量1638- -我的我p1我更快地处理具有挑战性的数据）。我们的工作代表了重大进展，使全球最佳共识最大化实际的真实数据。1.1. 相关工作除了树搜索，其他类型的全局最优方法包括分支定界（BnB）[16，28，22]，其穷举搜索是通过测试所有可能的θ来完成的。然而，BnB的时间复杂度在参数空间的大小上是指数的，参数空间通常很大。此外，BnB的边界函数是问题依赖的，并不总是微不足道的建设。另一种类型的方法[20，9]在所有可能的基础上枚举和拟合模型，其中每个基础是大小为p的数据子集，其中pN和p通常是稍大一点。ndΣ，例如， p = d +1。所有可能的N，它与N和d的比例关系很差。除了实际运行时的差异之外，树搜索与其他两种方法的区别在于树搜索是FPT [4]：其最坏情况运行时间在d和o上是指数的，但在N上是多项式的。2. 一致最大树搜索我们首先回顾几个概念，是相关的共识最大化树搜索。2.1. 应用范围树搜索需要残差r（θ|si）是伪凸的[6]。一个简单的例子是线性回归残差r（θ|si）= |aTθ − b i|、（二）其中每个数据si={ai，bi}，ai∈Rd，bi∈R.另一个示例是在常见的多视图几何问题[21，2]中使用的残差，其具有以下形式在整篇文章中，我们将假设r（·）是伪凸的，并且S是非退化的（否则可以应用无穷小扰动来去除退化[18，6]）。Un-在此假设下，问题（4）具有唯一的最优解，并且可以用标准求解器有效地求解[10]。此外，（4）可证明是LP型问题[25，1，10]，它是线性规划（LP）问题的推广。LP型问题具有以下属性：财产1（单调性）。为每两 集S1<$S2 <$S，f（S1）≤ f（S2）≤ f（S）.属 性 2 （ 局 部 性 ） 。 对 任 意 两 个集 合S1<$S2<$S和任意si∈ S，f（S1）= f（S2）=f（S2<${si}）<$f（S1）= f（S1<${si}）.有了上述性质，基的概念，这是必不可少的树搜索，可以定义。定义1（基础）。S中的一个基B是S的一个子集，使得对于每个B′B，f（B′）f（B）}。我们称l（B）=| V（B）|B的水平和C（B）= S\V（B）B的覆盖度。根据上述定义，c（θ（B）|S）=| S|-l（B）.（五）LP型问题的一个重要性质是在C（B）和B上求解（4）返回相同的解。定义3（支持集）。S的0层基称为S的支撑集，我们将其表示为τ（S）。假设我们知道（1）的最大内点集I，其中¨¨|我|=c（θ）|S）。定义B_∞=τ（I）为I的支撑集;�ATθ b�r（θ|s）=ip，（3）icTθ−dB*可以通过对I求解（4）得到。l（B）是最小离群点集的大小。我们的目标问题（1）可以重新转换为寻找最优基其中每个数据si={Ai，bi，ci，di}，Ai∈Rd×m，bi∈Rm，ci∈Rd，di∈R.通常，p是1、2或∞。2.2. LP型问题（1）的树搜索算法是通过求解一系列极大极小问题来构造的，这些问题的形式如下：最小化max r（θ|si）。（四）θ i∈S问题（4）最小化S1中所有数据的最大残差，S1是S的任意子集。为方便起见，我们定义f（S1）为（4）在数据S1上计算的最小目标值，θ（S1）为（精确）最小值。我1639B*=argmin l（B），s.t. f（B）≤λ，（6）B组而θ（B）是（1）的最大化者。直觉上，B是可行的最低层基，其中基B被称为可行的，如果f（B）≤B。2.3. A* 树搜索算法Matousˇek[18]表明，LP型问题的基集可以排列在一棵树中，其中根节点是τ（S），树上节点B所占的层是I（B）=| V（B）|. 另一个关键的见解是，从τ（S）到任意高阶基的路径，其中路径由相邻基的序列形成，定义如下。1640i=1算法1 Chin等人的A* 树搜索。[6]对于（6）算法2 A* 树搜索的可容许启发式hins要求：S={si}N，阈值.要求：B1：将具有优先级e（B）的B=τ（S）插入队列q。2：将哈希表T初始化为NULL。第三章： 当q不为空时4：从q中取e（B）最小的B。5：如果f（B）≤，则6：返回B=B。7：如果结束8：Br←尝试用TOD方法降低B9：对于每个s∈ Br，10：如果T中不存在V（B）的索引1：如果f（B）≤ 0，则返回0。2：O ←。第三章： 当f（B）> 0时，4：O ← O ∪ B，B ←τ（C（B）\B）.5：结束while6：h ins←0，F ← C（B）。7：对于每个B ∈ O，8：对于每个s∈ B，图9：B′←τ（F <${s}）.10：如果f（B′）≤f，则F {s}\B′。定义4（基础邻接）。两个基B′和B是相邻的，如果对某个si ∈ B，V（B′）= V（B）<${si}.直觉上，B′是B在树中的直接子节点。我们说，当我们计算时，我们s使得F不可行，从扩展的F中移除τ（F <${s}），并且启发式值hins增加1。文[6，定理4]证明了h_ins的可容许性简而言之，将F记为C（B）的最大可行子集。如果F <${s}是不可行的，τ（F <${s}）必须至少包含一个τ（C（B）\{si}）. Chin等人[6]通过搜索树结构使用A* 最短路径查找技术（算法1）。给定输入数据S，开始A* 树搜索在F中的点。因为我们只给h加1则h*（B）≥hins（B）。ins 当这种情况发生时，从根节点τ（S）开始，迭代地扩展树队列q存储所有未扩展的树节点。并且在每次迭代中，扩展具有最低评估值e（B）的基B。展开遵循基邻接cy，其计算对于所有s∈ B的τ（C（B）\{s}）（算法1中的第12行）。评估值定义为e（B）=l（B）+h（B），（7）其中h（B）是估计C（B）中离群值的数量的启发式算法。A* 搜索只使用可接受的分类。定义5（可受理性）。如果h（B）≥0且h（B）≤h（B），则启发式h是可容许的，其中h（B）是必须从C（B）中删除以使剩余数据可行的最小数据数。注意，设置e（B）=l（B）（即，h（B）=0）将A* 搜索简化为广度优先搜索（BFS）。 在允许的启发式算法下，A* 搜索保证总是在其他次优可行基之前找到B **（参见[6]）。证明）。算法2描述了[6]中使用的启发式算法直觉上，hins的算法在第一轮迭代中移除一系列基，直到得到一个可行子集找到了F C（B）之后，算法迭代地将每个移除的基点s插入回F中。如果插入2.4. 避免冗余节点扩展算法1采用两种策略来避免冗余的节点扩展。在第8行 中 ， 在 扩 展 B之 前 ， 使 用 称 为 真 实 离 群 值 检 测（TOD）[6]的快速启发式方法来尝试从B中识别和移除真实离群值（更多细节请参见第2节）。4），这有可能减少从B开始的分支的大小。在第10行中，执行重复的基础检查试探法以防止已经被检测到的基础。再次考虑以前探索（细节在第二节。（3）第三章。我们的主要贡献是两个新的策略，改进了上述原始方法，我们将在Secs中描述。3和4在每一节中，我们将首先仔细分析现有战略的弱点秒然后，5秒6显示结果。3. 非相邻路径回避回想一下关于邻接的定义4：若B和B′相邻，则它们的违反集V（B）和V（B′）必须相差一点;换句话说，它必须认为，|=1时。|= 1.（八）给定一个B，算法1中的第12行十一：将V（B）的索引{s}散列到T中。十一：F ← F{s}。十二：B′←τ（C（B）\{s}）.十二：其他十三：将优先级为e（B′）的B′插入q。十三：hins←hins+ 1，F←十四：end if十四：end if1641′(a) 根节点B根。（b）1级节点B。（c）1级节点B。s2∈ C（B）.（d）树形结构图1.（B′可以从B和B根生成，但它不与B相邻，因为l（B′）=l（B）.注意，算法1中的第10行不能避免该非相邻路径，因为V（B′）={s，s}=V（B′）={s}。2121图（d）显示了在树搜索期间三个碱基之间的关系在所提出的非相邻路径回避（NAPA）策略中，不遵循红色绘制的路径正如我们将在Sec中展示的那样这个简单的想法大大减少了A* 树搜索的运行时间C（B）\{s}上的极大极小问题（4）.在这条路上，l（B′）=l（B）+1。（九）这样，通过迭代s来移除，就可以生成B的所有相邻子基，从而可以对树进行探索。然而，一个被忽视的重要现象算法1是，虽然上述过程生成B的所有相邻子基，但并非所有在该过程中生成的B′都是相邻子基。图1示出了来自线拟合（2）的具体示例：从根节点Broot开始，分别去除点s2和s1，生成两个子基B和B′。然而，通过进一步从B中移除s1并在C（B \{s1}）上求解（4），我们再次获得B′ 以来(a) TOD（b）DIBP图2. (a)在TOD中，在当前节点B上，如果s2被识别为真正的离群值，则通往可行基B的最短路径必须通过s2（红色路径）。所有其他的|B|可以跳过-1分支（在本例中从s1和s3开始）。(b) 在DIBP中，不是试图识别单个真正的离群值，而是包含至少一个真离群值的组SB（SB={s，s}in12l（B）=l（B），这两个碱基不相邻。一般来说，算法1在解决C（B\{s}）上的mini-max问题后，当V（B）的一些元素在C（B′）中时，会出现不相邻的路径。虽然在队列中插入一个不相邻的B′不会影响全局最优性，但它确实会降低效率。这是因为重复的基础检查算法1中的启发式假设子节点B’的级别总是比父节点B低1;如果生成的基B’不相邻，则该更正式地说，如果B′不与B相邻，则如果成功，则另一个|B|− |SB|可以跳过路径（在该示例中对应于S3）。DIBP比TOD更有效，因为它更容易拒绝子集而不是单个点作为离群值;参见第二节。4.2有关详细信息当找到B′时仍然需要求解，则计算e（B′）（其需要求解多个问题（4））的大得多的成本与遍历B′的子节点所需的所有计算一起被节省。这一战略的有效性将在后面的章节中予以说明。六、V（ B）{s}=V（B′）（10）4. 不敏感分支修剪并且算法1中的第8行中的重复基检查失败。由于相同的B′可以从其“真实”父节点生成在图1中，B′也是由B根生成的），相同的基可以不止一次地插入队列中。由于树搜索只需要相邻的路径，我们可以安全地跳过任何不相邻的路径，而不会影响最终的解决方案。为此，我们提出了一种用于A* 树搜索的非相邻路径避免（NAPA）策略;参见图1B。第1段（d）分段。给定一个基B，从它生成的任何非相邻基都不能具有高于l（B）的水平。因此，如果l（B′）≤l（B），我们可以简单地丢弃任何新生成的基B′（第12行）。 一个冗余极大极小问题（4）我们对A* 树搜索的第二个改进在于一个新的分支修剪技术。我们首先回顾了原始的方法（TOD），然后描述我们的新技术。4.1. 真离群值检测（True Outlier Detection，TOD）参考算法1 [6]中的第8行，设F是C（B）的最大可行子集。一个点s ∈ B，如果s∈/F ∈B，则称它为真离群点，否则我们称它为真内点r。给定一个不可行的节点B，B中的一个元素必须是真正的离群1642值。TOD的目标是在B中识别一个这样的真实离群值。如果s∈ B被成功地识别为a1643C（ B）真离群值，我们可以跳过B中所有其他点的子生成而不会损害最优性，因为s必须在通过B的可行性的最短路径上;见图2（a）。如果这样的s可以被识别，则约化子集Br简单地是{s}。TOD的原理如下：定义h（B|s）作为必须从C（B）中移除以实现可行性的数据点的最小数量，其中s强制可行。我们可以得出结论，s∈ B是一个真正的离群值，当且仅当h （ B|s ） >h （ B ） ;（ 11）见[6]，见[7]，见[8]。直觉上，如果s是一个真正的内点，强制其可行性不会改变h的值。另一方面，如果强制s是可行的导致上述条件，则s不可能是真正的内点。TOD的边界计算。 不出意料的h（B|s）和h（B）一样难以计算。为了避免直接计算-inghh（B|s），则TOD计算可容许的启发式h（B|个）没有为B识别出真正的离群值，算法2必须冗余地执行，|B|次TOD是否能找到真正的离群值在很大程度上取决于hins（B|s）逼近h（B|s）的情况。我们现在证明，h ins（B|s）通常是h（B）的较差估计量|s）的情况。 定义O*（B|s）作为必须从C（B）\s中移除以实现可行性的最小子集，其中s被强制为可行的，即，|个）|= h（B|s）的情况。|s).然后，h ins（B|s）和h（B|如果在算法2期间移除的基Brem包含O*（B）中的多个元素，则O *（B）将不同|s），因为我们只在B rem中实际上应该删除1个以上的点时才向h ins添加1。下面的引理表明，h ins（B）之间的差|s）和h（B|s）将太大，TOD是有效的，如果真正的离群值的比率∗在C（B）中，即，h（B），太大了。引理1. 条件（12）在以下情况下始终为假h（B）|s）和h ∈（B）的上界g（B）. 给定s∈ B，h（B|s）和g（B），如果h（B）C（B）≥1·φ|−1|− 1|C(B)|，（15）那么它就必须h（B|s）> g（B），（12）其中φ是算法2期间所有Brem的平均大小。证据 由于h ins（B|s）是算法2期间B rem的数量，h ins（B|s）·φ ≤ |C（B）\{s}|为|C（B）|-1。因此，我们认为，h（B|s）≥h（B|s）> g（B）≥ h（B），（13）这意味着s是真正的离群值。h ins（B|s）≤|−1|− 1φ、（十六）如[6]所示，g（B）可以作为计算h ins（B）和h（B）的副产品来计算|（S）是由一个常数计算的，因此，条件（12）永远不会为真，如果hins的应变版本，我们将其表示为hins（B|s）的情况。计算hins（B|s）是由算法2的约束版本完成的，其中所有的极大极小问题（4）需要h（B）≥|−1|− 1 .（十七）φ解算将被其受约束版本替换，其形式如下：将（17）的两边除以C（B）得到（15）。直觉上，当（15）发生时，有太多的-尽量减少最大r（θ|si）、（14a）C（B）中的列，因此包含多个元素的Bremθsi∈S1在O形（B）中的部分|s），使得hins（B）|s）离h太远（B）|s）的情况。S.T.r（θ|s′）≤S ′，S′∈S′.（14b）此外，φ与d正相关，并且在J J最坏的情况可以是d+1，这使得TOD对d敏感。（14）和（4）之间的唯一区别是约束S′中的所有数据必须是可行的。与（4）类似，（14）也是一个LP型问题，可以通过标准求解器求解与（4）类似，我们也定义f（S1| S′）作为（14）的最小目标值，θ（S1| S′）作为相应的最优解。利用上述定义，将算法2改变为其约束版本可以简单地通过用f（B）替换f（B）（ 行 3 ） 和f（B′）（行10）来完成|{s}）和f（B′|{s}）。为什么TOD无效？TOD在加速算法1中的有效性取决于TOD能够检测到真正离群值的频率。当检测到B的真正离群值时，TOD将进行修剪|B|-1个分支;另一方面，如1644果TOD无法将s∈ B识别为真正的离群值，则计算h ins（B）的运行时|S）将被浪费。在最坏的情况下图3示出了对于具有线性残差（2）的问题，TOD作为d的函数的有效性。可以看出，TOD可以有效的离群值率随着d快速降低（当d≥7时为15%）。<注意，由于g（B）只是一个h*（B）的估计，TOD有效的实际范围可以小于虚线上方的区域。4.2. 新的修剪技术：DIBP由于上述限制，TOD在修剪中通常不是有效为了解决这个问题，我们提出了一个更有效的分支修剪技术称为DIBP（维数不敏感的分支修剪）。DIBP扩展了TOD的思想，其中不是搜索一个真正的离群值，而是搜索B的子集SB，1645g（B）φφ10.80.60.40.200 0.2 0.4 0.6 0.8 1图3.作为d的函数的TOD的有效性。所有问题实例都是随机生成的，每条实曲线都包含h（B）真实离群值率C（B）为0 - 90%的数据。注意，（15）是当d的实曲线低于虚线时，对于d为真θg（B），它导致g（B）。在DIBP期间，s∈ B具有最大残差r（θg（B））|s）将首先被添加到SB中，因为较大的残差意味着s是真正的离群值的机会更高。在实践中，这种策略通常使DIBP能够找到接近最小尺寸的SB。对于具有线性残差的问题，我们可以进一步计算自适应起始值z（B），|SB|，其中DIBP可以安全地跳过hins（B）的第一个z（B）−1计算|SB）而不影响枝条修剪效果。的价值z（B）应该是max{1，d+2 - 1，d +1}。|C（B）|-1}。其原因在以下引理中得到证明：引理2. 对于具有线性残差的问题，（18）不可能为真，除非150100|SB|C（B）|-1。|− 1.（十九）g（B）证据 如在（16）中，我们有h ins（B| SB）<|C（B）|-1。到50.确保（18）能为真，则必有g（B）<|C（B）|-1，2 3 4 5 6 7图4.当d=8时DIBP的有效性。 |=200。|= 200.hins（B| B）稳定增长|S B|并且即使在我们重写为|C（B）|− 1φ。（二十）g（B）当真实的异常率是90%时。虽然只有50%的案例如图所示，在实践中改变异常值率仅影响hins（B）的值|SB）只要数据分布相似。必须包含至少一个真正的离群值。如果可以识别出这样的子集，则在节点扩展期间可以忽略B的对应于移除不在SB中的点的子节点-再次，这是因为经由B的可行性的最短路径必须经过SB;图2（b）说明了这个想法。为了找到这样一个SB，我们从B开始，SB，看看执行SB的可行性是否与以下不等式相h ins（B| S（B）> g（B），（18）对于具有线性残差的问题，（14）（S′=SB）为一个线性规划，其最优解位于顶点[19] 第 十 三 章 可 行 多 面 体 。 这 意 味 着 对 于 问 题（14），基大小加上最优解处的有效约束的数量必须是d+1。并且由于（14 b）中的每个绝对值约束最多可以贡献一个有效线性约束，因此最大数量活 动 约 束 的 |SB|.因 此 ，在 计 算 h ins （ B ） 时 ，|SB），平均基尺寸φ≥d+1− |SB|.把这个不等式代入公式（20）得到公式（19）。5. 主要算法算法3总结了A* 树搜索算法与我们的新的加速技术。重新排序完成这是（12）的扩展，其中h=hins. 类似从而首先执行更便宜的加速技术具体地说，给定当前基B，我们通过到h ins（B|s），h ins（B|SB）由问题（14）中的算法2的约束版本计算，其中S′= SB。这个观点是通过增加越来越多的限制在问题（14）中，平均基大小φ将逐渐减小，使得（15）的右手侧增加直到其超过左手侧，使得即使具有大d，分支修剪也将是有效的，具有高的真实离群值率。图-图4显示了DIBP对于具有线性残差的8维问题的有效性观察到h ins（B| SB）稳步增长，|SB|并且可以容忍超过90%的真实离群值，|SB|为|B|-1 = 8。在DIBP期间，我们希望尽快将真实离群值添加到SB中，因为如果SB不包含，则（18）永远不会为真真正的离群值。为此，我们使用相应的解决方案每个元素s∈ B，首先检查它是否导致重复的相邻节点，如果是，则跳过s（第8行）。否则，我们检查由s生成的节点B′是否与B不相邻，如果是，则丢弃B′（第11行）。如果不是，我们将B′插入队列，因为它不能被其他技术修剪之后，我们执行DIBP（第14行），如果满足条件（18），则跳过B中请注意，我们仍然可以将s添加到SB中，即使它导致重复的碱基。这种策略使DIBP在实践中更加有效6. 实验为了证明我们的新技术的有效性，我们比较了以下d =1D =2D =3D =4D =5D =6D =7D =8d =9D =101646A* 树搜索变体：1647i=1i=1算法3NAPA和DIBP为了验证树搜索的优越效率要求：S={si}N，阈值N。1：将具有优先级e（B）的B=τ（S）插入队列q。2：将哈希表T初始化为NULL。第三章： 当q不为空时4：从q中取e（B）最小的B。5：如果f（B）≤B，则返回B=B。6：SB← B;基于r（θg（B））对B进行降序排序|s）的情况。7：对于每个s∈ B，8：如果T中不存在V（B）的索引，则9：将V（B）的索引{s}散列到T中。10：B′←τ（C（B）\{s}）.11：如果l（B′）> l（B），则12：SB← SB{s}.13：在q中插入优先级为e（B′）的B′。14：如果|SB|为|B|第18章真的假的15：如果结束16：其他17：SB← SB{s}.18：如果结束19：结束20：结束while21：返回错误（没有大小大于p的内点集）。• 原始A* 树搜索（A*）[5]。• A* 与TOD用于分支修剪（A*-TOD）[6]。• 具有非邻接路径避免（A*-NAPA）的A*• A*-具有TOD分支修剪的NAPA（A*-NAPA-TOD）。• A*-具有DIBP分支修剪的NAPA（A*-NAPA-DIBP）。所有变体都在MATLAB 2018 b中实现，基于A* 的原始代码。对于具有线性剩余的问题，我们使用自己实现的顶点到顶点算法[3]来解决极大极小问题（4）和（14）。在非线性情况下，利用matlab函数fminimax解 决 了 这 两 个 问 题 。 所 有 实 验 在 具 有 Intel Core2.60GHz i7 CPU、16GB RAM和Ubuntu 14.04 OS的膝上型计算机上执行。6.1. 合成数据对照试验为了分析o和N对不同方法的影响，我们对不同N和o的8维稳健线性回归问题进行了对照实验。线性回归的残差形式为（2）。到生成数据S={ai，bi}N ，随机模型θ∈Rd首先生成了N个数据点，模型随机抽样。然后，我们随机选取N − o个点作为内点，并将均匀分布在[−0]之间的噪声分配给这些点的bi。1，0。1]中。然后，我们将噪声从[-5，-0]均匀分布到其他o点。1）∪（0. 1，5]以创建受控数量的离群值。将内值阈值设定为0.1。与其他类型的全局最优方法不同，在本实验中测试了基于混合可编程的BnB最先进的Guesthouse求解器被用作MIP的优化器。MIP的并行化由Guidelines使用8个线程完成，而所有的树搜索方法按顺序执行。如图5所示，所有A* 树搜索变体都比MIP快得多，即使MIP通过并行计算显著NAPA和DIBP都为A* 树搜索带来了相当大的加速，这可以通过使用和不使用这些技术的变体之间的差距来验证。注意，当N=200时，A*-NAPA在有和没有TOD的情况下具有相似的性能，而DIBP为所有数据提供稳定且显著的加速。有趣的是，具有更大的N使得A* 树搜索对于更大的o有效。这可以用条件（15）来解释。对于相同的o，较大的N意味着较低的真实离群值率，这使得（15）的可能性较小。6.2. 线性化基本矩阵估计实验也进行了真实数据。我们执行了线性化基本矩阵估计[6]的所有树搜索变体，其使用代数误差[13，Sec.11.3]作为残差，并忽略非凸秩-2约束。从KITTIOdometry数据集的序列00中选择5个图像对（前5个十字路口）[12]。对于每个图像对，输入是使用VLFeat[27]生成的一组SIFT [17]特征匹配。将内值阈值设置为0。03对于所有图像对。结果示于表1中。我们还显示了在每个算法终止之前生成的唯一节点数（NUN）和执行的分支修剪步骤数（NOBP）。对于所有数据，A*-NAPA-DIBP在不到10s的时间内找到了最优解，而A* 和A*-TOD通常无法在2 h内完成。A*-NAPA-DIBP在所有数据上的速度都快了500多倍，A* 和A*-TOD中最快的方法。对于每种技术的有效性，将NAPA应用于10个中的A* 导致超过10倍的加速。应用DIBP进一步加快了A*-NAPA超过1000倍的挑战性数据（例如，帧-198-201）。这意味着-加速度是因为SB中的那些导致冗余节点的，这使得大多数非-冗余路径被有效地修剪。TOD比DIBP的效率低得多，并且在帧104-108和帧198-201上为A*-NAPA引入了额 外 的 运 行 时 间 。 我 们 还 附 加 了 LRS ， 即 从 LO-RANSAC返回的离群值的估计数量[8]，这是一种有效的RANSAC变体。没有一个LO-RANSAC结果是最佳的。树搜索结果的可视化如图6所示。16483500300025002000150010003500300025002000150010005000010 20 30 40O(a)N= 2005000020 40 6070O(b)N= 400图6. (Top)帧-738-742上的A*-NAPA-DIBP的基本矩阵估计结果。（下）A*-NAPA-DIBP对数据BruggeTower的单应性估计结果。顶部的内围值（绿色）图5.对合成数据进行稳健线性回归的方法。d=8。为了清楚起见，数字被下采样到100。数据D=8框架-104-108o= 13（oLRS= 23）;N=302车架-198-201o= 13（oLRS= 19）;N=309车架-417-420o= 19（oLRS= 23）;N=385车架-579-582o= 22（oLRS= 25）;N=545车架-738-742o= 14（oLRS= 32）;N=476NUN/NOBP运行时间NUN/NOBP运行时间NUN/NOBP运行时间NUN/NOBP运行时间NUN/NOBP运行时间A*A*-TODA*-NAPAA*-NAPA-TODA*-NAPA-DIBP163232/0134589/11987135359/033165/22275205/311>6400>6400561.81770.087.63169369/0129680/12691123775/019308/13459105/160>6400>6400351.07451.393.88144560/080719/92627175806/015310/10946172/216>64003712.995993.68429.066.85136627/055764/58314147200/015792/1207360/84>64002709.21>6400576.823.49160756/049586/5011829574/014496/1075252/77>64001729.34471.15373.362.00A*-NAPA-DIBP vs前最佳法最佳先前法A*/A*-TOD更快>839x最佳先前法A*/A*-TOD更快>1648x最佳先前法A*-TOD更快541x最佳先前法A*-TOD更快775x最佳先前法A*-TOD更快864x表1.线性化基本矩阵估计结果。数据的名称是序列中的图像索引oLRS是估计的LO-RANSAC返回的离群值编号NUN：生成的唯一节点数NOBP：执行的分支修剪步骤数最后一行显示了A*-NAPA-DIBP比之前提出的最快变体（A* 和A*-TOD）快多少数据D=8亚当o= 38（oLRS= 40）;N=282市o= 19（oLRS= 22）;N=87波士顿〇= 43（〇LRS= 44）;N=678布鲁塞尔o= 9（oLRS= 25）;N= 231布鲁日塔o= 17（oLRS= 26）;N=208NUN/NOBP运行时间NUN/NOBP运行时间NUN/NOBP运行时间NUN/NOBP运行时间NUN/NOBP运行时间A*A*-TODA*-NAPAA*-NAPA-TODA*-NAPA-DIBP224/038/37168/038/3738/37538.91156.98404.77156.98156.987072/0462/5146481/0286/24134/40>6400910.51>6400485.3664.44406/07/6234/07/67/62455.0374.631284.1474.6374.63397/0359/281264/0249/19130/42437.25499.77268.85297.9150.135003/0333/2603731/0201/15140/48>6400298.394740.68161.9568.20A*-NAPA-DIBP vs前最佳法最佳先前方法A*-TOD在相同的运行时间最佳先前方法A*-TOD更快十三岁1x最佳先前方法A*-TOD在相同的运行时间最佳先前方法A*更快7 .第一次会议。7x最佳先前方法A*-TOD更快3 .第三章。4x表2.单应性估计结果。〇LRS是由LO-RANSAC返回的估计离群值数目。NUN：生成的唯一节点数。NOBP：执行的分支修剪步骤数最后一行显示了A*-NAPA-DIBP比之前提出的最快变体（A* 和A*-TOD）快多少6.3. 单应性估计（非线性）为了测试非线性问题的所有方法，在“homogr”数据集1上进行了单应性估计的另一个实验[13]和前面一样，我们挑选了5个图像对，计算SIFT匹配并将它们用作输入数据。一个图像[13]中的传递误差被用作残差，其形式为（3）。像素设置为4像素。表2显示了所有方法的结果。与线性情况相比，解决非线性极大极小问题（4）和（14）要耗时得多（使用fminimax可能慢100倍）。因此，使用类似的NUN和NOBP，运行时间要大得多。 然而，价值在非线性情况下的φ通常也小得多，这使得启发式hins以及所有分支修剪技术比线性情况下有效得多。对于波士顿和亚当这样的简单数据，执行-1http://cmp.felk.cvut.cz/data/geometry2view/index.xhtml使用TOD或DIBP都足以达到最高速度。尽管如此，DIBP在其他数据上仍然比TOD有效得多。而且DIBP从来没有像TOD有时那样减慢A*树搜索的速度（例如，布鲁塞尔）。A*-NAPA-DIBP在所有图像对上保持最快。图6中提供了视觉结果的示例。7. 结论我们提出了两个新的加速技术的consensus最大化树搜索。第一种方法避免了存在于共识最大化树结构中的冗余非相邻路径。第二个使得分支修剪对问题维度不那么敏感，因此更可靠。这两种技术带来的显着加速为实现实用和全局最佳共识最大化迈出了坚实的一步鸣谢。我们感谢dr.感谢李南提出的宝贵建议.MIP（并行）A*A*-TODA*-NAPAA*-NAPA-TODMIP（并行）A*A*-TODA*-国家适应行动方案A*-NAPA-TODA*-NAPA-DIBP运行时间运行时间1649引用[1] 尼娜·阿门塔，马歇尔·伯恩，大卫·埃普斯坦。网格平滑的最佳点放置。Journal of Algorithms，30（2）：302[2] Zhipeng Cai，Tat-Jun Chin，Huu Le，and David Suter.双凸规划的确定性一致最大化。在欧洲计算机视觉会议（ECCV），2018。[3] E. W.切尼近似理论导论。McGraw-Hill，1966年。[4] Tat-Jun Chin，Zhipeng Cai，and Frank Neumann.计算机视觉中的鲁棒拟合：容易还是难？在欧洲计算机视觉会议（ECCV），2018年。[5] Tat-Jun Chin ， Pulak Purkait ， Anders Eriksson ， andDavid Suter.树搜索的高效全局最优共识最大化在计算机视觉和模式识别（CVPR），2015。[6] Tat-Jun Chin ， Pulak Purkait ， Anders Eriksson ， andDavid Suter.树搜索的高效全局最优共识最大化IEEETransactions on Pattern Analysis and Machine Intelligence（TPAMI），39（4）：758[7] Ondrej Chum和Jiri Matas。与prosac匹配-渐进样本共识。计算机视觉和模式识别（CVPR），2005年。[8] Ondˇrej Chum 、Jiˇr´ı Matas和Josef Kittler 。