Source-linked AI summary
Efficient Outlier Removal in Large Scale Global Structure-from-Motion
Fei Wen, Danping Zou, Rendong Ying, Peilin Liu
TL;DR
Global SfM outlier removal must address mismatches that can remain after pairwise matching and degrade structure estimation. The paper exploits multiview geometry to reduce formulation dimensions and proposes convex-relaxed ℓ1 and iteratively reweighted ℓ0 methods. Reconstruction experiments report faster algorithms than state of the art with improved solutions.
Problem
Outliers can remain because local epipolar constraints may miss mismatches in long tracks, degrading structure estimation in global SfM.
Source: §I · p. 1Method
The paper uses a dimension-reduced formulation with a convex-relaxed ℓ1 method and an iteratively reweighted approximation to ℓ0 minimization.
Source: §I · pp. 1–2, B. Iteratively Reweighted Algorithm · p. 3Results
Realistic multiview reconstruction experiments report that the new algorithms are more than three times faster than the ℓ1 method while giving an improved solution.
Source: §V · p. 5Takeaways & Limitations
The authors conclude that the methods could be useful in practical large-scale Structure-from-Motion applications.
Source: §V · p. 5
Abstract
from arXiv · showhide
This work addresses the outlier removal problem in large-scale global structure-from-motion. In such applications, global outlier removal is very useful to mitigate the deterioration caused by mismatches in the feature point matching step. Unlike existing outlier removal methods, we exploit the structure in multiview geometry problems to propose a dimension reduced formulation, based on which two methods have been developed. The first method considers a convex relaxed $\ell_1$ minimization and is solved by a single linear programming (LP), whilst the second one approximately solves the ideal $\ell_0$ minimization by an iteratively reweighted method. The dimension reduction results in a significant speedup of the new algorithms. Further, the iteratively reweighted method can significantly reduce the possibility of removing true inliers. Realistic multiview reconstruction experiments demonstrated that, compared with state-of-the-art algorithms, the new algorithms are much more efficient and meanwhile can give improved solution. Matlab code for reproducing the results is available at \textit{https://github.com/FWen/OUTLR.git}.
I. INTRODUCTION
Global SfM outlier removal remains difficult because local epipolar constraints can miss outliers in long tracks, which can degrade structure estimation. The paper proposes dimension-reduced formulations and two algorithms for efficient, robust removal in large-scale SfM.
I. INTRODUCTION
- Long-track outliers can evade local epipolar constraints and significantly degrade structure estimation if not processed.The work targets efficient and robust outlier removal in global SfM.Source: §I · p. 1
- The proposed dimension-reduced formulation yields two methods intended to be more efficient than the ℓ1 method for large-scale Global SfM.The first uses convex-relaxed ℓ1 minimization solved by linear programming; the second approximately solves the ideal ℓ0 formulation by iterative reweighting.Source: §I · pp. 1–2
- Experiments on synthetic and real-world datasets report that the proposed methods retain more inliers than existing methods and run much faster.Source: §I · p. 2
A. Proposed Formulation
- The ℓ0 formulation represents outliers through the nonzero entries of an auxiliary vector s, whose support is the outlier index set.For a solution s*, M − ∥s*∥0 equals the number of inliers.Source: A. Proposed Formulation · p. 2
- The formulation’s inequality constraint is rewritten as linear inequalities using the stated construction of A_i and b_i.The formulation also defines κ = 2 and uses a Kronecker product.Source: A. Proposed Formulation · p. 2
B. Multiview Geometry
The paper extends residual-based outlier removal formulations to geometric residuals in multiview reconstruction. Under specified conditions, geometric residuals can be rewritten in a linear form suitable for the formulation.
B. Multiview Geometry
- In multiview reconstruction, the goal is to estimate scene structure and camera motion from image projections.The paper considers camera matrix P = [R, t] and squared reprojection error.Source: B. Multiview Geometry · p. 2
- When either z or R is known, the geometric residual can be rewritten in the linear form used by the formulation.For known-rotation multiview reconstruction, x contains 3D-point positions and camera translations.Source: B. Multiview Geometry · p. 2
- The general residual formulation accommodates Euclidean, coordinate-wise max (ℓ∞), and absolute (ℓ1) distances.Source: B. Multiview Geometry · p. 2
- For the geometric residual, the outlier-removal constraint can be converted into two linear constraints and then expressed as linear inequalities.The passage also notes that a depth constraint may additionally be considered in practical applications.Source: B. Multiview Geometry · p. 2
C. Connection to Existing Works
Prior formulations either do not scale to large-scale multiview reconstruction or use a higher-dimensional relaxation. The paper’s dimension-reduced formulation preserves the ℓ1 relaxation while reducing variables and computational complexity.
C. Connection to Existing Works
- The existing GORE approach uses mixed integer linear programming but does not scale to high-dimensional problems such as large-scale multiview reconstruction.Source: C. Connection to Existing Works · p. 3
- Deterministic methods in, [24] use Frank-Wolfe and ADMM but remain unsuitable for large-scale multiview reconstruction.Source: C. Connection to Existing Works · p. 3
- The proposed formulation reduces the variable count from κM to M by retaining structure ignored by the existing ℓ1 formulation, reducing complexity and improving results.Source: C. Connection to Existing Works · p. 3
- The ℓ1 relaxation is convenient because of convexity and direct use of LP solvers, but may remove true inliers under some conditions.The passage motivates reweighted approaches as a way to seek sparser solutions.Source: C. Connection to Existing Works · p. 3
III. PROPOSED ALGORITHMS
The proposed algorithms address the difficulty of directly solving the nonconvex ℓ0 minimization problem. They combine a convex-relaxed method with an iteratively reweighted approximation to the ideal formulation.
III. PROPOSED ALGORITHMS
- Directly solving the nonconvex ℓ0 minimization problem is difficult.Source: §III · p. 3
- The paper first proposes an algorithm for a convex-relaxed version, then develops an iteratively reweighted algorithm to approximately solve the ideal ℓ0 problem.Source: §III · p. 3
A. ℓ1 Algorithm with Reduced Dimension
The method relaxes the outlier-removal problem to an ℓ1 minimization and solves its dual with an LP. Its reduced formulation uses fewer slack variables than the earlier ℓ1 method.
A. ℓ1 Algorithm with Reduced Dimension
- The ℓ1 formulation replaces the ℓ0 norm in (5) with its convex envelope.Source: A. ℓ1 Algorithm with Reduced Dimension · p. 3
- The formulation uses M slack variables rather than the κM used by the ℓ1 algorithm in [6], yielding a dimension-reduction speedup.Source: A. ℓ1 Algorithm with Reduced Dimension · p. 3
- The dual problem uses variables y and v and can be solved by a well-developed LP solver.Here y ∈ R^(κM) and v ∈ R^M.Source: A. ℓ1 Algorithm with Reduced Dimension · p. 3
- The algorithm constructs A and b from the measurements, solves the LP for s, and removes residuals with s_i > 0.Source: A. ℓ1 Algorithm with Reduced Dimension · p. 3
B. Iteratively Reweighted Algorithm
The iteratively reweighted method approximately solves the ideal ℓ0 minimization, motivated by the possibility that ℓ1 minimization removes true inliers. It updates weights and solves an LP repeatedly, with experiments indicating that a small iteration count can suffice.
B. Iteratively Reweighted Algorithm
- The method approximately solves the ideal ℓ0 problem because ℓ1 minimization may remove true inliers in practical applications.Source: B. Iteratively Reweighted Algorithm · p. 3
- It approximates ℓ0 with an ℓq norm and linearizes that norm at the current solution to update the weights.Source: B. Iteratively Reweighted Algorithm · pp. 3–4
- Each iteration solves an LP with the current weights, then updates the weights from the resulting s_k.Source: B. Iteratively Reweighted Algorithm · p. 4
- A small iteration count K can yield sufficiently good performance in practical applications.Source: B. Iteratively Reweighted Algorithm · p. 4
IV. EXPERIMENTS
The experiments compare the proposed algorithms with several methods, including RANSAC, exact penalty, ℓ1, and ℓ∞. Algorithm 2 uses q = 0.1 and ε = 10^-3, and the LP problems are solved with SeDuMi.
IV. EXPERIMENTS
- The comparison includes RANSAC, exact penalty, ℓ1, and ℓ∞ methods.The exact penalty method uses Frank-Wolfe; the ℓ∞ method uses Gugat’s algorithm.Source: §IV · p. 4
- Algorithm 2 uses q = 0.1 and ε = 10^-3, and SeDuMi solves the involved LP problems.Source: §IV · p. 4
- The experiments ran in MATLAB on a laptop with a 2 GHz Intel I7 CPU and 16 GB RAM.Source: §IV · p. 5
A. Robust Linear Regression on Synthetic Data
On synthetic robust linear regression data, Algorithm 2 converges within a few iterations. Across outlier ratios, Algorithm 1 matches the ℓ1 method in outlier removal, while Algorithm 2 removes fewer outliers; EP yields the largest consensus size.
A. Robust Linear Regression on Synthetic Data
- The synthetic experiment used 500 points from an 8-dimensional linear model, with Gaussian noise and a subset of elements corrupted by higher-variance noise.The baseline noise standard deviation was 0.1 and the higher-variance outlier noise standard deviation was 1.Source: A. Robust Linear Regression on… · p. 5
- Fig. 1 shows Algorithm 2’s performance versus iteration number for q values 0.1, 0.2, and 0.5; it converges within a few iterations, e.g., K < 10.Source: A. Robust Linear Regression on… · p. 5
- Algorithm 1 removes the same number of outliers as the ℓ1 method across tested outlier ratios, while Algorithm 2 removes fewer.EP yields the largest consensus size.Source: A. Robust Linear Regression on… · p. 5
- Algorithm 1 is fastest, while Algorithm 2 is much faster than EP in runtime.Source: A. Robust Linear Regression on… · p. 5
B. Global SfM on Real World Datasets
On three real-world datasets, the methods reduced reprojection RMSE; Algorithm 1 was over three times faster than ℓ1, while Algorithm 2 removed fewer outliers and ran faster than ℓ1 and ℓ∞.
B. Global SfM on Real World Datasets
- The evaluation used known-rotation outlier removal after pairwise RANSAC initialization and before bundle adjustment, with a 5-pixel reprojection-error tolerance.The datasets were house, cathedral, and college; SIFT correspondences and pairwise RANSAC orientations were used.Source: B. Global SfM on Real World Datasets · p. 5
- Each algorithm significantly reduced reprojection RMSE, which the authors interpret as evidence of effective outlier removal.The RMSEs without outlier removal were 4.76 pixels for house, 3.24 for cathedral, and 4.16 for college.Source: B. Global SfM on Real World Datasets · p. 5
- Algorithm 1 was more than three times faster than ℓ1, with 96,976 variables versus 327,201 in the cathedral experiment.The experiments also used a depth constraint of κ = 6.Source: B. Global SfM on Real World Datasets · p. 5
- Algorithm 2 removed much fewer outliers than the other algorithms while running much faster than ℓ1 and ℓ∞.Algorithm 1 removed fewer outliers than ℓ1 while achieving comparable RMSE.Source: B. Global SfM on Real World Datasets · p. 5
V. CONCLUSION
The paper develops two efficient methods for removing feature-matching outliers in global SfM. On realistic multiview reconstruction experiments, they were faster than state-of-the-art methods and gave an improved solution.
V. CONCLUSION
- Dimension-reduced outlier-removal methods were much faster than state-of-the-art algorithms in realistic multiview reconstruction, including over three times faster than ℓ1, while giving an improved solution.The authors suggest the methods could be useful in practical large-scale SfM applications.Source: §V · p. 5