Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection

3 min read

GNC turns any least-squares solver into an outlier-robust one, without an initial guess. It uses the Black-Rangarajan duality: a robust cost (Geman-McClure or truncated least squares) is rewritten as a weighted least-squares problem plus a penalty on the weights. Graduated non-convexity then starts from a convex surrogate of the robust cost and makes it less convex step by step, controlled by a parameter . Each step alternates two easy moves: solve weighted least squares with an existing non-minimal solver, then update every measurement’s weight in closed form. Measurements with large residuals drift to weight zero, which is outlier rejection with no RANSAC sampling.

Findings

  • Point cloud registration (Bunny, 100 correspondences): GNC-GM, GNC-TLS, RANSAC and ADAPT all hold up to about 90% outliers and break there. TEASER, a specialised global solver, does better.
  • At 80% outliers the average runtimes are 218 ms for RANSAC and 22 to 23 ms for the two GNC variants; GNC’s iteration count stays almost flat as outliers grow, RANSAC’s explodes.
  • Mesh registration: GNC-GM, GNC-TLS and ADAPT are robust to 80% outliers, where RANSAC breaks at 50%.
  • Pose graph optimisation with spoiled loop closures: on INTEL, the robust solvers are insensitive up to 40% outliers and acceptable to 70% to 80%; on CSAIL, GNC-TLS holds to 90%. g2o is not robust, and DCS and PCM depended on their parameters.
  • Shape alignment (FG3DCar, 600 images): robust to 70% outliers, RANSAC breaks at 60%. The paper also gives the first certifiably optimal non-minimal solver for shape alignment, an SOS relaxation that took about 80 ms and was always exact in their tests.

Limits

  • The authors state that GNC’s global optimality “cannot be guaranteed”. It is a heuristic with good empirical behaviour, and convergence conditions are left to future work.
  • It needs a non-minimal solver for the outlier-free problem, which not every estimation problem has.
  • The outlier models in the tests are random. A coordinated set of wrong measurements that agree with each other (perceptual aliasing, or a liar) can look like inliers.
  • The truncation threshold for TLS must be chosen from the inlier noise bound.

Relevance

GNC is the robust back end that Hydra-Multi uses to reject wrong inter-robot loop closures and merges, and TEASER++ uses it for the rotation step, see TEASER. It is a building block of outlier-robust estimation and collaborative SLAM. The gap between random and adversarial outliers is where it meets resilient consensus.