Source-linked AI summary
Robust Camera Location Estimation by Convex Programming
Onur Ozyesil, Amit Singer
TL;DR
Camera location estimation in structure from motion is vulnerable to noisy and outlier pairwise directions. The paper characterizes well-posed instances using parallel rigidity and combines robust pairwise-direction estimation with a convex location estimator, reporting highly accurate and sometimes exact recovery.
Problem
Camera location estimation from noisy pairwise directions is sensitive to outlier directions, which can arise from incorrect point correspondences.
Method
The paper uses parallel rigidity to characterize well-posed instances and introduces robust pairwise-direction estimation followed by a convex program for camera locations.
Results
Highly accurate location recovery compared with existing methods and exact recovery under partially corrupted measurements are reported empirically.
Takeaways & Limitations
The formulation can extract well-posed image subsets and recover camera locations exactly when partially corrupted directions leave sufficiently many noiseless directions.
Takeaways & Limitations
The conditions guaranteeing exact recovery with partially corrupted directions remain for future investigation.
Abstract
from arXiv · showhide
$3$D structure recovery from a collection of $2$D images requires the estimation of the camera locations and orientations, i.e. the camera motion. For large, irregular collections of images, existing methods for the location estimation part, which can be formulated as the inverse problem of estimating $n$ locations $\mathbf{t}_1, \mathbf{t}_2, \ldots, \mathbf{t}_n$ in $\mathbb{R}^3$ from noisy measurements of a subset of the pairwise directions $\frac{\mathbf{t}_i - \mathbf{t}_j}{\|\mathbf{t}_i - \mathbf{t}_j\|}$, are sensitive to outliers in direction measurements. In this paper, we firstly provide a complete characterization of well-posed instances of the location estimation problem, by presenting its relation to the existing theory of parallel rigidity. For robust estimation of camera locations, we introduce a two-step approach, comprised of a pairwise direction estimation method robust to outliers in point correspondences between image pairs, and a convex program to maintain robustness to outlier directions. In the presence of partially corrupted measurements, we empirically demonstrate that our convex formulation can even recover the locations exactly. Lastly, we demonstrate the utility of our formulations through experiments on Internet photo collections.
1. Introduction
The paper frames camera location estimation as recovering 3D positions from noisy pairwise directions, a problem vulnerable to outliers from incorrect correspondences. It proposes rigidity-based characterization and robust estimation procedures, with empirical evidence of highly accurate and sometimes exact recovery.
- Problem: Structure from motion recovers 3D structure by estimating camera motion from collections of 2D images.The classical pipeline estimates correspondences and relative poses, then global motion, followed by structure recovery through reprojection-error minimization.
- Problem: Camera location estimation recovers n locations in R^d from a subset of potentially noisy pairwise direction measurements.For camera problems, d = 3; incorrect point correspondences can create direction outliers and destabilize location estimation.
- Existing methods: Existing location estimators have distinct weaknesses, including accumulated errors in incremental methods, clustered solutions from least squares, local minima, and sensitivity to outlier directions.These limitations motivate a robust alternative for large, irregular image collections.
- Contributions: The paper characterizes well-posed location-estimation instances through parallel rigidity and introduces a two-step robust formulation.The steps estimate pairwise directions robustly to correspondence outliers, then estimate camera locations with a convex program robust to corrupted directions.
- Results: Highly accurate location recovery compared to existing methods and exact recovery under partially corrupted measurements are reported in synthetic experiments.The paper also evaluates accuracy and efficiency on real images.
2. Location Estimation
The section characterizes when camera locations are uniquely and stably recoverable from pairwise directions, then develops a convex formulation designed to resist outlier measurements.
- 2.1. Parallel Rigidity: Parallel rigidity characterizes formations whose locations are uniquely realizable up to global translation and scale.
- 2.1. Parallel Rigidity: Parallel rigidity is a generic graph property with a complete combinatorial characterization and efficient testing algorithms.Testing can use pebble-game adaptations with time complexity O(n^2) or a randomized spectral test with time complexity O(m).
- 2.1. Parallel Rigidity: Without parallel rigidity, maximally rigid components can be independently scaled and translated, causing instability under noisy directions.
- 2.2. Robust Location Estimation: The robust location estimator rewrites direction errors as displacement errors and minimizes their sum using unsquared norms.This formulation substitutes displacement-error minimization for direction-error minimization and is intended to limit the influence of large errors.
- 2.2. Robust Location Estimation: The convex LUD formulation drops intrinsic distance constraints, while centering and lower bounds remove translation, scale, and trivial clustered-solution ambiguities.
- 2.2. Robust Location Estimation: For general-position, parallel-rigid formations with noiseless directions, both LUD and CLS recover locations exactly up to congruence.An iteratively reweighted least-squares solver uses quadratic-program approximations and regularization to solve the LUD problem computationally.
3. Robust Pairwise Direction Estimation
The paper estimates pairwise camera directions robustly against outlier point correspondences, then uses these directions in camera-motion estimation. Its robust estimator improves direction accuracy over PCA without significantly increasing pipeline runtime.
- Robust direction estimation: The method robustly estimates pairwise directions despite outlier point correspondences between image pairs.It first estimates camera rotations, then uses epipolar constraints to estimate pairwise direction lines and their signs.
- Robust direction estimation: Rotation and translation estimates from essential-matrix decomposition can be highly inaccurate when correspondences are misidentified or sparse.The method therefore avoids directly relying on those decomposed pairwise estimates for direction estimation.
- Robust direction estimation: The estimated direction signs are recovered using the constraint that scene points should lie in front of the cameras.This converts undirected line estimates into directed pairwise directions.
- Robust direction estimation: The estimator uses a non-convex formulation with IRLS to obtain robust estimates of the direction lines from noisy samples.The paper reports high-quality empirical estimates despite the absence of a global-optimality guarantee for IRLS.
- Evaluation: The robust method significantly improves direction-estimation accuracy over PCA-based estimation.Figure 3 compares angular errors against reference directions; the histograms are restricted to [0, π/4] to emphasize quality differences.
- Evaluation: The robust direction estimator has running time comparable to PCA and therefore does not significantly increase total pipeline runtime.The paper also summarizes the complete camera-motion procedure in Table 1.
4. Experiments
Synthetic and real-image experiments evaluate LUD under corrupted direction measurements, compare it with existing solvers, and assess its accuracy and computational cost. LUD achieves exact recovery in some partially corrupted synthetic settings and produces highly accurate initial estimates on real image collections.
- Synthetic Data Experiments: Synthetic experiments use random parallel-rigid Erdős–Rényi measurement graphs, Gaussian locations, controlled outlier probability p, and NRMSE averaged over 10 trials.The experiments normalize location estimates for global scale and translation before evaluating NRMSE.
- Synthetic Data Experiments: LUD exactly recovers locations with sufficiently small nonzero corruption when σ = 0, using NRMSE < 1e-8 as the recovery criterion.Exact-recovery regions improve in d = 3 relative to d = 2 and become marginally better for n = 200 than n = 100 at small p.
- Synthetic Data Experiments: LUD remains robust across substantial outlier proportions and generally outperforms CLS, SDR, and LS, even when small inlier errors dominate.Figure 5 compares NRMSE for n = 200 locations, with values averaged over 10 trials.
- Real Data Experiments: Real-image experiments on nine irregular collections compare location accuracy using average and median distances to reference cameras, measured approximately in meters.Table 2 distinguishes PCA and robust pairwise-direction estimation and reports the number of estimated cameras.
- Real Data Experiments: Combining robust direction estimation with LUD yields highly accurate initial estimates at slightly higher computational cost than CLS and, after which one PBA pass improves structures and accuracy.The experiments also include comparisons with SDR and use PBA to construct richer 3D structures.
5. Conclusion and Future Work
The paper connects well-posed camera-location estimation to parallel rigidity and proposes robust direction estimation plus the LUD convex program. Experiments show exact recovery under some partial corruption and accurate initialization for reprojection-based structure recovery, while the conditions for exact recovery remain future work.
- Conclusion: Parallel rigidity characterizes well-posed camera-location instances and supports extracting maximal image subsets where location estimation is well posed.The approach addresses the global translation and scale ambiguities inherent in location recovery.
- Conclusion: The proposed pipeline combines robust pairwise direction estimation with the least unsquared deviations convex program to reduce the effects of outlier directions.The method targets both outliers in point correspondences and large errors in pairwise direction measurements.
- Conclusion: LUD uniquely enables exact location recovery in experiments with partially corrupted direction measurements, and real-image tests produce high-quality initialization for reprojection error minimization.The real-image application uses the estimated camera locations to initialize structure recovery algorithms.
- Future Work: The conditions under which exact recovery persists with partially corrupted directions remain an open topic for future investigation.The authors specifically plan to characterize when this phenomenon exists.