In: Stilla U, Rottensteiner F, Paparoditis N (Eds) CMRT09. IAPRS, Vol. XXXVIII, Part 3/W4 — Paris, France, 3-4 September, 2009 
Figure 3: Erosion of the input footprint (green) by a flat rhombus 
(blue) of height d orthogonal to a main direction (red). 
which means that the splitted footprints have a width of at least d 
on at least half of their length. Hence, the parameter d is used to 
indicate minimum expected size of a footprint. For instance the 
hypothesis in Figure 2(b) (top) is discarded because the top right 
triangle satisfies this criterion (it has |7lTP e | = 0). This geomet 
ric criterion proved to be the most robust in our experiments, and 
it was implemented using the CGAL Minkowsky sums. Note that 
we replaced the segment by a flat rhombus to avoid degeneracies. 
2.2 Cut score 
For each cut hypostesis, we can compute a cutting score as the 
energy E(X) restricted to the cut. To enhance this estimation we 
take into account the following facts: 
• An existing edge corresponds to an altimetric discontinuity. 
Hence the gradient in its vicinity should not be taken into 
account for the score of a new cut. Thus the meaningful 
zone is defined by the erosion of the footprint by a centered 
segment. Ideally, the length of this segment should equal the 
size of the kernel used to compute the gradient. In practice, 
it should be even greater as the edges of the footprint are not 
exactly located on discontinuities. We chose the same length 
d as before, such that we only need to compute one erosion 
per footprint and per direction. We chose to compute the 
erosion with CGAL’s exact arithmetics as we encountered 
failure cases using inexact computations. This is quite time 
consuming, such that the choice of taking the same parame 
ter is really saving us time. 
• Vegetation hides the geometry of the building so the DEM 
will be considered not pertinent within the vegetation mask. 
• The DEM is more inaccurate in shadowed areas. 
These three facts are integrated in the computation of E(l) by 
weighting the gradients by a confidence term that is 0 outside the 
eroded footprint and in vegetation areas, and elsewhere propor 
tional to luminosity. 
2.3 Recursion 
For the input footprint V, we can build the cutting hypotheses 
(Section 2.1) and their scores (Section 2.2). We select the cutting 
hypothesis with the lowest score and apply it to the footprint V, 
which splits it into two sub-footprints V\ and V?. We apply this 
process again to Vi and V2, and so on recursively. 
To ensure that our cuts minimize E, we stop the recursion when 
the lowest score becomes positive. In that case the footprint is 
final and will not be splitted. Our shape criterion (2), guarantees 
that the width of the resulting sub-footprints is greater than d in 
each direction. 
2.4 Results 
As figure 4 shows, the segmentation resulting from the recursive 
split runs through most of the altimetric discontinuities. How 
ever, the segmentation presents many undesired cuts as our cuts 
are straight so they run through the whole footprint when they 
may correspond to much more local altimetric discontinuities. 
To achieve a better segmentation, and further minimize our en 
ergy, we need to remove these superfluous cuts by merging sub 
footprints whenever this improves the energy E(B). 
3 MERGE 
3.1 Geometric polygon merging 
Merging the sub-footprints resulting from the splitting process 
can be tricky as numerical precision forces us to use thresholds 
to determine whether two edges from different polygons touch 
or not. To make the merge process independent from numerical 
precision and thresholds, we label all edges produced during the 
splitting process by (a pointer to) the cut line that produced it. 
This way, the merging algorithm is both robust and simple: 
1. For each pair of edges e k € Pi and ej € Pj belonging to 
the same cut line: 
• Compute the intersection edge ek,i = e\ Pi e\ 
• If e k ,i # 0. add e k ,i to h,j. 
2. Build the connected components of Uj. If there are more 
than one, this means that the merged footprint has holes. We 
need to prevent these holes to appear as they are harder to 
handle in the reconstruction process. To do so, we keep only 
one connected component in /¿j (the longest or the one with 
lowest score). 
3. Build the merged footprint Pij: 
• For each interface edge e k ,i E U.j tag e k and e\ as 
interface edges. 
• Build the connected components Ci and Cj of edges 
of Pi and Pj not tagged as interface. 
• Connect the endpoints of Ci and Cj (this is unam 
biguous if Pi and Pj where properly oriented). 
3.2 Merging algorithm 
The merging process goes as follows: 
1. Compute all possible merges, their interfaces and scores 
Sij = E(Ii,j). 
2. Build a priority queue of all merges, where the priority is 
the score Sij. Remember that a high score means it is 
likely that the interface is not an altimetric discontinuity so 
it should be removed from the final cut. 
3. While the merge with highest priority is positive: 
• Apply the merge with highest priority Sij between 
footprints Pi and Pj by replacing Pi and Pj by their 
union Pij = Pi U Pj. 
• Remove all merges involving Pi and Pj from the pri 
ority queue. 
• Compute all possible merges involving Pij, their in 
terfaces, their scores, and add them in the priority 
queue.