Robust Structure From Motion Based on
Relative Rotations and Tie Points
X. Wang, F. Rottensteiner, and C. Heipke
Abstract
In this article, we present two new approaches for image
orientation with a focus on robustness, starting with rela-
tive orientations of available image pairs, an incremental
and a global one, and compare
incremental approach, we first
age pair, and we then iterativel
by adding new images. The rotations of these newly added
images are estimated from relative rotations by single rota-
tion averaging. In the next step, a linear equation system is
set up for each new image to solve the translation parameters
with triangulated tie points that can be viewed in that new
image, followed by a resection for refinement. Finally, we
refine the orientation parameters of the images by a local
bundle adjustment. We also present a global method that
consists of two parts: global rotation averaging, followed by
setting up a large linear equation system to solve for all im-
age translation parameters simultaneously; a final bundle
adjustment is carried out to refine the results. We compare
these two methods by analyzing results on different bench-
mark sets, including ordered and unordered image data
sets from the Internet and two other challenging data sets
to demonstrate the performance of our two approaches. We
conclude that while the incremental method typically yields
results of higher accuracy and performs better on the chal-
lenging data sets, our global method runs significantly faster.
Introduction
In recent years, surveying and mapping showed a lot of
interest in automatic
3D
modeling of architectural and urban
areas from images. The determination of image orientation
via automatically determined tie points (also called structure
from motion [
SfM
]) is a prerequisite to realize this task. Various
methods have been suggested to solve this problem (Snavely
et al.
2006; Agarwal
et al.
2009; Wu 2013).
SfM
can be divided
into three categories: incremental
SfM
, hierarchical
SfM
, and
global
SfM
. Incremental
SfM
(Snavely
et al.
2006; Wu 2013;
Schönberger and Frahm 2016; Wang
et al.
2018) is the earliest
idea. Two images or triplets are initially chosen according to
some specific requirements; their relative orientation param-
eters are computed, new images are iteratively added by space
resection (also called the perspective-n-point problem [PnP])
and triangulation, and a robust bundle adjustment is typically
adopted to obtain reliable results. The above procedure is re-
peated until no more images can be added. Incremental
SfM
is
relatively robust against outliers because these can be detected
and removed incrementally when adding new images. How-
ever, due to the repeated use of bundle adjustment, it is rather
slow. To overcome this problem, hierarchical
SfM
(Farenzena
et al.
2009; Havelena
et al.
2009; Mayer 2014; Toldo
et al.
2015) was proposed. The basic idea is to divide the whole
data set into several overlapping subsets that are reconstructed
independently using incremental methods. Finally, all recon-
structions are merged and optimized by bundle adjustment.
Global
SfM
(Govindu 2001; Martinec and Pajdla 2007; Jiang
et
al.
2013; Moulon
et al.
2013; Ozyesil and Singer 2015; Arri-
i
et al.
2016; Reich and Heipke 2016; Goldstein
et al.
2016;
g
et al.
2019) considers this problem from a different per-
ctive. Global
SfM
draws on the well-known idea that rota-
tion and translation estimation (i.e., the computation of the
3D
coordinates of the projection center) can be separated. Accord-
ingly, these methods consist of two main steps: global rotation
averaging and global translation estimation. Global rotation
averaging simultaneously estimates the rotation matrices of all
images in a consistent (global) coordinate system (Hartley
et
al.
2013). Given global rotations, global translation estimation
aims at simultaneously solving the translation parameters of
all images. The advantage of global
SfM
is that it can solve both
rotations and translations without using intermediate bundle
adjustment, only a final one is necessary. However, it is more
sensitive to outliers than the other methods.
We are most interested how incremental and global
methods compare with respect to robust and time-efficient
solutions; to this end, we propose and investigate novel
incremental and global
SfM
approaches in this article. Figure 1
shows the work flows of our methods. We first extract features
from all images and perform relative orientation of all image
pairs; for unordered sets, we first determine image similar-
ity using the method described in (Wang
et al.
2017). Then,
for the incremental approach, an initial image pair is chosen,
and clusters of new images are iteratively added and oriented
by single rotation averaging and linear translation estima-
tion (see pointed box in Figure 1). Subsequently, new scene
points are triangulated, and a local bundle adjustment is used
to refine the results. The global method uses the two steps of
global rotation estimation and global translation estimation
(see dashed box in Figure 1), both making sure that blunders
are detected and eliminated beforehand.
The main contribution of this article is threefold. First, as
part of the incremental approach, we adopt single rotation
averaging to estimate the new image rotation matrix
.
Second,
again for the incremental approach, we set up a linear equa-
tion system with only two tie points that can be seen in the
new images to calculate the translation parameters. Finally,
inspired by the second contribution, if the global rotation
matrices can be provided in one way or another, we set up
a linear equation system that solves all image translation
parameters simultaneously. The L1 norm (minimization of
the sum of the absolute values of the residuals) is chosen to
solve the above optimization, as it is more robust than the
L2 norm (least squares). We evaluate the performance of our
approaches’ w.r.t. accuracy and time efficiency using various
Wang, Rottensteiner, and Heipke are with the Institute of
Photogrammetry and GeoInformation, Leibniz Universität
Hannover,Nienburger Str. 1, D-30167 Hannover, Germany
(
).
Photogrammetric Engineering & Remote Sensing
Vol. 85, No. 5, May 2019, pp. 347–359.
0099-1112/18/347–359
© 2019 American Society for Photogrammetry
and Remote Sensing
doi: 10.14358/PERS.85.5.347
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
May 2019
347
