Concerning the application requirements for the fast classification of large-scale remote sensing images, a parallel classification method based on K-means algorithm was proposed. Combined the CPU process-level and thread-level parallelism features, reasonable strategies of data granularity decomposition and task scheduling between processes and threads were implemented. This algorithm can achieve satisfactory parallel acceleration while ensuring classification accuracy. The experimental results using large-volume and multi-scale remote sensing images show that: the proposed parallel algorithm can significantly reduce the classification time, get good speedup with the maximum value of 13.83, and obtain good load-balancing. Thus it can solve the remote sensing image classification problems of the large area.
[1] JIA K, LI Q, TIAN Y, et al.A review of classification methods of remote sensing imagery[J]. Spectroscopy and Spectral Analysis, 2011, 31(10): 2618-2623.(贾坤,李强子,田亦陈,等. 遥感影像分类方法研究进展[J]. 光谱学与光谱分析,2011,31(10):2618-2623.) [2] HARTIGAN J A, WONG M A. Algorithm AS 136: a K-means clustering algorithm[J]. Applied Statistics, 1979, 28(1): 100-108. [3] ZHAO Y, ZHOU P. An improved K-means algorithm for remote sensing classification[J].Remote Sensing for Land and Resources, 2011(2): 87-90.(赵越, 周萍. 改进的 K-means 算法在遥感图像分类中的应用[J]. 国土资源遥感, 2011(2): 87-90.) [4] ZHANG W, GU X, CHEN L, et al. An algorithm for initializing of K-means clustering based on mean-standard deviation[J].Journal of Remote Sensing, 2006, 10(5): 715-721.(张文君, 顾行发, 陈良富, 等. 基于均值-标准差的K均值初始聚类中心选取算法[J]. 遥感学报, 2006, 10(5): 715-721.) [5] KANUNGO T, MOUNT D M, NETANYAHU N S, et al. An efficient K-means clustering algorithm: Analysis and implementation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(7): 881-892. [6] JU H, ZHANG J,LI C, et al. Automated remote sensing image classification method based on K-means and SVM[J]. Application Research of Computers, 2007, 24(11): 318-320.(居红云, 张俊本, 李朝峰, 等. 基于 K-means与SVM 结合的遥感图像全自动分类方法[J]. 计算机应用研究, 2007, 24(11): 318-320.) [7] ZHANG T. Remote sensing image classification utilizing K-means and SOM[J].Geospatial Information, 2011, 9(1):109-112.(张涛. 一种利用K均值和 SOM 进行遥感图像分类的方法[J]. 地理空间信息, 2011, 9(1):109-112.) [8] QIN C, ZHAN L, ZHU A, et al. A strategy for raster-based geocomputation under different parallel computing platforms[J]. International Journal of Geographical Information Science, 2014, 28(11):2127-2144. [9] GüRSOY A, CENGIZ I. Parallel pruning for K-means clustering on shared memory architectures[C]// Euro-Par 2001: Proceedings of the 7th International Euro-Par Conference. Heidelberg: Springer, 2001: 321-325. [10] BLIKBERG R, SØREVIK T. Load balancing and OpenMP implementation of nested parallelism[J]. Parallel Computing, 2005, 31(10): 984-998. [11] JIN H, JESPERSEN D, MEHROTRA P, et al. High performance computing using MPI and OpenMP on multi-core parallel systems[J]. Parallel Computing, 2011, 37(9): 562-575. [12] GURSOY A. Data decomposition for parallel K-means clustering[C]// Proceedings of the 2004 International Conference on Parallel Processing and Applied Mathematics, LNCS 23019. Heidelberg: Springer, 2004: 241-248. [13] JIANG L, LIU D. Research on K-means clustering parallel algorithm of remote sensing image[J].Remote Sensing Information, 2008(1): 27-30.(蒋利顺, 刘定生. 遥感图像 K-means 并行算法研究[J]. 遥感信息, 2008(1): 27-30.) [14] LYU Z, HU Y, ZHONG H, et al. Parallel K-means clustering of remote sensing images based on MapReduce[C]// Proceedings of the 2010 International Conference on Web Information Systems and Mining, LNCS 26318. Heidelberg: Springer, 2010: 162-170. [15] ZHAO W, MA H, HE Q. Parallel K-means clustering based on MapReduce[C]// Proceedings of the 1st International Conference on Cloud Computing. Heidelberg: Springer, 2009: 674-679. [16] NAKAJIMA K. Three-level hybrid vs. flat MPI on the earth simulator: Parallel iterative solvers for finite-element method[J]. Applied Numerical Mathematics, 2005, 54(2): 237-255. [17] BULL J M, ENRIGHT J, GUO X, et al. Performance evaluation of mixed-mode OpenMP/MPI implementations[J]. International Journal of Parallel Programming, 2010, 38(5/6): 396-417. [18] SHEKHAR S, RAVADA S, CHUBB D, et al. Declustering and load-balancing methods for parallelizing geographic information systems[J]. IEEE Transactions on Knowledge and Data Engineering, 1998, 10(4): 632-655. [19] WANG S, COWLES M K, ARMSTRONG M P. Grid computing of spatial statistics: using the TeraGrid for g(i)*(d) analysis[J]. Concurrency and Computation: Practice and Experience, 2008, 20(14): 1697-1720. [20] GUAN Q, CLARKE K C. A general-purpose parallel raster processing programming library test application using a geographic cellular automata model[J]. International Journal of Geographical Information Science, 2010, 24(5): 695-722. [21] WANG S, ARMSTRONG M P. A quadtree approach to domain decomposition for spatial interpolation in grid computing environments[J]. Parallel Computing, 2003, 29(10): 1481-1504. [22] LIU J, ZHU A, QIN C. Estimation of theoretical maximum speedup ratio for parallel computing of grid-based distributed hydrological models[J]. Computers and Geosciences, 2013, 60: 58-62. [23] XIE J. Implementation and performance optimization of a parallel contour line generation algorithm[J]. Computers and Geosciences, 2012, 49: 21-28.
2015, Vol. 35 
