betaFeedback

WorksComputer Science

Object Pose: The Link between Weak Perspective, Paraperspective, and Full Perspective

Abstract

Recently, DeMenthon and Davis [4,5] proposed a method for determining the pose of a 3-D object with respect to a camera from 3-D to 2-D point correspondences. The method consists of iteratively improving the pose computed with a weak perspective camera model to converge, at the limit, to a pose estimation computed with a perspective camera model. In this paper we give an algebraic derivation of DeMenthon and Davis' method and we show that it belongs to a larger class of methods where the perspective camera model is approximated either at zero order (weak perspective) or first order (paraperspective). We describe in detail an iterative paraperspective pose computation method for both non coplanar and coplanar object points. We analyse the convergence of these methods and we conclude that the iterative paraperspective method (proposed in this paper) has better convergence properties than the iterative weak perspective method. We introduce a simple way of taking into account the orthogonality constraint associated with the rotation matrix. We analyse the sensitivity to camera calibration errors and we define the optimal experimental setup with respect to imprecise camera calibration. We compare the results obtained with this method and with a non-linear optimization method.

This work has been supported by the Esprit programme through the Basic Research Project SECOND (Esprit-BRA No. 6769). R. Horaud acknowledges partial support from the University of Bern, Institut für Informatik und angewandte Mathematik, where he was a visiting scientist during July 1994.

Introduction

Recently, DeMenthon & Davis [4], [5] proposed a method for determining the pose of a 3-D object with respect to a camera from 3-D to 2-D point correspondences. The method consists of iteratively improving the pose computed with a weak perspective camera model to converge, at the limit, to a pose estimation computed with a perspective camera model. To our knowledge, the method proposed by DeMenthon & Davis is among one of the first attempts to link linear techniques, associated with the weak perspective camera model, with non-linear techniques, associated with a perspective camera model. Indeed, on one side, linear resolution methods can be used but the solution thus obtained is just an approximation and, on the other side, non linear resolution methods lead to a very accurate solution but proper initialization is required.

One possibility could be to use a robust numerical method to perform the non linear minimization that is initialized with the solution obtained by a linear method. However, there are several drawbacks. First, such an approach does not take into account the simple mathematical link that exists between the perspective model and its linear approximations. Second, the linear approximation may be quite faraway from the true solution and a large number of iterations would be required before the non-linear minimization process converges to a stable solution. For example, as it will be described below, a non-linear method requires 10 times more iterations than the method of DeMenthon & Davis and than the method described in this paper.

The perspective projection is modelled by a projective transformation mapping the 3-D projective space to the 2-D projective plane. Weak perspective is just an affine approximation of full perspective. More precisely, it may well be viewed as a zero-order approximation: 1/(1+ε)≈11/(1+\varepsilon) \approx1. Paraperspective [1] is a first order approximation of full perspective: 1/(1+ε)≈1−ε1/(1+\varepsilon) \approx1-\varepsilon. The method proposed by DeMenthon & Davis starts with computing the pose of an object using weak perspective and after a few iterations converges towards a pose estimated under perspective. The method is very elegant, very fast, and quite accurate. It is however limited to situations where the weak perspective approximation is valid. If the object is close to the camera and/or at some distance away from the optical axis then the pose algorithm of DeMenthon & Davis either converges very slowly (100 iterations rather than 5 to 10) or it doesn’t converge at all.

In this paper we show how the initial method proposed in [4] and [5] may be extended to paraperspective. More precisely, we describe a method for computing object pose with a paraperspective model and we establish the link between paraperspective pose and perspective pose. We show that the case of a coplanar set of object points is somehow more complex than the case of a non coplanar set of object points and we describe a method which can deal with both cases. We show both theoretically and experimentally that our method has better convergence properties than the method proposed by DeMenthon & Davis. Moreover we introduce a simple computational way of taking into account the orthogonality constraint associated with the 3×33\times3 matrix describing the orientation between the 3-D object and the camera. Indeed, the linear pose algorithms using weak perspective and paraperspective do not guarantee that this matrix is orthogonal. The orthogonalization method that we describe below computes the best rotation in close form using unit quaternions. This orthogonalization method considerably increases the accuracy of the method at the cost of very few extra computations. We characterize the best experimental setup that allows one to compute a precise pose even in the presence of camera calibration errors. Finally we provide a comparison between the results obtained with this method and the results obtained with a non-linear minimization method [14], [15].

Background

The problem of object pose from 2-D to 3-D correspondences has received a lot of attention both in the photogrammetry and computer vision literatures. Haralick et al. [10] cites a German dissertation from 1958 that surveys nearly 80 different solutions from the photogrammetry literature. Various approaches to the object pose (or external camera parameters) problem fall into 2 distinct categories: closed-form solutions and numerical solutions.

Closed-form solutions may be applied only to a limited number of correspondences [8], [11], [6]. Whenever the number of correspondences is larger than 4 then closed-form solutions are not efficient any more and iterative numerical solutions are necessary [18], [12], [10]. These approaches are, in general, very robust but they converge towards the correct solution on the premise that a good initial estimate of the true solution is provided. Phong et al. [15] describe a method that uses trust-region optimisation and that is less sensitive to initialisation than other minimization methods. However, the method of Phong et al. performs well for a relatively large number of correspondences. Whenever the number of correspondences is between 3 and 10, then the trust-region minimization method either requires a large number of iterations or doesn’t converge towards the correct solution. From a practical point of view, it is important to have available an object pose algorithm which doesn’t necessarily require a large number of correspondences and which doesn’t suffer from the limitations that are inherent to closed-form methods.

The method recently proposed by DeMenthon & Davis [4], [5] requires an arbitrary number of point correspondences. The 3-D points must be in general position (i.e., non coplanar) and there should be at least 4 point correspondences. The method is fast and it is robust with respect to image measurements and to camera calibration errors. However, the object pose algorithm as suggested by DeMenthon and Davis has convergence problems if the object is too faraway from the optical axis of the camera — a limitation that can be overcome as explained farther in this paper. The method of DeMenthon & Davis was extended to the case of a coplanar set of points by Oberkampf, DeMenthon, and Davis [13] and by DeMenthon [3].

Paper organization

The remainder of this paper is organized as follows. In Section 2 we briefly recall the perspective camera model and two possible approximations of this model, weak and paraperspective. Section 3 describes the iterative weak perspective algorithm as it has been proposed in [5]. Section 4 describes the new iterative paraperspective algorithm that we propose as well as how to compute the object pose from a paraperspective approximation. Section 5 provides details for solving the linear equations associated with pose computation in the case of both non coplanar and planar sets of object points. § 7 analyses the convergence of both the iterative weak and paraperspective algorithms and § 8 shows how to improve the pose algorithms using a simple and straightforward formulation of the orthogonality constraint. § 9 analyses the sensitivity of both algorithms with respect to camera calibration errors, and § 10 provides an experimental comparison of the two methods described in this paper together with a comparison of these methods with a non-linear minimization method. § 11 shows many examples of application of pose computation. Finally, § 12 provides a discussion and gives directions for future work.

Camera models

