atics, 
Stephan Heuel 
TOPOLOGICAL AND GEOMETRICAL REASONING IN 3D GROUPING FOR 
RECONSTRUCTING POLYHEDRAL SURFACES 
Stephan Heuel, Wolfgang Förstner* and Felicitas Lang* 
* Institut für Photogrammetrie, Universität Bonn 
: Nussallee 15, D-53115 Bonn, 
e-mail: Stephan.Heuel|Wolfgang.Foerstner@ipb.uni-bonn.de 
* Institut für Photogrammetrie und Ingenieurvermessungen, 
Universität Hannover 
Nienburger Strasse 1, D - 30167 Hannover 
email: felicitas.lang 9 ipi.uni-hannover.de 
KEY WORDS: Building Extraction, 3D Grouping, Reasoning, Topology, Uncertain Geometry 
ABSTRACT 
We are developing a system for reconstructing polyhedral surfaces from multiple images. This process can take advantage 
of the topological relations of the observed image features triggering and therefore speeding up the grouping of features 
to polyhedral surfaces. Exploiting the statistical properties of features when grouping them leads to consistent decisions 
being invariant to numbering and choice of coordinate system and allows statistical testing. This simplifies the choice of 
thresholds to the definition of a scene independent significance level. We decribe the topological and statistical models 
used within our system. Experiments with synthetic and real data prove the feasibility of the approach.! 
1 INTRODUCTION 
Reconstructing polyhedral surfaces from multiple images is a classical task in Computer Vision. In case of controlled 
environment solutions are quite far advanced. However, in outdoor environments, e. g. when tracking vehicles or when 
reconstructing buildings, systems have to cope with quite a number of difficulties, such as a non-optimal feature extraction 
producing cluttered image descriptions with qualitative and quantitative errors. The technique of grouping significant 
features to high-level structures is often used to overcome some of these problems. The rules for grouping features are 
either very general and do not apply to real imagery or are rather specific and depend on the specific task. Most of the 
work was done in grouping two dimensional features but there also exists some work in 3D, for an overview see (Sarkar 
and Boyer, 1993). 
Apart from early work (cf. (Clowes, 1971), (Brooks, 1987), (Herman and Kanade, 1986)), grouping straight lines or 
planes in 3D mostly appears in the context of building extraction from aerial images (cf. (Roux and McKeown, 1994), 
(Henricsson, 1996), (Frere et al., 1997) (Baillard et al., 1999)). These approaches, though embedded in a specific ap- 
plication appear to be the most general ones by restricting to polyhedral surfaces. The work of (Roux and McKeown, 
1994) contains the most explicit use of 2D and 3D connectivity between features. (Baillard et al., 1999) generate plane 
hypothesis by half-plane detection and group 3D lines within these half-planes using collinearity and coplanarity criteria. 
Furtheron they close the half-planes by plane intersections. 
All these systems primarily aim at finding at least one path from the basic features to object descriptions of generic nature 
and in this respect give valuable rules for grouping. However, due to the complexity of the objects and the need to use 
domain specific knowledge, no general grouping rules have been established. 
We are developing a system for reconstructing polyhedral surfaces in outdoor environments aiming at exploiting as much 
generic knowledge as available from the structure of polyhedra, the imaging and the feature extraction process. There are 
two types of knowledge: a) neighborhood relations between the atomic features, points, edges and faces, resulting from 
topology, and b) crisp form relations at the object, especially planarity, and during the imaging process, resulting from 
geometry. On one hand, our feature extraction procedure (Forstner, 1994) was motivated by the need to exploit all features 
and their mutual neighborhood relations. In (Rothwell et al., 1996) topology as basic information in object representation 
  
! This work has been founded by the European Community as part of the ESPRIT project “Image Processing for Automatic Cartographic Tools 
(IMPACT)", No. 20.243. ue 
*This work originates from the time the author belonged to the Institute for Photogrammetry at the University of Bonn 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 397