Research map / 3D vision / Depth and stereo
A Subspace-Constrained Tyler's Estimator and its Applications to Structure from Motion
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes the subspace-constrained Tyler's estimator (STE), a fusion of Tyler's M-estimator and a p=0 fast median subspace variant for robust subspace recovery, and applies it to fundamental matrix estimation and initial camera removal in SfM.
Problem
Robust subspace recovery from data heavily corrupted by outliers, where the fraction of inliers is below the theoretical threshold (8/9 for fundamental matrix estimation) required by existing methods, with applications to structure from motion.
Approach
Adapt Tyler's M-estimator to the d-dimensional subspace by keeping TME's shape information within the subspace while replacing the orthogonal complement eigenvalues with a shared shrunken value, yielding a regularized reduced-dimension covariance; theory shows recovery with DS-SNR below 1 when initialized by TME.
Key results
- On Photo Tourism fundamental matrix estimation, STE gives significantly lower mean relative rotation errors than TME, FMS and SFMS across 14 datasets, and is competitive with LO-RANSAC and DEGENSAC.
- Theory shows STE initialized by TME recovers the subspace for DS-SNR below 1 under the asymptotic generalized haystack model, where TME fails.
- In SfM camera removal, LUD+STE generally improves rotation and translation errors over the LUD pipeline, notably on Roman Forum and Gendarmenmarkt.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use STE instead of TME, FMS, or SFMS for fundamental matrix estimation | Fundamental matrix estimation · Photo Tourism | relative rotation error | Helped |
| Use STE instead of vanilla RANSAC | Fundamental matrix estimation · Photo Tourism | relative rotation error | Mixed |
| Use STE instead of LO-RANSAC or DEGENSAC | Fundamental matrix estimation · Photo Tourism | relative rotation error | Mixed |
| Screen cameras with STE before running the LUD pipeline | LUD · Photo Tourism | rotation error | Helped |
| Screen cameras with STE before running the LUD pipeline | LUD · Photo Tourism | translation error | Helped |
| Screen cameras with STE before running the LUD pipeline | LUD · Photo Tourism | runtime | Helped |
| Vary the STE parameter γ from 1/3 (ablation) | STE camera screening within LUD · Photo Tourism | rotation and translation errors | No clear effect |
Surprising findings
- STE is slightly faster than or comparable to other filters in SfM, but LUD+SFMS is even faster than LUD+STE.
- STE does not beat vanilla RANSAC on Ellis Island and Vienna Cathedral, nor LO-RANSAC and DEGENSAC on Notre Dame and the latter datasets.
Limitations
- Generic theory requires hard-to-verify conditions on initialization; the probabilistic guarantee is only asymptotic (N to infinity) with Gaussian assumptions.
- Camera removal application is described as not yet practical and gives no real speed-up since scale factors come from LUD.
- Fundamental matrix results are weaker than RANSAC variants on several datasets and STE needs a gamma search.
Experimental setup
Datasets: Photo Tourism
Benchmarks: Photo Tourism
Metrics: median relative rotation error mean relative rotation error mean rotation error mean translation error mAA(10°) runtime
Baselines: FMS SFMS TME RANSAC LO-RANSAC DEGENSAC LUD
Builds on: Tyler's M-estimator fast median subspace RANSAC LUD global SfM pipeline
Closest papers by meaning
- Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension (ICLR 2022 · similarity 0.87)
- Nearly Optimal Robust Subspace Tracking (ICML 2018 · similarity 0.87)
- Compact Matrix Factorization With Dependent Subspaces (CVPR 2017 · similarity 0.86)
- A Nullspace Property for Subspace-Preserving Recovery (ICML 2021 · similarity 0.86)
- Multi-Subspace Matrix Recovery from Permuted Data (AAAI 2025 · similarity 0.84)
- RESfM: Robust Deep Equivariant Structure from Motion (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.