We consider a simple setup, as depicted on Figure 1. We denote by PiP_i a 3-D point with coordinates XiX_i, YiY_i, and ZiZ_i in a frame that is attached to the object – the object frame. The origin of this frame is the object point P0P_0. An object point PiP_i projects onto the image in pip_i with camera coordinates xix_i and yiy_i and we have (PiP_i is the vector from point P0P_0 to point PiP_i):

General setup for object pose

Figure 1. This figure shows the general setup. One of the object’s point is selected as the origin of the object frame. Therefore, the pose parameters are the coordinates of this object point (P0P_0) in the camera frame and the orientation of the object frame with respect to the camera frame.

xi=i⋅Pi+txk⋅Pi+tz(1)x_i = \frac{\mathbf{i} \cdot P_i + t_x}{\mathbf{k} \cdot P_i + t_z} \tag*{(1)}
yi=j⋅Pi+tyk⋅Pi+tz(2)y_i = \frac{\mathbf{j} \cdot P_i + t_y}{\mathbf{k} \cdot P_i + t_z} \tag*{(2)}

These equations describe the classical perspective camera model where the rigid transformation from the object frame to the camera frame is:

T=(iTtxjTtykTtz0001)=(Rt0001)T = \begin{pmatrix} \mathbf{i}^{T} & t_x \\ \mathbf{j}^{T} & t_y \\ \mathbf{k}^{T} & t_z \\ 0 & 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} R & t \\ 0 & 0 & 0 & 1 \end{pmatrix}

The relationship between the camera coordinates and the image coordinates may be easily obtained by introducing the intrinsic camera parameters:

ui=αuxi+uc(3)u_i = \alpha_u x_i + u_c \tag*{(3)}
vi=αvyi+vc(4)v_i = \alpha_v y_i + v_c \tag*{(4)}

In these equations αu\alpha_u and αv\alpha_v are the vertical and horizontal scale factors and ucu_c and vcv_c are the image coordinates of the intersection of the optical axis with the image plane.

We divide both the numerator and the denominator of eqs. (1) and (2) by tzt_z. We introduce the following notations:

  • I=i/tzI = \mathbf{i}/t_z is the first row of the rotation matrix scaled by the zz-component of the translation vector;

  • J=j/tzJ = \mathbf{j}/t_z is the second row of the rotation matrix scaled by the zz-component of the translation vector;

  • x0=tx/tzx_0 = t_x/t_z and y0=ty/tzy_0 = t_y/t_z are the camera coordinates of p0p_0 which is the projection of P0P_0 – the origin of the object frame, and

  • εi=k⋅Pi/tz\varepsilon_i = \mathbf{k} \cdot P_i/t_z.

We may now rewrite the perspective equations as:

xi=I⋅Pi+x01+εi(5)x_i = \frac{I \cdot P_i + x_0}{1 + \varepsilon_i} \tag*{(5)}
yi=J⋅Pi+y01+εi(6)y_i = \frac{J \cdot P_i + y_0}{1 + \varepsilon_i} \tag*{(6)}

These equations may also be written as in [5]:

xi(1+εi)−x0=I⋅Pi(7)x_i(1 + \varepsilon_i) - x_0 = I \cdot P_i \tag*{(7)}
yi(1+εi)−y0=J⋅Pi(8)y_i(1 + \varepsilon_i) - y_0 = J \cdot P_i \tag*{(8)}

Whenever the object is at some distance from the camera, the εi\varepsilon_i are small compared to 1. We may therefore introduce two approximations of the perspective equations: weak and paraperspective. One can find a geometric description of these projections in [16].

Weak perspective

Weak perspective assumes that the object points lie in a plane parallel to the image plane passing through the origin of the object frame, i.e., P0P_0, e.g., Figure 2. This is equivalent to a zero-order approximation:

Figure 2. This figure shows p0p_0, pip_i — the perspective projections of two object points, P0P_0 and PiP_i, and piwp_i^w, pipp_i^p — the weak and paraperspective projections of PiP_i. The quality of the paraperspective projection depends on the angle between the line of projection of PiP_i and the line of projection of P0P_0. Similarly, the quality of the weak perspective projection depends on the angle between the line of projection of PiP_i and the optical axis.

11+εi≈1∀i, i∈{1...n}\frac{1}{1+\varepsilon_i} \approx1 \quad\forall i,\ i \in\{1...n\}

With this approximation, eqs. (5) and (6) become:

xiw−x0=I⋅Pi(9)x_i^w-x_0=\mathbf{I}\cdot\mathbf{P}_i \tag*{(9)}
yiw−y0=J⋅Pi(10)y_i^w-y_0=\mathbf{J}\cdot\mathbf{P}_i \tag*{(10)}

In these two equations xiwx_i^w and yiwy_i^w are the camera coordinates of the weak perspective projection of the point PiP_i. By identification with eqs. (7) and (8) we obtain the relationship between the weak perspective and the perspective projections of PiP_i:

xiw=xi(1+εi)(11)x_i^w=x_i(1+\varepsilon_i) \tag*{(11)}
yiw=yi(1+εi)(12)y_i^w=y_i(1+\varepsilon_i) \tag*{(12)}

These equations allow us to determine the quality of the weak perspective approximation with respect to the perspective projection. Indeed the error between the weak perspective projection and the “true” projection is:

Δxw=∣xiw−xi∣=∣xiεi∣(13)\Delta x^w=\left|x_i^w-x_i\right|=\left|x_i\varepsilon_i\right| \tag*{(13)}
Δyw=∣yiw−yi∣=∣yiεi∣(14)\Delta y^w=\left|y_i^w-y_i\right|=\left|y_i\varepsilon_i\right| \tag*{(14)}

Hence the quality of the approximation depends both on the value of εi\varepsilon_i AND on the position of the point in the image. We consider for example a 512×512512 \times512 image. Approximate values for the intrinsic parameters are: αu=αv=1000\alpha_u=\alpha_v=1000 and uc=vc=256u_c=v_c=256. Therefore using eq. (3) and (4) we have:

0≤xi, yi≤0.250\leq x_i,\ y_i\leq0.25

The lower bound corresponds to the point of intersection of the optical axis with the image plane (xi=yi=0x_i=y_i=0). The upper bound corresponds to the image borders:

xi=ui−ucαu=512−2561000≈0.25x_i=\frac{u_i-u_c}{\alpha_u}=\frac{512-256}{1000}\approx0.25

We conclude that for small distance/size ratios, i.e., large values for εi\varepsilon_i, the weak perspective approximation is still valid provided that the object lies in the neighbourhood of the optical axis.

Paraperspective

Paraperspective may almost be viewed as a first-order approximation of perspective. Indeed, two approximations are needed in order to obtain the paraperspective camera model. With the approximation:

11+εi≈1−εi∀i, i∈{1...n}\frac{1}{1+\varepsilon_i}\approx1-\varepsilon_i \quad\forall i,\ i\in\{1...n\}

we obtain the paraperspective projection of PiP_i, e.g., Figure 2:

xip=(I⋅Pi+x0)(1−εi)≈I⋅Pi+x0−x0εi=i⋅Pitz+x0−x0k⋅Pitzx_i^p=(\mathbf{I}\cdot\mathbf{P}_i+x_0)(1-\varepsilon_i) \approx\mathbf{I}\cdot\mathbf{P}_i+x_0-x_0\varepsilon_i =\frac{\mathbf{i}\cdot\mathbf{P}_i}{t_z}+x_0-x_0\frac{\mathbf{k}\cdot\mathbf{P}_i}{t_z}

