L1-Penalized Robust Estimation for a Class of Inverse Problems Arising in Multiview Geometry

Arnak S. Dalalyan, Renaud KerivenNeurIPS 2009 · OpenReview

Authors: Arnak S. Dalalyan and Renaud Keriven

This paper presents a mathematically rigorous yet computationally efficient approach to handling outliers in 3D reconstruction. By bridging the gap between computer vision and sparse recovery statistics, the authors introduce an $L_1$-penalized estimator for multiview geometry. Combining $L_\infty$ data fidelity with an $L_1$ penalty on outliers creates a robust estimation framework that can be solved as a single linear program, outperforming state-of-the-art methods in both speed and accuracy.

The Problem: Sensitivity to Outliers in Multiview Geometry

In multiview geometry, the primary objective is to recover 3D structures and camera positions from a series of 2D images—a classic inverse problem. Traditionally, researchers use the $L_2$-norm (least squares) to minimize reprojection error. However, this leads to "hard" non-convex optimization problems that are prone to getting stuck in local minima.

An attractive alternative is the $L_\infty$-norm. It is computationally elegant because it is quasiconvex and can be solved quickly using linear programming. Unfortunately, $L_\infty$ has a fatal flaw: it is extremely sensitive to outliers. A single misidentified point (a "mismatch" between images) can completely ruin the entire 3D reconstruction. Existing fixes for this sensitivity often lack theoretical guarantees or require the user to guess the number of outliers in advance.

Proposed Method: L1-Penalized Estimation

The authors propose a new estimator based on a Bayesian Maximum A Posteriori (MAP) framework, which elegantly separates structural noise from gross outliers.

  1. The Statistical Model: The 2D measurements are modeled as a function of the 3D geometry plus two distinct types of errors: small, bounded noise (modeled with a uniform distribution) and large outliers (modeled with a sparse vector $\omega$).
  2. The $L_1$ Penalty: To isolate the outliers, the authors place a multivariate Laplace prior on the vector $\omega$. In optimization terms, this translates to an $L_1$-norm penalty. Borrowed from compressed sensing, this penalty promotes "sparsity," operating on the assumption that most entries in $\omega$ should be zero (i.e., most points are inliers).
  3. The Optimization: The resulting objective is to minimize the $L_1$-norm of the outlier vector subject to linear constraints that enforce the geometry and the $L_\infty$ noise bounds.
  4. Two-Step Refinement: For practical application, the authors suggest a two-step approach: first, solve the linear program to identify and remove outliers; second, run a standard $L_\infty$ bisection algorithm on the remaining "clean" data to fine-tune the final reconstruction.

Evaluation: The Dinosaur Sequence

The primary evaluation is conducted on the "Dinosaur Sequence," a standard benchmark in the computer vision community. The dataset consists of 36 images of a toy dinosaur on a turntable, yielding 16,432 image points corresponding to 4,983 scene points.

Crucially, the data is heavily affected by outliers, making "blind" $L_\infty$ methods fail spectacularly by producing non-planar camera paths and messy point clouds.

3D reconstruction of the Dinosaur Sequence. (a) Original image. (b, c) Standard methods fail due to outliers, producing jittery camera paths. (d, e) The proposed L1-penalized method recovers a clean, coplanar camera path and accurate 3D structure.

Key Insights and Results

  • Sparsity as Robustness: The core insight is treating outliers as a sparse signal to be estimated alongside the geometry. If we assume most data points are good, the vector of errors should be mostly zeros.
  • No Need for Outlier Counts: Unlike many robust methods (such as RANSAC or trimmed estimators), this approach does not require the user to specify the number or proportion of outliers beforehand. The $L_1$ penalty discovers them automatically.
  • Theoretical Rigor: The authors provide proofs showing that their estimator is stable and accurate under conditions similar to the "Restricted Isometry Property" found in compressed sensing, offering mathematical guarantees that heuristic methods lack.
  • Speed and Accuracy: The proposed procedure is roughly 50 times faster than the competing SH-procedure (Sim & Hartley), which requires dozens of iterative cycles. By solving just one linear program, the authors' method achieved a maximal reprojection error of 0.62 pixels, compared to 1.33 pixels for the SH-procedure.
  • Qualitative Improvement: Visually, the estimated camera centers using the proposed method were almost perfectly coplanar (as expected for a turntable sequence), whereas competing methods produced significant "jitter" and structural inaccuracies.

Limitations and Future Work

While highly effective, the framework has a few limitations that pave the way for future research:

  • Known Rotations: The paper assumes that camera rotations are already known, focusing only on translation and triangulation. Integrating existing rotation-finding algorithms into this robust framework is a logical next step.
  • The $\sigma$ Parameter: The method requires a parameter $\sigma$ representing the inlier noise level. Choosing an optimal $\sigma$ in fully automated pipelines remains an area for further investigation.
  • Verification of Assumptions: The theoretical guarantees rely on certain geometric assumptions that might be difficult to verify for complex, real-world camera configurations in real-time.

Summary updated

Abstract

We propose a new approach to the problem of robust estimation in multiview geometry. Inspired by recent advances in the sparse recovery problem of statistics, our estimator is defined as a Bayesian maximum a posteriori with multivariate Laplace prior on the vector describing the outliers. This leads to an estimator in which the fidelity to the data is measured by the $L_\infty$-norm while the regularization is done by the $L_1$-norm. The proposed procedure is fairly fast since the outlier removal is done by solving one linear program (LP). An important difference compared to existing algorithms is that for our estimator it is not necessary to specify neither the number nor the proportion of the outliers. The theoretical results, as well as the numerical example reported in this work, confirm the efficiency of the proposed approach.
BibTeX
@inproceedings{dalalyan2009l,
  author = {Arnak S. Dalalyan and Renaud Keriven},
  title = {{L1-Penalized Robust Estimation for a Class of Inverse Problems Arising in Multiview Geometry}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=3TL5Lj8uA4r},
}
Figure