Minimal Problems in Computer Vision


This page provides a list of papers, software, data, and evaluations for solving minimal problems in computer vision, which is concerned with finding parameters of (geometrical) models from as small (minimal) data sets by solving systems of algebraic equations.

Please send links to papers that should be listed here to Tomas Pajdla (pajdla@cmp.felk.cvut.cz) or Zuzana Kukelova (zukuke@microsoft.com).

Title Authors Published Year Links Problem
Zur Ermittlung eines Objektes aus zwei Perspektiven mit Innerer Orientierung E. Kruppa Z. Sitz.-Ber. Akad.Wiss.,Wien, Math. Naturw. Kl., Abt. IIa., 122:1939-1948 1918 Relative camera pose
An alternative formulation for five point relative pose problem D. Batra, B. Nabbe, M. Hebert IEEE Workshop on Motion and Video Computing 2007 [pdf | http] Relative camera pose, 5pt, calibrated camera
Automatic Generator of Minimal Problem Solvers Z. Kukelova, M. Bujnak, T. Pajdla ECCV 2008, Marseille, France, October 12-18 2008 [pdf | code] Solver generator, GB
An Efficient Hidden Variable Approach to Minimal-Case Camera Motion Estimation R. Hartley, H. Li IEEE Transactions On Pattern Analysis And Machine Intelligence, 34(12):2303-2314, Dec 2012 2012 [pdf | code] Relative camera pose, 5pt, 6pt, calibrated camera, focal length, HV
Polynomial eigenvalue solutions to minimal problems in computer vision Z. Kukelova, M. Bujnak, T. Pajdla IEEE Transactions on Pattern Analysis and Machine Intelligence,34(7):1381-1393, 2012 2012 [pdf | code1 | code2] Relative camera pose, 5pt, 6pt, calibrated camera, focal length, HV
Five-point motion estimation made easy H. Li, R. Hartley ICPR 2006, volume 1, pages 630-633 2006 [pdf | code] Relative camera pose, 5pt, calibrated camera, HV
An efficient solution to the five-point relative pose problem D. Nister IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(6):756-777, June 2004 2004 [pdf] Relative camera pose, 5pt, calibrated camera, CF
Recent developments on direct relative orientation H. Stewenius, C. Engels, D. Nister ISPRS Journal of Photogrammetry and Remote Sensing, 60(4):284-94, 2006 2006 [pdf | http] Relative camera pose, 5pt, calibrated camera, GB
A non-iterative algorithm for determining all essential matrices corresponding to five point pairs J. Philip Photogrammetric Record, 15(88):589-599, 1996 1996 [http] Relative camera pose, 5pt, calibrated camera
Four points in two or three calibrated views: Theory and practice D. Nister, F. Schaffalitzky International Journal of Computer Vision, Volume 67, Number 2, April, 2006 2006 [pdf |http] 4 points in 3 views, calibrated camera
Some results on minimal euclidean reconstruction from four points L. Quan, B. Triggs, B. Mourrain J. Math. Imaging Vis., 24(3)::341–348, 2006 2006 [pdf | http] 4 points in 3 views, calibrated camera
Multi-View Structure Computation without Explicitly Estimating Motion H. Li CVPR 2010 2010 [pdf] 4 points in 3 views, calibrated camera
Improving numerical accuracy of Gröbner basis polynomial equation solver M. Byröd, K. Josephson, K. Åström ICCV 2007 2007 [pdf] Gröbner basis solvers, Relative camera pose, generalized camera, 6pt, focal length, three-view triangulation, GB
A simple solution to the six-point two-view focal-length problem H. Li ECCV 2006 2006 [pdf | code] Relative camera pose, 6pt, focal length, HV
Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography M. A. Fischler, R. C. Bolles Comm. of the ACM, Vol 24, pp 381-395 1981 [http] Absolute camera pose, P3P, calibrated camera, CF
A general solution to the P4P problem for camera with unknown focal length M. Bujnak, Z. Kukelova, T. Pajdla CVPR 2008, Anchorage, Alaska, USA, 2008 [pdfcode] Absolute camera pose, P4Pf, focal length, GB
Camera Pose and Calibration from 4 or 5 Known 3D Points B. Triggs ICCV 1999 1999 [pdf] Absolute camera pose, P4Pf, focal length, uncalibrated camera
A new efficient and direct solution for pose estimation using quadrangular targets: Algorithm and evaluation M. A. Abidi, T. Chandra IEEE PAMI, 17(5):534–538, 1995 1995 [http] Absolute camera pose, P4Pf, focal length, planar scene
Pose Estimation with Radial Distortion and Unknown Focal Length K. Josephson, M. Byröd, K. Åström CVPR 2009, Florida, USA 2009 [pdf | code] Absolute camera pose, P4Pfr, focal length. radial distortion, GB
New efficient solution to the absolute pose problem for camera with unknown focal length and radial distortion M. Bujnak, Z. Kukelova, Pajdla T. ACCV 2010, Queenstown, NZ 2010 [pdf | code] Absolute camera pose, P4Pfr, focal length. radial distortion, GB
Real-time solution to the absolute pose problem with unknown radial distortion and focal length. Z. Kukelova, M. Bujnak, T. Pajdla ICCV 2013, Sydney, Australia 2013 [pdf] Absolute camera pose, P5Pfr, focal length. radial distortion, CF
Closed-form solutions to the minimal absolute pose problems with known vertical direction Z. Kukelova, M. Bujnak, T. Pajdla  ACCV 2010, Queenstown, NZ, November 8-12, 2010 2010 [pdf | code1 | code2] Absolute camera pose, uP2P, uP3Pfr, known vertical direction, IMU, calibrated camera, focal length, radial distortion CF
Pose estimation using both points and lines for geo-localization S. Ramalingam, S. Bouaziz, P. Sturm ICRA 2011 2011 [pdf] Absolute camera pose, calibrated camera, P2P1L, P1P2L, points, lines
3D reconstruction from image collections with a single known focal length M. Bujnak, Z.Kukelova, T. Pajdla ICCV 2009, Kyoto, Japan, September 29 – October 2, 2009 2009 [pdf] Relative camera pose, 6pt-on-off, calibrated-uncalibrated, focal length, GB
Minimal Solutions for Panoramic Stitching M. Brown, R. Hartley, D. Nister CVPR 2007. Minneapolis, USA 2007 [pdf | http] Camera rotation, panorama, homography, focal length, CF, HV
Minimal Solutions for Panoramic Stitching with Radial Distortion M. Byröd, M. Brown, K. Åström  BMVC 2009, London, UK 2009 [pdf | http] Camera rotation, panorama, homography, focal length, radial distortion, GB
Solutions to minimal generalized relative pose problems H. Stewenius, D. Nister, M. Oskarsson, K. Åström OMNIVIS 2005 2005 [pdf] Relative camera pose, generalized camera, calibrated camera, GB
Fast and robust numerical solutions to minimal problems for cameras with radial distortion Z. Kukelova, M. Byröd, K. Josephson, T. Pajdla, K. Åström Computer Vision and Image Understanding, Volume 114, Issue 2, Pages 234-244, ISSN 1077-3142, February 2010 2010 [http | code] Relative camera pose, 6ptr, 9ptr1r2, radial distortion, calibrated camera, uncalibrated camera, different distortions, GB
Fast and robust numerical solutions to minimal problems for cameras with radial distortion M. Byröd, Z. Kukelova, K. Josephson, T. Pajdla, K. Åström CVPR 2008 2008 [pdf | code] Relative camera pose, 6ptr, 9ptr1r2, radial distortion, calibrated camera, uncalibrated camera, different distortions, GB
Two minimal problems for cameras with radial distortion Z. Kukelova, T. Pajdla OMNIVIS 2007, Rio de Janeiro 2007  [pdf] Relative camera pose, 6ptr, 9ptr1r2, radial distortion, calibrated camera, uncalibrated camera, different distortions, GB
A minimal solution to the autocalibration of radial distortion Z. Kukelova, T. Pajdla CVPR 2007 2007  [pdf] Relative camera pose, 8ptr, radial distortion, uncalibrated camera, GB
Simultaneous Linear Estimation of Multipleview Geometry and Lens Distortion A. Fitzgibbon CVPR 2001 2001 [pdf] Relative camera pose, 9ptr, radial distortion, uncalibrated camera, non-miniml, HV
A Non-iterative Method for Correcting Lens Distortion from 9 Point Correspondences H. Li, R. Hartley OMNIVIS 2005 2005 [pdf] Relative camera pose, 9ptr, radial distortion, uncalibrated camera, non-miniml, HV
P2Pi: A minimal solution for the registration of 3D points to 3D planes S. Ramalingam, Y. Taguchi, T. Marks, O.Tuzel ECCV 2011 2011 [pdf] 3D points to 3D planes registration
Hand-Eye Calibration without Hand Orientation Measurement Using Minimal Solution Z. Kukelova, J. Heller, T. Pajdla ACCV 2012, Daejeon, Korea, November 2012 2012 [pdf] Hand-eye calibration, known translation, robotics, GB
Fast Optimal Three View Triangulation M. Byröd, K. Josephson, Kalle Åström ACCV 2007, Tokyo, Japan 2007 [pdf | code] Three view triangulation, L2, GB
A Column-Pivoting Based Strategy for Monomial Ordering in Numerical Gröbner Basis Calculations M. Byröd, K. Josephson, K. Åström ECCV 2008 2008 [pdf] Gröbner basis solvers, Relative camera pose, generalized camera, 6pt, focal length, three-view triangulation, GB
How hard is three-view triangulation really? H. Stewénius, F. Schaffalitzky, D. Nister ICCV 2005 , volume 1, pages 686-693, Beijing China, October 2005 2005 [http] Three view triangulation, L2, GB
Radial Distortion Homography Z. Kukelova, J. Heller  M. Bujnak, T. Pajdla CVPR 2015, Boston, USA 2015 [pdf | code] Homography, H5r1r2, radial distortion, different distortions, GB
Making minimal solvers fast M. Bujnak, Z. Kukelova, T. Pajdla CVPR 2012, Providence, USA, June 16-21, 2012 2012 [pdf] Gröbner basis solvers, Relative camera pose, 6pt, 6pt, focal length, P4Pf, GB
Fast and stable algebraic solution to L2 three-view triangulation Z. Kukelova, M. Bujnak, T. Pajdla 3DV 2013, Seattle, USA, June, 2013 2013 [pdf] Three view triangulation, L2, GB
Singly-Bordered Block-Diagonal Form for Minimal Problem Solvers Z. Kukelova, M. Bujnak, J. Heller, T. Pajdla ACCV 2014, Singapore, November, 2014 2014 [pdf] Gröbner basis solvers, Relative camera pose, Absolute camera pose, 9pt, P4Pf, P4Pfr, focal length, radial distortion, GB
P3.5P: Pose Estimation with Unknown Focal Length Ch. Wu CVPR 2015, Boston, USA 2015 [pdf] Absolute camera pose, P3.5f, focal length, HV

