Sparse Resultant-Based Minimal Solvers in Computer Vision and Their Connection with the Action Matrix
Bhayani, Snehal; Heikkilä, Janne; Kukelova, Zuzana (2024-03-23)
Springer
23.03.2024
Bhayani, S., Heikkilä, J. & Kukelova, Z. Sparse Resultant-Based Minimal Solvers in Computer Vision and Their Connection with the Action Matrix. J Math Imaging Vis 66, 335–360 (2024). https://doi.org/10.1007/s10851-024-01182-1
https://creativecommons.org/licenses/by/4.0/
© The Author(s) 2024, corrected publication 2024. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
https://creativecommons.org/licenses/by/4.0/
© The Author(s) 2024, corrected publication 2024. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
https://creativecommons.org/licenses/by/4.0/
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:oulu-202406104302
https://urn.fi/URN:NBN:fi:oulu-202406104302
Tiivistelmä
Abstract
Many computer vision applications require robust and efficient estimation of camera geometry from a minimal number of input data measurements. Minimal problems are usually formulated as complex systems of sparse polynomial equations. The systems usually are overdetermined and consist of polynomials with algebraically constrained coefficients. Most state-of-the-art efficient polynomial solvers are based on the action matrix method that has been automated and highly optimized in recent years. On the other hand, the alternative theory of sparse resultants based on the Newton polytopes has not been used so often for generating efficient solvers, primarily because the polytopes do not respect the constraints amongst the coefficients. In an attempt to tackle this challenge, here we propose a simple iterative scheme to test various subsets of the Newton polytopes and search for the most efficient solver. Moreover, we propose to use an extra polynomial with a special form to further improve the solver efficiency via Schur complement computation. We show that for some camera geometry problems our resultant-based method leads to smaller and more stable solvers than the state-of-the-art Gröbner basis-based solvers, while being significantly smaller than the state-of-the-art resultant-based methods. The proposed method can be fully automated and incorporated into existing tools for the automatic generation of efficient polynomial solvers. It provides a competitive alternative to popular Gröbner basis-based methods for minimal problems in computer vision. Additionally, we study the conditions under which the minimal solvers generated by the state-of-the-art action matrix-based methods and the proposed extra polynomial resultant-based method, are equivalent. Specifically, we consider a step-by-step comparison between the approaches based on the action matrix and the sparse resultant, followed by a set of substitutions, which would lead to equivalent minimal solvers.
Many computer vision applications require robust and efficient estimation of camera geometry from a minimal number of input data measurements. Minimal problems are usually formulated as complex systems of sparse polynomial equations. The systems usually are overdetermined and consist of polynomials with algebraically constrained coefficients. Most state-of-the-art efficient polynomial solvers are based on the action matrix method that has been automated and highly optimized in recent years. On the other hand, the alternative theory of sparse resultants based on the Newton polytopes has not been used so often for generating efficient solvers, primarily because the polytopes do not respect the constraints amongst the coefficients. In an attempt to tackle this challenge, here we propose a simple iterative scheme to test various subsets of the Newton polytopes and search for the most efficient solver. Moreover, we propose to use an extra polynomial with a special form to further improve the solver efficiency via Schur complement computation. We show that for some camera geometry problems our resultant-based method leads to smaller and more stable solvers than the state-of-the-art Gröbner basis-based solvers, while being significantly smaller than the state-of-the-art resultant-based methods. The proposed method can be fully automated and incorporated into existing tools for the automatic generation of efficient polynomial solvers. It provides a competitive alternative to popular Gröbner basis-based methods for minimal problems in computer vision. Additionally, we study the conditions under which the minimal solvers generated by the state-of-the-art action matrix-based methods and the proposed extra polynomial resultant-based method, are equivalent. Specifically, we consider a step-by-step comparison between the approaches based on the action matrix and the sparse resultant, followed by a set of substitutions, which would lead to equivalent minimal solvers.
Kokoelmat
- Avoin saatavuus [34176]
Ellei muuten mainita, aineiston lisenssi on https://creativecommons.org/licenses/by/4.0/