High-resolution Remote Sensing Image Segmentation Using Minimum Spanning Tree Tessellation and RHMRF-FCM Algorithm

doi:10.11947/j.JGGS.2020.0106

Abstract

Abstract:

It is proposed a high resolution remote sensing image segmentation method which combines static minimum spanning tree (MST) tessellation considering shape information and the RHMRF-FCM algorithm. It solves the problems in the traditional pixel-based HMRF-FCM algorithm in which poor noise resistance and low precision segmentation in a complex boundary exist. By using the MST model and shape information, the object boundary and geometrical noise can be expressed and reduced respectively. Firstly, the static MST tessellation is employed for dividing the image domain into some sub-regions corresponding to the components of homogeneous regions needed to be segmented. Secondly, based on the tessellation results, the RHMRF model is built, and regulation terms considering the KL information and the information entropy are introduced into the FCM objective function. Finally, the partial differential method and Lagrange function are employed to calculate the parameters of the fuzzy objective function for obtaining the global optimal segmentation results. To verify the robustness and effectiveness of the proposed algorithm, the experiments are carried out with WorldView-3 (WV-3) high resolution image. The results from proposed method with different parameters and comparing methods (multi-resolution method and watershed segmentation method in eCognition software) are analyzed qualitatively and quantitatively.

Key words: static minimum spanning tree tessellation; shape parameter; RHMRF; FCM algorithm; high-resolution remote sensing image segmentation