where the term in 1/tz21/t_z^2 was neglected. There is a similar expression for yipy_i^p.

Finally, the paraperspective equations are:

xip−x0=i−x0ktz⋅Pi(15)x_i^p-x_0=\frac{\mathbf{i}-x_0\mathbf{k}}{t_z}\cdot\mathbf{P}_i \tag*{(15)}
yip−y0=j−y0ktz⋅Pi(16)y_i^p-y_0=\frac{\mathbf{j}-y_0\mathbf{k}}{t_z}\cdot\mathbf{P}_i \tag*{(16)}

In order to obtain the relationship between the paraperspective and the perspective projections of PiP_i we can write these equations as follows:

xip=x0+I⋅Pi−x0εix_i^p=x_0+\mathbf{I}\cdot\mathbf{P}_i-x_0\varepsilon_i
yip=y0+J⋅Pi−y0εiy_i^p=y_0+\mathbf{J}\cdot\mathbf{P}_i-y_0\varepsilon_i

Again, by identification with eqs. (7) and (8) we obtain the relationship between the paraperspective and the perspective projections of PiP_i:

xip=xi(1+εi)−x0εi(17)x_i^p = x_i(1+\varepsilon_i)-x_0\varepsilon_i \tag*{(17)}
yip=yi(1+εi)−y0εi(18)y_i^p = y_i(1+\varepsilon_i)-y_0\varepsilon_i \tag*{(18)}

As in the previous section, we can easily estimate the error between the paraperspective and perspective projections:

Δxp=∣xip−xi∣=∣(xi−x0)εi∣(19)\Delta x^p = \lvert x_i^p-x_i\rvert= \lvert(x_i-x_0)\varepsilon_i\rvert \tag*{(19)}
Δyp=∣yip−yi∣=∣(yi−y0)εi∣(20)\Delta y^p = \lvert y_i^p-y_i\rvert= \lvert(y_i-y_0)\varepsilon_i\rvert \tag*{(20)}

Whenever an object point PiP_i is far from the optical axis then the weak perspective model is a poor approximation. However, a proper choice of the origin, i.e, P0P_0, and the use of the paraperspective model can compensate and provide a good approximation even if εi\varepsilon_i is not small.

From weak perspective to perspective

In order to solve the pose problem, DeMenthon & Davis [5] noticed that eqs. (9) and (10) are similar to eqs. (7) and (8) for which the εi\varepsilon_i are set to 0. They conclude that:

  • Whenever the εi\varepsilon_i are fixed (not necessarily null) the pose equations (7) and (8) become linear in II and JJ. A solution can be found if at least 4 object points are provided (see § 6).

  • It is possible to solve eqs. (7) and (8) iteratively by successive linear approximations.

In this case the pose algorithm proposed in [5] starts with a weak perspective camera model and computes an approximated pose. This approximated pose is improved iteratively as follows:

  1. For all ii, i∈{1...n}i \in\{1...n\}, n≥3n \ge3, εi=0\varepsilon_i=0;

  2. Solve the overconstrained linear system of equations (7) and (8) which provides an estimation of vectors II and JJ, i.e., § 6;

  1. Compute the position and orientation of the object frame with respect to the camera frame:

tz=12(1∥I∥+1∥J∥)t_z = \frac{1}{2}\left(\frac{1}{\lVert I\rVert}+\frac{1}{\lVert J\rVert}\right)
tx=x0tzt_x=x_0t_z
ty=y0tzt_y=y_0t_z
i=I∥I∥i=\frac{I}{\lVert I\rVert}
j=J∥J∥j=\frac{J}{\lVert J\rVert}
k=i×jk=i\times j
  1. For all ii, compute:

εi=k⋅Pitz\varepsilon_i=\frac{k\cdot P_i}{t_z}

If the εi\varepsilon_i computed at this iteration are equal to the εi\varepsilon_i computed at the previous iteration then stop the procedure, otherwise go to step 2.

While iterating, the above algorithm replaces the actual image coordinates xix_i and yiy_i (which are perspective projections of a 3-D point) with xi(1+εi)x_i(1+\varepsilon_i) and yi(1+εi)y_i(1+\varepsilon_i), which are weak perspective projections of the same 3-D point. A geometric interpretation of this algorithm can be found in [3, 5].

From paraperspective to perspective

In this section we provide a generalization of the above algorithm to deal with the paraperspective case. We consider again the perspective equations (7) and (8) and let us subtract the paraperspective term from both the left and right sides of these equations. We obtain:

xi(1+εi)−x0−x01tzk⋅Pi=1tzi⋅Pi−x01tzk⋅Pix_i(1+\varepsilon_i)-x_0-x_0\frac{1}{t_z}k\cdot P_i=\frac{1}{t_z}i\cdot P_i-x_0\frac{1}{t_z}k\cdot P_i
yi(1+εi)−y0−y01tzk⋅Pi=1tzj⋅Pi−y01tzk⋅Piy_i(1+\varepsilon_i)-y_0-y_0\frac{1}{t_z}k\cdot P_i=\frac{1}{t_z}j\cdot P_i-y_0\frac{1}{t_z}k\cdot P_i

These equations can be written more compactly as:

(xi−x0)(1+εi)=Ip⋅Pi(21)(x_i-x_0)(1+\varepsilon_i)=I_p\cdot P_i \tag*{(21)}
(yi−y0)(1+εi)=Jp⋅Pi(22)(y_i-y_0)(1+\varepsilon_i)=J_p\cdot P_i \tag*{(22)}

with:

Ip=i−x0ktz(23)I_p=\frac{i-x_0k}{t_z} \tag*{(23)}
Jp=j−y0ktz(24)J_p=\frac{j-y_0k}{t_z} \tag*{(24)}

One may notice that when all the εi\varepsilon_i are null, the perspective equations above – eqs. (21) and (22) – become identical to the paraperspective equations – eqs. (15) and (16).

As in the weak perspective case, we have now a linear method for computing the pose with a paraperspective model and an iterative method to compute the object pose with a perspective model by successive paraperspective approximations. More precisely, the pose parameters can be derived from IpI_p and JpJ_p as follows.

First, one may notice that:

∥Ip∥2=(i−x0k)⋅(i−x0k)tz2=1+x02tz2\lVert I_p\rVert^2 = \frac{(i-x_0 k)\cdot(i-x_0 k)}{t_z^2} = \frac{1+x_0^2}{t_z^2}

and:

∥Jp∥2=1+y02tz2\lVert J_p\rVert^2 = \frac{1+y_0^2}{t_z^2}

We therefore obtain:

tz=12(1+x02∥Ip∥+1+y02∥Jp∥)(25)t_z = \frac{1}{2}\left(\frac{\sqrt{1+x_0^2}}{\lVert I_p\rVert}+\frac{\sqrt{1+y_0^2}}{\lVert J_p\rVert}\right) \tag*{(25)}

and:

tx=x0tzt_x=x_0t_z
ty=y0tzt_y=y_0t_z

Second, we derive the three orthogonal unit vectors ii, jj, and kk. From eqs. (23) and (24) we obtain:

