Mv 
N" NV 
3.1.2 Stability of the closed form solution 
Stability means that small changes in the data produce 
small changes in the results. In case the geometric situation 
is not stable, singularities in the analytical formulas and 
unreliable results may occur. 
The input to the closed form solution described above 
consists of 4 randomly chosen image points. In order to 
avoid those combinations of image points, which lead to an 
ill-conditioned geometry, a measure for the stability of the 
solution is developped. 
Weak points with respect to the numerical sensitivity are 
the three cross products used to compute the line direction 
vector B. A cross product is computed in a stable way if 
the angle between the two input vectors is close to 90°. In 
case the angle comes close to 0°, the result is a random 
outcome according to the noise in the input vector 
components. Image points very close to each other as well 
as line/camera formations with similar projection planes 
should be avoided. 
The stability of a cross product axb is measured by the 
sinus of the angle © between two vectors a and b: 
> ax] 
3-6 
"eT alibi d 
Random points for which the value of sin « doesn't exceed 
an upper bound are considered to have a good geometry. 
The thresholds can be derived from error propagation of the 
interior camera geometry and the noise level. 
In this study the thresholds were found by experiments. The 
value 0.05 for the cross products of the image rays and 0.2 
for the cross product of the normal vectors were sufficient 
to avoid bad cases. Because of the nearly symmetric 
geometry in the experiments the impact of the stability of 
N,xN, is very strong and so the threshold very low. 
3.2 Application of the RANSAC method 
The straight line model, described by (1-4), allows the 
calculation of the RANSAC algorithm parameters based on 
the individual geometry of that line representation. 
3.2.1 Thresholds for outlier detection and model 
accepfance 
An important item in the RANSAC procedure is the 
decision in algorithm step 2) if an observation fits or not 
into the model of a certain random subset. The decision is 
drawn with the help of a threshold for the residuals. 
As residual the coplanarity value f is taken. It can be seen 
as ’pseudo residual’ - compared to the residuals v of the 
original observations. It is computed by the scalar triple 
product, where the observation data is the original one and 
the line center and line direction come from the random 
model. The coplanarity value f, expressing the volume of 
the error tetrahedon, grows strongest along the normal of 
the projection plane. 
The coplanarity values are scaled by their pseudo weights 
Q, ; to make them comparable to each other. The pseudo 
residual d; for one point is 
   
   
   
   
   
  
    
   
  
  
    
   
    
   
  
   
   
  
   
   
    
  
  
   
   
   
   
   
   
   
   
   
    
     
   
  
  
  
   
   
    
   
   
   
   
   
   
   
   
   
   
   
     
4-5/9 (3-7) 
A point is called outlier when its pseudo residual d, is 
larger than a threshold t = 3 * noiselevel. The noiselevel is 
the expected noise of the image observations. Thus the 
comparison is done in image space. For the further 
processing the observation weights are set to O in order to 
mark an outlier and to 1 for an accepted point. The number 
of accepted points for one random subset is counted. 
The threshold for the model acceptance in algorithm step 4) 
has to decide which one of the models fits the data best. 
The primary best fit criterion is the number of inliers, the 
secondary is the a posteriori reference variance. 
à -IWÍ (3-8) 
Of course the search for the best model is limited to those 
models provided by the used random subsets. The chances 
for better results grow with the number of subsets. 
3.3 RANSAC in the presence of noise 
What happens to the RANSAC solution, when the data is 
as well noisy as contaminated with outliers? - Up to now 
the RANSAC distinguishes between good and bad 
observations. The procedure is designed to find a subset 
containing only good points, even if the noise in these good 
points might be so heavy that the solution becomes wrong. 
One method against that is to get rid of those random 
points which are very close to each other and easily 
produce an incorrect solution. 
But even points at different ends of a line segment may in 
some case produce a solution deviating from the correct 
line more than 3*noiselevel for the most image points. The 
consequence is the detection of more outliers than really 
exist and the rejection of the model. 
  
   
correct line 
o 
  
  
  
  
Fig. 4: RANSAC-solution for a line, based on a random 
subset with noisy observations 
The basic idea to cope with the noise in the observations of 
the random subset is to use a least squares adjustment, after 
an initial solution is found by the closed form solution. 
Because the observation weights are set to 1 and 0, only 
the reduced set of inlying points is used for the adjustment. 
The normal distributed noise in the points will affect the 
least squares solution come closer to the correct line than 
the RANSAC solution and find more inlying points. After 
some iterations this process is able to find the best possible 
solution of a certain subset. The iterations are stopped when 
no more inliers are found. If the same data is used, all 
random subsets will end up in exactly - with respect to the 
computing precision - the same least squares solution.