Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Events
Topic Page
Marketing
Start single access now
Access for companies
12th International Engine Congress 2025 | 25. + 26. February 2025

Meeting Place for the Powertrain and Sustainable Fuels Community

The congress will examine the future role of the internal combustion engine and its non-fossil fuels from a global perspective with leading experts. Be part of it! More information and booking options are available on our website.
EXTENDED SEARCH
Log in
Top
Foundations of Computational Mathematics
Published in:

20-09-2022

An Atlas for the Pinhole Camera

Authors: Sameer Agarwal, Timothy Duff, Max Lieblich, Rekha R. Thomas

Published in: Foundations of Computational Mathematics | Issue 1/2024

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We introduce an atlas of algebro-geometric objects associated with image formation in pinhole cameras. The nodes of the atlas are algebraic varieties or their vanishing ideals related to each other by projection or elimination and restriction or specialization, respectively. This atlas offers a unifying framework for the study of problems in 3D computer vision. We initiate the study of the atlas by completely characterizing a part of the atlas stemming from the triangulation problem. We conclude with several open problems and generalizations of the atlas.
previous article Covariance’s Loss is Privacy’s Gain: Computationally Efficient, Private and Accurate Synthetic Data
next article Efficient Computation of the Zeros of the Bargmann Transform Under Additive White Noise

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
To distinguish between known and unknown quantities, we use a bar over an object to indicate specialization. For instance, A stands for a symbolic \(3 \times 4\) matrix denoting a camera, while \({\bar{A}}\) is a \(3 \times 4\) scalar matrix realizing a camera. We also use bold face letters to indicate collections. For instance, we use \(\mathbf {A}\) and \({\bar{\mathbf {A}}}\) to specify a collection of symbolic and scalar cameras, respectively.
 
2
The imaging map of (1.3) models a scenario in which all points are visible in every image. One may consider other scenarios of interest in computer vision, e.g., when each point is visible in only some of the images (e.g., [19, 29]).
 
3
We note that the definition of \(\Gamma _{\mathbf {A}, \mathbf {q}, \mathbf {p}}^{m,n}\) is independent of the choice of U. As such, it is insensitive to certain physical assumptions about the camera matrices (e.g.,  that they have full rank, or that their centers do not coincide.) In particular, although a generic point \(({\bar{\mathbf {A}}}, {\bar{\mathbf {q}}}, {\bar{\mathbf {p}}}) \in \Gamma _{\mathbf {A}, \mathbf {q}, \mathbf {p}}^{m,n}\) will be such that each \(A_i\) has full rank and all \(A_i q_j \) are defined, these conditions do not hold for an arbitrary point \(({\bar{\mathbf {A}}}, {\bar{\mathbf {q}}}, {\bar{\mathbf {p}}}) \in \Gamma _{\mathbf {A}, \mathbf {q}, \mathbf {p}}^{m,n}.\)
 
4
Not every result of successively applying projection and specialization operations to \(\Gamma _{\mathbf {A}, \mathbf {q}, \mathbf {p}}^{m,n}\) is included here. For example \(\Gamma ^{m,n}_{\mathbf {A}}\) and \(\Gamma ^{m,n}_{\mathbf {q}}\) are trivial. Similarly \(\Gamma ^{m,n}_{{\bar{\mathbf {A}}},\mathbf {q},{\bar{\mathbf {p}}}}\) and \(\Gamma ^{m,n}_{\mathbf {A},{\bar{\mathbf {q}}},{\bar{\mathbf {p}}}}\) are defined by linear equations and not interesting for projective cameras. However, this can change as the model for the camera is varied. For example, \(\Gamma ^{m,n}_{\mathbf {A},{\bar{\mathbf {q}}},{\bar{\mathbf {p}}}}\) is an interesting nonlinear variety for Euclidean cameras. See Sect. 8 for more.
 
