Quaternion-Based Solutions for the
Single Photo Resection Problem
Mehdi Mazaheri and Ayman Habib
Abstract
This paper introduces three quaternion-based approaches
to solve the SPR problem. The first two are based on pro-
jective transformation and
DLT
coefficients through which
the position of the perspective center is derived first us-
ing four or more planar and six or more non-planar object
points, respectively. The rotation matrix is then directly
estimated using quaternions. The third one (quaternion-
based general approach) can handle three or more points
in either planar or non-planar configuration. In this ap-
proach, the rotation angles are iteratively estimated first
using quaternions without the need for user-defined ap-
proximations. Then, the position of the perspective center
is directly derived. Experimental results show the feasibility
of the proposed approaches and the high accuracy of the
quaternion-based general approach, which is superior to the
state-of-the-art non-iterative method and does not deviate
more than 1 percent from the traditional non-linear
SPR
, i.e.,
the de-facto standard for the most accurate
SPR
solution.
Introduction
Single Photo Resection (
SPR
) is a fundamental task in photo-
grammetry and computer vision.
SPR
deals with the recovery
of the Exterior Orientation Parameters (
EOP
s) from given im-
age/object points. The
SPR
problem has been denoted by other
names such as space resection, pose estimation, Perspective
3-Points (
P3P
) problem, or
P
n
P
for
n
-points. Previous studies
regarding the
SPR
problem can be categorized into closed-form
and iterative methods. The closed-form solutions are non-
iterative and mainly used to initialize the iterative methods.
A group of the closed-form approaches such as
P3P
and
P4P
are
limited to minimal data i.e., three or four points, respectively.
In contrast, traditional closed-form methods such as
DLT
or
projective as well as the state-of-the-art solutions can handle
redundant data. Existing closed-form solutions for minimal
and redundant data as well as iterative methods are reviewed
in the following paragraphs.
The very first
P3P
solution is introduced in Grunert (1841)
by applying the cosine law for the rays from the perspective
center to three image points and the perspective center to
the corresponding object points. Different variations of the
Grunert method have been published later by Finsterwalder
and Sheufele (1937), Merritt (1949), Fischler and Bolles
(1981), Linnainmaa
et al
. (1988), and Grafarend
et al
. (1989).
These methods are reviewed and analyzed by Haralick
et
al
. (1994) for numerical stability. Later on, Gao
et al
. (2003)
describe geometric and algebraic approaches to find complete
and numerically stable solutions for the
P3P
problem. Kneip
et al
. (2011) proposes a novel solution for the
P3P
problem in
which the position and orientation of the image are directly
computed. Recently, Huaien (2012) presents another solution
for
P3P
starting from the Grunert equations. In addition to
P3P
,
several researchers tried to tackle the
P4P
problem. Fischler
and Bolles (1981) solve the
P4P
problem by finding the com-
mon solution between subsets of three out of four points.
Horaued
et al
. (1989) generate a pencil of three lines from four
points and develop biquadratic polynomials from geometric
constraints. Grafarend (1997) uses Möbius barycentric coor-
dinates and Awange and Grafarend (2003) employ Groebner-
basis elimination to solve the
P4P
problem by computing dis-
tances between the perspective center and the object points.
For more detailed information about the algebraic solutions
for the
P3P
and
P4P
problems, one can refer to Bujnák (2012).
Photogrammetric and computer vision applications usu-
ally involve redundant data, which might be contaminated
by noise. Least-squares adjustment incorporating redundant
data can be employed to reduce the effect of noise and achieve
higher accuracy. Therefore, closed-form solutions that are
capable of handling redundant data are highly desired. For
instance, the
DLT
equations (Abdel-Aziz and Karara, 1971) are
extensively used to linearly recover the
EOP
s using six or more
non-planar points. The two-dimensional variant of
DLT
- pro-
jective transformation (Abdel-Aziz and Karara, 1971; Seed-
ahmed and Habib, 2002; Shih and Faig, 1987) - deals with four
or more planar points. Quan and Lan (1999) develop a closed-
form approach by considering triplets of points for each of
which a fourth-order polynomial is derived. By placing all
the polynomials’ coefficients into a matrix, a linear equation
system is formed. The equation system is solved by Singular
Value Decomposition (
SVD
) and the unknown distances from
the perspective center to the object points are derived. Trigs
(1999) develops a solution for
P
n
P
(where
n
≥
4), which is
based on the constraint that the cross product of the vectors
connecting the perspective center to the image point and the
perspective center to the corresponding object point should
be zero. Fiore (2001) presents an efficient linear solution for
SPR
with four or more coplanar points (and six or more points
in any configuration). Lepetit
et al
. (2009) reduce the prob-
lem to three/four virtual control points for planar/non-planar
object points, and develop an Efficient
P
n
P
solution (
EP
n
P
).
Li
et al
. (2012) introduce a Robust
P
n
P
solver (
RP
n
P
) that uses
(
n
−2) subsets of three points and generate (
n
−2) fourth-order
polynomials. Sum of squares of polynomials are considered as
a cost function and differentiated in order to find the minima.
The differentiation yields a seventh-order polynomial, which
is solved by the eigenvalue method (Press
et al
., 2007).
The second category of the
SPR
solutions is iterative meth-
ods, which are the best choice to achieve high accuracy with
minimal or redundant noisy data. However, iterative methods
Lyles School of Civil Engineering, Purdue University,
550 Stadium Mall Drive, West Lafayette, IN 47907-2051
(
).
Photogrammetric Engineering & Remote Sensing
Vol. 81, No. 3, March 2015, pp. 209–217.
0099-1112/15/813–209
© 2014 American Society for Photogrammetry
and Remote Sensing
doi: 10.14358/PERS.81.3.209
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
March 2015
209
