The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B3b. Beijing 2008 
(a) (b) 
Figure 7: Objects merging process: a) connected regions, b) re 
segmentation taking into account the rectangular shaped regions. 
4 PRELIMINARY RESULTS 
This Section presents some experimental results obtained by our 
re-segmentation approach. The method was tested for Quickbird 
images of urban regions. For the first experiment, a segmented 
image superimposed on the original image (300 x 250 pixels), 
some connected nodes (represented in different colors) and the 
resultant re-segmentation are shown in Figures 8a, 8b and 8c, re 
spectively. The over-segmentation was obtained by the region 
growing method implemented in SPRING (Camara et al., 1996). 
In Figure 8c we observe that some regions did not merge although 
they look like spectrally similar. This is due to the fact that the ap 
proach aims to merge only those regions which originate rectan 
gular objects. Other merging or cutting operations that originate 
irregular objects are not performed. Consequently, the segmenta 
tion gets more adequate results. In this case, the algorithm took 
37 seconds to generate the re-segmentation. 
The second experiment took an image (256 x 256 pixels) as 
shown in Figure 9. Figures 9a and 9b display the regions super 
imposed on the original image and the resultant re-segmentation, 
respectively. The over-segmentation also was obtained by the 
region growing method implemented in SPRING. The image 
presents several instances of roofs that are broken apart in the 
segmentation process as shown in Figure 8a. It is important to 
emphasize that the segmentation is the key step for further image 
analysis. After applying our approach, posterior stages of image 
recognition or even geographical tasks can be more accurate or 
adequate to the application. In spite of using small image in this 
experiment, the number of input over-segmented regions is very 
high. In this case, the algorithm spent 216 seconds to accomplish 
the complete re-segmentation process. 
5 CONCLUSIONS 
A new approach for image re-segmentation and some aspects of 
its implementation have been described. Moreover, in order to 
show the potential of our approach two experimental results have 
been presented. The main contribution of this paper is the pro 
posed strategy to find regular regions in the urban imagery. The 
re-segmentation approach uses spectral and shape attributes as 
well the thematic map to define the merging and cutting strate 
gies in the RAGs. 
The algorithm complexity including the graph searching opera 
tion is 0(n 2 ). One way to improve its performance is generat 
ing a Minimum Spanning Tree (MST) before the graph search 
ing procedure. Nevertheless, the MST generation has also a high 
cost. Therefore, research have to be done to find out the attributes 
set used to find the MST, which is not a trivial task. 
The algorithm has been developed in the Free C++ Li 
brary called TerraLib (Camara et al., 2000) available at 
http://www.terralib.org/. Preliminary results presented in 
this paper still have some errors mainly due to the input segmen 
tation. This process, in certain cases, merges some objects that 
should be broken apart. Future works include the algorithm op 
timization for faster execution and implementation of different 
approaches for the graph cutting operation. 
REFERENCES 
Baatz, M. and Schápe, A., 2000. Multiresolution Segmentation- 
an optimization approach for high quality multi-scale image 
segmentation. Angewandte Geographische Informationsverar- 
beitung XII, Wichmann-Verlag, Heidelberg 12, pp. 12-23. 
Bins, L., Fonseca, L., Erthal, G. and Ii, F, 1996. Satellite imagery 
segmentation: a Region Growing approach. Simposio Brasileiro 
de Sensoriamento Remoto 8, pp. 677-680. 
Camara, G., Souza, R., Freitas, U. and Garrido, J., 1996. Spring: 
integrating remote sensing and GIS by object-oriented data mod 
elling. Computers & Graphics 20(3), pp. 395-403. 
Camara, G., Souza, R., Pedrosa, B., Vinhas, L., Monteiro, A., 
Paiva, J., Carvalho, M. and Gatass, M., 2000. TerraLib: Tech 
nology in Support of GIS Innovation. II Workshop Brasileiro de 
Geoinformática, Geolnfo2000 2, pp. 1-8. 
Chen, Z., Zhao, Z., Gong, P. and Zeng, B., 2006. A new process 
for the segmentation of high resolution remote sensing imagery. 
International Journal of Remote Sensing 27(22), pp. 4991-5001. 
Duarte, A., Sánchez, A., Fernández, F. and Montemayor, A., 
2006. Improving image segmentation quality through effective 
region merging using a hierarchical social metaheuristic. Pattern 
Recognition Letters 27(11), pp. 1239-1251. 
Egenhofer, M. and Franzosa, R., 1991. Point-set topological spa 
tial relations. International Journal of Geographical Information 
Science 5(2), pp. 161-174. 
Falcáo, A. X., Stolfi, J. and Lotufo, R. A., 2004. The Im 
age Foresting Transform: Theory, Algorithms, and Applications. 
IEEE Trans, on Pattern Analysis and Machine Intelligence 26(1), 
pp. 19-29. 
Felzenszwalb, P. and Huttenlocher, D., 2004. Efficient Graph- 
Based Image Segmentation. International Journal of Computer 
Vision 59(2), pp. 167-181. 
Hart, P, Nilsson, N. and Raphael, B., 1968. A Formal Basis for 
the Heuristic Determination of Minimum Cost Paths. Systems 
Science and Cybernetics, IEEE Transactions on 4(2), pp. 100- 
107. 
Kohonen, T., 2001. Self-Organizing Maps. Springer. 
Lezoray, O., Elmoataz, A., SRC, I., EA, L. and Saint-Lo, F, 
2003. Graph based smoothing and segmentation of color im 
ages. Signal Processing and Its Applications, 2003. Proceedings. 
Seventh International Symposium on. 
Lucchese, L. and Mitra, S., 2001. Color image segmentation: 
A state-of-the-art survey. Proc. of the Indian National Science 
Academy (INSA-A) 67(2), pp. 207-221. 
Schettini, R., 1993. A segmentation algorithm for color images. 
Pattern Recogn. Lett. 14(6), pp. 499-506. 
Shi, J. and Malik, J., 2000. Normalized Cuts and Image Seg 
mentation. IEEE Transactions on Pattern Analysis and Machine 
Intelligence 22(8), pp. 888-905. 
Tremeau, A. and Colantoni, R, 2000. Regions adjacency graph 
applied to color image segmentation. Image Processing, IEEE 
Transactions on 9(4), pp. 735-744.