SAC-GNC: SAmple Consensus for adaptive Graduated Non-Convexity

IEEE/CVF International Conference on Computer Vision (ICCV) 2025, Highlight Paper.

MERL Researchers: Pedro Miraldo.
Joint work with:
Valter Piedade (Instituto Superior Tecnico, Lisboa, Portugal)
Chitturi Sidhartha (Indian Institute of Science, Bengaluru, India)
Jose Gaspar (Instituto Superior Tecnico, Lisboa, Portugal)
Venu Madhav Govindu (Indian Institute of Science, Bengaluru, India)

---

Overview

Outliers pose a major challenge in geometric vision tasks like pose estimation and mapping, often leading to inaccurate results. Although robust loss functions help, they struggle with sensitivity to initialization and selecting the correct shape parameter to differentiate inliers from outliers. Graduated Non-Convexity (GNC) is commonly used to address this, but its fixed annealing strategy can result in suboptimal performance. This paper introduces an adaptive GNC method that dynamically adjusts the shape parameter by sampling multiple annealing options and scoring models to select the best one at each iteration. The approach also includes new stopping criteria and initialization techniques.

Applications

Pose Graph Optimization (PGO) plays a central role in Simultaneous Localization and Mapping (SLAM), particularly in enhancing the global consistency of the estimated trajectory and map. Below, we present results demonstrating the use of SAC-GNC for PGO across four SLAM sequences.

3D registration involves aligning two point clouds captured from different sensor viewpoints and plays a key role in visual odometry, mapping, and other 3D computer vision tasks. In the figure below, we show results on a 3D registration problem. Left: Input scans with the respective point correspondences. Right: Results of our alignment procedure using SAC-GNC.

Method

SAC-GNC introduces an adaptive strategy to improve robustness and efficiency in Graduated Non-Convexity (GNC) frameworks. The method begins with a least squares solution and initializes the shape parameter using residual-based statistics. At every iteration, multiple annealing factors are sampled from a defined range and used to generate hypotheses. Each hypothesis consists of an updated shape parameter and model estimate, which are evaluated using robust scoring functions such as MSAC, RANSAC, or LMedS.

Instead of having a constant annealing update, SAC-GNC maintains a priority queue that enables a search-tree-based exploration of hypotheses. Hypotheses are prioritized by tree depth and score, favoring breadth-first traversal to avoid getting stuck in poor local optima. The method avoids committing to a fixed final shape parameter and instead introduces convergence-based and queue-based stopping criteria.

To ensure efficiency, only a limited number of hypotheses are added to the queue per iteration, and the queue has a capped size. Parameters like the number of trials, queue size, and hypothesis selection thresholds allow for tuning between speed and accuracy. Two variants are proposed: SAC-GNC, which is tuned for speed, and SAC-GNC++, which pursues higher accuracy via deeper search.

The approach is compatible with a wide range of robust cost functions, and its components-adaptive sampling, scoring, and termination-can be parallelized and reused in other GNC settings. Experiments on 3D registration and pose graph optimization demonstrate that SAC-GNC significantly outperforms previous GNC methods and robust estimators, offering improved accuracy, adaptability, and computational efficiency.