The DOI matches its Crossref record; 53 of the 53 references it cites were found in a registry or an index.
Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection
Open accessAbstract
Semidefinite Programming (SDP) and Sums-of-Squares (SOS) relaxations have led to certifiably optimal non-minimal solvers for several robotics and computer vision problems. However, most non-minimal solvers rely on least squares formulations, and, as a result, are brittle against outliers. While a standard approach to regain robustness against outliers is to use robust cost functions, the latter typically introduce other non-convexities, preventing the use of existing non-minimal solvers. In this letter, we enable the simultaneous use of non-minimal solvers and robust estimation by providing a general-purpose approach for robust global estimation, which can be applied to any problem where a nonminimal solver is available for the outlier-free case. To this end, we leverage the Black-Rangarajan duality between robust estimation and outlier processes (which has been traditionally applied to early vision problems), and show that graduated non-convexity (GNC) can be used in conjunction with non-minimal solvers to compute robust solutions, without requiring an initial guess. we demonstrate the resulting robust non-minimal solvers in applications, including point cloud and mesh registration, pose graph optimization, and image-based object pose estimation (also called shape alignment). Our solvers are robust to 70-80% of outliers, outperform RANSAC, are more accurate than specialized local solvers, and faster than specialized global solvers. We also propose thefirst certifiably optimal non-minimal solver for shape alignment using SOS relaxation.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fischler, M. A., & Bolles, R. C. (1981) · Communications of the ACM · doi:10.1145/358669.358692 · Cited by 25,893
Closed-form solution of absolute orientation using unit quaternions
Horn, B. K. P. (1987) · Journal of the Optical Society of America A · doi:10.1364/josaa.4.000629 · Cited by 4,116
Least-Squares Fitting of Two 3-D Point Sets
Arun, K. S., Huang, T. S., & Blostein, S. D. (1987) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1987.4767965 · Cited by 3,952 · cited 2×
“[35] develop a method for P-REG, using Horn‘s or Arun’s methods [3], [36].”
BackgroundMethodPast, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., Reid, I., & Leonard, J. J. (2016) · IEEE Transactions on Robotics · doi:10.1109/tro.2016.2624754 · Cited by 3,596
Self-citationA volumetric method for building complex models from range images
Curless, B., & Levoy, M. (1996) · Proceedings of the 23rd annual conference on Computer graphics and interactive techniques · doi:10.1145/237170.237269 · Cited by 3,124 · cited 2×
“Performance of GNC-GM and GNC-TLS compared with state-of-the-art techniques on the Bunny dataset [48] for increasing”
MethodPast, present, and future of simultaneous localization and mapping: Toward the robust-perception age
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., Reid, I. D., & Leonard, J. J. (2016) · Zurich Open Repository and Archive (University of Zurich) · doi:10.5167/uzh-138892 · Cited by 3,048
Self-citationMultiple View Geometry in Computer Vision (2nd ed)
Hartley, R. I., & Zisserman, A. (2003) · Cambridge University Press eBooks · Cited by 2,761
Global Optimization with Polynomials and the Problem of Moments
Lasserre, J. B. (2001) · SIAM Journal on Optimization · doi:10.1137/s1052623400366802 · Cited by 2,474
Blake, A., & Zisserman, A. (1987) · The MIT Press eBooks · doi:10.7551/mitpress/7132.001.0001 · Cited by 2,105
G2o: A general framework for graph optimization
Kummerle, R., Grisetti, G., Strasdat, H., Konolige, K., & Burgard, W. (2011) · 2011 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2011.5979949 · Cited by 1,982
Fundamentals of Spacecraft Attitude Determination and Control
Markley, F. L., & Crassidis, J. L. (2014) · doi:10.1007/978-1-4939-0802-8 · Cited by 1,035
Zhou, Q.-Y., Park, J., & Koltun, V. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-46475-6_47 · Cited by 1,028
Rose, K. (1998) · Proceedings of the IEEE · doi:10.1109/5.726788 · Cited by 876
Black, M. J., & Rangarajan, A. (1996) · International Journal of Computer Vision · doi:10.1007/bf00131148 · Cited by 757
Beyond PASCAL: A benchmark for 3D object detection in the wild
Xiang, Y., Mottaghi, R., & Savarese, S. (2014) · IEEE Winter Conference on Applications of Computer Vision · doi:10.1109/wacv.2014.6836101 · Cited by 727
An ICP variant using a point-to-line metric
Censi, A. (2008) · 2008 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.2008.4543181 · Cited by 626
New algorithms for 2D and 3D point matching
Gold, S., Rangarajan, A., Lu, C.-P., Pappu, S., & Mjolsness, E. (1998) · Pattern Recognition · doi:10.1016/s0031-3203(98)80010-1 · Cited by 580
Robust reconstruction of indoor scenes
Choi, S., Zhou, Q.-Y., & Koltun, V. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7299195 · Cited by 555
Sparse Iterative Closest Point
Bouaziz, S., Tagliasacchi, A., & Pauly, M. (2013) · Computer Graphics Forum · doi:10.1111/cgf.12178 · Cited by 534
Switchable constraints for robust pose graph SLAM
Sunderhauf, N., & Protzel, P. (2012) · 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems · doi:10.1109/iros.2012.6385590 · Cited by 344
Robust map optimization using dynamic covariance scaling
Agarwal, P., Tipaldi, G. D., Spinello, L., Stachniss, C., & Burgard, W. (2013) · 2013 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2013.6630557 · Cited by 293
SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group
Rosen, D. M., Carlone, L., Bandeira, A. S., & Leonard, J. J. (2019) · The International Journal of Robotics Research · doi:10.1177/0278364918784361 · Cited by 282
Self-citationInference on networks of mixtures for robust robot mapping
Olson, E., & Agarwal, P. (2013) · The International Journal of Robotics Research · doi:10.1177/0278364913479413 · Cited by 252
Global Optimization through Rotation Space Search
Hartley, R. I., & Kahl, F. (2009) · International Journal of Computer Vision · doi:10.1007/s11263-008-0186-9 · Cited by 227
Guaranteed Outlier Removal for Point Cloud Registration with Correspondences
Bustos, A. P., & Chin, T.-J. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2773482 · Cited by 214
Pairwise Consistent Measurement Set Maximization for Robust Multi-Robot Map Merging
Mangelson, J. G., Dominic, D., Eustice, R. M., & Vasudevan, R. (2018) · 2018 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra.2018.8460217 · Cited by 202
Branch-and-Bound Methods for Euclidean Registration Problems
Olsson, C., Kahl, F., & Oskarsson, M. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.131 · Cited by 161
Consensus set maximization with guaranteed global optimality for robust geometry estimation
Li, H. (2009) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2009.5459398 · Cited by 150
Sparse Representation for 3D Shape Estimation: A Convex Relaxation Approach
Zhou, X., Zhu, M., Leonardos, S., & Daniilidis, K. (2016) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2016.2605097 · Cited by 145
A Polynomial-time Solution for Robust Registration with Extreme Outlier Rates
Yang, H., & Carlone, L. (2019) · Robotics: Science and Systems · doi:10.15607/rss.2019.xv.003 · Cited by 144
Self-citationJointly Optimizing 3D Model Fitting and Fine-Grained Classification
Lin, Y.-L., Morariu, V. I., Hsu, W. H., & Davis, L. S. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-10593-2_31 · Cited by 140
Robust Bundle Adjustment Revisited
Zach, C. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-10602-1_50 · Cited by 109
Modeling Perceptual Aliasing in SLAM via Discrete–Continuous Graphical Models
Lajoie, P., Hu, S., Beltrame, G., & Carlone, L. (2019) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2019.2894852 · Cited by 108
Self-citationConvex Global 3D Registration with Lagrangian Duality
Briales, J., & González-Jiménez, J. (2017) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2017.595 · Cited by 104
Planar Pose Graph Optimization: Duality, Optimal Solutions, and Verification
Carlone, L., Calafiore, G. C., Tommolillo, C., & Dellaert, F. (2016) · IEEE Transactions on Robotics · doi:10.1109/tro.2016.2544304 · Cited by 100
Self-citationOn the Link between Gaussian Homotopy Continuation and Convex Envelopes
Mobahi, H., & Fisher, J. S. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-14612-6_4 · Cited by 95
Lagrangian duality in 3D SLAM: Verification techniques and optimal solutions
Carlone, L., Rosen, D. M., Calafiore, G., Leonard, J. J., & Dellaert, F. (2015) · 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2015.7353364 · Cited by 95
Self-citationRotation Averaging and Strong Duality
Eriksson, A. P., Olsson, C., Kahl, F., & Chin, T.-J. (2018) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2018.00021 · Cited by 95
A Quaternion-Based Certifiably Optimal Solution to the Wahba Problem With Outliers
Yang, H., & Carlone, L. (2019) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2019.00175 · Cited by 95
Self-citationGlobally Optimal Consensus Set Maximization through Rotation Search
Bazin, J., Seo, Y., & Pollefeys, M. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-37444-9_42 · Cited by 85
Inference on networks of mixtures for robust robot mapping
Olson, E., & Agarwal, P. (2012) · Robotics: Science and Systems · doi:10.15607/rss.2012.viii.040 · Cited by 85
Convex Relaxations for Pose Graph Optimization With Outliers
Carlone, L., & Calafiore, G. C. (2018) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2018.2793352 · Cited by 83
Self-citationModeling Perceptual Aliasing in SLAM via Discrete–Continuous Graphical ModelsPreprint
Lajoie, P., Hu, S., Beltrame, G., & Carlone, L. (2019) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 76
Self-citationThe Maximum Consensus Problem: Recent Algorithmic Advances
Chin, T.-J., & Suter, D. (2017) · Synthesis lectures on computer vision · doi:10.2200/s00757ed1v01y201702cov011 · Cited by 70
A Certifiably Globally Optimal Solution to the Non-minimal Relative Pose Problem
Briales, J., Kneip, L., & González-Jiménez, J. (2018) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2018.00023 · Cited by 58
Robust Fitting in Computer Vision: Easy or Hard?
Chin, T.-J., Cai, Z., & Neumann, F. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-01258-8_43 · Cited by 54
Robust Estimation and Applications in Robotics
Bosse, M. C., Agamennoni, G., & Gilitschenski, I. (2016) · Foundations and Trends in Robotics · doi:10.1561/2300000047 · Cited by 53
Outlier-Robust Spatial Perception: Hardness, General-Purpose Algorithms, and Guarantees
Tzoumas, V., Antonante, P., & Carlone, L. (2019) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros40897.2019.8968174 · Cited by 47
Self-citationPfingsthorn, M. F., & Birk, A. (2015) · The International Journal of Robotics Research · doi:10.1177/0278364915585395 · Cited by 42
Agostinho, S., Gomes, J. P., & Bue, A. D. (2022) · Journal of Mathematical Imaging and Vision · doi:10.1007/s10851-022-01133-8 · Cited by 34
Mangelson, J. G., Liu, J., Eustice, R. M., & Vasudevan, R. (2019) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2019.8794454 · Cited by 27
Robust Estimation and Applications in Robotics
Bosse, M. C., Agamennoni, G., & Gilitschenski, I. (2016) · now publishers, Inc. eBooks · doi:10.1561/9781680832150 · Cited by 25
Accelerated Inference in Markov Random Fields via Smooth Riemannian Optimization
Hu, S., & Carlone, L. (2019) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2019.2895124 · Cited by 15
Self-citation
Cited by
TEASER: Fast and Certifiable Point Cloud Registration
Yang, H., Shi, J., & Carlone, L. (2021) · IEEE Transactions on Robotics · doi:10.1109/tro.2020.3033695 · Cited by 895
Self-citationA Survey on Active Simultaneous Localization and Mapping: State of the Art and New Frontiers
Placed, J. A., Strader, J., Carrillo, H., Atanasov, N., Indelman, V., Carlone, L., & Castellanos, J. A. (2023) · IEEE Transactions on Robotics · doi:10.1109/tro.2023.3248510 · Cited by 332
Self-citationKimera-Multi: Robust, Distributed, Dense Metric-Semantic SLAM for Multi-Robot Systems
Tian, Y., Chang, Y., Herrera Arias, F., Nieto-Granda, C., How, J. P., & Carlone, L. (2022) · IEEE Transactions on Robotics · doi:10.1109/tro.2021.3137751 · Cited by 288
Self-citationTsintotas, K. A., Bampis, L., & Gasteratos, A. (2022) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2022.3175656 · Cited by 175
Metadata
- Authors
- Yang, H., Antonante, P., Tzoumas, V., & Carlone, L.
- Venue
- IEEE Robotics and Automation Letters
- Published
- 2020-04
- Volume
- 5
- Issue
- 2
- Pages
- 1127-1134
- ISSN
- 2377-3766 (ISSN-L)
- 2377-3774
- OpenAlex
- W2973258311
- Cited by
- 325
- References
- 53
- FWCI
- 32.18
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.