tablished, changes to one patch are propagated to all other 
affected patches in the roof. In keeping with the dual patch 
representation, two kinds of constraints exist. Firstly, para- 
metric constraints can be used to couple a specific param- 
eter of two patches. As example consider a symmetric 
roof consisting of two patches (Figure 4(a)). By setting 
the parametric constraint eX? E o? this symmetry of the 
roof is always preserved; if the inclination of one of the 
patches is changed, the inclination of the other is updated 
automatically. 
Secondly, coordinate constraints allow to model coinci- 
dence relations between patch corner points. As an ex- 
ample for both types of constraints, consider the L-shaped 
patch in Figure 4(b), constructed out of two quadrangular 
patches which have collinear upper borders. In order to 
compose the two patches to represent one L-shaped patch, 
two constraints are imposed. By making use of the para- 
metric representation, a unique slant angle can be achieved 
by requiring o = e. Additionally, the coordinate 
based representation allows to glue corner points together 
by setting pt = po. Constraints are also important 
during topological model refinement (Section 5.2). 
       
patch 1 
  
patch 2 
(a) (b) 
Figure 4: (a,b): Illustration of the two different types of 
constraints. See description in text. 
2.3 Implementation 
The realization of geometric constraints requires a one-to- 
many communication protocol between the involved pat- 
ches. This has been implemented by means of the observer 
pattern (Gamma et al., 1995). Each change in the geome- 
try of a patch evokes the broadcast of a message contain- 
ing the changed coordinates and parameters. A constraint 
is implemented as an observer which scans the message 
stream for a specific pair of parameters or coordinates. If 
one component of the pair changed, the other is updated 
by the observer. Since limited numeric precision makes 
it impossible for a constraint to be fulfilled exactly (in a 
mathematical sense), equality is defined within some toler- 
ance. 
3 INPUT DATA AND SEMANTIC LABELLING 
This section describes the preprocessing steps used to gen- 
erate the input data for roof reconstruction, as well as the 
concept of semantic labelling of 3D line segments. 
3.1 3D Line Segment Reconstruction 
The raw input data for our application consist of high reso- 
lution aerial colour images of densely built up urban areas. 
(Figure 5(a,b) shows an example stereo pair.) The images 
are taken with mutual overlap in order to allow a 3D re- 
construction of the scene. The precise camera calibration 
is known. After edge detection and straight line fitting, cor- 
responding 2D line segments are sought in the stereo pairs. 
Besides the geometric constraints given by epipolar geom- 
etry and the specific image acquisition setup, chromatic 
constraints are also exploited to disambiguate the match- 
ing and thus reduce the number of wrong matches (Scholze 
et al., 2000). The chromatic constraints are obtained by 
comparing the image neighbourhood of the line segments 
under consideration in order to reject chromatically incom- 
patible matches. Some of the remaining matches are purged 
by considering the trifocal constraint, and the chromatic 
constraints already mentioned between multiple views. If a 
match passes all statistical and geometrical tests, its 3D po- 
sition is recalculated using bundle adjustment to enhance 
the geometric precision of the reconstructed 3D line seg- 
ment. The resulting 3D line segments (see Figure 5(c)) 
form the input for the roof reconstruction process described 
in this paper. 
  
(a) (b) 
eem 
1 NT \ \ 3 
X AN + # T€ — 
Nu ae > % 
A wc. ey. À 
Nu OM id NN 
er S a # 
# Gy = 
< X > 
\ . 
\ = 
s 
; « S MH 
N DM 
Ye Tu 
AN 
x N ; p : 
wA # 
\ SUA 7 
Y ; (c) 
Figure 5: (a,b): Example aerial image stereo pair used for 
3D line segment reconstruction. (c): Resulting 3D line seg- 
ments used as input for roof reconstruction. 
3.2 Semantic Labels by Geometric Measurements 
The semantic interpretation of 3D line segments is a key 
feature of the presented methodology. Five different se- 
mantic labels for patch segments are distinguished. The 
—206— 
five | 
The 
they 
segn 
no n 
6 gi 
(e. £ 
i em 
tic 1: 
men 
segn 
adja 
The 
forn 
and 
Figi 
bels 
ary 
a pa 
cavi 
33 
use 
The 
folc 
(IG 
ang 
matr 
diti: 
ric : 
reci