2019/03/27 by Vasileios Tzoumas, Tzoumas, Vasileios, Pasquale Antonante +3
Computer Science · Engineering · #Advanced Vision and Imaging #Applications (stat.AP) #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #FOS: Electrical engineering #Image and Object Detection Techniques #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Robotics (cs.RO) #Robotics and Sensor-Based Localization #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1903.11683
openalex publication_date 2019/03/27 · openalex created_date 2022/07/24 · openalex updated_date 2026/07/28
Spatial perception is the backbone of many robotics applications, and spans a\nbroad range of research problems, including localization and mapping, point\ncloud alignment, and relative pose estimation from camera images. Robust\nspatial perception is jeopardized by the presence of incorrect data\nassociation, and in general, outliers. Although techniques to handle outliers\ndo exist, they can fail in unpredictable manners (e.g., RANSAC, robust\nestimators), or can have exponential runtime (e.g., branch-and-bound). In this\npaper, we advance the state of the art in outlier rejection by making three\ncontributions. First, we show that even a simple linear instance of outlier\nrejection is inapproximable: in the worst-case one cannot design a\nquasi-polynomial time algorithm that computes an approximate solution\nefficiently. Our second contribution is to provide the first per-instance\nsub-optimality bounds to assess the approximation quality of a given outlier\nrejection outcome. Our third contribution is to propose a simple\ngeneral-purpose algorithm, named adaptive trimming, to remove outliers. Our\nalgorithm leverages recently-proposed global solvers that are able to solve\noutlier-free problems, and iteratively removes measurements with large errors.\nWe demonstrate the proposed algorithm on three spatial perception problems: 3D\nregistration, two-view geometry, and SLAM. The results show that our algorithm\noutperforms several state-of-the-art methods across applications while being a\ngeneral-purpose method.\n