b. Beijing 2008 
VCH 
;d on the RAG 
nt the topologi- 
lass. Therefore, 
;r, they are can- 
'e-segmentation 
; stage includes 
hs. However, it 
[f urban objects 
e algorithm can 
Another impor- 
rge the regions, 
rectangular and 
ration. 
ation approach, 
are 3, it is pos- 
i regions. Our 
regular objects 
similar regions 
heir spectral at- 
nore regions to 
im. 
es a sample im- 
ess. The three 
'AG’s construc- 
■ in the Figure. 
lportant task in 
allows the algo- 
ling out regular 
for further pro- 
n order to clas- 
gure 5 presents 
g Maps (Koho- 
Figure 3. After 
ing adjacent re- 
xt stage tries to 
nerge the nodes 
ularity. 
dements can be 
path through a 
The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part Bib. Beijing 2008 
Roofs 
Streets 
Trees 
№ 
%• 
• 
Figure 3: Input Patterns. 
graph (Hart et al., 1968). It provides a structure whose nodes 
are connected to one or more neighboring regions. 
Several algorithms to find the minimum-cost path in a RAG have 
been proposed in the literature (Falcao et al., 2004, Shi and Ma 
lik, 2000). A minimum-cost path is a set of edges that connects 
all nodes in a graph without cycles. As this graph connects all re 
gions belonged to the same class, a minimum-cost path represents 
the best way to find the cuts. 
Regarding the urban imagery, the graph edges represent the reg 
ularity measures of the regions obtained by the union of two or 
more sub-regions. The problem is to find out which regions must 
be merged or not. Next section, we will discuss about the parame 
ter Q that indicates how rectangular a region is, independently of 
rotation and scale. The objective is to merge regions to generate 
new objects with shapes more appropriate to urban objects. 
The following algorithm summarizes the proposed approach 
shown in Figure 2: 
Get input over-segmented images; 
Classify the regions (identify the classes); 
Build RAGs for adjacent objects of same class; 
For each RAG, find the best merging arrangement: 
I Find minimal-cost path; 
I Calculate regularity measure; 
I Perform path cuts; 
I Merge connected nodes; 
Return resultant regions. 
(a) (b) 
Figure 5: Pattern classification; a) input regions, b) classified 
regions. 
3.3 Rectangular objects generation 
Some good examples of rectangular regions for urban imagery 
are roofs and streets. However, in some cases the segmented 
objects do not preserve such rectangular shape; they are broken 
apart into smaller irregular objects. Therefore, our aim is to join 
such over-segmented regions. 
In order to identify the object rectangularity degree we calculate 
the ratio between its area AREA(Pi) and its bounding box area 
AREA(BOX(Pi)). Due to the rotation, this measure can not 
correctly represent the object regularity. Thus, a preprocessing 
step is performed in order to transform the retangularity measure 
invariant to rotation. 
Given an object Pi and its internal points coordinates 
Ci = {{x,y}\{x,y} E Pi} (1) 
the eigenvectors of Ci are calculated. Taking the first eigenvector 
the main angle of Pi, a is obtained. Thus, a new region Ri with 
bounding box BOX(Ri) is created by rotating it in relation to 
the angle a. Afterward, the unbiased parameter Q is obtained as 
following: 
AREA(Ri) 
AREA(BOX(Ri)) 
(2) 
(c) (d) 
Figure 4: Sample image and full re-segmentation process: a) in 
put urban image, b) input segments, c) classified input and d) 
resultant re-segmentation. 
395 
The range of Q is [0, 1]. The more rectangular the object Pi, the 
closer to 1 is the parameter Q. Figure 6 shows an example of a 
rectangular object with Q « 1. 
Figure 6: Rectangular objects identification: a) input region, b) 
the region and its bounding box, c) the rotated region and its new 
bounding box and Q « 1. 
At this stage, the algorithm aims to find rectangular objects. If 
irregular objects are found, two operations are performed: cut 
ting and merging. The objective of these operations is to generate 
regions whose parameter Q is about 1. As we can observe in Fig 
ure 7, some regions belonging to the same class can be split into 
smaller regions instead of being merged in the initial segmen 
tation process. These are the main problem that our algorithm 
proposes to solve.