Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
International Journal of Computer Vision

10.03.2024

PL\({}_{1}\)P: Point-Line Minimal Problems under Partial Visibility in Three Views

verfasst von: Timothy Duff, Kathlén Kohn, Anton Leykin, Tomas Pajdla

Erschienen in: International Journal of Computer Vision

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We present a complete classification of minimal problems for generic arrangements of points and lines in space observed partially by three calibrated perspective cameras when each line is incident to at most one point. This is a large class of interesting minimal problems that allows missing observations in images due to occlusions and missed detections. There is an infinite number of such minimal problems; however, we show that they can be reduced to 140,616 equivalence classes by removing superfluous features and relabeling the cameras. We also introduce camera-minimal problems, which are practical for designing minimal solvers, and show how to pick a simplest camera-minimal problem for each minimal problem. This simplification results in 74,575 equivalence classes. Only 76 of these were known; the rest are new. To identify problems having potential for practical solving of image matching and 3D reconstruction, we present several natural subfamilies of camera-minimal problems as well as compute solution counts for all camera-minimal problems which have fewer than 300 solutions for generic data.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
1
Under this restriction, in two cameras, the only reduced (camera-)minimal problem is the five-point problem. See Sect. 10 for an explanation.
 
2
In birational geometry, dominant maps are analogs of surjective maps.
 
3
Since we are testing minimality, being minimal is the positive outcome. See Sect. 13.2 for detailed explanation why false positives cannot occur.
 
4
We note that reduced minimal PL\({}_{0}\)Ps are terminal.
 
5
A fiber of a map is the preimage over a single point in its codomain.
 
6
Our computations described in Sect. 8 verify that actually each of the observed features marked as minimal in Table 6 does appear in some minimal PL\({}_{1}\)P.
 
