An Improved Algorithm Based on Minimum Spanning Tree for Multi-scale Segmentation of Remote Sensing Imagery

doi:10.11947/j.AGCS.2015.20140060

Abstract

Abstract:

As the basis of object-oriented information extraction from remote sensing imagery,image segmentation using multiple image features,exploiting spatial context information, and by a multi-scale approach are currently the research focuses. Using an optimization approach of the graph theory, an improved multi-scale image segmentation method is proposed. In this method, the image is applied with a coherent enhancement anisotropic diffusion filter followed by a minimum spanning tree segmentation approach, and the resulting segments are merged with reference to a minimum heterogeneity criterion.The heterogeneity criterion is defined as a function of the spectral characteristics and shape parameters of segments. The purpose of the merging step is to realize the multi-scale image segmentation. Tested on two images, the proposed method was visually and quantitatively compared with the segmentation method employed in the eCognition software. The results show that the proposed method is effective and outperforms the latter on areas with subtle spectral differences.

Key words: multi-scale segmentation, minimum spanning tree, minimum heterogeneity criterion, remotely sensed imagery

CLC Number:

P237
TP751.1

LI Hui, TANG Yunwei, LIU Qingjie, DING Haifeng, JING Linhai. An Improved Algorithm Based on Minimum Spanning Tree for Multi-scale Segmentation of Remote Sensing Imagery[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(7): 791-796.

References

[1] BAATZ M, SCHÄPE A. Multiresolution Segmentation: An Optimization Approach for High Quality Multi-scale Image Segmentation[J]. Journal of Photogrammetry and Remote Sensing, 2000, 58(3-4): 12-23.
[2] NEUBERT M, HEROLD H, MEINEL G. Assessing Image Segmentation Quality——Concepts, Methods and Application[M]//BLASCHKE T, LANG S, HAY G J. Object-based Image Analysis. Berlin: Springer, 2008: 769-784.
[3] MARPU P R, NEUBERT M, HEROLD H, et al. Enhanced Evaluation of Image Segmentation Results[J]. Journal of Spatial Science, 2010, 55(1): 55-68.
[4] WANG M. A Multiresolution Remotely Sensed Image Segmentation Method Combining Rainfalling Watershed Algorithm and Fast Region Merging [C] //Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Beijing: [s.n.], 2008: 1213-1218.
[5] LIU Jing, LI Peijun. A High Resolution Image Segmentation Method by Combined Structural and Spectral Characteristics[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(5): 466-473. (刘婧, 李培军. 结合结构和光谱特征的高分辨率影像分割方法[J]. 测绘学报, 2014, 43(5): 466-473.)
[6] WU Zhaocong, HU Zhongwen, ZHANG Qian, et al. On Combining Spectral, Textural and Shape Features for Remote Sensing Image Segmentation[J]. Acta Geodaetica et Cartographica Sinica, 2014, 42(1): 44-50. (巫兆聪, 胡忠文, 张谦, 等. 结合光谱纹理与形状结构信息的遥感影像分割方法[J]. 测绘学报, 2014, 42(1): 44-50.)
[7] MORTENSEN E N, BARRETT W A. Intelligent Scissors for Image Composition [C]//Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques.New York: [s.n.], 1995: 191-198.
[8] ZAHN C T. Graph-theoretical Methods for Detecting and Describing Gestalt Clusters[J]. IEEE Transactions on Computers, 1971, C-20(1): 68-86.
[9] XU Y, UBERBAEHER E C. 2D Image Segmentation Using Minimum Spanning Trees[J]. Image and Vision Computing, 1997, 15(1): 47-57.
[10] LERSCH J R, IVERSON A E, WEBB B N, et al. Segmentation of Multiband Imagery Using Minimum Spanning Trees [C] //Aerospace/Defense Sensing and Controls, International Society for Optics and Photonics.Orlando, FL: SPIE, 1996: 10-18.
[11] FELZENSZWALB P F, HUTTENLOEHER D P. Efficient Graph-based Image Segmentation[J]. International Journal of Computer Vision, 2004, 59(2): 167-181.
[12] WU Z, LEAHY R. An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, 15(11): 1101-1113.
[13] BOYKOV Y Y, JOLLY M P. Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in ND Images [C] //Proceedings of the 8th IEEE International Conference on Computer Vision.Vancouver, B C: IEEE, 2001: 105-112.
[14] PENG B, ZHANG L, ZHANG D. A Survey of Graph Theoretical Approaches to Image Segmentation[J]. Pattern Recognition, 2013, 46(3): 1020-1038.
[15] CUI W H, ZHANG Y. An Effective Graph-based Hierarchy Image Segmentation [J].Intelligent Automation & Soft Computing, 2011, 17(7): 969-981.
[16] WEICKERT J. Anisotropic Diffusion in Image Processing [M].Stuttgart: Teubner, 1998.
[17] WEICKERT J, SCHARR H. A Scheme for Coherence-enhancing Diffusion Filtering with Optimized Rotation Invariance[J]. Journal of Visual Communication and Image Representation, 2002, 13(1-2): 103-118.
[18] ZHANG H, FRITTS E J, GOLDMAN S A. Image Segmentation Evaluation: A Survey of Unsupervised Methods[J]. Computer Vision and Image Understanding, 2008, 110(2): 260-280.
[19] HARALICK R M, SHAPIRO L G. Image Segmentation Techniques[J]. Computer Vision, Graphics, and Image Processing, 1985, 29(1): 100-132.
[20] ESPINDOLA G M, CAMARA G, REIS I A, et al. Parameter Selection for Region-growing Image Segmentation Algorithms Using Spatial Autocorrelation[J]. International Journal of Remote Sensing, 2006, 27(14): 3035-3040.
[21] KIM M, MADDEN M, WARNER T. Estimation of Optimal Image Object Size for the Segmentation of Forest Stands with Multispectral IKONOS Imagery[M]//BLASCHKE T, LANG S, HAY G J. Object-based Image Analysis. Berlin: Springer, 2008: 291-307.
[22] TRIMBLE GERMANY GMBH. eCognition Developer 8.7, 2009[EB/OL].[2011-09-26]. http://www.ecognition.com.