确定性一致最大化的双凸规划优化算法

双凸规划的确定性一致最大化蔡志鹏1、秦达俊1、胡乐2、苏大卫31阿德莱德大学计算机科学学院{zhipeng.cai，tat-jun.chin} @ adelaide.edu.au2昆士兰科技大学电气工程与计算机科学学院huu. qut.edu.au3Edith Cowan University计算与安全学院d. ecu.edu.au抽象。一致性最大化是计算机视觉中应用最广泛的鲁棒拟合范式之一，而一致性最大化算法的研究是一个活跃的研究课题。在本文中，我们提出了一个有效的确定性优化算法的共识最大化。 给定初始解，我们的方法进行确定性搜索，强制增加初始解的共识。我们展示了如何每次迭代的更新可以制定为双凸规划的一个实例，我们有效地解决了使用一种新的双凸优化算法。与我们的算法相比，以前的共识改进技术依赖于随机采样或目标函数的松弛，这降低了它们显著改进初始共识的能力事实上，在具有挑战性的情况下，先前的技术甚至可能返回更差的解决方案。综合实验表明，该算法能在不增加大量代价的情况下，持续地提高初始解的质量。4关键词：稳健拟合·一致最大化·双凸规划1介绍由于真实数据中存在噪声和异常值，鲁棒模型拟合对于许多计算机视觉应用 是必要的。 可以说， 最流行的鲁 棒技术是随 机样本共识（RANSAC）[11]，其目的是找到具有最大共识集的模型。RANSAC算法通过在a处重复地对该d的最小子集进行采样来近似地解决该优化问题，这是因为“高”是产生具有高一致性的模型假设的所有最小子集已经提出了RANSAC的许多变体[7]。大多数变体尝试使用各种启发式进行引导采样，以加快检索速度4Matlab演示程序可在辅助材料中找到2Z. Cai，T.- J. Chin，H. Le和D.Suter所有内点最小子集。然而，从根本上说，采用最小子集会减少数据的跨度，并产生有偏的模型估计[20，27]。因此，RANSAC发现的最佳假设通常具有比可实现的最大值低得多的共识，特别是在高维问题上。实际上，RANSAC解应该仅被视为粗略的初始估计[9]。为了通过RANSAC算法进行“优化”，可以在RANSAC估计的一致性集合（即，黄金标准算法[12，Chap. 4]）。虽然从最大似然的角度来看是合理的，但LS的功效取决于开始时具有足够大的共识集。更有用的方法是局部优化的RANSAC（LO-RANSAC）[9，18]，其试图通过从共识集的大于最小子集生成假设来5基本原理是，拟合在大量内点上的假设通常会导致更好的估计值，甚至支持率更高。然而，最终，LO-RANSAC也是随机化算法。虽然它进行了更集中的采样，但该算法不能保证改进初始估计。我们将在SEC中演示。5.2，通常在更具挑战性的数据集上，LO-RANSAC不能显著改善RANSAC结果。由于其组合性质，共识集最大化是NP难的[4]。虽然这并没有阻止全局最优算法的发展[21，30，19，10，6，5，25，3]，但问题的根本棘手性意味着全局算法本质上是穷举搜索和修剪过程的变体，其运行时间在一般情况下呈指数级增长。虽然全局算法在计算机视觉中有其位置，但目前它们大多局限于具有低维度和/或少量测量的问题。1.1确定性算法--一类新的方法最近，共识最大化的有效确定性算法正在获得关注[17，22]。与随机采样不同，这样的算法从初始解（使用最小二乘法或随机采样方法获得）开始，并且迭代地对解执行确定性更新以改进其质量。虽然它们不追求全局最优，但由于有向搜索，这些算法能够找到优秀的解决方案。为了执行确定性更新，先前的方法放松目标函数（Le et al.[17]使用1惩罚，以及Purkait et al.[22]使用平滑代理函数）。因此，这需要设置控制松弛程度的平滑参数，以及松弛的逐渐收紧以确保收敛到好的解。我们将在SEC中演示。5.4中，平滑参数和/或其退火速率的不正确设置实际上可能导致比起始点更差的解这通常从主RANSAC例程内调用双凸规划的确定性一致最大化3域D1.2我们的贡献我们提出了一种新的确定性优化算法的共识最大化。我们的方法的整体结构是一个二分法搜索，以增加当前解决方案的共识我们的方法的有效性的关键是制定的可行性测试在每一次迭代作为一个双凸规划，我们有效地解决了通过双凸优化算法。与[17，22]不同，我们的方法既不放松目标函数，也不需要调整平滑参数。在合成数据集和真实数据集上，我们证明了我们的方法比以前的共识改进技术具有更好的性能。2问题定义给定一组N个离群污染的测量值，共识最大化的目标是找到与最大数据子集一致的模型x∈D最大x∈DI（x），⑴其中D是模型参数的域（稍后更详细地描述），并且ΣNI（x）=i=1I（ri（x）≤）（2）计算x的内点（一致性）的数量。函数ri（x）给出残差第i次测量w.r.t.x，是内点阈值，I是指示符函数，如果输入语句为真，则返回1，否则返回0图图1示出了目标函数I（x）。如从内点计数操作可以理解的，I（x）是具有无信息梯度的阶跃函数2.1更新问题Le tx~b是一个独立的解决方案，我们将继续实施x ~toyldater解决方案。我们将此任务正式定义为找到x ∈D，使得I（x）彡δ，⑶F ig. 1：我将使用已更新的应用程序。 给定x~上的计算结果和使用δ的计算结果，其中δ>I（x~），则问题（3）旨在找到x（）上的另一个计算结果，其中I（x（）≥δ。 Late r inSec. 4.将问题（3）嵌入在一个在δ上搜索的重载算法中，以实现确定性共识最大化。4Z. Cai，T.- J. Chin，H. Le和D.Suteri=1我我其中δ>I（x~）是一个大的连续值。 SeeFig. 1如果使用不当。 F或现在，假设δ是给定的;稍后在第二节。4我们将把（3）嵌入到一个更广泛的算法中来搜索δ。此外，尽管（3）没有将保留的存储器定义为“关闭”x ~，但将x ~作为备份备份的一个备份是一个很好的选择。 InSec. 3，我们将提出这样一种算法，能够有效地解决（3）。2.2残差函数与可解模型在着手解决（3）之前，重要的是首先详细说明ri（x）的形式和可以由所提出的算法拟合的模型的类型根据以前的作品[14，15，5]，我们专注于形式r（x）=qi（x），（4）ipi（x）其中qi（x）是凸二次的，pi（x）是线性的。我们还坚持pi（x）是正的。我们称ri（X）为拟凸几何残差，因为它是拟凸[2，Sec.3.4.1]在域D={x ∈ R d|pi（x）> 0，i = 1，. . . ，N}，（5）注意，上述形式中的D指定Rd中的凸域。计算机视觉中的许多模型拟合问题具有类型（4）的残差例如，在多视图三角测量中，我们的目标是估计3D点x∈R3来自多个（可能不正确的）2D观测{ui}N，（P（1：2）−uiP（3））x¯ri（x）=我我P（3）x<$（六）是在相机中执行的预连接，其中x¯=[xT1]T，ΣPi =Σ（1：2）我（三）我∈R3×4（七）是第i个相机矩阵，其中P（1：2）和P（3）分别是前两个我我行和第三行P。坚持x位于凸域D={ x∈R3|P（3）x′>0，则表示在所有相机的帧中存在最小的x列。其他具有拟凸几何残差的模型拟合问题包括单应性拟合，相机切除和已知的旋转问题;有关详细信息和其他示例，请参见然而，请注意，基本矩阵估计不是一个拟凸问题[14];在Sec.5，我们将展示如何所提出的技术可以适应鲁棒估计的基本矩阵。3解决更新问题作为（1）的决策版本，更新问题（3）是NP完全的[4]，因此只能近似求解。在这一节中，我们提出了一个算法，在工作中，我们将在实践中，即。例如，能够将信号传输到预处理器。PP双凸规划的确定性一致最大化5我我我我我我3.1作为连续优化的对于拟凹几何残差（4），不等式ri（x）≤变为qi（x）−pi（x）≤ 0。（八）由于qi（x）是凸的并且pi（x）是线性的，因此约束（8）指定D中的凸区域。限定r′（x）：=qi（x）−pi（x）（9）对每个r′（x）引入一个指示变量yi∈[0，1]和一个松弛变量si≥0，我们可以使用互补约束[13]将（3）写为求x∈D（10a）Σ受yi≥δ，（10b）我yi∈[0，1]，i，（10c）yisi= 0，i，（10d）si−r′（x）≥0，i，（10e）si≥ 0，i.（10f）直观地，yi反映第i个数据是否是相对于i的内点X. 在下文中，我们建立yi的完整性以及（10）和（3）之间的等价性。引理1. 问题（10）和（3）是等价的。证据注意对于任何xa1：若r′（x）>0，则第i个数据离x远，（10d）和（10e）将迫使si≥r′（x）> 0且yi= 0。a2：如果r′（x）≤ 0，则第i个数据与x内插，并且（10 f）和（10d）允许si和yi仅具有以下设置之一：a2.1：si> 0且yi= 0;或si= 0且yi不确定。如果x对于（3）是不可行的，即 I（x）<δ，条件a1确保（10b）被违反。例如，如果x表示为（10），则例如，iyi<δ，则I（x）<δ，因此x对于（3）也是不可行的如果x对于（3）是可行的，我们总是可以对所有内点设置yi= 1和si以满足（10b），确保x到（10）的可行性。相反，如果x是可行的对于（10），通过在列表中的tδ的保留，其值等于等式（3）。⊔⊓从计算的观点来看，（10）并不比（3）更容易求解然而，通过从双线性约束（10d）构造成本函数，我们6Z. Cai，T.- J. Chin，H. Le和D.Suter我我得到以下连续优化问题Σ尽量减少x∈D， s∈RN，y∈RN受yisi（11a）我Σyi≥δ，（11b）我yi∈[0，1]，i，（11c）si−r′（x）≥0，i，（11d）si≥0，i，（11e）其中s =[s1，. . . ，sN] T且y =[y1，. . . ，yN] T. 下面的引理建立了（11）和（3）之间的等价性。引理2. 如果（11）的全局最优值为零，则存在满足更新问题（3）的x。Prof. 对于（11c）和（11e），（11Σ）的bjv值小于d零. 设（x*， s*， y*）是（11）的全局极小元如果ys= 0，则x*i我我尽管所有这些概念都在（10）中，但它们可以如图（3）所示。 ⊔⊓3.2双凸优化算法尽管（11）中的所有约束都是凸的（包括x∈D），但目标函数不是凸的。尽管如此，公式（11）的主要价值是使得能够使用凸解算器来近似地解决更新问题。还要注意，（11）不需要任何平滑参数。为此，观察到（11）实际上是双凸规划的实例[1]。如果我们固定x和s，（11）简化为线性规划（LP）Σ尽量减少y∈RN受yisi（12a）我Σyi彡δ，（12b）我yi∈[0， 1]，ni，（12 c）这可以用封闭的形式来解决。6另一方面，如果我们固定y，则（11）简化为二阶锥规划（SOCP）尽量减少x∈D，s∈RNΣyisi（13a）我服从si−r′（x）≥0，i， （13 b）si≥ 0，i.（13c）6如果si是δ-最小松弛之一，则设置yi = 1，否则yi = 0。双凸规划的确定性一致最大化7我我算法1用于连续问题（11）的双凸优化（BCO）R等式：在不存在的情况下，将x与t相加，则t等于s。1：Initializex←x，setsing（14）.2：不收敛时3： y←solveLP（12）.4： （x，s）←solveSOCP（13）.5：结束while6：returnx，sandy.注意，如果对应的yi= 0，则si不具有影响;这些松弛变量可以从问题中移除以加速优化。7所提出的算法（称为双凸优化或BCO）是简单的：我们将x初始化为来自（3）的标准x，并且将标准k设为si=max{0，r′（x~）}，i。（十四）然后，我们交替求解LP和SOCP，直到收敛。 由于（11）的下限为零，并且LP和SOCP的每次调用都保证节省成本，因此BCO将允许复制到一个局部最小值（x（，y（）。在此情况下，如果局部最优解（x，s，y）turnsouttobetheglobaloptimum（i. e. ，iyisi=0），tenxisasolutionto（3），i. 例如， I（x）≥δ。Else，xmightstillrepresentanimprovedsoutionoverx~。与随机化数据库相比，我们的方法是通过设计更易于实现x~。 这是一个非常好的选择（11），因为“s”必须是“s”的外部特征，即。例如，当yi=1时，其可能仍然会导致局部精确度，即。例如， I（x（））>δ1=I（x~），即问题（3）是否可行。在下一节中，我们将基于算法1构建一个有效的确定性共识最大化技术。4主要算法-确定性共识最大化给定初始解x（0）到（1），例如，使用最小二乘法或随机抽样试探法获得，我们希望将x（0）更新为更好的解。我们提出的算法的主要结构很简单：我们对共识值进行二分以寻找更好的解;参见算法2。维持并逐渐收紧共有序列的下限和上限δ1和δh，其分别初始化为I（x（0））和NLetx~是当前最佳解（初始化为x（0））;然后，中点δ= 100。5（δl+δh）δ的连续双锥更新问题用于多个单元（11）的v e x是使用A1或hm1来求解的。如果（11）的解x（对于该等式而言是高的，则x 〜被保留为等式x（并且δ1被保留为等式I（x（））。 并且如果I（x（）<δ，δh被表示为edoδ。当δ h = δ l + 1时，Algorithm2ens。对于（13）的操作x，具有所确定的空间变量的值不会在可执行的假设中被分割，其中i=max{0，r’（x（）}。8Z. Cai，T.- J. Chin，H. Le和D.Suter算法2用于确定性共识最大化的二分（非全局）。要求：使用最小二乘法或随机抽样获得（1）的初始解x（0）。1：x~←x（0），δh←N，δl←I（x（0））。2：当δh> δl+ 1时3： δ ← 0。5（δ l+ δ h）4： （x，s，y）←BCO（x〜，δ）（seeAlgorithm1）. 5：ifI（x）>I（x〜）then6：x~←x，δl←I（x）。7：如果结束8： ifI（x）δthen图9：δh←δ。10：如果结束11：结束while12：returnx~，δ1。由于在Algorithm2（步骤4）中的“fetas i i i i t y t e t etet”是通过非约束子例程来解决的，所以对分技术不保证找到全局解，即，最终解决方案的质量可能会低估最大可实现质量。然而，与以前的方法[9，17，22]相比，我们的技术从根本上是有利的，下一节的实证结果将证明所提出的算法的有效性。5结果我们称所提出的算法IBCO（迭代双凸优化）。我们将IBCO与以下随机抽样方法进行了比较：– RANSAC（RS）[11]（基线）：置信度ρ设定为0。99，用于计算终止阈值。– PROSAC（PS）[8]和Guided MLESAC（GMS）[26]（带引导采样的RS变体）：仅测试基本矩阵和单应性估计，因为需要内点先验，如对应性的匹配分数。– LO-RANSAC（LRS）[9]：内部采样中的子集大小被设置为当前一致性大小的一半，并且内部迭代的最大数量被设置为10。– 修复LO-RANSAC（FLRS）[18]：内部采样中的子集大小设置为7×最小子集大小，内部迭代的最大次数设置为50。– USAC [23]：结合PS和LRS思想的现代技术8USAC仅在基本矩阵和单应性估计上进行评估，因为可用代码仅实现这些模型。除USAC是用C++实现的外，其他采样方法均基于MATLAB [16]。此外，对最终共识集执行最小二乘法以细化所有随机采样方法的结果。8http://www.cs.unc.edu/~rraguram/usac/USAC-1.0.zip。双凸规划的确定性一致最大化9i=1我凸子问题LPSOCP使用的解算器Gurobi 塞杜米方法使用求解程序EP、SSIBCO表1：确定性方法中使用的凸解算器除了随机抽样方法外，我们还将IBCO与以下确定性共识最大化算法进行了比较：– 精确罚分（EP）方法[17]：为了对我们的数据进行最佳性能，重新调整了方法9：对于基本矩阵估计，我们将惩罚参数α设置为1.5，对于所有其他问题，设置为0.5。对于线性回归和2D单应性估计，惩罚参数的退火速率κ被设置为5，对于三角测量和基本矩阵估计，退火速率κ被设置为1.5– 平滑替代（SS）方法[22]：使用我们自己的实现。将平滑参数γ设定为0。01如[22]中所建议的。对于确定性方法，表1列出了用于其各自子问题的凸解算器。此外，提供了具有FLRS和随机初始化（X（0）是随机生成的）的这些方法的结果，以便分别示出具有良好（FLRS）和不良（随机）初始化的性能。我们还测试了最小二乘初始化，但在高离群值率下，其有效性并不比随机初始化好。所有实验在具有Intel Core 2.60GHz i7 CPU和16GBRAM的膝上型计算机上执行。5.1基于合成数据的8维线性回归的大小N= 1000的数据（即，x∈R8）。在线性回归中，残差采用以下形式ri（x）=aT x−bi，（15）I2这是（4）的特殊情况（设置pi（x）= 1），并且每个数据由下式表示：{ai∈ R8，bi∈ R}. 首先，独立测量{ai}N和参数向量X被随机采样。相关测量值计算为bi= a Tx，并加上均匀分布在[−0]之间的噪声。3，0。3]。然后随机选择相关测量的η %的子集，并添加σ = 1的高斯噪声。5、创造奇迹为了保证离群值速率，重新生成每个离群值，直到噪声不在[-0.3，0.3]内。（1）的内点阈值被设置为0。3.图2示出了针对η ∈ {0，5，… 70，75}，对于每个数据实例在10次运行上取平均。请注意，实际离群值率有时略低于预期，因为最大共识集包括一些具有低噪声值的离群值 对于η = 75，实际离群值率约为72%（见图11）。第2（a）段）。为了防止由该现象引起的不准确分析，未提供η >9代码来自https://cs.adelaide.edu.au/ ~ huu/。10Z. Cai，T.- J. Chin，H. Le和D.Suter1000900百分之十五800700百分之十6005004003000 10 20 30 40506070百分之五0%的百分比0 10 203040 50 60 70离群值率（%）(a) 平均优化共识。离群值率（%）(b) 一致性与RS的相对差异。1030.1750.171021010.1650.16100十比一0 10 20 30 40 50 6070离群值率（%）0.1550.1510 20 30 40 50 60 70离群值率（%）(c) 平均运行时间（秒，以log（d）为单位）规模）。通过最小二乘法在共识集上拟合的模型的liers。图2：具有变化的η（约100%）的稳健线性回归结果。异常率）。图2（b）显示了每种方法与RS的相对一致性差异。显然，两种IBCO变体总体上优于其他方法。与其他方法不同，在高离群值率下对RS的改善较低虽然IBCO仅在离群值率低于65%时略优于EP，但图图2（a）示出了对于大多数数据实例，两种IBCO变体都发现共识非常接近或完全等于可实现的最大值。IBCO的成本是相当实际的（所有数据实例都不到5秒，参见图1中的数据提示。第2段（c）分段）。此外，随机采样方法（RS、LRS、FLRS）的运行时间随着η呈指数增加。因此，在高η下，FLRS+EP、FLRS+SS和FLRS+IBCO的主要成本来自FLRS。为了证明具有更高一致性的重要性，我们进一步对每种方法的一致性集进行最小二乘拟合。给定最小二乘拟合模型xLS，将真实内点（分配有小于0.3噪声水平的数据）的平均残差定义为：Σe（xLS）=i*∈I*ri*（xLS）|、（十六）|, (16)RsLRSFLRSSSFLRS+SSEPFLRS+EPIBCOFLRS+IBCOEPFLRS+EPIBCOFLRS+IBCOLRSFLRSSSFLRS+SSRsLRSFLRSSSFLRS+SSEPFLRS+EPIBCOFLRS +IBCOX：75Y：平均一致性log scaled runtime（s）相对一致性差异到RSAvg. GT上的残留物。内点RsLRSFLRSSSFLRS +SSEPFLRS+EPIBCOFLRS+ IBCO双凸规划的确定性一致最大化11其中，我*是所有地面真实内围值的集合。图2（d）显示了所有数据实例上所有方法的e（xLS一般而言，较高的一致性导致较低的平均残差，表明更准确的模型。5.2单应性估算来自NYC Library数据集[29]的五个图像对用于2D同源性估计。在每个图像对上，SIFT对应由VLFeat工具箱[28]产生并用作输入。图3描绘了输入的示例，以及来自FLRS和FLRS+IBCO的共有集。一个图像中的传输错误[12，Sec. 4.2.2]用作距离测量。将内围阈值设置为4个像素。4点算法[12，Sec. 4.7.1]在所有随机抽样方法中用于最小样本的模型拟合图图4显示了50次运行的平均定量结果虽然比SS和随机方法稍微昂贵，但对于所有数据，两种IBCO变体都发现了比其他方法更大的共识集。同时，与线性回归情况不同，EP不再具有与IBCO相似的结果质量。还要注意，对于具有挑战性的问题，例如，Ceiling1和Sign，两个IBCO变体是返回比RS高得多的一致性的唯一方法。5.3三角测量选择来自NotreDame数据集[24]的五个特征轨迹进行三角测量，即，估计3D坐标。来自每个特征轨迹的输入包含一组相机矩阵和对应的2D特征坐标。再投影误差被用作距离测量[15]，并且内点阈值被设置为1个像素。对于所有RANSAC变体，最小样本的大小为2（视图）。结果如图1B所示。5.对于三角剖分，初始解的质量在很大程度上影响EP、SS和IBCO的性能。在FLRS的初始化下，IBCO设法找到了比所有其他方法都大得多的5.4细化的有效性虽然所有确定性方法都提供了可靠的初始FLRS解决方案，IBCO是唯一一个有效地完善所有FLRS结果。EP和SS有时甚至收敛到比初始解更差的解为了说明这些效果，图。图6示出了在用于单应性估计的Ceiling1和用于三角测量的点16上的三种确定方法（由FLRS初始化）的迭代期间的解质量与EP和SS逐渐使初始解变差相反，IBCO稳步改进初始解。可以通过选择更合适的平滑参数和/或它们的退火速率来校正EP和SS的行为。然而，对数据依赖性调优的需求使得EP和SS不如IBCO有吸引力12Z. Cai，T.- J. Chin，H. Le和D.Suter运行时间(a)输入对应（b）FLRS共识集合（c）FLRS + IBCO consen-（N=455）。（协商一致意见：323）。SUS集（共识：353）。(d)输入对应（e）FLRS共识set（f）FLRS + IBCO consen-（N=346）。（协商一致意见：321）。SUS集（共识：331）。图3：针对建筑物1（顶部）和天花板1（底部）的稳健单应性估计的数据和结果。对共有集进行下采样以进行目视清除。1009080706050121086420天花板1天花板2Building12栋签署(b)优化浓度40超过50次运行。3020100上限1（N =346）上限2（N =414）1号楼（N= 455）2号楼（N= 415）86标志4（N = 236）2(a)平均优化一致性（作为输入大小N的%）。N设置在支架中。0天花板1天花板21号楼2号楼签署ets.（c）以秒为单位的运行时间。图4：稳健的单应性估计结果。5.5基础矩阵估计来自CMP10的双视图几何语料库的图像对用于基础矩阵估计。如在单应性估计中，SIFT对应性被用作输入数据。由于桑普森错误[12，Sec.11.4.3]和重投影误差[12，第11.4.3节]。11.4.1]对于基本矩阵估计不是线性或拟凸的，确定性算法（EP、SS、IBCO）不能10http://cmp.felk.cvut.cz/data/geometry2view/RS PSGMSLRSFLRSUSACEPFLRS+EPSSFLRS+SSIBCOFLRS+IBCORSPSGMSLRSFLRSUSACEPFLRS+EPSSFLRS+SSIBCOFLRS+IBCO一致性（输入大小的%）RS PSGMSLRSFLRSUSACEPFLRS+EPSSFLRS+SSIBCOFLRS+IBCO偏差双凸规划的确定性一致最大化13RSLRSFLRSLPECFLRS+EPSSFLRS+SSIBCOFLRS+IBCOFLRSEPSSIBCO共识3602.52501.51400.501636点点6530点16点72点58(b)优化浓度20个感官超过50次运行。十点六01636点（N =117）点65（N =105）点16（N =116）点72（N =104）点58（N =114）0.40.2(a)平均优化一致性（作为输入大小N的%）。N设置在支架中。01636点点65点16点72点58ets.（c）以秒为单位的运行时间。图5：稳健的三角测量结果。33050483254632044421 2 3 4 5 6 78迭代次数(a) 单应性估计中的上限12 4 6 8 10 12迭代次数(b) 三角测量中的16点图6：每次迭代中的一致性大小，给定FLRS结果作为初始化。观察到EP和SS收敛到更差的解决方案。直接应用。因此，我们线性化极线约束并使用代数误差[12，Sec. [11.3]剩余部分。将内值阈值设置为0。006所有数据此外，有效的基本矩阵满足秩-2约束[12，Sec. 11.1.1]，它是非凸的。对于EP、SS、IBCO，我们在每次参数向量更新之后（对于IBCO，在每次BCO运行之后）使用SVD施加秩2图7描绘了样本图像对和所生成的SIFT对应关系，如以及来自FLRS和FLRS+IBCO的共有集。七点法[12，Sec. 11.1.2]在USAC中使用，标准化8点算法[12，Sec.11.2]在所有其他RANSAC变体中使用。如图8（a），与EP和SS不同，EP和SS未能针对所有测试数据细化初始FLRS结果，IBCO仍然有效，即使问题包含非凸约束。RSLRSFLRSLPECFLRS+EPSSFLRS+SSIBCOFLRS+IBCORSLRSFLRSLPECFLRS+EPSSFLRS+SSIBCOFLRS+IBCO一致性（输入大小的%）FLRSEPSSIBCO偏差共识运行时间14Z. Cai，T.- J. Chin，H. Le和D.SuterRS PSGMSLRSFLRSUSACEPFLRS+EPSSFLRS+SSIBCOFLRS+IBCO(a) 输入对应（b）FLRS共识集合（c）FLRS + IBCO consen-（N=186）。（共识：85）。SUS集（共识：97）。(d) 输入对应（e）FLRS共识set（f）FLRS + IBCO consen-（N=101）。（协商一致意见：32）。SUS集（共识：36）。图7：用于缩放的基本矩阵估计的数据和结果（顶部）和喊（底部）。60121085064402030RS PSGMSLRSFLRSUSACEPFLRS+EPSSFLRS+SSIBCOFLRS+IBCO喊Kampa布克什植物缩放(b)优化浓度的标准偏差20个感官超过50次运行。2101.5喊（N =101）kampa（N =239）booksh（N =174）植物（N =174）变焦（N =186）10.5(a) 平均优化一致性（作为输入大小N的%）。N是在0喊Kampa布克什植物变焦括号（c）以秒为单位的运行时间。图8：稳健的基本矩阵估计结果。6结论我们提出了一种新的确定性算法的共识最大化与非线性残差。我们的方法的基础在于重新制定的决策版本的共识最大化到一个双凸规划的实例，这使得使用二分法进行有效的引导搜索。与其他确定性方法相比，我们的方法不放松的共识最大化问题的目标，是免费的平滑参数的调整，这使得它更有效地细化初始解。实验表明，我们的方法是能够大大提高从广泛使用的随机抽样启发式的初始结果致谢本工作得到ARC资助DP160103490的支持一致性（输入大小的%）RSPSGMSLRSFLRSUSACEPFLRS+EPSSFLRS+SSIBCOFLRS+IBCO偏差运行时间双凸规划的确定性一致最大化15引用1. 双凸优化。https://en.wikipedia.org/wiki/Biconvex_ 优化2. 博伊德，S.，Vandenberghe，L.：凸优化剑桥大学出版社（2004）3. Campbell，D. Petersson，L.克奈普湖Li，H.：全局最优的内点集最大化，同时相机姿势和功能对应。arXiv预印本arXiv：1709.09384（2017）4. 阿成TJ蔡志，Neumann，F.：计算机视觉中的鲁棒拟合：容易还是难？arXiv预印本arXiv：1802.06464（2018）5. 阿成TJ Heng Kee，Y.，Eriksson，A.，Neumann，F.：混合整数线性规划的保证离群点去除。In：Proceedings of the IEEE Conference on C〇mputerVis isinandPater nRec 〇 gnit i tin. pp. 58586. 阿成TJPurkait，P.，Eriksson，A.，Suter，D.：高效的全局最优一致性最 大 化 与 树 搜 索 。 In ： Proceedings of the IEEE Conference onC 〇 mputerVisi s i n andPater n Rec 〇 g nit i ti n.pp. 24137. Choi，S.，金，T.，Yu，W.：RANSAC家族的性能评估。英国机器视觉会议（BMVC）（2009）8. Chum，O.，Matas，J.：与prosac-progressive样本共识匹配。2005年IEEE计算机协会计算机视觉和模式识别会议（CVPR' 05）。 vol. 第1页。 220-226 IEEE（200 5）9. Chum，O.，Matas，J.，Kittler，J.：局部优化的ransac。In：DAGM. 03The Dog（2003）10. E nqvist，O.， Ask，E.， Kahl，F.， ˚Astr¨om，K. ：Tractablealgorithmsforrbustmodel这是一个很好的例子。InternalJour nalofComut erVison112（1），11511. Fischler，文学硕士，Bolles，R.C.：随机样本一致性：一个范例模型拟合与应用程序的图像分析和自动制图。 Communi-cationsoftheACM24（6），38112. 哈特利河齐瑟曼，A.：计算机视觉中的多视图几何。剑桥大学出版社（2003）13. 胡，J，米切尔，J.E.，Pang，J.S.，Yu，B.：关于具有线性复杂约束的线性规划。J〇urnal〇fGlobalOptimi zation53（1），2914. Kahl，F.，哈特利，R.： l∞范数下的多视图几何。 IEEE Transac-tionsonPat t er nAnalysisandMachineIn t elligence30 （ 9 ） ， 16 03- 1617（2008）15. Ke， Q.Kanade，T.：鲁棒几何重建的拟凸优化IEEE Transactions onPattern Analysis and Machine Intelligence 29（10）（2007）16. Kovesi，P.D.：用于计算机视觉和图像处理的MATLAB和Octave函数，可从17. Le，H.，阿成TJ Suter，D.：局部收敛最大一致性的精确罚方法。在：计算机视觉和模式识别（CVPR），2017年IEEE会议上。IEEE（2017）18. Lebeda，K. 再见，J。，Chum，O. ：将本地化的对象对象定义为一个完整的X-边缘值。 In：BritishMachineVis is ionConferee. pp. 1-11 02TheDog（2012）19. Li，H.：鲁棒几何估计的保证全局最优性的一致集最大化。在：计算机视觉，2009 IEEE第12届国际会议。pp. 1074 -1080 IEEE（200 9）20. Meer，P.：计算机视觉的强大技术。计算机新兴课题。10716Z. Cai，T.- J. Chin，H. Le和D.Suter21. Olsson，C.，Enqvist，O.，卡尔，F.：一个多项式时间边界的匹配和配准与 离 群 。 在 ： 计 算 机 视 觉 和 模 式 识 别 ， 2008 。 CVPR2008.IEEEConfencen。pp. 一比八02The Dog（2008）22. Purkait，P.，Zach，C.，Eriksson，A.：最大一致性参数估计的加权方法In：InternationalWorkshoponEnergyMinimizationMeth-odsinComputerVisionandPatternRecognition.pp.312-327电 影 Springer（2017）23. Raguram河Chum，O.，Pollefeys，M.，Matas，J.，Frahm，J.M.：Usac：随 机 样 本 共 识 的 通 用 框 架 。 IEEE transactions on pattern analysisandmachineintellige nce35（8），202224. Snavely，N. Seitz，S.M.，Szeliski，R.：摄影旅游：探索3D照片集。 在：ACMtransacti onsongraphics （ TOG ） 。vol. 第 25 页 。835-846 ACM（2006）25. Speciale，P.，波德尔，民主党，奥斯瓦尔德，医生Kroeger，T.，Gool，L.V.，Pollefeys，M.：线性矩阵不等式约束下的一致最大化在：2017 IEEECo nfere nceo nCom uterVisio n andPater n Re cognitio n （ CVPR）中。pp. 5048IEEE（2017）26. Tordoff，B.J.，Murray，D.W.：Guided-mlesac：利用匹配先验的快速图像变 换 估 计 。 IEEE Transactions on pattern analysis and machineintelligence27（10），152327. Tran，Q.H.，阿成TJ Chojnacki，W. Suter，D.：稳健估计的大跨度最小子集采样。International Journal of Computer Vision 106（1），9328. Vedaldi，A.，Fulkerson，B.：VLFeat：一个开放和可移植的计算机视觉算法库。http://www.vlfeat.org/04 - 5.1分29. Wilson，K. Snavely，N.：使用1dsfm进行强大的全局翻译。在：欧洲计算机视觉会议（ECCV）（2014年）30. 郑宇，Sugimoto，S.，Okutomi，M.：确定性最大化可行子系统的单位范 数 约 束 鲁 棒 模 型 拟 合 。 在 ： Computer VisionandPatternReg i tition（CVPR），2011IEEEConferenceon中。pp. 1825- 1832年。IEEE（2011）