Wenjie LIN,Yu LI,Quanhua ZHAO. High-resolution Remote Sensing Image Segmentation Using Minimum Spanning Tree Tessellation and RHMRF-FCM Algorithm[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(1): 52-63.

Figures/Tables 11

Fig.1

Fig.2

Fig.3

Tab.1

Fig.4

Tab.2

Fig.5

Tab.3

Fig.6

Tab.4

Fig.7

References 25

[1]	LI Yu . Remotely sensed data segmentation under a spatial statistics framework[D]. Waterloo:University of Waterloo, 2009.
[2]	LI Deren, TONG Qingxi, LI Rongxing , et al. Current issues in high-resolution earth observation technology[J]. Science China: Earth Science, 2012,42(6):805-813.
[3]	HONG Liang . Research on the segmentation of high resolution remote sensing image based on object-oriented markovian random fields model[D]. Wuhan: Wuhan University, 2010.
[4]	ASKARI Ghasem, XU Aigong, LI Yu , et al. Automatic determination of number of homogenous regions in sar images utilizing splitting and merging based on a reversible jump MCMC algorithm[J]. Journal of the Indian Society of Remote Sensing, 2013,41(3):509-521.
[5]	WANG Yu, LI Yu, ZHAO Quanhua . SAR image segmentation combined regular tessellation and M-H algorithm[J]. Geomatics and Information Science of Wuhan University, 2016,41(11):1491-1497.
[6]	ZHAO Quanhua, LI Xiaoli, ZHAO Xuemei , et al. Fuzzy ISODATA image segmentation intergrating voronoi tessellationn HMRF model[J]. Journal of Signal Processing, 2016,32(10):1233-1243.
[7]	WANG Ping, WEI Zheng, CUI Weihong , et al. A minimum spanning tree based method for UAV image segmentation [C] //ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences. Prague: [s.n.], 2016, III-7:111-117.
[8]	LI Ying, DAI Fang, HAO Yong , et al. Image segmentation based on minimum spanning tree[J]. Computer Engineering and Applications, 2013,49(13):149-151.
[9]	PENG Bo, ZHANG Lei, ZHANG David . A survey of graph theoretical approaches to image segmentation[J]. Pattern Recognition, 2013,46(3):1020-1038.
[10]	WU Zhaocong, HU Zhongwen, ZHANG Qian , et al. On combining spectral, textural and shape features for remote sensing image segmentation[J]. Acta Geodaetica et Cartograhica Sinica, 2015,44(7):791-796.
[11]	LI Hui, TANG Yunwei, LIU Qingjie , et al. An improved algorithm based on minimum spanning tree for multi-scale segmentation of remote sensing imagery[J]. Acta Geodaetica et Cartograhica Sinica, 2015,44(7):791-796.
[12]	ZAHN Charles T . Graph-theoretical methods for detecting and describing gestalt clusters [J]. IEEE Transactions on Computers, 1971, C-20(1):68-86.
[13]	PENG Bo, ZHANG Lei, ZHANG David . A survey of graph theoretical approaches to image segmentation[J]. Pattern Recognition, 2013,46(3):1020-1038.
[14]	FELZENSZWALB Pedro F, HUTTENLOCHER Daniel P . Efficient graph-based image segmentation[J]. International Journal of Computer Vision, 2004,59(2):167-181.
[15]	ZHAO Xuemei, LI Yu, ZHAO Quanhua . Image segmentation by fuzzy clustering algorithm combining hidden markov random field and gaussian regression model[J]. Journal of Electronics & Information Technology, 2014,36(11):2730-2736.
[16]	ZHAO Quanhua, LI Xiaoli, ZHAO Xuemei , et al. Remote sensing image segmentation algorithm with regional fuzzy cluster and mahalanobis distance[J]. 2017,46(1):222-228.
[17]	LUCARINI Valerio . Symmetry-break in voronoi tessellations[J]. Symmetry, 2009,1(1):21-54.
[18]	SCHNEIDER Rolf . Weighted faces of poisson hyperplane tesslations[J]. Advances in applied probability, 2009,41(3):682-694.
[19]	ACHANTA R, SHAJI A, SMITH K , et al. SLIC superpixels compared to state-of-the-art superpixel methods[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012,34(11):2274-2282.
[20]	BANERJEE B, VARMA S, BUDDHIRAJU K M , et al. Unsupervised multi-spectral satellite image segmentation combining modified mean-shift and a new minimum spanning tree based clustering technique[J]. IEEE journal of selected topics in applied earth observations and remote sensing, 2014,7(3):888-894.
[21]	CUI Weihong, ZHANG Yi . An effective graph-based hierarchy image segmentation[J]. Intelligent Automation & Soft Computing, 2011,17(7):969-981.
[22]	NARAYAN Deepthi, MURTHY Srikanta, KUMAR G Hemantha . Image segmentation based on graph theoretical approach to improve the quality of image segmentation[J]. Proceedings of World Academy of Science Engineering & Technology, 2008: 41.
[23]	YANG Jiaxue . Research on the parallel algorithm of the minimum spanning tree on large scale graphs[D]. Shenyan: Northeastern University, 2013.
[24]	CHATZIS Storios P, VARVARIGOU Theodora A . A fuzzy clustering approach toward hidden markov random field models for enhanced spatially constrained image segmentation[J]. 2008,16(5):1351-1361.
[25]	CONGALTON Russel G, GREEN Kass. Assessing the accuracy of remotely sensed data: principles and practices [M]. Boca Raton: CRC Press, 2008: 169-190.

S	Accuracy	Homogeneous regions
S	Accuracy	Ⅰ	Ⅱ	Ⅲ	Ⅳ	Ⅴ
40	User’s	0.92	0.90	0.68	0.99	0.81
	Producer’s	0.85	0.80	0.87	0.96	0.85
	Overall	0.87
	Kappa	0.84
100	User’s	0.96	0.95	0.81	0.99	0.85
	Producer’s	0.88	0.90	0.91	0.98	0.92
	Overall	0.93
	Kappa	0.91
160	User’s	0.92	0.94	0.75	0.99	0.84
	Producer’s	0.88	0.88	0.94	0.98	0.81
	Overall	0.90
	Kappa	0.88
220	User’s	0.88	0.94	0.72	0.99	0.81
	Producer’s	0.85	0.87	0.91	0.97	0.76
	Overall	0.88
	Kappa	0.86

α	Accuracy	Homogeneous regions
α	Accuracy	Ⅰ	Ⅱ	Ⅲ	Ⅳ	Ⅴ
0.9	User’s	0.94	0.94	0.80	0.99	0.84
	Producer’s	0.89	0.89	0.89	0.98	0.91
	Overall	0.91
	Kappa	0.90
0.8	User’s	0.96	0.95	0.83	0.99	0.85
	Producer’s	0.88	0.90	0.92	0.98	0.92
	Overall	0.93
	Kappa	0.91
0.7	User’s	0.95	0.93	0.82	0.99	0.93
	Producer’s	0.95	0.90	0.89	0.98	0.91
	Overall	0.92
	Kappa	0.90

γ	Accuracy	Homogeneous regions
γ	Accuracy	Ⅰ	Ⅱ	Ⅲ	Ⅳ	Ⅴ
0.1	User’s	0.96	0.95	0.83	0.99	0.85
	Producer’s	0.88	0.90	0.92	0.98	0.92
	Overall	0.93
	Kappa	0.91
0.2	User’s	0.86	0.91	0.89	0.98	0.92
	Producer’s	0.95	0.93	0.81	0.99	0.85
	Overall	0.92
	Kappa	0.90
0.3	User’s	0.86	0.89	0.87	0.98	0.90
	Producer’s	0.95	0.93	0.77	0.99	0.82
	Overall	0.91
	Kappa	0.89

Methods	Accuracy		Homogeneous regions
Methods	Accuracy		Ⅰ		Ⅱ		Ⅲ		Ⅳ		Ⅴ
The proposed		User’s		0.96		0.95		0.83		0.99		0.85
		Producer’s		0.88		0.90		0.92		0.98		0.92
		Overall		0.93
		Kappa		0.91
eCognition multi-solution		User’s		0.93		0.73		0.51		0.99		0.63
		Producer’s		0.59		0.81		0.64		0.94		0.72
		Overall		0.77
		Kappa		0.72
eCognition watershed		User’s		0.87		0.79		0.53		0.99		0.69
		Producer’s		0.75		0.81		0.69		0.94		0.67
		Overall		0.80
		Kappa		0.75