716 
The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B3b. Beijing 2008 
graph and the system creates an edge between them. In the 
example shown in Figure 5, C is T-junction, and it can connect 
to D, A and E. Meanwhile, A can connect to B, C and E but C 
is nearer than E towards A on the line segment AE so that A 
only connects to B and C. Consequently there will be two 
collated features ACGB and CEFD in the Figure 5. 
4.5 Rooftop hypothesis selection 
The graph is the place to store features and their groupings. 
Feature as comer is node in the graph and relations between 
comers are represented with an edge between the corresponding 
nodes. Closed cycles in the graph represent the rooftop 
candidates. The hypothesis selection can be seen as a simple 
graph search problem. The close cycles in the graph are 
rooftops that we need to detect. Figure 6 show a graph 
constructed from the example in Figure 5. Comer C and comer 
D are T-junctions so that there are two nodes in the graph for 
each comer. Node Cl, C2 for comer C and node Dl, D2 for 
comer D. There are two close cycles Cl and C2 as shown in 
Figure 6. 
5. EXPERIMENTAL RESULTS 
The experimental environment was set up based on Ascona 
aerial images of the Avenches area. Since this area’s 3D model 
is supplied as a ground truth data, we can evaluate the 
quantitative accuracy for the 3D rooftop model generated by the 
proposed method. Two aerial images as shown in Figure 7 are 
used as a set of stereo images for experiments. 
C1 C2 
G 
Figure 6. Feature graph 
Figure 7. Aerial images used as a set of stereo image 
The result of epipolar resampling process is shown in Figure 8. 
We generate suspected building regions from the map to reduce 
unnecessary line segments. To find the accurate disparity map, 
we employed the multi-resolution scheme with four different 
resolutions, where scaled image sizes equal to original size 
divided by 2 n , n = (0,1,2,3). The corresponding correlation 
window sizes are 3x3, 5x5, 7x7 and 9x9, while the census 
transform window sizes are 3x3, 5x5, 7x7, and 9x9. The final 
disparity map is shown in Figure 9. Figure 10 shows generated 
DEM image and ground truth image. 
Figure 8. Example of epipolar images 
Figure 10. Generated DEM image and ground truth image 
Figure 11. Example of low level extraction result 
Figure 11 shows the line segments obtained from low level 
feature extraction process. The number of extracted line 
segment is about 1425. To remove unnecessary line segments, 
we use the suspected building regions extracted from the 
disparity map as shown in Figure 12.