recognized as an “empty” polygon, otherwise the null value 
is assigned as the partitioning score for P^ by H. The "best" 
partition of P^ can be obtained when an "empty" polygon 
with the largest area is produced by // (see figure 9 (b)). 
The partition scoring function, H, for "pseudo-closed" 
polygon can be described by 
  
A(P* 
H(P' Wu) ) if P" ="empty" polygon 
  
A(P”) 
A(P! 
jte 0) = E if P z"empty" polygon “@ 
[re NU ) =0 if P" #"empty" polygon 
IE HL) =0 if P" #"empty" polygon 
where A() is the area of corresponding polygon. In fact, the 
partition functions defined in Eq. 3 and Eq. 4 generate 
polygons according to their level-of-detail forming a 
building object; the most "significant" building part is 
generated first and less "significant" one is later. 
  
  
   
lower partitioning score higher partitioning score 
(a) “open” polygon 
  
  
lower partitioning score higher partitioning score 
(b) “pseudo-closed” polygon 
Q non-building label Q building label 
Figure 9. Illustration of partition scoring functions 
Once the partitioning scores for h' are computed by Eq. 3 or 
Eq. 4, remaining hyperlines are sequentially selected from 
the hyperline list and their partitioning scores are measured 
by H. In figure 7(b), a hyperline, 4”, with the maximum 
partitioning score is finally selected to partition P^. Then, 
geometric information of P^ and A" are stored as a root node 
of BSP tree, which is expanded as new child nodes with 
vertices of P'* and P^ are added to the root node for further 
recursive partitioning. The same method used for the 
partition of P^ is applied to P'* and P^ respectively, but to 
only an “open” or “pseudo-closed” polygon. This process 
continues until no leaf node of the BSP tree can be 
partitioned by hyperlines (see figure 7 (c)). 
4.4 Polygonal cue grouping 
Figure 10 (a) — (c) shows an example how the BUS space 
with a set of convex polygons is generated by the recursive 
partition of an initial polygon as described in the previous 
section. 
Once the BUS space is generated by expanding a BSP tree, 
final leaves of the BSP tree are collected. A heuristic 
filtering is applied to them so that only "building" polygons 
remain (see figure 10(d)). A convex polygon of final leaves 
   
  
   
    
   
   
     
   
    
   
  
   
    
   
       
    
     
     
    
   
   
     
    
     
    
    
   
     
  
    
     
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
of the BSP tree is verified as the "building" polygon by 
following rules: 
e A polygon, P, is verified as the “building” polygon If it 
is classified as "closed" polygon, satisfying following 
conditions: 
N, (P) » n, and d, (P) » yxd,; P 5 "closed" polygon(5) 
where Nye» is the number of member points of P^. n, 
(75) is a member point threshold; d,, is the point density 
of P' computed by Eq. 1; y (70.6) is a control parameter 
(0€ y €1); dj, (70.1) is a point density threshold. 
e A polygon, P, is verified as the “building” polygon if it 
is classified as "open" polygon, satisfying following 
conditions: 
N ULP! 
Pp» (P) = IU > Pns P* ="open" polygon (6) 
where py; is a point ratio of building labels over the total 
number of member points of P and its threshold is pil 
(70.6); Ny, and N,,,,, are functions to count numbers of 
building labels and non-building labels belonging to P'. 
  
(a) initial partitioning (b) intermediate partitioning 
      
(c) final BSP partitioning (d) “open” polygon filtering 
Figure 10. Polygonal cue generation and grouping 
5S. BUILDING EXTRACTION RESULT 
Figure 11(a) shows a building extraction result over the 
Greenwich dataset (referred as the UCL building map) 
generated by the proposed technique. The overall success of 
the technique was evaluated in comparison with the ground 
plan vectors of MasterMap® provided by the Ordnance 
Survey (see figure 11(b)). 
Although the OS MasterMap® provides a high-level of detail 
and accuracy, there are distracting features of the OS 
MasterMap® that causes difficulties in the quality 
assessments. The OS data does not contain some buildings 
even though they are obviously apparent in the Ikonos image 
and lidar. This is because the OS data was constructed at a 
different time to the acquisition of the Ikonos image and 
lidar data, from which the UCL building map was generated. 
In addition, the scale of the features in the OS MasterMap” 
has been compiled at a larger scale than the one of Ikonos 
Inte 
— 
ima 
rec 
inte 
rath 
the 
sme 
poii 
Fi; 
A 1 
Shu 
qua 
algc 
bui, 
bra 
que 
whe 
data 
clas 
clas 
Neg 
Mas 
and 
Eq.