a threshold T,: 
(g? = 42 X (gt = gy ^ I (3) 
From these two line segments a line in 3D-space can 
exactly be determined. The line segments of (r1) and 
(I1) are projected onto the line in space and furnish 
line segments in space. À match is only assumed to 
be true if the overlap in space is higher than a certain 
threshold I',. Currently we claim a relative overlap in 
space of 50% minimum. 
In the next step possible matches in the consequent 
image pairs are searched. If a line in the left image 
(12) has a similar length and orientation as in the left 
image (I1), i.e. the absolute differences are less than 
some thresholds T; and Te, this line is a possible can- 
didate. Now we check whether the grey value diffe- 
rence is the smallest one for all lines in image (12). 
If this condition is fulfilled as well we make a geome- 
trical test: the projection of the reconstructed line in 
3D-space into the image (/2) is compared with the 
candidate line. For the orientation of image (/2) we 
use the estimates from the wheel sensors. If their dif- 
ferences again lie beneeth thresholds l'», and I, we 
finally accept the candidate line as a possible match. 
The same procedure is performed with all lines of 
the right image (r2). An initial correspondence is only 
kept if a corresponding line in (/2) or (r2) is found. 
This quite complicate procedure gives a number 
of possible matches that are most probable linked 
to really corresponding line segments. Typically the 
matches are not unique: some lines are matched more 
than once. 
5 Camera Orientation 
An orientation algorithm which estimates the orienta- 
tion of the camera pair in ta is presented. The abso- 
lute orientation is determined in the local coordinate 
system. All measurements are performed in a local 
coordinate system defined by the first image pair: the 
camera (/1) lies in the co-ordinate origin. In a la- 
ter processing the measurement results obtained in 
this local coordinate system can be transformed into 
a global co-ordinate system using GPS observations. 
As already mentioned, the relative orientation of 
the camera pair remains constant. The orientation of 
both cameras is therefore completely described by the 
known orientation of one (in our case the left) camera. 
The orientation algorithm uses straight lines to de- 
termine the exterior orientation. It is based on the 
method presented in [7] and only uses the line para- 
meters of the observed lines. At least three lines in 
at least three images are needed to calculate the exte- 
rior orientation. They must not be parallel in space. 
The unknown parameters of the lines in space and 
the unknown exterior orientation are determined in a 
least square approach. The parameters of the image 
28 
lines are compared with those calculated from the pro- 
jection of the lines in space into the image with the 
assumed orientation. The weighted square differences 
of the line parameters in the images 1s minimized. 
The orientation starts with the lines in the ima- 
ges with the highest radiometric similarity. The 
Schwermann-algorithm [7] is performed once. If there 
are false matches, the algorithm will not converge to 
the correct values. There are two possibilities to de- 
tect this case. A low accuracy of the calculated lines 
in space indicates false matchings. These are elimi- 
nated and the process is repeated until the algorithm 
converges to reasonable values. If orientation values 
are near to the approximation determined from the 
wheel sensors, this orientation is accepted. 
6 Finding Optimal Line 
Correspondences 
6.1 Optimisation Algorithm 
It is assumed that N possible assignments are given. 
We denote the assignments with C;, i € (1... NN). 
Every assignment contains a list of matched elements 
xU) j is the image number (j = 1,..., M) and M is 
the number of available images. 
C= (iV, x, 438 2M, 
'Null matches! where no object in one image is mat- 
ched are allowed as well. The task is now to find a 
set of optimal assignments. We are looking for a set 
Q being a subset of (1,2,..., N), the set of all pos- 
sible assignments. The number of assignments in 2 
is denoted with |Q]. © has to fulfill a compatibility 
restriction. The compatibility or uniqueness restric- 
tion requires that every object must only be matched 
once: 
zt) + 20) Vie (1, MM), amd i,k EQ iL k 
Further on we claim that the selected assignment 
set is ’better’ than every other assignment set. For 
this purpose we construct a cost function K (2) that 
describes the quality of an assignment set. The cost 
function K(f) has to be minimized. A possible cost 
function is presented in the next paragraph. We as- 
sume here that the cost function depends on two fac- 
tors: attribute costs K4 and relational costs Kg. 
Then we get the following cost function: 
K@) =) KaC)+)_ M5 Ka(CoC;. (4) 
ien 1EN 7EN,j>1 
For ervery || there exists an optimal solution £2. To 
find the optimal soultion we use a branch-and-bound 
algorithm. 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B2. Vienna 1996 
for ?. 
fori. 
Figur 
mina 
Th 
versic 
timal 
numl 
all pc 
from 
empt 
ded. 
yet ir 
dure 
the n 
highe 
signn 
into 1 
WI 
the o 
1S orc 
searc| 
with 
Th 
and c 
ment 
from 
parar 
red. | 
best 
are a 
The: 
shoul 
all ai