i=tzIp+x0k(26)i=t_z I_p+x_0 k \tag*{(26)}
j=tzJp+y0k(27)j=t_z J_p+y_0 k \tag*{(27)}

The third vector, kk is the cross-product of these two vectors:

k=i×j=tz2Ip×Jp+tzy0Ip×k−tzx0Jp×kk=i\times j =t_z^2 I_p\times J_p+t_zy_0 I_p\times k-t_zx_0 J_p\times k

Let S(a)S(a) be the skew-symmetric matrix associated with a 3-vector aa and I3×3I_{3\times3} be the identity matrix. The previous expression can now be written as follows:

(I3×3−tzy0S(Ip)+tzx0S(Jp))k=tz2Ip×Jp(28)\left(I_{3\times3}-t_zy_0 S(I_p)+t_zx_0 S(J_p)\right)k=t_z^2 I_p\times J_p \tag*{(28)}

This equation allows us to compute kk, provided that the linear system above has full rank. Indeed, the 3×33\times3 matrix AA:

A=I3×3−tzy0S(Ip)+tzx0S(Jp)A=I_{3\times3}-t_zy_0 S(I_p)+t_zx_0 S(J_p)

is of the form:

A=(1c−b−c1ab−a1)A=\begin{pmatrix} 1 & c & -b\\ -c & 1 & a\\ b & -a & 1 \end{pmatrix}

Its determinant is always strictly positive:

det⁡(A)=1+a2+b2+c2\det(A)=1+a^2+b^2+c^2

Therefore, one can easily determine kk using eq. (28) and ii and jj using eqs. (26) and (27).

The εi\varepsilon_i can now be easily computed as before and the pose algorithm becomes:

  1. For all ii, i∈{1...n}i\in\{1...n\}, n≥3n\geq3, εi=0\varepsilon_i=0;

  2. Solve the overconstrained linear system of equations (21) and (22) which provides an estimation of vectors IpI_p and JpJ_p, i.e., § 6;

  3. Compute the position (txt_x, tyt_y, and tzt_z) and orientation (ii, jj, and kk) of the object frame with respect to the camera frame as explained above in this Section;

  4. For all ii, compute:

εi=k⋅Pitz\varepsilon_i=\frac{k\cdot P_i}{t_z}

If the εi\varepsilon_i computed at this iteration are equal to the εi\varepsilon_i computed at the previous iteration then stop the procedure, otherwise go to step 2.

Solving the linear equations

Both the weak perspective and paraperspective iterative algorithms need to solve an overconstrained linear system of equations, namely eqs. (7), (8) (weak perspective) and eqs. (21), (22) (paraperspective). In matrix form these equations can be written as:

P⏟n×3I⏟3×1=x⏟n×1(29)\underbrace{P}_{n\times3}\underbrace{I}_{3\times1} =\underbrace{x}_{n\times1} \tag*{(29)}
P⏟n×3J⏟3×1=y⏟n×1(30)\underbrace{P}_{n\times3}\underbrace{J}_{3\times1} =\underbrace{y}_{n\times1} \tag*{(30)}

where PP is a n×3n\times3 matrix formed by the 3-D coordinates of nn vectors P1…PnP_1\ldots P_n. Since the point P0P_0 is the origin of the object frame, this matrix can be written as:

P=(X1Y1Z1⋮⋮⋮XnYnZn)P=\begin{pmatrix} X_1 & Y_1 & Z_1\\ \vdots& \vdots& \vdots\\ X_n & Y_n & Z_n \end{pmatrix}

In order to solve for these linear equations one has to distinguish two cases: non coplanar and coplanar sets of object points.

Non coplanar object points

If the object points are not coplanar, the rank of PP is 3 and therefore the solutions for II and JJ (and equivalently for IpI_p and JpJ_p) are simply given by:

I=(PTP)−1PTxI = (P^{T}P)^{-1}P^{T}x
J=(PTP)−1PTyJ = (P^{T}P)^{-1}P^{T}y

One may notice that the pseudo-inverse of PP can be computed off-line and hence the estimation of II and JJ is particularly efficient.

Coplanar object points

If the object points are coplanar then the rank of PP is 2 and the above solution cannot be considered anymore. We consider the plane formed in this case by the object points and let uu be the unit vector orthogonal to this plane. Vectors II and JJ (and equivalently IpI_p and JpJ_p) can be written as a sum of a vector belonging to this plane and a vector perpendicular to this plane, namely (see [3], [13] and Figure 3):

Figure 3. A coplanar configuration of object points.

I=I0+λu(31)I = I_0 + \lambda u \tag*{(31)}
J=J0+μu(32)J = J_0 + \mu u \tag*{(32)}

By substituting these expressions for II and JJ into eqs. (29) and (30) we obtain:

PI0=xP I_0 = x
PJ0=yP J_0 = y

These linear equations can be solved provided that the following additional linear constraints are used:

u⋅I0=0u \cdot I_0 = 0
u⋅J0=0u \cdot J_0 = 0

Thus we obtain solutions for I0I_0 and J0J_0 as follows.

I0=(P′TP′)−1P′T(x0)I_0 = (P^{\prime T}P^\prime)^{-1}P^{\prime T} \begin{pmatrix} x \\ 0 \end{pmatrix}
J0=(P′TP′)−1P′T(y0)J_0 = (P^{\prime T}P^\prime)^{-1}P^{\prime T} \begin{pmatrix} y \\ 0 \end{pmatrix}

With P′P^\prime defined by:

P′=(Pu)P^\prime= \begin{pmatrix} P \\ u \end{pmatrix}

Obviously, the rank of P′P^\prime is equal to 3.

In order to estimate II and JJ (and equivalently IpI_p and JpJ_p) one is left with the estimation of two scalars, λ\lambda and μ\mu. In the case of weak perspective Oberkampf, DeMenthon, and Davis [13] provided a solution using the constraints ∥I∥=∥J∥\lVert I\rVert= \lVert J\rVert and I⋅J=0I \cdot J = 0.

In the case of paraperspective a similar solution can be obtained using the following constraints onto IpI_p and JpJ_p (derived from eqs. (23) and (24)):

∥Ip∥2=1+x02tz2\lVert I_p\rVert^2 = \frac{1+x_0^2}{t_z^2}
∥Jp∥2=1+y02tz2\lVert J_p\rVert^2 = \frac{1+y_0^2}{t_z^2}
Ip⋅Jp=x0y0tz2I_p \cdot J_p = \frac{x_0y_0}{t_z^2}

By eliminating tzt_z we obtain two constraints:

Ip⋅Jp=x0y01+x02∥Ip∥2I_p \cdot J_p = \frac{x_0y_0}{1+x_0^2}\lVert I_p\rVert^2
Ip⋅Jp=x0y01+y02∥Jp∥2I_p \cdot J_p = \frac{x_0y_0}{1+y_0^2}\lVert J_p\rVert^2

By substituting in these expressions IpI_p and JpJ_p given by eqs. (31) and (32) we obtain:

