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:
- Outliers: Real-world data is messy. Sensors produce noise, and matching algorithms produce outliers (false correspondences) that can easily derail standard fitting methods.
- 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.
Dual Sparsity Formulation
The optimization objective is considered "dual" because it seeks sparsity in two distinct places simultaneously:
- The Model ($X$): Using as few parameters as possible to describe the geometry.
- 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.
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