基于GPU的同伦延拓算法在计算机视觉中的应用与优化

15765基于GPU的同伦延拓算法在计算机视觉布朗大学工程学院chien@brown.edu埃利亚斯·齐加里达斯范弘毅工程布朗大学弘毅fan@brown.edu斯塔尼米尔·托莫夫Ahmad Abdelfattah创新计算实验室田纳西大学ahmad@icl.utk.edu本杰明·基米亚INRIAaridas@inria.fr田纳西大学创新计算v@icl.utk.edu布朗大学工程学院benjaminkimia@brown.edu摘要多项式方程组在计算机视觉中，特别是在多视图几何问题中经常出现用于求解这些系统的传统方法通常旨在消除变量以达到单变量多项式，例如，用于5点姿态估计的十阶多项式，使用巧妙的操作，或者更一般地使用Grobner基础、结果和消除模板，导致用于多视图几何和其他问题的成功算法。然而，当问题复杂时，这些方法不起作用，并且当它们起作用时，它们面临效率和稳定性问题。同伦延拓（HC）可以解决更复杂的问题，而没有稳定性问题，并保证全局解，但它们被称为是缓慢的。在本文中，我们表明，HC可以在GPU上并行化，在多项式基准测试中显示出高达56倍的显着加速。我们还表明，GPU- HC可以通用地应用于一系列计算机视觉问题，包括四视图三角剖分和三焦点姿态估计与未知的焦距，这不能解决与消除模板，但他们可以有效地解决与HC。GPU-HC为一系列计算机视觉问题的简单公式和解决方案1. 介绍由于透视投影是一种代数模型，多项式方程组在计算机视觉中，特别是在多视图几何问题中经常出现。例子比比皆是，包括绝对姿态估计[35，92，5]，相对姿态估计[75，86，52]，单应性估计[54， 14]，Pestival [94 ，95]，3 视图三角测量[17]，卷帘快门相机绝对姿态估计[4]以及许多其他方法。挑战在于如何以稳定的方式有效地解决这些多项式系统。经典的相对姿态估计5点算法[78，75]就是一个很好的例子。它的公式开始于15个未知数的15个方程，即10个深度和5个姿态参数。传统的方法是消除深度，并最终得到极线方程，该极线方程具有5个点，导致10次单变量多项式，从该多项式确定姿态一个更正式的方法来消除变量是Gr？ bner基础[21，22]或结式[21，22]。消除模板被开发为自动求解器生成器[59]，其中从一个输入中获得的基于Gr？ bne？的消除策略被“记住”用于未来的这些方法在第2节中进行了审查。上述方法的挑战在于，它们仅限于具有少量解决方案的问题。对于可以计算消除模板的较大问题，它们的速度很慢。对于更大的问题，消除模板的计算超过了实际资源，使问题无法解决。此外，在将聚乙烯系统转化为聚乙烯系统的过程中可能会出现单变量多项式的多项式，例如，[71、70]。同伦延拓方法，相比之下，可以解决非常复杂的多项式系统。其基本思想是找到一个起始系统的所有解，然后将它们不断演化为目标系统的解。他们可以确保，以概率1，找到所有的解决方案[84，91]，提供了一个它们还避免了符号方法的稳定性问题，因为它们不操纵15766输入多项式它们的复杂性取决于它们遵循的解决方案（轨道）的数量。这就是使用GPU来加速计算的想法。GPU已被用于计算机图形和计算机视觉，以加速大规模并行操作。关键是HC是否可以并行化以利用GPU中的许多处理器，同时避免存储器之间的数据传输延迟。HC过程由从启动系统到目标系统的连续过程中的预测和校正步骤组成。这是通过计算雅可比矩阵来预测下一步的走向，然后用牛顿我们表明，通过并行化的预测和correc- tion步骤中的计算，一个轨道可以实现一个GPU的翘曲这在一定程度上是通过在MAGMA库中建立核融合来解决批量线性系统而实现的。此外，同伦雅可比矩阵的表达式是齐次化的，因此它们的求值可以以单指令多线程（SIMT）的方式并行化。涉及多项式系统的计算机视觉问题符合这些要求。我们已经将GPU-HC应用于各种问题，并发现对于中等复杂的系统和超越GPU-HC提供了显着的节省（具有隐含的稳定性）。我们还探讨了两个问题的解决方案，即四视图三角剖分和三焦点姿态估计未知的焦距，没有在文献中探讨。这些都是作为例子介绍的情况下，消除模板未能产生的解决方案，但GPU-HC解决有效。因此，本文的基本论点是GPU-HC可以应用于所有多项式系统的计算机视觉问题，并产生有效和稳定的解决方案。2. 多项式系统我们将求解多项式方程组的算法大致分为三类：（i）依赖于代数消元工具的符号方法，如G ro¨ bner基，结式等。（ii）数值求解器是迭代的，通常是牛顿法的一种变体，如同伦延拓，以及（iii）混合方法，结合了符号和数值求解器的优点，符号求解器然后使用专用算法如Sturm或Descartes计算根，并用于恢复系统解决方案，例如。，[21，22，82，28].这些算法主要依赖于有理数的精确计算，使用诸如Gr？bner基和结式之类的工具进行消除。格罗布纳基“递增地”操作多项式符号方法被广泛用于解决计算机视觉中的最小问题[49，48，31，85，40]。他们总是输出准确的结果，成功和有效地处理退化，如多重根。然而，符号算法的有效实现远不是一个简单的任务，并且超过5-6个中等程度的变量的系统不能容易地处理，除非稀疏性和结构被特别利用。此外，我们离使用符号求解器在毫秒内解决中等系统还很远另一个主要问题，特别是Gro¨bner基，是数值上不稳定的[50，70]。这主要是由于当输入多项式的系数是浮点数或已知达到一定精度时，引起不稳定的项排序为了解决这个问题，我们需要付出更多的努力[71]。数值求解器几乎完全是迭代算法，利用牛顿算子的变体，在浮点运算中执行计算[9，84，91]。基于数值线性代数技术的方法，主要是特征值计算[11，16]，也属于这个家族。最突出的代表是同伦连续（HC）算法[7，8，20，41，91，39]。它依赖于一个简单而优雅的想法，首先解决一个简单的多项式系统（开始系统），然后将其根变形为我们想要解决的系统（目标系统）的根。在选择一个易于求解的启动系统时需要注意，该系统的解至少与目标系统的解一样多。HC可以处理非常大的问题，特别是在没有退化的情况下，比如多根，并且能够处理超出范围的系统象征性的解决者。HC广泛用于计算机视觉，特别是多视图几何中的最小问题[51，79，68，26，29，25]。然而，HC相对较慢，是其广泛采用的严重瓶颈。在HC算法中也可能出现数值问题，特别是如果系统的雅可比矩阵是病态的，并且在许多情况下我们需要使用双精度浮点运算，例如。，[9]。然而，HC是一种继承的数值方法，不需要精确的输入。有时候，即使有可能，也不容易找到好的，更不用说最优的启动系统，输出的基数并不总是正确的，需要额外的验证步骤。然而，它们通常比符号方法更容易实现，即使在所有情况下，有效的软件需要大量的时间，精力和努力才能有效解决现实生活中的问题。混合求解器旨在结合符号和数值方法[27，70，67]，并且它们具有各种算法变体。计算机视觉领域的一个众所周知的方法是消除模板，或自动求解器生成[55，56，60，64，59]。其主要思想是保留消去法（通常为Gro？ bner基）算法对一个输入执行的步骤，并将这些步骤应用于15767∈DTXXx×任何其他输入。他们在离线阶段用有限域上的“虚拟”系统的随机系数生成消除的“模板”。然后通过本征值计算得到的解决方案。该方法特别适用于求解低阶和低变量数的系统[80，19，93，61，4，23]。尽管如此，即使它们在某些问题上相当成功，它们可能需要处理非常大的矩阵[59]，这在计算上是难以处理的。此外，分析它们的稳定性绝非易事。可以进行几次预先计算来克服不稳定性问题;可惜的是，最后他们必须用一个矩阵来计算，类似于格鲁布纳基和结式，其维数至少为 条件-这类矩阵的根数研究得并不多，也不清楚它们是否能处理≥300个根的问题3. 同伦延拓同伦延拓（HC）[69，84]的思想是演化一个多项式系统G（设XRM表示M个未知数。设F（X）=（f1（X），f2（X），.，f N（X））是N个多项式方 程 的 系 统 ， 并 且 G （ X ） = （ g1 （ X ） ， g2（X），...， g N（X））是具有已知解的多项式系统。HC 的思想是构造一系列中间多项式系统H（X，t），其中H（X，0）=G（X）且H（X，1）=F（X），例如：通过线性插值：H（x，t）=（1−t）G（x）+tF（x），t∈[0，1].（一）其基本思想是从H（X，t）的解中求出H（X，t+nt）的解。图1说明了一个解决方案和一个未知数的想法。黑色曲线是形成同伦曲线的H（X，t）的解X（t）的轨迹，其中X0是G（X）的已知解，X1是F（X）的期望解。我们跟踪解决方案的H（X，t）从X0的迭代次数，每个预测和校正步骤组成。预测使用一阶泰勒展开来估计t+t处的X，X （ t+t ） =X （ t ） +dXt ，（2）其中X是X（t + t）的一阶估计。我们图1：同伦延拓算法的轨迹（曲线），以黑色显示H（X，t），以及一个预测（红色）和一个校正（蓝色）。龙格库塔法在预测步骤之后，Xt（t+δt）可能远离同伦曲线X（t）。因此，使用校正来将X（t+t）更新为X（t+t），即。e. 、H（X，t+t）+H（X，t+t）（X−X）=0，（4）使用牛顿方法，给出X的X=X−（H）−1（X，t+t）H（X，t+t）。（五）当F（X）的解随着t从0迭代到1时，预测和校正步骤对将X0作为G（X）的解数值地演化到X假设我们有一个良好的启动系统，HC算法以概率1找到所有的解（直到某种近似值）。关于HC al-taxim的更详细的描述可以在[13]中找到。4. 说明性问题矩阵：令Γ表示投影到具有深度ρ的像点γ=（η，η，1）T的3D点，使得Γ =ργ。 通过姿态（R，T）与另一相机相关的相机中的Γ的表达式为Γ <$= R Γ + T，其中R是旋转矩阵，T是平移。 由于度量模糊性，求出了沿T的单位方向T，其中T=λT。使用校准相机的相对姿态估计是Nister的5点算法最常解决的经典问题 考虑五个对应点（γi，γ<$i）其中一个图像中的γ i对应于另一个图像中的γ<$i。 因为Γi=ρiγi，所以Γ<$i=ρ<$i γ<$i，且Γ<$i=RΓi+T。γi和γ<$i之间的关系如下：ρ<$iγ<$i=Rρiγi+T，i=1，2，···，N，（6）其中深度（ρ，ρ<$）表示10个未知数，（R，T）通过对H（X（t），t）微分来获得dX，即，我我DTH dX+5个未知数上述五个矢量方程的集合给出了15个未知数中的15个约束代表X dtdt X tR与四元数，其中涉及4个未知数与一个方程产生16个多项式方程的16个未知数。其中J=H是H关于X的M N雅可比矩阵。 这一步，从X（t）对X进行一阶估计，称为预测步骤（图1）。然而，我们可以使用更高阶的方法来改进预测，如4阶观察到，在文献中没有尝试解这些方程，HC可以解这些方程，称为“5 pt rel.姿势深度侦察”&表2中相反，事务处理方法是通过以下方式15768我···×T TT×××××××J1···23通过将方程6与T进行叉积，然后与γi进行点积来消除十个深度变量，从而给出经典的对极关系，e. ，γ<$TEγi=0，i=1，2，，5，其中E=[T]×R. 虽然这是5个未知数中的5个方程除非R由一个四元数表示，给出6个未知数的6个同样，这也可以通过HC来解决。不过，经典的方法是将E视为9个非[2019-07- 17][2019 - 07][2019 - 07]2EE TE − trace（EE T）E = 0。（七）这是9个三次多项式方程，但只有4个是独立的，可以结合经典的对极关系来求解E。也就是说，E以矢量形式写为E，E=[E11，E12，E13，E21，E22，E23，E31，E32，E33]wTE=0，i=1，2，···，5，（八）在3D世界坐标点Γi和它们在图像γ i中的2D投影之间。其中3D点（ri，r2，r3）对应于2D图像点（γ1，γ2，γ3）的P3P问题具有悠久的历史[33，32，36，81]，并且它具有4个解决方案，需要第4个对应关系来消除歧义。基本公式可以用Γi=ρ i γ i来表示，其中i=1，2，3。这是一组九个未知数的九个方程。此时，HC可用于求解（R，T）和深度。使用R的四元数表示，其中涉及4个未知数和一个方程，这变成了一组10个10多项式与10个未知数。传统的方法消除了R和T来求解深度，（Γ2−Γ1）T（Γ2−Γ1）=（ρ2γ2−ρ1γ1）T（ρ2γ2−ρ1γ1）（Γ3−Γ1）T（Γ3−Γ1）=（ρ3γ3−ρ1γ1）T（ρ3γ3−ρ1γ1），（9）（Γ2− Γ1）（Γ3− Γ1）=（ρ2γ2−ρ1γ1）（ρ3γ3−ρ1γ1）三个未知数（ρ，ρ，ρ）的三个二次方程的集合。阿格夫·T我¯ ¯ ¯同样，这种简化形式可以很容易地由HC解决，但=[i i，ηi i，i，i η<$i，η iη<$i，η<$i，i，ηi，1]。那么，E是四个矩阵表示的任意线性和设右零空间为E1=α1E1+α2E2+α3E3+E4，其中最后一个常数α4由于E的标度不变性而设为1。唯一剩下的约束是9个三次方程7的集合，其中未知数（α1，α2，α3）涉及20个直到3阶的单项式，使得它们可以表示为9 × 20矩阵乘以20个单项式的向量然后，除了涉及一个变量（比如α3）的单项式之外，所有单项式都可以被消去。 这可以通过部分旋转的Gauss-Jordan消去法来完成，以形成上三角矩阵，该上三角矩阵可以通过手动导出的Gr o ¨ bner基得到一个单变量α3的单个十阶多项式，给出10个根。 α 3的实根可以解α1、α2和E，从中可以恢复R和T。Li和Hartle y[65]使用隐变量技术（一种代数消元法[21]的结果技术），使用方程8所述的E_n求解方程7。它们包括det（E）= 0作为第十个方程，以及将10 10矩阵的行列式等于零作为α3的函数来求解，这是一个可以求解的十阶多项式。与尼斯特的技术相比，这种技术的优势在于复杂性和易于实施。观察到这两种方法都设计了巧妙的算法来将多项式方程6的基本系统转换为单10次单变量多项式。而同伦延拓法可直接用于求解16 × 16多项式系统或方程7的约化6 × 6系统。最后，HC也可以用于使用三次多项式的3 3系统来求解（α1，α2，α3）。 请注意，我们并不提倡使用HC来解决相对姿态（系统太小，无法从中受益相反，我们注意到它可以通过HC来解决。传统的方法是将西尔维斯特得到一个8次多项式，包含偶数项，因此它实际上是一个四次多项式。一般的Pendant问题依赖于3D点Γi和2D图像点γ i之间的n个对应关系，i= 1，2，...，n. 代数重构误差的直接最小化[94]使用R的非单位四元数表示，并明确优化R。 这就给出了四个变量的四个三次多项式，用G ro¨ bner基求解，并利用文[55]中的自动生成器构造了一个消去模板。 这给出了最多81个解决方案，具有575 656消除模板和81 81动作矩阵。或者，这些方程可以使用HC求解，而无需任何进一步的处理，在GPU上加速约5倍，表2。 在这种较大的情况下，HC具有简单性和效率。N视图三角测量旨在找到与来自N个视图的一组投影γ1，γ N最一致的3D世界点Γ，给定视图i和j之间的成对本质矩阵Eij形式的所有相机的相对姿态。由于噪声，来自对应点的投影射线不一定在空间中相遇。对于两个视图，使用投影射线[10]上最近点之间的中点可能是错误的，特别是在校准误差较大的情况不是最小化潜在的3D误差，而是可以最小化重投影误差[37，38，46]。 令γi=γi+γi，其中γi是真实的二维观测值，γi是噪声引入的误差，即，、γ<$TEijγ<$i=0，（γj−<$γj）TEij（γi−<$γi）=0。（10）最小化重投影误差<$γi和<$γ j求解透视n点问题（Pestive-n-Point Problem，Pestive-n-Point Problem）（γi，γj）=argmin（||γi||2个以上||∆γj||2）。-使用n个 对应关系的校准相机（R，T），（γj−<$γj）TEij（γi−<$γi）=015769我×N2NN不×××J× ××J JIJ我我我|γ k|、233113ρ3eT K−1γ3 = eT ρ1K−1R13γ1 + eTK−1T13。K吉夫茨3使用拉格朗日乘子和符号<$γT=（ui，vi，0）问题就变得（ui，vi，uj，vj，λ）=argmin（u2+v2+u2+v2）校准矩阵是K = diag（f，f，1），其中f是焦距。分别考虑图像（1，2，3）中的三个对应点（γ1，γ2，γ3），分别具有未知深度（ρ1，ρ，ρ然后，表示（R，T）和（R，i ij j 23ui，v i，u j，vj，λT13）第二和第三相机相对于第一相机的相对姿态+λ（γ T−[u，v，0]）E（γ − <$uv0<$T）。第一个，分别，我们有设定五个变量的一阶导数，5 5多项式系统。该系统可以用HC轻松解决。传统上，系统ρ2K−1γ2=ρ1K−1R12γ1+T12ρ3K−1γ3=ρ1K−1R13γ1+T13，（十三）通过消除五个变量中的四个来求解，给出一个六阶多项式[38]。这给出了很好的结果，但它是缓慢的，促使[46，66]使用迭代方法，该方法更快，但易于陷入局部极小值。尽管最小化重投影误差的公式是相同的，但N视图三角剖分没有得到很好的探索（<$γ1<$，<$γ2<$，···，<$γN<$）=（11）其中，T12被设定为具有单位长度。因此，有11三个未知深度。由于有四组对应关系，因此总共有24个未知数，包括一个f，11个姿势和12个深度。还有四组矢量，方程13，每组给出6个方程。如果R12和R13用四元数表示，我们有26个方程，26个未知数，可以用HC求解。或者，ρ2和ρ3可以用ρ1表示为：Σ。TK−1γ第一，第二，...γ-Nk=13=eT ρ K−1R3γ+eT K−1T使得TEij（γi−<$γi）=0或（u1，v1，u2，v2，···，uN，vN）=（12）Σ将这些代入方程13，对于每个对应三元组给出4个方程，总共16个方程。未知数是1个焦距，11个姿势和4个深度，总共16个未知数。如果R表示为四元数，arg min[（u2+v2）+K Ku1，v1，u2，v2，···，uN，vN，λkk=1ΣΣλ（γji=1j=i+1乌岛我）的情况。0每个旋转矩阵引入一个额外的未知数和一个额外的方程，总共给出18个多项式，18个未知数的数学方程这个小问题可以-注意，有2N+N（N−1）=N2+ 3N个未知数，即使在高性能计算环境22机器。 但是，我们的HC实现可以解决这个问题将一阶导数设置为零，对于两个、三个和四个视图，分别给出5 5、9 9和14 14，这对于使用Gr？ bner基和其他传统方法变得明显更困难[58]将所有顺序成对本质矩阵的考虑限制为具有先前视图的那些，即，、E12、E23等。 并使用274305模板的消除模板法; [59]将消除模板的尺寸减小到239290。请注意，完整的问题给出了1866 - 1975年的消除模板，这是不切实际的解决。类似地，4-视图三角化给出了改进的误差，但它导致大的多项式系统。然而，同伦延拓可以解决这些问题，并提高效率，表2。焦距未知情况下的三焦点相对位姿估计是在估计焦距的同时估计三个视图之间的相对位姿。三焦姿态估计最近引起了人们的关注[63，18，45，47，30]。这些方法通常假设内禀矩阵是可用的。最近，[62]估计了具有径向畸变的三焦点张量，这是一个针孔相机和两个径向相机的最小问题。我们考虑另一个最小问题，三个针孔相机和一个共同的焦距，它只需要4点对应的三个视图。让.Nargmin21212（十四）-[uj，vj，0]）Eij（γi −不能通过消除模板解决，因为它需要15770系统，CPU为3326 ms，GPU为388 ms，表2。5. GPU与计算机视觉GPU通常比CPU更受欢迎，因为它们具有超强的计算能力、内存带宽和能源效率。例如，V100GPU在250瓦时提供7 TFlop/s的FP 64计算峰值和900 GB/s的内存带宽。虽然一个CPU核心更快，并提供更广泛的指令集，但GPU有更多的核心，例如。，V100中的5，120。解锁GPU计算能力的关键是设计高度并行并有效使用所有内核的算法。图2显示了GPU架构。CUDA核心被组织成流式多处理器（SM），其中每个SM具有多个CUDA核心。GPU工作被组织成具有两个嵌套并行性级别的内核，一个是数据并行并且跨SM分布的粗略级别，以及每个SM内的精细级别并行是按照线程块（TB）来组织的TB被调度用于在SM之一上执行，并且是相对于其他TB的数据解析。每个TB由多个线程组成，这些线程以32个线程为一组运行，称为warp。15771∼图2：NVIDIA在Tesla V100 GPU中，有80个SM，每个SM分成四个处理块，每个处理块具有16个核心。每个SM的寄存器堆、每个SM的共享存储器/L1高速缓存、L2高速缓存和全局存储器分别为256 KB和96 KB、6，144 KB和16 GB，命中延迟分别为3ns、22.68ns、156.33ns和大约366ns [44]。TB中的线程可以通过共享内存模块共享数据。具有一个线程范围的私有变量通常存储在寄存器文件中。算法必须设计成支持这种类型的并行性。多级存储器层次结构使计算限制操作（如通用矩阵-矩阵乘法（GEMM））能够接近GPU的计算峰值执行[73]。随后，许多稠密线性代数算法，如LAPACK中的 算 法 ， 以 及 随 后 的 MAGMA （ 用 于 GPU 的LAPACK），通常可以使用GEMM和BLAS表示[89]。一些数值算法，如第6节中提到的算法，涉及相对小的矩阵上的许多独立计算（例如稠密因子分解）这些算法虽然受内存带宽的限制，但具有很高的并行度，适合于GPU。通过将每个矩阵完全缓存在寄存器文件或共享内存中，可以最大限度地提高数据重用，这使得GPU在这些类型的算法中优于多核CPU。计算机视觉中的算法自然是数据并行和计算密集型的，因此非常适合现代GPU。涉及一对一映射的计算模式（如由不同过滤器卷积的图像）可以受益于数据并行性和存储器体系结构。涉及某些缓冲区求和的多对一映射也有利于内存层次结构，并在多处理器中快速完成多对多计算模式也可以有效地映射到 GPU[77]。不能有效地映射到GPU的操作通常留给CPU。这通常涉及在并行性不足的小数据集上进行不规则计算，以及具有严重数据依赖性的计算（如求解小型方程组）。不过，技术-像GPU的并行计算和数字线性代数库的发展[1，34]，已经为更多的算法容易移植和有利于GPU的使用奠定了基础。通常，由于计算成本而被避免的算法在当前的进步使得它们的GPU映射非常有效时成为GPU的首选这就是我们要开发的HC的情况。6. HC的GPU实现同伦延拓过程可以通过两种方式并行化：首先，观察到由于HC遵循许多独立的轨道来收敛，因此直接的方法是将每个轨道分配给线程。然而，GPU处理的效率取决于（i）并行处理许多磁道的线程数量，以及（ii）通过使用快速寄存器文件或至少L1高速缓存与更慢的二级缓存或更慢的全局内存，图2。在我们的应用程序中，每个磁道需要几个KB，而对于每个磁道的一个线程，寄存器文件、L1缓存、L2缓存和全局内存的可用内存分别为125、46、37和97 KB。因此，任何需要超过125 + 46 + 37 = 208字节内存的进程都将使用非常慢的全局内存。因此，每个轨道必须使用许多线程，不仅处理必须并行化，而且内存的使用也必须并行化，目的是将所有内容保存在寄存器文件、共享内存或至少L1缓存中。观察到，将交易分散在许多线程上的另一个极端开始变得适得其反，因为线程的同步采用较慢的共享存储器（每32个线程2个时钟周期），使得如果每个磁道采用2048个线程，则需要128个时钟周期（104 ns）乘以它们的同步的数万倍，这变成不必要的开销。目标应用程序的最佳平衡是使用一个GPU核心将一个轨道分配给一个线程（32个线程）这使应用程序可以访问256K/64 = 4K的非常快的寄存器文件存储器和96K/64= 1。5K的快速L1缓存（如果不使用共享内存），很好地满足了目标应用程序的内存需求。另一方面线程同步的成本仅为2个时钟周期。第二直觉旨在通过以下方式在每个线程束内并行化HC：（i）在预测步骤Eq.3和校正步骤，Eq.4和（ii）评估雅可比矩阵H/H/x，H/x，和同伦H，等式2和5。线性系统求解器：在GPU上求解线性系统的绝大多数工作都集中在大型矩阵上，这激发了混合CPU+GPU方法[88，90]。对于像我们这样的较小矩阵，可以使用cuBLAS或MAGMA [3，2，43]。 线性系统通常通过具有部分主元的LU分解来求解，随后是两个三主元。15772时间（µs）×××Σ××angular解。MAGMA中的LU分解速度很快，对于小矩阵，通常比cuBLAS快15%至80%。然而，我们发现cuBLAS比MAGMA更快的组合（分解+求解）操作。这主要是由于MAGMA中的三角形求解器内核很慢，它没有利用小矩阵。我们对改进这些标准库的贡献是双重的。首先，将线性系统作为两个单独的GPU内核来求解会导致冗余的全局内存流量。这两个内核可以融合成一个，如果矩阵trices是小的，从而最大限度地提高数据重用的寄存器文件。提出的核融合显着加快解决方案。其次，在求解线性系统Ax=b时，分解可以作用于增广矩阵[A b]，其隐式地执行关于A的L因子的三角求解。第二个三角形求解在因子分解完成后使用缓存的U因子。 拟议融合内核现在集成到MAGMA库中。雅可比矩阵和向量的并行求值：雅可比矩阵的元素和向量的并行求值的主要瓶颈是其元素的异质性，这阻止了需要统一格式的许多线程的求值。这种异质性可以用一个简单的例子来说明，这个例子是一个具有两个变量X=（x1，x2）的系统，其中雅可比元素由单项式张成，例如，A=a1x1+a2x1x2+a3x2或B =a4x1x2+a5x2，其中（（1，1，1，3），（1，2，1，2），（1，3，2，2）），且B表示为（（1，4，1，2），（1，5，2，2），（0，1，1，1））。注意，H以相同的方式进行评估，尽管系数ak不同。这种齐次形式允许并行计算雅可比矩阵的所有元素和向量的所有元素。最后，还有一个问题是如何分配每个线程的并行计算。回想一下，每个轨道被分配给一个有32个线程的线程束。由于矩阵一般小于32 32，并且由于LU分解的后续操作是逐行的，每行一个线程，因此为每个线程分配一行是有意义的。7. 实验实验旨在测试批处理线性系统的核融合，并测量多项式系统基准以及计算机视觉问题的性能我们使用8核2.6GHz Intel Xeon CPU 和 nVidia Quardro RTX 6000GPU，除非另有说明。内核融合的批处理线性系统：第6节中的具有内核融合和 增 广 矩 阵 的 批 处 理 线 性 系 统 的 性 能 与 图 3 中 的cuBLAS和MAGMA在Tesla V100-PCIe GPU上进行了比较，用于1000个矩阵，大小范围从4 4到20 20。 同样，内核融合MAGMA的性能优于cuBLAS，2的系数2加速2。23× 3。65倍和MAGMA，具有加速功能ai是相应启动和目标系统中的元素。一个简单的方法来同质化这些表达式是写每个作为一个总和在所有可能的单项式和相关的标量零与那些缺席的雅可比元素。然而，由于极端的稀疏性，这个过程是低效的。或者，考虑K是雅可比矩阵元素中的最大项数;在上面的例子中，A有三项，B有两项，因此如果雅可比矩阵只有这些元素，则K= 3此外，考虑到每一项由标量乘以系数和多个变量组成，例如。，A的第三项是（1，a3，x3，x3）的乘积，而第一项是范围从3. 11× 491倍。16014012010080604020045678 9101214161820基质大小（N）图3：MAGMA与内核融合，MAGMA和cuBLAS的批处理线性系统的性能。B是（1，a4，x1，x2）。注意，A的第一项是a（1，a1，x1）。因此，为了使表达均质化问题数量数量CPUGPUCPU它被写为（1，a，x，x），其中辅助变量无名氏。索尔斯（ms）（ms）GPU1 1 3[76] 105.67 2.02 52.31×x3= 1。现在A和B的所有项都可以写为循环7 [12] 7 924 177.95 4.77 37.31×U=Kk=1 skak、jxk，m1xk，m2···x k，m，M，桂10 [42] 11 1024 414.12 7.34 56.42×经济12 [69] 12 1024 227.54 17.06 13.34×其中sk是标量，ak ，j标识系数，xk ，mi标识变量之一，包括x3= 1，M是项中变量的最大数量。考虑到这一点，对于U的并行计算要传送的唯一数据是（sk，a k，j，x k，m1，x k，m2，.，其中a k，j，x k，mi是指向存储在共享存储器中并由索引访问的数据的指针，即，，A表示为表1：GPU-HC在基准测试问题上的性能多项式系统基准：我们选择了四个代表性的基准多项式系统[76，12，42，69]来评估我们的GPU-HC。表1显示了GPU-HC显着的加速范围从13到56。图4（a）显示了对每个多项式系统进行平均后的残差CUBLAS （ 分 离式 ） MAGMA （ 分离 式 ） MAGMA（熔融式）15773无名氏。8.32×5点相对值姿态深度侦察16 160 X 150.9426.895.61×N./ A.6点卷帘ABS。姿势w. 1-lin。[6] 18 160 X 158.4827.115.85×N./ A.三视图三角测量[17] 9 94 612.432 101.868.1724.19× 38.24×最优四元数的Pests [72] 4 128 36.329 80.267.1811.18×5.06×P4P，未知焦距径向畸变[15] 5 192 9.03 130.797.5117.42×1.2×2-带径向畸变的视图三角剖分[57]5285.9266.223.0621.64×1.93×最佳P4P绝对值[第87话]5 32 1.864 53.131.5733.84×1.19×3 pt rel.姿势w.单应性约束[83]8 8 1.472 51.250.9553.95×1.55×rel.姿势w.未知焦距[53]电话：+86-21 - 6666666传真：+86-21- 6666666P3P绝对值[第55话]180.18× 0.29× 180.185点相对值摆姿势深度侦察[75个]3 270.03555.48 0.96 57.79×0.036×X：由于内存不足的问题，消除模板无法解决表2：GPU-HC和CPU-HC与 消除模板在应用中的几个最小问题。从100次随机输入开始，目标系统。结果表明，这种加速并不是以降低精度为代价的. GPU-HC的计算结果满足多项式系统的高精度要求。（a）（b）图4：残差的正态平滑直方图所有的解决方案都由GPU-HC解决。(a)多项式系统基准（b）计算机视觉问题。计算机视觉问题：我们考虑了计算机视觉中的最小问题的样本，范围从经典的姿态估计P3P到更复杂的3视图三角测量，以及先前尚未探索的两个问题：（i）4视图三角测量是3视图三角测量的扩展[17]。据我们所知，这是探索这个问题的第一次尝试。（ii）具有未知焦距的三焦点相对姿态估计是现有的三焦点相对姿态估计问题[29，62]到未校准场景的扩展;据我们所知，该问题以前没有被探索这两个问题在第4节中介绍。求解多项式系统最流行的技术是消除模板方法[59]，用于衡量GPU-HC的性能。表2显示了消除模板性能与HC在CPU和GPU上的性能每个问题用随机参数实例化20次，并对其性能进行平均。HC的启动系统由Macaulay中的单值模块生成2 [24]。影响加速的因素的GPU-HC在CPU-HC，包括解决方案的数量，未知数的数量，和雅可比矩阵的多项式评估中的项数。消元模板的性能取决于它所解的线性方程组的大小，而线性方程组的大小又与多项式方程组的解的个数有关注意，对于前四个问题，即使有足够的内存，消去模板也不能计算系统的商环的基按消除模板时间排序的表2显示，除了P3 P（底部四行）等简单问题外，GPU-HC优于消除模板。GPU-HC为消除模板无法处理的更复杂的问题打开了大门。此外，图4（b）是选定问题的残差直方图，表明GPU-HC的加速也不会以给出有希望的估计为代价其他实验数据可参见补充材料。8. 结论我们提出了GPU-HC，这是HC的GPU实现，是通用的，可以很容易地应用于任何计算机视觉问题，制定为多项式方程系统 GPU-HC的显著加速是一个推动因素，因为HC现在可以有效地用于中等复杂的问题，而不是完成方法。GPU-HC还可以探索那些迄今为止还没有实际解决方案的复杂问题。确认Kimia 、 Fan 和 Chien 感 谢 NSF 1910530 奖 的 支 持 。Tsigaridas 由 ANR JCJC GALOP （ ANR-17-CE 40 -0009）提供部分支持。Abdelfattah和Tomov部分由NSF Grant No.OAC 1740250。问题数量#21040;的SOLS。以琳温度（毫秒）CPU（毫秒）GPU（毫秒）CPUGPU以琳 温度GPU15774引用[1] A. Abdelfattah ，A. Haidar，S. Tomov和J. Dongarra。GPU的批处理GEMM的性能、设计和自动调整. InHighPerformance Computing-31st International Conference ，ISC High Performance 2016，Frankfurt，Germany，June19-23，2016，Proceedings，pages 216[2] E. Agullo，J.Demmel，J.栋加拉湾Hadri，J.库扎克，J. Langou，H. Ltaief，P. Luszczek，and S.托莫夫新兴体系结构上的数值线性代数：PLASMA和MAGMA项目。J. Phys.：Conf.系列，180（1），2009. 6[3] A. Ahmad，H. Azzam，T. Stanimire和D. Jack.使用GPU的小矩阵的批量单侧因子分解：挑战和对策。计算科学杂志，26：226-236，2018。6[4] C. Albl，Z. Kukelova，V. Larsson，and T.帕杰拉卷帘快门相机绝对姿势。IEEE transactions on pattern analysisand machine intelligence，42（6）：1439-1452，2019。第1、3条[5] C. Albl，Z. Kukelova和T.帕杰拉卷帘快门绝对相机姿势。在IEEE/CVF计算机视觉和模式识别会议论文集，第2292-2300页1[6] V. L. Albl Cenek、Kukelova Zuzana和T.帕杰拉卷帘快门相机绝对姿势。IEEE transactions on pattern analysis andmachine intelligence，42（6）：1439-1452，2019。8[7] 亚历山大和J. A.约克 同伦延拓方法：数值可实现的拓扑 过 程 。 Transactions of the American MathematicalSociety，242：271-284，1978. 2[8] D. J.Bates，J.D. Hauenstein，A. J. Sommese和C. W.万普勒自适应多精度路径跟踪。SIAM Jour-nal on NumericalAnalysis，46（2）：722-746，2008. 2[9] D. J. Bates，A. J. Sommese，J. D. Hauenste