I0⋅J0+λμ=x0y01+x02(∥I0∥2+λ2)I_0 \cdot J_0 + \lambda\mu= \frac{x_0y_0}{1+x_0^2}\left(\lVert I_0\rVert^2+\lambda^2\right)
I0⋅J0+λμ=x0y01+y02(∥J0∥2+μ2)I_0 \cdot J_0 + \lambda\mu= \frac{x_0y_0}{1+y_0^2}\left(\lVert J_0\rVert^2+\mu^2\right)

And finally, by eliminating μ\mu we obtain a biquadratic equation in one unknown:

Aλ4+Bλ2+C=0(33)A\lambda^4+B\lambda^2+C=0 \tag*{(33)}

With:

A=a2−gA = a^2 - g
B=2a2d−gd+e−2acB = 2a^2d - gd + e - 2ac
C=a2d2+c2−2acdC = a^2d^2 + c^2 - 2acd
a=x0y01+x02a = \frac{x_0y_0}{1+x_0^2}
b=x0y01+y02b = \frac{x_0y_0}{1+y_0^2}
c=I0⋅J0c = I_0 \cdot J_0
d=∥I0∥2d = \lVert I_0\rVert^2
e=∥J0∥2e = \lVert J_0\rVert^2
g=1+y021+x02g = \frac{1+y_0^2}{1+x_0^2}

In order to study the number of real roots of eq. (33) we substitute λ2\lambda^2 by tt:

At2+Bt+C=0At^2 + Bt + C = 0

We examine the signs of the roots of this equation. Therefore we have to examine the sign of their product, i.e., C/AC/A. We have:

CA=f(x0,y0,c,d)=−x02y02d2−(1+x02)2c2+2x0y0(1+x02)cd1+x02+y02=−(x0y0d−(1+x02)c)21+x02+y02\begin{aligned} \frac{C}{A} = f(x_0,y_0,c,d) \\ &= -\frac{x_0^2y_0^2d^2-(1+x_0^2)^2c^2+2x_0y_0(1+x_0^2)cd}{1+x_0^2+y_0^2} \\ &= -\frac{(x_0y_0d-(1+x_0^2)c)^2}{1+x_0^2+y_0^2} \end{aligned}

Therefore, the value of C/AC/A is either negative or null. Therefore there are one positive (or null) root and one negative (or null) root for tt. Hence there are two real roots for λ\lambda – a positive one and a negative one – and two imaginary roots.

The two real roots for λ\lambda provide two solutions for μ\mu and hence there are two solutions for IpI_p and JpJ_p. These two solutions correspond to the well-known reversal ambiguity associated with an affine camera model. These two solutions are shown on Figure 4. The points PiP_i (lying on the planar object in one orientation) and Pi′P'_i (lying on the planar object in another orientation) have the same paraperspective projection but different perspective projections. Notice that these object orientations are symmetric with respect to a plane which is perpendicular to the line of sight passing through P0P_0.

Figure 4. A planar object and a paraperspective camera model produces two orientations. However, these two object orientations have distinct perspective projections – pip_i and pi′p'_i.

Therefore, the iterative algorithm described in Section 4 produces two poses at each iteration. The two poses have the same translation vector but different orientations. Hence, after nn iterations there will be 2n2^n

solutions. In order to avoid this redundancy we proceed as follows. At the first iteration we retain both solutions while at the next iterations we retain only one solution – the solution which is the most consistent with the data. At convergence we obtain two solutions for the orientation of the planar object: one solution associated with the “left” branch of the search tree and another solution associated with the “right” branch of the search tree (see Figure 5). Among the final two solutions, one of them is generally closer to the image data than the other. However, if the orientation of the planar object is close to the orientation of the plane of symmetry, the ambiguity remains and the algorithm provides two solutions.

A binary tree search for selecting the best object pose when the object points are coplanar

Figure 5. A binary tree search for selecting the best object pose when the object points are coplanar.

An analysis of convergence

In order to analyse the convergence of these algorithms (sections 3 and 4) we consider again eqs. (7) and (8):

xi(1+εi)−x0=I⋅Pix_i(1+\varepsilon_i)-x_0 = \mathbf{I}\cdot\mathbf{P}_i
yi(1+εi)−y0=J⋅Piy_i(1+\varepsilon_i)-y_0 = \mathbf{J}\cdot\mathbf{P}_i

as well as eqs. (21) and (22):

(xi−x0)(1+εi)=Ip⋅Pi(x_i-x_0)(1+\varepsilon_i) = \mathbf{I}_p\cdot\mathbf{P}_i
(yi−y0)(1+εi)=Jp⋅Pi(y_i-y_0)(1+\varepsilon_i) = \mathbf{J}_p\cdot\mathbf{P}_i

Both these sets of equations describe the full perspective projection. The first ones allows to express the pose problem in terms of an iterative weak perspective algorithm while the second ones allows to express the pose problem in terms of an iterative paraperspective algorithm. From Figure 2 and § 3 we have:

  • x0x_0 and y0y_0 are the camera coordinates of p0p_0, the perspective projection of P0P_0;

  • xix_i and yiy_i are the camera coordinates of pip_i, the perspective projection of PiP_i;

  • xi(1+εi)x_i(1+\varepsilon_i) and yi(1+εi)y_i(1+\varepsilon_i) are the camera coordinates of piwp_i^w, the weak perspective projection of PiP_i;

  • xi(1+εi)−x0εix_i(1+\varepsilon_i)-x_0\varepsilon_i and yi(1+εi)−y0εiy_i(1+\varepsilon_i)-y_0\varepsilon_i are the camera coordinates of pipp_i^p, the paraperspective projection of PiP_i;

Therefore, if good estimates for εi\varepsilon_i (i∈{1...n}i\in\{1...n\}) are available, then the perspective pose problem is reduced to solving an overconstrained set of linear equations. These equations provide a solution either for I\mathbf{I} and J\mathbf{J} or for Ip\mathbf{I}_p and Jp\mathbf{J}_p from which a pose may be easily calculated. However, in practice it is rather difficult to provide such estimates. Hence, one has to use a heuristic. The simplest heuristic is to initialize the values of εi\varepsilon_i to zero and to use either the iterative weak perspective or the iterative paraperspective algorithms.

We consider the first one of these two algorithms and let εi∗\varepsilon_i^* be the true values that the algorithm is supposed to compute. Therefore, at the first iteration, one attempts to solve in a least-square sense a linear set of equations of the form:

