Ke
1
g
H
1S
> >
ISPRS Commission III, Vol.34, Part 3A ,,Photogrammetric Computer Vision“, Graz, 2002
1. Initialization of the surface;
2. For each point
e compute cost function values for all possible val-
ues the surface can have
e attribute to the point the value which minimizes
the cost function
3. Stop calculations if there are no changes at step 2;
otherwise - come back to step 2.
ICM algorithm is a relatively fast optimization technique
which unfortunately does not converge towards the global
optimum unless initial point is close from it. Another very
known technique is simulated annealing which gives a global
optimum but is considerably more expensive in calculation
time (Picard et al., 1995).
4 COMPARISON OF RESULTS
41 Methodology
Obviously, the quality of the results is not to be determined
only visually. Correlation values with a ground truth can
be used as quality measures in this case. The Digital Eleva-
tion Model (DEM), obtained from high resolution optical
images, is taken as a reference here. A correlation coef-
ficient is calculated between two vectors: a vector X of
the DEM elevation values and a vector Y of the surface
elevation values obtained with the laser scanner data:
M Sm “aly
N-1
where - 3
TS and mm o.
2 dX) 9 sd(Y)
where X, Y - mean values of the vectors X and Y re-
spectively, std(.X), std(Y ) - their standard deviations, N
- a number of elements in a vector, r - the correlation co-
efficient. A perfect correspondence between interpolated
measurements and the DEM should lead us to a coefficient
r equal to 1.
The resolution of the DEM is 10cm, and the resolution of
a surface issued from laser is 1.80m. In order to com-
pare our results to the reference, we perform the follow-
ing steps. For each point of the resultant surface we find
the corresponding point in the reference DEM. Then the
value for comparison is taken as the median value of all the
points inside the 5x5 window the reference DEM. There
are some points where the reference DEM does not pro-
vide any information (Figure 8) (absence of textures on
very uniform surfaces or hidden parts during the construc-
tion of the DEM). In the first case, the median value makes
it possible to correct this absence, in the second (too large
zones) the point is ignored in the correlation calculation.
We also noticed that the area of study contained 2 different
zones: the largest part of the area contains mostly build-
ings, but the part of the area located at the top of the scene,
has vegetation with much more irregular geometry. Since
this vegetation area may strongly influence the compari-
son, we evaluated our results with and without this zone.
Figure 8: The Digital Elevation Model used as a reference.
The black values correspond to pixels where altitude val-
ues are not determined
4.2 Experimentation
To start, we choose both potential functions to be the same:
1) = . We initialized the optimization algorithm with dif-
ferent surfaces: white noise, results of triangle-based linear
interpolation, results of nearest neighbour interpolation, re-
sults of kriging.
The density of primary laser data is about 1 point per 3.24
m?. We selected the grid size to have the same density of
points in the DSM: it corresponds to a sampling step of
1.8m.
The chosen method of optimization is the ICM for its more
reduced calculating time. A significant parameter in this
algorithm is the choice of the step in altitude (the height
discretization). A too small step significantly increases the
calculations since it is necessary to calculate the potential
function for all these altitudes. A too coarse step leads to
a too schematic description of the buildings but can also
produce false minima. We chose a step of 50 cm, quite
compatible with the required space resolution. For these
initial surfaces, we obtained the results of correlation of
Table 1.
At the initialisation, we can notice that kriging gives better
results than the linear interpolation, the nearest neighbor
interpolation is worse. We also can see that the zone of
vegetation has tendency to degrade the correlation.
We take linear interpolation results as an initial surface, be-
cause they give the better output for o, — 1 (see Table 1).
The results are presented on Figures 9 and 10.The horizon-
tal line gives the correlation between the DEM and the best
initialization surface (kriging for both figures) in order to
see if the energy minimization approach outperforms the
classical ones or not. A curve located below this line indi-
cates that optimization degrades the initial solution.
A- 421