3.4 Algorithm for a combined procedure of RANSAC 
and 1/0-weighted least squares adjustment 
The main steps of the algorithm tested in the simulation 
experiments are the following: 
- determine number of subsets 
for i=0 up to the number of subsets 
{ 
- Choose 2 different random points in 2 random images. 
- Compute the line direction for the actual subset. 
- Check the stability; if geometry not stable reject subset. 
- Compute the line center for the actual subset. 
- Set all observation weights to 1. 
- Compute the residuals d, for all points with respect to 
the actual solution and detect outliers. 
- Count the number of inliers. 
if (more than 4 inliers (= random points)) 
while (number of inliers changes) 
{ 
- Do a least squares adjustment with the weights 1 or 0. 
- Reset all observation weights to 1. 
- Compute residuals, detect outliers and count inliers. 
- Compute the reference variance of the actual fit. 
} end of while-loop 
} end of for-loop 
- Find the best subset as the solution with the maximum 
number of inliers and the smallest reference variance. 
4. SIMULATION EXPERIMENTS 
A straight line reconstruction was simulated with the help 
of a generated space line. 
4.1 The simulation data 
The space line is observed by 4 cameras and represented by 
96 image points equally distributed over the 4 images. The 
image format is 512 x 512 pixels. For the generation a line 
center point C (0,0,0) and a normalized line direction 
vector B (V Vs, Vs, Vs) is used. 
In this experiment the 24 points per image correspond to 
the points in the other images. In general, however, this 
correspondence is not required for the chosen line 
representation. 
  
   
  
  
  
Y 
  
  
  
  
  
  
  
Mie n ui m m e eis em em em 0 mm 2 
  
Fig. 5: Camera positions 
     
in the simulation experiments 
     
The camera constant is 950 pixel for each camera. The 
positions and orientation angles of the cameras are given. 
In addition to the basic data the simulation parameters are: 
1) noiselevel c = standard deviation of normal distribution, 
2) number of outliers = o, 
3) size of outliers, size = s*o 
4.2 Noise and outlier generation 
In all experiments Gaussian noise is used, distributed like 
N(mean, noiselevel) = N(0,1). The noisy point is generated 
by shifting the original point away from its position in 
perpendicular direction to the correct line. The 
perpendicular distance of the shift equals the value of the 
normal distribution. All points are contaminated with noise. 
After the contamination with noise the outlying points are 
randomly selected. Their number is as equally as possible 
distributed over the 4 images. 
Two variations of outlier generation are used. 
The first variation produces outliers which all possess the 
same perpendicular distance from the correct line. Their 
position is reached after a shift with random sign and 
absolute value of size s*o. In the following text this kind 
of outliers is called ’constant’ outliers. 
The second variation produces outliers, whose absolute 
value of the perpendicular shift is uniformly distributed in 
the interval [-s*o; +s*o]. That kind of outliers is called 
'variable' outliers. 
4.3 Experiments 
The experiments are carried out by reading the original 
data, then contaminating the data with normal distributed 
noise and outliers, marking the outlying points and 
performing the algorithm listed in 3.4. In the end some 
values for the table statistics are counted. 
For the experiments with outliers which possess a constant 
distance from the correct line, following values are 
calculated and listed in the table columns: 
[1] percentage of outliers (among 96 points) 
[2] constant distance of outliers from line [pixel] 
[3] number of subsets for RANSAC procedure 
[4] probability [%] for at least 1 good subset (see 2-3) 
[5] number of experiments carried out for the results in 
one line of the table 
[6] percentage of experiments which find the correct 
line, detect all outliers and reject not more than 3 
good points = success rate = convergence rate 
[7] percentage of experiments which don’t converge to 
the correct line = failure rate 
[8] percentage of successful experiments with solutions 
based on a random subset containing outliers 
[9] probability [%] for detection of a good point as 
outlier = false alarms = €, 
The probability of £, equals the probability to generate 
normal noise exceeding 36, which is