1
|
Yang H, Carlone L. Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2023; 45:2816-2834. [PMID: 35639680 DOI: 10.1109/tpami.2022.3179463] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/15/2023]
Abstract
We propose the first general and scalable framework to design certifiable algorithms for robust geometric perception in the presence of outliers. Our first contribution is to show that estimation using common robust costs, such as truncated least squares (TLS), maximum consensus, Geman-McClure, Tukey's biweight, among others, can be reformulated as polynomial optimization problems (POPs). By focusing on the TLS cost, our second contribution is to exploit sparsity in the POP and propose a sparse semidefinite programming (SDP) relaxation that is much smaller than the standard Lasserre's hierarchy while preserving empirical exactness, i.e., the SDP recovers the optimizer of the nonconvex POP with an optimality certificate. Our third contribution is to solve the SDP relaxations at an unprecedented scale and accuracy by presenting [Formula: see text], a solver that blends global descent on the convex SDP with fast local search on the nonconvex POP. Our fourth contribution is an evaluation of the proposed framework on six geometric perception problems including single and multiple rotation averaging, point cloud and mesh registration, absolute pose estimation, and category-level object pose and shape estimation. Our experiments demonstrate that (i) our sparse SDP relaxation is empirically exact with up to 60%- 90% outliers across applications; (ii) while still being far from real-time, [Formula: see text] is up to 100 times faster than existing SDP solvers on medium-scale problems, and is the only solver that can solve large-scale SDPs with hundreds of thousands of constraints to high accuracy; (iii) [Formula: see text] safeguards existing fast heuristics for robust estimation (e.g., [Formula: see text] or Graduated Non-Convexity), i.e., it certifies global optimality if the heuristic estimates are optimal, or detects and allows escaping local optima when the heuristic estimates are suboptimal.
Collapse
|
2
|
Cheng J, Jin Y, Zhai Z, Liu X, Zhou K. Research on Positioning Method in Underground Complex Environments Based on Fusion of Binocular Vision and IMU. SENSORS (BASEL, SWITZERLAND) 2022; 22:5711. [PMID: 35957268 PMCID: PMC9371209 DOI: 10.3390/s22155711] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 07/08/2022] [Revised: 07/29/2022] [Accepted: 07/29/2022] [Indexed: 06/15/2023]
Abstract
Aiming at the failure of traditional visual slam localization caused by dynamic target interference and weak texture in underground complexes, an effective robot localization scheme was designed in this paper. Firstly, the Harris algorithm with stronger corner detection ability was used, which further improved the ORB (oriented FAST and rotated BRIEF) algorithm of traditional visual slam. Secondly, the non-uniform rational B-splines algorithm was used to transform the discrete data of inertial measurement unit (IMU) into second-order steerable continuous data, and the visual sensor data were fused with IMU data. Finally, the experimental results under the KITTI dataset, EUROC dataset, and a simulated real scene proved that the method used in this paper has the characteristics of stronger robustness, better localization accuracy, small size of hardware equipment, and low power consumption.
Collapse
Affiliation(s)
- Jie Cheng
- School of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018, China; (J.C.); (Z.Z.)
| | - Yinglian Jin
- College of Modern Science and Technology, China Jiliang University, Hangzhou 310018, China;
| | - Zhen Zhai
- School of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018, China; (J.C.); (Z.Z.)
| | - Xiaolong Liu
- Department of Mechanical Engineering, Johns Hopkins University, Baltimore, MD 21211, USA;
| | - Kun Zhou
- School of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018, China; (J.C.); (Z.Z.)
| |
Collapse
|
3
|
Fast Loop Closure Selection Method with Spatiotemporal Consistency for Multi-Robot Map Fusion. APPLIED SCIENCES-BASEL 2022. [DOI: 10.3390/app12115291] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 02/01/2023]
Abstract
This paper presents a robust method based on graph topology to find the topologically correct and consistent subset of inter-robot relative pose measurements for multi-robot map fusion. However, the absence of good prior on relative pose gives a severe challenge to distinguish the inliers and outliers, and once the wrong inter-robot loop closures are used to optimize the pose graph, which can seriously corrupt the fused global map. Existing works mainly rely on the consistency of spatial dimension to select inter-robot measurements, while it does not always hold. In this paper, we propose a fast inter-robot loop closure selection method that integrates the consistency and topology relationship of inter-robot measurements, which both conform to the continuity characteristics of similar scenes and spatiotemporal consistency. Firstly, a clustering method integrating topology correctness of inter-robot loop closures is proposed to split the entire measurement set into multiple clusters. Then, our method decomposes the traditional high-dimensional consistency matrix into the sub-matrix blocks corresponding to the overlapping trajectory regions. Finally, we define the weight function to find the topologically correct and consistent subset with the maximum cardinality, then convert the weight function to the maximum clique problem from graph theory and solve it. We evaluate the performance of our method in a simulation and in a real-world experiment. Compared to state-of-the-art methods, the results show that our method can achieve competitive performance in accuracy while reducing computation time by 75%.
Collapse
|
4
|
Wu J, Liu M, Huang Y, Jin C, Wu Y, Yu C. SE(n)++: An Efficient Solution to Multiple Pose Estimation Problems. IEEE TRANSACTIONS ON CYBERNETICS 2022; 52:3829-3840. [PMID: 32877345 DOI: 10.1109/tcyb.2020.3015039] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/11/2023]
Abstract
In robotic applications, many pose problems involve solving the homogeneous transformation based on the special Euclidean group SE(n) . However, due to the nonconvexity of SE(n) , many of these solvers treat rotation and translation separately, and the computational efficiency is still unsatisfactory. A new technique called the SE(n)++ is proposed in this article that exploits a novel mapping from SE(n) to SO(n + 1) . The mapping transforms the coupling between rotation and translation into a unified formulation on the Lie group and gives better analytical results and computational performances. Specifically, three major pose problems are considered in this article, that is, the point-cloud registration, the hand-eye calibration, and the SE(n) synchronization. Experimental validations have confirmed the effectiveness of the proposed SE(n)++ method in open datasets.
Collapse
|
5
|
Chen Y, Zhao L, Zhang Y, Huang S, Dissanayake G. Anchor Selection for SLAM Based on Graph Topology and Submodular Optimization. IEEE T ROBOT 2022. [DOI: 10.1109/tro.2021.3078333] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/09/2022]
|
6
|
Antonante P, Tzoumas V, Yang H, Carlone L. Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applications. IEEE T ROBOT 2022. [DOI: 10.1109/tro.2021.3094984] [Citation(s) in RCA: 4] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/06/2022]
|
7
|
|
8
|
Li L, Bano S, Deprest J, David A, Stoyanov D, Vasconcelos F. Globally Optimal Fetoscopic Mosaicking Based on Pose Graph Optimisation With Affine Constraints. IEEE Robot Autom Lett 2021. [DOI: 10.1109/lra.2021.3100938] [Citation(s) in RCA: 3] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/07/2022]
|
9
|
Chen Y, Huang S, Zhao L, Dissanayake G. Cramér–Rao Bounds and Optimal Design Metrics for Pose-Graph SLAM. IEEE T ROBOT 2021. [DOI: 10.1109/tro.2020.3001718] [Citation(s) in RCA: 6] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/10/2022]
|
10
|
Do H, Hong S, Kim J. Robust Loop Closure Method for Multi-Robot Map Fusion by Integration of Consistency and Data Similarity. IEEE Robot Autom Lett 2020. [DOI: 10.1109/lra.2020.3010731] [Citation(s) in RCA: 7] [Impact Index Per Article: 1.8] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/08/2022]
|
11
|
Wu F, Beltrame G. Cluster-based Penalty Scaling for Robust Pose Graph Optimization. IEEE Robot Autom Lett 2020. [DOI: 10.1109/lra.2020.3011394] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/07/2022]
|
12
|
Yang H, Antonante P, Tzoumas V, Carlone L. Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection. IEEE Robot Autom Lett 2020. [DOI: 10.1109/lra.2020.2965893] [Citation(s) in RCA: 59] [Impact Index Per Article: 14.8] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/10/2022]
|
13
|
|
14
|
|
15
|
Griffith S, Dellaert F, Pradalier C. Transforming multiple visual surveys of a natural environment into time-lapses. Int J Rob Res 2019. [DOI: 10.1177/0278364919881205] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/16/2022]
Abstract
This article presents a new framework to help transform visual surveys of a natural environment into time-lapses. As data association across year-long variation in appearance continues to represent a formidable challenge, we present success with a map-centric approach, which builds on 3D vision for visual data association. We use a foundation of map point priors and geometric constraints within a dense correspondence image alignment optimization to align images and acquire loop closures between surveys. This framework produces many loop closures between sessions. Outlier loop closures are filtered in the frontend and in the backend to improve robustness. From the result map, the Reprojection Flow algorithm is applied to create time-lapses. The evaluation of our framework on the Symphony Lake Dataset, which has considerable variation in appearance, led to year-long time-lapses of many different scenes. In comparison with another approach based on using iterative closest point (ICP) plus a homography, our framework produced more and better-quality alignments. With many scenes of the 1.3 km environment consistently aligning well in random image pairs, we next produced 100 time-lapses across 37 surveys captured in a year. Approximately one-third had at least 20 (out of usually 33) well-aligned images, which spanned all four seasons. With promising results, we evaluated the pose error of misaligned image pairs and found that improving map consistency could lead to even better results.
Collapse
Affiliation(s)
- Shane Griffith
- College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
- GeorgiaTech Lorraine, Metz, France
| | - Frank Dellaert
- College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
| | - Cédric Pradalier
- College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
- GeorgiaTech Lorraine, Metz, France
| |
Collapse
|
16
|
Lajoie PY, Hu S, Beltrame G, Carlone L. Modeling Perceptual Aliasing in SLAM via Discrete–Continuous Graphical Models. IEEE Robot Autom Lett 2019. [DOI: 10.1109/lra.2019.2894852] [Citation(s) in RCA: 34] [Impact Index Per Article: 6.8] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/10/2022]
|