In: Stilia U, Rottensteiner F, Paparoditis N (Eds) CMRT09. IAPRS, Vol. XXXVIII, Part 3/W4 — Paris, France, 3-4 September, 2009
3.3 Results
The merging process ensures that the result is a valid segmenta
tion of the input footprint into a set of sub-footprints. As seen
in Figure 5, the algorithm is general enough to allow for a broad
range of possible sub-footprints, while being constrained enough
(in particular by the allowed directions and minimum size d) to
avoid overly complex shapes. The advantage is that such simple
shapes are proper for reconstruction. The inconvenient is that if
discontinuities do not follow the detected directions, they will not
be detected and lead to inconsistencies. Finally, note that as we
prevent holes from appearing, inner courts stay connected to the
outer boundary (there are two examples of that behavior in Figure
5(c))
4 DISCUSSION
Our method allows for a much more accurate 3D reconstruction
on footprints with inner altimétrie discontinuities as shown in
Figures 6 and 7. However, it sometimes misses some global cuts
that are obvious to the eye but do not correspond to altimétrie dis
continuities. For instance Figure 6 show that a single (and small)
handmade cut relying more on a global perception of the foot
print shape than on an altimétrie discontinuity allows for a great
improvement of the result.
This method is proposed as a tool to support the reconstruction of
wide urban areas. The splitting and merging results shown here
are all obtained based on the same parameters. The tuning param
eters are mainly the erosion width <7 that controls the minimum
footprint size and gradient threshold Tv that serves to specify the
limit between what is a discontinuity and what is not. They are
intuitive and simple to tune. In practice, we used the same stan
dard parameters (d = 1.5m, Tv — 3.5) to process an entire 1km
by 1km working area.
Step
(a)
(b)
(c)
Load inputs
0.27
0.4
0.27
Precompute
0.24
0.44
0.12
Erosions
0.2
0.19
0.36
Scores
0.15
0.2
0.1
Splits
0.23
0.17
0.15
Merge
0.01
0.01
0.04
Total
1.1
1.41
1.04
Table 1: Timings (in seconds on a 2.8GHz Pentium 4 processor)
of the different steps of the algorithm. The three columns corre
spond to the examples shown on figures 4 and 5.
In terms of computation time, the algorithm is extremely fast (see
table 1). This makes it possible to process very wide working
zones rapidly, or to tune the parameters interactively.
The algorithm is heavily dependant on the quality of the input
DEM, and only very weakly on the orthophotography and veg
etation mask (the latter only serves when the footprint contains
vegetation that has an important impact on the DEM, which is
quite rare). The most important problems that we encountered
are: •
• The DEM has a poor quality on shadows as it requires a
good contrast. As roughly half of the altimetric discontinu
ities generate a shadow at their bottom, half of the altimetric
discontinuities are not accurately represented in the DEM.
We simply added a confidence parameter to handle this is
sue, but we believe some more adequate solutions can be
found.
• If the footprint contains an important altimetric discontinu
ity that is not aligned with one of the clustered direction,
it will perturb the splitting as it will add an important fac
tor to the energy of all cuts not exactly orthogonal to it. To
limit this effect we penalized wrong gradient directions by
weighting the gradient by a factor max (0, cos(2(n, Vz))J
that smoothly decreases from 1 (perfect direction) to 0 for
angles greater that 7t/4.
• Superstructures cause altimetric discontinuities that are of
ten close to or higher than discontinuities between different
buildings. Thus they may generate cuts even with a fine
tuning of Tv- A possible remedy would be to implement a
superstructure detection such as (Bredif et al., 2007) prior to
cutting.
The energy that we use matches closely the Mumford and Shah
segmentation formulation (Mumford and Shah, 1989) except that
it has no data attachment term. This drawback is inherent to the
problem that we pose, and its consequence will be that we lack
of a global quality measure. This will sometimes lead to a lack of
global coherence, such as missing a small cut that would enhance
greatly the reconstruction (see Figure 6). A workaround would
be to interact with the reconstruction method, and for instance
only split footprints on which the reconstruction is bad (far from
the DEM). As this estimation needs to be done many times, this
would require the reconstruction to be very fast, which is not the
case for the one that we were working with (at least for complex
footprints).
The fact that this energy is not necessarily positive makes it im
possible to minimize with graph cuts based segmentation where
the non-negativity of weights is a fundamental requirement (Kol
mogorov and Zabih, 2004). However, this energy is very natural
for segmenting with an unknown a priori number of regions, as
minimizing this energy will naturally lead to an optimal number
of region, without the need to specify a source/sink pair. For in
stance, not cutting is a solution like any other, and it has its own
energy that can be optimal in the case that no segmentation is
required (which is the case on many footprints that are adequate
for reconstruction without enhancement). In contrast, graph cut
energy is always lower for not cutting than for cutting, and the re
sult is in fact the optimum over bipartition. The drawback is that
we cannot use the very efficient graph cut algorithm and need a
heuristic approach with no guarantee on optimality.
5 CONCLUSIONS AND FUTURE WORK
We have presented an algorithm to split cadastral maps into smaller
regions proper for subsequent 3D reconstruction. The algorithm
has only be tested for one reconstruction method but the authors
believe it might be a useful preprocessing step to any 3D recon
struction method based on the cadastral map or any other vec
torial footprint of the building to reconstruct. The algorithm is
simple and fast, as it has been designed with the purpose of help
ing reconstruction of large urban areas.
In the future, we plan on running this algorithm in a production
framework to have a better feedback on its large scale usability.
We will also look into correcting the DEM in shadowed area, or
maybe detection of altimetric discontinuities directly based on
correlation in the aerial images. Finally, we will look into less
heuristic means of minimizing our energy, especially in the merg
ing phase.
143
