Abstract
Maximum consensus (MC) robust fitting is a fundamental problem in low-level vision to process raw-data. Typically, it firstly finds a consensus set of inliers and then fits a model on the consensus set. This work proposes a new formulation to achieve simultaneous maximum consensus and model estimation (MCME), which has two significant features compared with traditional MC robust fitting. First, it takes fitting residual into account in finding inliers, hence its lowest achievable residual in model fitting is lower than that of MC robust fitting. Second, it has an unconstrained formulation involving binary variables, which facilitates the use of the effective semidefinite relaxation (SDR) method to handle the underlying challenging combinatorial optimization problem. Though still nonconvex after SDR, it becomes biconvex in some applications, for which we use an alternating minimization algorithm to solve. Further, the sparsity of the problem is exploited in combination with low-rank factorization to develop an efficient algorithm. Experiments show that MCME significantly outperforms RANSAC and deterministic approximate MC methods at high outlier ratios. Besides, in rotation and Euclidean registration, it also compares favorably with state-of-the-art registration methods, especially in high noise and outliers.
Introduction
In computer vision, robust fitting is the essential task of extracting mathematical models—such as camera rotations or geometric shapes—from datasets cluttered with "outliers." These outliers are data points that do not conform to the underlying model and can severely degrade estimation accuracy.
Historically, two main strategies have dominated this field:
- Maximum Consensus (MC): Exemplified by RANSAC, this approach seeks the model that agrees with the largest number of points. However, it treats all inliers equally, often ignoring the specific distribution of residuals and potentially settling for a suboptimal fit.
- M-estimation: This method uses robust loss functions to downweight outliers. While statistically powerful, these functions can be computationally difficult to optimize for complex geometric models.
This paper introduces the MCME (Simultaneous Maximum Consensus and Model Estimation) framework. By bridging the gap between MC and M-estimation, MCME identifies inliers and fits the model simultaneously, ensuring a statistically optimal result even in extreme noise.
The MCME Framework
The core of the MCME formulation is the use of a truncated loss function. This function acts as a "hard cutoff": if a point's error is below a threshold $\beta$, it contributes to the model fit; if it exceeds $\beta$, it is assigned a constant penalty and effectively ignored.
Unlike traditional consensus methods that merely count inliers, MCME optimizes the fit within the inlier set. Theoretically, this ensures that MCME will always achieve a lower (better) fitting residual than standard Maximum Consensus. Furthermore, the authors demonstrate that MCME serves as an approximate Maximum Likelihood (ML) estimator, assuming inliers follow a natural exponential distribution (like Gaussian noise) while outliers are uniformly distributed.
Optimization Strategy
Solving the MCME problem is inherently NP-hard due to its combinatorial nature. To address this, the authors propose two primary algorithmic approaches:
Alternating Minimization (AM)
For many applications, the problem exhibits a biconvex structure. The AM algorithm iteratively switches between identifying the optimal inlier set for a fixed model and updating the model parameters for that fixed set. This approach is computationally efficient and converges quickly to a local optimum.
AM with Semidefinite Relaxation (AM-R)
To mitigate the risk of getting stuck in local minima, the authors employ Semidefinite Relaxation (SDR) on the binary inlier/outlier variables. To ensure this remains scalable for large datasets, they utilize Burer-Monteiro factorization. This technique transforms a massive, complex optimization problem into a smaller, unconstrained one that can be solved using standard tools like L-BFGS. This formulation possesses a "hidden convexity" that allows it to be solved significantly faster than previous state-of-the-art SDR methods.
Experimental Highlights
The framework was evaluated across synthetic benchmarks and real-world datasets, including the VGG image dataset and the Stanford Bunny 3D point cloud.
- Extreme Outlier Resilience: In 3D rotation tasks, the AM-R algorithm maintained high accuracy even when 95% of the data were outliers, significantly outperforming RANSAC and other deterministic methods.
- Computational Efficiency: The proposed AM-R algorithm is approximately 1000x faster than previous SDR-based methods like QUASAR for rotation registration.
- Geometric Accuracy: On the VGG homography dataset, MCME achieved the highest average scores compared to L1-relaxation and RANSAC. In 6-DoF registration, it performed comparably to or better than TEASER++, particularly in high-noise scenarios.
Conclusion
MCME provides a robust, unified framework for model fitting that outperforms traditional consensus maximization in both accuracy and resilience to outliers. While the performance depends on the selection of the truncation threshold $\beta$, the method's ability to handle up to 95% outliers while remaining computationally viable marks a significant advancement in robust estimation. Future work may focus on automated hyperparameter tuning to further simplify the deployment of MCME in diverse vision tasks.
Summary updated