巧妙消除模板系统的贪婪优化搜索方法

15754通过贪婪参数搜索优化消除模板*南乌拉尔国立大学martiushevev@susu.ru查尔斯大学MFF代数系j. gmail.comTomas PajdlaCIIRC -反恐组在布拉格pajdla@cvut.cz摘要本文提出了一种构造消元模板的新方法，我们首先构造一个特定的仿射参数化的消除模板系统的有限数量的不同的解决方案。然后，我们在参数空间上使用一种渐进的贪婪优化策略来得到一个小尺寸的模板。我们在计算机视觉中的34个最小问题 对于所有这些，我们发现与最先进的模板相比，模板的大小相同或更小。对于一些困难的例子，我们的模板是，例如，2.1，2.5，3.8，6.6倍。对于未知焦距的折射绝对姿态估计问题，我们已经找到了一个小20倍的模板。我们对合成数据的实验也表明，新的求解器是快速和数值精度。我们还提出了一个快速和数值精确的求解问题的相对姿态估计未知的共同焦距和径向失真。1. 介绍3D重建[49，50]和摄像机跟踪[46，55]中的许多任务导致解决最小问题[1，4，10，25，29，36，38，45，48，51]，其可以被公式化为多项式方程的系统。最先进的有效解决多项式系统的最小问题的方法是使用基于消除模板的符号-数值求解器[5，29，33]。这些求解器有两个主要部分。在第一个离线零件中，构造消除模板。该模板由从输入数据到（Macaulay）系数矩阵的映射（公式）组成。对于不同的输入通用（噪声）数据，模板是相同的在第二个在线阶段，共同-* 该 研 究 得 到 欧 盟 项 目 的 支 持RDFIMPACT 编 号CZ.02.1.01/0.0/0.0/15 003/0000468和EU H2020编号871245春天T. Pajdla就职于布拉格捷克技术大学捷克信息学、机器人学和控制论研究所。有效矩阵由特定问题的数据填充，通过Gauss-Jordan（G-J）消去法约简，并用于构造传递系统的解的虽然离线阶段不是时间关键的，但是在线阶段必须非常快地计算（主要在亚毫秒时间内），以用于基于RANSAC 方 案 的 鲁 棒 优 化 [16] 。 因 此 ， 构 建 模 板（即，Macaulay矩阵），这些矩阵尽可能小以使G-J消除快速。除了尺寸，我们还需要注意构建模板，以实现数值稳定的计算。1.1. 贡献我们开发了一种新的方法来构造消除模板，有效地解决最小的问题。首先，使用来自[33]的消除模板的一般基于合宿的参数化，我们构造模板的部分（但仍然足够通用）参数化。然后，我们在参数空间上应用贪婪启发式优化，以找到尽可能小的模板。我们证明了我们的方法在几何计算机视觉中的34个最小问题。对于所有这些，我们发现与最先进的模板相比，模板的大小相同或更小。对于一些困难的例子，我们的模板是，例如，2.1，2.5，3.8，6.6倍。对于未知焦距的折射绝对姿态估计问题，我们已经找到了一个小20倍的模板。我们对合成数据的实验也表明，新的求解器是快速和数值精度。我们提出了一个实用的解决方案，未知的公共焦距和径向畸变的相对姿态估计的问题所有以前提出的解决这个问题的方法要么是非常缓慢或数值不稳定。1.2. 相关工作消除模板是对从初始系统的多项式到构造动作矩阵所需的多项式的变换进行编码的矩阵了解一个AC-15755--⟨ ⟩∈\{}∈⟨ ⟩⊂联系我们⊂B∼− ∈ ⟨ ⟩∈这导致了波利诺河的显著加速B {∈}∈∈矩阵，系统的解决方案是从其特征向量计算。自动生成器（AG）是一种输入多项式系统并输出消除模板用于动作矩阵计算的算法。自动发电机：第一个自动生成器在[29]中构建，其中模板通过扩展初始多项式及其增加次数的倍数来迭代构建。该AG已被计算机视觉社区广泛用于为各种最小问题构造多项式求解器，例如，[6，7，31，37，43，48，59]，另见[33，Tab.1]中。文献[33]介绍了一种基于跟踪Gro¨ bner基构造和随后的基于合宿的约简的非迭代AG这个AG允许快速构建模板，即使是困难的问题。最近在[5]中提出了一种基于使用稀疏结式的替代AG。这种方法与[36]一起，是目前最先进的自动模板生成器。提高稳定性：从模板构造动作矩阵的标准方法需要执行其LU分解。对于大的模板，这种操作的-10导致显着的舍入和截断误差，因此数值不稳定。系列论文[9-11 ]解决了这个问题，并提出了几种通过在从模板构造动作矩阵的步骤上执行具有列旋转的QR分解。优化配方：选择一个适当的最小问题的公式可以大大简化寻找它的解决方案。文[30]提出了减少初始多项式系统中未知数对于某些问题，这种策略导致明显更小的模板[23，35]。优化模板：通过优化模板的构造步骤，加快了动作矩阵法的速度。论文[44]介绍了一种通过删除一些不必要的行和列来优化模板的方法。 该方法[28]通过将大型稀疏模板转换为所谓的单边界块对角形式来利用消除模板的稀疏性。这允许将初始问题分解为几个更小的子问题，这些子问题更容易解决。在文献[36]中，作者提出了两种显著减小消除模板大小的方法。第一种方法使用所谓的多项式理想的Gro¨ bnerfan构造模板w.r.t.商空间的所有可能的第二种方法从非标准基出发，引入了随机抽样策略来构造非标准基。优化求根：在实际应用中，复根对于大多数问题都是伪根。文[8]介绍了两种避免计算复变函数的方法发现对称性：某些极小问题的多项式系统可能具有隐藏的对称性。揭示这些对称性是优化模板的另一种方法。在[27，32]中，对最简单的部分p最近在[15]中调查了一个更普遍的案例。文[34]提出了一种处理具有（可能）无穷多个伪解子集的特殊多项式方程组的最相关的工作：我们的工作基本上是基于文献[5，11，33，36]的结果。2. 多项式系统的模板在这里，我们回顾解决多项式系统的有限个解决方案的作用矩阵的特征分解我们还展示了如何在计算机视觉中使用消除模板构建动作矩阵。我们建立在[9，12，13]的命名法上2.1. Grobner基与作用矩阵在这里我们介绍作用矩阵并解释它们是如何与G r？bner基相关的。我们用K表示一个域，X=x1，. . .，x k对于一个k个变量的集合，[X]对于X中的单项式的集合，K[X]对于K上的多项式环。设F=f1，. . .，f ∈K[X]，J=F.一个集合GK[X]是理想J的一个Gr？ bner 基， 如果J=G，且对每个f存在g G使得g d的主单项式等于f的主单项式。称Gr？bner 基 G 是 约 化 的 ， 如 果 对 所 有 g G ， c （ g ， LM（g））=11，且当g′g时，LM（g）不整除g′G的任何单项式.对于固定的单项排序（参见SM Sec. 7），对每个理想唯一地定义了约化的Gr o¨ bner基. 此外，对于任何多项式理想J，存在许多不同的约化Gr o？bner基，它们都可以使用J的Gr o？bner扇[36，42]找到。对于理想JK[X]，商环K[X]/J由等价关系fg下的所有等价类[f]组成当且仅当fg J.如果J=F是零维的，即，若F = 0的根的集合是有限的，则K[X]/J是有限维向量空间。此外，当计算多重性时，dim K[X]/J等于F = 0的解的数量[13]。若G是理想J的一个Gr？bner基G，则商环K[X]/J的标准（线性）基可以构造为G中所有不能被任何引导单项式整除的单项式的集合，即=b：LM（g）nb，gG.固定多项式aK[X]，定义线性操作，TorT a：K [X]/J → K [X]/J：[f] ›→[a·f].在K[X]/J中选择一个基，例如，标准的一个，允许将算子Ta表示为d×d矩阵，其中d=mial解算器。1我们用c（g，m）表示g在m处的系数。15756--BBBB∈ΣΣΣ⟨ ⟩BBBB}\B E\ RBMEMRMBΣ̸ΣΣiM（A·F）dimK[X]/J.这个矩阵，也用Ta表示，称为作用矩阵，多项式a称为作用多项式。作用矩阵可以用理 想 J 的 一个G ro¨ bner基G求出如下。设b1，. . .，bd是商环K[X]/J中的基. 对于给定的a，我们使用G来构造abi的标准形：一般情况下，由单项式表示的元素等价于标准单项式的（无限）许多不同的线性组合，因此提供（无限）许多不同的向量来构造（无限）许多不同的基。在下文中，我们假设单项基，即，由单项式表示的类组成的基G（abi）=ti jbj， i=1，. -是的-是的，d，J3. 构造行动矩阵T aw.r.t.：一旦选择了a和，就可以直接构造T a通过在SEC中描述的过程。2.1.然而，在计算机视觉中，多项式系统通常具有相同的支持。其中tij∈K。因此，我们有T a=（t ij）。2.2. 用作用矩阵作用矩阵对于计算具有有限个解的多项式系统的解是有用的 当（i）所有解pjKk，j = 1，. - 是的- 是的，d的重数为1，以及（ii）作用多项式A在解上评估为成对不同的值，即，a（p）=a（q）对于所有解pq。那么，作用矩阵Ta有d个一维特征空间，d个向量b1（pj） -是的-是的-是的bd（pj） 的多项式bi的解pj，i，j=1，. -是的-是的 ，d是d个特征空间的基本向量[12，p. 59号支柱4.7]。 有了一维特征空间，对于e，提取所有的溶液p，j。因此，经典方法端口的不同值的系数。然后，通过（i）使用在离线阶段设计的固定程序-模板-构建麦考利矩阵M，然后（ii）通过M的G-J消去在在线阶段产生Ta，来构造Ta是有效的[11，57]我们的主要客户，SEC。3、第二。4的方法是构造Macaulay矩阵的一种有效途径。4. 计算特征n个向量vj，j=1，. -是的-是的，dofTa：当存在d个一维特征空间时，计算Ta5. 从特征向量中恢复解：为了找到解，只需计算所有未知数x l，l=1，. -是的-是的 ，k，在解p， j 上。 它可以通过在标准基bi中将未知数xl写成xl=clibi.那么，xl（pj）=iclibi（pj）=icli（vj）i，其中（vj）i是求具有有限个解的多项式系统F的解的方法如下。1. 选择一个作用多项式a：假设解pj的重数为1，i。例如，理想的J=F是自由基[13，p.253 Prop. 7]，我们的目标是选择a，使得它具有两两不同的值a（pj）。通过选择a=x，这是可能的，即，一个变量，在坐标线性变化后[12，p.59]。正如我们将看到的，这样的选择导致了一个简单的解决方法。在计算机视觉中，我们对求解由两组方程F=F1<$F2组成的多项式系统特别感兴趣，其中F1不依赖于向量vj的 第i个 元 素。2.3. 麦考利矩阵及消去模板现在让我们介绍麦考利矩阵和消元模板。为了简化构造，我们仅限于以下假设：（i）基的元素由单项式表示，以及（ii）作用多项式a是单项式且a为1。给定多项式F =（f1，. - 是的- 是的，fs），设[X]F是F中所有单项式的集合. 设[X]F的基数#[X]F为n。则Macaulay矩阵M（F）∈Ks×n有系数c（fi，mj），其中mj∈[X]F，在图像测量（例如，Demazure对本质矩阵[14]）和F2取决于图像mea。（i，j）元素：M（F）ij移位=c（f i，m j）.f是f的单倍，受随机噪声影响的确定（例如，基本矩阵上的线性核线约束[39]）。然后，坐标的线性变化可以在离线阶段中仅进行一次以变换F1。接下来，我们将假设存在解p j上具有两两不同值的a。2. 选择K[X]/J的一个基：有无限多个K[X]/J的基。我们的目标是选择一个基础，导致一个简单的和数值稳定的解决方法。元件的是由单项式的K-线性组合的多项式表示的等价类。因此，最简单的基由表示的等价类组成的monomials。 重要的是K[X]/J具有标准多项式m∈[X]. 设A =（A1，. - 是的- 是的，A s）是单项式A j∈ [X]的集合的s -元组。我们定义F的位移集为：A·F={m·fj：m∈Aj，fj∈F}.（1）设B是商环K[X]/<$F<$的单项式基，a是作用单项式.集合B，R={a b：b∈得双曲正弦值.=[X]A·F（）是基本的集合，[11]《易经》中的“易”字和“易”字，都有“易”字。定义1. 设B=B <$[X]A·F。一个列按有序块排列的Macaulay矩阵M（A·F）=对于Fw.r.t.a如果下列条件成立：叫做排除模板[12，53]对于每个约化的Gr？ bner基。在15757BΣBBBB BB^^XΣ·B0 00MEMRMBM′=MEMRM′这显然也是一个模板。知道矩阵H就足以构造一个消除-ΣGΣΣGΣ^^^^1. [X]A·F;2. M（A·F）的约化列梯形为∗ 0 ∗M（A·F）=0IMB，（2）3. 构造参数化模板设是K[X]/J的单项式基。我们区分了标准基和非标准基，标准基来自J的一个givenGr？bner基，非标准基可以由[X]中的任意单项式表示。给定一个多项式f∈K[X]，令[f]=ici[bi]，其中bi∈B且ci∈K，其中n表示具有任意元素的子矩阵，0是[f]在基B中的唯一表示。然后多项式icibi称为f w的标准型。r. t.BBm在#R阶的矩阵上，并且MB是大小为#R×的矩阵并由f表示。让我们固定动作单项a，#B.定 理 1. 消 除 模 板 定 义 明 确 ， 即 ， 对 于 多 项 式 F=（f1，. . .，fs）使得理想的f∈F ∈是零维的，则存在一组移位（）a v（ ）B，即，每个向量的标准形式阿比岛如果是对应于一个Gr？bner基G的标准基，标准形w.r.t.是以多项式除后的唯一余数的形式直接找到的A·F满足定义1的条件。证据 参见SM Sec. 8.来自G的MIals，即，a v（B）B =a v（B）G=TTa ∈Kd×d是作用矩阵。v（B），其中在SM Sec. 9，我们提供了几个用消元模板求解多项式系统的例子。2.4. 消除模板现在，考虑一个任意的（可能是非标准的）ba-姐构造一个v（）w.r.t.，我们选择一个理想J的Gr？bner基G，并找到相关的（标准）基B^。然后，我们得到v（B）=Sv（B^）。因为B是a基，方阵S是可逆的。我们也可以-现在我们将解释如何构造动作矩阵从消除模板。⊂普特Gav（B^）=T^av（B^），其中T^a∈Kd×d 是矩阵给定一个有限集合A K[X]，设v（A）表示向量由A的元素组成。如果A是一组单项式，则v（A）的元素由[X]上所选择的mono-mial排序来排序。对于一组多项式，v（A）中元素的阶是无关紧要的。设a∈[X]是一个作用单项式，M（A·F）=标准基B中的操作符。 然后，我们有a v（B）B=Ta v（B），其中Ta=S Ta S−1是以下矩阵：B中的操作符。V=a v（B）−Ta v（B）（5）和计算a.简称M=M（A·F）和X=[X]A·F，GGGG对应于M的列的单项式的集合。由于M是Macaulay矩阵，Mv（）= 0表示展开的方程组。B=B <$XB，参见SM中的实施例1和4让我们构造矩阵V=Sa·（S−1v（B） ）−Ta S−1v（B）=S a v（B） −T a v（B）=0。因此，向量V的元素属于J。在那里-因此，存在矩阵H∈K[X]d×s，使得M′通过将对应于以下的零列添加到ea cBhb∈B\B。将nB，h模板M转换为V= Hv（F）。（六）因此，M ′的约化rBow梯形必为（2）式.因此，我们得到了v（R）=−M′v（B）。（三）根据定义1的F的tion模板。方程（6）可以改写为形式V=kh k f k，其中h k是H的第k列设[X]k是hk的支集，A=（[X]1，. . .，[X]s）和A·F是相关移位集。为了给作用矩阵提供一个明确的公式，让基本单项式 的 集 合 B 被 划 分 为 B=B1<$B2 ， 其 中 B2<$={a<$b ：b∈B}<$B且B1=B\B2。然后然后，麦考利矩阵M（A F）是F的消去项，见SM Sec.8.现在，我们讨论如何构造矩阵H，v（B）=如下所示：让我们定义是适当大小的零矩阵，I是单位元成为Fw.r.t.的淘汰模板一15758v（B1）v（B2）行动矩阵可以解读为这（6）是真的。如[33]中所述，这种矩阵不是唯一定义的，反映了构造消除模板。一个这样的矩阵，比如H，可以是B-M-0002哪里Ta=B、（四）P发现作为一个副产品的格罗布纳基础计算。2在实践中，矩阵H0可以通过使用P是二进制矩阵，即，矩阵由0和1，使得v（B2）=Pv（B）。格罗布纳基计算命令，例如，ChangeMatrix=>true在Macaulay2 [18]或输出=在Maple中扩展。15759∈∈ΣΣ×∈∈W∈ E∈ W∈ EWE−另一方面，有一个简单的算法来计算任何有限多项式集的第一合合模的生成元[12]。对于多项式F的s元组，该算法输出矩阵H1K[X]l×s，使得H1v（F）=0。让H=H0+ΘH1，（7）10.80.60.40.203 4 6 9 11 15 16 18最小的问题22 25 28其中Θ是d参数θij的l矩阵K. 我们将与矩阵H相关联的消去模板称为参数化消去模板。我们注意到，由于矩阵H1的行生成合合模，公式（7）将给出方程（1）的完整解集。（6）证明了θijK[X]。然而，在本文中，我们仅限于更简单的情况θijK.通常，参数化模板可以非常大。在下一节中，我们提出了几种减少它的方法。4. 减少模板4.1. 通过贪婪搜索在（7）中定义的矩阵H的第k列可以写为hk=Zkck。其中Zk是第k个系数矩阵，其元素是参数θ ij中的仿射函数，ck是相关单项向量r。 设W=Z1。. . Zs。矩阵W的列与扩展系统中的多项式的移位一一对应，并且因此与消除模板的行一一对应。因此，模板减少的问题导致调整参数的组合优化问题，其目的是最小化W中的非零列的数量。下面我们提出两个启发式策略来处理这个问题。我们称第一种策略为“逐行”，因为它倾向于移除模板的行。第二个策略是首先，我们注意到，如果矩阵W的一列包含一个非零标量的条目，那么这一列不能通过调整参数来归零。因此，我们进一步假设所有这样的列都从W中移除。逐行减少：设wk为矩阵的第k列W. 将矩阵W的一列归零意味着解出线性-图1.我们的调整策略（Our）与[33]（Syzygy）中基于syzygy的减少的比较。我们还显示了缩减之前的初始模板的大小（无缩减）。每个箱形图表示100个随机选择的标准单项碱基的归一化模板大小的分布。每个基的动作变量也是随机的。问题编号与选项卡中的相同。1和Tab。二、每个e，我们表示为e是W的列的子集，使得相应的移位包含e。对于每个e，我们为e分配得分σ（e），这是通过对所有we求解w=0而归零的列数。我们的列式贪婪策略意味着，在每一步，我们将e中对应于具有最大得分的多余单项式e的当σ（e）>0时，至少有一个e。列策略更快，因为它在每一步都将矩阵W的几列归零另一方面，行策略在某些情况下输出较小的模板我们的自动模板生成器尝试这两种策略，并输出最小的模板。在图1中，我们在几个最小问题上比较了我们的调整策略与[33]中的模板约简方法。图中的每个箱形图表示对应于随机选择的单体排序的100个标准单体碱基每个基的动作变量也是随机的。每个问题的问题实例都相同（已修复）。为了可见性，我们还在应用任何缩减之前显示参数化模板的大小。在大多数情况下，我们的归约方法产生的消元模板较小. 可以看出，对于某些情况，基于合朔的约简产生模板，大于参数化模板。4.2. 舒尔补约化1.提案设M是以以下块形式耳方程w k=0.由于W的每一行都有自己的集合，ABC D其是通过求解wk=0而被归零的列的数目。我们的逐行贪婪策略意味着，在每一步中，我们都将具有最大得分的列归零。我们继续进行，当σ（k）>0时，至少有一个k。逐列还原： 让 是过度的集合参数化消除模板的单项式。为其中A是一个可逆方阵，它的列对应于一些多余的单项 式 。 然 后 A 的 Schur 补 集 ， 即 ， 矩 阵 M/A=DCA−1B，也是一个消除模板。证据 参见SM Sec. 10个。归一化模板大小对于参数，求解wk=0分为求解d个单一方程。对于每个k，我们将得分σ（k）分配给wkM=、（8）15760ΣΣ----∗××BBB −B在实践中，Prop。1可以如下使用 设多项式集合F= f1，. - 是的- 是的 ，fs包含一个子集，设Fs = f1，.- 是的- 是的 ，fk，使得（i）所有来自Fk的多项式都是稀疏的，即， 由一个相对较少的条款，和（ii）系数多项式从F是不变的所有情况下的问题。 这样的多项式可以出现，标准化条件下设F的消去模板M以块形式（8）表示，其中子矩阵AB对应于多项式从F的移位，矩阵A是正方形且可逆的，其列对应于一些多余的多项式，并且其条目对于问题的所有实例都是相同的。然后，以prop。1.用Schur补M/A代替M，可以安全地降低模板。由于来自F的多项式是稀疏的，所以（8）中的块A和B因此，矩阵M/A的非零元素是M的元素的简单（多项式）函数，可以很容易地离线预先计算。舒尔补约简允许我们为一些最小的问题显着减少模板，见表1。1和Tab。下面2个。4.3. 删除相关行和列第二个提案 设M ′′是一个大小为s′′×n′′的消去模板，其列按w.r.t.分区E <$R <$B。 则存在一个大小为s× n的临时层M，使得s≤s′′，n≤n′′且n-s=#B。证据 参见SM Sec. 11个国家。通过Prop.2，给定一个消除模板，比如M"，我们总是可以选择线性无关行的最大子集，并从M“中删除所有剩余的（相关）行。结果是消除模板M′。类似地，我们总是可以选择对应于多余单项式集合的线性无关列的最大子集，并从M′中移除对应于多余单项式的所有剩余列这是通过两次应用G-J消去法来实现的5. 实验在本节中，我们将在两组最小问题上测试我们的模板生成器第一个问题包括文献[33]、[36]和[5]中的21个问题。它们提供了最先进的模板生成器，分别由Syzygy、Be- yondGB和SparseR表示第一组问题的结果见表1。1.一、第二组由12个在[5，36]中没有提出的附加问题第二组问题的结果二、下面我们就来谈谈Tab。1和Tab。二、1. 列列2.标记为的模板采用Subsect方法进行约简。四点二。相关的极小问题公式包含一个简单的稀疏多项式与（几乎）所有的常系数。例如，问题#25和#26的公式包含四元数归一化约束x2+y2+z2+σ2=1，其中x，y，z未知，σ值已知. 通过构造相应块的舒尔补，可以安全地从模板中消除该方程的所有倍数。3. 问题#3的多项式方程是从6 × 9矩阵的零空间构造的。我们使用由G-J消去法构造的零空间的稀疏基，4. 找到了问题#8的39 95消除模板w.r.t.作用变量λ的倒数表示径向畸变，即，式（5）中的向量V定义为V=λ−1v（）T λ−1v（），其中非标准基由可被λ整除的单项式组成。在论文[11]中，该集合构成了冗余的求解基，因为它由56个单项式组成，而问题#8的解的数量是52。四个虚假的解决方案可以通过去除具有最差值的解决方案来过滤掉使用归一化残差。5.问题#15的初始公式由5个变量中的5个3次多项式组成：3个旋转参数和2个相机中心坐标。如[5]中所建议的，我们首先在相关的Macaulay矩阵上使用G-J消元来简化这些多项式之后，5个多项式中的2个其余3个多项式 线 性 依 赖 于 相 机 中 心 变 量 。 We used 2 of thesepolynomials to solve for the camera cen- ter and thensubstitute the solution into the third polynomial resulting inone additional polynomial of degree 4 in 3 rota- tionvariables only.因此，我们的问题的公式由3个变量的3个多项式组成：1个4次多项式和2个2次多项式。重要的是要注意，（i）4次多项式的系数是线性的（并且很容易）表示为3个初始多项式的系数，（ii）这种消除过程不会引入任何伪根。 我们还注意到这个问题具有以下2重对称性：如果x、y、z是凯莱变换表示的旋转参数，则替换x→y/z，y→ −x/z，3我们使用了软件ware包Gf an [21]来计算Gro¨ bnerf ans。15761-→ −#问题[36]第三十六话[33]第五届全国政协副主席、全国政协委员、全国政协委员1Rel. poseF +λ8pt [26]8 11× 197×1511× 19 11× 197×157× 162Rel. poseE +f6pt [6]911×20 11×2021× 3011×20 11×20 11×203Rel. posef +E+f6pt [52]，[29]15 12× 2711×2631× 46 31× 46 21× 40 12× 304Rel. poseE +λ6pt [26]26 34× 6014×4034× 60 34× 6014×4014×405拼接fλ+R+fλ3pt [44]18 48× 6618×3648× 66 48× 6618×3618×366ABS. pose P4P+fr [7]1652×68 52×68 140× 156 54× 70 54× 7052×687ABS. pose P4P+fr（el.（f）[35] 1228×40 28×40 28×40 28×40 28×40 28×408Rel. poseλ +E+λ6pt [29]52 73× 12539×95 149× 201−53× 10539×959Rel. poseλ1 +F+λ29pt [29]2476×100 76×100165× 189 87× 111 87× 111 90× 11710Rel. poseE +fλ7pt [26]1955×7456× 75 185× 204 69× 88 69× 88 61× 8011Rel.姿态E+fλ7pt（el. λ）[5]19 37× 5622×4152× 71 37× 56 24× 4322×4112Rel.姿态E+fλ7pt（el. fλ）[30]1951×70 51×70 51×70 51×70 51×70 51×7013[48]第四十八话847×55 47×55 47×55 47×55 47×55 47×5514三角测量（sat. im.）[59个]2787×114 87×11488× 115 88× 115 88× 11587×11415ABS. [19]第十九话1657×73 57×73 240× 256 112× 128 199× 215 68× 9316ABS. [25]第二十五话2065×8566× 86 169× 189−68× 88 68× 9217不同步rel. pose [2]16 159× 175139×155159× 175−299× 315 150× 16818[20]第20话2787×114 87×11488× 115 88× 115 88× 11587×11419[43]第43话最后一句40118×158 118×158 118×158 118×158 118×158 118×15820最佳姿势2pt v2 [54]24139×163∗141× 165∗192× 216−192× 216 176× 20021Rel. [37]第37话：我的世界2099×119∗99×119∗246× 276−183× 249−表1.我们的测试最小问题的消除模板的比较。我们遵循[5，36]中的符号来命名问题。列最小模板以粗体显示，小于最新技术水平的模板以蓝色粗体显示，符号““表示缺失模板，d是商空间的维度，：采用Subsect. 四点二。#问题我们[33]第三十三话22Rel. poseλ +F+λ8pt [29]1631×47 31×4732× 48 32× 4823P3.5P+局灶性[58]1018×28 19× 29 20× 43 20× 3024P4P+量表[56]847×55 47×5548× 5647×5525Rel. poseE +angle 4pt v2 [41]2016×36∗16×36∗16×36∗36× 5626Gen. rel. [41]第41话：我的世界4437×81∗37×81∗37×81∗317× 36127Rel. 姿势E+fuv+角度7pt [40]13×3219× 326 46× 52 40× 46 66× 7228卷帘门R6P [3]11× 2014×2020120×140 120×140196× 216 204× 22429[54]第54话：我的世界28134×162∗144× 172∗280× 252 203× 23130[54]第54话：我的世界48 397× 445∗385×433∗1260× 1278 544× 59231L2三视图三角形。（放松）[31]31217×248281× 312 274× 305 231× 26232屈光性P6P+局灶性[19]36126×162178× 214 648× 917 636× 65433Rel. posefλ +E+fλ7pt [22]68209×277255× 323 886× 1011 581× 65934Gen. rel. [24]第二十四话140144×284 144×284−144×284表2.我们的测试最小问题的消除模板的比较。列我们遵循[33]中的符号来命名问题最小模板以粗体显示，小于最新技术水平的模板以蓝色粗体显示，符号表示缺失的模板，d是商空间的维数，m：通过Subsect方法约简模板四点二。z1/z保持多项式系统不变。因此，该问题具有不超过8个6. 问题#27最初是通过对手动饱和多项式理想应用四个G-J消去的级联来解决的我们将原始求解器标记为粗体，因为它比新的单消元求解器快（0.4 ms，0.6ms）。7.问题#32的初始公式由6个变量的6个4次多项式组成：3个旋转参数，2个相机中心坐标和焦距。与我们对问题#15所做的类似，我们首先使用相关Macaulay矩阵的G-J消元来简化这导致4个方程中的4个未知数：1次多项式15762××ΣΣ×- ≤≤5、2个3度和1个2度。与问题#15的情况我们还注意到，该问题具有4重对称性，这意味着其“本质上不同”的根的数量因此，可以进一步减少这个问题的模板0.30.250.20.150.10.050-15-10-5 00.30.250.20.150.10.050-15-10-5 08.新AG的实施，以及作为Matlab解决所有 最小可能标签：Tab 1和Tab。2，可在www.example.com上获得http://github.com/martyushev/EliminationTemplates。在SM Sec. 13，我们测试我们的求解器的速度和数值稳定性。5.1.具有未知焦距和径向畸变的对于具有未知但固定焦距和径向畸变的相机的相对位姿估计问题，可以从两个视图中的七个点对应最小地解决。在文献[ 22 ]中首次考虑了这一问题，在文献[22]中将其表述为12个多项式方程的系统：1个2次方程，1个3次方程，2个5次方程，3个6次方程和5个7次方程。5个未知数是：[17]中除法模型的径向畸变参数λ，焦距f−2的倒数平方和基本矩阵F的三个元素F32，F13，F23。相关的多项式理想具有68次，这意味着该问题通常有68个解。我们从同样的问题出发如原文[22]。我们没有设法在合理的时间内（大约24小时）构造出相关多项式理想的Gr？ bnerfan 相反，我们随机抽取了1,000个加权单项式序，使得相应的约化Gro¨ bner基都是不同的。我们避免了一个条目比其他条目小得多的权重向量，因为这样的权重的单项排序通常会导致显着更大的模板。我们还利用[36]中的随机抽样策略构造了500个条件环然后，我们使用我们的自动生成器为所有的碱基（标准和非标准）和所有的动作变量构建消除模板。我们用这种方法找到的最小的模板尺寸是209277.它对应于加权单项式排序的标准基，其中f−2>F32>F13>F23>λ和权向量w=135819810768磅操作变量为λ。基于尺寸为886 1011的消除模板的论文[22]中的求解器不可用。然而，论文中报告的结果假设[22]中的求解器比我们的求解器慢得多（400 ms对8.5 ms），而两个求解器都表现出相当的数值精度。基于AG从[33]生成的581 659模板的求解器几乎比我们的求解器慢两倍（约16 ms）。而且（a）f = 0。5，λ = −0。1（b）f = 2，λ = −0。20.30.250.20.150.10.050-15-10-5 0(c) f = 1，λ = −0。图5 （d）f = 3，λ = −0。9图2.问题#33的相对误差分布。在104次试验中，对不同的焦距f和径向畸变λ值进行了2次试验为了进行比较，我们还添加了由[47]中最先进的（SOTA）求解器获得的λ解算器[33]它是不稳定，需要额外的稳定性改进技术，例如，列旋转[11]。因此，我们将我们的求解器与最近论文[47]中唯一公开可用的最先进的求解器进行了比较。我们对由两个相机观察的七个点组成的场景进行了建模，其中两个相机具有未知但共享的焦距f和径向失真参数λ。第一摄像机中心与场景之间的距离为1，场景尺寸（w×h×d）为1×1×0.5，基线长度为0。3 .第三章。我们通过构造无噪声图像数据上焦距f、径向畸变参数λ和基频F的相对误差分布来测试我们的求解器的数值精度。我们只保留满足以下“可行性”条件的根：（i）f −2是实数;（ii）f −2 > 0 ;（iii）1λ1.一、不同f和λ值的结果如图所示。二、我们的求解器失败了（即，没有发现可行的解决方案）。[ 47 ]中求解器的平均运行时间为2。9毫秒，这几乎是 我们 的求解器 的执行 时间的三 分之一 （8.5ms）。然而，我们注意到[47]中求解器的主要部分是用C++编写的，而我们的算法完全在Mat- lab中实现。这为进一步加快求解器的速度提供了空间6. 结论我们开发了一种新的方法，用于构造小而稳定的消除模板，以有效地解决最小问题的多项式我们为许多最小问题提供了最先进的模板，并为更难的问题提供了实质性的改进。0.30.250.20.150.10.050-15-10-50频率频率频率频率15763引用[1] SameerAgarwal ， Hon-LeungLee ， BerndSturmfels和Rekha R Thomas，关于对极矩阵的存在性，国际计算机视觉杂志121（2017），第3号，403-415。1[2] CenekAlbl ， ZuzanaKukelova ， AndrewFitzgiant ， Jan Heller ， Matej Smid 和 TomasPajdla，关于非同步相机的双视图几何，IEEE计算机视觉和模式识别会议的4847-4856. 7[3] Cenek Albl，Zuzana Kukelova和Tomas Pajdla，R6p-滚动快门绝对相机姿势，IEEE计算机视觉和模式识别会议论文集，2015年2292-2300. 7[4] Daniel Barath和Levente Hajder，从两个仿射对应中 有 效 恢 复 基 本 矩 阵 ， IEEE Transactions onImage Processing27 （ 2018 ） ， 第 11 期 ， 5328-5337。1[5] SnehalBhayani ， ZuzanaKukelova 和 JanneHeikkila，一种基于稀疏结果的高效最小解算器方法，IEEE/CVF计算机视觉和模式识别会议论文集，2020年，pp.1770-1779. 一、二、六、七[6] Martin Bujnak 、 Zuzana Kukelova 和 Tomas Pa-jdla，从具有单个已知焦距的图像集合进行3d重建，2009年IEEE第12届国