PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Heng Yang, Pasquale Antonante, Vasileios Tzoumas, Luca Carlone

arXiv:1909.08605v4cs.CVcs.ROmath.OC

TL;DR

Least-squares non-minimal solvers are brittle to outliers, while robust costs introduce nonconvexities that impede their use. The paper combines Black-Rangarajan duality, GNC, and non-minimal solvers to obtain robust estimation without an initial guess, achieving strong empirical robustness across spatial-perception tasks and a certifiably optimal SOS solver for shape alignment.

  • Problem

    Most non-minimal solvers use least-squares formulations that are brittle to outliers, whereas robust costs introduce nonconvexities that prevent using existing solvers.

  • Method

    The paper combines Black-Rangarajan duality and GNC with non-minimal solvers, alternating weighted least-squares variable updates and closed-form outlier-process updates.

  • Results

    Across point cloud and mesh registration, pose graph optimization, and shape alignment, the solvers are robust to 70-80% outliers, outperform RANSAC, and are faster than specialized global solvers.

  • Takeaways & Limitations

    The approach extends robust non-minimal estimation across several spatial-perception problems and provides a certifiably optimal SOS-based non-minimal solver for shape alignment.

Abstract

from arXiv · show

Semidefinite Programming (SDP) and Sums-of-Squares (SOS) relaxations have led to certifiably optimal non-minimal solvers for several robotics and computer vision problems. However, most non-minimal solvers rely on least-squares formulations, and, as a result, are brittle against outliers. While a standard approach to regain robustness against outliers is to use robust cost functions, the latter typically introduce other non-convexities, preventing the use of existing non-minimal solvers. In this paper, we enable the simultaneous use of non-minimal solvers and robust estimation by providing a general-purpose approach for robust global estimation, which can be applied to any problem where a non-minimal solver is available for the outlier-free case. To this end, we leverage the Black-Rangarajan duality between robust estimation and outlier processes (which has been traditionally applied to early vision problems), and show that graduated non-convexity (GNC) can be used in conjunction with non-minimal solvers to compute robust solutions, without requiring an initial guess. Although GNC's global optimality cannot be guaranteed, we demonstrate the empirical robustness of the resulting robust non-minimal solvers in applications, including point cloud and mesh registration, pose graph optimization, and image-based object pose estimation (also called shape alignment). Our solvers are robust to 70-80% of outliers, outperform RANSAC, are more accurate than specialized local solvers, and faster than specialized global solvers. We also propose the first certifiably optimal non-minimal solver for shape alignment using SOS relaxation.

I. INTRODUCTION

The paper reconciles robust estimation with non-minimal solvers by combining Black-Rangarajan duality and graduated non-convexity, without requiring an initial guess. It develops robust solvers across spatial-perception tasks and introduces a certifiably optimal SOS-based solver for shape alignment.

  • Outliers make least-squares solutions poor, limiting existing non-minimal solvers to cases where outliers have already been removed.
  • Robust costs can improve outlier handling, but nonconvex losses limit the application of existing non-minimal solvers.Examples include Huber, truncated least squares, and Geman-McClure costs.
  • The proposed general-purpose algorithm combines non-minimal solvers with GNC to solve robust estimation problems without an initial guess.The approach is motivated by reconciling non-minimal solvers and robust estimation.
  • Black-Rangarajan duality and GNC are combined with non-minimal solvers for mesh registration, pose graph optimization, and image-based object pose estimation.The paper extends techniques previously used in early vision problems to spatial perception.
  • The method alternates a weighted least-squares variable update using a non-minimal solver with a closed-form outlier-process weight update.This construction is tailored to Geman-McClure and truncated least-squares costs.
  • The solvers tolerate 70-80% outliers, outperform RANSAC, exceed specialized local solvers in accuracy, and surpass specialized global solvers in speed.They are demonstrated on point cloud registration, mesh registration, pose graph optimization, and shape alignment.

II. RELATED WORK

Prior work spans minimal and non-minimal solvers, global robust methods, and local robust optimization, but robust non-minimal estimation remains broadly limited.

  • Minimal and Non-minimal Solvers: Minimal solvers use the smallest measurement sets, whereas non-minimal solvers exploit redundancy to reduce sensitivity to measurement noise.
  • Minimal and Non-minimal Solvers: SDP and SOS relaxations provide global or certifiable solutions for several non-minimal problems, but shape alignment lacks a certifiably optimal non-minimal solver.
  • Global Methods: Global robust methods include RANSAC, adaptive trimming, graph-based pruning, and branch-and-bound, with different solver assumptions and computational trade-offs.
  • Global Methods: Robust M-estimation methods use costs such as TLS, ℓ1, or Huber, but existing approaches can scale exponentially or target specific problem classes.
  • GNC Methods: GNC gradually transforms a convex surrogate into the original non-convex cost, but its broader spatial-perception use has been limited by missing non-minimal solvers.
  • Local Methods and Black-Rangarajan Duality: Local robust methods iteratively refine estimates and auxiliary variables from an initial guess, while Black-Rangarajan formulations remain non-convex and can yield brittle local solutions.
  • Local Methods and Black-Rangarajan Duality: The Black-Rangarajan duality represents robust estimation through measurement weights and an outlier-process penalty, but the resulting problem remains difficult because of non-convexity.

