ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision“, Graz, 2002 
  
Increasing the training data set size doesn’t affect the 
detection rate significantly, we can see that the range of the 
detection rate is between 98.2% and 99.2%; we gain only 1% 
in the detection rate when we increase the size of the training 
data set from 20 samples to 400 samples. However 
increasing the size of the training data set has a significant 
effect on the false alarm rate. Increasing the size of the data 
set from 20 samples to 400 samples reduce the false alarm 
rate from 11.5% to 5.5%; we gain 6.0% improvement in the 
false alarm rate by increasing the size of the training data set 
from 20 samples to 400 samples. The results using 100 
training samples are used in the rest of this research. 
4. CONVERTING REGIONS TO POLYGONS 
The 2D modified Hough space discussed in the previous 
section is helpful in extracting the border lines for the roof 
regions. Given all points contributing to a certain cell, a 
nonlinear least squares estimation model is used to adjust the 
line parameters given the cell locations in the parameter 
space as approximate values for the line represented by this 
cell. Lines are then grouped recursively until no more lines 
with similar parameters are left. Short lines are then rejected. 
Figure 6 shows the extracted border lines for two buildings. 
  
Figure 6. Extracted Border Lines for 2 Buildings 
The next step is to convert the extracted lines to polygons 
using a rule-based system. The rules are designed as complex 
as possible to cover a wide range of polygons. Figure 6 
shows the challenging in converting the extracted border 
lines to polygons. For some polygons they might be 
quadrilaterals, however only three borderlines are detected. 
Some quadrilateral regions might have more than four 
borderlines detected. The mechanism that is developed in 
this research works in three steps. The first step is to find all 
the possible intersections between the borderlines. However 
if the two lines are almost parallel the intersection point is 
not considered. If the distance between the end point of the 
line and the intersection point is large the intersection point is 
rejected. The next step is to generate a number of polygons 
from all the recorded intersections. Each combination of four 
or three intersection points is considered to be a polygon 
hypothesis. Some hypotheses are ignored if the difference in 
area between the region and the hypothesized polygon is 
more than 50%. If the internal angles between the intersected 
lines is out of the range [30°-150°] the hypothesis is 
discarded. The third step is to find the optimal polygon that 
represents the region borders. The best polygon that 
represents the region is chosen from the remaining polygons. 
A template matching technique is used to find the best 
polygon that represents the region. Figure 7 shows the 
extracted polygons for two buildings. 
  
Figure 7. Extracted Image Polygons for 2 Buildings 
5. 3D POLYGON EXTRACTION 
In this section the process of finding the correspondence 
polygons among all images and matching them is discussed. 
5.1. Polygon Correspondence 
After finding the building roof polygons in the images, we 
start finding the correspondence polygons. We designed a 
new technique to find correspondence polygons based on 
their geometrical properties. All possible polygon 
correspondence combinations are considered and for each 
combination the vertices of the correspondent polygons are 
matched across all available views, since we have more than 
one pair of images we can calculate the residuals of the 
matched 3D polygon vertices. The matching residuals are 
summed for each combination set, and the combination set 
with the minimum residual is selected as the best 
combination set. Figure 8 describes the process of finding the 
correspondence polygons in four images. In order to 
minimize the running time, some subsets are rejected before 
the matching process using the epipolar geometry and the 
minimum and maximum building heights. 
  
  
   
  
Image A Image B Image D 
e LU 
Polygon Total Total Residual 
Combinations Residuals 
  
1111 &2222 R =p ir 
ABCD  ABCD Ts m 
141: 12-&2 22 R =r +r 
ABCD “ABCD 2-34 
11241. &2212 R =r +r 
ABCD "ABCD 3.56 
1122 &2 221 R =r +7 
ABCD" ABCD 4 7 
1211 &2122 R =r +1 
ABCD ABCD 59 10 
1 212 &2 12 1 R = ty 
ABCD "ABCD 6 1112 
  
  
  
8 
  
  
  
  
  
  
  
  
W Combination 
  
  
  
Figure 8. The Multi Image Polygon Matching Process