Figure 1 : RAG example - Image with 5 regions and their con 
nections. 
In this case, the graph weights correspond to each region mean 
value. (Duarte et al., 2006) use the so called hierarchical so 
cial metaheuristic for the merging operation, which is based on 
human social behavior. First of all, the regions are joined in a 
randomly way generating a set of solutions controlled by groups 
of objective functions. Iteratively, each group tries to improve its 
objective in a cooperative fashion or competing with the neighbor 
groups. The ambivalence between social cooperation and compe 
tition aims to maximize the quality of the results. 
In the other hand, (Lezoray et al., 2003) apply a preprocessing 
stage to smooth the RAG at each region before merging simi 
lar regions. This stage is iterated until the RAG satisfies some 
stop criterion such as the number of iterations or some similarity 
threshold. Using a nonlinear function, they perform smoothing 
operation over the iterations taking into account the regions spec 
tral attributes and connected region neighbors. 
Here, we propose a new merging strategy in the RAG structure. 
The regions are merged if they are similar in respect to their spec 
tral attributes (e.g. mean and variance) and if the resultant shape 
(after merging operation) is regular. In order to carry out this task, 
firstly, the regions are divided taking into account their classes. In 
case of urban environment, the classes can be buildings, streets, 
and trees. Therefore, the regions are classified and several RAG 
are built through connecting adjacent regions which belong to the 
same class. Afterward, the algorithm perform the graph searching 
and merging operations for every classes. The knowledge about 
the class improves the segmentation accuracy because each class 
has specific shape regularity measure. 
2.2 RAG construction 
Let be an image I and a group of M regions, Pi,i = 
with |J Pi = /. Let be a graph, G =< VJH > , where V = 
{1 ,...M } is the set of nodes and E C V x V is the set of edges 
or links between adjacent regions. In the graph notation, each 
region Pi matches one vertex so that P % = V t ,i =1 ,...M 
Each region is a vertex Vi. Adjacent regions have the weights 
defined by some spectral distance measure. Table 1 depicts the 
graph generated from Figure 1. Here, the weights are given by 
the mean differences between connected nodes. Weights denoted 
by -1 means that there is not topological connection between the 
nodes. 
3 RE-SEGMENTATION APPROACH 
The proposed re-segmentation approach is based on the RAG 
construction. The graph is built taking into account the topologi 
cal relation “touch” between the regions of same class. Therefore, 
if two regions are connected, i.e. touch each other, they are can 
didate to be graph nodes. In order to perform the re-segmentation 
the RAGs are preprocessed. This preprocessing stage includes 
the procedure to find the graph minimal-cost paths. However, it 
is necessary to know the class of each region. If urban objects 
samples (trees, roads, buildings) are provided the algorithm can 
treat them conform with their own properties. Another impor 
tant parameter is the object regularity used to merge the regions. 
For instance, roads and trees can be assigned to rectangular and 
irregular shapes, respectively, in the merging operation. 
Figure 2 shows the diagram of our re-segmentation approach. 
Based on input patterns, as those shown in Figure 3, it is pos 
sible to define different strategies to merge the regions. Our 
objective is to merge regions so that new larger regular objects 
are obtained. For objects with irregular shapes, similar regions 
are merged based on previous classification and their spectral at 
tributes. The process finishes when there is no more regions to 
merge. 
Figure 2: The re-segmentation diagram. 
To picture the proposed diagram, Figure 4 exposes a sample im 
age that goes through the re-segmentation process. The three 
main operations, namely pattern classification, RAG’s construc 
tion and graph search, plus the final result appear in the Figure. 
3.1 Pattern classification 
The pattern classification procedure is a very important task in 
our approach. It reduces the attribute space and allows the algo 
rithm to work with few data in the process of finding out regular 
shapes. In this stage, similar regions are merged for further pro 
cessing. 
Firstly, a supervised classification is performed in order to clas 
sify the regions in accord with their pattern. Figure 5 presents 
a resultant classification using the Self Organizing Maps (Koho- 
nen, 2001) and the three classes depicted in the Figure 3. After 
the classification, the RAGs are built by connecting adjacent re 
gions belonging to the same class. Finally, the next stage tries to 
find the best way to connect the graphs, to cut or merge the nodes 
so that the resultant regions have better shape regularity.