GPU-Based Homotopy Continuation for Minimal Problems in Computer Vision
GPU-Based Homotopy Continuation for Minimal Problems in Computer Vision
复制标题
DOI：
10.1109/cvpr52688.2022.01531
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Chiang-Heng Chien;Hongyi Fan;A. Abdelfattah;Elias P. Tsigaridas;S. Tomov;B. Kimia
中科院分区：
文献类型：
--
作者：
Chiang-Heng Chien;Hongyi Fan;A. Abdelfattah;Elias P. Tsigaridas;S. Tomov;B. Kimia
多项式方程组在计算机视觉中经常出现，特别是在多视图几何问题中。用于求解这些系统的传统方法通常旨在消除变量以达到单变量多项式，例如，一个十阶多项式的5点姿态估计，使用巧妙的操纵，或更一般地使用Grobner基础，resultants，和消除模板，导致多视图几何和其他问题的成功算法。然而，当问题复杂时，这些方法不起作用，并且当它们起作用时，它们面临效率和稳定性问题。同伦延拓（HC）可以解决更复杂的问题，而没有稳定性问题，并保证全局解，但它们被称为是缓慢的。在本文中，我们表明，HC可以在GPU上并行化，在多项式基准测试中显示出高达56倍的显着加速。我们还表明，GPU-HC可以通用地应用于一系列计算机视觉问题，包括4视图三角测量和焦距未知的三焦点姿态估计，这不能用消除模板解决，但可以有效地解决HC。GPU-HC为一系列计算机视觉问题的简单制定和解决方案打开了大门。
Systems of polynomial equations arise frequently in computer vision, especially in multiview geometry problems. Traditional methods for solving these systems typically aim to eliminate variables to reach a univariate polynomial, e.g., a tenth-order polynomial for 5-point pose estimation, using clever manipulations, or more generally using Grobner basis, resultants, and elimination templates, leading to successful algorithms for multiview geometry and other problems. However, these methods do not work when the problem is complex and when they do, they face efficiency and stability issues. Homotopy Continuation (HC) can solve more complex problems without the stability issues, and with guarantees of a global solution, but they are known to be slow. In this paper we show that HC can be parallelized on a GPU, showing significant speedups up to 56 times on polynomial benchmarks. We also show that GPU-HC can be generically applied to a range of computer vision problems, including 4-view triangulation and trifocal pose estimation with unknown focal length, which cannot be solved with elimination template but they can be efficiently solved with HC. GPU-HC opens the door to easy formulation and solution of a range of computer vision problems.