Fig. 6 - Paths in the disparity map using 
a dynamic programming technique. 
A road section is the portion of road between two 
consecutive crossroads. On the disparity map calcu- 
lated previously we consider a large band along each 
road section. If it is possible to find a regular path 
in this band between the two extremities of the road 
section, then the road section is validated as well as 
the two crossroads. 
The search for a regular path is performed by a dy- 
namic programming procedure[5), that finds the best 
path from one crossroad to the other one. The cost of 
an elementary displacement in the disparity map bet- 
ween two neighboring pixels is equal to the absolute 
value of the disparity difference. The cost of a path 
from one crossroad to the other one is then the sum 
of these elementary costs. The dynamic programming 
approach allows to find the best path with respect to 
that global cost with O(nm) operations where n is the 
length of the band and m its width. The best path is 
validated if it does not contain any disparity gradient. 
This validation step is applied twice: 
- in a first iteration, a constraint is applied in order 
to force the different paths to begin and to end at 
pixels with the same disparity as the two extremity 
crossroads; 
- in a second iteration, the previously non-validated 
crossroads and road sections are examinated again wi- 
thout this constraint on the extremities. This allows to 
correct wrong values of disparity at some crossroads. 
Figure 6 shows several paths found by this dyna- 
mic programming procedure, white lanes correspond 
to validated paths and black lanes to non-validated 
paths. One can notice that some paths not validated 
during the first iteration because of a wrong disparity 
value at the crossroads are validated during the se- 
cond iteration (lower left part of the figure). Wrong 
disparity values for these crossroads were mainly due 
700 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
Fig. 7 - First digital terrain model 
before the road section validation. 
to misplacement of the road network extracted from 
the map. 
3.3 Calculation of a dense image of disparity 
At this point of the process, disparity is known 
only for a few points: the validated crossroads and 
road sections. In order to obtain a dense map of dis- 
parity, a 2D Delaunay triangulation is performed on 
the validated crossroads. The disparity at each point is 
then interpolated considering that each triangle repre- 
sents a planar surface: the plane equation associated 
with each triangle is calculated with the 3 coordinates 
(u, v, disparity) of its corners. 
A more sophisticated approach would consider com- 
plex 3D surface models like Bernstein-Bézier patches 
in order to obtain G* continuous surfaces[6|. 
4 Test scene 
Results are presented on a scene in the suburb of 
Paris. This scene presents a large variety of construc- 
tion density and buildings of various sizes and shapes. 
À portion of the scanned map is presented on figure 1, 
while figure 2 shows a small but significant part of the 
stereo pair of aerial images. 
4.1 Results 
The road network extraction provides, after the ma- 
nual correction, 369 crossroads and 612 road sections. 
A polynomial transform of degree 2 between the map 
and the left aerial image has been calculated with a 
least mean square approximation on manually selected 
control points. On figure 3 the road network extracted 
from the scanned map has been superimposed on the 
left aerial image. 
Disparity at crossroads was calculated as described 
in section 3.1. The DTM calculated without the va- 
lidation process along the road sections is presented 
on figure 7. One can notice some obvious errors given 
  
200 300 
| 
number of points 
100 
1 
by w 
gene 
disp: 
and 
gure 
of tk 
supe 
fits 
prev 
4.2 
a gr 
The 
cula: 
data 
ordn 
calik 
ponc 
sible 
poin 
tion 
defin 
iwo 
poin 
The 
Figu 
As i 
peak 
signi 
This 
tend 
shou