UPnP:An Optimal O(n)Solution
to the Absolute Po Problem
with Universal Applicability
Laurent Kneip1,Hongdong Li1,and Yongduek Seo2 1Rearch School of Engineering,Australian National University,Australia 2Department of Media Technology,Sogang University,Korea
Abstract.A large number of absolute po algorithms have been pre-
nted in the literature.Common performance criteria are computational
complexity,geometric optimality,global optimality,structural degenera-
cies,and the number of solutions.The ability to handle minimal ts of
correspondences,resulting solution multiplicity,and generalized cameras
are further desirable properties.This paper prents thefirst PnP solu-
tion that unifies all the above desirable properties within a single algo-
rithm.We compare our result to state-of-the-art minimal,non-minimal,
central,and non-central PnP algorithms,and demonstrate universal ap-
plicability,competitive noi resilience,and superior computational effi-
ciency.Our algorithm is called Unified PnP(UPnP).
Keywords:PnP,Non-perspective PnP,Generalized absolute po,lin-
ear complexity,global optimality,geometric optimality,DLS.
1Introduction电脑桌面可爱
The Perspective-n-Point(PnP)algorithm is a fundamental problem in geometric computer vision.Given a certain number of correspondences between3D world points and2D image measurements,the problem consists offitting the absolute position and orientation of the camera to the measurement data.Our contribu-tion is a PnP solution that unifies most desirable properties within one and the same algorithm.We call our method Unified PnP(UPnP),and the benefits are summarized as follows:
–Universal applicability:UPnP is applicable to both central and non-central camera ralized cameras).In contrast,existing methods are often designed exclusively for the central [6],[17]).
–Optimality:Similarly to[16],we employ the object space error.However,we do not rely on convex relaxation techniques,which is why our solution is theoretically guaranteed to return a geometrical optimum.Likewi,UPnP is guaranteed tofind the global optimum.
–Linear complexity:Similarly to many recent [11]),our algorithm solves the PnP problem with O(n)(linear)complexity in the number of points.From a practical point of view,the O(n)-complexity argument is D.Fleet et al.(Eds.):ECCV2014,Part I,LNCS8689,pp.127–142,2014.
c Springer International Publishing Switzerland2014
128L.Kneip,H.Li,and Y.Seo
stronger than simple algebraic linearity of the solution.Despite of returning comparable results to[16]in terms of noi resilience,our method does not employ any iterative parts and therefore turns out to be faster by about two orders of magnitude.
冒牌货冒菜
–Completeness:The propod solution is complete in the n of return-ing multiple solutions.It therefore supports the minimal ca,as well as other possible ambiguous-po situations[15].Moreover—in contrast to re-cent works such as[6]and[17]—our algorithm still does not return any spurious solutions.The returned number of solutions is precily equal to the maximum number of solutions in the minimal ca.Similarly to[17],we furthermore exploit2-fold symmetry in the space of quaternions in order to avoid solution duplicates.
–Homogeneity:We parametrize rotations in terms of unit-quaternions—a non-minimal parametrization of rotations that is free of singularities and leads to homogeneous accuracy.
UPnP unifies all listed properties.It is inspired by veral recent works,and—usingfirst-order optimality conditions—solves the problem by a clod-form com-putation of all stationary points of the sum of squared object space errors.The conceptual innovations lie in the avoidance of a Lagrangian formulation,a geo-metrically consistent application of the Gr¨o bner basis methodology,and a general technique to circumvent2-fold symmetry in quaternion-bad parametrizations.
The paper is structured as follows:The related work is prented in the follow-ing subction.Section
2then outlines the core theoretical contributions behind our approach.Section3finally contains a detailed comparison to existing algo-rithms,show-casing state-of-the-art noi resilience at superior computational efficiency.
1.1Related Work
While an exhaustive review of the vast literature on the PnP problem goes be-yond the extend of this introduction,we nonetheless note that—after more than 170years of related rearch—still new solutions with interesting properties keep being discovered.The most recent advancement in the minimal ca—the P3P problem—was prented in2011[9].The P3P problem us3correspondences and returns at most4solutions.One of the major recent achievements in the PnP ca then consists of proving that the problem can be solved accurately in linear time with respect to the number of correspondences.Thefirst solution to provide accurate results under linear complexity is EPnP[11](2009).This algorithm is computationally efficient,however depends on a special variant with only3control points in the planar ca,minimizes only an algebraic error,and fails in situations of solution ,in situations of po-ambiguity such as for instance the minimal ca).Thefirst O(n)-successor that succeeds in all the criteria was prented in2011and is called DLS[6].It performs measurement data compression in linear time and then computes all statio
nary points of the sum of squared object-space errors in clod-form,using polynomial resultant techniques.It achieves a least-squares geometric error in linear time,六十四卦卦象
UPnP:An Optimal O(n)Solution with Universal Applicability129 Table1.Comparison of properties of various O(n)PnP algorithms.Note,however, that[16]contains an iterative convex relaxation part,which means that the effective computational complexity of SOS is in fact unbounded(hence the brackets).川菜有哪些
EPnP DLS OPnP SOS GPnP UPnP reference[11][6][17][16][8]this
year200920112013200820132014
central cameras
non-central cameras
geometric optimality
linear complexity ( )
multiple solutions
大学毕业论文格式
singularity-free rotation param. however employs a singularity-affected rotation matrix parametrization[2].The most recent contribution in O(n)-complexity PnP solvers is then given by the OPnP algorithm[17](2013),which esntially replaces the Cayley parametriza-tion by the singularity-free non-unit quaternion parametrization,thus leading to improved accuracy.They also exploit2-fold symmetry in the solver,thus avoiding the duality of quaternion solutions.Although they achieve very good accuracy,we still note that—from a theoretical point of view—their algorithm again falls back to an algebraic error.
An interesting fact is that—while arching for all stationary points—the DLS and OPnP algorithmsfind27and40solutions,respectively.In other words, despite of using more than the minimum amount of information,tho algorithms return far more solutions than a minimal solver.It is true that many of the stationary points can be neglected becau they are either complex or local maxima/saddle points,but still the computation at least intermediately reaches a emingly too high level of complexity.
More recently,people have also started to consider the generalized PnP prob-lem,which consists of estimating the position of a non-central or generalized camera given correspondences between arbitrary non-central rays in the camera frame and points in the world frame.[3],[14],and[8]prent mi
nimal solvers for the generalized PnP problem,proving that3correspondences are still enough and that the maximum number of possible solutions corresponds to8.Regarding the generalized PnP problem,there has been less progress to date.[5]prents thefirst linear complexity solution,however minimizes only an algebraic error. It fails in situations of multiple he minimal ca),and depends on a special variant for the planar ca.The linear complexity solution prented in[16](SOS)minimizes a geometric error,however again fails in the mentioned special cas,and depends on a computationally intensive,iterative convex re-laxation technique.Yet another algebraic O(n)solution to the generalized PnP problem has been discovered in2013[8](GPnP),and esntially consists of a generalization of the EPnP algorithm to the non-central ca.It thus comes with similar drawbacks.
月落参横Table1shows a summary of all relevant algorithms and their properties, including the propod UPnP algorithm.
130L.Kneip,H.Li,and Y.Seo
2Theory
We now proceed to the theoretical part of our method.We start by recalling the geometry of the absol
ute po problem in the generalized ca,which covers the classical perspective situation as well.We then derive a cost-function in the space of quaternions reflecting the geometrical error as a function of absolute orientation.All local minima are found by a clod-form computation of all sta-tionary points.This is achieved by computing a Gr¨o bner basis over the first-order optimality conditions and the quaternion unit-norm constraint.We also prent an alternative unit-norm constraint allowing us to exploit 2-fold symmetry in quaternion-space,thus reducing the number of solutions by a factor of two.We finally obtain an ideal number of solutions,and also introduce an easy way to verify cond-order optimality and polish the final result.
2.1Geometry of the Absolute Po
Problem
Fig.1.Point measurements of a generalized camera
Let p i ∈R 3describe a point in
the world frame,R ∈SO 3the
rotation from the world frame to
the camera frame,and t ∈R 3
the position of the world origin
en from the camera frame.The
measurements of p i in the cam-
era frame are given by non-central
rays expresd by αi f i +v i ,where
v i ∈R 3reprents a point on the
ray,f i ∈R 3the normalized direc-
法制宣传黑板报
tion vector of the ray,and αi the
depth.The situation is explained in Figure 1.The non-central pro-jection equation results to
αi f i +v i =Rp i +t ,i =1,...,n.(1)
R ,t ,and αi are the parameters to be computed from the inputs f i ,v i ,and p i .In ca the generalized camera is given by a multi-camera system,the v i ’s are simply the positions of the respective camera centers inside the main common frame.In this ca,some f i ’s may obviously have the same v for reflecting the non-centrality of their measurement.For a central camera,v i =0,i =1,...n .Let I be the 3×3identity matrix.We can stack all constraints into
⎡⎢⎣f 1−I ......f n −I ⎤⎥⎦⎡⎢⎢⎢⎣α1...αn t
⎤⎥⎥⎥⎦=⎡⎣R ...R ⎤⎦⎡⎢⎣p n ⎤⎥⎦−⎡⎢⎣v m ⎤⎥⎦⇔Ax =Wb −w .(2)
UPnP:An Optimal O (n )Solution with Universal Applicability 131
2.2Derivation of the Objective Function
The derivation of the objective function is bad on the work of [6]:–We start by applying block-wi matrix inversion to eliminate the unknown translation and point depths from the projection equations.(Result 1)
–The obtained expressions are then transformed into a residual that notably corresponds to the object-space error.(Definition 1)
–Factorization of the rotation matrix in the sum of squared object space errors then results in a fourth-order energy function of the quaternion variables.The measurement data inside this expression is compresd in form of linear-complexity summation terms.(Results 2&3)
We now proceed to the details of this derivation.
Result 1:x appears linearly in (2)and can be eliminated by x =(A T A )−1A T (Wb −w )= U V (Wb −w ).(3)The pudo-inver of A is hence partitioned such that the depth parameters are a function of U = u u T n T ,and the translation is a function of V .Back-substitution results in the rotation-only projection equation u T i (Wb −w ) f i +v i =Rp i +V (Wb −w ).
(4)Proof:The symbolic solution of x is mainly bad on [6].The derivation of the symbolic form of U and V is bad on a) f i =1,b)the Schur-complement,and c)block-wi matrix inversion.It results in
V 3×3n =[V 1,...,V n ],with
V i =H [f i f T i −I ]∈R 3×3
i =1,...,n ,and (5)H 3×3= n I −n i =1f i f T
i −1(6)U n ×3n =⎡
⎣f f T n ⎤⎦+⎡⎢⎣f f T n ⎤⎥⎦V =⎡⎢⎣u u T n ⎤
⎥⎦,with u T i =[u T i 1,...,u T in ]1×3n ,i =1,...,n ,and
u T ij =f T i δ(i,j )+f T i V j ∈R
1×3,i,j =1,...,n.(7)u T i reprents row i of U ,and u T ij reprents the 1×3element of U in row
i and column 3j .We obtain αi =u T i (Wb −w )and t =V (Wb −w ),and back-substitution in (1)yields the rotation-only constraint (4).1 1It is worth noting here that the DLS mechanism is the only one to solve for the linear elements (i.e.depth and translation)in a homogeneous way.While this might be irrelevant for the central ca,where we can assume that the z -coordinate in the camera frame is bi
万里长城第一关gger than 1,there is no guarantee on any coordinate in the gener-alized camera situation.In the non-central ca,the prented resolution therefore has better accuracy than the ones in [11]and [17].
