局部收敛最大一致性估计算法：解决计算机视觉中局部优化问题

1局部收敛最大一致性Huu Le、Tat-Jun Chin和David Suter阿德莱德大学计算机科学学院{huu.le，tat-jun.chin，david.suter}@ adelaide.edu.au摘要最大一致性估计在计算机视觉中起着至关目前，最流行的方法来自一类非确定性假设和验证算法，这是便宜的，但不能保证解决方案的质量。在另一个极端，存在全局算法，其本质上是穷举搜索，并且对于实际大小的输入可能是昂贵的本文旨在填补这两个极端之间的差距，提出了一个局部收敛的最大共识算法。我们的方法是基于一个制定的问题与线性互补约束，然后定义一个惩罚版本，这是可证明的等价于原来的问题。基于罚问题，我们发展了一个Frank-Wolfe算法来确定性地求解最大一致性问题.与随机化技术相比，我们的方法是确定性的和局部收敛的;相对于全局算法，我们的方法是更实际的实际输入大小。此外，我们的方法自然适用于几何残差1的问题。1. 介绍鲁棒模型拟合是计算机视觉的核心，因为许多基本任务需要处理噪声和被离群值污染的真实数据。为了进行鲁棒模型拟合，鲁棒拟合准则被优化w.r.t.一组输入测量值。可以说，最流行的鲁棒性标准是最大共识，其目的是找到与最大数量的内点一致的模型，即，有最高的共识。由于最大一致性估计的关键重要性，相当大的努力已经投入到设计算法优化的标准。大量的工作是在假设和验证方法的框架内进行的，即，[18]其变种。一般来说，这些方法通过将模型拟合到随机采样的数据的最小子集上来操作，并返回-1代码和演示在补充材料中提供。使用具有最大内围集的候选者。对基本算法的改进包括引导采样和加快模型验证步骤[4]。一 个 重 要 的 创 新 是 局 部 优 化 的 RANSAC （ LO-RANSAC）[6，15]。顾名思义，该方法的目标是局部优化RANSAC估计。这是通过在RANSAC中嵌入内部假设和验证例程来实现的，该内部假设和验证例程在解决方案在外部循环中更新与主RANSAC算法不同，内部子例程从从现任解的内围集采样的大于最小子集生成假设，希望将其推向改进的结果。虽然有效，但在假设和验证启发式中存在根本性的缺点首先，它不提供其解决方案的质量分析保证。这种弱点在LO-RANSAC中表现为算法不能严格保证局部收敛。启发式的随机性也意味着不同的运行可能会产生不可预测的不同结果，这使得它对于需要高重复性的任务来说并不理想。最近，有越来越多的全局最优算法用于共识最大化[19，26，7，16，3]。然而，最大一致性估计的基本棘手性意味着全局最优只能通过搜索来找到事实上，以前的技术分别进行分支定界搜索[26，16]，树搜索[3]或穷举搜索[19，7]。因此，全局算法仅在具有少量测量和/或低维模型的问题上是实用的。到目前为止，在文献中严重缺失的是一种位于上述两个极端之间的中间地带的出租权。具体而言，确定性和局部收敛的最大一致性算法将显著增加计算机视觉的鲁棒拟合工具箱在本文中，我们贡献这样一个算法。我们重新制定的共识最大化与线性复杂的约束，然后定义一个惩罚版本的问题。我们证明了，在容易实现的条件下，罚问题是等价的，在这个意义上，他们有相同的最优解。我们18881889J我我我我我我然后开发一个Frank-Wolfe算法来确定表示形式的每个约束|xTθ−y j|≤ ǫ局部地和局部地改进给定的最大一致性估算总的来说，我们的方法执行一系列线性等效地使用两个线性约束xTθ−yj≤，−xTθ+yj≤，（2）程序（LP），这使得它在realis-jj上是有效tic输入（数百到数千次测量）。Fur-并将数据收集到矩阵中因此，我们的算法自然能够处理非ΣA= x，−x，. . .得双曲余切值.，−xΣ、（3）计算机视觉中常用的线性几何残差[13，14]。正如将要证明的那样，我们的方法可以1 1N NΣΣTb= n + y1，n − y1，. . . ，n + y N，n− y N、（四）不断改进的粗略估计（获得我们-最小二乘、RANSAC等）而仅导致略微更高的运行时间。其中A∈Rd×M，b∈RM且M=2N，我们可以等价地将（1）改写为上述性质使我们的算法成为RANSAC及其变体的优秀后处理器，这些变体是当前的。Maxθ∈Rd，I ∈P（M）|I|（五）在该领域占主导地位。1.1. M估计和IRLS更广泛地说，在统计学中，M-估计量[12]是一种建立的稳健统计方法。通过最小化在残差上定义的一组ρ函数的和来获得M估计，其中ρ（例如，Huber范数）负责对离群值的影响进行贴现。最小化的主要技术是迭代加权最小二乘（IRLS）。在IRLS的每次迭代中，解决加权最小二乘问题，其中基于先前的估计来计算权重如果ρ满足某些性质[25，1]，IRLS将收敛到极小值.这就导致了最大限度的共识--如果Tθ−bi≤0<$i∈ I，其中ai是A的第i列，bi是A的第i个元素，B. 问题（1）和（5）是等价的，因为它们有相同的最大化者，尽管最大目标（5）的值是N加上（1）的最大目标值，因为对于任何θ，至少满足（2）中的一个约束。尽管如此，我们将基于（5）作为我们的目标问题来开发我们的最大共识算法。2.1.互补约束引入指标变量u∈ {0，1}M和松弛变量s∈RM，我们等价地将（5）转化为离群点计数最小化问题Σ因为对应的ρ（对称阶跃函数）不是正定的，也不是处处可微的。minu∈{ 0， 1}M，s∈RM，θ∈Rdui（6a）我可以说，人们可以简单地选择一个与IRLS一起工作的鲁棒ρ，并免除最大共识。然而，IRLS可行的另一个重要要求是加权最小二乘问题是有效可解的。不幸的是，对于计算机视觉中使用的许多几何距离，情况并非如此[13，14，10]。IRLS的上述局限性表明，局部收敛算法的鲁棒拟合仍然是一个悬而未决的问题，我们提出的算法应该代表朝着这个方向作出重大贡献。2. 问题定义我们开发我们的算法的背景下，拟合线性模型，然后扩展到模型的几何残差，在第二节。四点二。最大一致性的目标是找到由向量θ∈Rd参数化的一致性模型在si−aTθ+bi≥0的条件下，（6b）ui（si−aTθ+bi）=0，（6c）si（1−ui）=0，（6d）s i≥ 0。（6e）直觉上，如果第i个数据是相对于r.t.的异常值，则s i必须非零。在这种情况下，ui必须被设置为1以满足（6d）。反过来，（6c）迫使量（si− aTθ + bi）为零。相反，如果第i个数据是相对于.θ，则s i为零，ui为零，且（s i−aTθ+b i）非零。因此，观察到（6c）和（6d）实现了u i和（si−aTθ+ bi）之间的互补性。1890我j=1还应注意的是，由于目标函数和约束条件，版本（6d）中，可以放宽指标变量，而不影响最优值，从而导致等效问题 Σ利用尽可能多的输入数据，即，minu，s∈RM，θ∈Rdui（7a）我Maxθ∈Rd，I ∈P（N）|I|（一）不在si−aTθ+bi≥0的条件下，（7b）u（s-aTθ+b）=0，（7c）受|xjθ−y j|≤I，我我我其中{xj，y j}N是线性模型的N个测量的集合，N是内点阈值，P（N）是索引集合{1，2，. . . ，N}。si（1−ui）=0，（7d）1−ui≥0，（7e）s i，u i≥ 0。（7f）1891一我我我我我1个月1个月然而，这并不能使（7）易于精确求解，因为（7c）和（7d）在未知数中是双线性的。为了仅使用正变量重新表达（7），定义3.1. 最优性必要条件虽然P（z|α）是二次的，问题（10）是非凸的。然而，可以证明（10）具有顶点ΣΣv =θ+γ1γΣ， ci=T−aT1T，（8）解决方案，即，是凸集的一个端点P={z∈R2M+d+1|Mz+ q≥0， z≥0}，（15）其中两者都是长度为（d +1）的实向量。第1007章问题（七）可以等价地重新表述为 Σ哪里Σ Σ民乌伊u，s∈RM，v∈Rd+1我M =0 I-C，−I0 0如果si−cTv +bi≥0，ui（ si−cTv + bi）= 0，（九）Σ ΣTC = c 1c 2 . . .c M，Σ ΣT（十六）我si（1− ui）=0，1−ui≥0，si，ui，vi≥0.对于（9）的解u_n，u_s和v_n，只需从v_n的前-d个元素中减去v_n的最后一个元素即可得到（7）的相应解θ_n3. 刑罚方法将等式约束条件转化为代价函数作为惩罚项，我们得到惩罚问题q =bT1T;(here并且此后，为了最小化混乱，我们不定义I、0和1的大小，但是可以基于上下文来计算大小首先，观察到（10）的最小值服从KKT条件[18，Chap. 第十二章]uT（−α Cv +α b +1+λG）= 0，sT（α1−λH）= 0，vT（−α CT u + CTλH）= 0，（λH）T（s− Cv+ b）= 0，（十七）minu，s，vΣui+ α我Σ Σui（si−cTv +bi）+si（1−ui）（λG）T（1−u）= 0，s-Cv + b≥ 0，S.T.s i− cTv + b i≥0，1−u i≥ 0，si，ui，vi≥0.（十）常数α≥0称为罚参数。直观地说，惩罚项阻止了违反互补约束的解，并且概率化的强度由α控制。为了减少混乱，我们有时会使用1−u≥0，λH， λG，u，v，s≥0，其中λH=[λH. . . λH]T和λG=[λG. . .λG]T是（10）中前两种约束的拉格朗日乘子;详见补充材料。通过重新排列，KKT条件（17）可以由以下关系式M′z′+q′≥0，z′≥0，（z′）T（M′z′+q′）=0，（18）Σz = uT sTvTT.（十一）哪里另外，（10）中的成本函数被重写为P（z |α）= F（z）+ αQ（z），（12）其中F（z）=1，z′=<$zT（λH）T（λG）T<$T，0 0−α C 0 I00 0−I0Q（z）=Σ u（s-cTv+b）+s（1−u）（13）M′=α CT0 0CT0分，（十九）我我我0I−C 00Σ=s − u（cTv − b）。（十四）1892- 我0 0 0 0我我我我我q′=Σ（αb+1）Tα1T0TbT1吨。特别地，Q（z）被称为互补残差。节中 3.3我们将调查其中求解（10）等价于求解（9），并在Sec. 4利用等价性实现共识最大化。首先，在接下来的两节中，我们讨论对给定α的罚问题（10）的求解。找到（18）的可行z′是线性互补问题（LCP）的一个例子[17]。定义凸集P ′={z′∈R4M+d+1|M′z′+ q′≥0，z′≥0}。 （20）我们从[17，引理2]中引用以下结果1893vvvJ我JJ我定理1如果由约束（18）定义的LCP具有算法1的Frank-Wolfe方法（10）。一个解，则它在P′的顶点有一个解。要求：数据{c，b}M，罚值α，初始解我ii =1定理1表明（10）的KKT点（包括问题的解）出现在P′的顶点上.这也意味着（10）有一个顶点解，即：定理2对任意顶点u（0），v（0），s（0），阈值δ。一曰： P（0）←P（u（0），s（0），v（0））|α）。2：t← 0.第三章： 而真正的4： t←t+1。5： s（t），v（t）←arg mins，vP（u（t−1），s，v|α）s.t.P.z′= [zT（λH）T（λG）T）]T（21）v v v v其中zv是P′的一个顶点。证明如果z′是P′的一个顶点，则存在一个对角矩阵这样，M′Ez′+ q′−γ′= 0，（22）其中，如果M′的第i列出现在对应于顶点z′的基本解中，则Ei，i=1，否则Ei，i=0（非负向量γ′包含附加松弛变量的值，以将P′中的约束转换为标准松弛变量）。6： u（t）←arg minuP（u，s（t），v（t））|α）s.t. P.7： P（t）←P（u（t），s（t），v（t））|α）。8： 如果|P（t−1）−P（t）|≤ δ则9：休息。10：如果结束11：结束while12：返回u（t），v（t），s（t）。更新步骤的分析更仔细的观察揭示了第5行（算法1）中的LP是形式）。 设M′是M′的最后2M行。然后，M′ Ez′ + ΣΣTbT1T-γ′=0，（23）mins，vsi−ui（cTv−bi）J v J其中γ′是γ ′的最后2M个元素。 注意，由于S.T.S我i−cTv +bi≥0，（LP1）M′最右2M×2M子矩阵为零矩阵si，vi≥0，(see（19），然后M′ Ez+bT1TT−γ′=0，（24）并且行6（算法1）中的LP为J K vJminΣΣ Σui1− α（cTv− bi）其中EK是E的前-（2M+d+1）列。以来M′EK= M，则（24）蕴涵zv是P的一个顶点。uii（LP2）J3.2. 弗兰克沃尔夫算法定理2提出了一种通过寻找顶点解来求解（10）的方法此外，请注意，对于固定的u，（10）简化为LP。相反，对于固定的s和v，（10）也是LP。这提倡使用LP在优化变量的子集之间交替算法1总结了该方法，其实际上是用于非凸二次最小化的Frank-Wolfe方法[9]定理3在有限步中，算法1收敛到（10）的KKT点.证明约束P的集合可以解耦为两个不相交的子集P=P1×P2，（ 25）其中P1只涉及s和v，P2是P1的补集。当u固定在第5行时，LP收敛到P1的一个顶点.类似地，当s和v固定在第6行时，LP收敛到P2中的一个顶点。因此，每个中间解u（t），v（t），s（t）是P的顶点或（10）的KKT点。由于每个LP必须减少或保持P（z |α），该过程以有限步终止。1894我S.T. 0≤u i≤ 1。观察到LP 2可以以封闭形式求解，并且它也将u驱动为完整性：如果[1−α（cTv−b i）]≤0，则设置ui=1，否则，设置u i= 0。此外，LP 1可以被看作是“加权”的n-1范数最小化，其中u是权重。因此，直观地，算法1在残差最小化（LP 1）和内点-外点二分化（LP 2）之间交替。3.3. 惩罚的准确性罚问题（10）是非光滑精确罚方法的一个实例[18，Sec.17.2]。注意Q（z）是等式约束的LHS的LHS范数。惩罚的精确性在下面的定理中得到了证明（在我们的问题中重新表述）。定理4（在[ 18 ]定理17.3的基础上）若z∈ P是原问题（9）的局部解，则存在α∈>0使得对所有α≥α∈，z∈ P也是P（z）的局部极小子|a）受约束P。直观地说，该定理指出问题（10）有一个足够大的α，使得任何远离z的微小移动都将受到αQ（z）的足够强的惩罚。1895Ji=1以立即否定通过违反互补性约束而能够实现的对F（z）的任何潜在约简。一个后续的定理将证明对我们的目的更有用。或者通过执行RANSAC（Sec. 5将比较这两种不同初始化方法的结果）。其他所需的输入是初始惩罚参数α以及增量率κ。这些值会影响转换-Theorem5（基于[18]中的Theorem17.4）令z是算法2的收敛速度。 为了避免坏的最小值，我们设置惩罚问题（10）的KKT点，α大于αα 则Q（z）=0，z也是（9）的KKT点。然而，将α设置为一个非常大的值并求解（10）的单个实例的在下一节中，我们将描述一种更实用的方法，该方法使用α的递增序列。4. 主要算法α和κ保守地，例如，α∈[1，10]，κ∈[1，5]. 我们将在SEC中演示5、这些设置启用Algo-rithm 2在竞争激烈的运行时找到非常好的解决方案4.2.处理几何距离对于计算机视觉中的大多数应用，用于几何模型拟合的残差函数是非线性的。然而，已经表明[13，19，2]，许多几何残差具有以下广义分数形式基于上述结果，我们提出了我们的主要算法-α Gθ+hβprTθ+q其中rTθ+q>0，（26）解决最大一致性问题的算法（9）;参见算法2.我们的方法使用算法1成功地解决了（10），其中特定α的解z用于初始化下一个较大α的算法1。当互补残基Q（z）消失时，序列终止。只要每个z是一个KKT点，其中，n·np是p-范数，G∈R2×d，h∈R2，r∈Rd，q ∈ R1是由输入数据导出的常数. 例如，三角测量中的重投影误差和单应性估计中的传递误差可以以形式（26）编码相关的最大共识问题是相关的惩罚问题（10），我们可以证明-由于定理3，定理5保证了Maxθ∈Rd，I ∈P（N）|I|算法2将收敛到满足最优性的一阶必要条件的（9）的解算法2主要算法求解（9）.要求：数据{ci，bi}M，初始模型参数θ，初始罚值α，增量率κ，阈值δ.服从<$Gjθ+h j<$p≤ <$（rTθ+q j）j∈I，（二十七）其中（26）的分母可以移动到RHS，因为RHS是非负的（详见[13]）。我们表明，对于p=1，我们的方法可以很容易地适应解决（27）到局部最优2。定义1：v← Σ（θ +）|最小j（θ j）|1）TΣT|.|.Σ Σ Σ Σ2：u←I（Cv−b>0）。3：s←u（Cv − b）.Gj=不j，1Tj，2hj=hj，1hj，2.（二十八）第四章： 而真正的5：u，s，v ←FW（{ci，bi}M，α，u，s，v）。/*Algo。1.*/现在，对于p=1，（27）中的约束变为i=1.T..T.不6：如果Q（z）≤δ，则7：休息。8：如果结束图9： α←κ·α。10：结束时11：返回u，s，v。值得注意的是，典型的非平滑惩罚函数不能被容易地最小化（例如，没有梯度信息）。然而，在我们的例子中，我们利用了（10）的特殊性质。3.1）以实现有效的最小化。4.1. 初始化算法2需要初始化u、s和v。对于共识最大化，更自然的是初始化模型参数θ，这反过来又为v，s和联合在我们的工作中，我们将θ初始化为最小二乘解，GG1896. gj，1θ +hj，1. +。gj，2θ +hj，2. ≤n（rjθ+qj），（29）这又可以使用四个线性约束来等效地实现（细节参见[2]）。然后，我们可以将（27）操纵成形式（5），我们的理论和算法的其余部分将立即适用。5. 结果我们测试了我们的方法（算法2，此后焦维，命名为EP）对常见的参数估计问题。我们将EP与以下众所周知的方法进行了比较：• RANSAC（RS）[8]：我们使用置信度ρ=0。99的停止标准在所有实验中。在每个数据实例上，RANSAC执行10次，并报告平均共识大小和运行时间2请注意，在存在离群值的情况下，残差不再是独立同分布。正常因此，对于鲁棒拟合，1-范数与2-范数同样有效1897j=1• LO-RANSAC（LORS）[6]：更新后的共识集上内部采样的最大迭代次数设置为100。• 改进的LO-RANSAC（LORS 1）[15]：正如所提议的，只有当新的共识大小高于预定义的阈值（在我们的实验中设置为数据大小的10%）时，才会运行局部细化• 近似（101）[20]：这种方法相当于将松弛变量引入问题（5），并最小化松弛变量的101-范数，以产生最大共识的近似解。•去 除离群值（l∞）[21]：同样，在（5）的上下文中，引入了松弛变量，并且最大松弛值被最小化。删除具有最大松弛值的数据，并重复该过程，直到0.50-0.5-110.50-1-0.5 0 0.5 1-0.5 0 0.5 1最大松弛值不大于零。• 对于关键点匹配分数可用作内点先验的图像数据的实验，我们执行了两种最先进的RANSAC变体 ： PROSAC （ PS ） [5] 和 Guided MLESAC（GMLE）[23]。所有的方法和实验都是在MATLAB中实现的，并在标准的桌面机器上运行，3.5 GHz处理器和8 GB RAM。对于EP、EP1和EP∞，Guesthouse被用作LP求解器。5.1. 线性模型合成数据线性回归我们产生N=500点{xj，yj}N在R9中遵循线性趋势图1. 在我们的实验中生成的平衡（顶部）和不平衡（底部）数据的2D模拟。RANSAC，最小二乘法，我们的方法与前两种方法初始化的结果显示。观察到最小二乘在非平衡数据下严重偏置，但EP能够从错误的初始化中恢复EP-LSQ。很明显，在溶液质量方面，EP的两种变体始终优于其他方法。事实上，EP-LSQ可以匹配EP-RS的质量不平衡的数据证明了EP的能力，从坏的初始化。在运行时间方面，虽然两种EP变体都比RANSAC变体稍贵，但随着pout增加超过35%，EP-LSQ开始超过RANSAC变体（因为EP-RS已初始化y=xTθ，其中θ∈R8和xj∈[−1，1]8是随机的-多姆利采样。每个yj都受到高斯噪声的扰动使用RANSAC，其运行时间也随着pout）。标准差为σ in= 0。1.一、为了模拟离群值，随机选择并破坏yj的pout%为了测试EP处理不良初始化的能力，考虑了两种不同的离群值设置• 平衡数据：离群值的yj加上σout=1的高斯噪声。这将异常值均匀地分布在超平面的两侧• 不平衡数据：如上所述，但是加性噪声的符号被强制为正。因此，离群值仅分布在超平面的一侧在这样的数据上，最小二乘解是有严重偏差的。这些异常值设置的2D模拟见图1。我们用p out={0，5，10}进行测试。. .，60}。最大一致性的内点阈值设定为0。1.一、EP分别用RANSAC（变异EP-RS ）和最小二乘（变异EP-LSQ）初始化 初始α设置为0。对于所有运行，κ=5图2显示了终止时的平均共识大小和运行时（以对数刻度）的方法。请注意，RS和LSQ的运行时间包含在EP-RS的运行时间中，基本矩阵估计遵循[11，第11]，对极线约束进行线性化，以使基要线性估计的心理矩阵（注意，用于基本矩阵估计的通常几何距离不具有广义分数形式（26），因此线性化对于实现我们的方法是必要的秒5.2将描述几何距离模型估计的结果）。使用了来自VGG数据集的五个图像对：Corridor、House、Merton II、Wadham和Aerial View I。首先调整图像大小，然后使用SIFT（如在VLFeat [24]上实现的）提取每对约500个对应。对于所有图像对，均使用内点阈值=1对于EP，除了使用RANSAC和最小二乘法进行初始化外，我们还使用Ep∞离群值去除（变体EP-Ep∞）进行初始化。对于所有EP变体，初始α设定为0。对于所有运行，κ=5表1（顶部）总结了所有方法的定量结果。无论初始化方法如何，EP都能够找到最大的共识集。虽然EP的运行时间更高，但它们仍然与其他版本处于相同的量级图3（a）显示了EP的样品定性结果;另一张图片的定性结果EP-RSEP-LSQRsEP-RSEP-LSQRs1898350 330022502001501003002001000 10 20 30 40 5060(a)终止时的共识大小（平衡数据）。0 10 20 30 40 5060(c)终止时的共识大小（不平衡数据）。10-10 10 20 30 40 50 60(b)单位为秒（对数标度，平衡数据）。210-10 10 20 30 40 50 60(d) 以秒为单位（对数标度，不平衡数据）。图2. 线性回归的结果（d= 8维）。（a）（b）平衡的数据;（c）（d）数据不平衡。(a) 走廊（b）基督堂。（c）树木。图3. EP关于（a）基本矩阵估计、（b）单应性估计和（c）亲和性估计的定性结果。绿线和红线表示检测到的内值和离群值。为清楚起见，仅绘制了100个内值/离群值更多结果请参见supp材料请参阅补充材料。5.2. 几何距离单应性估计我们使用所有方法基于传递误差估计2D单应使用了来自VGG数据集的五个图像对：大学图书馆，基督教堂，瓦尔邦，卡佩尔和巴黎的Invalides.与基本矩阵估计实验中相同的预处理和对应提取方法对于所有输入数据，均使用内点阈值=4初始α设置为10，κ= 1。5适用于所有EP变体。定量结果见表1（中），EP的样品定性结果见图1。3（b）款。与基本矩阵情况类似，EP变体在解质量方面优于其他方法，但速度较慢，但运行时间仍在相同范围内数量级。请注意，这里没有调用EP-LSQ，因为通常难以基于几何距离找到最小二乘估计值[10]。亲和力估计重复先前的实验以进行亲和力（6 DoF仿射变换）估计，其中初始α设置为0。5，κ=5，且λ=2个像素。使用来自VGG的仿射图像数据集的五个图像对：自行车，格拉夫，树皮，树和船。定量结果见表1（中），样品定性结果见图1。3（c）款。可以得出类似的结论。利用离群点污染下的重投影误差估计三维点的三角我们从NotreDame数据集[22]中选择了五个特征轨迹，每个轨迹具有超过N=150个视图来测试我们的算法。将最大一致性的内点阈值设置为1像素。α最初设置为0.5，1899方法RsPSGMLELORSLORS1ℓ1ℓ∞EP-RSEP-LSQEP-100房子N = 556|我|时间2502.122511.602541.092571.332563.411750.22050.062677.622674.792674.96空中N = 421|我|时间2670.122610.162660.12830.172830.272820.152770.032971.912972.012971.67默顿N = 590|我|时间3670.143440.273700.093770.213830.324080.254040.044512.844512.754513.69沃德姆N = 587|我|时间4470.054260.084730.044700.124760.155030.24330.045122.995123.295123.06走廊N = 686|我|时间2635.232694.222634.642663.872659.062460.722640.0830315.263035.573035.75方法RsPSGMLELORSLORS1ℓ1ℓ∞EP-RSEP-100单应性估算高校图书馆N = 545|我|时间2510.732690.622510.692941.902941.891203.10532.4930112.7630114.49基督教堂N = 445|我|时间2350.472360.472270.432501.332461.612461.231602.4428010.3728012.67ValbonneN = 434|我|时间1313.171342.391175.761563.041365.80241.36221.2715817.2015814.84卡佩尔N = 449|我|时间1631.191671.151309.891672.181682.70281.621611.161708.461708.68InvalidesN = 413|我|时间1441.361590.901401.601492.171562.94841.041420.7117810.201789.15亲和度估计自行车N = 557|我|时间4246.094276.094255.794266.2842411.83871.774311.7743715.264379.81格拉夫N = 327|我|时间1263.511293.351273.141344.071266.611470.992740.232765.942762.70树皮N = 458|我|时间2794.892884.932704.682845.112799.542981.314390.1944210.194425.51树N = 568|我|时间3725.703676.013715.733726.9337211.503774.813700.8139615.9639611.82船N = 574|我|时间4766.324776.294766.024777.1847612.324694.124641.0248314.864839.33第719N = 192第585N = 153点570N = 167点24N = 155点1N = 167|我|时间|我|时间|我|时间|我|时间|我|时间Rs1020.26770.13470.141110.14940.15LORS1021.16770.60470.651110.71940.78LORS11030.29770.24470.261110.25940.26ℓ1610.27200.17140.23600.13620.33ℓ∞961.29610.75350.951110.46811.06EP-RS1072.06801.02541.401131.10960.96EP-1001073.08801.70542.221131.35962.16表1. （顶部）基本矩阵估计结果。（中）单应性估计和亲和性估计结果。（底部）三角测量结果。 性别：|我|=终止时的一致性大小，RS=RANS A C，PS=PR OS A C，GMLE=引导MLES A C，LORS= LO-RANSAC，LORS 1 =改进的LO-RANSAC，EP =采用不同初始化技术的建议方法。κ= 1。5对于EP的所有变体表1（底部）显示了定量结果。同样，EP变体在解决方案质量方面优于其他方法。由于模型的低维性（d=3），运行时间差距在这里并不显著。6. 结论我们介绍了一种新的局部收敛算法的最大共识，基于互补约束的精确惩罚。在解的质量方面，我们的算法优于其他启发式和近似方法-这是由我们的方法被证明，特别是-能够改进RANSAC的解决方案。即使在出现不良初始化时（即，当使用最小二乘法对不平衡数据进行初始化时），我们的方法能够恢复并获得良好的解决方案。虽然我们的方法可能会慢一些，但与随机算法不同，它能够保证收敛到局部最优。事实上，在高离群率下，我们的方法实际上比RANSAC变体更快，同时产生更高质量的结果。致谢本工作得到ARC资助DP160103490的支持。1900引用[1] K. Aftab和R.哈特利迭代重加权最小二乘对稳健m-估计量的收敛性。在2015年IEEE计算机视觉应用冬季会议上，第480-487页。IEEE，2015年。2[2] S. Agarwal，N.Snavely和S.M. 塞茨多视图几何l问题的快速算法计算机视觉和模式识别，2008年。CVPR2008。IEEE会议，第1-8页。IEEE，2008年。5[3] T.- J. Chin，P. Purkait，A. Eriksson和D.苏特树搜索的高效全局最优共识最大化。在IEEE计算机视觉和模式识别会议论文集，第2413-2421页1[4] S.崔，T. Kim和W. Yu. RANSAC家族的性能评估。英国机器视觉会议（BMVC），2009年。1[5] O. Chum和J. Matas。与prosac-progressive样本共识匹配。2005年IEEE，2005年。6[6] O. Chum、J. Matas和J.基特勒局部优化的ransac。在DAGM。施普林格，2003年。1、6[7] O. Enqvist，E. 问吧F Kahl和K. 一个大漩涡。多视图几何体的旋转式拟合在欧洲计算机视觉会议上，第738-751页。Springer，2012. 1[8] M. A. Fischler和R. C.波尔斯随机样本同意：一个范例模型 拟 合 与 应 用 程 序 的 图 像 分 析 和 自 动 制 图 。Communications of the ACM，24（6）：381-395，1981.一、五[9] M. Frank和P.沃尔夫二次规划的一个算法.《海军后勤研究》，1956年第3期（95）。4[10] R. Hartley和F.卡尔多视图几何中的优化算法。在亚洲计算机视觉会议上，第13-34页。Springer，2007. 二、七[11] R. Hartley和A.齐瑟曼。计算机视觉中的多视图几何。剑桥大学出版社，2003年。6[12] P. J. Huber等人位置参数的鲁棒估计。数学统计年鉴，35（1）：73-101，1964年。2[13] F.卡尔多视图几何和l范数。 在第十届IEEE计算机视觉国际会议（ICCVIEEE，2005年。二、五[14] Q. Ke和T.卡纳德鲁棒几何重建的拟凸优化。IEEETransactionsonPatternAnalysisandMachineIntelligence，29（10）：1834 2[15] K. Lebeda、J.Matas和O.好朋友修复局部优化的ransac-full实验评估。在英国机械视觉会议上，第1-11页。Citeseer，2012年。1、6[16] H.李鲁棒几何估计的保证全局最优性的一致集最大化。2009年IEEE第12届计算机视觉国际会议，第1074-1080页。IEEE，2009年。1[17] O.曼格萨里安线性互补问题作为线性规划的特征。在互补性和不动点问题，第74-87页Springer，1978年。3[18] J. Nocedal和S.赖特数值优化Springer Science BusinessMedia，2006. 三、四、五[19] C. Olsson，O. Enqvist和F.卡尔一个多项式时间边界的匹配和配准与离群。计算机视觉和模式识别，2008年。CVPR 2008。IEEE会议，第1-8页。IEEE，2008年。一、五[20] C. Olsson，A. P. Eriksson和R.哈特利使用对偶去除离群值。在IEEE国际会议上在Copmuter Vision and PatternRecognition中，第1450-1457页。IEEE计算机学会，2010年。6[21] K. Sim和R.哈特利使用linfty norm去除离群值。在2006年 IEEE 计 算 机 协 会 计 算 机 视 觉 和 模 式 识 别 会 议（CVPRIEEE，2006年。6[22] N. Snavely，S. M. Seitz和R.塞利斯基摄影旅游：探索3D照片集。在ACM transactions on graphics（TOG），第25卷，第835-846页。ACM，2006年。7[23] B. J. Tornard和D. W.默里Guided-mlesac：利用匹配先验的快速图像变换估计。IEEE模式分析与机器智能学报，27（10）：1523-1535，2005年。6[24] A. Vedaldi和B.富尔克森Vlfeat：一个开放的、可移植的计算机视觉算法库。第18届ACM国际多媒体会议论文集，第1469-1472页。ACM，2010年。6[25] Z.张某确定对极几何形状及其不确定性：审查. 国际计算机视觉杂志，27（2）：161-195，1998。2[26] Y. Zheng，S. Sugimoto和M.奥富确定性最大化可行子系统用于单位范数约束的鲁棒模型拟合在计算机视觉和模式识别（CVPR）中，2011 IEEE会议，第1825IEEE，2011年。1