Literatur
Aholt, C., & Oeding, L. (2014). The ideal of the trifocal variety. Mathematics of Computation, 83(289), 2553–2574.MathSciNetCrossRef
Aholt, C., Sturmfels, B., & Thomas, R. (2013). A Hilbert scheme in computer vision. Canadian Journal of Mathematics, 65(5), 961–988.MathSciNetCrossRef
Alismail, H. S., Browning, B., & Dias, M. B. (2011). Evaluating pose estimation methods for stereo visual odometry on robots. In The 11th International Conference on Intelligent Autonomous Systems (IAS-11).
Barath, D. (2018). Five-point fundamental matrix estimation for uncalibrated cameras. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18–22, 2018, pp. 235–243
Barath, D., Toth, T., & Hajder, L. (2017). A minimal solution for two-view focal-length estimation using two affine correspondences. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pp. 2557–2565.
Barath, D., & Hajder, L. (2018). Efficient recovery of essential matrix from two affine correspondences. IEEE Transactions on Image Processing, 27(11), 5328–5337.ADSMathSciNetCrossRefPubMed
Bhayani, S., Kukelova, Z., & Heikkilä, J. (2020). A sparse resultant based method for efficient minimal solvers. In Computer Vision and Pattern Recognition (CVPR).
Byröd, M., Josephson, K., & Åström, K. (2008). A column-pivoting based strategy for monomial ordering in numerical Gröbner basis calculations. In European Conference on Computer Vision (ECCV) (vol. 5305, pp. 130–143). Springer.
Camposeco, F., Sattler, T., & Pollefeys, M. (2016) Minimal solvers for generalized pose and scale estimation from two rays and one point. In ECCV: European Conference on Computer Vision, pp. 202–218
Chen, H. H. (1990). Pose determination from line-to-plane correspondences: existence condition and closed-form solutions. In ICCV, pp. 374–378.
Dhome, M., Richetin, M., Lapreste, J., & Rives, G. (1989). Determination of the attitude of 3D objects from a single perspective view. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(12), 1265–1278.
Duff, T., Kohn, K., Leykin, A., & Pajdla, T. (2019). PLMP: Point-line minimal problems in complete multi-view visibility. In International Conference on Computer Vision (ICCV).
Duff, T., Hill, C., Jensen, A., Lee, K., Leykin, A., & Sommars, J. (2018). Solving polynomial systems via homotopy continuation and monodromy. IMA Journal of Numerical Analysis, 39(3), 1421–1446.MathSciNetCrossRef
Elqursh, A., & Elgammal, A. M. (2011). Line-based relative pose estimation. In Cvpr.
Fabbri, R., Giblin, P. J., & Kimia, B. B. (2012). Camera pose estimation using first-order curve differential geometry. In Proceedings of the European Conference in Computer Vision.
Fabbri, R., Duff, T., Fan, H., Regan, M., da de Costa Pinho, D., Tsigaridas, E., Wampler, C., Hauenstein, J., Giblin, P. J., & Kimia, B. B. (2023). Trifocal relative pose from lines at points. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(6), 7870–7884.CrossRefPubMed
Fabbri, R., Giblin, P., & Kimia, B. (2020). Camera pose estimation using first-order curve differential geometry. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(10), 3321–3332.CrossRef
Fabbri, R., & Kimia, B. B. (2016). Multiview differential geometry of curves. International Journal of Computer Vision, 120(3), 324–346.MathSciNetCrossRef
Fischler, M. A., & Bolles, R. C. (1981). Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6), 381–395.MathSciNetCrossRef
Hartley, R. I. (1997). Lines and points in three views and the trifocal tensor. International Journal of Computer Vision, 22(2), 125–140.CrossRef
Hartley, R., & Li, H. (2012). An efficient hidden variable approach to minimal-case camera motion estimation. IEEE PAMI, 34(12), 2303–2314.CrossRef
Hartley, R., & Zisserman, A. (2003). Multiple view geometry in computer vision. Cambridge.
Hauenstein, J. D., & Rodriguez, J. I. (2019). Multiprojective witness sets and a trace test. To appear in Advances in Geometry. arXiv preprint arXiv:​1507.​07069
Hruby, P., Duff, T., Leykin, A., & Pajdla, T. (2022). Learning to solve hard minimal problems. In Computer vision and pattern recognition (CVPR).
Johansson, B., Oskarsson, M., & Åström, K. (2002). Structure and motion estimation from complex features in three views. In ICVGIP 2002, Proceedings of the Third Indian Conference on Computer Vision, Graphics & Image Processing, Ahmadabad, India, December 16–18 (2002).
Kileel, J. (2017). Minimal problems for the calibrated trifocal variety. SIAM Journal on Applied Algebra and Geometry, 1(1), 575–598.MathSciNetCrossRef
Kneip, L., Scaramuzza, D., & Siegwart, R. (2011). A novel parametrization of the perspective-three-point problem for a direct computation of absolute camera position and orientation. In CVPR: IEEE Conference on Computer Vision and Pattern Recognition, pp. 2969–2976
Kneip, L., Siegwart, R., & Pollefeys, M. (2012). Finding the exact rotation between two images independently of the translation. In ECCV: European Conference on Computer Vision, pp. 696–709.
Kuang, Y., & Åström, K. (2013a) Stratified sensor network self-calibration from TDOA measurements. In 21st European signal processing conference.
Kuang, Y., & Åström, K. (2013b). Pose estimation with unknown focal length using points, directions and lines. In IEEE international conference on computer vision, ICCV 2013, Sydney, Australia, December 1–8, 2013, pp. 529–536
Kukelova, Z., Bujnak, M., & Pajdla, T. (2008). Automatic generator of minimal problem solvers. In European conference on computer vision (ECCV).
Kukelova, Z., Kileel, J., Sturmfels, B., & Pajdla, T. (2017). A clever elimination strategy for efficient minimal solvers. In Computer vision and pattern recognition (CVPR) IEEE.
Larsson, V., Åström, K., & Oskarsson, M. (2017). Efficient solvers for minimal problems by syzygy-based reduction. In 2017 IEEE conference on computer vision and pattern recognition, CVPR 2017, Honolulu, HI, USA, July 21–26, 2017, pp. 2383–2392.
Larsson, V., Åström, K., & Oskarsson, M. (2017a). Efficient solvers for minimal problems by syzygy-based reduction. In Computer vision and pattern recognition (CVPR).
Larsson, V., Åström, K., & Oskarsson, M. (2017b). Polynomial solvers for saturated ideals. In IEEE international conference on computer vision, ICCV 2017, Venice, Italy, October 22–29, 2017, pp. 2307–2316.
Larsson, V., Kukelova, Z., & Zheng, Y. (2017c). Making minimal solvers for absolute pose estimation compact and robust. In International conference on computer vision (ICCV).
Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2), 91–110.CrossRef
Ma, Y., Huang, K., Vidal, R., Kosecka, J., & Sastry, S. (2004). Rank conditions on the multiple-view matrix. International Journal of Computer Vision, 59(2), 115–137.CrossRef
Matas, J., Obdrzálek, S., & Chum, O. (2002). Local affine frames for wide-baseline stereo. In 16th International Conference on Pattern Recognition, ICPR 2002, Quebec, Canada, August 11–15, 2002., pp. 363–366
Miraldo, P., Dias, T., & Ramalingam, S. (2018). A minimal closed-form solution for multi-perspective pose estimation using points and lines. In Computer vision: ECCV 2018—15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part XVI, pp. 490–507.
Miraldo, P., & Araujo, H. (2015). Direct solution to the minimal generalized pose. Cybernetics, IEEE Transactions on, 45(3), 418–429.CrossRef
Mirzaei, F. M., & Roumeliotis, S. I. (2011). Optimal estimation of vanishing points in a manhattan world. In International Conference on Computer Vision (ICCV).
Nistér, D., Naroditsky, O., & Bergen, J. (2004). Visual odometry. In Computer vision and pattern recognition (CVPR), pp. 652–659.
Nistér, D. (2004). An efficient solution to the five-point relative pose problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(6), 756–770.CrossRefPubMed
Nistér, D., & Schaffalitzky, F. (2006). Four points in two or three calibrated views: Theory and practice. International Journal of Computer Vision, 67(2), 211–231.CrossRef
Oskarsson, M., Zisserman, A., & Åström, K. (2004). Minimal projective reconstruction for combinations of points and lines in three views. Image and Vision Computing, 22(10), 777–785.CrossRef
Oxley, J. (2022). Matroid theory. In Handbook of the Tutte polynomial and related topics, pp. 44–85. Chapman and Hall/CRC, London.
Raguram, R., Chum, O., Pollefeys, M., Matas, J., & Frahm, J. (2013). USAC: A universal framework for random sample consensus. IEEE Transactions on Pattern Analysis Machine Intelligence, 35(8), 2022–2038.CrossRefPubMed
Ramalingam, S., & Sturm, P. F. (2008). Minimal solutions for generic imaging models. In CVPR: IEEE Conference on Computer Vision and Pattern Recognition.
Ramalingam, S., Bouaziz, S., & Sturm, P. (2011). Pose estimation using both points and lines for geo-localization. In ICRA, pp. 4716–4723.
Rocco, I., Cimpoi, M., Arandjelović, R., Torii, A., Pajdla, T., & Sivic, J. (2018). Neighbourhood consensus networks
Salaün, Y., Marlet, R., & Monasse, P. (2016). Robust and accurate line- and/or point-based pose estimation without manhattan assumptions. In European Conference on Computer Vision (ECCV).
Sattler, T., Leibe, B., & Kobbelt, L. (2017). Efficient & effective prioritized matching for large-scale image-based localization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(9), 1744–1756.CrossRefPubMed
Saurer, O., Pollefeys, M., & Lee, G. H. (2015). A minimal solution to the rolling shutter pose estimation problem. In Intelligent Robots and Systems (IROS), 2015 IEEE/RSJ international conference on, IEEE, pp. 1328–1334
Schönberger, J. L., & Frahm, J.-M. (2016). Structure-from-motion revisited. In Conference on computer vision and pattern recognition (CVPR).
Snavely, N., Seitz, S. M., & Szeliski, R. (2006). Photo tourism: Exploring photo collections in 3D. In ACM SIGGRAPH.
Snavely, N., Seitz, S. M., & Szeliski, R. (2008). Modeling the world from internet photo collections. International Journal of Computer Vision (IJCV), 80(2), 189–210.CrossRef
Sottile, F. (2001). Enumerative real algebraic geometry. In: Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science.
Stewenius, H., Engels, C., & Nistér, D. (2006). Recent developments on direct relative orientation. ISPRS Journal of Photogrammetry and Remote Sensing, 60, 284–294.ADSCrossRef
Taira, H., Okutomi, M., Sattler, T., Cimpoi, M., Pollefeys, M., Sivic, J., Pajdla, T., Torii, A. (2018). InLoc: Indoor visual localization with dense matching and view synthesis. In CVPR.
Trager, M. (2018). Cameras, shapes, and contours: Geometric models in computer vision. (caméras, formes et contours: modèles géométriques en vision par ordinateur). PhD thesis, École Normale Supérieure, Paris, France
Trager, M., Ponce, J., & Hebert, M. (2016). Trinocular geometry revisited. International Journal Computer Vision, 120, 134–152.
Ventura, J., Arth, C., & Lepetit, V. (2015). An efficient minimal solution for multi-camera motion. In International Conference on Computer Vision (ICCV), pp. 747–755
Xia, G., Delon, J., & Gousseau, Y. (2014). Accurate junction detection and characterization in natural images. International Journal of Computer Vision, 106(1), 31–56.MathSciNetCrossRef
Metadaten
Titel
PLP: Point-Line Minimal Problems under Partial Visibility in Three Views
verfasst von
Timothy Duff
Kathlén Kohn
Anton Leykin
Tomas Pajdla
Publikationsdatum
10.03.2024
Verlag
Springer US
Erschienen in
International Journal of Computer Vision
Print ISSN: 0920-5691
Elektronische ISSN: 1573-1405
DOI
https://doi.org/10.1007/s11263-024-01992-1

Premium Partner

    Bildnachweise