Revisiting Robust Model Fitting Using Truncated Loss

Fei Wen, Hewen Wei, Yipeng Liu, Peilin Liu

TL;DR

This paper introduces SIME, a novel robust model fitting framework that unifies inlier identification and model estimation using a generalized truncated loss. SIME offers a theoretical advantage over traditional Maximum Consensus (MC) methods by achieving lower fitting residuals, and the authors provide efficient alternating minimization (AM) and semidefinite relaxation (SDR)-based algorithms to solve it, demonstrating superior performance in various 2D/3D registration tasks, especially under high outlier conditions.

What Problem Does This Paper Address?

Robust model fitting is crucial in computer vision for tasks like image registration, where data often contains outliers (erroneous measurements). Two dominant approaches are Maximum Consensus (MC) methods (like RANSAC), which first identify inliers and then fit a model, and M-estimators, which directly fit a model using robust loss functions. While effective, MC methods can be sensitive to the choice of inlier threshold and may not achieve the lowest possible fitting residual. M-estimators, on the other hand, don't explicitly identify inliers. This paper addresses the challenge of simultaneously identifying inliers and estimating a robust model with a lower fitting residual than existing methods, particularly in scenarios with a high percentage of outliers.

Methods

The core contribution is the Simultaneous Inlier Identification and Model Estimation (SIME) formulation. SIME uses a generalized truncated loss function that balances fitting residuals with the number of outliers. This formulation is flexible, adapting to both linear and nonlinear residual models.

To solve the non-convex SIME problem, the authors propose two algorithms:

  1. Direct Alternating Minimization (AM): This algorithm iteratively updates the model parameters and inlier/outlier labels.
  2. Semidefinite Relaxation (SDR)-based AM (AM-R): To handle the high nonconvexity, this method employs semidefinite relaxation on the binary inlier variables. It further leverages low-rank factorization and exploits problem sparsity for efficiency.

The paper also theoretically demonstrates that SIME can achieve a lower fitting residual than MC methods.

Datasets

The paper evaluates the proposed algorithms on various standard 2D and 3D registration problems using publicly available datasets, including:

  • VGG dataset: For homography and affinity estimation.
  • Stanford 3D Scanning Repository: For rotation registration (Bunny dataset).
  • Synthetic data: Generated for robust linear regression and 6-DoF Euclidean registration experiments.

No new datasets were introduced.

Key Insights and Ideas

  • Unified Inlier Identification and Model Estimation: SIME elegantly combines the strengths of MC (inlier identification) and M-estimation (direct model fitting) into a single framework.
  • Theoretical Advantage in Fitting Residual: By explicitly considering fitting residuals when identifying inliers, SIME can theoretically achieve a lower fitting residual than traditional MC methods. This is a significant improvement for applications where precise model fitting is paramount.
  • Generalized Truncated Loss: The use of a generalized truncated loss makes SIME applicable to a wider range of geometric residual models, including nonlinear ones, which are common in multi-view geometry.
  • Efficient Optimization Algorithms: The development of both a direct AM and a more robust SDR-based AM (AM-R) algorithm, with the latter benefiting from low-rank factorization and sparsity exploitation, makes SIME practical for real-world applications.
  • Superior Performance in High Outlier Scenarios: Experimental results consistently show SIME (via AM and AM-R) outperforming RANSAC and other deterministic MC methods, especially when the proportion of outliers is high.

Key Results

  • Improved Accuracy: SIME-based methods (AM and AM-R) significantly outperform RANSAC and deterministic approximate MC methods in various registration tasks, particularly at high outlier ratios (e.g., >20%).
  • Competitive with State-of-the-Art: In rotation and Euclidean registration, SIME methods compare favorably with state-of-the-art approaches, especially under high noise and outlier conditions.
  • Efficiency: While the SDR-based AM-R is slower than the direct AM, it offers better robustness. The AM-R algorithm is significantly faster (orders of magnitude) than comparable SDR-based methods like QUASAR due to its efficient formulation and optimization strategy.
  • Lower Fitting Residual: Theoretical analysis and experimental results confirm that SIME achieves lower fitting residuals compared to MC methods.

Limitations and Future Work

  • Local Minima: Both the direct AM and SDR-based AM algorithms are local optimization methods and can be trapped in local minima, although the SDR approach helps mitigate this.
  • Computational Cost of SDR: While more efficient than previous SDR methods, the AM-R algorithm can still be computationally more expensive than simpler methods like RANSAC, especially for very large datasets.
  • Initialization Dependence: The performance of the AM algorithms can be sensitive to initialization, as demonstrated in the experiments.
  • Future Work: The paper suggests exploring the truncated lp loss for different noise distributions (Appendix C) and applying SIME to other computer vision problems. The authors also provide code for their algorithms, encouraging further research and application.

Summary updated

Abstract

Robust fitting is a fundamental problem in low-level vision, which is typically achieved by maximum consensus (MC) estimators to identify inliers first or by M-estimators directly. While these two methods are discriminately preferred in different applications, truncated loss based M-estimators are similar to MC as they can also identify inliers. This work revisits a formulation that achieves simultaneous inlier identification and model estimation (SIME) using truncated loss. It has a generalized form adapts to both linear and nonlinear residual models. We show that as SIME takes fitting residual into account in finding inliers, its lowest achievable residual in model fitting is lower than that of MC robust fitting. Then, an alternating minimization (AM) algorithm is employed to solve the SIME formulation. Meanwhile, a semidefinite relaxation (SDR) embedded AM algorithm is developed in order to ease the high nonconvexity of the SIME formulation. Furthermore, the new algorithms are applied to various 2D/3D registration problems. Experimental results show that the new algorithms significantly outperform RANSAC and deterministic approximate MC methods at high outlier ratios. Besides, in rotation and Euclidean registration problems, the new algorithms also compare favorably with state-of-the-art registration methods, especially in high noise and outliers. Code is available at \textit{https://github.com/FWen/mcme.git}.
BibTeX
@misc{wen2020revisiting,
  author = {Fei Wen and Hewen Wei and Yipeng Liu and Peilin Liu},
  title = {{Revisiting Robust Model Fitting Using Truncated Loss}},
  year = {2020},
  eprint = {2008.01574},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2008.01574},
}
Figure