ISPRS Commission III, Vol.34, Part 3A ,Photogrammetric Computer Vision“, Graz, 2002 
  
tree contains the partitions corresponding to each partitioning 
scheme. 
Next, the tree will be expanded with a level corresponding to 
the different building hypotheses generated for each building 
partition. Corresponding to each building primitive defined 
in the building library, a building hypothesis is generated. 
The estimation of the parameters of the building model is 
performed using a fitting algorithm, which fits the edges of 
the projected wire frame of the model to gradients of the 
pixels from both images simultaneously. 
The building hypotheses can be verified by back projecting 
them into the images and then matching with the informa- 
tion extracted from the images. The matching defines a score 
function that will be used to guide the search in the tree. 
So, this function allows comparison and evaluation of differ- 
ent building hypotheses. The score function is based on the 
formulation of the mutual information between the building 
model and the images. 
The CSG tree representing a building will be given by the 
best fit of the building models corresponding to the building 
partitions. In the final verification step the complete CSG 
tree will be fit to the image data. To improve the results, 
constraints, which describe geometric relationships between 
building primitives, are incorporated in the fitting algorithm. 
If all the partitioning schemes are rejected by the tree search 
then the partitioning has to be refined using image informa- 
tion as well. This process will start up a new branch in the 
search tree and the whole process is repeated. 
3 LOCALIZATION OF BUILDINGS INTO THE 
IMAGES 
Most of the building reconstruction strategies have two main 
parts: the localization step and the actually reconstruction 
step, more or less connected. The localization of the building 
in the images means the detection of regions of interest where 
the buildings lie. By having the building localized in the 
images first, the reconstruction process can be focused on 
one building reduces the complexity of the reconstruction by 
a large amount. 
In [Suveg and Vosselman, 2000] information about the 
ground plan of the building contained in the GIS database 
was used to delineate a building in an image. The uncertain- 
ties introduced by different knowledge sources were identified 
and a two step method was developed to quantify these un- 
certainties and determine the region where the building lies 
in the image. In the building localization process the uncer- 
tainties are due to: the unknown height of the buildings, the 
accuracy of the map, the roof extensions, and the feature 
extraction. 
In the first step of the proposed method the uncertainty due to 
the unknown height of the buildings is handled, by assuming 
that height of a building is between two extreme values. By 
projecting the ground plan of the building into the image 
for each of these extreme values two contours are obtained. 
These contours are concatenated in order to get the area 
where the building is located. In the next step the contour 
obtained after the concatenation process is dilated taking in 
order to handle the other uncertainties mentioned above. 
This method worked well in case of small height variations 
of the terrain, i.e. close extreme values. The method could 
  
Figure 1: Localization of the building and the pattern used 
in the localization process 
handle variations of 15 m in height. Applying the method for 
larger height variations would increase the obtained region 
where the building lies. In case of a very oblique view this 
region becomes so large that it may include multiple building 
structures (Figure 1). 
We have extended this method to be able to handle large 
variations in height. A large interval of height values can be 
reduced to a few individual height values which have to be 
checked afterwards by some higher level image understanding 
methods. Therefore the building localization can no longer be 
separated from the building reconstruction process anymore. 
The main idea is to divide the interval of height variations into 
small intervals. On these small intervals the former method 
can be applied to determine the maximal region and the min- 
imal region inside of which the building could lie. For each 
of these small intervals a function that looks for evidence in 
the image that the building lies in that region is defined. In 
order to compute this function lines are extracted from the 
image and the image lines which lie between the maximal and 
the minimal region are selected. Afterwards the length of the 
selected lines are summed up to compute the score for the 
given interval of height values. The score is integrated over 
both images. A high value indicates a high likelihood for the 
correct height of the building. This score is computed for 
each height interval. 
Actually this process can be seen as moving the pattern de- 
fined by the maximal and minimal region along a line in the 
image and counting for evidence for each position. In this 
way we get the graphic of the likelihood of having the build- 
ing correctly localized for different height values (Figure 2 
corresponding to the building from Figure 1). 
Generally, a threshold of 70% of the largest peak can be used 
the select the peaks which might correspond to the correct 
building height. With this thresholding a large interval of 
height values is reduced to some individual values. 
Unfortunately, not all peaks in the graph correspond to cor- 
rect building locations. For instance, an edge corresponding 
to a road might introduce a false peak in the graph. There- 
fore, each peak has to be verified. This verification can be 
done by actually trying to find the building model which best 
describes the image data. 
Since the building model generation process was designed to 
A- 357