Multiple rotation averaging is an important problem in computer vision. The problem is challenging because of the nonlinear constraints required to represent the set of rotations. To our knowledge no one has proposed any globally optimal solution for the case of simultaneous updates of the rotations. In this paper we propose a simple procedure based on Lagrangian duality that can be used to verify global optimality of a local solution, by solving a linear system of equations. We show experimentally on real and synthetic data that unless the noise levels are extremely high this procedure always generates the globally optimal solution.
We consider the least-squares (L2) minimization problems in multiple view geometry for triangulation, homography, camera resectioning and structure-and-motion with known rotatation, or known plane. Although optimal algorithms have been given for these problems under an Linfinity cost function, finding optimal least-squares solutions to these problems is difficult, since the cost functions are not convex, and in the worst case may have multiple minima. Iterative methods can be used to find a good solution, but this may be a local minimum. This paper provides a method for verifying whether a local-minimum solution is globally optimal, by providing a simple and rapid test involving the Hessian of the cost function. The basic idea is that by showing that the cost function is convex in a restricted but large enough neighbourhood, a sufficient condition for global optimality is obtained.
The method is tested on numerous problem instances of real data sets. In the vast majority of cases we are able to verify that the solutions are optimal, in particular, for small to medium-scale problems.
Many problems in computer vision can be turned into a large-scale boolean optimization problem, which is in general NP-hard. In this paper, we further develop one of the most successful approaches, namely roof duality, for approximately solving such problems for higher-order models. Two new methods that can be applied independently or in combination are investigated. The first one is based on constructing relaxations using generators of the submodular function cone. In the second method, it is shown that the roof dual bound can be applied in an iterated way in order to obtain a tighter relaxation. We also provide experimental results that demonstrate better performance with respect to the state-of-the-art, both in terms of improved bounds and the number of optimally assigned variables.
Geometric reconstruction from image collections is a classical computer vision problem. The problem essentially consists of two steps; First, the identification of matches and assembling of point tracks, and second, multiple view geometry computations. In this paper we address the problem of constructing point tracks using graph theoretical algorithms. From standard descriptor matches between all pairs of images we construct a graph representing all image points and all possible matches. Using Gomory-Hu trees we make cuts in the graph to construct the individual point tracks. We present both theoretical and experimental results (on real datasets) that clearly demonstrates the benefits of using our approach.
Here we propose an energy-based framework for approximating surfaces from a cloud of point measurements corrupted by noise and outliers. Our energy assigns a tangent plane to each (noisy) data point by minimizing the squared distances to the points and the irregularity of the surface implicitly defined by the tangent planes. In order to avoid the well-known "shrinking" bias associated with first-order surface regularization, we choose a robust smoothing term that approximates curvature of the underlying surface. In contrast to a number of recent publications estimating curvature using discrete (e.g. binary) labellings with triple-cliques we use higher-dimensional labels that allows modeling curvature with only pair-wise interactions. Hence, many standard optimization algorithms (e.g. message passing, graph cut, etc) can minimize the proposed curvature-based regularization functional. The accuracy of our approach for representing curvature is demonstrated by theoretical and empirical results on synthetic and real data sets from multi-view reconstruction and stereo.
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: 
