OutlierRobust Spatial Perception: Hardness, GeneralPurpose Algorithms, and Guarantees Spatial perception is the backbone of many robotics applications, and spans a broad range of research problems, including localization and mapping, point cloud alignment, and relative pose estimation from camera images. Robust spatial perception is jeopardized by the presence of incorrect data association, and in general, outliers. Although techniques to handle outliers do exist, they can fail in unpredictable manners (e.g., RANSAC, robust estimators), or can have exponential runtime (e.g., branchandbound). In this paper, we advance the state of the art in outlier rejection by making three contributions. First, we show that even a simple linear instance of outlier rejection is inapproximable: in the worstcase one cannot design a quasipolynomial time algorithm that computes an approximate solution efficiently. Our second contribution is to provide the first perinstance suboptimality bounds to assess the approximation quality of a given outlier rejection outcome. Our third contribution is to propose a simple generalpurpose algorithm, named adaptive trimming, to remove outliers. Our algorithm leverages recentlyproposed global solvers that are able to solve outlierfree problems, and iteratively removes measurements with large errors. We demonstrate the proposed algorithm on three spatial perception problems: 3D registration, twoview geometry, and SLAM. The results show that our algorithm outperforms several stateoftheart methods across applications while being a generalpurpose method.

Efficient Algorithms for Global Outlier Removal in Largescale StructurefromMotion This work addresses the outlier removal problem in largescale global structurefrommotion. In such applications, outlier removal is very useful to mitigate the deterioration caused by mismatches in the feature point matching step. Unlike existing outlier removal methods, we exploit the structure in multiview geometry problems to propose a dimension reduced formulation, based on which two efficient methods have been developed. The first method considers a convex relaxed l 1  minimization and is solved by a single linear programming (LP). The second method approximately solves the ideal l 0  minimization by an iteratively reweighted method. The dimension reduction results in a significant speedup of the new algorithms. Further, the iteratively reweighted method can significantly reduce the possibility of removing true inliers. Results show that, compared with stateoftheart algorithms (e.g., the l 1  method), the proposed algorithms are more than three times faster and meanwhile produce better consensus sets. Matlab code for reproducing the results is available at https:github.comFWenOUTLR.git.