10233三维视觉中一致性和非最小问题的凸松弛Thomas Probst，Danda Pani Paudel，Ajad Chhatkuli，Luc VanGool计算机视觉实验室，苏黎世联邦理工学院，瑞士摘要在本文中，我们制定了一个通用的非最小求解器使用现有的工具多项式优化问题（POP）从计算代数几何。所提出的方法利用了著名的肖尔或拉塞尔的放松，其理论方面也进行了讨论。值得注意的是，我们进一步利用POP制定的非最小的求解器也通用的共识最大化问题的3D视觉。我们的框架是简单和直接的实现，这也是由三个不同的应用程序在3D视觉，即刚体变换估计，非刚性结构从运动（NRSfM），和相机自动校准的支持。在所有这三种情况下，非最小和共识最大化都进行了测试，这也与最先进的方法进行了我们的结果与比较的方法具有竞争力，也与我们的理论分析相一致。本文的主要贡献是，利用现有的数值计算代数理论，可以得到三维视觉这一说法让我们思考为什么3D视觉中的许多放松方法表现得如此出色？并且也允许我们以一种相当直接的方式提供一个通用的松弛求解器.我们进一步表明，这些多项式的凸松弛可以很容易地用于以确定性的方式最大化共识。我们支持我们的主张，使用几个实验，上述三个不同的问题，在3D视觉。1. 介绍3D视觉中的鲁棒模型估计通常涉及两个子问题：内点检测和模型计算。在许多情况下已经存在的忠实方法为3D视觉应用提供了无与伦比的成功，从3D场景重建到6DoF相机定位。一般来说，内点检测的任务是通过最大化测量之间的一致性来执行的与已知模型的某些参数一致的测量是被视为inliers。通常，使用所谓的最小求解器方法，从随机选择的最小数量的测量值中估计模型参数。然后，这些参数在随机采样和一致性（RANSAC）的框架内寻求最大一致性。最大化一致性的参数相对于所有内点测量值进一步细化-共识最大化的全局方法已经引起了极大的关注[27，5，16，10，37，46，33]，主要是因为RANSAC是不确定的，并且不保证最优性。虽然共识最大化问题已被证明是NP难的[14]，但具有凸模型表示的全局方法在速度和最优性方面都显示出有希望的结果[42，16]。因此，现有的方法提供了令人满意的解决方案，只有凸模型。在非凸模型的情况下，一些方法引入具有额外凸约束的线性化辅助模型参数[43，42]。确实存在用于探索精确参数的非凸模型的方法[46，37，33]。然而，所有为非凸问题设计的方法因此，这些方法不能推广到其他非凸模型。因此，一个通用的框架，确定性的共识最大化的非凸模型，超越简单的线性化，是非常可取的。与共识最大化不同，非最小解算器获得的关注相对较少。在实际应用中，人们往往忽视了对最优非极小解的需求。相反，从通过最大化一致性获得的模型参数开始，对所有内点导出的一些几何成本进行局部细化，作为替代方法。 然而，这带来了陷入全局成本函数的局部极小陷阱的风险，导致不充分的解决方案，这已经被证明是各种问题[8，32，22，9，39，18，23]。更具体地说，已经为3D旋转[18]、[8，32，39，23]中的3D刚体变换、[22]中的透视n点和[9]中的两视图相对姿态一方面，这些求解器非常10234XY=0具体到他们自己解决的问题，只有[32]提供了理论上的最优性保证，由于使用的分支定界（BnB）搜索范式。另一方面，[22，8，9]中的方法是快速的，并且还实现了全局最优性的后验证书，具有理论证明的开放问题。一项值得注意的工作[21]为多个计算机视觉问题提供了凸松弛，同时主要关注几何误差最小化的任务，其中所解决的问题通常与代数误差最小化相关。实际上，多项式代价函数的极小化问题是代数几何中一个长期存在的问题，多项式代价函数是非极小情形下的全局代价函数。最值得注意的是，可以使用平方和（SoS）方法来使用半定规划（SDP）最小化此类多项式。在这个过程中的理论最优性可以得到保证，当一个层次的SoS多项式作为约束[36]被强制执行时。在这种情况下，3D视觉中的许多方法利用SoS层次结构;其中包括非刚性3D重建[34，4]、摄像机自动校准[11，33]、3D-3D配准[33]和3D建模[1]等。SoS层级也被称为SDP中的LasserreLasserre松弛的第一项因此，[8，9]的非最小解算器（使用Shor此外，在非最小解算器的上下文中，其中提供了足够多的多项式，仅使用Shor松弛获得的紧密性可能不是问题。出于这些观察，我们有兴趣研究的行为的SoS层次的共识最大化和非最小的问题。在本文中，我们制定了一个通用的非最小求解器使用现有的工具多项式优化问题（POP）从计算代数几何。我们还提供了使用肖尔或Lasserre的放松的理论见解更准确地说，我们建议，肖尔此外，我们表明，更高阶的Lasserre更有趣的是，我们成功地应用了同样的配方用于非最小解也在共识最大化的背景下。然后，很明显，可以按照人们的愿望，通过增加更多的拉塞尔然而，我们认为，可能并不总是需要使用高阶松弛时，寻求多项式之间的共识。我们的框架是简单和直接的实现，这是由三个不同的应用程序在3D视觉，即刚体变换估计，非刚性重建，相机自动校准的支持。在所有三种情况下，都测试了非最小和共识我们进一步表明，建议的松弛工作令人满意，即使是最小的问题设置。我们所有的实验都与领先的最先进的方法进行了比较。我们的结果在速度和精度上都比计算机方法有竞争力，这也与我们的理论分析相一致。2. 背景和注释我们用大写字母表示矩阵，用双下标小写字母表示其元素：A =（a ij）。类似地，向量被索引：a=（a i）。 我们写一个1000（resp. A≠0）来表示对称矩阵A是正定的（分别为半正定）。 设IR [x]是由变量x ∈ IR n参数化的多项式环，zd（x）是在x的元素上的一个单项式向量，其阶递增到d. 任何多项式p（x）∈ IR [x]都可以用zd（x）和Gram矩阵表示。定义2.1（Gram矩阵[38]）对于次数≤ 2 d的多项式p（x）∈ IR [x]，使得p（x）=zd（x）<$Gzd（x）的对称矩阵G是p（x）的Gram矩阵。人们通常对解决以下一般非凸多项式优化问题感兴趣。问题2.2（多项式优化问题[24]）对于一组一般 非凸多项式pi（x），i =0，. . . ，m，多项式优化问题（POP）由下式给出，min？p0（x）|pi（x）≥ 0，i = 1，. . . ，m}。（1）在下文中，我们首先关注p（x）是二次的，然后才是更高次的多项式。注意，对于二次多项式，z1（x）是x的齐次表示.在这种情况下，可以使用Shor方法获得松弛凸解定义2.3（Shor松弛[41]）对于一般非凸二次多项式pi（x），i=0，. . . ，m，则（1）的POP等价于以下问题。min？tr（G0Y）|rk（Y）= 1，tr（GiY）≥ 0，i =1，. . . ，m}，（2）对于秩和迹运算符Rk（. ）和tr（. ）的情况下。 通过去掉对Y∶ = z1（x）z1（x）n的秩-1约束，可以得到（2）的凸松弛.10235i=1W0x，xi众所周知，对于（2）[6，26]的设置，Shor因此，（1）的解通过这种松弛非常好地近似。虽然，我们开发- velop大部分的理论使用二次多项式与肖尔的松弛，我们也解决了更高的次数多项式的情况下，更严格的松弛。在后者中，我们利用基于Lasserre的分层[ 25 ]的松弛现在，我们简要介绍拉萨尔的再润滑理论。特别是，我们讨论的情况下，最高阶的松弛是2n。对于松弛变量问题3.1对于x∈IR n，m≥ n，多项式 pi（x）∈ IR[x]，i = 1，. . . ，m，是，min？拉吉吉|公司简介|pi（x）|，i=1，. . . ，m}。（五）我3.1的问题实际上是多项式的L1人们通常感兴趣的是最小化这样的目标，因为在许多3D视觉问题中，距离是一个几何度量（例如使用基本矩阵的两视图极线约束的点到线距离）。根据应用，可能会有兴趣最小化L2w，2n阶截断矩矩阵为M2n（w）=（或L）。 然而，这并不是一个真正的W=W，使得wαβ=wα+β 其中α，β∈IN n.通过con-∞问题. 为了简单起见，我们首先介绍-结构，任何低阶矩矩阵都是W的子矩阵，其中Mn（w）=Y∶ =zd（x）zd（x）n，M0（w）=1。Lasserre的方法使用以下条件导出约束的层次结构：所谓的局部化矩阵。定义2.4（局部化矩阵[25]）多项式p（x）和松弛阶s≤n的局部化矩阵是矩阵Ms（p（x）w），由下式给出Ms（p（x）w）= L（tr（GY）Ms（w）），（3）其中Riesz函数L（. ）将Y和W上的双线性项映射到W的相应项。注意，Ms（w）是Y的子矩阵，其中s≤n。 因此，Ms（p（x）w）可以理论上使用L1公式。在第6节中讨论了它对Lp-范数的推广。非最小问题是过度确定系统的结果。我们所寻求的解决方案是一个符合所有多项式的最小累积误差，不像最小情况下的精确解。注意当n=m时，非最小问题变成最小问题。3.1. 二次多项式命题3.2对于一组非凸二次多项式{pi（x）}m，Shor松弛提供了非极小问题3.1的凸松弛，在这种情况下，可以线性地表示在W定义2.5（Lasserremin2000年，？拉吉吉|公司简介|tr（GiY）|，i=1，. . . ，m}。（六）我一般非凸问题2.2多项式可以通过求解弛豫层次的半定规划（SDP）来获得。对于松弛阶为2 n且i = 1，. . . ，m，它由下式给出，min？tr（G0Mn（w））|tr（Ms（pi（x）w））<$0}.（四）已知Lasserre事实上，Lasserre松弛包括Shor松弛，作为s = 0时的特殊情况，不用说，Lasserre然而，对于二次多项式的非极小问题，我们的实验表明Lasserre定理并不是真正必要的3. 多项式的非极小问题在这一节中，我们用公式表示多项式的非极小问题首先，我们提出了一个解决这个问题的一般二次多项式使用肖尔稍后，所提出的解决方案将被推广到10236我i=1在这里，我们提供了证明背后的直觉。注意，当rk（Y）= 1时，对于二次多项式{pi（x）}m，（6）的问题等价于（5）（6）可以可以直接通过丢弃秩约束来获得，类似于Shor事实上，可以使用第2节的POP公式得到严格的证明。请参阅补充资料的替代证明。松弛凸问题（6）是SDP。这可以使用内点方法有效地解决[7]。理想地，期望Y的秩为秩-1。然而，通常情况并非因此，我们使用奇异值分解（SVD）在强制秩-1约束后恢复原始解x∈IRn实际上，主奇异向量Y是x∈IRn+1的齐次表示.回想一下，对偶松弛变量Y以Y∶ =z1（x）z1（x）的形式编码原始解。3.2. 一般多项式命题3.3对于次数≤d的非凸一般多项式{pi（x）}m的集合，阶为s ≤ n ∈ IN的Lasserre使用Lasserre松弛方法的更高次多项式的情况minW100，？拉吉吉|吉吉我≥|tr（Ms（pi（x）w））|，i=1，. . . ，m}。 （七）10237i=1i=1i=1我i=1证明与命题3.2相似。请，推论4.3（二次情形）给定一组非凸详见补充资料。二次多项式S = {pi（x）}m 以 及 阈值ξ，最优原始解x∈IRn可以从W，类似于上面讨论的（6）。一致性最大化问题4.1可以使用下面的混合整数半定规划来解决，M4. 共识最大化问题minY∈0，zi∈Z？斯塔兹岛|ZiM+Z≥|tr（GiY）|，Z∈{0，1}m}。（十）i=1在前一节中提出的非最小方法假设多项式可能被噪声破坏。因此，搜索使所有多项式的累积误差最小化在存在噪声和异常值的情况下，我们希望解决以下问题。问题4.1给定一个集合S = {pi（x）}m 以及阈值ξ，（10）的MI-SDP可以使用离线优化工具箱有效地求解。MI-SDP解决方案为我们提供了最佳的内点多项式集，以及可行的x。然后，这些内点多项式用于解决（6）的非最小问题，以获得最优解x。下面给出了用于一般多项式之间的一致性最大化的类似MI-SDP公式Max ？|，≥|pi（x）|，<$pi（x）∈<$}.|,∀pi(x)∈ζ}.（八）推论4.4（一般情况）给定一个非凸的x，ζS一般多项式S = {p（x）}m 和阈值，共识最大化问题寻求一个可行的解决方案，导致最大的内点集-一然而，这个问题是一致性最大化问题4.1对于分配Z∈{0， 1}m可以使用以下MI-SDP求解M[14]这是一个很难解决的问题，而且是NP难的问题，p（x）是关于x的线性函数。在这项工作中，我们接近这个minW∈0，zi∈Z？斯塔兹岛|ZiM+Z≥|tr（Ms（pi（x）w））|{\fn方正粗倩简体\fs12\b1\bord1\shad1\3cH2F2F2F}（十一）i=1使用分支定界搜索范式的问题。4.1. 分支定界法我们的分支定界（BnB）搜索是通过在二元赋值变量空间上分支来执行的，S中的每个成员一个。在BnB过程中，我们使用混合整数规划方法来寻求可行的x定义4.2（混合编程，MIP）对于一组二元变量Z∈{0， 1}m，表示内点/离群点分配，一组给定的多项式，5. 3D视觉问题我们提出了三个例子的3D视觉问题的共识最大化和非最小的问题。我们从所有三个问题的共识最大化的一般公式开始。一致性最大化的内点集，然后用于解决最优参数集的非最小问题在这两个阶段中，我们还引入了特定于问题的多项式约束。让我们考虑一组向量化多项式{P i（x）} m ，可能来自许多离群值测量，米亚尔斯 S = {pi（x）}m和阈值，共识最大化问题4.1等价于，i=1给我们的在第一步中，我们感兴趣的是解决在共识最大化问题之后，minx，zi∈ZM？斯塔兹岛|ZiM+Z≥|pi（x）|，Z∈{0，1}m}，（9）i=1minx，zi∈ZM？斯塔兹岛|ZiM+Z≥|Pi（x）|，x∈K，Z∈{0，1}m}，（12）i=1其中M是一个足够大的正标量常数，通常用于优化以忽略无效约束[17]。如果二进制变量z i= 0，则多项式pi（x）是内点。否则，它是一个离群值。4.2.使用MI SDP达成我们用公式表示共识最大化问题，其中x∈ K表示问题特定的约束，Z度量内点/离群点分配，"“≥”“表示一对多元素不等式。对于x和Z，我们使用推论4.3/4.4求解（12）。一旦内点/离群点分配，即Z，我们使用我们的命题3.2 / 3.3解决以下非极小问题。M10238在混合半定规划（MI-SDP）的框架内使用多项式松弛，minx，xi？拉吉吉|ZiM+Zi≥|Pi（x）|，x∈K}。（十三）i=1两个不同的案子首先，我们使用（2）的Shor后来，在相同的框架内使用（4）的Lasserre5.1. 刚体变换我们考虑两个点云之间的对应关系，不同的3D刚体变换。设{u，v}是一对对应点的欧几里得坐标，10239i=12我I=2I=2对于旋转矩阵R∈SO（3）和平移矩阵t∈IR3，v=Ru+t.对于四元数q∈IR4，我们将旋转矩阵表示为R（q），其元素在q中是二次的。给定一组对应关系{ui，vi}m，我们分别解决以下共识最大化和非最小化问题：（12）和（13），对于变量x=（q，t）和多项式P i（x）= vi− R（q）ui− t，其中K ={x |q相机帧中的图像坐标。然后可以计算n个形状的每个对应点处的表面法线。我们解决了共识最大化和（15）的非最小问题以解决NRSfM问题。6. 讨论（5）的L1约束（以及随后的约束）可以5.2. 相机自动校准从一组给定的基本矩阵{F}m，我们通过用单个变量替换所有的可变量来扩展到L∞ii=1最小化[7]。 同样，L2范数也可以最小化希望估计相机内禀矩阵K。这里我们假设在基本矩阵估计期间所涉及的所有图像 设ω是绝对二次曲线的对偶像，用K表示为ω=KK<$。简化的Kruppa设Fi=UiDiVi是奇异值分解，D= diag（[ri，si，0] ） . 对 于 Ui=[ui1|ui2|ui3] 和 Vi=[vi1|vi2|vi3] ， 简 化Kruppa方程的两个独立多项式为，Pi1 （ ω ） = （ r sv<$ωvi2 ） （ u<$ωui2 ） +（r2v<$ωvi1）（u<$ωui2），通过对多项式 vi（x）= [trace（G1iY），. . .，trace（GmiY）]的值（分别为：（7））对于m个第i个测度的多项式，使得n∈vi（x）n ∈2≤n ∈i. 在这个过程中，我们为每个测量引入一个变量，因此我们的方法的时间复杂度预计与测量次数呈线性关系尽管这些辅助变量看起来可能会引入开销，但它们实际上是有帮助的。这些变量允许我们将非最小问题表示为SOCP。SOCP约束使我们能够很容易地将我们的非最小公式扩展到共识最大公式。一、二、三、四i i1i1在这种情况下，变量numi自然会变成内点阈值。Pi2（ω）=（r s v<$ωvi2）（u<$ωui1）+（s2v<$ωvi2）（u <$ωui2）。老了对于非最小问题，可以我1我1i i2I1（十四）选择最小化∑i（或偶数∑pi（x）2）di-我们使用x ∈ IR 5来参数化ω，因为ω是3 × 3矩阵，其中ω=ω且ω（3，3）=1。给定一组基本矩阵{Fi}m，我们求解一致最大化问题使用标准的SOS优化方法。这样的公式化不仅损害了灵活性，而且通过增加多项式的次数而增加了负担。i=15以及（12）和（13）的非极小问题，对于x∈IR，Pi（x）=（Pi1（ω），Pi2（ω））π，并且K = {x|ω0}。利用ω上的Cholesky分解恢复了固有K。5.3.运动非刚性结构[34]中的方法提出了一个框架，使用等距的几何先验将NRSfM建模为POP。它将静止形状建模为黎曼流形，将变形形状建模为静止形状的等距映射。然后通过度量张量、k1，k2∈R参数化的Christoffel符号和摄像机坐标系下的图像间配准翘曲来我们从原始问题公式中借用Christoffel符号参数化的符号和定义[34]。如[34]中所述，我们将所得多项式系统总结为：Pi（x）= P（x）− {P1i（x）}n（15）事实上，公式（15）是n-1个独立的四次多项式的系统，用于n个图像，其将逐点图像间扭曲测量qn与由x=[k1k2]n表示的Christoffel符号相关联。求解（15）相当于求解等距NRSfM问题，因为k1，k2可用于获得每个形状相对于参考的雅可比矩阵7. 实验我们用合成和真实数据集进行了几次实验。合成数据是使用[8]的工具箱在非常相似的设置中生成的，而使用的真实数据集是Fountain和Herz-Jesu [44]，Flag[45]，Hulk和Tshirt [34]。在真实数据集的情况下，仅合成生成离群值用于定量评价。我们所有的非最小解算器的结果后产生的共识最大化，除了最小的情况下。我们的框架在MAT-LAB 2015 a中实现，所有优化问题都使用MOSEK [29]解决。所有实验都在16 GBRAM Pentium i7/3.40GHz上进行。图1中显示了针对不同应用获得的一些定性结果（稍后讨论）。7.1. 刚体变换我们进行了大量的合成实验，以探索所提出的框架对刚体变换估计的行为，无论是非最小和共识最大化问题。这主要是因为存在三个不同的非极小解，即Briales在第一个前-210240Briales'17Olsson'08Olsson-BnBOur方法101101100100图1：使用我们的框架获得的非最小结果。从左至右：刚性配准（型号：绿色;0 2 4 6噪音（%）0 10 20 30数量的点数据：红色）;使用估计的相机本征函数获得的喷泉序列的3D重建;非刚性3D重建（地面实况：绿色;重建：红色）的T恤与拉塞尔的放松。图3：噪声最小情况（3分）和数字点非最小情况（固定1.0%噪声）所用的时间刚体变换估计的结果。432100 2 4 6噪音（%）1210864200 2 4 6噪音（%）10.80.60.40.20Briales'17Olsson'08Olsson-BnBOur方法0 10 2030数量的点32.521.510.50Briales'17奥尔森'08Olsson-BnB我们的方法0 10 20 30数量的点图2：最小（3点）刚体变换估计的结果。从左到右：四种不同方法的噪声与旋转角度和平移误差的关系。实验中，我们测试了不同的方法在最小的设置与不同的噪声水平的性能所得结果报告于图2中。注意，刚体变换问题是一个3点问题。对于图2可以观察到，在估计旋转和平移参数方面，与全局最优方法Olsson-BnB相比，我们的方法表现得非常有竞争力，然而，我们的方法在时间方面非常有竞争力，如图3（左）所示，与BrialesOlsson'08的实验还进行了非最小设置的实验，通过改变固定噪声水平的点数，报告了与最小情况类似的措施。这些实验的结果报告在图4中。这里图4：刚体变换估计的非最小（1.0%噪声）结果。旋转角度和平移误差与越来越多的点。最大化尽管将非最小解算器与提供一致性最大化和非最小解的框架进行比较是不公平的，但图5显示了仅使用非最小解算器时离群值的影响请注意，我们的方法表现良好，即使数据被90%的离群值污染（10个内点和90个离群值）。正如预期的那样，非最小解算器在时间上与离群值的增加保持一致，其中它们是无关紧要的，如图6（左）所示另一方面，我们的框架在解决非最小问题之前过滤离群值 我们的方法也与 全局一致性最大化Speciale离群值数量增加的时间比较如图6（右）所示。我们可以观察到，我们的方法在精度方面仍然表现得非常类似于Olsson-BnB。请注意，我们的方法的时间（如图3（右）所示）随点数线性增加这背后的原因是-我们已经在第6节中讨论过了，在那里我们还提出了通过牺牲灵活性来加速不像最小情况，Olsson'08执行非常类似于01sUsosinn-gBnthBeaflnedxBibriilaiyso'1ff7e。通过我们的方法，我们相信-102101100十比一10-2Briales'17Olsson'08Olsson-BnB我们的方法0 20 40 60 80 100数量的异常值103102101100十比一Briales'17Olsson'08Olsson-BnB我们的方法0 20 40 60 80 100数量的异常值导出了异常值数量增加的实验，并在图5中报告了实验。我们的框架提供了一致的结果，即使在测量中存在离群值，因为它通过了共识的过程图5：我们的框架与其他非最小解算器具有增加的离群值（和固定的10个内点对应），用于刚体变换估计。旋转和平移估计中的误差与离群值的增加。数据模型GT重调玻璃Briales'17奥尔森'08Olsson-BnBOur方法Briales'17Olsson'08Olsson-BnBOur方法Briales'17Olsson'08Olsson-BnBOur方法旋转误差（度）翻译错误（%）时间（秒）旋转误差（度）旋转误差（度）翻译错误（%）时间（秒）翻译错误（%）1024141041031021021000 20 40 60 80100数量的异常值1011000 20 40 60 80 100离群值数量图6：与全局非最小解算器（左）和全局一致性最大化方法（右）的时间比较，刚体变换估计的离群值增加（固定10个内点对应）。7.2. 相机自动校准表1：我们的框架与两个本地[19，28]和三个全局[13，12，20]方法在两个真实数据集上的摄像机自动校准的非最小设置中。视图-1是所有实验中使用的测量数量。我们在两个真实数据集上进行了相机自动校准实验：[44]朱熹和朱熹。将我们的框架获得的结果与三种现有的全局自动校准方法进行比较：[20 ]中的LMI直接方法，[ 12 ]中的秩3直接方法，[ 13 ]中的分层方法。这三种方法都假定自洽运动所需的射影运动是自洽运动，201510500 100 200 300 400迭代次数50403020100500增加离群值振动没有异常值，并且以最优方式最小化全局成本。因此，它们可以被认为是某种非最小解算器。[20]、[12]和[13]所需的投影重建是使用[30]得到的。我们还将我们的方法与两种本地相机校准方法进行了比较，即实用形式[19]和[28]的Simplified-Kruppa。通过计算摄像机内参数的误差，给出了标定精度的定量结果。使用三种不同的误差测量度量：焦距误差φ f、主点误差φ uv、偏斜误差φ s。所有6种方法获得的结果见表1。对于一致性最大化的实验，我们综合地引入了离群Kruppaourliers以增加的方式增加到80%。我们的共识最大化方法，与Shor的放松，是能够正确地检测两个数据集的所有内点和离群点。我们跟踪了增加BnB迭代的悲观和最优内点的数量，如图7（左）所示。将共识最大化实验与用于自动校准的全局共识最大化方法（即来自[ 37 ]的Paudel为了进行公平的比较，如[37]中所示，选择DIAC。因此，我们假设焦距位于相对于图像尺寸的[110]间隔内，纵横比位于0.7-1.25之间，主点位于图像中心周围，半径为图像尺寸的1倍有了这些假设，我们使用区间分析算法[2]推导出DIAC的界，类似于（10）中相应的变量X请注意，在大多数情况下，这些假设对于相机校准是有效的我们的研究结果表明图7：左：喷泉数据集的收敛图。右：我们的方法和[37]检测到的时间和内点，Herz-jesu上的离群值和固定内点图7（右）中报道了Paudel'18的框架以及这些结果还表明，我们的框架可以大大受益，如果所寻求的参数的界限也是已知的。事实上，在许多3D视觉问题中，情况往往如此。7.3. 运动非刚性结构在Parashar从N个图像中，使用5.3节中提出的理论提取了2个N-2个关于Christoffel符号k1和k2的2个变量的多项式，即（15）。对于这些多项式，我们首先计算的非最小的解决方案，使用建议的框架与肖尔然而，肖尔河注意，（15）是使用局部对应的二阶测量来表示的，因此它们的系数对噪声非常敏感。此外，对于每个点独立地求解（15）的多项式。在这种情况下，非最小解算器是非常有价值的，其中四次多项式的超定系统由跨视图的多个测量提供。因此，[35]的方法使用SOS弛豫的层次来获得期望的解。在这种情况下，我们观察到Lasserre因此，我们展示了Briales'17Olsson'08Olsson-BnB我们的方法我们的方法Speciale'17悲观乐观正确内点时间（秒）内值和离群值Inliers-Paudel'18Inliers-我们的时代-我们的时代Time-Paudel'18时间（秒）的内点的数量时间（秒）数据集方法Δf∆uv∆s时间（s）喷泉（11-视图）实用[19]0.01170.01490.00370.36分类[13]0.07770.09690.0125388.24三品嫡系[12]0.01000.01470.00445.75[20]第二十话0.05060.02690.0024156.88[28]第二十八话2.93e-050.00693.23e-051.88我们0.00600.00616.46e-040.83Herz-jesu（8-views）实用[19]0.00170.01130.00680.36分类[13]0.72310.44620.3232380.72三品嫡系[12]0.00260.00960.0069十六点五四[20]第二十话0.01380.00860.005115.61[28]第二十八话4.46e-050.00693.40e-050.5310242Parashar'18-SoSShor的放松Lasserre放松深度误差（mm）深度误差（mm）6544322100 5 10 15 20 25 300视图索引标志绿巨人Tshirt虽然，比较非最小解算器的结果可能不是很有趣，即。Parashar'18，与一般的共识最大化方法相比，它在这种情况下有些不同。我们还没有讨论的一个方面是SOS方法的力量它是根-图8：非最小等距非刚性重建的结果。从左到右：标志数据集的深度和法向误差，三种方法在不同数据集上的深度误差。Shor's和Lasserre's松弛之间的差异在前两个问题中，它们的差异在准确性方面不是很显著，而只是在速度方面我们使用数据集Flag [45]，Hulk和Tshirt [34]来评估我们的非最小解算器。对于非最小情况，将我们获得的解决方案与图8中的基线Parashar从图8中注意到，基线方法与仅基于Shor然而当我们众所周知，SOS解算器对噪声具有鲁棒性[36]，SOS解算器即使在存在离群值的情况下也相对稳定。乍一看，我们认为这可能是因为Parashar'18的al-taxm中的离群值的迭代细化事实证明并非如此。SOS方法始终表现得相当好，即使当迭代细化过程被删除。这是因为两个原因：一个是SOS方法对中等数量的离群值的鲁棒性;另一个是在某种意义上无法获得有效的解决方案意味着检测离群值。这种离群值检测特定于[35]的问题形成，因为在这种情况下POP是逐点定义的。5使用Lasserre的一阶松弛（即，s= 1），该解与[ 35 ]中使用的SOS弛豫的层次结构的解相比变得非常有竞争力。这表明，高阶弛豫并没有提供显著的改善，43210 5视图索引4210 150标志绿巨人Tshirt至少对于NRSfM的这种特定制剂而言。事实上，人们普遍认为，NRSfM是一个非常棘手的问题，在三维视觉。我们从实际数据集的观察当然，我们的观察可能只从我们测试过的三个问题中产生偏差。特别是刚体变换和摄像机标定的二次多项式，以及NRSfM情况下一次只涉及两个未知变量的四次多项式然而，人们需要意识到，在泄露到更高的松弛之前，可以先尝试更低的松弛如果低阶松弛已经提供了满意的解决方案，这不仅允许人们更快地获得非最小解，而且还允许通过使用BnB范式在共识最大化的全局框架内使用相当不明显的多项式问题。为了支持我们的主张，即使是较低程度的放松是足够的共识最大化，我们进行了几个实验与各种数量的合成离群值在上述真实数据集。对于NRSfM的设置，当引入高达70%的离群值时，我们能够检测到几乎所有的离群值。图9中报告了所有三个数据集的一个此类共识最大化实例的结果，其中50%为离群值视图在图9中，我们在左侧显示了内部层视图的估计深度误差正如预期的那样，Lasserre松弛的结果尽管如此，肖尔图9：等距非刚性重建的共识最大化结果。从左到右：对flag数据集的深度误差和正态误差进行了比较，对综合添加50%离群值的不同数据集，三种方法的深度误差进行了比较。8. 结论在本文中，我们证明了一个适当的使用现有的工具，在数值代数几何POP可以用在一个简单的方式在许多三维视觉问题。这是通过使用已知的一方面，我们认为，现有的解决方案可以在其目前的形式来解决许多3D视觉问题，特别是最佳的非最小解算器还没有被设计出来。我们还讨论了制定POP的良好做法。使用我们的理论推理，我们提出了一个通用的宽松的非最小解算器，是适合可能的3D视觉问题的建议。我们进一步论证了多项式松弛的标准方法确实是强大的，它也可以以确定性的方式用于共识最大化。我们已经支持我们的建议/索赔使用三个不同的问题在3D视觉的几个实验。我们得出这一结论主要是因为3D视觉问题中的许多多项式固有地具有有限变量的低次。Parashar'18-SoSShor的放松Lasserre放松Parashar'18-SoSShor的放松Lasserre放松深度误差（mm）Parashar'18-SoS Shor的放松Lasserre放松深度误差（mm）10243引用[1] Amir Ali Ahmadi，Georgina Hall，Ameesh Makadia，and Vikas Sindhwani.三维环境几何与多项式平方和。arXiv预印本arXiv：1611.07369，2016。2[2] GotzAlefeld和GunterMaye r.区间分析：理论与应用。计算与应用数学杂志，121（1）：421-464，2000。7[3] 丹尼尔·巴拉斯，泰克拉·托特，和莱文特·哈德尔。利用两个仿射对应关系估计两视图焦距的最小解。2017. 5[4] 阿德里安·巴托利。推广了预测平方和统计量和公式，并 将 其 应 用 于 线 性 分 形 图 像 变 形 和 曲 面 拟 合 。International Journal of Computer Vision，122（1）：61-83，2017。2[5] Jean-Charles Bazin，Yongduek Seo，Richard Hartley，and Marc Pollefeys.旋转和焦距未知的全局最优内点集最大化。在欧洲计算机视觉上，第803Springer，2014.1[6] 斯蒂芬·博伊德和利文·范登伯格。控制与组合最优化中非凸问题的半定规划松弛。《通信、计算、控制和信号处理》，第279Springer，1997. 二、三[7] 斯蒂芬·博伊德和利文·范登伯格。凸优化。剑桥大学出版社，纽约，纽约，美国，2004年。三、五[8] Jesus Briales，Javier Gonzalez-Jimenez，et al.具有拉格朗日对偶性的凸2017年计算机视觉与模式识别国际会议（CVPR）。一、二、五[9] Jesus Briales ， Laurent Kneip ， SIST Shanghai Tech 和Javier Gonzalez-Jimenez。非最小相对位姿问题的可证全局最优解在IEEE计算机视觉和模式识别会议上，第145-154页，2018年一、二[10] Zhipeng Cai，Tat-Jun Chin，Huu Le，and David Suter.双凸规划的确定性一致最大化2018年欧洲计算机视觉会议。1[11] Manmohan Chandraker ， Sameer Agarwal ， FredrikKahl，David Nister，and David Kriegman.通过绝对二次曲面的秩约束估计的IEEE计算机视觉与模式识别会议（CVPR），2007年。2[12] 曼莫汉·钱德拉克，萨米尔·阿加瓦尔，弗雷德里克·卡尔，达维德·尼斯特尔和达维德·克里曼。 通过绝对二次曲面的秩约束估计的自动校准 计算机视觉和模式识别，2007年。07年CVPR。IEEE会议，第1-8页。IEEE，2007年。7[13] ManmohanChandraker 、 SameerAgarwal 、 DavidKriegman和Serge Belongie。分层自动校准中的全局最优仿射和度量升级。计算机视觉，2007年。ICCV 2007年。IEEE第11届国际会议，第1-8页。IEEE，2007年。7[14] Tat-Jun Chin，Zhipeng Cai，and Frank Neumann.计算机视觉中的鲁棒拟合：容易还是难？在欧洲计算机视觉会议上，2018年。1、4[15] Tat-Jun Chin，Yang Heng Kee，Anders Eriksson，andFrank Neumann.混合整数线性规划的保证离群点去除。在IEEE计算机视觉和模式识别会议论文集，第5858-5866页，2016年。6[16] Tat-Jun Chin ， Pulak Purkait ， Anders Eriksson ， andDavid Suter.树搜索的高效全局最优共识最大化。在IEEE计算机视觉和模式识别会议论文集，第2413- 2421页，2015年。1[17] 约翰·W·钦内克优化的可行性和不可行性：算法和计算方法，卷118。Springer Science Business Media，2007. 4[18] Anders P. Eriksson，Carl Olsson，Fredrik Kahl，and Tat-Jun Chin. 旋转平均和强对偶性。在CVPR，2018年。1[19] Riccardo Gherardi和Andrea Fusiello。实际自动校准。计算机7[20] Adlane
我的内容管理
展开
