anbul 2004 
btained. In 
, by which 
regularized 
ar space in 
cue density 
h intensity 
re inferred 
pointing to 
ed. To this 
h of /,=5m 
of detecting 
ection, the 
rrain point 
er (o have 
n size (see 
ded, but at 
ons to the 
Thus, “1/2 
| boundary 
rtual lines 
then, their 
cast-square 
; extracted 
  
il line cue 
tion 
tion result 
olygons by 
hyperlines. 
by BSP 
oduced by 
1e overall 
se that we 
wherein 
and non- 
tored as a 
oning (see 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
A set of hyperlines, {h':i=1,...,N}, are computed as P! is 
intersected respectively by a set of line segments, 
Ini... NI which is constructed by integrating the data- 
driven and model-driven line cues. After setting up the 
hyperline list, a process to partition P" with hyperlines 
starts. This partitioning process consists of two procedure; 
polygon classification and partition scoring. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
pp me = 5 
O 
(a) 
ris) 
p ? 
? zo ) 
Poh p 
p P 
best partition 
Partition test and scoring Partitioning result BSP tree 
© “open” or "pseudo-closed" polygon Q closed" or'empty' or "garbage polygon 
Figure 7. Illustration of polygonal cue generation 
43.1  Polygon classification 
Polygon classification is a process to determine whether or 
not the partitioning process is triggered over a given 
polygon, P'. A polygon, P, is classified into a number of 
polygon classes; "empty", "open", "closed", "pseudo- 
closed”, “garbage” polygon. These polygon classes are pre- 
determined depending on the labelling attributes of the 
member points of P' or point density of the member points of 
P or geometric property of P' as follows: 
  
      
O 
eee 
o e Oo 
  
  
  
  
  
(a) "empty" polygon (c) "closed" polygon 
(b) “open” polygon 
  
P i 
n 
| e P' a 
| ® © ; = Ge” e if «lI, or A Xa, 
  
(d) 'Pseudo-closed" polygon (e) “garbage” polygon 
© non-building label Q building label 
Figure 8. Polygon classification 
* "Empty" polygon: P' is classified as “empty” polygon if 
there is no member point within P (see figure 8 (a)). 
* “Open” polygon: P is classified as "open" polygon if 
the member points of P are attributed with both 
building and non-building labels (see figure 8 (b)). 
* "Closed" polygon: P is classified as "closed" polygon if 
the member points of P' are attributed with only building 
label (see figure 8 (c)). 
* "Pseudo-closed" polygon: P' is classified as "pseudo- 
closed" polygon if the member points of P* are attributed 
with only building label, and the point density of P. 
dp(P), is less than d;=0.1 (see figure 8 (d)), where 
d, (P^) is determined by 
NP 
gl 0 
where N,en(P) and A’ are the number of member points 
and the area of P' respectively. 
e "Garbage" polygon: P is classified as "garbage" 
polygon if the member points of P are attributed with 
both building and non-building labels, and any lateral 
length or the area P is less than a certain threshold, i.e., 
l7 5 and a,5,750 respectively (see figure 8 (e)) 
The P' is partitioned with two child convex polygons if it is 
classified as “open” or “pseudo-closed” polygon; otherwise 
the partitioning over P' is terminated. 
4.3.2 Polygon scoring 
Once the partitioning of P is determined through the 
polygon classification. The second step is partition scoring. 
This process determines a hyperline, h', to generate the 
“best” partitioning result of P' from the hyperline list. The 
selection of /' is achieved by a partition scoring function. 
That is, all the hyperlines are tested to obtain the "best" 
partition of P' and the partitioning result generated by each 
hyperline is evaluated by a partition scoring function. A 
hyperline, h', with the highest partitioning score is finally 
selected to partition P'. The partition scoring function, A, 
over a polygon, P^, is given by 
H (P^: l)e arg max (H(P^ WP gn #1) (2) 
where P/* and P^ are child polygons produced by halving P” 
with a hyperline, A’. In Eq 2, H assigns a maximum score to 
A if it produces the best partitioning result, whereas a 
minimum score for the worst partitioning result. Also, H 
differently computes scores depending on the polygon class 
of P^. 
If P^ is classified as the “open” polygon, H computes 
partitioning scores according to a bias degree of Ibe 
distribution over P'* and P^ divided by h'; H for “open” 
polygon computes higher partitioning score when a “closed” 
polygon with larger area is produced by // (see figure 9 (a)). 
The partition scoring function, 77, for *open" polygon can be 
described by 
P: = 
P. I) (3) 
(Pul) Nora 
(rar) Nul 
val? 5 ls NE (Psi. 3 
(Pun) Gus 
  
N on-bld 
  
N on- bld 
where A,,44 and Ny are functions to count numbers of 
building labels and non-building labels belonging to a 
corresponding polygon. 
If. P is classified as the "pseudo-closed" polygon, 77 
computes the partitioning score by an area ratio of child 
“empty” polygon over P^ when either of P^ and P^ is