"alibration
d unknown
)-96, 1998
| A. Oost-
liscontinu-
tockholm,
, One-shot
1e Interna-
6-340, 25-
nvariance,
matching
ze my hol-
penhagen,
'iew depth
rocessing,
. 416-425,
tp://www-
> quadric,
h, Match-
ing, Inter-
n, Detroit,
ine stereo
ons, Proc.
. 412-425,
ysterlinck,
nvariance
157-192,
ys, and L.
thm using
Computer
M. Proes-
' patches,
|
on of mu-
cquisition
EE Trans-
elligence,
ISPRS Commission III, Vol.34, Part 3A ,Photogrammetric Computer Vision‘, Graz, 2002
FACTORIZATION WITH ERRONEOUS DATA
Henrik Aanzes^, Rune Fisker^^, Kalle Astrom® and Jens Michael Carstensen?
@ Technical University of Denmark
b Lund Institute of Technology
¢ 3Shape Inc.
KEY WORDS: Robust statistics, feature tracking, Euclidean reconstruction, structure from motion
ABSTRACT
Factorization algorithms for recovering structure and motion from an image stream have many advantages, but tradition-
ally requires a set of well tracked feature points. This limits the usability since, correctly tracked feature points are not
available in general. There is thus a need to make factorization algorithms deal successfully with incorrectly tracked
feature points.
We propose a new computationally efficient algorithm for applying an arbitrary error function in the factorization scheme,
and thereby enable the use of robust statistical techniques and arbitrary noise models for individual feature points. These
techniques and models effectively deal with feature point noise as well as feature mismatch and missing features. Fur-
thermore, the algorithm includes a new method for Euclidean reconstruction that experimentally shows a significant
improvement in convergence of the factorization algorithms.
The proposed algorithm has been implemented in the Christy—Horaud factorization scheme and the results clearly illus-
trate a considerable increase in error tolerance.
1 INTRODUCTION
Structure and motion estimation of a rigid body from an
image sequence, is one of the most widely studied fields
within the field of computer vision. A popular set of so-
lutions to the subproblem of estimating the structure and
motion from tracked features are the so—called factoriza-
tion algorithms. They were originally proposed by [Tomasi
and Kanade, 1992], and have been developed consider-
ably since their introduction, see e.g. [Christy and Horaud,
1996, Costeira and Kanade, 1998, Irani and Anandan, 2000,
Kanade and Morita, 1994, Morris and Kanade, 1998, Poel-
man and Kanade, 1997, Quan and Kanade, 1996, Sturm
and Triggs, 1996].
These factorization algorithms work by linearizing the ob-
servation model, and give good results fast and without any
initial guess for the solution. Hence the factorization algo-
rithms are good candidates for solving the structure and
motion problem, either as a full solution or as initializa-
tion to other algorithms such as bundle adjustment, see e.g.
[Slama, 1984, Triggs et al., 2000].
The factorization algorithms assume that the correspon-
dence or feature tracking problem has been solved. The
correspondence problem is, however, one of the difficult
fundamental problems within computer vision. No perfect
and fully general solution has been presented. For most
practical purposes one most abide with erroneous tracked
features as input to the factorization algorithm. This fact
poses a considerable challenge to factorization algorithms,
since they implicitly assume independent identical distributed
Gaussian noise on the 2D features (the 2-norm is used as
error function on the 2D features). This noise assumption
based on the 2-norm is known to perform rather poorly in
the presence of erroneous data. One such badly tracked
feature can corupt the result considerably.
A popular way of addressing the sensitivity of the 2-norm
to outliers is by introducing weights on the data, such that
less reliable data is down-weighted. This is commonly
referred to as weighted least squares. We here propose
a method for doing this in the factorization framework.
Hereby the sensitivity to outliers or erroneous data is re-
duced. In other words we allow for an arbitrary Gaussian
noise model on the 2D features, facilitating correlation be-
tween the 2D features, directional noise on the individual
2D features in each frame and an arbitrary variance. In this
paper we focus on different sizes of the variance on the in-
dividual 2D features, in that this in itself can address most
of the issues of concern.
In order to down-weight less reliable data these have to
be identified. A popular way to do this is by assuming
that data with residual over a given threshold are less re-
liable. This assumption is the basis of most robust statis-
tics, and is typically implemented via Iterative Reweighted
Least Squares (IRLS). IRLS allows for arbitrary weighting
functions. We demonstrate this by implementing the Hu-
ber M-estimator [Huber, 1981] and the truncated quadratic
[Black and Rangarajan, 1996].
The proposed approach applies robust statistical methods
in conjunction with a factorization algorithm to obtain bet-
ter result with erroneous data.
There has been other attempts to address the problem of
different noise structures in the factorization framework
[Irani and Anandan, 2000, Morris and Kanade, 1998]. Irani
and Anandan [Irani and Anandan, 2000] assumes that the
noise is separable in a 3D feature point contribution and a
frame contribution. In other words if a 3D feature point
has a relatively high uncertainty in one frame it is assumed
that it has a similar high uncertainty in all other frames.
However, large differences in the variance of the individual
2D feature points is critical to the implementation of robust
statistical techniques that can deal with feature point noise,
missing features, and feature mismatch in single frames.
As an example, a mismatched feature in one frame does
in general not mean that the same feature mismatch occurs
A- 15