Literature
1.
Sameer Agarwal, Hon-leung Lee, Bernd Sturmfels, and Rekha R. Thomas, On the existence of epipolar matrices, International Journal of Computer Vision 121 (2017), no. 3, 403–415.MathSciNetCrossRef
2.
Sameer Agarwal, Andrew Pryhuber, and Rekha R. Thomas, Ideals of the Multiview Variety, IEEE Transactions on Pattern Analysis & Machine Intelligence 43 (2021), no. 04, 1279–1292.CrossRef
3.
Chris Aholt, Sameer Agarwal, and Rekha Thomas, A QCQP approach to triangulation, European Conference on Computer Vision, Springer-Verlag, 2012, p. 654–667.
4.
Chris Aholt and Luke Oeding, The ideal of the trifocal variety, Mathematics of Computation 83 (2014), no. 289, 2553–2574.MathSciNetCrossRef
5.
Chris Aholt, Bernd Sturmfels, and Rekha Thomas, A Hilbert scheme in computer vision, Canadian Journal of Mathematics 65 (2013), no. 5, 961–988.MathSciNetCrossRef
6.
Michael F. Atiyah and Ian G. Macdonald, Introduction to Commutative Algebra, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969.
7.
Adrien Bartoli and Peter Sturm, Structure-from-motion using lines: Representation, triangulation, and bundle adjustment, Computer Vision and Image Understanding 100 (2005), no. 3, 416–441.CrossRef
8.
David Bernstein and Andrei Zelevinsky, Combinatorics of maximal minors, Journal of Algebraic Combinatorics 2 (1993), no. 2, 111–121.MathSciNetCrossRef
9.
Adam Boocher, Free resolutions and sparse determinantal ideals, Mathematical Research Letters 19 (2012), no. 4, 805–821.MathSciNetCrossRef
10.
Paul Breiding, Felix Rydell, Elima Shehu, and Angélica Torres, Line multiview varieties, 2022.
11.
Stefan Carlsson and Daphna Weinshall, Dual computation of projective shape and camera positions from multiple images, International Journal of Computer Vision 27 (1998), no. 3, 227–241.CrossRef
12.
Dustin Cartwright and Bernd Sturmfels, The Hilbert scheme of the diagonal in a product of projective spaces, International Mathematics Research Notices 2010 (2010), no. 9, 1741–1771.MathSciNet
13.
Aldo Conca, Emanuela De Negri, and Elisa Gorla, Universal Gröbner bases for maximal minors, International Mathematics Research Notices 2015 (2015), no. 11, 3245–3262.
14.
David A. Cox, The moving curve ideal and the Rees algebra, Theoretical Computer Science 392 (2008), no. 1-3, 23–36.
15.
David A. Cox, John Little, and Donal O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 4 ed., Undergraduate Texts in Mathematics, Springer, Cham, 2015.
16.
Song De Ma, Conics-based stereo, motion estimation, and pose determination, International Journal of Computer Vision 10 (1993), no. 1, 7–25.CrossRef
17.
Michel Demazure, Sur deux problemes de reconstruction, Tech. Report RR-0882, INRIA, July 1988.
18.
Jan Draisma, Emil Horobeţ, Giorgio Ottaviani, Bernd Sturmfels, and Rekha R Thomas, The Euclidean distance degree of an algebraic variety, Foundations of Computational Mathematics 16 (2016), no. 1, 99–149.MathSciNetCrossRef
19.
Timothy Duff, Kathlén Kohn, Anton Leykin, and Tomas Pajdla, PL\(_1\)P-Point-Line minimal problems under partial visibility in three views, European Conference on Computer Vision, Springer, 2020, pp. 175–192.
20.
Olivier D. Faugeras and Bernard 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.
21.
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, Lecture Notes in Math., vol. 961, pp. 103–118, Springer, Berlin, 1982.
22.
23.
Richard Hartley and Andrew Zisserman, Multiple View Geometry in Computer Vision, Cambridge University Press, 2004.CrossRef
24.
Richard I Hartley, An investigation of the essential matrix, Tech. report, General Electric CRD, 1995.
25.
Richard I Hartley, Lines and points in three views and the trifocal tensor, International Journal of Computer Vision 22 (1997), no. 2, 125–140.CrossRef
26.
Richard I Hartley and Peter Sturm, Triangulation, Computer Vision and Image Understanding 68 (1997), no. 2, 146–157.CrossRef
27.
Anders Heyden and Kalle Åström, Algebraic properties of multilinear constraints, Mathematical Methods in the Applied Sciences 20 (1997), no. 13, 1135–1162.ADSMathSciNetCrossRef
28.
Fredrik Kahl and Anders Heyden, Affine structure and motion from points, lines and conics, International Journal of Computer Vision 33 (1999), no. 3, 163–180.CrossRef
29.
Joe Kileel, Minimal problems for the calibrated trifocal variety, SIAM Journal on Applied Algebra and Geometry 1 (2017), no. 1, 575–598.MathSciNetCrossRef
30.
Laurent Kneip, Roland Siegwart, and Marc Pollefeys, Finding the exact rotation between two images independently of the translation, European Conference on Computer Vision, vol. 7577, Springer, 2012, pp. 696–709.
31.
Zuzana Kukelova, Martin Bujnak, and Tomas Pajdla, Polynomial eigenvalue solutions to minimal problems in computer vision, IEEE Transactions on Pattern Analysis and Machine Intelligence 34 (2011), no. 7, 1381–1393.CrossRefPubMed
32.
Viktor Larsson, Kalle Astrom, and Magnus Oskarsson, Efficient solvers for minimal problems by syzygy-based reduction, IEEE Conference on Computer Vision and Pattern Recognition, 2017, pp. 820–829.
33.
Vincent Lepetit, Francesc Moreno-Noguer, and Pascal Fua, EPnP: An accurate\({O}(n)\)solution to the PNP problem, International Journal of Computer Vision 81 (2009), no. 2, 155–166.CrossRef
34.
Max Lieblich and Lucas Van Meter, Two Hilbert schemes in computer vision, SIAM Journal on Applied Algebra and Geometry 4 (2020), no. 2, 297–321.MathSciNetCrossRef
35.
Peter Lindstrom, Triangulation made easy, 2010 IEEE Conference on Computer Vision and Pattern Recognition, 2010, pp. 1554–1561.
36.
H Christopher Longuet-Higgins, A computer algorithm for reconstructing a scene from two projections, Nature 293 (1981), no. 5828, 133–135.ADSCrossRef
37.
Quan-Tuan Luong and Olivier D Faugeras, The fundamental matrix: Theory, algorithms, and stability analysis, International Journal of Computer Vision 17 (1996), no. 1, 43–75.CrossRef
38.
Yi Ma, Stefano Soatto, Jana Košecká, and Shankar Sastry, An Invitation to 3-D Vision: from Images to Geometric Models, vol. 26, Springer, 2004.
39.
Laurentiu G Maxim, Jose I Rodriguez, and Botong Wang, Euclidean distance degree of the multiview variety, SIAM Journal on Applied Algebra and Geometry 4 (2020), no. 1, 28–48.MathSciNetCrossRef
40.
Mateusz Michałek and Bernd Sturmfels, Invitation to Nonlinear Algebra, vol. 211, American Mathematical Society, 2021.
41.
Behrooz Nasihatkon, Richard Hartley, and Jochen Trumpf, A generalized projective reconstruction theorem and depth constraints for projective factorization, International Journal of Computer Vision 115 (2015), no. 2, 87–114.MathSciNetCrossRef
42.
David Nistér, An efficient solution to the five-point relative pose problem, IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (2004), no. 6, 756–770.CrossRefPubMed
43.
44.
Patrik Persson and Kalle Åström, Global trifocal adjustment, Scandinavian Conference on Image Analysis, Springer, 2019, pp. 287–298.
45.
Long Quan, Invariants of six points and projective reconstruction from three uncalibrated images, IEEE Transactions on Pattern Analysis and Machine Intelligence 17 (1995), no. 1, 34–46.CrossRef
46.
Michel Raynaud and Laurent Gruson, Criteres de platitude et de projectivité, Inventiones Mathematicae 13 (1971), no. 1, 1–89.ADSMathSciNetCrossRef
47.
Antonio L Rodríguez, Pedro E López-de Teruel, and Alberto Ruiz, Reduced epipolar cost for accelerated incremental SfM, IEEE Conference on Computer Vision and Pattern Recognition, 2011, pp. 3097–3104.
48.
Ewelina Rupnik and Marc Deseilligny, Towards structureless bundle adjustment with two-and three-view structure approximation, ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, vol. 2, 2020, pp. 71–78.CrossRef
49.
Frederik Schaffalitzky, Andrew Zisserman, Richard I. Hartley, and Philip H. S. Torr, A six point solution for structure and motion, European Conference on Computer Vision (David Vernon, ed.), vol. 1842, Springer, 2000, pp. 632–648.
50.
J. Schneider, C. Stachniss, and W. Förstner, On the quality and efficiency of approximate solutions to bundle adjustment with epipolar and trifocal constraints, ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences IV-2/W3 (2017), 81–88.
51.
Amnon Shashua and Lior Wolf, On the structure and properties of the quadrifocal tensor, European Conference on Computer Vision, Springer, 2000, pp. 710–724.
52.
Richard Steffen, Jan-Michael Frahm, and Wolfgang Förstner, Relative bundle adjustment based on trifocal constraints, European Conference on Computer Vision, Springer, 2010, pp. 282–295.
53.
Henrik Stewénius, Gröbner basis methods for minimal problems in computer vision, PhD thesis 2005.
54.
Henrik Stewénius, Frederik Schaffalitzky, and David Nistér, How hard is 3-view triangulation really?, IEEE International Conference on Computer Vision, vol. 1, 2005, pp. 686–693.
55.
Bernd Sturmfels, Gröbner bases and Convex Polytopes, University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996.
56.
Bernd Sturmfels and Andrei Zelevinsky, Maximal minors and their leading terms, Advances in Mathematics 98 (1993), no. 1, 65–112.MathSciNetCrossRef
57.
Camillo J Taylor and David J Kriegman, Structure and motion from line segments in multiple images, IEEE Transactions on Pattern Analysis and Machine Intelligence 17 (1995), no. 11, 1021–1032.
58.
Sebastian Thrun, Wolfram Burgard, and Dieter Fox, Probabilistic robotics, MIT Press, 2005.
59.
Matthew Trager, Martial Hebert, and Jean Ponce, The joint image handbook, IEEE International Conference on Computer Vision, 2015, pp. 909–917.
60.
Matthew Trager, Martial Hebert, and Jean Ponce, Coordinate-free carlsson-weinshall duality and relative multi-view geometry, IEEE Conference on Computer Vision and Pattern Recognition, 2019, pp. 225–233.
61.
Bill Triggs, Matching Constraints and the Joint Image, IEEE International Conference on Computer Vision, 1995, pp. 338–343.
62.
Bill Triggs, Factorization methods for projective structure and motion, IEEE Conference on Computer Vision and Pattern Recognition, 1996, pp. 845–851.
63.
Bill Triggs, Philip F McLauchlan, Richard I Hartley, and Andrew W Fitzgibbon, Bundle Adjustment—a Modern Synthesis, International Workshop on Vision Algorithms, Springer, 1999, pp. 298–372.
64.
Metadata
Title
An Atlas for the Pinhole Camera
Authors
Sameer Agarwal
Timothy Duff
Max Lieblich
Rekha R. Thomas
Publication date
20-09-2022
Publisher
Springer US
Published in
Foundations of Computational Mathematics / Issue 1/2024
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-022-09592-6

Other articles of this Issue 1/2024

Most Probable Paths for Anisotropic Brownian Motions on Manifolds

Covariance’s Loss is Privacy’s Gain: Computationally Efficient, Private and Accurate Synthetic Data

  • Open Access

Adversarial Manifold Estimation

Efficient Computation of the Zeros of the Bargmann Transform Under Additive White Noise

  • Open Access

The Bubble Transform and the de Rham Complex

Functional Equivariance and Conservation Laws in Numerical Integration

Premium Partner

    Image Credits