nstruc- 
images 
n that 
«ample 
camera 
d with 
ending 
nilarity 
re grey 
vhether 
in one 
ng fea- 
e same 
stances 
assign- 
case of 
or even 
s paper 
1fficient 
s infor- 
ric comn- 
| of the 
the co- 
res: two 
ar. 
h 4 pa- 
h 2 pa- 
images 
| redun- 
line lies 
in the epipolar plane is excluded). A third orienta- 
ted image is needed to impose a geometric constraint. 
'The only escape from this situation is to claim that 
the line segments in space have to overlap [6]. 
'The assignment problem is a multi-dimensional de- 
cision problem. À multidimensional optimisation can, 
in general, not be achieved. That is why we trans- 
form the problem into a onedimensional one. For this 
purpose, we introduce a cost function that has to be 
minimized. 
'The assignment problem is a problem of exponen- 
tional complexity. It would be too time-consuming to 
check the cost function for all possible sets of matches. 
Therefore, we reduce the number of possible matches 
considerably by heuristic means. The optimisation 
procedure is performed afterwords. 
2 Camera Calibration 
Before the surveying drive is carried out, the camera 
pair is calibrated in a three dimensional test field. The 
test field consists of 92 circular targets that are captu- 
red. The positions of the targets in the images are au- 
tomatically determined using least squares matching. 
Then the interior orientation and the exterior orienta- 
tion in a local co-ordinate system can be derived. We 
use the well known photogrammetic collinearity equa- 
tions, where the exterior orientation is described with 
6 parameters: the position of the centre of projection 
and 3 spatial angles. The interior orientation is mo- 
deled using the principal distance c, the position of 
the principal point (zo, yo), the lens distortion which 
is modeled with a circular distortion A], As, and a 
linear-affine distortion B4: 
Ay(r? — r2)r 4 As(r* — ré)r, with 
puts (z'— 2g)? + (vy =u). (1) 
de "= 2H 
dr(s,u) = 
Tests have shown that this model for the interior ori- 
entation is appropriate for the used camera-lens sy- 
stem. 
3 Feature extraction 
The feature extraction, the first step of the image eva- 
luation, is performed using standard operators known 
from image processing. Interest points are extrac- 
ted using the FORSTNER interest operator [4]. These 
points show a high significance and can be matched 
with high accuracy. 
Straight lines are found in two steps: first grey scale 
edges are found by using a gradient operator [3] and 
then straight lines which are longer than a threshold 
length are extracted from the edge image. 
Due to image noise and other influences, the end 
points of the line segments are very unstable features. 
27 
fr p eva AN Scene 
  
  
Figure 1: A scene is recorded in two stereo frames. 
The displacement of the frames is between 3 and 10m. 
Therefore we only deal with lines, which can be de- 
scribed by 
y=mz +b or = My FW (2) 
The first form is used if the angle 0 between the line 
and the x-axis is between —45? and 45^, otherwise the 
second form is used. 
For every extracted feature some attributes are cal- 
culated. The attributes of points are the position in 
the image, a small square grey value matrix with the 
point in the centre. The attributes of lines are again 
the position, the line length and orientation, and the 
mean grey values g1 and g» on both sides of the line. 
Relations are calculated between pairs of features. 
Two types of line relations are considered. Every line 
pair has an enclosed angle in the domain 0°...180°. 
Further on for each line pair the perpendicular dis- 
tance of the second's line midpoint from the first line 
is calculated. 
Points are related if their distance is below a thres- 
hold distance. In that case their relative position is 
determined. All features and relations are saved in a 
database. 
4 Finding Initial Line Matches 
In order to restrict the total number of possible line 
matches, we determine initial matches by heuristic 
means. For this purpose geometric properties and the 
extracted features are used. The procedure 1s descri- 
bed for the case of 4 images, it can easily be generali- 
zed for more than 4 images. The imagining situation 
is shown in figure 1. 
First all possible matches of lines in both images 
(11) and (r1) of timet; are regarded. We only admit a 
match if the squared difference of grey values is below 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B2. Vienna 1996