B. Graduated Non-Convexity (GNC)

GNC solves non-convex optimization by traversing surrogate costs controlled by µ, beginning with a convex approximation and gradually recovering the original robust cost.

  • GNC introduces a surrogate ρ_µ governed by µ, requiring convexity for one parameter value and recovery of the original cost in a limit.
  • The solution at each µ becomes the initial guess for the next surrogate as the optimization gradually increases non-convexity.
  • Geman-McClure: For Geman-McClure, the surrogate is convex for large µ, becomes quadratic as µ approaches infinity, and recovers the original cost at µ = 1.
  • Geman-McClure: GNC-GM therefore minimizes progressively less convex surrogates by decreasing µ toward the original Geman-McClure cost.
  • Truncated Least Squares: For TLS, the surrogate is convex as µ approaches zero and recovers the original truncated least-squares cost as µ approaches infinity.

IV. THE GNC ALGORITHM FOR ROBUST ESTIMATION

The proposed algorithm combines GNC, Black-Rangarajan duality, and non-minimal solvers to optimize robust estimation without an initial guess.

  • The method applies GNC to robust estimation without requiring an initial guess.
  • At each outer iteration, the algorithm fixes µ and optimizes a surrogate robust cost rather than the original robust estimation problem directly.
  • Black-Rangarajan duality rewrites the surrogate using an outlier process whose penalty terms can be computed for the surrogate cost.
  • Alternating optimization first updates x with fixed weights and then updates each weight with fixed x.
  • The variable update is a weighted outlier-free problem and can therefore use certifiably optimal non-minimal solvers.
  • The process repeats while changing µ, increasing the amount of non-convexity at each stage.
  • The key novelty is enabling this combination where prior applications were limited by the lack of global solvers for the variable update.

B. The GNC Algorithm with GM and TLS Costs

The paper specializes the GNC algorithm to Geman-McClure and truncated least-squares costs, using alternating weighted updates and cost-specific continuation schedules.

  • GNC-GM: For GNC-GM, minimizing the surrogate is equivalent to an outlier process with a cost-specific penalty term.
  • Weight Updates: The weight updates for both costs are solved in closed form from the current residuals.
  • GNC-TLS: For GNC-TLS, minimizing the surrogate likewise yields an outlier process with its corresponding penalty term.
  • Continuation Schedules: GNC-GM starts from a convex large-µ surrogate and decreases µ toward 1, while GNC-TLS starts near µ = 0 and increases µ toward the original cost.
  • Implementation Details: Each outer iteration performs one variable update and one weight update, with all initial weights set to 1.
  • Implementation Details: The parameter c̄ is chosen as the maximum error expected for inliers for both robust functions.

V. APPLICATIONS AND EXPERIMENTS

The experiments apply GNC-based robust non-minimal solvers to point-cloud and mesh registration under increasing outlier rates. Across these applications, GNC remains effective at high outlier levels while maintaining nearly constant iteration counts.

  • Registration: The applications include point-cloud registration and mesh registration using robustified non-minimal solvers.The registration setup estimates rotation and translation from potentially corrupted point-to-primitive correspondences.
  • Point Cloud Registration: At 90% outliers, RANSAC, GNC-GM, GNC-TLS, and ADAPT all break and have similar accuracy below that ratio.TEASER outperforms the other techniques but does not scale to large problem instances.
  • Point Cloud Registration: At 80% outliers, RANSAC, GNC-GM, and GNC-TLS require average runtimes of 218, 22, and 23ms, respectively.The reported runtimes show substantially lower runtime for both GNC variants than RANSAC in this experiment.
  • Mesh Registration: GNC-GM, GNC-TLS, and ADAPT remain robust against 80% mesh-registration outliers, whereas RANSAC breaks at 50%.At 70% outliers, the figure shows successful registration with GNC-TLS and incorrect registration with RANSAC.
  • Mesh Registration: For mesh registration, ADAPT iterations grow linearly with outliers, while GNC-GM and GNC-TLS iterations remain constant.The comparisons use rotation error, translation error, and iterations over 20 Monte Carlo runs.

B. Pose Graph Optimization

