MAGSAC：一种快速、可靠、准确的鲁棒估计器

1MAGSAC++，一个快速、可靠、准确的鲁棒估计器Daniel Barath12岁，Jana Noskova1岁，Maksym Ivashechkin1岁，Jiri Matas1岁1布拉格捷克技术大学控制论系视觉识别组2布达佩斯市MTA SZTAKI机器感知研究实验室sztaki.mta.hu摘要提出了一种新的抗差估计方法MAGSAC++1。它引入了一个新的模型质量（评分）功能，不需要内-外决策，和一个新的边缘化过程制定为一个M-估计与一类新的M-估计（一个强大的内核）解决了迭代重新加权最小二乘程序。我们还提出了一个新的采样器，渐进NAPSAC，RANSAC样的鲁棒估计。利用附近的点通常来自真实世界数据中的相同模型的事实，它比全局采样器更早地找到局部结构。从局部采样到全局采样的渐进过渡在六个公开可用的真实世界数据集的单应性和基本矩阵拟合，MAGSAC++产生优于国家的最先进的强大的方法的结果。它速度更快，几何精度更高，故障频率更低。1. 介绍RANSAC（RANDom SAmple Consensus）算法[5]已成为计算机视觉中使用最广泛的鲁棒RANSAC及其变体已成功应用于广泛的视觉任务，例如，运动分割[27]，短基线立体声[27，29]，宽基线匹配[19，14，15]，几何图元检测[23]，图像拼接[7]，以及执行[32]或初始化多模型拟合[9，18]。简而言之，RANSAC重复地选择输入点集的最小随机子集并拟合模型，例如，两个2D点的直线或七个2D点对应的基本矩阵接下来，例如通过其支持的基数来测量估计模型的质量，即，inlier数据点的数量。最后，具有最高质量的模型，抛光，例如，通过所有内点的最小二乘拟合，返回。1https://github.com/danini/magsac(a) CommunityPotoCollectiondataset[30].(b) ExtremeViwdaset[11].(c) Tan k sanddTemmplesdataset[10].图1.图像对，其中所有测试的鲁棒估计器（即，LMeDS[22]，RANSAC [5]，MSAC [28]，GC-RANSAC [1]，MAGSAC [2]）失败，除了建议的MAGSAC++。由MAGSAC++找到的内点对应由线绘制。自RANSAC算法发表以来，人们提出了许多改进算法。例如，MLESAC [28]通过最大似然过程及其所有有益特性来估计模型质量，尽管是在关于数据分布的某些假设下。在实践中，MLESAC结果通常优于普通RANSAC的内点计数，并且它们对用户定义的内点-离群点阈值不太敏感。在MAPSAC [26]中，鲁棒估计被公式化为估计13041305根据最大后验概率匹配数据分布的参数和模型的质量。用于减少对内点-外点阈值的依赖性的方法包括MINPRAN [24]，其假设外点均匀分布，并找到内点最不可能随机发生的模型。Moisan等人[16]提出了一种相反的RANSAC，为每个模型选择最可能的噪声尺度 。 Barath 等 人 [2]提 出了 边 缘化 样 本一 致性 方 法（MAGSAC），对噪声σ进行边缘化，以消除模型质量计算中的阈值。MAGSAC算法，除了不需要一个人工设置的阈值，据报道，在各种问题上，在许多数据集上比其他鲁棒估计更准确。准确性的提高源于新的模型质量函数和σ-一致性模型抛光。质量函数在噪声尺度上边缘化，数据被解释为均匀分布的离群值和内点的混合物，残差 具 有 χ2 分 布 。 σ- 一 致 性 算 法 用 加 权 最 小 二 乘（WLS）代替了最初使用的最小二乘（LS）拟合，其中通过边缘化过程计算权重-这需要对不同的点集进行许多独立的LS估计。由于几个LS拟合，σ-共识是缓慢的。在[2]中，许多技巧（例如，抢先验证; σ值的下采样）来实现可接受的速度。然而，MAGSAC通常比其他鲁棒估计器慢得多。在本文中，我们提出了新的质量和模型抛光功能，reformulating问题作为一个M-估计与一类新的M-估计（鲁棒核）通过迭代重加权最小二乘程序解决。在每个步骤中，权重的计算与MAGSAC中的数据分布假设相同，但不需要大量昂贵的LS拟合。所提出的MAGSAC++和σ-consensus++方法比原始MAGSAC算法产生更准确的结果，通常快一个数量级。在实践中，还有其他方法可以加速鲁棒性估计。NAPSAC [20]和PROSAC [4]修改了RANSAC采样策略，以增加早期选择全内点样本的概率。PROSAC利用点的先验预测内点概率秩，并从最有希望的点开始采样PROSAC和其他类似RANSAC的采样器处理模型时没有考虑内点通常彼此邻近。这种方法在寻找内点稀疏分布的全局模型时是有效的，例如，在两视图匹配中改变视点然而，正如它经常通过在采样中利用这一点，大大加快了速度NAPSAC假设内点是空间相干的。它从以第一个随机选择的点为中心的超球体中绘制采样如果该点是内点，则在其附近采样的其余点比球外部的点更可能是内点。在许多情况下，NAPSAC可以快速、成功地终止然而，它在实践中遇到了一些问题。首先，由于点的条件不好，拟合局部全内点样本的模型通常是不精确的。其次，在某些情况下，从局部样本中估计模型会导致退化解。例如，当通过七点算法拟合基本矩阵时，对应关系必须来自多个平面。因此，在接近的、可能的全内点和全局的、良好条件的、较低的全内点概率样本之间存在权衡。第三，当点稀疏分布且在空间上不连贯时，NAPSAC通常无法找到所寻求的模型。除 了 MAGSAC++ 之 外 ， 本 文 还 提 出 了 渐 进 式NAPSAC（P-NAPSAC）采样器，该采样器通过从逐渐增长的邻域中抽取样本来融合考虑到附近的点更有可能来自相同的此外，由于从局部采样到全局采样的渐进混合，它不会遭受纯局部采样器的弱点，其中混合因子是输入数据的函数。在六个公开的真实数据集上对所提出的方法进行了单应性和基本矩阵拟合的测试。结合P-NAPSAC采样器的MAGSAC++在速度、精度和故障率方面优于最先进的稳健估计器。当除MAGSAC++之外的所有测试的稳健估计器失败时，示例模型估计1.一、2. MAGSAC++我们提出了一个新的质量函数和模型拟合程序MAGSAC [2]。它表明，新的方法可以制定为一个M-估计求解的迭代加权最小二乘（IRLS）算法。边缘化样本一致性（MAGSAC）算法基于两个假设。首先，噪声水平σ是具有密度函数f（σ）的随机变量。在没有先验信息的情况下，假设σ是均匀分布的，σ<$U（0，σmax），其中σmax是用户定义的最大噪声尺度。其次，对于给定的σ，内点的残差由具有n个自由度的修剪χ分布2乘以具有密度的σ来g（r |σ）= 2 C（n）σ−nexp（− r2/2σ2）rn−1，在真实世界的数据中，如果模型是本地化的，内点彼此接近，鲁棒估计可以2χ2分布的平方根。1306对于r<τ（σ）和g（r|对于r≥τ（σ），σ）= 0。恒定C（n）=（2n/2Γ（n/2））−1，并且对于a>0，设τ（σ）= kσ为χ分布的选定分位数。对于0≤r≤kσmax，Γ（a）=∫+∞0ta−1exp（−t）d tw（ r）= σ. - 是的 21MaxΣσmaxR/K.g（r |σ）dσ=2ΣΣ是伽马函数，n是计算残差的欧几里得空间的维数，τ（σ）设置为1σmaxC（n）2n−12n −1Γ，2R2Maxn−1k-r，2 2高分位数（例如，0的情况。99.非对称分布。假设我们给定输入点集P和模型θ，如RANSAC中那样从数据点的最小样本估计。令θσ=F（I（θ，σ，P））是从使用输入模型θ周围的τ（σ）选择的内点集I（θ，σ，P）估计的模型。标量τ（σ）是σ所代表的阈值;函数F从一个集合中估计模型参数函数I返回点到模型残差小于τ（σ）的数据点集。对于每个可能的σ值，点p ∈P内点计算为当r> kσmax时，w（r）= 0. 功能∫+∞Γ（a，x）=ta−1exp（−t）dtX是上不完全伽马函数。权重w（r）是正的并且在区间（0，kσmax）上递减。因此，存在M-估计量的ρ-函数，其通过使用w（r）的IRLS最小化，并且每次迭代保证其损失函数不增加（[13]，第9章）。因此，它收敛到局部最小值。这P（p|θσ，σ）= 2C（n）σ−nDn−1（θσ，p）exp.Σ−D2（θσ，p）2σ2，IRLS，τ（σ）=3。64σ，其中3. 64是0。99分位数我们称之为σ-一致++。对于使用点对应的问题，n=4。参数σmax与用户定义的最大噪声水平参数相同，如果D（θσ，p）≤τ（σ），其中D（θσ，p）是点到模型的残差。若D（θσ，p）>τ（σ），则似然P（p|θσ，σ）为0。在MAGSAC中，通过加权最小二乘法计算最终的模型参数，其中点的权重来自对σ上的似然性的边缘化。当在σ上边缘化时，每个P（p| θσ，σ）计算要求选择内点集，并通过LS拟合获得θσ，他们这一步是耗时的，即使在论文中提出的加速的数量。在MAGSAC++中，我们提出了一种新的方法，而不是原来的方法，当边缘-在MAGSAC中，通常设置为相当高的值，例如，10像素。σ-consensus++算法用于拟合非最小样本，也可作为后处理来改善任何鲁棒估计器的输出。2.2.模型质量函数为了能够选择最能解释数据的模型，必须定义质量函数Q。让1Q（θ，P）=，（3）L（ θ，P）在噪声水平σ上进行调整。所提出的算法是迭代重加权最小二乘（IRLS），其中第（i+1）步中的模型参数计算如下：哪里L（ θ，P）=Σp∈Pρ（D（θ，p）），是由我们的权重定义的M估计量的损失函数θi+1=ar gminθw（D（θi，p））D（θ，p），（1）函数w（r）。函数ρ（r）=rxw（x）dx，其中r ∈p∈P0[0，+∞）。对于0≤r≤kσmax，其中点p的权重为1n+12Maxn+1r2ρ（r）=σmax C（n）22[γ（ ，2 22 ）+Maxw（ D（θi，p））=P（p|θi，σ）f（σ）dσ（2）2σσ2σ130722σr2n−1r2n−1k2且θ0= θ，即，最小样本的初始模型2.1.权重计算（1）（4对于r >kσmax，、 2Max）−r（） ]。2 2在（2）中定义的权重函数是内点残差的边际密度，如下所示：ρ（r）=ρ（kσmax）=σmaxC（n）2n−12γ（n+1k2， ），2 2∫w（ r）=g（r |σ）f（σ）d σ。哪里γ（a，x）=阿克斯ta−1exp（− t）d t01308Ki是下不完全伽马函数。权重w（r）可以像在MAGSAC中那样精确地或近似地计算。然而，通过将完整和不完整的伽马函数的值存储在查找表中，可以非常快速地完成精确计算。然后重量和质量算法1渐进式NAPSAC的概述。输入：P一曰： t1，…tn：=0命中数。第二章： k1，…kn：= m<$邻域大小。重复直至处死：计算变成每点仅仅几个操作。MAGSAC++算法使用（3）作为质量函数，σ-共识++用于估计模型参数。3. 渐进式NAPSAC采样我们提出了一种新的采样技术，逐渐从局部移动到全球，假设最初本地化的最小样本更有可能是全内点。如果假设不导致终止，则过程逐渐朝向RANSAC的随机化采样移动。3.1. N个相邻点样本共识N个相邻点采样一致性（NAPSAC）采样技术[20]建立在模型的点是空间结构化的假设基础上，因此，从局部邻域采样会局部增加内围值比率。简单地说，算法如下：1.从所有点中随机选择一个初始点pi2.找到位于以pi为中心的半径为r的超球面内的点的集合Si，r。3.如果Si，r中的点数小于最小样本量，则从步骤1重新开始4.点pi和从Si，r中均匀选择的点形成最小样本。在实践中，当地抽样有三个主要问题。首先，拟合局部全内点样本的模型通常太不精确（由于条件差）。其次，在某些情况下，从局部样本估计模型会导致退化。例如，对于基本矩阵拟合，对应必须源自一个以上的平面。这通常意味着通信是有益的远。因此，纯局部采样失败。第三，当具有全球结构时，例如，图像对中背景的刚性运动，局部采样比全局采样慢得多因此，我们提出了一个过渡的地方和全球采样逐渐混合从一个到另一个。3.2. 渐进式NAPSAC在本节中，提出了渐进式NAPSAC，选择第一个点：3：设pi为随机点。 由PROSAC选择。第四章： ti：=ti+1<$增加命中数。5：如果（ti≥T′kin），则<第六章：ki：=ki+1<$扩大邻域。大小为m的半随机样本Mi，ti：7：如果Si，ki−1/=P，则8：将pi;第ki个最近邻;以及来自Si，ki−1的m−2个随机点放入样本Mi，ti。9：其他十：从P中随机选择m−1个增加来自Mi，ti的点的命中数：11：对于pj∈Mi，ti\pi做对于样本中的所有点，12：如果pi∈Sj，kj则如果第i个接近，13：tj：=tj+1 增加命中数。模型参数估计图14：根据样本Mi，ti计算模型参数θ。模型验证15：计算模型质量。最小样本如下所述，点的局部子集的大小如果没有qual- ity函数可用，则与RANSAC类似地随机选择第一点，从逐渐增长的邻域均匀地选择其他点。在具有局部模型的情况下，样本更有可能仅包含内点，从而触发早期终止。当所寻找的模型的点不形成空间相干结构时，邻域的逐渐增加导致发现全局结构不会比使用全局采样器更晚，例如，PROSAC。增长函数和采样。定义邻域在选定点pi周围的增长速度的增长函数的设计必须在严格的NAPSAC假设（完全局部化的模型）和在全局尺度上处理每个模型的RANSAC方法之间找到平衡将类似NAPSAC的地方抽样和设{Mi，j}T（i）={p，p、...、 p}T（i）表示j=1ixi，j，1xi，j，m−1j=1RANSAC的全局采样。P-NAPSAC采样器如下进行：使用PROSAC策略选择最小样本中的第一个位置定义点其余的点根据它们的距离从局部邻域中选择。该过程从最靠近中心的m个点进行采样，该中心由包含点pi∈ P并由某个采样器（例如， 其中m是最小样本大小，P是P的幂集，并且xi，j，1，. ，xi，j，m−1∈N+是指P中的点的指数。 在每个Mi，j中，点是根据它们到pi的距离和索引来排序的。1309我j表示抽取样本的顺序。 我们的目标是找到一种策略，该策略绘制的样本组成的点接近第i个，然后，样本包含数据点远离pi逐步绘制。由于该问题与PROSAC的问题非常相似，因此可以使用相同的增长函数。 让我们定义集合Si，k为以pi为中心的最小球，k近邻 设Tk（i）为样本从{Mi，j}T（i），其中包含p，其他点是j=1i从S，K。 For the expected number of Tk(i), holds:.kΣmY−2k −jE（T（i））|T（i））=T（i）。m−1=T（i） ，kn−1m−1j=0 n−1−j(a) P-NAPSAC制造了18302它-(b) P-NAPSAC制造了65842它-其中n是数据点的数量在这种情况下，比率E（Tk+1（i））|T（i））/E（Tk（i））|T（i））不依赖于i在0的时代。49秒PROSAC84831在1。76秒场景“那里”。在0的时代。84秒PROSAC99913在1。28秒场景“文”。和E（Tk+1（i））|T（i））可以递归地定义为：K+1E（Tk+1（i））|T（i））=k+2−mE（Tk（i））|T（i））。图2.EVD数据集中用于同质性估计的示例图像对内点对应由连接对应点的线段标记。我们用整数函数T ′=T′+中文（简体）k+1′kk+1（i）|T（i））− E（Tk（i））|T（i）），其中对于来自Si，ki−1的随机点，T 1 = 1（即，球面上的点阿尔岛因此，T′是i-独立的。增长函数g（t）=最小值{k ：T′k≥t}，即，对于整数t，g（t）=k，其中在P1周围，不包括最远的一个）。基于随机克T=t。设ti为包括p的样本数。为sample，更新相应的t值最后估计隐含模型，并度量其质量。Ki设Si，g（ti），ti约为平均取样数如果使用RANSAC的随机采样器，则从Si，g（ti）在所提出的P-NAPSAC采样器中，如果g（ ti）=k，则p i的邻域Si，k增长，即，包含第i个点的所提取样本的数量近似等于从该相邻点提取的样本的平均数量。随机抽样的结果包含pi的第ti个样本Mi，ti为Mi，ti={p，p<$（g（ti））}<$M′ ，其中M′<$Si，g（t）−1是一个集合放宽终止标准。 我们观察到，在实践中，RANSAC的终止标准是保守的，不适合早期发现局部结构。RANSAC的所需迭代次数r为r=log（1−µ）/log（1 −ηm），（4）其中，m是最小样本的大小，μ是结果所需的置信度，η是内点比。 这场呐喊--I'i，tii，ti ii的 | 我 ， 我 |=m−2 个 数 据 点 ， e 不 包 括 pi 和 p （ g（ti）），从Si，g（t）−1中随机抽取。 点p（g（ti））是g（ti）- 点pi的第三近邻。点击数的增长 给定点pi，相应的ti在两种情况下增加。首先，当选择pi作为超球面的中心时，ti←ti+1第二，当选择pl时ti增加，pl的邻域包含pl，并且pl的邻域也包含pl。对于- mally，令pl被选为球面的中心（li<$l∈[1，n]）。令样本Ml，j={pl，pxl，j，1，...，p×l，j，m-1}以先前描述的方式被随机选择作为样本 If i ∈ {xl,j,1, ..., xl ， j ， m−1}（或等价地，pi ∈ Ml，j）且pl ∈ Si，g（ti）则ti增加1。采样器（见Alg。1）可以想象为PROSAC为每个第i个点独立定义采样，其中第i个点的采样序列取决于其相邻点。初始化后，第一个主要步骤是选择pi作为球心并更新相应的ti。然后，抽取一个半随机样本，其中包括选定的pi、其第ki个最近邻和m −21310ESTA不假设所寻求的模型的点是空间相干的，即，选择全内点样本的概率高于ηm。局部结构通常具有低内围比。因此，在低内围值比率的情况下，Eq. 4导致太多的迭代，即使模型是局部化的，并且由于局部采样而被提前发现。提前终止的一个简单方法是放宽终止标准。找到具有η+γ内点比的模型的迭代次数r′为r′=log （ 1−μ ） /log （ 1− （ η+γ ） m ） ，（5）其中γ∈[0，1−η]是松弛参数。快速邻域计算。 确定空间所有点的关系是一个耗时的操作，通过应用近似算法，例如，快速近似最近邻方法[17]。在RANSAC类方法的采样中，主要目标是尽早找到最佳样本，因此，花费大量时间初始化采样器是负担不因此，我们认为，1311i=1我们提出了一个多层网格的邻域估计，我们描述的点对应。它可以根据不同的输入数据进行直接修改假设给定两个大小为wl×hl（l∈{1，2}）和点对应集合{（pi，1，pi，2）}n，其中pi，l=[ui，l，vi，l]T。2D点对应可以被认为是四维空间中的点因此，在四维网格Gδcon中，单元的大小是由输入图像的尺寸引起的应变是W1×H1×W2×H2，从Flickr上收集了各种大小的地标图片。在基准测试中，从每个数据集中随机选择1000个图像对。检测SIFT [12]对应性，通过标准SNN比率测试[12]进行过滤，最后用于估计对极几何。比较的方法是RANSAC [5]，LMedS [22]，MSAC[28]， GC-RANSAC [1]， MAGSAC [2]，MAGSAC++。所有方法均采用P-NAPSAC采样，模型验证和简并性测试作为一种δ δ δ δ其中δ是确定分割沿着一个轴。函数f（Gδ，[ui，1，vi，1ui，2，vi，2]T）返回与第i个单元在相同的4D单元因此，在本发明中，|（Gδ，. ）|是特定点的邻域的基数。 有多个层意味着我们被给予一个δs序列，使得：δ1> δ2>. >δd≥1。 对于每个δ，对应的构造了Gδk网格对于在其第i次选择期间的第i个对应，选择在存储有pi的单元中具有足够点的最精细层Gδmax参数δmax计算为δmax：=max{δk：k∈[1，d]|Si，g（ti）−1|≤|（Gδk，. ）|{\fn方正粗倩简体\fs12\b1\bord1\shad1\3cH2F2F2F}在P-NAPSAC中，d= 5，δ1= 16，δ2= 8，δ3=4，δ4= 2δ5=1。当使用哈希映射和适当的哈希函数时，网格创建的隐含计算复杂度为O（n）。对于搜索，它是O（1）。请注意，δ5= 1导致网格只有一个单元格，因此不需要计算。4. 实验结果在本节中，我们评估了这两种算法的精度和速度。首先，我们在六个公开可用的真实世界数据集上测试MAGSAC++的基本矩阵和单应性拟合。其次，我们表明，渐进式NAPSAC采样导致更快的鲁棒估计比国家的最先进的采样器。请注意，这些贡献是正交的，因此，可以一起使用，以实现高性能有效地-4.1. 评估MAGSAC++在[3]的基准上评估基本矩阵 [3]基准包括：（1）由室内场景视频组成的TUM数据集[25]。每个视频分辨率为640×480。(2)KITTI数据集[6]由安装在移动 车 辆 上 的 相 机 的 连 续 帧 组 成 。 图 像 分 辨 率 为1226×370。在KITTI和TUM中，图像对都是短基线的。(3)坦克和寺庙（T T）数据集[10]为基于图像的重建提供了真实世界物体的图像，因此，主要包含宽基线对。图像大小从1080×1920到1080×2048。(4)的社区照片集（CPC）数据集[30][21]第21话 置信度设置为0。九十九。 为每个方法和问题，我们选择阈值最大化-的准确性。对于单应性拟合，其如下：MSAC和GC-RANSAC（5. 0像素）; RANSAC（3. 0pix-els）; MAGSAC和MAGSAC++（σmax的设置考虑到50 块 0 像 素 阈 值 ） 。 对 于 基 本 矩 阵 拟 合 ， 如 下 ：RANSAC 、 MSAC 和 GC-RANSAC （ 0. 75 像 素 ） ;MAGSAC和MAGSAC++（σmax，其中5. 0像素阈值暗示 ） 。 使 用 的 误 差 度 量 是 对 称 几 何 距 离 [31]（SGD），它通过迭代生成图像边界上的点，然后测量它们的极线距离来比较两个基本矩阵。所有方法都是C++。在图3中，示出了SGD误差（水平）的累积分布函数 （ CDF ） 。MAGSAC++ 是 CPC ， Tanks andTemples和TUM数据集上最准确的鲁棒估计器，因为它的曲线总是高于其他方法。在KITTI中，图像对是安装在汽车上的相机的后续帧，因此具有短基线。因此，这些图像对很容易，所有方法都能达到相似的精度。在表1中，报告了中值误差（以像素为单位）、故障率（以百分比为单位）和处理时间（以毫秒为单位我们报告的中位数值，以避免受到影响的失败-这也显示。如果估计模型的误差大于图像对角线的1%，则认为测试失败最佳值以红色显示，第二佳值以蓝色显示 。 对 于 基 础 矩 阵 拟 合 （ 前 四 个 数 据 集 ） ，MAGSAC++ 在 中位 误差 和失 败率 方面 都 是三 个在KITTI上，所有方法都具有相似的精度-最低精度和最高精度之间的差异为0。3像素。在那里，MAGSAC++是最快的。在测试数据集上，MAGSAC++通常与其他鲁棒估计器一样快，同时导致更高的准确性和失败率。MAGSAC++总是比MAGSAC快，例如，两个数量级。在图的左侧图中。5、avg. 将所有数据集上的log 10误差绘制为内点-外点阈值的函数。MAGSAC和MAGSAC++对阈值的敏感性低于其他鲁棒估计器。注意，LMeDS的准确度对于所有阈值是相同的，因为它不需要设置内点-外点阈值。1312基本矩阵（Fig. 3）单应性（图4）方法/数据集KITTI [6]TUM [25]T& T [10]CPC [30]Homogr [11]EVD [11]表1. The median errors (ǫmed; in pixels), failure rates (λ; in percentage) and average processing times (t, in milliseconds) are reported foreach method (rows from 4th to 9th) on all tested problems (1st row) and datasets (2nd). 基本矩阵的误差从地面真值矩阵计算为对称几何距离[31]（SGD）。对于单应性，它是来自地面实况内点的RMSE重新投影误差如果误差大于图像对角线的1%，则认为测试失败对于每种方法，将阈值设置为最大化准确度，置信度为0。九十九。 每列中的最佳值用红色显示，最好的蓝色。请注意，除MAGSAC和MAGSAC++外，所有方法都在所有内点上完成最终LS拟合10.80.60.40.20MAGSAC++MSACGC-RANSACRANSACLMEDS0 5 1015TUM数据集;SGD误差（像素）10.80.60.40.200 5 1015T T数据集;SGD误差（像素）1.31.21.110.90.80.7基础矩阵估计10.90.80.70.60.50.4单应性估算10.810.80.7523 5 10内-外阈值135 10 25内-外阈值0.60.40.200 5 1015CPC数据集;SGD误差（像素）0.60.40.200 5 1015KITTI数据集;SGD误差（像素）图5. 基础数据集上的平均log10对话矩阵（左; SGD误差）和单应性（右; RMSE重新投影误差）拟合绘制为内点-离群点阈值（以像素为单位）的函数。在右边的小图中，阈值上升到100像素。图3.估计的基本矩阵的SGD误差（水平轴）的累积分布函数（CDF），数据集CPC，T T，KITTI和TUM。准确是由接近顶部的曲线来解释的。对于单应性估计，我们下载了homogr（16对）和EVD（ 15 对 ） 数 据 集 [11] 。 它 们 由 大 小 从 329×278 到1712×1712不等的图像对组成，并提供了点对应。Homogr数据集主要包含短基线立体图像，而10.80.60.40.20MAGSAC++ MSACGC-RANSACRANSACLMEDS0 5 1015EVD数据集;RMSE误差（像素）10.80.60.40.200 5 10 15Homogr数据集;RMSE误差（像素）成对的EVD经历极端的视图变化，即，宽基线或极端变焦。在这两个数据集中，主平面的内点对应是手动选择的。所有算法均应用归一化四点算法[8]进行单应性估计，并在每个图像对上重复100次为了测量估计的单应性的质量，我们使用RMSE重新投影图4.数据集EVD和homogr上估计的homographs的RMSE重新投影误差（水平轴）的累积分布函数（CDF）。准确的解释是接近顶部的曲线。根据所提供的真实内点计算的误差。误 差 的 CDF 如 图 所 示 。 4. 第 一 章 在 EVD 上 ，MAGSAC++的精度最高-它是最准确的方法。在同形项上，除了原始MAGSAC和LMedS外，所有方法都具有相似的表1中的最后两个数据集报告了中位错误、故障率和运行时间。在EVD上，MAGSAC++失败的频率最低，MAGSAC MAGSAC++ MSAC GCRANSAC RANSAC LMEDS525501000.40.210.80.61.2概率概率概率概率概率概率avg. log10误差（像素）拉梅德λ不拉梅德λ不拉梅德λ不拉梅德λ不拉梅德λ不拉梅德λ不MAGSAC++3.62.483.516.4 133.90.41426.47.8 1561.10.062.6 10.4 173MAGSAC [2]3.52.81173.717.7 184.20.72677.07.8 2611.30.8 322.6 12.0 426GC-RANSAC [1]3.72.3114.125.1 114.52.21267.5 12.1 1441.10.0 252.6 18.366RANSAC [5]3.82.795.422.1 116.32.613316.9 29.5 1511.10.0 264.0 26.168LMedS [22]3.62.7114.323.9 124.91.116610.7 17.8 1871.512.5 3189.9 60.082MSAC [28]3.82.6105.536.2 117.02.213316.5 33.8 1531.10.0 243.2 23.764avg. log10误差（像素）1313最好的中位精度和2. 比MAGSAC快5倍。所有更快的方法都无法返回所寻求的模型。MAGSAC++、GC-RANSAC、RANSAC和MSAC对同调函数有相似的结果。MAGSAC++是最快的，几乎快了一个数量级在图的右侧图中。5、avg. log10误差被绘制为内点-外点阈值（以px为单位）的函数。MAGSAC和MAGSAC++对阈值的敏感性明显低于其他鲁棒估计器。在3.532.521.510.50与P-NAPSAC相比的采样器P-NAPSAC均匀iters。时间错误失败（一）1.210.80.60.40.200 0.2 0.4 0.6 0.81松弛参数（b）第（1）款小的数字，在大的数字里面，阈值上升到100像素。对于MAGSAC和MAGSAC++，根据阈值计算参数σmax。总之，实验表明，MAGSAC++在测试问题和数据集上比所有比较的最先进的鲁棒估计器更准确，并且比原始MAGSAC更快。4.2. 评估渐进式NAPSAC在本节中，使用与前几节相同的数据集，对所提出的P-NAPSAC采样器进行单应性和基本矩阵拟合评估每个被测采样器都与MAGSAC++相结合。比较的采样器是普通RANSAC [5]，NAPSAC [20]，PROSAC [4]和建议的P-NAPSAC的均匀采样器。由于提出的P-NAPSAC和NAPSAC都假设内点是局部的，因此他们使用了γ = 0的宽松终止标准。1.一、因此，当找到导致至少0的模型的概率时，它们终止。1内围值比率的增加低于阈值。PROSAC使用其原始终止标准和质量函数对对应进行排序。示例图像对如图所示。二、内层对应由连接对应点的线段标记。标题中报告了PROSAC或P-NAPSAC采样器的迭代次数和处理时间在这两种情况下，P-NAPSAC 导 致 比 PROSAC 显 著 更 少 的 迭 代 。 与 P-NAPSAC相比并对所有数据集进行平均的采样器结果如图所示6a. P-NAPSAC的迭代次数这是接近。1.一、比第二好的快6倍，即，PROSAC，while being similarly accurate with the same failurerate.通过将P-NAPSAC应用于使用不同γ值的所有数据集来测试放松的终止标准我曾为每一个人，错误、失败率、运行时间和迭代次数）的变化。图图6b绘制了所报告的属性的平均值（每个场景超过100次运行）作为γ的函数。显示了相对值因此，对于每个测试，值除以最大值。例如，如果P-NAPSAC在γ = 0时绘制100次迭代，则对于每隔一个γ，迭代次数除以100。错误率和失败率从大约100%缓慢增加。八比一。0的情况。这一趋势似乎接近线性。图 6. （ a ） 取 样 器 与 P-NAPSAC 的 比 较 （ 蓝 条 ; 除 以 P-NAPSAC的值;全部与MAGSAC++组合）在表1的数据集上。报告的特性为：迭代次数;处理时间;平均误差失败率。（b）亲属（即，除以最大值）误差、失败次数、处理时间和迭代次数作为松弛参数γ的函数（来自等式（1））绘制。5）放宽RANSAC终止标准。同时，迭代次数和处理时间显著减少 在γ = 0附近。1，从1大幅下降。0到0。3 .第三章。如果γ>0. 1这两个值都略有下降。因此，选择γ=0。1作为松弛因子不会导致明显更差的结果，但显著加快了手术。5. 结论在论文中，有两个贡献首先，我们formulate一个新的边缘化过程作为一个迭代重加权最小二乘方法，我们引入了一个新的模型质量（评分）功能，不需要内-外决策。其次，我们提出了一个新的采样器，渐进NAPSAC，RANSAC样的鲁棒估计。P-NAPSAC反映了附近点通常源自真实世界数据中的相同模型的事实，它比全局采样器更早发现局部结构。从局部采样到全局采样的渐进过渡不受纯粹局部化采样器的弱点的影响这两个正交改进与USAC的“铃铛和哨子”相结合抢先验证简并测试在六个公开可用的真实世界数据集上进行单应性和基本匹配拟合，MAGSAC++产生的结果优于最先进的鲁棒方法。它速度更快，在地理上更准确，故障频率更低。确认这项工作得到了捷克科学基金会资助GA 18 - 05360S、捷克技术大学学生资助SGS 17/185/OHK 3/3 T/13、教育部OP VVV项目CZ.02.1.01/0.0/0.0/16 019/0000765信息学研究中心和资助2018-1.2.1-NKP-00008的支持。#21040;的人。 失败次数时间错误相对值相对值1314引用[1] D. Barath和J.马塔斯图形切割RANSAC。在IEEE计算机视觉和模式识别会议论文集，第6733-6741页，2018年。https://github.com/danini/graph-cut-ransac. 一、六、七[2] D. Barath，J. Noskova，and J.马塔斯MAGSAC：边际化样本共识。在IEEE计算机视觉和模式识别会议论文集，2019年。https://github.com/danini/magsac. 一、二、六、七[3] J. - W. Bian，Y.- H. Wu，J. Zhao，Y. 柳湖，加-地 张曼-M.我和阿诚。里德 用于基本矩阵估计的特征匹配器的评 价 。 arXiv 预 印 本 arXiv ： 1908.09474 ， 2019 。https://jwbian.net/fm-bench. 6[4] O. Chum和J.马塔斯与PROSAC渐进样本一致性匹配计算机视觉与模式识别。IEEE，2005年。二、八[5] M. A. Fischler和R. C.波尔斯随机样本同意：一个范例模型拟合与应用程序的图像分析和自动制图。ACM通讯，1981年。一、六、七、八[6] A. Geiger，P. Lenz，和R.盖革，等.乌塔松我们准备好了吗？Kitti Vision基准套件。在2012年IEEE计算机视觉和模式识别会议上，第3354-3361页。IEEE，2012。六、七[7] D. Ghosh和N.卡博奇图像拼接技术综述。视觉传达和图像表示杂志，2016年。1[8] R. Hartley和A.齐瑟曼。计算机视觉中的多视图几何。剑桥大学出版社，2003年。7[9] H. Isack和Y.博伊科夫基于能量的几何多模型拟合。国际计算机视觉杂志，2012年。1[10] A. Knapitsch，J. Park，Q.- Y. Zhou和V.科尔顿。坦克和寺 庙 ： 对 大 规 模 场 景 再 现 进 行 基 准 测 试 。 ACMTransactions on Graphics （ ToG ） ， 36 （ 4 ） ： 78 ，2017。一、六、七[11] K. Lebeda 、 J.Matas 和 O. 好 朋 友 修 复 局 部 优 化 的RANSAC。英国机器视觉会议。Citeseer，2012年。http://cmp.felk.cvut.cz/wbs/的网站。1、7[12] D. G.洛基于局部尺度不变特征的目标识别。在计算机视觉。IEEE，1999年。6[13] R. A. 马龙纳河D. Martin，V. J. Yohai和M. 萨利比-巴雷拉 。 鲁 棒 统 计 ： 理 论与 方 法 （ 与 R ） 。 John WileySons，2019年。3[14] J