Mercedes Garcia-Salguero and Javier Gonzalez-Jimenez, “Certifiable Solver for Real-Time N-View Triangulation,” IEEE Robotics and Automation Letters, vol. 8, no. 4, pp. 1999–2005, Apr. 2023, doi: 10.1109/LRA.2023.3245408. [Online]. Available at: https://ieeexplore.ieee.org/document/10044919/. [Accessed: December 12, 2023]
@article{garcia_salguero_certifiable_2023,
title = {Certifiable {Solver} for {Real}-{Time} {N}-{View} {Triangulation}},
volume = {8},
issn = {2377-3766, 2377-3774},
url = {https://ieeexplore.ieee.org/document/10044919/},
doi = {10.1109/LRA.2023.3245408},
language = {en},
number = {4},
urldate = {2023-12-12},
journal = {IEEE Robotics and Automation Letters},
author = {Garcia-Salguero, Mercedes and Gonzalez-Jimenez, Javier},
month = apr,
year = {2023},
pages = {1999--2005},
code = {https://github.com/mergarsal/FastNViewTriangulation},
freepdf = {https://mapir.isa.uma.es/papersrepo/2023/2023_mercedes_RAL_Nview_triangulation_paper.pdf},
tldr = {Formulates L2 norm N-view triangulation problem as a QCQP (Quadratically Constrained Quadratic Problem), where constraints are pair-wise epipolar constraints. Iterative solve using linear relaxations of the QCQP. Solutions are certified for optimality by checking for constraints' satisfaction and positive semi-definiteness of a Hessian.}
}
Cutting-edge field robotic systems, such as UAV or autonomous cars, demand fast and optimal solutions for any component at the core of their critical navigational tasks. Among them, we focus on the triangulation of image points from multiple views, which is a cornerstone for more complex tasks such as visual localization and SLAM. In this paper we present a fast and certifiable solver for the N-view triangulation problem that doesn’t require any specific optimization software package and can be implemented with any linear algebra library. The proposal relies on a series of linear convexifications which, in the limit, recovers the original problem, allowing us to solve problem instances with N = 10 views in 150 microseconds on a standard desktop computer. On real data our solver obtains and certifies the optimal solution in more than 99% of the problem instances. We make the code available at https://github.com/mergarsal.
tl;dr: Formulates L2 norm N-view triangulation problem as a QCQP (Quadratically Constrained Quadratic Problem), where constraints are pair-wise epipolar constraints. Iterative solve using linear relaxations of the QCQP. Solutions are certified for optimality by checking for constraints’ satisfaction and positive semi-definiteness of a Hessian.
Certifiable Solver for Real-Time N-View Triangulation.
Mercedes Garcia-Salguero and Javier Gonzalez-Jimenez.
Publisher: http://doi.org/10.1109/LRA.2023.3245408
h/t Amy Tabbpdf: https://mapir.isa.uma.es/papersrepo/2023/2023_mercedes_RAL_Nview_triangulation_paper.pdf
code: https://github.com/mergarsal/FastNViewTriangulation