International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XXXIX-B1, 2012
XXII ISPRS Congress, 25 August — 01 September 2012, Melbourne, Australia
Algorithm 1: Rotation then Translation
1. Given N (N > 3) 3D-to-2D line correspondences and initial
rotation Ro, compute K; for i — 1,..., N. Define
B= (dy, dy, -- , dy). Set Kk —0.
2. Perform the following steps:
(a) Compute A= Ki{Ridy,:--, KyRidy).
(b) Compute M = AB” and perform SVD: UDV" = M.
(c) Compute Ry41 = USV”, where S is set according to
Eqs. (15) and (16).
(d) Terminate the iteration if convergence is reached;
otherwise, k — k 4- 1, go to setp (a).
3. Compute translation t via (18).
3.0 LOI-1: Rotation then Translation
We propose a pose estimation algorithm which optimizes alterna-
tively on the rotation matrix and translation vector.
Lemma 1 gives us a solution to the optimal estimate of rotation
matrix R. Let us assume we are given N 3D-to-2D line corre-
spondences and we have obtained the projection operator K; for
each correspondence. We define:
A = (K,Rd;, KoRd>,--- ,KyRdy).
B=(d.dy, , dy).
E, (R) then becomes :
E,(R) = ||A—RB]f. (17)
It is seen that Eq. (17) bears a close resemblance to Eg. (13).
This naturally lets us compute R iteratively as follows: given the
estimation rotation matrix Ry, at k-th iteration, we compute A(R)
and seek to minimize ||A(R;) — RBJ|? to get the next estimate
R41 according to the Lemma (1). This step is repeated until
convergence is achieved.
After attaining an estimate of rotation R, the optimal estimate of
translation t can be computed easily by minimizing E;(R,t) of
Eg. (9):
CR) (
r=
N
(I- Kj)! Y. (Ki - DRP;. (18)
i=l
Y
Clearly the matrix (x (I-K;)) must be invertible for Eq. (18)
to hold. Since I — K; — nn’, we have ( N d — K;)) = CC”,
where
ai ag «dw
Colb Pa. by
C1 C2 .... CN
Hence if rank(CCT) = 3, Eq. (18) can be well-defined. In fact,
rank(CC”) = rank(C) —3 is always true if N > 3 and the N in-
terpretation planes do not all intersect in one line. In other words,
if there are at least three of the 3D lines that do not intersect in
one point, the value of translation t can always be computed by
Eq. (18).
We now achieve a two-step pose estimation algorithm(LOI-1):
firstly the optimal R* is iteratively computed, and then the best
translation t* is obtained given the estimated R*. The algorithm
is summarized in Algorithm 1.
82
33 LOI-2: Alternative Optimization
In Algorithm 1, the objective function E; (R) is minimized firstly
to solve for rotation R. The estimate is then used to minimize the
objective function E;(R,t) to determine the translation t. This
method only uses the information of line direction to compute ro-
tation, and doesn’t use the set of constraints effectively. In the
framework of solving rotation and translation separately, the s-
mall errors in the rotation estimation are amplified into large er-
rors in the translation stage (Kumar, 1994). To fully exploit the
set of constraints, we can modify Algorithm 1 to optimize alter-
natively on the rotation matrix and translation vector.
Assuming we have obtained the k-th estimation of Ry, t, is com-
puted via #(R;). We firstly use the rotation estimation iterative
step of Algorithm 1 to estimate a new rotation value R',, ;, and
obtain a new estimate of translation t'; | via #(R’;,) from Eq.
(18). Then with (R',, ;, t^), We use the method of (Lu et al,
2000) to obtain the final (k + 1)-th estimation by minimizing the
objective function E? (R, t). The last step is described as follows.
In the algorithm of (Lu et al., 2000), R and t are iteratively opti-
mized by minimizing an object space objective function defined
for the point correspondences:
N
E(R.t) — ) |(I- Vi) (RP; -t)]". (19)
where V; is a projection matrix that, when applied to a point,
projects the point orthogonally to the line of sight defined by the
image point. When R^ and t^ are obtained, the next estimate
R^*! is determined by solving the following absolute orientation
problem:
N
R^ = arg min Y IRP; +t —Viqf|, (20)
i=1
where qf = R¥P; + t*. This absolute orientation problem is then
solved by SVD method (Horn et al., 1988).
It is seen that the only difference in Eq. (9) compared with Eq.
(19) is the use of projection matrix K; instead of V;. Both projec-
tion vectors K; and V; bear the same properties (Sect. 3.1). Hence
after we have obtained the estimates (R',,; , t^i, 1), an estimate of
rotation, Ry, 1, can be computed by directly using the algorithm
of (Lu et al., 2000) to minimize the objective function (9). The
new algorithm is summarized in Algorithm 2.
Obviously if given an initial estimate for both R and t, purely
minimizing E> (R,t) by using the the method of (Lu et al., 2000)
leads to another algorithm (we denote it as LOI-3). Since the only
difference is the definition and use of a projection vector, we will
not go further on this algorithm. For more details, the readers are
referred to (Lu et al., 2000).
4 EXPERIMENTS
To evaluate our methods, we carried experiments on both syn-
thetic and real data.
4.1 Synthetic Data
A set of 3D lines are generated uniformly within a cube defined
by [-0.5,0.5] x [-0.5,0.5] x [-0.5,0.5] (Fig. ??) in the object
space. The corresponding 2D lines are then created by linear fit-
ting of the projections of a set of sampling points in the 3D lines.
Alg«
al
rc
2 PB
We :
side:
rand
the «
of tk
runn
the «
and
In F
duce
with
ber «
set z
of oi
mor
Fig
ima,
Fig.