1一个聪明的消除策略，有效的最小解算器Zuzana Kukelova1 Joe Kileel2 Bernd Sturmfels2 Tomas Pajdla11捷克布拉格技术大学，电气工程学院，捷克共和国网址：kukelova@cmp.felk.cvut.cz，pajdla@cvut.cz2美国加州大学伯克利分校网址：jkileel@math.berkeley.edu，bernd@math.berkeley.edu摘要我们提出了一个新的见解，在计算机视觉中的最小解算器的系统生成，从而导致更小，更快的求解器。许多最小问题公式是线性和多项式方程的耦合集，其中图像测量仅进入线性方程我们表明，它是有用的，以解决这样的系统，首先消除所有的未知数，不出现在线性方程组，然后扩展的解决方案，其余的未知数。这可以通过提升线性化推广到完全非线性系统。我们证明，这种方法导致更有效的求解器在三个问题的部分校准的相对相机姿态计算与未知的焦距和/或径向失真。我们的方法还产生了新的有趣的约束的基本矩阵的部分校准的相机，这是以前不知道的。1. 介绍计算多视图几何是计算机视觉中最基本和最重要的任务之一[1]。这些包括最小问题求解器[2，3]，例如，结构从运动[4]，视觉导航[5]，大规模三维重建[6]和基于图像的定位[7]。快速有效的最小解算器有助于基于RANSAC [8]的鲁棒估计算法[9]。在本文中，我们提出了一个新的见解系统生成的最小求解器[3]，这导致更小，更快的求解器。我们在消除理论[10]的背景下解释我们的方法，并提供对计算机视觉实践有用的理论解释。我们的主要技术贡献是解决最小问题的新策略。对于许多计算机视觉应用，该策略允许在6420-2-4-6-6-4-2 0 2 4 6X图1.定义f+E+f问题的两个方程（17）和（18）的图示，由六个线性方程切割，用于六个图像点对应。离线阶段和在线阶段中更少的计算。我们利用计算机虚拟现实中的许多小问题解导致耦合的线性和多项式方程组其中图像测量仅进入线性方程。我们展示了如何有效地解决这样的系统，首先消除所有的未知数，不出现在线性方程，然后扩展解决方案的其他未知数。此外，我们的方法可以推广到完全非线性系统的线性化通过单项式提升[11]。我们证明，这种方法导致更有效的在线求解器在三个问题的部分校准的相对相机姿态计算与未知的焦距和/或径向失真。有趣的是，我们的方法还对部分校准的相机的基本矩阵产生了新的约束，这是以前不知道的1.1. 相关工作历史上，最小问题[12，13，14，15]解决了一个和两个透视相机的几何问题。后来，一个更系统的方法来解决最小问题，4912等式（17）等式y4913出现了计算机视觉中的LEMS，例如，在[2，16，17，18，19，20]中。它开发了一些特别的，以及系统的工具来解决出现在计算机视觉中的多项式系统这些后来被许多研究者使用和改进，例如，[21、22、3、23、24、25、26、27、28、29、30、31]。最近，计算机视觉的代数几何基础在代数视觉中成为焦点[32，33，34，35，36]。计算机视觉应用中的关键要素之一是设计用于求解特殊多项式系统的程序，该程序将计算从在线解方程的阶段到较早的离线阶段[37]。有趣的是，消除理论[10]尚未在此类计算机视觉应用中得到充分利用，尽管它已在许多作品中隐式使用[2，20，38，3，39]1.2. 其主要思想我们的主要思想是利用消元法，在离线阶段多做计算，在线阶段少做计算。视觉模型的自然公式通常涉及比那些出现在依赖于图像测量的线性约束中的未知数更多的未知数。例如，基本矩阵计算中的约束detF=0不涉及任何图像测量。我们认为有利的是通过计算其在相关未知量空间中的投影来预处理这种模型。这是通过消除来实现的。然后，在所得到的投影变量上求解线性方程组是快速的。随后，其他未知数的值可以使用计算机代数中的扩展定理[10]来确定。2. 用消元法求解多项式方程组的经典（教科书）策略是使用消元理论[40，10，41]。该战略包括两个主要步骤。1. 首先，通过消除一些未知数来“简化”方程，以得到一组方程，从该组方程可以计算剩余的未知数。这提供了一组部分解。2. 其次，通过将部分解代入原始方程并求解剩余的未知量，将部分解扩展为完全接下来，我们解释不同的消除策略。2.1. 消除战略2.1.1标准教科书淘汰策略标准（教科书）消元法基于消元定理[10]，我们在附录的定理1.1中对此进行了回顾。它指出，对于理想的IC[x1 ， . . . ， xn] ， 我 们 可 以 读 出 所 有 消 去 理 想Il=I∈C[x1，. . . ，xn]从一个LEXGr¨ obner基G对I.在这里，消去理想的序列结束于In=IC[xn]。这是由一个方程在单一的未知数xn，这是很容易解决的数字。对于Cn中具有有限个解的多项式系统，总是可以从xl+1，. . . ，Xn到Xl，. . . ，Xn。为此，我们选择一个单一的多项式g与最低的次数在所有的一元多项式xl后，取代的多项式的部分解决方案，在xl+1，. . . ，Xn。2.1.2标准计算机视觉消除策略在现有的最小解算器中，应用了几种不同的策略来消除输入方程中的未知量这些策略通常依赖于特定的问题，并且是手动导出的在这里，我们描述了一种在绝大多数现有的最小求解器中使用的策略[2，20，38，3，42，39]。考虑一个m多项式方程{f1（x1，. . . ，xn）= 0，. . . ，fm（x1，. . . ，xn）= 0}在n个未知数中，X ={x1，. . . ，xn}。我 们 假设集合F ={f1，. . . ，fm}生成零维理想I ∈C[X]，即系统F有有限个解。在该策略中，集合F被划分为两个子集：FL={fi∈F|deg（fi）= 1}，（1）FN={fi∈F|deg（fi）> 1}。（二）这意味着FL包含来自F而FN包含更高次的多项式。线性方程FL可以被重新写为MXL=0，其中XL是出现在这些方程中的所有未知量的向量。然后，M的零空间基N，即，M N = 0，用于通过XL=NY用新的未知数Y参数化未知数XL。然后将参数化XL=NY插入非线性方程FN中。 系统FN（Y∈（X\XL））= 0使用例如 Gr？bner基方法和高效求解器的自动生成器[3]。溶液Y用于回收溶液XL=N Y。2.1.3一个聪明的计算机视觉消除策略在计算机视觉中，我们经常遇到多项式系统，其中只有线性方程FL依赖于图像测量，而非线性方程FN保持不变，而不管图像测量如何。例如，极线约束[1]生成依赖于输入测量的线性方程，而基本矩阵[1]的奇异性导致非线性方程det（F）=0，其不依赖于测量。在这里，我们提出了一个新的这通常允许我们在离线阶段进行更多的计算，而在在线阶段进行更少的计算。4914147258在本节中，我们假设非线性方程FN不依赖于图像测量，即。对于所有情况，这些方程是相同的稍后，在第- tion3.3，我们将展示如何处理的问题时，FN包含方程，取决于图像测量。现在让我们描述一下我们的新的消除策略。我们首先将输入方程F分成（1）中的线性方程FL和（2）中的非线性方程FN此外，我们将n个给定的未知数X分成两个子集：XL={xi∈X|xi出现在某个f∈FL}（3）中XN=X\XL.（四）集合XL包含线性方程中出现的未知数。集合XN只包含出现在高次方程中的未知数。 我们修正以下符号：|FL|=mL，|FN|=mN，|XL|=nL，|XN|=nN，这意味着m=mL+mN和n=nL+nN。现在，我们新的消元法的思想是从非线性方程组FN中消除所有未知数XN。非线性方程FN不依赖于图像测量，并且对于给定问题的所有实例都是相同的因此，我们可以在预处理步骤中离线执行此消除。这种消除可能需要计算。但是，由于我们只在预处理步骤中执行一次，因此在求解器运行时这不是问题接下来，我们进一步消除mL未知数从XL使用mL线性方程从FL。这是在线完成的，但它很快，因为求解一个小的线性系统很容易。更详细地说，我们的方法执行以下步骤。离线：1. 设I=<$FN<$，考虑消去理想IXL =IC[XL].2. 计算I×L的生成元G。这些仅包含来自XL的未知数，即。在线性方程组FL中出现的未知数。缐上：7. 回代以恢复XL= NY。8. 将XL的部分解推广到X的解。我们的消除策略与之前在极小解算器中使用的消除策略（参见第2.1.2节）之间的主要区别在于，之前的策略将参数化XL=NY直接替换到输入非线性方程FN中。这导致了在nN+k个未知数Y<$XN中的mN多项式方程。另一方面，新方法从非线性方程组中消除了nN个未知量，并在预处理步骤中创建了k个未知量的系统G（Y）=0我们将展示计算机视觉中的几个重要问题，解决系统G（Y）=0而不是系统FN（Y<$XN）=0更有效。在介绍我们对计算机视觉中更复杂问题的新策略之前，我们用一个简单但仍然具有代表性的例子来说明我们策略的关键思想。在附录§A.2中，我们将证明估计具有未知焦距的3D平面单应性的问题，即。来自平面点的具有未知焦距的投影矩阵导致具有与该说明性示例中相同结构的多项式方程系统。2.2. 例如让我们考虑下面的九个齐次多项式方程的系统，十个未知数X={h1，h2，h3，h4，h5，h6，h7，h8，h9，w}。有七条线-在h1，. . . ，h9，即Σ9FL={fj=cijhi= 0，j = 1，. . . ，7; cij∈Q}，（5）i=1和两个四阶方程{h1，h2，h4，h5，h7，h8，w}FN={w2h1h2+w2h4h5+h7h8=0，（6）w2h2+ w2h2+ h2− w2h2− w2h2− h2= 0}。3. 把线性方程组FL改写成未知数XL其中M是系数矩阵，向量XL包含来自XL的所有未知数。4. 计算M的零空间基N并重新参数化未知数XL=NY。如果M的秩是mL，即FL中的方程是线性无关的，Y将包含k=nL−mL个新的未知数。 注意，如果F中的所有输入方程都是齐次的，我们可以将Y中的一个未知数设置为1（假设它是非零的），然后k=nL−mL−1。使用第2.1.3节的符号，我们有XL={h1，. . . ，h9}和XN={w}。（七）我们进行如下操作：1. 创造消除理想Iw= I <$Q[h1，h2，h3，h4，h5，h6，h7，h8，h9]。2. 计算主理想Iw的生成元。这是一个四次多项式：5. 将XL=NY代入元素的生成元GG={h h h h2+h h h h2−h2hh h+h2h h理想I×L。1 274 571 7 827 8−h2h7h8+h2h7h8−h1h2h2−h4h5h2}（8）6. 解决 的 新 系统 的 多项式方程G（Y）=0（例如， 使用Gr？bner基方法和通4915过使用自动生成器[3]获得的G（Y）= 0的预先计算的消除模板）。4 5 8 8G中的多项式可以在离线预处理阶段使用计算机代数系统Macaulay 2[43]中的以下代码计算：4916]我R = QQ[w，h1，h2，h3，h4，h5，h6，h7，h8，h9];G =消除（{w}，理想（w 2* h1* h2 + w 2* h4*h5 + h7* h8，w 2* h1 2 + w 2* h4 2 + h72 - w 2* h2 2 - w 2* h5 2 -h8 2））;3. 将FL（5）中的七个线性方程改写为Mh=0，由自动生成器[3]生成的求解器执行31×46矩阵的G-J消去，并且据我们所知，它是f+E+f问题的最快和最稳定的数值求解器。所有最先进的（SOTA）求解器都利用了其中h=[h1，h2，h3，h4，h5，h6，h7，h8，h9]，M=3×3基本矩阵F=[f3iji，j=1∈R3×3满足[cij]是7×9系数矩阵。4. 使用M的零空间基{n1，n2}将来自XL的未知数重新参数化，其中两个未知数为：h=y1n1+ y2n2.（9）由于输入方程是齐次的，我们设置y2=1（假设y20）。E=K F K=K F K（10）其中K=diag（f，f，1）是具有未知焦距f的对角3×3校准矩阵，E是3×3基本矩阵[1]。本质矩阵的秩为2，并且满足Demazure方程[44]。2E E E − trace（E E）E = 0。（十一）5. 将新的参数化（9）代入生成器（8）。6. 用一个未知量y1解出所得方程。（也称为跟踪约束）。在所有SOTA求解器[20，21，3]中，来自极线约束的线性方程（12）第二个条件：7. 使用y1的解来恢复XLii的解使用（9）。8. 通过代入FN的解，将XL的解推广到X的解.在这种情况下，我们的消元策略生成一个四次方程。另一方面，第2.1.2节中描述的消元策略生成两个未知数的两个方程。更准确地说，第2.1.2节中的策略将参数化（9）直接替换为来自FN（6）的两个方程。这就得到了两个未知数y1和w的两个方程。在联机阶段求解两个未知数的两个方程的系统比求解单个二次方程花费更多的时间。1. 应用1.1. f+E+f相对位姿问题我们使用我们的消除策略解决的第一个问题是从六个图像点对应估计两个相机的相对姿态和共同的未知焦距。这个问题也被称为6点焦距问题，或f+E+f问题。f+E+f问题是计算机视觉中的一个经典和流行的问题，有许多应用，例如，从运动中恢复结构（Structure-from-Motion）[4]。最小f+E+f问题有15个解，最早由Ste w e`nius等人解决。 [20]使用Gr o bner基方法。Stewe` nius的求解器包括三个大小为12×33、16×33和18×33的矩阵的G-J消去和一个15×15矩阵的特征值计算。近年来，文献[21]和[3]提出了f+E+f问题的两种Gr？bner基解法 来自[ 21 ]的求解器执行34×50矩阵的SVD分解，并使用特殊技术来提高Gr o¨ bner基求解器的数值稳定性。Gr öbner基对于六个像点对应xi，x′，i = 1，. . . ，6，在两个视图中首先以矩阵形式重写Mf=0，（13）其中M是一个6×9系数矩阵，f是基本矩阵F的9个元素的向量。对于两个视图中的六个（通用）图像对应，系数矩阵M具有三维零空间。因此，基本矩阵可以由两个未知数参数化为：F=xF1+yF2+F3，（14）其中F1，F2，F3是从M的三维零空间创建的矩阵，x和y是新的未知数。我们使用参数化（14），即基本矩阵det（F）= 0，（15）以及基本矩阵的迹约束（11），连同（10）以如下形式：2F Q F<$ Q F−trace（F Q F<$ Q）F=0，（16）这导致十个三阶和五阶多项式方程，三个未知数x，y和w=1/f2。在（16）中，我们设Q=KK=diag（f2，f2，1）。我们注意到，迹线约束（16）可以通过将其乘以1/w2来简化。4917在三个未知数x，y中的十个方程（15）和（16）和w被用作f+E+f问题的所有SOT AGro¨bner基求解器的输入方程[20，21，3]。注意，所有SOTA求解器都遵循第2.1.2节中描述的消去法，它们的区别仅在于用于求解最终非线性系统FN的方法。接下来，我们为使用2.1.3节中的消去策略创建的f+E+f问题提出一个新的求解器。这种策略不仅生成了一个更有效的求解器，而且还揭示了基本的矩阵的相机与未知的焦距。49181313232321 2322 23消去理想公式对于f+E+f问题，我们从理想I∈C [f11，f12，f13，f21，f22，f23，f31，f32，f33，f]开始，理想I ∈ C由秩约束（15）和迹约束（11）与本质矩阵（10）的十个方程生成由于对极约束（12）给出了关于XL={f11， f12，f13，f21，f22，f23，f31，f32，f33}的线性方程，我们有XN={f}. 因此，在第二节中提出的战略150010005000-15-10-5 0Log10焦距误差（一）2000150010005000-15-10-5 0Log10焦距误差（b）第（1）款步骤2.1.3将首先消除未知的焦距f。为了计算消去理想If=I<$C [f11，f12，f13，f21，f22，f23，f31，f32，f33]的生成元，即不包含焦距f的元素，我们使用以下Macaulay 2[43]代码：R = QQ[f，f11，f12，f13，f21，f22，f23，f31，f32，f33];F =矩阵{{f11，f12，f13}，{f21，f22，f23}，{f31，f32，f33}};K =矩阵{{f，0，0}，{0，f，0}，{0，0，1}};E = K * F * K;I =子式（1，2* E*转置（E）*E- 迹（E*转置（E））*E）+理想（det（E））;G =消除（{f}，饱和（I，理想（f）dim G，degree G，mingens G输出告诉我们，G的簇的维数为6，次数为15，并且G是P8中两个超曲面的完全相交，被三次det（F）（17）和五次曲线f11f3f31+f2f21f23f31+f11f13f2f31+f21f3f31−f11f 13f3−f 21f 23f3+f 12f3f 32+f2f 22f 23f 32+图2. 数值稳定性：（a）f+E+f问题焦距相对误差的对数10;EI-fEf求解器（蓝色），Kukelova 08 [3]（红色）。(b)E+f问题; EI-Ef求解器（蓝色），Buj-nak 09 [39]（红色）。用两个新的未知数x和y参数化基本矩阵F（14）。将这个参数代入If的两个生成元（17）和（18）后，我们得到两个未知数x和y的两个方程（3次和5次）。通过求解这两个方程，我们得到了基本矩阵F的多达15个实数解。这两个方程中的两个未知数可以使用Syl v ester结式[1 0]或使用Gro¨bner基方法求解，该方法用于f+E+f问题的所有SOTA求解器。使用自动生成器[3]生成的这两个方程的Gr？bner基解算器对21×36矩阵进行G-J消元。该矩阵包含的非零元素几乎比最小的31×46 SOTA求解器[ 3 ]中的矩阵少3倍，该求解器也是使用自动生成器生成的，但对于三个未知量的十个方程的原始公式。这两个解算器的稀疏模式如Ap所示31312 313 13 2 22第五部分A.5.f12f13f23f32+f22f 23f32−f12f13f 31f32−f 12f 13f33−f11f 13f 31f2−f 21f 23f 31f2 -f12f13f3−f22f23f3实验32 3222 23232（十八）−f11f 13f33−f22f23f 31f32−2f11f13f21f23f33−2f12f13f22f23f33−f2f2f33−f2f2f33+f2f2f33+f2f2f33+ 2f11 f12 f31 f32 f33+由于f+E+f问题的新求解器在代数上等价于SOTA求解器，因此我们评估了新11 3121 3122 22f+E+f求解器仅适用于无合成噪声数据。2f21f22f31f32f33+f 12 f 32 f33+ f 22 f 32 f33。（17）和（18）的消失以及从基本矩阵[45]中提取未知焦距的方程（另见附录§A.3.2）完全描述了f+E+f问题。因此，我们可以得出以下结果。结果3.1（17）和（18）的零点集等于所有基本矩阵F的空间，即 奇异3×3矩阵，可分解为F=K−1EK−1，其中eK=diag（f，f，1），f ∈ C且E是本质矩阵.通过将该变量与由对极约束（12）给出的六个超平面相交，得到六个像点对应关系，我们获得了基本矩阵的多达15个实数解（见图1）。在我们新的f+E+f问题的有效在线求解器中，我们首先使用来自epipolar约束（12）的线性方程组，用于六个图像点对应，我们研究了基于第2.1.3节中提出的新消除策略的新f+E+f求解器（EI- fEf）在无噪声数据上的行为，以检查其数值稳定性。我们将其与S OT AG ro？bner基解算器Kukelova08 [3]的结果进行了比较。在这个实验中，我们生成了10000个合成场景，其中3D点随机分布在[-10，10]3立方体中 每个3D点由两个相机以随机但可行的方向和位置以及随机焦距fgt∈ [0. 5，5]。 图2（a）示出了通过选择最接近地面真值fgt的实根而获得的焦距f的相对误差的log 10。在新EI-fEf求解器的情况下，使用附录§A.3.2中给出的公式从计算的F中提取焦距f。然而，这里可以使用用于从F提取焦距的任何方法，例如基于SVD的方法[45]。新的EI-fFf解算器（蓝色）比Kukelova 08（红色）稳定性稍差。然而，这两个解算器都提供了非常稳定的解算器。Kukelova08（31x46）EI-fEf（21x36）Bujnak09（21x30）EI-fEf（6x15）4919你我在没有较大误差的情况下以及在存在噪声的情况下，它们的结果是可靠的，此外，新的求解器更小，更有效。1.2. E+f 6pt相对位姿问题第二个问题，我们使用新的消除策略解决的问题是估计的相对姿态的一个校准和一个焦距校准相机从六个图像点的对应关系，即.E+F问题最小E+f问题首先由Bujnak等人解决。[39]使用Gro¨ bner基和多项式特征值方法。他们的解算器在21×30上执行G-J消除矩阵和9×9矩阵的特征值计算。对于E+f问题，第一相机被校准到未知焦距，并且第二相机被完全校准。因此，本质矩阵和基本矩阵之间的关系具有以下形式：E=F K，（19）其中K=diag（f，f，1）是第一相机的对角校准矩阵，包含未知焦距f。通过将此关系代入本质矩阵（11）的迹约束，并设置Q=K K，我们得到2F Q F <$F − trace（F Q F <$）F = 0。（二十）SOTA求解器[39]使用第2.1.2节中的消除策略，并通过将极线约束（12）重写为Mf=0开始。然后，基本矩阵由两个未知数x和y参数化，如在f+E+f的情况下（等式2）。（14））。利用该公式，秩约束（15）和迹约束（20）导致三个未知数x、y和y中的十个三阶和四阶多项式方程。w=1/f2。这10个方程在[ 39 ]中是用Gr öbner基解算器[3]的自动生成器求解的。接下来，我们提出了一个新的解决方案，E+f问题，使用新的消除策略，从2.1.3节。消去理想公式我们从理想I∈C [f11，f12，f13，f21，f22，f23，f31，f32，f33，f]开始，由秩约束（15）和迹约束（11）的十个方程生成，其中基本矩阵（19）。对于f+E+f问题，在在线求解器中，用于六个图像点对应的极线约束（12）用于用两个新的未知数x和y（14）参数化基本矩阵F这种参数化，适用于四个发电机的消除理想IF，给出四个方程的程度三，四个两个未知数。我们使用Gr？bner基方法[3]在两个未知数中求解这四个方程。使用自动生成器[3]生成的Gr？bner基解算器对6×15矩阵进行G-J消去。该矩阵比SOTA求解器[ 39 ]中的消除模板矩阵小得多，其大小为21×30。实验研究了新的E+f消去理想的性质基于无噪声数据的求解器（EI-Ef），并将其与S OTAG ro？bner基求解器v erBujnak 09[3 9]的结果进行比较。我们生成了10000个合成场景，其中3D点均匀地从[-10，10]3立方体绘制。每个三维点由两个摄像机以随机但可行的方向和位置投影 第一相机的焦距从间隔fgt∈ [0. 5，5]并且第二相机的焦距被设置为1，即，校准第二照相机图2（b）示出了通过选择最接近地面真值fgt的实根而获得的焦距f的相对误差的log10。对于新的EI-Ef解算器，焦距f从com中提取使用附录§A.3.1中给出的公式计算F。新的EI-Ef解算器（蓝色）不仅更小，而且比Bujnak09 [39]（红色）更稳定。这两个求解器都提供了非常稳定的结果，没有较大的误差。1.3. E+f+k 7pt相对位姿问题我们将使用第2.1.3节中提出的新消除策略来公式化和解决的最后一个问题是估计一个校准相机和一个具有未知焦距和未知径向失真的相机的对极几何的问题，即，未校准的摄像头，带有径向失真。我们用E+f+k表示这个问题。径向变形的一个流行模型是单参数分割模型[46]。这是一个不失真模型，甚至可以处理非常明显的径向失真：X（λ）=。（二十一）对极约束（12）给出了X1={f11，f12，f13，f21，f22，f23，f13，f23，f33}。因此我们在这个模型中，xdi=[xdi ，ydi⊤[1]均质再次将仅消除未知的焦距F。计算消去理想的生成元If=I<$C [f11，f12，f13，f21，f22，f23，f31，f32，f33]，即对于不包含f的生成元，我们可以使用类似的Macaulay 2代码作为f+E+f问题，只需替换-测量（和径向失真）图像点，λ∈R是畸变参数。该模型用于[47]中提出的E+f+k问题的第一个7pt极小解对于E+f+k问题，极线约束读作：线E = K* F* K，线E = F* K。对于E+f问题，G的簇的维数为6xFx′uiui（λ）= 0， i = 1，. . . ，7，（22）4920在P8中为9次，定义为1立方和3其中xu，x′（λ）∈R3是齐次坐标Iui四次曲线（见附录§A.4）。对应的理想投影图像点，即，点4921不受径向失真的影响[1]。请注意，对于右摄像机，我们不知道摄像机校准参数，我们测量失真的图像点。因此，为了在对极约束中使用这些失真的图像点，我们首先需要使用模型（21）来消除它们的失真。极线约束（22）与迹线（20）和秩约束（15）一起形成相当复杂的多项式方程系统。注意，该系统中的所有方程都是非线性的，因此不能直接应用第2.1.2在SOTA求解器[47]中，首先通过手动消除一些未知数来简化该系统。首先，作者设置f33=1，这意味着他们的求解器在f 33 = 0的运动中失败。接下来，他们使用对极约束（22）用于六个图像点对应，以从方程中消除在对极约束中线性出现的六个未知量f11、f12、f21、f22、f31、f32。然后，对极线约束的剩余方程y23=f23λ，（24）y33= f33λ。（二十五）现在，（22）中的方程可以看作是线性齐次方程，12未知数f11，f12，f13，f21，f22，f23，f31，f32，f33，y13，y23，y33。关于这种线性化的另一种观点是，图像点被提升到4D空间，并且基础mas-mas-mas-F通过一列被丰富，.11f12f13y13F=F|f3λ=f21f22f23y23，（26）f31f 32f 33y 33其中f3是F的第3列。在文献[48]中引入了3×4基本矩阵F_（26），并称之为单侧径向畸变矩阵。利用该矩阵，对极约束（22）可以被写为：对于第七图像点对应，连同⊤ˆΣ′ ′′2′2Σ⊤+y迹线（20）和秩约束（15）形成如下系统：uiui（λ）=xuiFxdi，ydi，1，xdidi=0。（ 二十七）11个（一个二次，四个五次和六个六次）方程，四个未知数f13，f23，λ，w=1/f2。然后，再次手动简化方程。他们通过将11个输入方程乘以一组单项式来生成消除模板，使得所得方程中单项式的最大次数为8。产生的消除模板大小为200×231。该求解器的作者观察到，通过使用[ 3 ]中的自动策略或通过进一步减小消除模板大小，求解器的数值稳定性恶化。为了提高最终Gro¨bner基解的稳定性，作者进一步选择了40个单项式而不是必要的19个作为基选择.可以看出，E+f+k问题需要对输入方程进行非常仔细的手动操作，以获得数值稳定的求解器。然而，最终的求解器仍然相当大，在实际应用中并不真正有用。在这里，我们将表明，使用第2.1.3节中提出的新的消元策略，我们可以有效地解决这个问题，而不需要任何特殊的操作和处理输入方程。此外，使用这种新方法获得的最终求解器比SOTA求解器更有效且数值稳定[47]。消去理想公式不幸的是，对于E+f+k问题，对极锥straint（22）没有给出线性方程。因此，我们然而，在这种情况下，我们可以很容易地从极线约束（22）线性化方程。核线约束（22）包含单项式（f11，f12，f13，f21，f22，f23，f31，f32，f33，f13λ，f23λ，f33λ）.为了线性化方程（22），我们设置：y13=f13λ，（23）4922对于E+f+k问题，我们的方法是从由13个方程生成的理想I∈C [f11，f12，f13，f21，f22，f23，f31，f32，f33，y13，y23，y33，λ，f]开始的，即 来自约束条件（23）-（25）的三个方程、秩约束条件（15）和来自迹约束条件（11）的九个方程，其基本矩阵为（19）形式。这13个方程在我们的消去策略中形成来自（1）的集合FN在这种情况下，“提升的”对极约束（27）给出了3× 4径向畸变的12个基本矩阵F（2 6），即线性方程组XL={f11，f12，f13，f21，f22，f23，f31，f32，f33，y13，y23，y33}。因此，对于E+f+k问题，我们采用新的消去策略消去两个未知量：焦距f和径向畸变参数λ，即：XN={f，λ}。计算消去理想的生成元If ， λ=I<$C [f11，f12，f13，f21，f22，f23，f31，f32，f33，y13，y23，y33]，即不包含f和λ的生成元，我们可以使用与E+f问题类似的Macaulay 2代码。我们只需要将第一行替换为R = QQ[f，k，f11，f12，f13，f21，f22，f23，f31，f32，f33，y13，y23，y33];并在末尾Gu =消除（{k}，G +理想（y13-f13* k，f23-f23* k，f33-f33*k，））codim Gu，degree Gu，mingens Gu对于E+f+k问题，Gu簇在P11中的维数为7，次数为19. 除了形式为 fi3yj3−fj3yi3 的 三 个 二 次 曲 面 外，Gu 的理想生成元是两个三次曲面和九个四次曲面，即：共14个多项式。 虽然这个由14个多项式方程组成的系统看起来相当复杂，但它比SOTA [47]中使用的具有λ和f的原始系统更容易求解。492310008006004002000-15-10-50Log10焦距误差10008006004002000-15-10-5 0Log10径向畸变误差对于实际应用来说，重要的是新的EI-Efk求解器提供了非常稳定的结果，没有较大的误差，而对于SOTA求解器Kuang 14 [47]，我们观察到许多故障。E+f+k问题的噪声模拟实验结果见附录§§A.6。1.4. 计算复杂度(a)（b）第（1）款图3. 数值稳定性E+f+k问题：（a）焦距相对误差的Log 10（b）径向畸变相对误差的Log 10; EI-Efk求解器（蓝色），Kuang 14 [47]（红色）。用于七个一般图像点对应的tor包含单侧失真基本矩阵F的元素。这意味着，单方面的歧视-使用M的5维零空间，基本矩阵F可以由四个n维未知数x1、x2、x3和x4参数化，如F=x1F1+x2F2+x3F3+x4F4+F5。（二十八）将（28）代入消去理想If，λ的14个生成元中，得到4个未知数的14个我们使用Gr o¨ bner基方法[3]求解这些方程。使用自动生成器[ 3 ]生成的G ro？bner基解算器可对51×70mA进行G-J消元。该矩阵比SOTA求解器[ 47 ]中的消除模板矩阵小得多，其大小为200×231。此外，新的求解器不需要应用的方法，以提高数值稳定性的Gr o ¨bner基求解器，在[ 4 7 ]中使用。解决后14方程在四未知数x1，x2，x3，x4，我们用公式28重构F的解，用公式23重构λ的解，用附录§A.3.1中的公式重构f的解。实验我们首先研究了新的E+f+k的数值稳定性解算器（EI-Efk）对无噪声数据进行了计算，并将其与S OT AG ro？bner基解算器v erKuang的结果进行了比较14[47]。在这个实验中，我们以与E+f实验相同的方式生成了10000个合成场景，并且第一个相机中的图像点被遵循单参数划分模型的径向失真破坏。径向畸变参数λgt从区间[−0. 7，0]。图3（a）示出了通过选择最接近地面真值fgt的实根而获得的焦距f的相对误差的log10。图3（b）示出了通过选择最接近地面真值λgt的实根获得的径向失真λ的相对误差的log10。在这种情况下，新的EI-Efk解算器（蓝色）不仅明显小于SOTA Gro¨ bner基解算器v erKuang 14[47]（红色），而且明显更稳定。什么是真正在这里，我们展示了新的基于消除的求解器（EI-fEf，EI-Ef，EI-Efk）和SOTA求解器[3，39，47]的计算效率的比较。由于我们没有SOTA求解器的可比实现，我们比较了这些求解器执行的G-J消除（QR分解）的大小。G-J消元是所有求解器中最耗时的步骤之一。在选项卡中报告了尺寸的一致性。1.一、该表的最后一行显 示 SOTA 求 解 器 的 模 板 矩 阵 的 非 零 元 素 的 数 量（nzS）与我们的新的基于消除的求解器的模板矩阵的非零元素的数量（nzEI）的比率。f+E+fE+FE+f+kSOTA31×46[3]21×30[39]200×231[47]EI（新）21×366×1551×70nzS/nzEI35.22.8表1. 新的EI解算器比SOTA解算器小得多。线SOTA与EI（新）表明，聪明的求解器消除了更小的矩阵。他们操纵的数字也少得多。参见SOTA（nzS）与新（nzEI）求解器中非零数nz S /nz EI的比率。2. 结论我们提出了一个新的见解，最小求解器构造的基础上消除理论。通过消除单独的线性和非线性方程，并结合以后，我们能够产生比以前小得多的求解器，见表。1.一、我们还生成了一个有趣的新约束，方程。（18），在部分校准的相机对上。我们的方法首先是由利用我们的系统的线性方程（1）的想法，但我们也证明了它可以产生有效的求解器（第二节）。3.3）通过完全非线性情况的线性化。确认Z. Kukelova 得 到 了 捷 克 科 学 基 金 会 项 目 GACRP103/12/G 084的支持T. Pajdla得到了EU-H2020项目LADIO No.731970。J. Kileel和B. Sturmfels 得 到 了 美 国 国 家 科 学 基 金 会 （ DMS-1419018）和德国莱比锡马克斯-普朗克科学数学研究所的支持。Kuanng14（200x231）EI-Efk（51x70）Kuanng14（200x231）EI-Efk（51x70）4924引用[12] J. A.格鲁纳特 在erweit中的pothenotische问题ertergestal tnebstuüberseineanwendungeninder[1] R. Hartley和A.齐瑟曼。多视图几何计算机视觉剑桥，第二版，2003年。一、二、四、七[2] D. 是的。五点相对位姿问题的一个有效解IEEETransactions on Pattern Analysis and MachineIntelligence，26（6）：7562004年6月。 一、二[3] Z. Kukelova，M. Bujnak和T.帕杰拉最小问题求解器的自动生成器。在2008年的ECCV中，– 欧洲计算机视觉会议，计算机科学讲义第5304卷。Springer，2008. 一二三四五六七八[4] N. Snavely，S.M. Seitz和R.塞利斯基从互联网照片 集 建 模 世 界 。 International Journal ComputerVision，80（2）：189-210，2008. 1、4[5] D. Scaramuzza 和 F. 弗 劳 恩 多 夫 视 觉 里 程 计 [教程]。IEEE Robot.自动化麦格，18（4）：80-92，2011. 1[6] J. Hein
我的内容管理
展开
