International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
  
2.3 Cost function 
Bundle adjustment is based on the minimization of a cost function 
F, which depends on the parameters that have been defined. Let 
X € IR" be the vector of all parameters. N, is the number of 
unknowns : 7 per image, 3 per point, and 6 per line. The cost 
function is generally the sum of the squared differences between 
computed and observed values : 
= No x2 No 200s = UE 2 
HE) EZ ) 
i=1 i=1 2 
where 
e NN, is the number of observations, 
e 7;(X) is the i/^^ element of the normalized residual vector 
+ ; 2 ypbs oP (} 
Le RN I) ROT 
1 
e v9"? is the i^^ observation, 
1 
eo v{°™P(X) is the computed value of the 3" observation, 
obs 
EE 
e ci is the expected standard deviation of v 
Constraints have also to be taken into account. Let Ne be the total 
number of constraints : 1 per quaternion (see equation 1) and 2 
per line (see equations 2 and 3). Let c € Re be the vector of all 
constraints. Satisfying constraints is equivalent to eX) = {. 
The minimization problem consists of finding X: 
X = arg min (FX) subject to constraints (X) =0 (5) 
2.4 Observations 
Camera observations In some cases, camera position as well 
as its orientation can be directly measured. They can be taken into 
account in the cost function by adding one observation which can 
be a camera position or an orientation (e.g. GPS/INS measure- 
ment can be directly included in the process). c is then the ex- 
pected error on GPS/INS measures. These camera observations 
can also be used in order to provide an initial solution for our 
minimization process (Section 3.). 
Point observations For Ground Control Points (GCP), the 3.D 
position (x, y, z) is an observation. The cost function is directly 
the distance between the observed position and the measured one. 
o is the expected error on position measurement, depending on 
the measurement method (GPS, topography, ...). 
For each point, the image positions (c, /) either in pixels or in mil- 
limeters are also observations. The cost function is the distance 
between the projection of the corresponding 3D point and the 
measured image position. o is the expected error on image po- 
sition measurement, depending on the method used to determine 
the point position (monocular, stereo, automatic, etc.). 
Line observations In order to introduce linear features in the 
bundle adjustment process, we only need to introduce a distance 
between an observed and a computed value. Most algorithms 
represent image segments using their two extreme points I; and 
l» (see Figure 1). 
The cost function is the distance between the projected 3.D line 
and these extreme points, orthogonally to the projected 3.D line. 
Using this definition of distance, segment extremities in differ- 
ent images do not have to match, they just have to be as close 
as possible from the 2D re projection of the same 3D line. It 
is therefore possible to create tie lines between images with no 
overlap. c is the expected error on the position of segment ex- 
tremities, orthogonally to the 3.D line projection. Practically, this 
expected error is not easy to determine. 
3Dline 
Figure 1: Linear features distance 
3. MINIMIZATION 
This section deals with the problem of minimizing the cost 
function F, which is obviously a non-linear function. It is 
achieved through the Gauss-Newton algorithm. Should robust- 
ness problems arise, our algorithm may be easely transformed in 
a Levenberg-Marquard iterative algorithm. Constraints will be 
addressed in subsection 3.3. 
3.4 Gauss-Newton algorithm 
The Gauss-Newton algorithm is an iterative algorithm requiring 
an initial estimate .X(O, In this paper, X(9 is supposed to be 
available and will not be discussed (see Introduction). At each 
-— 
step k, vector X? is updated : XD — XO 4 3X. La 
H (X) be the Hessian matrix of function F(X) : 
aft 
Hi; (X) = A with i, j € [1, N,] (6) 
and G(X) be the gradient of F(X) : 
so 1 X 
te 
At each step, we seek X + dX minimizing cost function F. 
Hence : 
with à € [1, Na] (7) 
dF (X +4} 
nal) 
D cz 
which enables us to determine dX. The algorithm is : 
e at each step k, compute dX using: 
H(X®) 4 = 5 (3) (9) 
e oen = XO) ar 
e k=k--| 
e go to step | 
     
    
   
   
     
   
    
   
  
  
   
    
     
  
     
   
   
    
   
     
   
    
    
     
     
   
    
    
   
   
    
   
     
   
  
  
  
  
  
  
  
  
  
    
    
  
    
International A 
3.2 Jacobian 
In most applica 
pute, so a first o 
where J is the Je 
= 0 
(x) = = 
Using the same : 
This problem is € 
lem : 
The system can t 
Seeing that the m 
be solved using tI 
3.3 Constraint 
At the beginning 
into account. So, 
XO) _ 2k) 
reason to satisfy t 
The first obvious 
X +1) in order 1 
projection on the 
solution, but, the 
practice, the com 
introduce the con: 
al., 2000)). 
Equation 5 can b 
IR* be the veclc 
expansion of the c 
where C is the ma 
Cu = 
Solving equation 5 
F + CA, subject 
expressions are : 
i 
and 
Q= 
Combining these t 
of the algorithm :