PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
January 2017
47
Exterior Orientation Revisited:
A Robust Method Based on
l
q
-norm
Jiayuan Li, Qingwu Hu, Ruofei Zhong, and Mingyao Ai
Abstract
Camera
is essential in many
and computer vision applications, including 3D reconstruc-
tion, digital orthophoto map (
DOM
) generation, and localization.
In this paper, we propose a new formulation of
that is robust against gross errors (outliers). Different from
classic optimization methods whose cost function is based on
the l
2
-norm of residuals, we use l
q
-norm (
0<
q
<1
) instead. We
reformulate the new cost function as an augmented Lagrangian
function because it is not strictly convex. In addition, we em-
ploy the alternating direction method of multipliers (
ADMM
) to
decompose the augmented Lagrangian function into three sim-
ple sub-problems and solve them iteratively. Our work recovers
the orientation and position of a camera from outliers contami-
nating observations without any gross error detection stage such
as random sample consensus (
RANSAC
). Extensive experiments
on both synthetic and real data demonstrate that the proposed
method significantly outperforms state-of-the-art methods and
can easily handle situations with up to 85 percent outliers. The
source code of the proposed algorithm is made public.
Introduction
Camera exterior orientation, which is also known as perspec-
tive-n-point (
PnP
) problem in computer vision, refers to recov-
ering the orientation and position of a perspective camera from
n
3D-to-2D point correspondences. The
PnP
problem is a basic
aspect of many computer vision and photogrammetric appli-
cations (e.g., camera localization, digital elevation model (
DEM
)
production, incremental structure-from-motion, etc.), which has
been studied for several decades. However, only a few studies
have focused on the
PnP
problem with outliers in point corre-
spondences.
The majority of
PnP
solutions do not directly address prob-
lems containing outliers. These solutions simply assume that
all point correspondences are inliers. For example, Zheng
et
al
. (2013) validated their method on simulated data that were
contaminated by Gaussian noise with a zero-mean and a fixed
deviation
σ
= 2 pixels. Traditional methods usually combine
P3P
algorithms with random sample consensus (
RANSAC
)
(Fischler and Bolles, 1981) schemes to reject outliers during a
preprocessing stage before the
PnP
methods are applied. How-
ever,
RANSAC
significantly reduces the efficiency, particularly
for problems with numerous outliers.
Recently, Ferraz
et al
. (2014) proposed a fast, robust, and
accurate
PnP
algorithm (
REPPnP
) with an algebraic outlier
rejection stage. Their novel contribution was introducing a
novel outlier rejection mechanism within the pose estimation
framework. The
PnP
problem was formulated as a low-rank
homogeneous system, and the solution was obtained by
solving for its 1D null space. They assumed that rows of the
homogeneous system which perturbed its null space were
outliers. These outliers were then progressively rejected on
the basis of an algebraic criterion. Their proposed
REPPnP
dealt
well with situations with up to 50 percent outliers. However,
REPPnP
was ineffective when the outlier rate exceeded 50 per-
cent. Moreover, their mechanism cannot handle planar cases
and ordinary cases under a uniform framework.
In this paper, we introduce a new
PnP
solution that is more
robust than state-of-the-art algorithms.
Compared with
REPPnP
(Ferraz
et al
., 2014), our method
does not require any outlier detection mechanism and han-
dles all point configurations (planar, ordinary, and quasi-sin-
gular) in the same manner. Our work recovers the pose of a
camera from correspondences corrupted by numerous outliers
without any outlier detection stage such as
RANSAC
. The cen-
tral idea of our method is to reformulate the
PnP
problem as
an optimization function using
l
q
-norm (0<
q
<1) instead of
l
2
-
norm. This idea is motivated by many other works where the
l
q
-norm was successfully applied, such as signal reconstruc-
tion (Marjanovic and Solo, 2012; Marjanovic and Hero, 2014;
Marjanovic and Solo, 2014), compressive sensing (Candè and
Wakin, 2008), point cloud processing (Bouaziz
et al.
, 2013; Li
et al.
, 2016). The
l
q
-norm is a sparsity-inducing norm that can
minimize the number of non-zero residuals. Thus, it inherent-
ly rejects outliers. The
l
q
-norm cost function is then refor-
mulated as an augmented Lagrangian function and solved by
the alternating direction method of multipliers (
ADMM
) (Boyd
et al.
, 2011). An extensive experimental evaluation on both
synthetic and real data shows that the proposed approach
significantly outperforms the state-of-the-art methods and can
easily handle situations with up to 85 percent outliers.
Related Work
The minimal configuration of the
PnP
problem is the
P3P
(DeMenthon and Davis 1992, Gao
et al.
, 2003; Kneip
et al.
,
2011) or
P4P
(Horaud
et al.
, 1989) problem. In these cases,
there exist closed-form solutions finding roots of the formed
fourth- or fifth-degree polynomial systems. Unfortunately,
these solutions are sensitive to outliers and noise. The
PnP
problem, thus, focuses on over-constrained cases with larg-
er-scale correspondence sets. Ideal
PnP
solutions should have
the following properties: fast and unique convergence, global
optimality, high accuracy, and robustness. However, finding
a balance between all these features is difficult. The literature
on the
PnP
problem can be roughly classified into two catego-
ries: non-iterative and iterative methods.
The most straightforward non-iterative
PnP
algorithms are
the direct linear transformation (
DLT
) (Abdel-Aziz and Karara,
Jiayuan Li, Qingwu Hu, and Mingyao Ai are with the School
of Remote Sensing and Information Engineering, Wuhan Uni-
versity, Wuhan 430079, China (
).
Ruofei Zhong is with the Beijing Advanced Innovation Center
for Imaging Technology, Capital Normal University, Beijing
100048, China.
Photogrammetric Engineering & Remote Sensing
Vol. 83, No. 1, January 2017, pp. 47–56.
0099-1112/17/47–56
© 2017 American Society for Photogrammetry
and Remote Sensing
doi: 10.14358/PERS.83.1.47
