In: Stilla U, Rottensteiner F, Paparoditis N (Eds) CMRT09. IAPRS, Vol. XXXVIII, Part 3A/V4 — Paris, France, 3-4 September, 2009 
BUILDING FOOTPRINT DATABASE IMPROVEMENT FOR 3D RECONSTRUCTION: A 
DIRECTION AWARE SPLIT AND MERGE APPROACH 
Bruno Vallet and Marc Pierrot-Deseilligny and Didier Boldo 
IGN - Laboratoire MATIS 2/4 avenue Pasteur - 94165 Saint-Mand Cedex, France 
bruno.vallet@ign.fr - http://recherche.ign.fr/labos/matis 
Commission III/3 
KEY WORDS: Photogrammetry, 3D reconstruction, building footprint, split and merge, segmentation 
ABSTRACT: 
In the context of 3D reconstruction of wide urban areas, the use of building footprints has shown to be of great help to achieve both 
robustness and precision. These footprints however often present inconsistencies with the data (more than one building in the footprint, 
inner courts, superstructures...) This paper presents a fast and efficient algorithm to enhance the building footprint database in order to 
make subsequent 3D reconstructions easier, more accurate and more robust. It is based on a segmentation energy that is minimized by 
a split and merge approach. The algorithm is demonstrated on a wide urban area of one square kilometer. 
(a) Orthophotography and footprint (b) Shaded DEM and vegetation 
mask 
Figure 1 : Input to our algorithm 
1 INTRODUCTION 
The production of 3D models of urban areas has received a lot 
of attention from the scientific community in the last decade be 
cause of the broad range of its applications and the increase in 
both quality and quantity of data. In this setup, it becomes more 
and more crucial to design flexible tools to help human operators 
achieving efficient and accurate reconstruction of wide urban ar 
eas. 
1.1 Problem statement 
The problem of urban reconstruction consists in finding a 3D 
model (in general a polygonal surface) that is as coherent as pos 
sible with the input data. In our case where the footprints of 
the buildings are given, we can use the efficient and robust ap 
proach proposed in (Durupt and Taillandier, 2006). However, 
this approach relies heavily on the quality of the building foot 
print database, and might fail if the building to be reconstructed 
contains altimetric discontinuities that are not present in its foot 
print. This often happens in practice, and especially when: 
• Two (or more) adjacent buildings with different roof heights 
share the same footprint. 
• The real footprint of a building is only a portion of the foot 
print in the database (gardens, inner courts,...) 
• The building has some superstructures which sizes and heights 
are not negligeable with respect to the expected precision of 
the reconstruction. This problem becomes increasingly dif 
ficult as reconstructions gain in precision, and has already 
been tackled in the context of photogrammetry (Bredif et 
al„ 2007) (Domaika and Bredif, 2008). 
More difficult cases are often a combination of the three cited 
above, and require a manual intervention to enable a further re 
construction. In general, this intervention consists in subdividing 
the footprint by cutting through all (or most of) the altimetric dis 
continuities. In a production framework, where large areas need 
to be extensively reconstructed, it appears that this building foot 
print database enhancement step is one of the most time consum 
ing. Hence, the problem that we tackle in this paper is that of 
automatizing this enhancement as a required preprocessing step 
to 3D reconstruction. More precisely, our problem is to segment a 
polygonal footprint into a set of non-overlapping polygonal sub 
footprints that cover it entirely, such that the interface between 
the sub-footprints corresponds to altimetric discontinuities. This 
is a problem of segmentation of vector data (building footprints 
database) guided by raster data (photos, DEM,...) 
1.2 Available data 
The data available in our study mainly consisted of: 
• A set of 10 centimeter resolution aerial images with a high 
recovery ratio around 60% (intraband + interband) in order 
to ensure that each ground point is seen in at least 4 images, 
covering an area of one square kilometer. The images are in 
RGBI (the infrared channel is used to obtain the vegetation 
mask). 
• A vectorized cadastral map giving building footprints for the 
same area. It consists in a set of polygonal footprints given 
by their ordered list of points in ground coordinates (Figure 
1 (a), green). 
From this initial data, existing algorithms can be run to extract: