Robust Model Reasoning and Fitting via Dual Sparsity Pursuit

Xingyu Jiang, Jiayi Ma

Introduction

This paper introduces Dual Sparsity Pursuit (DSP), a unified optimization framework that simultaneously handles outlier rejection, model type identification (reasoning), and parameter estimation. By treating geometric fitting as a sparse subspace recovery problem, the authors achieve state-of-the-art robustness against extreme noise and outliers without needing to know the exact geometric model type in advance.

The Challenge: Outliers and Model Ambiguity

In computer vision, "geometric model fitting" is the process of finding the mathematical rule (like a line, a plane, or a complex camera motion matrix) that best explains a set of data points. This is notoriously difficult for two main reasons:

  1. Outliers: Real-world data is messy. Sensors produce noise, and matching algorithms produce outliers (false correspondences) that can easily derail standard fitting methods.
  2. Model Ambiguity: Most algorithms, like the famous RANSAC, require you to define the target model upfront (e.g., "find a plane"). But in many scenarios, the underlying geometry is unknown. Is the camera looking at a flat wall (Homography) or a complex 3D scene (Fundamental Matrix)? Choosing the wrong model leads to poor results.

Existing solutions often rely on "hypothesize-and-verify" loops or "model selection" metrics that are computationally expensive and prone to errors when outliers dominate the data.

The Solution: Dual Sparsity Pursuit (DSP)

The authors propose a shift from discrete sampling to continuous optimization. Their approach relies on several key technical pillars:

Sparse Subspace Recovery (SSR)

Instead of fitting directly in the original space, the authors "over-embed" the data into a higher-dimensional space. In this expanded space, the true geometric model appears as a "sparse" subspace. By searching for the sparsest solution that fits the data, the algorithm naturally gravitates toward the simplest, most accurate model.

Illustration of over-embedding data into higher-dimensional spaces to find sparse solutions.

Dual Sparsity Formulation

The optimization objective is considered "dual" because it seeks sparsity in two distinct places simultaneously:

  1. The Model ($X$): Using as few parameters as possible to describe the geometry.
  2. The Errors ($E$): Identifying which data points are outliers (the "sparse" set of points that deviate significantly from the model).

Accelerated Solver

To solve this complex non-convex problem, the authors employ an alternating optimization framework combined with a proximal approximation method. Crucially, they integrate an "optimal" sub-gradient descent (Nesterov-style acceleration). This boosts the convergence rate to $O(1/k^2)$, making it significantly faster than previous global optimization attempts.

Convergence comparison showing the accelerated solver achieving O(1/k^2) rates.

Key Insights

  • Model Reasoning via Sparsity: The most elegant insight is that different models (e.g., Fundamental vs. Homography) have different "intrinsic" sparsities in the over-embedded space. DSP doesn't just fit a model; it "reasons" which model is present by looking at the rank and sparsity of the recovered subspace.
  • Unified Modeling: Instead of having separate, sequential steps for cleaning data and fitting parameters, DSP does everything in one mathematical objective. This prevents errors in one stage from cascading into the next.
  • Robustness to Dominant Outliers: Unlike RANSAC, which struggles exponentially as the outlier ratio climbs, DSP remains stable even when 80% of the data is "garbage," thanks to the global nature of the optimization.

Experimental Results

The authors evaluated DSP across a wide range of benchmarks, including synthetic 2D point sets, real-world two-view datasets (like KITTI, TUM, and Hpatch), and multi-model scenarios.

  • Accuracy: On synthetic data with 80% outliers, DSP correctly identified the model type 99.7% of the time, significantly outperforming traditional criteria like AIC and BIC.
  • Real-World Performance: In two-view geometry tasks, DSP achieved the lowest median geometric error ($E_{med}$) and the lowest failure rate ($FR$) compared to robust baselines like RANSAC, USAC, and MAGSAC++.
  • Efficiency: While deep learning methods (like OANet) are faster on GPUs, DSP is much faster than other "global" optimization methods (like EAS) while maintaining higher accuracy.
  • Applications: The authors successfully applied DSP to Loop Closure Detection in SLAM pipelines, achieving higher recall at 100% precision than existing robust estimators.

Limitations and Future Work

The authors acknowledge that their current formulation is primarily optimized for single-model fitting (finding one dominant structure). While they demonstrated some success in multi-model scenarios by combining DSP with clustering techniques like DBSCAN, the core algorithm isn't yet a "native" multi-model solver.

In future work, the authors plan to integrate multi-model fitting directly into the unified optimization modeling, potentially allowing the algorithm to "reason" about multiple intersecting geometries—such as two different moving cars in a single scene—simultaneously.

Summary updated

Abstract

In this paper, we contribute to solving a threefold problem: outlier rejection, true model reasoning and parameter estimation with a unified optimization modeling. To this end, we first pose this task as a sparse subspace recovering problem, to search a maximum of independent bases under an over-embedded data space. Then we convert the objective into a continuous optimization paradigm that estimates sparse solutions for both bases and errors. Wherein a fast and robust solver is proposed to accurately estimate the sparse subspace parameters and error entries, which is implemented by a proximal approximation method under the alternating optimization framework with the ``optimal'' sub-gradient descent. Extensive experiments regarding known and unknown model fitting on synthetic and challenging real datasets have demonstrated the superiority of our method against the state-of-the-art. We also apply our method to multi-class multi-model fitting and loop closure detection, and achieve promising results both in accuracy and efficiency. Code is released at: https://github.com/StaRainJ/DSP.
BibTeX
@inproceedings{jiang2023robust,
  author = {Xingyu Jiang and Jiayi Ma},
  title = {{Robust Model Reasoning and Fitting via Dual Sparsity Pursuit}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=xRfTcZdQxq},
}
Figure