多核CPU下的K-means遥感影像分类并行方法

doi:10.11772/j.issn.1001-9081.2015.05.1296

计算机应用 ›› 2015, Vol. 35 ›› Issue (5): 1296-1301.DOI: 10.11772/j.issn.1001-9081.2015.05.1296

多核CPU下的K-means遥感影像分类并行方法

吴洁璇, 陈振杰, 张云倩, 骈宇哲, 周琛

江苏省地理信息技术重点实验室(南京大学), 南京 210023

收稿日期:2014-12-15 修回日期:2015-01-11 发布日期:2015-05-14 出版日期:2015-05-10
通讯作者: 陈振杰
作者简介:吴洁璇(1991-),女,浙江台州人,硕士研究生,主要研究方向:高性能地理计算、数据挖掘; 陈振杰(1974-),男,陕西宝鸡人,副教授,博士,主要研究方向:GIS算法、高性能地理计算; 张云倩(1992-),女,江苏扬州人,硕士研究生,主要研究方向:空间数据挖掘;骈宇哲(1989-),男,陕西铜川人,硕士研究生,主要研究方向:高性能地理计算; 周琛(1990-),男,江苏宿迁人,博士研究生,主要研究方向:高性能地理计算.
基金资助:
国家863计划项目(2011AA120301);国家科技支撑计划项目(2012BAH28B02).

Utilizing multi-core CPU to accelerate remote sensing image classification based on K-means algorithm

WU Jiexuan, CHEN Zhenjie, ZHANG Yunqian, PIAN Yuzhe, ZHOU Chen

Jiangsu Provincial Key Laboratory of Geographic Information Science and Technology (Nanjing University), Nanjing Jiangsu 210023, China

Received:2014-12-15 Revised:2015-01-11 Online:2015-05-14 Published:2015-05-10

摘要/Abstract

摘要：

针对海量遥感影像快速分类的应用需求,提出一种基于K-means算法的遥感影像并行分类方法.该方法结合CPU下进程级与线程级模式的并行特征,设计融合进程级与线程级并行的两阶段数据粒度划分方法和任务调度方法,在保证精度的基础上实现并行加速.利用大数据量的多尺度遥感影像进行实验,结果表明:所提并行方法可大大减少遥感影像的分类时间,取得了良好的加速比(13.83),并可达到负载均衡,从而解决了大区域遥感影像快速分类的问题.

关键词: K-means算法, 并行计算, 负载均衡, 数据粒度划分, 消息传递接口, OpenMP

Abstract:

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.

Key words: K-means algorithm, parallel computing, load balancing, data granularity decomposition, Message Passing Interface (MPI), Open Multi-Processing (OpenMP)

中图分类号:

TP751

吴洁璇, 陈振杰, 张云倩, 骈宇哲, 周琛. 多核CPU下的K-means遥感影像分类并行方法[J]. 计算机应用, 2015, 35(5): 1296-1301.

WU Jiexuan, CHEN Zhenjie, ZHANG Yunqian, PIAN Yuzhe, ZHOU Chen. Utilizing multi-core CPU to accelerate remote sensing image classification based on K-means algorithm[J]. Journal of Computer Applications, 2015, 35(5): 1296-1301.

参考文献

[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.

多核CPU下的K-means遥感影像分类并行方法

Utilizing multi-core CPU to accelerate remote sensing image classification based on K-means algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张润莲, 张密, 武小年, 舒瑞. 基于GPU的大状态密码S盒差分性质评估方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2785-2790.
[2]	张明, 付乐, 王海峰. 面向边缘计算的并发数据流接转控制模型[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3876-3883.
[3]	孙亚男, 吴杰宏, 石峻岭, 高利军. 改进自组织映射的多无人机协同任务分配方法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1551-1556.
[4]	龙运波, 唐聃. 分布式存储中基于局部修复码的负载均衡方法[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 767-775.
[5]	杨力, 陈建廷, 向阳. 基于HBase的工业时序大数据分布式存储性能优化策略[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 759-766.
[6]	刘乾, 张洋铭, 万定生. 网格化分布式新安江模型并行计算算法[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3327-3333.
[7]	姜松岩, 廖晓鹃, 陈光柱. 基于可满足性模理论的多处理机通信延迟优化任务调度方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 185-191.
[8]	蔡婧雯, 韦永壮, 刘争红. 基于GPU的密码S盒代数性质评估方法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2750-2756.
[9]	邱鑫源, 叶泽聪, 崔翛龙, 高志强. 联邦学习通信开销研究综述[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 333-342.
[10]	徐启迪, 刘争红, 郑霖. 基于GPU的低密度奇偶校验码译码加速技术[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3841-3846.
[11]	高旗, 吕娜, 缪竞成. 基于负载均衡的无线虚拟网络映射算法[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3148-3153.
[12]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[13]	许红亮, 杨桂芹, 蒋占军. 基于软件定义网络的数据中心自适应多路径负载均衡算法[J]. 计算机应用, 2021, 41(4): 1160-1164.
[14]	解文博, 韦永壮, 刘争红. 基于CUDA的SKINNY加密算法并行实现与分析[J]. 计算机应用, 2021, 41(4): 1136-1141.
[15]	杨先凤, 贵红军, 傅春常. 统一计算设备架构下的F-X域预测滤波并行算法[J]. 计算机应用, 2021, 41(2): 486-491.