Relative Pose Estimation for a Multi-Camera System with Known Vertical Direction

G. H. Lee, M. Pollefeys,  F. Fraundorfer CVPR 2014 2014 [pdf] Relative camera pose, multicamera system, known vertical direction, IMU, HV
Minimal Solutions for Pose Estimation of a Multi-Camera System G. H. Lee, B. Li., M. Pollefeys,  F. Fraundorfer ISRR 2014 2014 [pdf] Absolute camera pose, multicamera system
A 4-Point Algorithm for Relative Pose Estimation of a Calibrated Camera with a Known Relative Rotation Angle B. Li, L. Heng, G. H. Lee,  M. Pollefeys IROS 2013 2013 [pdf] Relative camera pose, calibrated camera, known relative rotation angle
A Minimal Solution to the Rolling Shutter Pose Estimation Problem O. Saurer, M. Pollefeys, G. H. Lee IROS 2015 2015 [pdf] Absolute camera pose, rolling shutter camera
Minimal Solutions for Pose Estimation of a Multi-Camera System G. H. Lee, B. Li., M. Pollefeys,  F. Fraundorfer International Journal of Robotics Research 2105 [http] Absolute camera pose, multicamera system
R6P – Rolling Shutter Absolute Camera Pose C. Albl, Z. Kukelova, T. Pajdla CVPR 2015 2015 [pdf | http | code] Absolute camera pose, rolling shutter camera, R6P, GB

