高效多模型拟合算法：Progressive-X方法

1Progressive-X：高效、随时、多模型拟合算法Daniel Barath12岁，Jiri Matas1岁1捷克布拉格捷克技术大学控制论系VRG 2匈牙利布达佩斯MTA SZTAKI机器感知研究实验室barath. sztaki.mta.hu摘要提出了一种用于几何多模型拟合的Progressive-X算法。该方法通过重复性假设建议、快速拒绝和重复性假设建议等方法对当前数据解释进行抽样和合并。（b）假定实例（c）复合模型建议重新分配，保持通过标记能量最小化将新的假设整合到保持的实例集合由于前-提案发动机提案优化验证通过逐步探索数据，与现有技术相比，该方法具有几个有益的特性。首先，从RANSAC采用的明确标准控制了时间间隔。(a)输入早期实例拒绝迭代删除实例(d)实例集和点指定该算法在找到具有合理数量的内点的新模型的概率低于阈值时停止。其次，Prog-X是一个任意时间的算法。因此，每当被中断时，例如，由于时间限制，返回的实例涵盖真实的，并且可能是最主要的实例。该方法是优于国家的最先进的合成实验和公开可用的真实世界的数据集单应性，双视图运动和运动分割的准确性方面。1. 介绍多类多模型拟合问题是将一组输入点解释为源自不一定属于同一类的多个模型实例的噪声观测的混合。该问题的示例是3D点云中的k个平面和l个球体的估计;2D边缘图中的多个线段和圆;来自点对应的多个单应性或基本矩阵;或视频中的多个动作。鲁棒性是通过考虑分配给一个或多个离群值类来实现的。多模型拟合的研究始于六十年代初。Hough变换[13，14]可能是寻找单个类的多个实例的第一个流行方法[10，21，24，33]。RANSAC [9]算法也被扩展到处理多个实例。顺序RANSAC [29，17]通过在点集中搜索来一个接一个地检测实例，从该点集中，图1：Prog-X多模型拟合管道获取一个点集作为输入（a）。然后重复三个步骤。首先，考虑活动实例集（c），即，假定假设（b）的提议。复合模型。在（b）中，蓝色点是假定实例的内点，绿色点是复合实例的内点。第二，快速拒绝多余的假设.第三，通过整合新的假设，重新分配点，维护模型参数和删除不必要的实例进行优化。在（c）和（d）中，颜色编码了对实例的分配。已删除受保护的实例。贪婪方法使RANSAC成为用于找到单个实例的强大工具，但这是多实例设置中的缺点。点不是分配给最好的，而是分配给第一个实例，通常是具有最大支持度的实例，对于第一个实例，它们不能被视为离群值。MultiRANSAC [35]形成关于n个实例的复合假设。除了需要先验地已知实例的数量n之外，处理时间很长，因为在每次迭代中绘制大小为n乘m的样本，其中m是估计模型实例所需的点数。然而，基于RANSAC的方法具有交错假设生成和验证步骤的期望性质此外，他们有一个合理的终止标准的基础上，在数据中的内点-离群值的比例，这提供了一个概率guarantee找到最好的例子。多模型拟合的最新方法[32，15，23，37803781(a) （左）最好，占4.8%;（右）最差，5.6%;（b）两视图运动：（左）最好，2.4%;（右）最差，27.4%(c)单应性;（左）最佳，5.9%;（右）最差，12.6%（d）运动;（左）最佳，0.0%;（右）最差，2.4%图2：Prog-X -选定问题的结果质量和稳定性：单应性估计（a，c）、多个对极几何（b）和刚性运动（d）。使用固定参数运行五次的最佳（左）和最差（右）结果，叠加在其中一张图像上。白色点被标记为离群值，颜色代码指定给实例。分类错误，即分配给错误聚类的点的分数以百分比表示。表3中的结果表明，竞争算法的稳定性要差得多。18，19，30，20，3，1]遵循两步过程，首先，使用类似于RANSAC的假设生成来生成多个实例。第二，选择最能解释输入数据点的假设的子集。这种选择以各种方式进行。例如，一组流行的方法[15，23，3，1]使用图标记技术[4]通过能量最小化来优化点到实例的分配。能量来源于点到实例残差、标签成本[7]、几何先验[23]以及点的空间相干性另一组方法使用基于数据点残差分布的偏好分析。[34、18、19、20]。此外，还有一些技术[30，31]将该问题作为超图分区来处理，其中实例是顶点，并且点是超边。这些算法的共同点是初始化步骤，即模型实例是盲目生成的，没有关于数据的信息。因此，必须由用户决定是否考虑最坏的情况，从而产生不必要的大量实例;或者使用一些经验法则，例如，以生成两倍的点数假设。在实践中，这是通常所做的。但是，它不能保证覆盖所有所需的实例。第一个认识到这个问题的方法是Multi-X [3]。它增加了一个新的步骤的优化过程，以减少实例的数量，通过在模型参数域中的相应的密度模式取代标签集即使这一步允许生成比以前更多的初始实例在没有高计算需求的情况下，它仍然不能提供保证，特别是在低内围值比率的情况下。所提出的Prog-X的主要贡献是其任何时间的性质，这源于交错采样和合并当前的数据解释。这是通过重复的实例建议来完成的，注意已经提出的;快速拒绝冗余假设;和整合的新假设到保持的情况下，通过能量最小化（见图1）。1为基本概念）。此外，Prog-X通过逐步探索数据，采用RANSAC的概率特性。我们使用基于集合重叠的一般实例到实例度量，其可以通过最小散列方法[6]有效地估计，并且考虑多个模型实例的存在来修改RANSAC的模型质量函数。该方法在合成实验和公开的真实世界的数据集上进行了测试它是优越的，以国家的最先进的在精度方面的同质性，双视图运动，运动聚类，并同时平面和圆柱体拟合。2. 术语和符号在本节中，我们将讨论本文中使用的最重要的概念。为了通用性，我们考虑多类多模型拟合，因此，旨在找到多个模型实例不一定是同一个模型类。我们采用[3]中的符号。多类多实例模型拟合。 首先，我们展示3782∀× P → H}一L∈H∈P∈||H{}--i=1nai=1∀∀HH∈ HΣi=1a我i=1pa，i}i=1×nai=1P →nina∈10020030040050010020030040050045040035030025020015010050定义3.4. 提案引擎Σ：h∪*是一个使用复合模型从数据中生成假定实例的函数。运算符*表示幂集。因此，函数重新获得复合模型和点集，并输出一个或多个建议。600100200300400500600600100200300400500600定义3.5. 多实例优化过程Θ：图3：复合模型的示例，由{h×{h}×P→{^hn^aL是一个函数--距离场的并集，由（左）两条线生成（右）一条直线和一个圆圈。最好用彩色观看。通过例子来说明问题。一个简单的问题是找到一对解释一个集合的线实例h1，h2∈Hl获取活动的、假定的实例和数据作为输入。它返回一组活动实例和一个标签L：h，该标签将每个点分配给单个活动实例。函数Θ得到活动实例{ha，i}，a，pro的集合np2D点PR。 线类Hl是线Hl ={（θ l，φ l，τ l），θ l=[αc]T}，其配备有距离函数φ l（θ l，p）=cos（α）x+sin（α）y+c（p=[xy]T）和函数τ l（p1，…p（m）=θ 1，用于从m/N个数据点估计θ 1。多线拟合是找到多个线实例{h1，h2，…}Hl，而多类情形是抽取一个子集H H，其中H = Hl∪Hc∪ H. 我... 集合X是所有类的空间，包括线和圆的空间。此外，该公式还包括离群值类o=（θ o，φ o，τ o），θ o=，表现为所有点的距离相等，φ o（θ o，p）=k，kR+和τ o（）=。多实例多类模型拟合是确定一组实例{hi}H，并标记-令L∈Pn→ H将每个点p∈ P赋给实例塞尔斯 hpi=1和输入点。 它返回优化的活动实例和标签。可以激活或拒绝假定的实例。此外，激活实例可以在此处停用和删除活动实例集始终包含离群值类的实例。3.1.提议引擎建议引擎在每次迭代中建议一个尚未看到的实例。对于引擎，我们选择RANSAC [9]的最新变体：Graph-Cut RANSAC [2]，因为它是最先进的并且其实现是公开可用的1。由于假设局部结构，与[3]类似，我们选择NAPSAC [22]作为GC-RANSAC内部的采样器。建议引擎的主要目标是建议未看到的实例，即可能不在从{hi}i最小化能量E。{h}中的活动项a我}i=1. 一个简单的选择3. 渐进多模型拟合在本节中，提出了一种用于多模型拟合的新管道。在深入描述每个步骤之前，先讨论一些定义。定义3.1. 推定模型实例hp是临时的，由建议引擎生成，未被激活以参与优化过程。定义3.2. 活动模型实例ha是其参数和支持度在优化过程中更新的实例。定义3.3. 复合模型实例。给定一组激活实例{h a，i}，其中na是的基数实现这一目标是优选具有原因的实例不与复合实例h∪共享的点的数目。因此，我们提出了一个新的质量函数Q^：H×H×P×R→R，对于RANS AC，表示-确保模型实例的分数源自∀w.r.t.该复合实例（来自于数据库）、数据和手动设置的阈值。为了便于理解，我们从最简单的质量函数之一开始，即RANSAC的内点计数。具体如下：QR（h，P，φ）=p∈P [φ（h，p）<φ]，其中[. ]是艾弗森括号，如果里面的条件成立，则等于1，否则等于0。是的基于QR，考虑到h_i，并且因此不对共享点进行计数的修改的质量函数如下：i=1集合，复合模型实例h∪被定义为每个由一个内生成的距离场的并集。Q^R（h，P，）= [φ（h，p）<∧φ（h∪p∈P，p）≥]。（一）单个活动实例ha，i（i[1，na]）. 点p到h∪的距离为φ（h∪，p）=minna φ（ha，i，p）。化合物实例的实例在图1中示出。3.第三章。颜色代码的距离（蓝色-近，红色-远）。左图显示了两条直线生成的距离场的并集右边的是一个圆和一条线。内部条件成立当且仅当点p到实例h的距离小于n，同时它到复合模型h的距离大于n比。因此，Q^R计数不在-复合实例的内点，但新实例的内点。1https://github.com/danini/graph-cut-ransacnpΣi=123783|P||P|∈|P|m√√k∈M√√|P|−||然而，事实证明，在实践中，MSAC [27]的截断质量函数在用户定义阈值的准确性和灵敏度方面优于RANSAC的内点计数。具体如下：点的数量上的凹痕因此，验证步骤在恒定时间内运行。3.3.多实例优化Q M（h，P，）=|P|−pΣ∈Pmin∫1，φ（h，p）2γ（）2，γ（π）=3π.2（二）这一步的目的是优化一组活动的模型实例，每当一个新的假定的一个来，并决定是否这个新的实例应被激活或应被拒绝。由于瞄准了最一般考虑到前面描述的目标，QM是mod-如下所示，以减少与复合模型共享的点的得分：在这种情况下，即具有多个类，只有少数算法[15，7，23，3]可以在不需要非平凡修改的情况下解决该问题。 这些算法是基于标记能量最小化的。 总体上∫∫Q^M（h，P，）=|P|−，，pΣ∈Pmin1，最大2φ（ h，p），1−γ（）2φ（h，p）2γ（）2（三）.标记算法的主要问题是它们的计算复杂性，特别是在大标签空间的情况下。 在我们的情况下，由于提出的实例一个接一个，标签因此，对于点p，如果p为零，则隐含得分为零（i）。与proposal和compound实例都很接近及（ii）如与建议相距甚远。总 结 本 节 ， 我 们 应 用 GC-RANSAC 作 为 具 有NAPSAC采样和质量函数的建议引擎来逐个建议实例。3.2.提案验证验证是在优化和优化之间的一个中间步骤，用于决定实例是否应该参与优化。为此，必须定义实例到实例的距离，以测量所提出的实例和复合实例的相似性。如果距离较近，则该提案可能是一个已经看到的提案空间总是很小，因此，花费的时间标签并不重要。多个X [3]可能是一个合理的选择。 但在我们的情况下，它被简化为PEARL算法[15，8]，因为它的主要贡献是在标签空间中移动，用相应的密度模式替换标签集。当只有几个标签时，不需要此移动。因此，我们选择PEARL作为优化过程。23.4. 终止标准在本节中，我们提出了一个标准来确定何时停止提出新实例。我们推广了基于公式M K1−µ≤（1−（|我|/|P|） ）、（4）一个，因此不需要优化。 在[3]中，立场由特定于问题的序列表示点和这种方法，导致了如何用点表示模型的问题。一般来说，答案不是微不足道的，并且表征显著地影响结果。有一个简单的解决方案，用于通过点集表示实例。在[26]中，模型由它们的偏好集描述，并且两个实例的相似性通过它们的Jaccard得分定义[16]。 首选项集的实例h是Ph∈{0，1}| P|，其中Ph，j是1，如果其中µ是结果所需的置信度，通常设置为0。95或0。k是迭代次数;m是最小样本的大小;和是第分别是内点和点。在RANSAC中，等式使用当前内点比率，公式化公式化公式4以确定k，即所需的迭代次数相反，我们用公式表示Eq。 4，以获得独立于复合模型的内点的最大数量的估计，如下所示：（|P| −|）|)1−1−µ≥|我|哪里|h∪|是内围值第j个 点是h 内点，否则为 零（j[1，]）。接受推定实例的建议标准是（1）A=（|Ph∩Ph∪|/|Ph∪Ph∪|）>S，其中J保持ber是复合模型的系数，h是数值复合实例未涵盖的点（1）A（1）A（2）A（3）A（4）A（5）A（|P| −|h∪|）1−k1 −µ如果Jaccard相似度高于手动设置的阈值，则Jaccard相似度为[0，1]，否则J为假。我们选择Jaccard相似性而不是Tanimoto距离[25，18]，因为用集合表示实例提供了一种加速过程的直接方法。在具有数千个点的情况下计算Jaccard相似性幸运的是，我们最感兴趣的是识别实例的重叠是否最小散列算法[6]是使相似性计算的处理时间快速且独立的直接选择。、3784是一个上限的内围数的一个尚未发现的-在第k次迭代中，具有置信度μ的为了找到一个实例，它必须适合（即，因此，至少m+1个点必须支持它，其中m是最小样本的大小因此，算法在每次迭代结束时更新I，如果I

下载后可阅读完整内容，剩余1页未读，立即下载