{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T11:11:20Z","timestamp":1774696280759,"version":"3.50.1"},"reference-count":26,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2023,6,14]],"date-time":"2023-06-14T00:00:00Z","timestamp":1686700800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>One of the most-extensively studied problems in three-dimensional Computer Vision is \u201cPerspective-n-Point\u201d (PnP), which concerns estimating the pose of a calibrated camera, given a set of 3D points in the world and their corresponding 2D projections in an image captured by the camera. One solution method that ranks as very accurate and robust proceeds by reducing PnP to the minimization of a fourth-degree polynomial over the three-dimensional sphere S3. Despite a great deal of effort, there is no known fast method to obtain this goal. A very common approach is solving a convex relaxation of the problem, using \u201cSum Of Squares\u201d (SOS) techniques. We offer two contributions in this paper: a faster (by a factor of roughly 10) solution with respect to the state-of-the-art, which relies on the polynomial\u2019s homogeneity; and a fast, guaranteed, easily parallelizable approximation, which makes use of a famous result of Hilbert.<\/jats:p>","DOI":"10.3390\/s23125585","type":"journal-article","created":{"date-parts":[[2023,6,15]],"date-time":"2023-06-15T02:28:56Z","timestamp":1686796136000},"page":"5585","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Fast and Reliable Solution to PnP, Using Polynomial Homogeneity and a Theorem of Hilbert"],"prefix":"10.3390","volume":"23","author":[{"given":"Daniel","family":"Keren","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Haifa, Haifa 3498838, Israel"}]},{"given":"Margarita","family":"Osadchy","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Haifa, Haifa 3498838, Israel"}]},{"given":"Amit","family":"Shahar","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Haifa, Haifa 3498838, Israel"}]}],"member":"1968","published-online":{"date-parts":[[2023,6,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Hartley, R., and Zisserman, A. (2004). Multiple View Geometry in Computer Vision, Cambridge University Press.","DOI":"10.1017\/CBO9780511811685"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s11263-008-0152-6","article-title":"EPnP: An Accurate O(n) Solution to the PnP Problem","volume":"81","author":"Lepetit","year":"2009","journal-title":"Int. J. Comput. Vis."},{"key":"ref_3","unstructured":"Kneip, L., Scaramuzza, D., and Siegwart, R. (2011). Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011, Colorado Springs, CO, USA, 20\u201325 June 2011, IEEE Computer Society."},{"key":"ref_4","unstructured":"Everingham, M., Needham, C.J., and Fraile, R. (2008). Proceedings of the British Machine Vision Conference 2008, Leeds, UK, 1\u20134 September 2008, British Machine Vision Association."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Jubran, I., Fares, F., Alfassi, Y., Ayoub, F., and Feldman, D. (2022, January 23\u201327). Newton-PnP: Real-time Visual Navigation for Autonomous Toy-Drones. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, IROS 2022, Kyoto, Japan.","DOI":"10.1109\/IROS47612.2022.9981922"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Zheng, Y., Kuang, Y., Sugimoto, S., \u00c5str\u00f6m, K., and Okutomi, M. (2013, January 1\u20138). Revisiting the PnP Problem: A Fast, General and Optimal Solution. Proceedings of the IEEE International Conference on Computer Vision, ICCV 2013, Sydney, Australia.","DOI":"10.1109\/ICCV.2013.291"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Fragoso, V., DeGol, J., and Hua, G. (2020, January 13\u201319). gDLS*: Generalized Pose-and-Scale Estimation Given Scale and Gravity Priors. Proceedings of the 2020 IEEE\/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA.","DOI":"10.1109\/CVPR42600.2020.00228"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Briales, J., and Gonz\u00e1lez, J. (2017, January 21\u201326). Convex Global 3D Registration with Lagrangian Duality. Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Honolulu, HI, USA.","DOI":"10.1109\/CVPR.2017.595"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"3314","DOI":"10.1109\/TRO.2022.3155880","article-title":"Quadratic Pose Estimation Problems: Globally Optimal Solutions, Solvability\/Observability Analysis, and Uncertainty Description","volume":"38","author":"Wu","year":"2022","journal-title":"IEEE Trans. Robot."},{"key":"ref_10","first-page":"478","article-title":"A Consistently Fast and Globally Optimal Solution to the Perspective-n-Point Problem","volume":"Volume 12346","author":"Vedaldi","year":"2020","journal-title":"Proceedings of the Computer Vision\u2014ECCV 2020\u201416th European Conference, Glasgow, UK, 23\u201328 August 2020"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Alfassi, Y., Keren, D., and Reznick, B. (2021). The Non-Tightness of a Convex Relaxation to Rotation Recovery. Sensors, 21.","DOI":"10.3390\/s21217358"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1137\/S1052623400366802","article-title":"Global Optimization with Polynomials and the Problem of Moments","volume":"11","author":"Lasserre","year":"2001","journal-title":"SIAM J. Optim."},{"key":"ref_13","unstructured":"Parrilo, P.A., and Sturmfels, B. (2001). Minimizing Polynomial Functions. arXiv."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Laurent, M. (2008). Sums of Squares, Moment Matrices and Optimization over Polynomials, Springer.","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1995","DOI":"10.1137\/080728214","article-title":"Convexity in SemiAlgebraic Geometry and Polynomial Optimization","volume":"19","author":"Lasserre","year":"2009","journal-title":"SIAM J. Optim."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Powers, V. (2021). Certificates of Positivity for Real Polynomials, Springer.","DOI":"10.1007\/978-3-030-85547-5"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s10851-021-01054-y","article-title":"On the Tightness of Semidefinite Relaxations for Rotation Estimation","volume":"64","author":"Brynte","year":"2022","journal-title":"J. Math. Imaging Vis."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1090\/jams\/847","article-title":"Sums of squares and varieties of minimal degree","volume":"29","author":"Blekherman","year":"2015","journal-title":"J. Am. Math. Soc."},{"key":"ref_19","unstructured":"(2023, April 11). Semidefinite Programming (SDP). Available online: https:\/\/sdpa.sourceforge.net\/."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s10107-010-0402-6","article-title":"Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion","volume":"129","author":"Kim","year":"2011","journal-title":"Math. Program."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/s10898-021-01071-6","article-title":"Exact SDP relaxations of quadratically constrained quadratic programs with forest structures","volume":"82","author":"Azuma","year":"2022","journal-title":"J. Glob. Optim."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/BF01443605","article-title":"Ueber die Darstellung definiter Formen als Summe von Formenquadraten","volume":"32","author":"Hilbert","year":"1888","journal-title":"Math. Ann."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Stewart, J.S.G. (1990). Matrix Perturbation Theory, Elsevier.","DOI":"10.1137\/1032121"},{"key":"ref_24","unstructured":"Metaxas, D.N., Quan, L., Sanfeliu, A., and Gool, L.V. (2011). Proceedings of the IEEE International Conference on Computer Vision, ICCV 2011, Barcelona, Spain, 6\u201313 November 2011, IEEE Computer Society."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1444","DOI":"10.1109\/TPAMI.2012.41","article-title":"A Robust O(n) Solution to the Perspective-n-Point Problem","volume":"34","author":"Li","year":"2012","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1109\/34.862199","article-title":"Fast and Globally Convergent Pose Estimation from Video Images","volume":"22","author":"Lu","year":"2000","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/12\/5585\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:55:04Z","timestamp":1760126104000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/12\/5585"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,14]]},"references-count":26,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2023,6]]}},"alternative-id":["s23125585"],"URL":"https:\/\/doi.org\/10.3390\/s23125585","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,14]]}}}