A homography formulation to the 3pt plus a common direction relative pose problem

O. Saurer, P. Vasseur, C. Demonceaux, F. Fraundorfer ACCV 2014 2014 [pdf] Relative camera pose, known vertical direction, IMU, 3pt

A new solution to the relative orientation problem using only 3 points and the vertical direction

M. Kalantari, A. Hashemi, F. Jung, J.P. Guedon

Journal of Mathematical Imaging and Vision 39, 2011

2011 [http] Relative camera pose, known vertical direction, IMU, 3pt, GB
Two Efficient Solutions for Visual Odometry Using Directional Correspondence O. Naroditsky, X.S. Zhou, J.H. Gallier, S.I. Roumeliotis, K. Daniilidis IEEETrans. Pattern Anal. Mach. Intell. 34, 2012 2012 [http] Relative camera pose, known vertical direction, IMU, 3pt, GB
Algebraic solutions to absolute pose problems M. Bujnak PhD Thesis, Czech Technical University in Prague 2012 [pdf | http] Absolute camera pose, P3P, P4Pf, P4Pfr, uP2P, uP3Pfr, calibrated camera, focal length, radial distortion, known vertical direction, GB
Algebraic Methods in Computer Vision Z. Kukelova PhD Thesis, Czech Technical University in Prague 2013 [pdf | http] Gröbner basis solvers, Relative camera pose, 6pt, 8ptr, 9ptr1r2, 6ptr, focal length, radial distortion, GB
Tractable Algorithms for Robust Model Estimation O. Enqvist , E. Ask, F. Kahl, K. Åström International Journal of Computer Vision 2015 [pdf] Robust fitting using minimal solvers
On the Minimal Problems of Low-Rank Matrix Factorization F. Jiang, M. Oskarsson, K. Åström CVPR 2015 2015 [pdf] Low rank matrix factorization, missing data
Absolute Pose for Cameras Under Flat Refractive Interfaces S. Haner, K. Åström CVPR 2015 2015 [pdf | code] Absolute pose, refractive surfaces
Revisiting Trifocal Tensor Estimation using Lines Y. Kuang, M. Oskarsson, K. Åström ICPR 2014 2014 [pdf] Trifocal tensor, Uncalibrated cameras, 10 lines in 3 views
Prime Rigid Graphs and Multidimensional Scaling with Missing Data M. Oskarsson, K. Åström, A. Torstensson ICPR 2014 2014 [pdf] MDS, missing data
Partial Symmetry in Polynomial Systems and Its Application in Computer Vision Y. Kuang,  Y. Zheng, K. Åström CVPR 2014 2014 [pdf] Gröbner basis solvers, symmetry
Minimal Solvers for Relative Pose with a Single Unknown Radial Distortion Y. Kuang, J.E. Solem, F. Kahl, K. Åström CVPR 2014 2014 [pdf] Relative camera pose, radial distortion
Minimal Solutions for Dual Microphone Rig Self-Calibration S. Zhayida, S. Burgess, Y. Kuang, Yubin, K. Åström European Signal Processing Conference (EUSIPCO 2014) 2014 [pdf] Time-of-arrival, relative pose, MDS , missing data
An Automatic System for Microphone Self-Localization Using Ambient Sound S. Zhayida, F. Andersson, Y. Kuang, K. Åström European Signal Processing Conference (Eusipco 2014) 2014 [pdf] Time-difference-of-arrival, relative pose, MDS, missing data
A Unifying Approach to Minimal Problems in Collinear and Planar TDOA Sensor Network Self-Calibration E. Ask, Y. Kuang, K. Åström European Signal Processing Conference (Eusipco 2014) 2014 [pdf] Time-difference-of-arrival, relative pose, MDS, missing data
A Minimal Solution to Relative Pose with Unknown Focal Length and Radial Distortion F. Jiang, Y. Kuang, J.F. Solem, K. Åström ACCV 2014 2014 [pdf] Relative camera pose, radial distortion, focal length
Stratified Sensor Network Self-Calibration From TDOA Measurements Y. Kuang, K. Åström 21st European Signal Processing Conference 2013 2013 [pdf] Time-difference-of-arrival, relative pose, MDS, missing data
Revisiting the PnP Problem: A Fast, General and Optimal Solution Y. Zheng, Y. Kuang, S. Sugimoto, K. Åström, M. Okutomi ICCV 2013 2013 [pdf] Absolute camera pose, PnP, optimal
Pose Estimation with Unknown Focal Length using Points, Directions and Lines Y. Kuang, K. Åström ICCV 2013 2013 [pdf] Absolute camera pose, points, lines, quivers
Optimal Geometric Fitting Under the Truncated L2 -Norm E. Ask, O. Enqvist, F. Kahl CVPR 2013 2013 [pdf] Optimal truncated L2-fitting using minimal solvers
Minimal Structure and Motion Problems for TOA and TDOA Measurements with Collinearity Constraints E. Ask, S. Burgess, K. Åström 2nd International Conference on Pattern Recognition Applications 2013 [pdf] Time-of-arrival, time-difference-of-arrival, relative pose, collinearity
A Complete Characterization and Solution to the Microphone Position Self-Calibration Problem Y. Kuang, S. Burgess, A. Torstensson, K. Åström The 38th International Conference on Acoustics, Speech, and Signal Processing 2013 [pdf] Time-of-arrival, 3D, 4-6 solver, 5-5 solver
Pose Estimation from Minimal Dual-Receiver Configurations S. Burgess, Y. Kuang, K. Åström ICPR 2012 2012 [pdf] time-of-arrival, pose
Numerically Stable Optimization of Polynomial Solvers for Minimal Problems E. Ask, Y. Kuang, K. Åström ECCV 2012 2012 [pdf] Gröbner basis solvers, making templates small and numerically stable
Exploiting p-Fold Symmetries for Faster Polynomial Equation Solving E. Ask, Y. Kuang,  K. Åström ICPR 2012 2012 [pdf] Gröbner basis solvers, symmetry
Fast and Stable Polynomial Equation Solving and Its Application to Computer Vision M. Byröd, K. Josephson, K. Åström International Journal of Computer Vision 2009 [pdf] Gröbner basis solvers, Numerical stability, GB
The Minimal Structure and Motion Problems with Missing Data for 1D Retina Vision M. Oskarsson, K. Åström, N.Chr. Overgaard Journal of Mathematical Imaging and Vision 2006 [http]
A minimal solution for relative pose with unknown focal length H. Stewenius, D. Nister, F. Kahl, F. Schaffalitzky CVPR 2005 2005 [pdf | code] Relative camera pose, 6pt, focal length, GB
A minimal solution to the generalized 3-point pose problem Nister, D., Stewenius, H. Journal of Mathematical Imaging and Vision (JMIV) 27(1):67-79 2006 [pdf] Generalized P3P
Computing similarity transformations from only image correspondences Sweeney, C., Kneip, L., Höllerer, T. & Turk, M. CVPR 2015 2015 [pdf] Generalized relative pose and scale with known directional correspondence
UPnP: An Optimal O(n) Solution to the Absolute Pose Problem with Universal Applicability Kneip, L., Li, H. & Seo, Y. ECCV 2014 2014 [pdf] P3P & PnP (normal and generalized)
Using multi-camera systems in robotics: Efficient solutions to the NPnP problem Kneip, L., Furgale, P. T. & Siegwart, R. ICRA 2013 2013 [pdf] Generalized PnP
Finding the exact rotation between two images independently of the translation Kneip, L., Roland, S. & Marc, P. ECCV 2012 2012 [pdf] Relative Pose problem
A novel parametrization Of the perspective-three-point problem for a direct computation of absolute camera position and orientation Kneip, L., Scaramuzza, D. & Siegwart, R. CVPR 2013 2013 [pdf] P3P
A Minimal Case Solution to the Calibrated Relative Pose Problem for the Case of Two Known Orientation Angles Fraundorfer, F., Tanskanen, P. & Pollefeys M. ECCV 2010 2010 [pdf] Relative Pose with known direction
An Efficient Minimal Solution for Multi-Camera Motion Ventura, J., Arth, C. & Lepetit, V. ICCV 2015 2015 [pdf] Generalized relative pose
A Minimal Solution to the Generalized Pose-and-Scale Problem Ventura, J., Arth, G., Reitmayr, G. & Schmalstieg. D. CVPR 2014 2014 [pdf] generalized P3P + unknown scale
gDLS: A Scalable Solution to the Generalized Pose and Scale Problem Sweeney, C., Fragoso, V., Hollerer, T. & Turk, M. ECCV 2014 2014 [pdf] Generalized P3P/PnP + unknown scale
Solving for Relative Pose with a Partially Known Rotation is a Quadratic Eigenvalue Problem Sweeney, C., Flynn, J. & Turk, M. 3DV 2014 2014 [pdf] Relative pose with known direction
Efficient Computation of Absolute Pose for Gravity-Aware Augmented Reality Sweeney, C., Flynn, J., Nuernberger, B., Turk, M. & Hollerer, T. IEEE International Symposium on Mixed and Augmented Reality (ISMAR 2015). 2015 [pdf] P3P with known direction
A Direct Least-Squares (DLS) Method for PnP Hesch, J.A. & Roumeliotis, S.I. ICCV 2011 2011 [pdf] P3P/PnP
Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commuta- tive Algebra. D. A. Cox, J. Little, D. O’Shea. Springer 2015 [] An Introduction to Algebraic Geometry. New edition!
Using Algebraic Geometry. D. A. Cox, J. Little, D. O’Shea. Springer 2998 [] More advanced Algebraic Geometry
Computing All Solutions to Polynomial Equations in Economics F. Kubler, P. Renner, K. Schmedders [pdf] Very lightweight intro to polynomial system solving
Estimating the fundamental matrix under pure translation and radial distortion C. Steger ISPRS Journal of Photogrammetry and Remote Sensing, 74:202-217 2012 [pdf] Relative pose, radial distortion, pure translation
A Robust Least Squares Solution to the Calibrated Two-View Geometry with Two Known Orientation Angles G. Nakano and J. Takada VISIGRAPP 2013, Revised Selected Papers 2013 [pdf] Relative camera pose with known vertical direction
Globally Optimal DLS Method for PnP Problem with Cayley Parameterization G. Nakano BMVC 2015 [pdf] P3P and PnP
Indoor robot motion based on monocular images D. Ortin, J. M. M. Montiel Robotica 19:331-342 2001 [pdf] Relative pose for planar motion of a calibrated camera from 2pt
Monocular Visual Odometry and Dense 3D Reconstruction for On-Road Vehicles M. Zhu, S. Ramalingam, Y. Taguchi, T. Garaas ECCV 2012 [pdf] Relative pose for planar motion of a calibrated camera from 2pt, closed form
1-Point-RANSAC Structure from Motion for Vehicle-Mounted Cameras by Exploiting Non-holonomic Constraints D. Scaramuzza IJCV 95:74–85 2011 [pdf] Relative pose for planar non-holonomic motion of a calibrated camera from 1pt
Classifying and solving minimal structure and motion problems with missing data M. Oskarsson, K. Astrom, N. C. Overgaard ICCV 2001 [pdf] 1D and 2D camera, SfM n points in m views classification
Structure from Motion with Wide Circular Field of View Cameras B. Micusik, T. Pajdla IEEE PAMI 18(7):1-15 2006 [pdf] Catadioptric cameras, radial distortion, generalized cameras, PolyEig
Minimal solution for uncalibrated absolute pose problem with a known vanishing point B. Micusik, H. Wildenauer 3DV 2013 [pdf] Absolute pose, known vertical direction, PolyEig
Closed form solution for radial distortion estimation from a single vanishing point B. Micusik, H. Wildenauer BMVC 2013 [pdf] Radial distortion, focal length, known vertical direction, orthogonal vanishing points, PolyEig
Relative pose problem for non-overlapping surveillance cameras with known gravity vector B. Micusik CVPR 2011 [pdf] Relative pose, non-overlapping cameras, PolyEig
Title Authors Published Year [pdf] Problem

(c) Maintained by Tomas Pajdla (pajdla@cmp.felk.cvut.cz) and Zuzana Kukelova (zukuke@microsoft.com). Last update on 10 Jan 2016.