Algebra and geometry of camera resectioning

Connelly, Erin; Duff, Timothy; Loucks-Tavitas, Jessie

doi:10.1090/mcom/4030

Algebra and geometry of camera resectioning
HTML articles powered by AMS MathViewer

by Erin Connelly, Timothy Duff and Jessie Loucks-Tavitas;

Math. Comp. 94 (2025), 2613-2643

DOI: https://doi.org/10.1090/mcom/4030

Published electronically: November 14, 2024

PDF | Request permission

Abstract:

We study algebraic varieties associated with the camera resectioning problem. We characterize these resectioning varieties’ multigraded vanishing ideals using Gröbner basis techniques. As an application, we derive and re-interpret celebrated results in geometric computer vision related to camera-point duality. We also clarify some relationships between the classical problems of optimal resectioning and triangulation, state a conjectural formula for the Euclidean distance degree of the resectioning variety, and discuss how this conjecture relates to the recently-resolved multiview conjecture.

References

Sameer Agarwal, Timothy Duff, Max Lieblich, and Rekha R. Thomas, An atlas for the pinhole camera, Found. Comput. Math. 24 (2024), no. 1, 227–277. MR 4707063, DOI 10.1007/s10208-022-09592-6
S. Agarwal, A. Pryhuber, and R. R. Thomas, Ideals of the multiview variety, IEEE Trans. Pattern Anal. Mach. Intell. 43 (2021), no. 4, 1279–1292.
Chris Aholt, Bernd Sturmfels, and Rekha Thomas, A Hilbert scheme in computer vision, Canad. J. Math. 65 (2013), no. 5, 961–988. MR 3095002, DOI 10.4153/CJM-2012-023-2
Adam Boocher, Free resolutions and sparse determinantal ideals, Math. Res. Lett. 19 (2012), no. 4, 805–821. MR 3008416, DOI 10.4310/MRL.2012.v19.n4.a6
Paul Breiding, Felix Rydell, Elima Shehu, and Angélica Torres, Line multiview varieties, SIAM J. Appl. Algebra Geom. 7 (2023), no. 2, 470–504. MR 4598813, DOI 10.1137/22M1482263
P. Breiding and S. Timme, HomotopyContinuation.jl: A Package for Homotopy Continuation in Julia, International Congress on Mathematical Software, Springer, 2018, pp. 458–465.
S. Carlsson and D. Weinshall, Dual computation of projective shape and camera positions from multiple images, Int. J. Comput. Vis. 27 (1998), no. 3, 227–241.
Yairon Cid-Ruiz, Oliver Clarke, and Fatemeh Mohammadi, A study of nonlinear multiview varieties, J. Algebra 620 (2023), 363–391. MR 4536152, DOI 10.1016/j.jalgebra.2022.12.036
Diego Cifuentes, A convex relaxation to compute the nearest structured rank deficient matrix, SIAM J. Matrix Anal. Appl. 42 (2021), no. 2, 708–729. MR 4252075, DOI 10.1137/19M1257640
Aldo Conca, Emanuela De Negri, and Elisa Gorla, Radical generic initial ideals, Vietnam J. Math. 50 (2022), no. 3, 807–827. MR 4447407, DOI 10.1007/s10013-022-00551-w
David A. Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, 4th ed., Undergraduate Texts in Mathematics, Springer, Cham, 2015. An introduction to computational algebraic geometry and commutative algebra. MR 3330490, DOI 10.1007/978-3-319-16721-3
Igor Dolgachev, Lectures on invariant theory, London Mathematical Society Lecture Note Series, vol. 296, Cambridge University Press, Cambridge, 2003. MR 2004511, DOI 10.1017/CBO9780511615436
Jan Draisma, Emil Horobeţ, Giorgio Ottaviani, Bernd Sturmfels, and Rekha R. Thomas, The Euclidean distance degree of an algebraic variety, Found. Comput. Math. 16 (2016), no. 1, 99–149. MR 3451425, DOI 10.1007/s10208-014-9240-x
Timothy Duff, Cvetelina Hill, Anders Jensen, Kisun Lee, Anton Leykin, and Jeff Sommars, Solving polynomial systems via homotopy continuation and monodromy, IMA J. Numer. Anal. 39 (2019), no. 3, 1421–1446. MR 3984062, DOI 10.1093/imanum/dry017
T. Duff, K. Kohn, A. Leykin, and T. Pajdla, PLMP-point-line minimal problems in complete multi-view visibility, IEEE International Conference on Computer Vision, 2019, pp. 1675–1684.
T. Duff, K. Kohn, A. Leykin, and T. Pajdla, PL1P—point-line minimal problems under partial visibility in three views, European Conference on Computer Vision, 2020.
Timothy Duff, Viktor Korotynskiy, Tomas Pajdla, and Margaret H. Regan, Galois/monodromy groups for decomposing minimal problems in 3D reconstruction, SIAM J. Appl. Algebra Geom. 6 (2022), no. 4, 740–772. MR 4522866, DOI 10.1137/21M1422872
O. D. Faugeras and B. Mourrain, On the geometry and algebra of the point and line correspondences between n images, IEEE International Conference on Computer Vision, 1995, pp. 951–956.
M. Giusti and M. Merle, Singularités isolées et sections planes de variétés déterminantielles. II. Sections de variétés déterminantielles par les plans de coordonnées, Algebraic geometry (La Rábida, 1981) Lecture Notes in Math., vol. 961, Springer, Berlin, 1982, pp. 103–118 (French). MR 708329, DOI 10.1007/BFb0071278
D. R. Grayson and M. E. Stillman, Macaulay2, a software system for research in algebraic geometry, Available at http://www2.macaulay2.com.
J. A. Grunert, Das pothenotische problem in erweiterter gestalt nebst über seine anwendungen in der geodäsie, Grunerts Archiv für Mathematik und Physik 1 (1841), 238–248.
Richard Hartley and Andrew Zisserman, Multiple view geometry in computer vision, 2nd ed., Cambridge University Press, Cambridge, 2003. With a foreword by Olivier Faugeras. MR 2059248
O. Hesse, Die cubische Gleichung, von welcher die Lösung des Problems der Homographie von M. Chasles abhängt, J. Reine Angew. Math. 62 (1863), 188–192 (German). MR 1579236, DOI 10.1515/crll.1863.62.188
Anders Heyden and Kalle Åström, Algebraic properties of multilinear constraints, Math. Methods Appl. Sci. 20 (1997), no. 13, 1135–1162. MR 1465398, DOI 10.1002/(SICI)1099-1476(19970910)20:13<1135::AID-MMA908>3.0.CO;2-9
Roger A. Horn and Charles R. Johnson, Topics in matrix analysis, Cambridge University Press, Cambridge, 1994. Corrected reprint of the 1991 original. MR 1288752
J. Kileel and K. Kohn, Snapshot of algebraic vision, 2022.
Z. Kukelova, M. Bujnak, and T. Pajdla, Automatic generator of minimal problem solvers, Computer Vision–ECCV 2008: 10th European Conference on Computer Vision, Marseille, France, October 12-18, 2008, Proceedings, Part III 10, Springer, 2008, pp. 302–315.
V. Larsson, K. Astrom, and M. Oskarsson, Efficient solvers for minimal problems by syzygy-based reduction, IEEE Conference on Computer Vision and Pattern Recognition, 2017, pp. 820–829.
V. Larsson, M. Oskarsson, K. Åström, A. Wallis, Z. Kukelova, and T. Pajdla, Beyond Gröbner bases: basis selection for minimal solvers, 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, Computer Vision Foundation / IEEE Computer Society, 2018, pp. 3945–3954.
Binglin Li, Images of rational maps of projective spaces, Int. Math. Res. Not. IMRN 13 (2018), 4190–4228. MR 3829180, DOI 10.1093/imrn/rnx003
Laurentiu G. Maxim, Jose I. Rodriguez, and Botong Wang, Euclidean distance degree of the multiview variety, SIAM J. Appl. Algebra Geom. 4 (2020), no. 1, 28–48. MR 4048615, DOI 10.1137/18M1233406
Laurentiu G. Maxim, Jose Israel Rodriguez, and Botong Wang, Euclidean distance degree of projective varieties, Int. Math. Res. Not. IMRN 20 (2021), 15788–15802. MR 4329882, DOI 10.1093/imrn/rnz266
L. Quan, Invariants of six points and projective reconstruction from three uncalibrated images, IEEE Trans. Pattern Anal. Mach. Intell. 17 (1995), no. 1, 34–46.
F. Schaffalitzky, A. Zisserman, R. I. Hartley, and P. H. S. Torr, A six point solution for structure and motion, European Conference on Computer Vision, Springer, 2000, pp. 632–648.
Peter Sturm, A historical survey of geometric computer vision, Computer analysis of images and patterns. Part I, Lecture Notes in Comput. Sci., vol. 6854, Springer, Heidelberg, 2011, pp. 1–8. MR 2872221, DOI 10.1007/978-3-642-23672-3_{1}
M. Trager, M. Hebert, and J. Ponce, Coordinate-free Carlsson-Weinshall duality and relative multi-view geometry, IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, Computer Vision Foundation / IEEE, 2019, pp. 225–233.

AMS Website Down

Mathematics of Computation

Algebra and geometry of camera resectioning
HTML articles powered by AMS MathViewer

Abstract: