CMRT09: Object Extraction for 3D City Models, Road Databases and Traffic Monitoring - Concepts, Algorithms, and Evaluation 
• A Digital Elevation Model (DEM) over the whole area (Fig 
ure 1(b)). It was obtained by dense correlation following 
(Roy and Cox, 1998) and the implementation described in 
(Pierrot-Deseilligny and Paparoditis, 2006). 
• The gradient of the DEM (Figures 1 (c) and 1 (d)) computed 
using a standard Canny-Deriche filter (Deriche, 1987). 
• An orthophotography of the area (Figure 1(a)). 
• A vegetation mask (Figure 1 (b), red) obtained by the method 
exposed in (Iovan et al., 2007). 
The initial data and extracted data form the input to our algorithm. 
1.3 Previous works 
The idea of using a 2D building footprint to enhance 3D building 
reconstruction first appeared in (Pasko and Gruber, 1996), and 
was developed in (Roux and Maitre, 1997), (Brenner, 2000) and 
(Jibrini et al., 2000). This idea is also at the core of the recon 
struction method (Durupt and Taillandier, 2006) for which we 
designed our building footprint enhancement algorithm, and to 
the more general framework (Taillandier, 2005) from which it 
derives. In the context of laser data, it is also central to the works 
of Vosselman et. al. (Vosselman and Dijkman, 2001) (Vosselman 
and Suveg, 2001) (Suveg and Vosselman, 2001). 
To the best of our knowledge, segmentation of building footprints 
has never been decoupled from the reconstruction itself as done 
in this paper, but used to find directly planar regions. 
1.4 Proposed approach 
In this paper we call V the polygonal footprint to segment, Vi 
the polygonal sub-footprint resulting from the segmentation and 
If = Vi D Vj the interface between two sub-footprints (it is an 
edge or set of edges in some cases). The result of our algorithm is 
a segmentation of V that is given indifferently by the set of sub 
footprints Vi or by the interface X = Ubetween the V, (it 
is a set of edges). 
The approach that we propose consists in defining an energy that 
is negative (resp. positive) on edges that are likely (resp. unlikely) 
to be altimetric discontinuities, and to find the segmentation that 
minimizes the sum of this energy over the edges of X. We start 
by choosing a gradient threshold Tv such that we consider that a 
point where the gradient value is above (resp. below) Ty is likely 
(resp. unlikely) to be on an altimetric discontinuity. The energy 
on an edge e can then be defined as: 
E{e)= / T v -\Vz(P).lt(e)\dP (1) 
Jp&e 
where 2 is the height at point P given by the DEM and r? (e) is 
a unit vector normal to e. As required, E(e) is negative when the 
mean absolute gradient across e is greater than Ty. 
To simplify this problem, and gain in robustness and quality, we 
will restrict the directions of the interface edges to follow direc 
tions present in the original footprint, which is not a strong condi 
tional assumption. This proved to be true on most examples that 
we have tested. In order to solve this problem, we propose a split 
and merge approach based on principal directions detected on the 
initial footprint V: 
1. Cluster the directions of the footprint’s edges in a direction 
space taking their lengths into account. 
2. Recursively split the footprint along lines of minimal energy. 
(a) Two hypotheses for a (b) Two hypotheses for a dou- 
snapped cut ble cut 
Figure 2: Cutting hypotheses. The eroded footprint is darkened. 
3. Merge the resulting sub-footprints in order to minimize E{X) 
The first step is a simple clustering in the space of line angles 
(modulus 7r), and does not require special care. Simply notice 
that we should keep the number of direction clusters as small as 
possible, for instance by eliminating the clusters which edges’ 
length sum is smaller than a given threshold, or a ratio of the 
“largest” cluster. 
In our algorithm, we will often need to compute energies of the 
form given by (1) thus to access the gradient across edges that 
can only be in a limited number of directions. Thus for efficiency 
reasons, we will precompute the gradient for each direction on a 
grid aligned with the direction and with the same resolution than 
the DEM. These grids will serve a double puipose as they will 
also be used to discretize our cutting lines. 
2 RECURSIVE SPLIT 
2.1 Cutting hypotheses 
For each direction, we will discretize the set of possible cut lines 
Ci as the lines passing through the (center of) rows of pixels in 
our grids for each direction. This way the integral of the gradient 
over an edge in this line’s direction will simply be computed as a 
sum over pixels of the same row in the grid. 
As our input footprint might not be convex, a cut might generate 
more than 2 sub-footprints. In this case, the same cut line Ci 
generates several cutting hypotheses, one for each edge of PilCi 
(see Figure 2(b)). Similarly, we snap our cuts by prolongating the 
initial footprint’s edges, and generating a new cut hypothesis for 
each part of the cut (see Figure 2(a)). This way, each cutting 
hypothesis consists of the two footprints generated by the split, 
and their interface I which is a single edge. 
This process however can introduce extremely poorly shaped foot 
prints and small footprints that are not desired in the final solu 
tion. To prevent the occurrence of such bad geometries, we build 
an erosion V e of the footprint V by a centered segment of length 
d orthogonal to the current direction (see Figure 3). This erosion 
is then used to discard the cutting hypotheses for which: 
|JnTe|<|/|/2 (2) 
140