The pose-graph experiments evaluate GNC robustification on standard SLAM datasets, while the shape-alignment subsection develops a certifiably optimal SOS-based non-minimal solver. Both application studies address estimation with corrupted correspondences or measurements.

  • B. Pose Graph Optimization: Pose graph optimization estimates robot poses from pairwise relative pose measurements that may contain outliers.SE-Sync provides a fast non-minimal solver for the outlier-free pose-graph problem.
  • B. Pose Graph Optimization: On INTEL, GNC-GM, GNC-TLS, and ADAPT are insensitive to up to 40% outliers and remain acceptable through 70−80% outliers.GNC-TLS dominates the other techniques on the INTEL dataset.
  • B. Pose Graph Optimization: On CSAIL, GNC-TLS dominates the other techniques and remains robust to 90% outliers.The CSAIL evaluation also reports CPU times for all C++ implementations.
  • C. Shape Alignment: Shape alignment estimates scale, rotation, and translation from 2D image features and 3D object points under weak perspective projection.The correspondences may include outliers, and the residual measures reprojection mismatch.
  • C. Shape Alignment: The SOS relaxation converts the degree-4 shape-alignment optimization into an SDP with certifiable optimality; the relaxation was empirically always exact and took about 80ms.The solver is implemented using GloptiPoly 3 in Matlab.
  • C. Shape Alignment: In FG3DCar experiments, GNC-GM, GNC-TLS, and ADAPT tolerate 70% outliers, while RANSAC breaks at 60%.GNC-GM and GNC-TLS require a roughly constant number of iterations across the tested outlier rates.

VI. CONCLUSIONS

The paper concludes that combining GNC with modern non-minimal solvers provides a deterministic robust-estimation approach across several spatial-perception problems. It reports resilience to many outliers and favorable speed comparisons, while identifying global-convergence guarantees as future work.

  • Contributions: The proposed approach extends Black-Rangarajan duality and GNC to mesh registration, shape alignment, and pose graph optimization.It leverages modern non-minimal solvers for robust estimation.
  • Conclusions: The approach is deterministic, resilient to a large number of outliers, and significantly faster than specialized solvers.The paper presents it as a potential replacement for RANSAC, which requires a minimal solver.
  • Future Work: Future work is to investigate a priori and a posteriori conditions guaranteeing convergence of GNC to globally optimal solutions.The conclusion does not claim that GNC’s global convergence is currently guaranteed.

VII. PROOF OF PROPOSITION 3

The proof derives the outlier-weight update by analyzing the objective’s gradient with respect to each weight. Monotonicity and endpoint behavior establish a unique stationary point, which is the global minimizer.

  • Gradient Analysis: The outlier process uses the objective Φρµ(wi) = µ¯c2(√wi −1)2, whose gradient is analyzed with respect to wi.The derivation follows the Black-Rangarajan procedure.
  • Gradient Analysis: As wi approaches 0, the gradient approaches −∞, while at wi = 1 it is nonnegative.These endpoint properties constrain the location of the weight minimizer.
  • Weight Update: Gradient monotonicity ensures a unique w⋆i where the gradient vanishes.The unique stationary point is identified through the weight-update derivation.
  • Weight Update: The vanishing-gradient point is the global minimizer of the outlier-process objective.This establishes the optimization status of the derived weight update.

VIII. PROOF OF PROPOSITION 4

The proof derives the weight-update rule by differentiating the objective containing the Black–Rangarajan outlier process and analyzing the zero-gradient condition.

  • The outlier process is derived using the Black–Rangarajan procedure, motivating a proof of the weight-update rule.
  • The derivation differentiates the objective function Φρµ(wi) with respect to wi.
  • When wi = 0, the gradient gi equals ˆr2i.
  • The update for ˆr2i follows by setting the gradient gi to zero.

IX. PROOF OF PROPOSITION 6

The proof converts weighted shape alignment into an unconstrained quaternion optimization by eliminating translation and reparameterizing rotation, then recovers the original pose variables from the solution.

  • Proof strategy: The proof has two steps: eliminate translation and convert the problem to a quaternion-based unconstrained optimization.The translation is marginalized first, followed by unit-quaternion reparameterization of rotation.
  • Translation-free Shape Alignment: Setting the translation derivative to zero yields the optimal translation in closed form.
  • Translation-free Shape Alignment: Substituting the optimal translation produces an optimization involving only scale and rotation.
  • Quaternion-based Translation-free Problem: A unit quaternion q represents rotation, whose matrix is linear in the degree-2 monomials [q]2 through a constant matrix A ∈ R9×10.The operator mat converts the resulting vector into a 3 × 3 rotation matrix.
  • Solution recovery: The solver computes Q, g, and h, solves the unconstrained problem using SOS relaxation, and recovers optimal scale, rotation, and translation from v⋆.
  • Quaternion-based Translation-free Problem: Defining v = √s q removes the unit-norm constraint on q while preserving the objective, yielding the unconstrained problem.
Loading 1909.08605v4…