Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and\n Applications

摘要

Nonlinear estimation in robotics and vision is typically plagued with\noutliers due to wrong data association, or to incorrect detections from signal\nprocessing and machine learning methods. This paper introduces two unifying\nformulations for outlier-robust estimation, Generalized Maximum Consensus\n(G-MC) and Generalized Truncated Least Squares (G-TLS), and investigates\nfundamental limits, practical algorithms, and applications. Our first\ncontribution is a proof that outlier-robust estimation is inapproximable: in\nthe worst case, it is impossible to (even approximately) find the set of\noutliers, even with slower-than-polynomial-time algorithms (particularly,\nalgorithms running in quasi-polynomial time). As a second contribution, we\nreview and extend two general-purpose algorithms. The first, Adaptive Trimming\n(ADAPT), is combinatorial, and is suitable for G-MC; the second, Graduated\nNon-Convexity (GNC), is based on homotopy methods, and is suitable for G-TLS.\nWe extend ADAPT and GNC to the case where the user does not have prior\nknowledge of the inlier-noise statistics (or the statistics may vary over time)\nand is unable to guess a reasonable threshold to separate inliers from outliers\n(as the one commonly used in RANSAC). We propose the first minimally tuned\nalgorithms for outlier rejection, that dynamically decide how to separate\ninliers from outliers. Our third contribution is an evaluation of the proposed\nalgorithms on robot perception problems: mesh registration, image-based object\ndetection (shape alignment), and pose graph optimization. ADAPT and GNC execute\nin real-time, are deterministic, outperform RANSAC, and are robust up to 80-90%\noutliers. Their minimally tuned versions also compare favorably with the state\nof the art, even though they do not rely on a noise bound for the inliers.\n