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.