can be 
duct of 
(9) 
before 
, new 
once a 
is of 
normal 
of the 
to add, 
impose 
ased on 
E The 
85]. 
form of 
quation 
eads to 
(10) 
is the 
is the 
jations. 
system 
(11) 
(12) 
(13) 
ind by 
ap - d. (14) 
Practically, from Equation (10), we consider one row 
vector from the system Rx - d and an observation row 
vector from the system Ax 1, 
0.02, 2, + Zp 
0..02; ay ^ Bj.’ as) 
A single Givens Transformation rotates these two 
vectors and replaces them with 
b or! / 
o 0r riu I.e 
16 
9.00 a. val. (is) 
where 
rip=0cz, vse 
aly=-sr.+ca, (17) 
C^ +5?=1, 
The requirement that a, be annihilated to zero allows 
the computation of the rotation parameters: 
P zr Z 
EL FIG * 2: 
C+ 1; //rT+at=r /r; (18) 
Se 8: / qi ta; ar, t, 
from the diagonal elements of R and the corresponding 
elements of the coefficient vector. Zeros appearing 
in corresponding elements of both vectors are left 
unchanged. 
R and the right hand side d, after being augmented by 
a new observation vector, appear as in Figure 2. 
  
Ty Tız Z13 — Inn di 
Taz Ta3 — Ian Q 
Ty; — Ian d, 
Inn d, 
Q 
2, 2, 23, a2, 1 
  
  
  
Figure 2: R Matrix Augmented By New Coefficient 
Vector 
An additional element (Q) is added to the right hand 
side to maintain the root residual sum of squares 
Q -/v'v-sd'd. (19) 
as was shown by [Lawson and Hanson,1974]. Thus, the 
variance factor : 
2 
= 9%, (20) 
I 
can be updated with Givens Transformations together 
with R and d. 
Computations Without Square Roots 
By using conventional Givens Transformations, one 
needs approximately 2n? multiplications and n+l 
square roots to process each new observation vector 
[Gentleman, 1973]. This is unacceptable for real- 
time applications. An alternative implementation of 
Givens Transformations avoids the square roots and 
requires only three-fourths as many multiplications. 
This method involves finding a diagonal matrix D and 
a unit upper triangular matrix R such that 
(21) 
tole 
R-D? R. 
A row of the product D'R is rotated with a scaled row 
of A [Gentleman,1973], 
   
   
   
   
      
     
     
   
   
   
    
  
    
   
   
    
    
    
   
  
  
        
   
   
     
   
   
   
   
   
    
    
    
    
   
   
   
   
   
   
     
     
  
   
    
     
     
   
    
    
     
  
    
  
0.0yad .Vdr,. 22 
0.0/852,..48 a, (22) 
where d is the diagonal element of the matrix D and 
ô is the scale factor for the coefficient vector and 
is initially set to one. 
After one rotation, from Equations (17) and (18), the 
newly transformed rows are 
0.9 Jd... /d' £/,-— 
(23) 
0-00 . J/EValt-, 
where d' is the updated diagonal element, Ó' is the 
updated scale factor and 
d'd*«baj (24) 
8 =d8/ (d+8 al) =ds/d 
€ = d / (d+8 af) = d / d' 
5 = à a, / (d + a;) = 8 a, / d' 
ak = à, - à, T, 
£z -Tf,423,. 
Practically, D and R are initialized to zero and the 
scale factor d is initialized to one. After one 
transformation, the updated rows are expressed as a 
row of an updated D'R and an updated scaled row of 
A with a new scale factor. 
This method simplifies the weighted least squares 
problem, for which each observation equation is 
multiplied by the square root of its weight. Using 
Givens Transformations without square roots, this is 
accomplished by simply initializing the scale factor 
to the weight instead of one. 
Introducing the same observation into the a system 
several times with various positive and negative 
weights, has the same effect as introducing it only 
once with the sum of the weights. Therefore, 
observations can be deleted by simply reintroducing 
them with the negative of their previous weight 
[Gentleman, 1973]. 
IMPLEMENTATION FOR ON-LINE TRIANGULATION 
OF STEREO-PAIRS 
The method of Givens Transformations without square 
roots was implemented in an on-line triangulation 
program to form a strip of stereo-pairs captured by 
the stereo-vision system of the mapping van. This 
program allows for a variable size solution vector in 
order to add new unknowns to the system, continuous 
monitoring of the solutions ànd the cofactor matrix, 
the capability of a simultaneous solution at the 
operators convenience, and the imposition of 
constraints to fix certain parameters, such as the 
relative orientation of any stereo-pair. 
The Trianqulation Program 
The triangulation functions and interface programs 
were implemented on a workstation, and allow for 
interactive image display and point selection with a 
cursor cn the screen. Sequential strip triangulation 
begins when the operator displays the first stereo- 
pair on the computer screen. Three dimensional 
coordinates of the perspective centers of the left 
and right cameras are known from the GPS position of 
the van and the calibrated relative orientation of 
the camera pair.  Conjugate points are measured in 
both images manually or by using an image matching 
technique. After measuring a few points in the 
first stereo-pair we can compute the exterior 
orientation parameters with the base and the relative 
orientation constrained.