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