{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:52:37Z","timestamp":1760241157523,"version":"build-2065373602"},"reference-count":42,"publisher":"MDPI AG","issue":"24","license":[{"start":{"date-parts":[[2019,12,13]],"date-time":"2019-12-13T00:00:00Z","timestamp":1576195200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Remote Sensing"],"abstract":"<jats:p>Absolute pose estimation from corrupted point correspondences is typically a problem of estimating parameters from outlier-contaminated data. Conventionally, for a fixed dimensionality d and the number of measurements N, a robust estimation problem cannot be solved exactly faster than     O (  N d  )    . Furthermore, it is almost impossible to remove d from the exponent of the runtime of a globally optimal algorithm. However, absolute pose estimation is a geometric parameter estimation problem, and thus has special constraints. In this paper, we consider pairwise constraints and propose a novel algorithm utilizing global optimization method Branch-and-Bound (BnB) for solving the absolute pose estimation problem. Concretely, we first decouple the rotation and the translation subproblems by utilizing the pairwise constraints, and then we solve the rotation subproblem using the BnB algorithm. Lastly, we estimate the translation based on the optimal rotation by using another BnB algorithm. The proposed algorithm has an approximately linear complexity in the number of correspondences at a given outlier ratio. The advantages of our method were demonstrated via thorough testing on both synthetic and real-world data.<\/jats:p>","DOI":"10.3390\/rs11243007","type":"journal-article","created":{"date-parts":[[2019,12,13]],"date-time":"2019-12-13T11:27:22Z","timestamp":1576236442000},"page":"3007","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Novel Method for the Absolute Pose Problem with Pairwise Constraints"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6468-8233","authenticated-orcid":false,"given":"Yinlong","family":"Liu","sequence":"first","affiliation":[{"name":"Chair of Robotics, Artificial Intelligence and Real-time Systems, Department of Informatics, Technical University of Munich, 85748 Garching, Munich, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4976-7283","authenticated-orcid":false,"given":"Xuechen","family":"Li","sequence":"additional","affiliation":[{"name":"Digital Medical Research Center, School of Basic Medical Sciences, Fudan University, Shanghai 200032, China"},{"name":"Shanghai Key Laboratory of Medical Imaging Computing and Computer Assisted Intervention, Shanghai 200032, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9255-3897","authenticated-orcid":false,"given":"Manning","family":"Wang","sequence":"additional","affiliation":[{"name":"Digital Medical Research Center, School of Basic Medical Sciences, Fudan University, Shanghai 200032, China"},{"name":"Shanghai Key Laboratory of Medical Imaging Computing and Computer Assisted Intervention, Shanghai 200032, China"}]},{"given":"Alois","family":"Knoll","sequence":"additional","affiliation":[{"name":"Chair of Robotics, Artificial Intelligence and Real-time Systems, Department of Informatics, Technical University of Munich, 85748 Garching, Munich, Germany"}]},{"given":"Guang","family":"Chen","sequence":"additional","affiliation":[{"name":"Chair of Robotics, Artificial Intelligence and Real-time Systems, Department of Informatics, Technical University of Munich, 85748 Garching, Munich, Germany"},{"name":"College of Automotive Studies, Tongji University, Shanghai 200092, China"}]},{"given":"Zhijian","family":"Song","sequence":"additional","affiliation":[{"name":"Digital Medical Research Center, School of Basic Medical Sciences, Fudan University, Shanghai 200032, China"},{"name":"Shanghai Key Laboratory of Medical Imaging Computing and Computer Assisted Intervention, Shanghai 200032, China"}]}],"member":"1968","published-online":{"date-parts":[[2019,12,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Campbell, D.J., Petersson, L., Kneip, L., and Li, H. (2018). Globally-Optimal Inlier Set Maximisation for Camera Pose and Correspondence Estimation. IEEE Trans. Pattern Anal. Mach. Intell.","DOI":"10.1109\/ICCV.2017.10"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1016\/j.robot.2011.07.005","article-title":"Robust Camera Pose and Scene Structure Analysis for Service Robotics","volume":"59","author":"Grigorescu","year":"2011","journal-title":"Robot. Auton. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Putra, E.Y., Wahyudi, A.K., and Dumingan, C. (2016, January 28\u201329). A proposed combination of photogrammetry, Augmented Reality and Virtual Reality Headset for heritage visualisation. Proceedings of the 2016 International Conference on Informatics and Computing (ICIC), Mataram, Indonesia.","DOI":"10.1109\/IAC.2016.7905687"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Autran, C., and Gu\u00e9na, F. (2014, January 9\u201312). 3D reconstruction of a disappeared museum. Proceedings of the 2014 International Conference on Virtual Systems Multimedia (VSMM), Hong Kong, China.","DOI":"10.1109\/VSMM.2014.7136697"},{"key":"ref_5","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_6","doi-asserted-by":"crossref","unstructured":"Taira, H., Okutomi, M., Sattler, T., Cimpoi, M., Pollefeys, M., Sivic, J., Pajdla, T., and Torii, A. (2018, January 18\u201322). InLoc: Indoor Visual Localization with Dense Matching and View Synthesis. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Salt Lake City, UT, USA.","DOI":"10.1109\/CVPR.2018.00752"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1744","DOI":"10.1109\/TPAMI.2016.2611662","article-title":"Efficient and Effective Prioritized Matching for Large-Scale Image-Based Localization","volume":"39","author":"Sattler","year":"2017","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1109\/TIP.2003.822592","article-title":"High-accuracy 3D modeling of cultural heritage: the digitizing of Donatello\u2019s \u201cMaddalena\u201d","volume":"13","author":"Guidi","year":"2004","journal-title":"IEEE Trans. Image Process."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Hess, M., Petrovic, V., Meyer, D., Rissolo, D., and Kuester, F. (October, January 28). Fusion of multimodal three-dimensional data for comprehensive digital documentation of cultural heritage sites. Proceedings of the 2015 Digital Heritage, Granada, Spain.","DOI":"10.1109\/DigitalHeritage.2015.7419578"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"2633","DOI":"10.1109\/TVCG.2015.2513408","article-title":"Pose Estimation for Augmented Reality: A Hands-On Survey","volume":"22","author":"Marchand","year":"2016","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"3022","DOI":"10.1109\/TPAMI.2018.2871832","article-title":"Re-weighting and 1-Point RANSAC-Base PnP Solution to Handle Outliers","volume":"41","author":"Zhou","year":"2018","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1455","DOI":"10.1109\/TPAMI.2016.2598331","article-title":"City-Scale Localization for Cameras with Known Vertical Direction","volume":"39","author":"Svarm","year":"2017","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Enqvist, O., and Kahl, F. (2008, January 12\u201318). Robust Optimal Pose Estimation. Proceedings of the 10th European Conference on Computer Vision (ECCV), Marseille, France.","DOI":"10.1007\/978-3-540-88682-2_12"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Enqvist, O., Ask, E., Kahl, F., and Astrom, K. (2012, January 7\u201313). Robust Fitting for Multiple View Geometry. Proceedings of the 12th European Conference on Computer Vision (ECCV), Florence, Italy.","DOI":"10.1007\/978-3-642-33718-5_53"},{"key":"ref_15","unstructured":"Wilcox, R. (1997). Introduction to Robust Estimation and Hypothesis Testing, Elsevier. [3rd ed.]."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Speciale, P., Paudel, D.P., Oswald, M.R., Kroeger, T., Gool, L.V., and Pollefeys, M. (2017, January 21\u201326). Consensus Maximization with Linear Matrix Inequality Constraints. Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Honolulu, Hi, USA.","DOI":"10.1109\/CVPR.2017.536"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Chin, T., Suter, D., Medioni, G., and Dickinson, S. (2017). The Maximum Consensus Problem: Recent Algorithmic Advances, Morgan & Claypool Publishers.","DOI":"10.1007\/978-3-031-01818-3"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Cai, Z., Chin, T.J., Le, H., and Suter, D. (2018, January 8\u201314). Deterministic Consensus Maximization with Biconvex Programming. Proceedings of the European Conference on Computer Vision (ECCV), Munich, Germany.","DOI":"10.1007\/978-3-030-01258-8_42"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Chin, T.J., Cai, Z., and Neumann, F. (2018, January 8\u201314). Robust fitting in computer vision: Easy or hard?. Proceedings of the European Conference on Computer Vision (ECCV), Munich, Germany.","DOI":"10.1007\/978-3-030-01258-8_43"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s11263-014-0760-2","article-title":"Tractable Algorithms for Robust Model Estimation","volume":"112","author":"Enqvist","year":"2015","journal-title":"Int. J. Comput. Vis."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/s00454-006-1267-6","article-title":"On the Least Median Square Problem","volume":"36","author":"Erickson","year":"2006","journal-title":"Discret. Comput. Geom."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Bold, S., and Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/s11263-012-0601-0","article-title":"Rotation Averaging","volume":"103","author":"Hartley","year":"2013","journal-title":"Int. J. Comput. Vis."},{"key":"ref_24","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 2013 IEEE International Conference on Computer Vision (ICCV), Sydney, NSW, Australia.","DOI":"10.1109\/ICCV.2013.291"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Kneip, L., Li, H., and Seo, Y. (2014, January 6\u201312). UPnP: An Optimal O(n) Solution to the Absolute Pose Problem with Universal Applicability. Proceedings of the 13th European Conference on Computer Vision (ECCV), Zurich, Switzerland.","DOI":"10.1007\/978-3-319-10590-1_9"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1145\/358669.358692","article-title":"Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography","volume":"24","author":"Fischler","year":"1981","journal-title":"Commun. ACM"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"2022","DOI":"10.1109\/TPAMI.2012.257","article-title":"USAC: A Universal Framework for Random Sample Consensus","volume":"35","author":"Raguram","year":"2013","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_28","unstructured":"Li, H. (October, January 29). Consensus set maximization with guaranteed global optimality for robust geometry estimation. Proceedings of the IEEE 12th International Conference on Computer Vision (ICCV), Kyoto, Japan."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Ferraz, L., Binefa, X., and Moreno-Noguer, F. (2014, January 24\u201327). Very Fast Solution to the PnP Problem with Algebraic Outlier Rejection. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Columbus, OH, USA.","DOI":"10.1109\/CVPR.2014.71"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Camposeco, F., Sattler, T., Cohen, A., Geiger, A., and Pollefeys, M. (2017, January 21\u201326). Toroidal Constraints for Two-Point Localization Under High Outlier Ratios. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Honolulu, HI, USA.","DOI":"10.1109\/CVPR.2017.709"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Larsson, V., Fredriksson, J., Toft, C., and Kahl, F. (2016, January 19\u201322). Outlier Rejection for Absolute Pose Estimation with Known Orientation. Proceedings of the British Machine Vision Conference, York, UK.","DOI":"10.5244\/C.30.45"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1109\/TPAMI.2008.131","article-title":"Branch-and-Bound Methods for Euclidean Registration Problems","volume":"31","author":"Olsson","year":"2009","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Briales, J., and Gonzalez-Jimenez, J. (2017, January 21\u201326). Convex Global 3D Registration with Lagrangian Duality. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Honolulu, HI, USA.","DOI":"10.1109\/CVPR.2017.595"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/s11263-008-0186-9","article-title":"Global Optimization Through Rotation Space Search","volume":"82","author":"Hartley","year":"2009","journal-title":"Int. J. Comput. Vis."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"2241","DOI":"10.1109\/TPAMI.2015.2513405","article-title":"Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration","volume":"38","author":"Yang","year":"2016","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell. (T-PAMI)"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Li, H., and Hartley, R. (2007, January 14\u201321). The 3D\u20133D Registration Problem Revisited. Proceedings of the IEEE 11th International Conference on Computer Vision, Rio de Janeiro, Brazil.","DOI":"10.1109\/ICCV.2007.4409077"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"2227","DOI":"10.1109\/TPAMI.2016.2517636","article-title":"Fast Rotation Search with Stereographic Projections for 3D Registration","volume":"38","author":"Chin","year":"2016","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Straub, J., Campbell, T., How, J.P., and Fisher, J.W. (2017, January 21\u201326). Efficient Global Point Cloud Alignment Using Bayesian Nonparametric Mixtures. Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Honolulu, HI, USA.","DOI":"10.1109\/CVPR.2017.258"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Ke, T., and Roumeliotis, S.I. (2017, January 21\u201326). An Efficient Algebraic Solution to the Perspective-Three-Point Problem. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Honolulu, HI, USA.","DOI":"10.1109\/CVPR.2017.491"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1109\/TPAMI.2016.2631531","article-title":"Efficient Globally Optimal Consensus Maximisation with Tree Search","volume":"39","author":"Chin","year":"2017","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s10851-009-0161-2","article-title":"Metrics for 3D Rotations: Comparison and Analysis","volume":"35","author":"Huynh","year":"2009","journal-title":"J. Math. Imaging Vis."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/s11263-011-0473-8","article-title":"Interesting Interest Points","volume":"97","author":"Dahl","year":"2012","journal-title":"Int. J. Comput. Vis."}],"container-title":["Remote Sensing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2072-4292\/11\/24\/3007\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:42:16Z","timestamp":1760190136000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2072-4292\/11\/24\/3007"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,13]]},"references-count":42,"journal-issue":{"issue":"24","published-online":{"date-parts":[[2019,12]]}},"alternative-id":["rs11243007"],"URL":"https:\/\/doi.org\/10.3390\/rs11243007","relation":{},"ISSN":["2072-4292"],"issn-type":[{"type":"electronic","value":"2072-4292"}],"subject":[],"published":{"date-parts":[[2019,12,13]]}}}