{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:42:10Z","timestamp":1787323330964,"version":"build-2736575974"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"Spanish and Andalusian Governments","award":["600 FPU18\/01526"],"award-info":[{"award-number":["600 FPU18\/01526"]}]},{"name":"Spanish and Andalusian Governments","award":["PID2020-117057"],"award-info":[{"award-number":["PID2020-117057"]}]},{"name":"Spanish and Andalusian Governments","award":["UMA20-FEDERJA-056"],"award-info":[{"award-number":["UMA20-FEDERJA-056"]}]},{"DOI":"10.13039\/501100008530","name":"European Regional Development Fund","doi-asserted-by":"publisher","award":["605"],"award-info":[{"award-number":["605"]}],"id":[{"id":"10.13039\/501100008530","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Imaging Sci."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Estimating the absolute pose of a camera given a set of [Formula: see text] points and their observations is known as the resectioning or Perspective-n-Point (PnP) problem. It is at the core of most computer vision applications and it can be stated as an instance of three-dimensional registration with point-line distances, making the error quadratic in the unknown pose. The PnP problem, though, is nonconvex due to the constraints associated with the rotation, and iterative algorithms may get trapped into any suboptimal solutions without notice. This work proposes an efficient certification algorithm for central and noncentral cameras that either confirms the optimality of a solution or is inconclusive. We exploit different sets of constraints for the rotation to assess their performance in terms of certification. Two of the formulations lack the Linear Independence Constraint Qualification (LICQ) while one of them has more constraints than variables. This hinders the usage of the \u201cstandard\u201d procedure which estimates the Lagrange multipliers in closed-form. To overcome that, we formulate the certification as an eigenvalue optimization and solve it through a line-search method. Our evaluation on synthetic and real data shows that minimal formulations certify most solutions (more than [Formula: see text] on real data) whereas redundant formulations are able to certify all of them and even random problem instances. The proposed algorithm runs in microseconds for all these formulations.<\/jats:p>","DOI":"10.1137\/23m159994x","type":"journal-article","created":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T04:36:26Z","timestamp":1720672586000},"page":"1415-1432","source":"Crossref","is-referenced-by-count":0,"title":["Fast Certifiable Algorithm for the Absolute Pose Estimation of a Camera"],"prefix":"10.1137","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3382-5872","authenticated-orcid":true,"given":"Mercedes","family":"Garcia-Salguero","sequence":"first","affiliation":[{"name":"Perception and Intelligent Robotics (MAPIR) Group, System Engineering and Automation Department, University of Malaga, Campus de Teatinos, 29071, Malaga, Spain."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elijs","family":"Dima","sequence":"additional","affiliation":[{"name":"Ericsson Research, 164 83 Stockholm, Sweden."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1044-4150","authenticated-orcid":true,"given":"Andr\u00e9","family":"Mateus","sequence":"additional","affiliation":[{"name":"Ericsson Research, 164 83 Stockholm, Sweden."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Javier","family":"Gonzalez-Jimenez","sequence":"additional","affiliation":[{"name":"Perception and Intelligent Robotics (MAPIR) Group, System Engineering and Automation Department, University of Malaga, Campus de Teatinos, 29071, Malaga, Spain."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,7,11]]},"reference":[{"key":"ref1","volume-title":"Optimization Algorithms on Matrix Manifolds","author":"Absil P.-A.","year":"2009"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-022-01133-8"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2007.09.014"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2017.2718661"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"J. Briales and J. Gonzalez-Jimenez, Convex global 3d registration with Lagrangian duality, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 4960\u20134969.","DOI":"10.1109\/CVPR.2017.595"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-021-01054-y"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915620033"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-009-0235-z"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"J. Campos, J. R. Cardoso, and P. Miraldo, POSEAMM: A unified framework for solving pose problems using an alternating minimization method, in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2019, pp. 3493\u20133499.","DOI":"10.1109\/ICRA.2019.8793694"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"A. Eriksson, C. Olsson, F. Kahl, and T.J. Chin, Rotation averaging and strong duality, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018, pp. 127\u2013135.","DOI":"10.1109\/CVPR.2018.00021"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/0724043"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.103862"},{"key":"ref14","first-page":"445","author":"Geyer C.","year":"2000","journal-title":"in European Conference on Computer Vision"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"M. D. Grossberg and S. K. Nayar, A general imaging model and a method for finding its parameters, in Proceedings of the IEEE International Conference on Computer Vision, Vol. 2, 2001, pp. 108\u2013115.","DOI":"10.1109\/ICCV.2001.937611"},{"key":"ref16","volume-title":"Multiple View Geometry in Computer Vision","author":"Hartley R.","year":"2003"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"J. A. Hesch and S. I. Roumeliotis, A direct least-squares (DLS) method for PnP, in Proceedings of the IEEE International Conference on Computer Vision, 2011, pp. 383\u2013390.","DOI":"10.1109\/ICCV.2011.6126266"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"ref19","unstructured":"A. Lewis and C. Wylie, A Simple Newton Method for Local Nonsmooth Optimization, preprint, https:\/\/arxiv.org\/abs\/1907.11742, 2019."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900002646"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2023.3240941"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"C. Olsson and A. Eriksson, Solving quadratically constrained geometrical problems using Lagrangian duality, in Proceedings of the IEEE International Conference on Pattern Recognition, IEEE, 2008, pp. 1\u20135.","DOI":"10.1109\/ICPR.2008.4761896"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/0609021"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/S089547989324598X"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918784361"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"T. Sch\u00f6ps, J. L. Sch\u00f6nberger, S. Galliani, T. Sattler, K. Schindler, M. Pollefeys, and A. Geiger, A multi-view stereo benchmark with high-resolution images and multi-camera videos, in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.","DOI":"10.1109\/CVPR.2017.272"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.252"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"G. Schweighofer and A. Pinz, Globally optimal \\(O(n)\\) solution to the PnP problem for general camera models, in British Machine Vision Conference, 2008, pp. 1\u201310.","DOI":"10.5244\/C.22.55"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1137\/0805028"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3006056"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10593-2_2"},{"key":"ref32","volume-title":"Robotics: Science and Systems (RSS), Workshop \u201cThe Problem of Mobile Sensors: Setting Future Goals and Indicators of Progress for SLAM\"","volume":"4","author":"Tron R.","year":"2015"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2018.04.006"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2022.3155880"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-0769-0_24"},{"key":"ref36","doi-asserted-by":"crossref","unstructured":"Y. Zheng, Y. Kuang, S. Sugimoto, K. Astrom, and M. Okutomi, Revisiting the PnP problem: A fast, general and optimal solution, in Proceedings of the IEEE International Conference on Computer Vision, 2013, pp. 2344\u20132351.","DOI":"10.1109\/ICCV.2013.291"},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"L. Zhou and M. Kaess, An efficient and accurate algorithm for the perspecitve-n-point problem, in Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, 2019, pp. 6245\u20136252.","DOI":"10.1109\/IROS40897.2019.8968482"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"L. Zhou, S. Wang, and M. Kaess, A fast and accurate solution for pose estimation from 3d correspondences, in Proceedings of the IEEE International Conference on Robotics and Automation, 2020, pp. 1308\u20131314.","DOI":"10.1109\/ICRA40945.2020.9197023"}],"container-title":["SIAM Journal on Imaging Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M159994X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:55:50Z","timestamp":1787320550000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M159994X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,11]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1137\/23M159994X"],"URL":"https:\/\/doi.org\/10.1137\/23m159994x","relation":{},"ISSN":["1936-4954"],"issn-type":[{"value":"1936-4954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,11]]}}}