{⋮I⋅Pi=xi−x0J⋅Pi=yi−y0⋮\left\{ \begin{array}{c} \vdots\\ \mathbf{I}\cdot\mathbf{P}_i=x_i-x_0\\ \mathbf{J}\cdot\mathbf{P}_i=y_i-y_0\\ \vdots \end{array} \right.

The pose thus computed is just an approximation since one uses xix_i and yiy_i instead of xiwx_i^w and yiwy_i^w. Therefore the “pose errors” are proportional to the following “projection errors”:

Δiw=∥pi−piw∥2=(xi2+yi2)∣εi∗∣2\Delta_i^w=\lVert p_i-p_i^w\rVert^2=(x_i^2+y_i^2)\lvert\varepsilon_i^*\rvert^2

If these projection errors are large, the linear least-square solution provided by the first iteration of the algorithm will be rather different than the true solution and convergence cannot be guaranteed. DeMenthon & Davis noticed that the iterative weak perspective algorithm converges with values as large for εi∗\varepsilon_i^* as 1, provided that the object lies in the neighbourhood of the optical axis. Indeed, when the object is close to the optical axis, the camera coordinates of its projections, xix_i and yiy_i, are small (the origin of the camera frame lies onto the optical axis) and they compensate for the large values of εi∗\varepsilon_i^*.

In theory, the iterative paraperspective algorithm is able to deal with configurations where the weak perspective algorithm diverges. Indeed, in the case of paraperspective, the projection errors are:

Δip=∥pi−pip∥2=((xi−x0)2+(yi−y0)2)∣εi∗∣2=∥pi−p0∥2∣εi∗∣2\begin{aligned} \Delta_i^p=\lVert p_i-p_i^p\rVert^2=\left((x_i-x_0)^2+(y_i-y_0)^2\right)\lvert\varepsilon_i^*\rvert^2 \\ &=\lVert p_i-p_0\rVert^2\lvert\varepsilon_i^*\rvert^2 \end{aligned}

Whenever one wants to use the paraperspective camera model, the choice for p0p_0 (and hence for P0P_0) is crucial. The best way to choose p0p_0 is to compute the center of gravity of all the image points and to select the image point which is the closest to this center of gravity. Hence, xi−x0x_i-x_0 and yi−y0y_i-y_0 will be small and they will compensate for large values of εi∗\varepsilon_i^*. Therefore, the iterative paraperspective algorithm is likely to converge for those configurations where the weak perspective one diverges. Notice that if the point p0p_0 thus computed lies in the vicinity of the optical axis then the paraperspective and weak perspective models will yield the same results.

The orthogonality constraint

The algorithms described so far are linear and in the general case (non coplanar object points) they don’t guarantee that the matrix describing the orientation of the object frame with respect to the camera frame is a rotation matrix. This matrix is formed by the three row vectors iT\mathbf{i}^{T}, jT\mathbf{j}^{T}, and kT\mathbf{k}^{T}. These vectors are updated at each step of the pose algorithms and we want to compute a rotation matrix from these three vectors. In other words, we seek a rotation matrix RR which verifies:

R(iTjTkT)=I3×3R\left(\begin{array}{c} \mathbf{i}^{T}\\ \mathbf{j}^{T}\\ \mathbf{k}^{T} \end{array}\right)=I_{3\times3}

This expression can be written as:

Ri=e1R i = e_1
Rj=e2R j = e_2
Rk=e3R k = e_3

where eie_i is the ithi^{\text{th}} column of the identity matrix. The solution is given by the rotation matrix which minimizes the following criterion:

min⁡R∑i=13∥Rvi−ei∥2\min_R \sum_{i=1}^{3} \lVert R v_i-e_i\rVert^2

where viv_i is either ii, jj, or kk. It is well known that this minimization problem has a closed-form solution [7]. Indeed, if the unknown rotation is represented by a unit quaternion qq, then the minimization problem can be written as a quadratic form:

min⁡q(qTBq)\min_q(q^{T}Bq)

where B is a 4×44 \times4 symmetric, semi definite, and positive matrix. Therefore, the quaternion qq which minimizes this quadratic form is the eigen vector associated with the smallest eigen value of BB. One may notice that two vectors, i.e., ii and jj are sufficient for computing the orthogonal matrix RR.

Sensitivity to camera calibration

So far we assumed that the camera is calibrated, which means that the intrinsic camera parameters are known, i.e., eqs. (3) and (4). It is well known that camera calibration is difficult and that the camera parameters vary a lot. In this section we analyse the sensitivity of the pose algorithms that we just described with respect to variations of the intrinsic camera parameters.

We consider the equations associated with full perspective. By combining eqs. (3) and (4) with eqs. (7) and (8) we obtain:

ui(1+εi)−u0−ucεi=αuI⋅Pi(34)u_i(1+\varepsilon_i)-u_0-u_c\varepsilon_i=\alpha_u I\cdot P_i \tag*{(34)}
vi(1+εi)−v0−vcεi=αvJ⋅Pi(35)v_i(1+\varepsilon_i)-v_0-v_c\varepsilon_i=\alpha_v J\cdot P_i \tag*{(35)}

When a camera is calibrated, relatively stable values may be obtained for the horizontal and vertical scale factors αv\alpha_v and αu\alpha_u while the image coordinates of the optical center, ucu_c and vcv_c can vary with up to 10% of their nominal values [17], [7]. By inspecting the previous equations it is easy to notice that the influence of ucu_c and vcv_c is weighted by εi\varepsilon_i. For any object point PiP_i, εi\varepsilon_i is the projection of the vector P0PiP_0P_i onto the optical axis, divided by the z-component of the displacement vector tt.

If the object is too far from the camera, the influence of ucu_c and vcv_c can be neglected but one needs to detect image points with great accuracy. If the object is too close to the camera, the influence of ucu_c and vcv_c becomes quite large. Therefore, in practice, the object should be at a distance from the camera that is roughly 5 to 10 times the size of the object. In that case the values of εi\varepsilon_i will be between 0.1 and 0.2 and the error on ucu_c and vcv_c will be scaled down by a factor of 5 to 10. These remarks are validated by experimental results as reported in the next section.

Experiments

In this section we study the performances of the iterative weak and para perspective algorithms. Two types of performances are studied:

  • the precision of pose as a function of position and orientation of the object with respect to the camera in the presence of image and/or camera noise, and

  • the convergence of the iterative pose algorithms as a function of position and orientation of the object with respect to the camera.

In the first class of experiments (precision) we compare the results obtained with three algorithms: the two linear algorithms described above and a non-linear algorithm [15]. In the second class of experiments (convergence) we compare the two linear algorithms. In both classes, the simulated object is a configuration of four points (tetrahedron), such that the three line segments joining the reference point to the other three points are equal and perpendicular to each other.

For each experiment we fix a number of positions of the object with respect to the camera and for each such position the object is rotated at 1000 random orientations. These experiments are repeated for various levels of image and/or camera noise. The rotation matrices defining these 1000 orientations are computed from Euler angles chosen by a random number generator in the range [0,2π][0,2\pi]. The position of an object with respect to the camera is described by the translation vector from the center of projection of the camera to the origin of the object frame. More quantitatively, we compute the error between the theoretical pose and the pose computed by an algorithm. For each position we plot the average of this error over all the 1000 orientations. The pose errors are: orientation error and position error. The orientation error is defined as the rotation angle in degrees required to align the coordinate system of the object in its computed orientation with the coordinate system of the object in its theoretical orientation. The position error is defined as the norm of the vector which represents the difference between the two translation vectors: the computed one and the theoretical one, divided by the norm of the second vector. The horizontal coordinates of all the following plots represents the z-component of the translation vector scaled by the object size.

Figure 6 shows the variation of the error in orientation in the presence of image gaussian noise as a function of the ratio between the distance to the camera and the object size, where the object size has been fixed to a constant value. The three curves in this figure correspond to the iterative paraperspective algorithm (solid line), the iterative paraperspective algorithm with the orthogonal constraint described in § 8 (dotted line) and to the non-linear algorithm described in [15] (dashed). The iterative weak perspective algorithm yields a curve that is identical to the paraperspective one. Figure 7 shows the variation of the relative error in position in the presence of image gaussian noise as a function of the ratio between the distance to the camera and the object size. The solid line corresponds to the iterative weak and paraperspective algorithms (identical behaviour) and the dashed line corresponds to the non-linear algorithm. In both cases (Figure 6 and Figure 7) the image data has been perturbed with gaussian noise with a standard deviation equal to 1 pixel.

Average orientation error as a function of distance to camera divided by object size

Figure 6. Error in orientation as a function of depth in the presence of image gaussian noise. The solid line corresponds to the iterative paraperspective algorithm, the dotted line corresponds to the iterative paraperspective algorithm combined with the orthogonal constraint, and the dashed line corresponds to a non linear algorithm.

Average relative position error as a function of distance to camera divided by object size

Figure 7. Error in position as a function of depth in the presence of image gaussian noise. The iterative weak and paraperspective algorithms have the same behaviour (solid line) while the non linear algorithm (dashed line) performs slightly better.

Figure 8 shows the variation of the error in orientation as a function of the distance to the camera scaled by the object size. The difference between this figure and Figure 6 is that here we added uniformly distributed noise to the intrinsic camera parameters. Namely the coordinates of the optical axis in the image frame were perturbed with uniform noise in the interval [-15%, +15%]. The behaviour of the iterative paraperspective algorithm (solid line) is the one predicted by equations (34) and (35) – the effect of an inacurate center of projection vanishes as the object is farther away from the camera. For short distances the non-linear algorithm (dashed line) is more acurate than the iterative paraperspective algorithm.

Error in orientation as a function of depth in the presence of camera uniform noise

Figure 8. Error in orientation as a function of depth in the presence of camera uniform noise. The behaviour of the iterative paraperspective algorithm (solid line) is compared with a non linear algorithm (dashed line).

If we combine camera noise and image noise, then we obtain two other curves shown on Figure 9. Uniform pixel noise in the interval [-0.5, +0.5] has been added to the data. The iterative paraperspective algorithm (solid line) has a minimum for a distance/size ratio equal to 10. This is consistent with the theoretical predictions of § 9. We conclude that the optimal behaviour of the iterative pose algorithms occur when the distance between the object and the camera is 5 to 10 times the size of the object. In the presence of both

Error in orientation as a function of depth in the presence of camera and image uniform noise

Figure 9. Error in orientation as a function of depth in the presence of camera and image uniform noise. The iterative paraperspective algorithm (solid line) has a behaviour that differs from the non-linear algorithm (dashed line).

camera noise and image noise, the non linear algorithm (dashed line) performs better than the linear algorithm.

We compare now more thoroughly the two iterative pose algorithms. More precisely we study the convergence of these algorithms. We performed the following kinds of experiments. The first kind is meant to compare the number of iterations needed by each one of these algorithms to converge to the theoretical solution.

In order to take into account the effect of the offset from the optical axis, we constrain the origin of the object frame to belong to a fixed line of sight. The object offset can now be defined as the angle between this line of sight and the optical axis. For each such offset and for each position (depth) we randomly selected 1000 different orientations and we run both algorithms for each such position and orientation. We plot the average value of the number of iterations over all the 1000 random orientations.

Figures 10 and 11 show the number of iterations as a function of depth - more precisely, the distance from the object to the camera scaled by the object size. The lines with squares correspond to the weak perspective algorithm, the lines with triangles correspond to the paraperspective algorithm. These figures correspond respectively to two offsets, 23° and 30°. On an average, the paraperspective algorithm converges 2 to 3 times faster than the weak perspective algorithm.

The second kind is meant to compare the rate of convergence of each one of these algorithms for small distance/size ratios. Figures 12 and 13 show the percentage of the convergence of both algorithms as a function of depth. These figures correspond respectively to two offsets, 30° and 35°. As studied above in the paper, the weak perspective algorithm has an optimal behaviour when the object is either quite far from the camera or close to the optical axis. In theory, the paraperspective algorithm does not suffer from the offset limitations (see figures 10, 11, 12 and 13). For example (Figure 13), when the distance from the object to the camera is 1.4 times the size of the object, the paraperspective algorithm has always converged (solid line with triangles) while the weak perspective algorithm has converged only in 76 % of the configurations.

Examples

The iterative algorithms proposed in this paper have been applied to a number of images. For example, Figure 14 shows the image of a polyhedral object to be located (top-left) and its wireframe representation (top-right) whose position and orientation with respect to the camera has been roughly hypothesized. Both the image and the model are described by a network of straight lines and junctions which are matched using a method similar to the one described in [9]. Using this technique, 10 junctions were correctly matched (middle). The first iteration of the algorithm found a “paraperspective pose” (bottom-left). After only three iterations the algorithm correctly determined the position and orientation of the polyhedral object with respect to the camera (bottom-right).

Speed of convergence as a function of depth, offset equal to 23°

Figure 10. Speed of convergence as a function of depth, the offset is equal to 23° (triangles: paraperspective, squares: weak perspective).

Speed of convergence as a function of depth, offset equal to 30°

Figure 11. Speed of convergence as a function of depth, the offset is equal to 30° (triangles: paraperspective, squares: weak perspective).

The second example, i.e., Figure 15 illustrates a situation where only 4 junctions have been matched corresponding to coplanar model vertices (top). The first iteration found an approximated pose (bottom-left) and

An example of applying the iterative paraperspective algorithm to a set of 4 coplanar point correspondences

Figure 15. An example of applying the iterative paraperspective algorithm to a set of 4 coplanar point correspondences.

Rate of convergence as a function of depth, offset equal to 30°

Figure 12. Rate of convergence as a function of depth, the offset is equal to 30° (triangles: paraperspective, squares: weak perspective).

Rate of convergence as a function of depth, offset equal to 35°

Figure 13. Rate of convergence as a function of depth, the offset is equal to 35° (triangles: paraperspective, squares: weak perspective).

after 3 iterations the algorithm converged to the correct pose (bottom-right).

In both examples the iterative paraperspective algorithm converged after 0.7×10−30.7 \times10^{-3} seconds on a Sun/Sparc10.

The third example illustrates the behaviour of the linear and non linear algorithm with 4 coplanar object points, e.g., Figure 16 and Table 1. As one may easily notice, the iterative paraperspective algorithm is faster (both in term of number of iterations and CPU time) than the iterative weak perspective algorithm. The non-linear algorithm was initialized with the solution obtained by using a paraperspective model, i.e., the pose computed at the first iteration of the iterative paraperspective algorithm.

MethodNumber of iterationsCPU time (ms)
It. weak persp.104.3
It. parapersp.52.9
Non linear9165.3

Table 1. A comparison of the performance of the three algorithms. The computer being used is a Sun Sparc10/51.

The four image dots correspond to a coplanar set of object points

Figure 16. The four image dots correspond to a coplanar set of object points. Because the object is farther away from the optical axis, the iterative paraperspective method performs better in this case than the iterative weak perspective method.

An example of applying the iterative paraperspective algorithm to a non coplanar set of point correspondences

Figure 14. An example of applying the iterative paraperspective algorithm to a non coplanar set of point correspondences.

The fourth example illustrates the behaviour of the iterative paraperspective and non linear algorithms as a function of the number of point correspondences. As in the previous experiment we are interested by the speed of convergence of the algorithm and by the computation time. Figure 17-left shows the image of a scene and 11

Comparison of the object pose image and the paraperspective pose reconstruction

Figure 17. It takes 1.47 miliseconds on a Sun-Sparc10/51 to compute the pose in this case with the iterative paraperspective algorithm.

points that correspond to the vertices of a polyhedral object. Figure 17-right shows the pose found for this object using these 11 points and the iterative paraperspective algorithm.

Table 2 summarizes the results obtained with a varying number of point correspondences.

Iterative paraperspectiveNon linear
Number of pointsN. of iterationsCPU time (ms)N. of iterationsCPU time (ms)
450.8711487.5
550.956758.7
661.026668.0
751.066672.5
861.125870.5
961.3382108.6
1061.3878117.4
1161.4778123.6

Table 2. A comparison of the iterative paraperspective and non linear methods as a function of the number of points. One may notice the large number of iterations required by the non linear method for 4 point correspondences.

Discussion

In this paper we proposed an extension to paraperspective of the iterative weak perspective pose algorithm developped by DeMenthon & Davis [4]. We established a link between perspective, weak perspective, and paraperspective camera models. We described a linear method for computing object pose with a paraperspective model and an iterative algorithm which computes pose with a perspective model by successive paraperspective approximations.

We studied, both theoretically and experimentally, the convergence of the iterative weak and paraperspective algorithms. We showed that, on an average, the latter algorithm requires 2.5 times less iterations than the former algorithm. Moreover, when the object is relatively close to the camera and at some distance from the optical axis, then the chance of convergence of the paraperspective algorithm is higher than the chance of convergence of the weak perspective one. Because it requires, on an average, less iterations, the iterative paraperspective algorithm is more time-efficient than the iterative weak perspective algorithm. Of course, if the experimental conditions are such that the image center of gravity of the set of points is near the optical axis then the weak perspective model should be prefered.

We showed that both algorithms (iterative weak and paraperspective) can take advantage of a simple orthogonality constraint associated with the rotation matrix of the object pose.

Moreover, we compared the accuracy of the results obtained with these iterative linear algorithms with the results obtained with a non-linear one. The former algorithms are much faster and almost as precise as the latter, especially when the orthogonality constraint mentioned above is being used. However, in the presence of noise the performances of the iterative linear methods degrade faster with increasing noise amplitude than the non-linear method. This is due to the fact that non-linear minimization numerical techniques are much more robust to noise than linear algebraic techniques.

Whenever speed is an important concern, iterative linear pose methods should however be prefered. Indeed, the iterative linear algorithms described by DeMenthon and Davis [5] and in this paper are one hundred times faster than the non-linear algorithms – this feature allows one to include these iterative linear techniques in real-time vision and robotics applications.

It is interesting to notice that the iterative linear techniques described here are able to deal with the problem of reconstruction from multiple views [2]. Indeed, attempts have been made to solve the multiple view reconstruction problem using either an approximated (linear) camera model or a projective (non-linear) camera model, but no attempts have been made to properly establish a link between these two classes of algorithms.

References

  1. [1]Y. Aloimonos. Perspective approximations. Image and Vision Computing, 8(3):177–192, August 1990.DOI
  2. [2]S. Christy and R. Horaud. Euclidean shape and motion from multiple perspective views by affine iterations. Technical Report RR-2421, INRIA, December 1994. Available by anonymous ftp on imag.fr, directory pub/MOVI, file RR-2421.ps.gz.
  3. [3]D. F. DeMenthon. De la Vision Artificielle à la Réalité Synthétique: Système d’interaction avec un ordinateur utilisant l’analyse d’images vidéo. PhD thesis, Université Joseph Fourier - Grenoble I, Laboratoire TIMC/IMAG, October 1993.
  4. [4]D. F. DeMenthon and L. S. Davis. Model-based object pose in 25 lines of code. In G. Sandini, editor, Computer Vision – ECCV 92, Proceedings Second European Conference on Computer Vision, Santa Margherita Ligure, May 1992, pages 335–343. Springer Verlag, May 1992.
  5. [5]D. F. DeMenthon and L. S. Davis. Model-based object pose in 25 lines of code. International Journal of Computer Vision, 15(1/2):123–141, 1995.
  6. [6]M. M. Dhone, M. Richeton, J.T. Lapreste, and G. Rives. Determination of the Attitude of 3D Objects from a Single Perspective View. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(12):1265–1278, December 1989.
  7. [7]O. D. Faugeras. Three Dimensional Computer Vision: A Geometric Viewpoint. MIT Press, Boston, 1993.
  8. [8]M.A. Fischler and R.C. Bolles. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6):381–395, June 1981.
  9. [9]P. Gros. Matching and clustering: two steps towards automatic model generation in computer vision. In Proceedings of the AAAI Fall Symposium Series: Machine Learning in Computer Vision: What, Why, and How?, Raleigh, North Carolina, USA, pages 40–44, October 1993.
  10. [10]R. B. Haralick, H. Joo, C-N. Lee, X. Zhuang, V. G. Vaidya, and M. B. Kim. Pose estimation from corresponding point data. IEEE Transactions on Systems, Man, and Cybernetics, 19(6):1426–1445, 1989.
  11. [11]R. Horaud, B. Conio, O. Leboulleux, and B. Lacolle. An analytic solution for the perspective 4-point problem. Computer Vision, Graphics, and Image Processing, 47(1):33–44, July 1989.
  12. [12]D. Lowe. Fitting parameterized three-dimensional models to images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(5):441–450, May 1991.DOI
  13. [13]D. Oberkampf, D. F. DeMenthon, and L. S. Davis. Iterative pose estimation using coplanar feature points. In Proceedings Computer Vision and Pattern Recognition, pages 626–627, New York, June 1993. IEEE Computer Society Press, Los Alamitos, Ca.
  14. [14]T. Q. Phong, R. Horaud, A. Yassine, and D. T. Pham. Optimal estimation of object pose from a single perspective view. In Proceedings Fourth International Conference on Computer Vision, pages 534–539, Berlin, Germany, May 1993. IEEE Computer Society Press, Los Alamitos, Ca.
  15. [15]T. Q. Phong, R. Horaud, A. Yassine, and D. T. Pham. Object pose from 2-D to 3-D point and line correspondences. International Journal of Computer Vision, 15(3):225–243, July 1995.arxiv.org/abs/2610.19734
  16. [16]C. J. Poelman and T. Kanade. A paraperspective factorization method for shape and motion recovery. In Jan-Olof Eklundh, editor, Computer Vision - ECCV 94, Proceedings Third European Conference on Computer Vision, Stockholm, May 1994, volume 2, pages 97–108. Springer Verlag, May 1994.
  17. [17]R. Y. Tsai. A versatile camera calibration technique for high-accuracy 3D machine vision metrology using off-the-shelf TV cameras and lenses. IEEE Journal of Robotics and Automation, RA-3(4):323–344, August 1987.
  18. [18]J. S.-C. Yuan. A general photogrammetric method for determining object position and orientation. IEEE Transactions on Robotics and Automation, 5(2):129–142, April 1989.DOI

Paper details

vlnc:W_78cwn7fg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents