This paper points out a few benefits of using a non-sequential approach to structure from motion.
Prior work on multi-view structure from motion is dominated by sequential approaches starting from a single two-view reconstruction, then adding new images one by one. In contrast, we propose a non-sequential methodology based on rotational consistency and robust estimation using convex optimization. The resulting system is more robust with respect to (i) unreliable two-view estimations caused by short baselines, (ii) repetitive scenes with locally consistent structures that are not consistent with the global geometry and (iii) loop closing as errors are not propagated in a sequential manner. Both theoretical justifications and experimental comparisons are given to support these claims.
This paper presents a non-incremental system for structure and motion.
Our solution is based on robustly computing global rotations from relative geometries and
feeding these into the known-rotation framework to create an initial solution for bundle adjustment.
To increase robustness we present a new method for constructing reliable point tracks from pairwise matches.
We show that our method can be seen as maximizing the reliability of a point track if the
quality of the weakest link in the track is used to evaluate reliability.
To estimate the final geometry we alternate between bundle adjustment and a robust version of the known-rotation formulation.
The ability to compute both structure and camera translations independent of initialization makes our algorithm insensitive
to degenerate epipolar geometries.
Triangulating a Plane
Olsson, Carl; Eriksson, Anders,
Scandinavian Conference on Image Analysis, 2011.
This paper investigates triangulation of a scene plane from two images.
It shows that when minimizaing back-projection error of the plane induced homography,
this problem is quasiconvex and can be solved using standard methods.
This report points out a few benefits of using a non-sequential approach to structure from motion.
In particular we show that non-sequential approaches are insensitive to geometries with small baselines.
This is in contrast to sequential methods that in each step rely on a well estimated structure to be able
to add new cameras.
This paper extends the L-infinity framework to problems in 1-dimmensional vision when using angular errors.
We show that a number of 1D geometry problems are quasiconvex.
Using these results we also propose a branch and bound method for the full (bi-quasiconvex) structure and motion problem for 1D-vision.
Furthermore, we show that due to limited field of view the problem is often ill posed, and there exist multiple good
(in terms of reprojection error) local minima.
The paper builds on the preliminary results of this one.
Recent work on geometric vision problems has exploited convexity properties in order to obtain globally optimal solutions.
In this paper we give an overview of these developments and show the tight connections between different types of convexity
and optimality conditions for a large class of multiview geometry problems.
We also show how the convexity properties are closely linked to different types of optimization algorithms for computing the solutions.
This paper is based on some of the preliminary results in this one and this one.
Outlier Removal using Duality
Olsson, Carl; Eriksson, Anders; Hartley, Richard, IEEE Conference on Computer Vision and Pattern Recognition, 2010.
(bibtex and
code
)
This paper proposes two methods for outlier removal in structure for motion.
The first is an improvment of the algorithm presented by Sim & Hartley in this
paper.
We achive a speedup or roughly an order of magnitude with the same guarantees.
The second one is related to the popular approach of
L1-approximation.
While this version is even more efficient in terms of computation times, it does not have the same guarantees as the previous one.
We show using duality that these methods are in fact related and we demonstrate on a number of large scale data sets that both methods
works very well.
This paper proposes a branch and bound method for solving optimization problems involving orthogonal constraints,
and is based on the two conference papers here and here.
Our first application is a generalization of the absolute orientation problem introduced in
Horn et.al. Rather than only registering two point clouds we also use point-to-plane and point-to-line correspondences.
The second application considered is calibrated camera pose estimation.
We show on both real and synthetic data that local minima do occur for this problem.
In this paper we study optimization problems with quasiconvex residuals under the L2-norm.
We consider the same framework as is introduced in
Kahl-Hartley-2008. However, since we are not using the max-norm, but rather the least squares formulation,
we cannot be sure that the resulting function is local minima free.
Rather than resorting to more complex global optimization methods, such as branch and bound,
we derive a simple test for verifying that a given local minima is indeed global.
We show on a number of real data sets that this approach is very efficient and in the vast majority of all cases
we are able to verify optimality.
This paper extends this one by considering 1-dimmensional vision problems.
In this case it is more natural to use the sum of squared angular error.
We show that similar to the 2D-case it is possible to derive a similar test to verify optimality.
Further more, we present a probabilistic method that can with high probability verify global optimality
should the former one fail.
In this paper we study how to fill in the missing data entries of a matrix under a low rank constraint.
The well known
factorization method can be used to solve for both structure and motion simultaneously
if the entire observation matrix is known. However, if some of the entries are missing these have to be
filled in using a rank constraint. Since the rank function is non-convex we propose to instead choose the
missing data that minimizes the sum of the singular values, the nuclear norm, of the measurement matrix.
This approach is similar to the successful
L1-relaxation
method that has successfully been applied to
compressed sensing and other related areas.
This paper studies the generalized registration problem introduced here.
In particular we investigate the quality of the lower bound on the global optimum which is provided by
Lagrangian duality. Since the orthogonallity constraints are non convex we cannot expect that there is no duality gap.
However, we show that the obtained solution is always better than direct linear methods, and in practice close to
the optimum.
In this paper we study outlier removal problems for problems with pseudoconvex residuals.
We show that these problems can be solved in polynomial time under the max-norm.
Speciffcally, if the dimmension of the search space is n (eg. triangulation n=3, homography estimation n=8) then
there is always a set of no more than n+1 residuals that determines the solution.
This paper studies how to effectively solve multiple view geometry problems under the max-norm.
The framework is the same as that of
Kahl-Hartley-2008. We show that these problems are not only quasiconvex but pseudoconvex, which is
a stronger criteria. This opens up the possibility of using other more efficient algorithms than the bisection algorithm.
This paper extends the L-infinity framework to problems in 1-dimmensional vision when using angular errors.
We show that a number of 1D geometry problems are quasiconvex.
Using these results we also propose a branch and bound method
for the full (bi-quasiconvex) structure and motion problem for 1D-vision.
This paper considers a generalization of the absolute orientation problem introduced in
Horn et.al. Rather than only registering two point clouds we also use point-to-plane and point-to-line correspondences.
We propose a branch and bound method that efficiently solves this problem.
In this paper we present a branch and bound method for calibrated camera pose estimation.
We show on both real and synthetic data that local minima do occur for this problem.
This paper presents a reformulation of the normalized cuts criterion that allows incorporation of linear equality constraints.
This is done by restating the problem and showing how linear constraints can
be enforced exactly in the optimization scheme through duality.
PhD-thesis: 
