A GPU-Based Parallel Algorithm for Landscape Metrics

ZHONG Aini; CHANG Lijun; MA Yunlong; KANG Mengjun; MAO Ziyuan

doi:10.13203/j.whugis20190095

Volume 45 Issue 6

Jun. 2020

Turn off MathJax

Article Contents

Abstract

References

Geomatics and Information Science of Wuhan University > 2020 > 45(6): 941-948. > DOI: 10.13203/j.whugis20190095

ZHONG Aini, CHANG Lijun, MA Yunlong, KANG Mengjun, MAO Ziyuan. A GPU-Based Parallel Algorithm for Landscape Metrics[J]. Geomatics and Information Science of Wuhan University, 2020, 45(6): 941-948. DOI: 10.13203/j.whugis20190095

Citation:

PDF (4332 KB)

A GPU-Based Parallel Algorithm for Landscape Metrics

ZHONG Aini^{1, 2,},
CHANG Lijun¹,
MA Yunlong^{1, 2},
KANG Mengjun^{1, 2, ,},
MAO Ziyuan¹

1.
School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079, China
2.
Institute of Smart Perception and Intelligent Computing, Wuhan University, Wuhan 430079, China

Funds: The National Key Research and Development Program of China(2017YFB0503500).

More Information

Author Bio:
ZHONG Aini, master, majors in geographic information processing and visualization.ainy_zhong@whu.edu.cn
Corresponding author:
KANG Mengjun ,PhD, associate professor. E-mail:mengjunk@whu.edu.cn
Received Date: April 06, 2019
Published Date: June 04, 2020

Graphical Abstract

Abstract

Abstract

Massive spatial data poses increasing challenges to traditional analysis software. For example, landscape pattern analysis software FRAGSTATS has been unable to process provincial-level high-resolution land cover data. Based on Two-Pass connected component labeling algorithm, this paper provides an improved parallel algorithm with GPU programming to solve the landscape metrics computation problem about massive land use data. This parallel algorithm for massive landscape metrics calculation takes full advantage of a general computer, and focuses on patch perimeter and area calculation. It can also accelerate computation speed by multithreading and iteration times reduction to decrease computation time than traditional serial algorithms. We apply the proposed algorithm and serial algorithm to calculate landscape metrics of the land use classification raster images at different resolutions under patch scale.The experiment result shows great improvement of calculation performance of landscape metrics, and the efficiency has been improved by 5 times comparing with the serial algorithm, which proves that our proposed algorithm is a better choice for landscape analysis of massive data.
- connected component labeling algorithm,
- landscape metrics,
- graphics processing unit（GPU）,
- parallel computing

FullText(HTML)

References (26)

References

[1]	彭建, 王仰麟, 张源,等. 土地利用分类对景观格局指数的影响[J]. 地理学报, 2006, 61(2):47-58 http://d.old.wanfangdata.com.cn/Periodical/dlxb200602005 Peng Jian, Wang Yanglin, Zhang Yuan, et al. Research on the Influence of Land Use Classification on Landscape Metrics[J]. Acta Geographica Sinica, 2006, 61(2):47-58 http://d.old.wanfangdata.com.cn/Periodical/dlxb200602005
[2]	陈文波, 肖笃宁, 李秀珍. 景观指数分类、应用及构建研究[J]. 应用生态学报, 2002, 13(1):121-125 doi: 10.3321/j.issn:1001-9332.2002.01.027 Chen Wenbo, Xiao Duning, Li Xiuzhen. Classification, Application, and Creation of Landscape Indices[J]. Chinese Journal of Applied Ecology, 2002, 13(1):121-125 doi: 10.3321/j.issn:1001-9332.2002.01.027
[3]	刘家福, 王平, 李京, 等. 土地利用格局景观指数算法与应用[J]. 地理与地理信息科学, 2009, 25(1):107-109 http://d.old.wanfangdata.com.cn/Periodical/dlxygtyj200901028 Liu Jiafu, Wang Ping, Li Jing, et al. An Algorithm for Land-Use Pattern Index and Its Application[J]. Geography and Geo-information Science, 2009, 25(1):107-109 http://d.old.wanfangdata.com.cn/Periodical/dlxygtyj200901028
[4]	罗名海, 蒋子龙, 程琦, 等. 地理国情在武汉市土地资源承载力评价中的应用[J]. 武汉大学学报·信息科学版, 2018, 43(12):2317-2324 doi: 10.13203/j.whugis20180389 Luo Minghai, Jiang Zilong, Chen Qi, et al. Carrying Capacity Evaluation of Land Resources in Wuhan Based on the Geographical Condition Monitoring[J]. Geomatics and Information Science of Wuhan University, 2018, 43(12):2317-2324 doi: 10.13203/j.whugis20180389
[5]	Mcgarigal K S, Cushman S, Neel M, et al. FRAGSTATS:Spatial Pattern Analysis Program for Categorical Maps[OL].http://www.umass.edu/landeco/research/fragstats/fragstats.html, 2002
[6]	Dillencourt M B, Samet H, Tamminen M. A General Approach to Connected-Component Labelling for Arbitrary Image Representations[J]. Journal of the ACM, 1992, 39(2):253-280 doi: 10.1145/128749.128750
[7]	Christophe F, Jens G. Two Linear Time Union-Find Strategies for Image Processing[J].Theoretical Computer Science, 1996, 154(2):165-181 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=8c93f9f1d9c94d7b538da10fa7ac1274
[8]	Chang Fu, Chen Chunjen, Lu Chijen. A Linear-Time Component-Labeling Algorithm Using Contour Tracing Technique[J]. Computer Vision and Image Understanding, 2004, 93(2):206-220 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=3e1c9d3e432f10bdbd28e750d1ceda6b
[9]	Wu K, Otoo E, Suzuki K. Optimizing Two-Pass Connected-Component Labeling Algorithms[J]. Pattern Analysis & Applications, 2009, 12(2):117-135 http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0211764717/
[10]	He L, Ren X, Gao Q, et al. The Connected-Component Labeling Problem:A Review of State-of-the-Art Algorithms[J]. Pattern Recognition, 2017, 70:25-43 doi: 10.1016/j.patcog.2017.04.018
[11]	Manohar M, Ramapriyan H K. Connected Component Labeling of Binary Images on a Mesh Connected Massively Parallel Processor[J]. Computer Vision Graphics & Image Processing, 1989, 45(2):133-149 https://www.sciencedirect.com/science/article/abs/pii/0734189X89901291
[12]	Celebi M E. A Simple and Efficient Algorithm for Connected Component Labeling in Color Images[C]. SPIE Electronic Imaging Conference, San Francisco, California, USA,2012
[13]	Zhao Xiao,He Lifeng, Yao Bin, et al. A New Connected-Component Labeling Algorithm[J]. IEICE Transactions on Information & Systems, 2015, 98(11):2013-2016 https://www.researchgate.net/publication/324927491_A_New_Connected-Component_Labeling_Algorithm
[14]	沈夏炯, 王晶晶, 范家铭,等. MGSI-8CA标记算法[J]. 计算机工程与应用, 2013, 49(20):126-139 doi: 10.3778/j.issn.1002-8331.1303-0116 Shen Xiajiong, Wang Jingjing, Fan Jiaming, et al. Labeling Algorithm of 8-Adjacent Connecting Area for Massive Gray Scale Images[J]. Computer Engineering and Applications, 2013, 49(20):126-139 doi: 10.3778/j.issn.1002-8331.1303-0116
[15]	Gupta S, Palsetia D, Agrawal A, et al. A New Parallel Algorithm for Two-Pass Connected Component Labeling[C]. 28th IEEE International Parallel & Distributed Processing Symposium, Phoenix,Arizona, USA,2014
[16]	马益杭, 占利军, 谢传节, 等. 连通域标记算法的并行化研究[J]. 地理与地理信息科学, 2013, 29(4):67-71 http://d.old.wanfangdata.com.cn/Periodical/dlxygtyj201304015 Ma Yihang, Zhan Lijun, Xie Chuanjie, et al.Parallelization of Connected Component Labeling Algorithm[J]. Geography and Geo-information Science, 2013, 29(4):67-71 http://d.old.wanfangdata.com.cn/Periodical/dlxygtyj201304015
[17]	刘洋, 关庆锋. 景观指数的并行计算方法[J]. 地球信息科学学报, 2017, 19(4):457-466 http://d.old.wanfangdata.com.cn/Periodical/dqxxkx201704003 Liu Yang, Guan Qingfeng. A Parallel Algorithm for Landscape Metrics[J]. Journal of Geo-information Science, 2017, 19(4):457-466 http://d.old.wanfangdata.com.cn/Periodical/dqxxkx201704003
[18]	关雪峰, 曾宇媚. 时空大数据背景下并行数据处理分析挖掘的进展及趋势[J]. 地理科学进展, 2018, 37(10): 1314-1327 http://d.old.wanfangdata.com.cn/Periodical/dlkxjz201810002 Guan Xuefeng, Zeng Yumei. Research Progress and Trends of Parallel Processing, Analysis, and Mining of Big Spatiotemporal Data[J]. Progress in Geography, 2018, 37(10):1314-1327 http://d.old.wanfangdata.com.cn/Periodical/dlkxjz201810002
[19]	杨靖宇, 张永生, 李正国,等. 遥感影像正射纠正的GPU-CPU协同处理研究[J]. 武汉大学学报·信息科学版, 2011, 36(9):1043-1046 http://ch.whu.edu.cn/article/id/645 Yang Jinyu, Zhang Yongsheng, Li Zhengguo, et al. GPU-CPU Cooperate Processing of RS Image Ortho-Rectification[J]. Geomatics and Information Science of Wuhan University, 2011, 36(9):1043-1046 http://ch.whu.edu.cn/article/id/645
[20]	董路明, 张斌, 赵学胜. 一种基于GPU Tessellation的地形无缝绘制算法[J]. 武汉大学学报·信息科学版, 2017, 42(3):402-407 doi: 10.13203/j.whugis20140850 Dong Luming, Zhang Bin, Zhao Xuesheng. A Seamless Terrain Rendering Algorithm Based on GPU Tessellation[J]. Geomatics and Information Science of Wuhan University, 2017, 42(3):402-407 doi: 10.13203/j.whugis20140850
[21]	刘金硕, 李扬眉, 江庄毅, 等. 基于PMVS算法的大规模数据细粒度并行优化方法[J]. 武汉大学学报·信息科学版, 2019, 44(4):608-616 doi: 10.13203/j.whugis20160186 Liu Jinshuo, Li Yangmei, Jiang Zhuangyi,et al. Fine-Grained Parallel Optimization of Large-Scale Data for PMVS Algorithm[J]. Geomatics and Information Science of Wuhan University, 2019, 44(4):608-616 doi: 10.13203/j.whugis20160186
[22]	Hawick K A, Leist A, Playne D P. Parallel Graph Component Labelling with GPUs and CUDA[J]. Parallel Computing, 2010, 36(12):655-678 doi: 10.1016/j.parco.2010.07.002
[23]	Kalentev O, Rai A, Kemnitz S, et al. Connected Component Labeling on a 2D Grid Using CUDA[J]. Journal of Parallel & Distributed Computing, 2011, 71(4):615-620 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=8a541419c1bfc05cda81b66bfec27cdf
[24]	Komura Y. A Generalized GPU-Based Connected Component Labeling Algorithm[J]. Journal of the Association for Computing Machinery, 2016, 39(2):253-280 https://www.researchgate.net/publication/299462450_A_generalized_GPU-based_connected_component_labeling_algorithm
[25]	覃方涛, 房斌. GPU加速的二值图连通域标记并行算法[J]. 计算机应用, 2010, 30(10):2774-2786 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=jsjyy201010057 Qin Fangtao, Fang Bin. GPU Accelerated Parallel Labeling Algorithm of Connected-Domains in Binary Images[J]. Journal of Computer Applications, 2010, 30(10):2774-2786 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=jsjyy201010057
[26]	王泽寰, 赖俊杰. 一种改进的图像连通区域标记的并行算法及其在GPU上的实现[C].全国高性能计算学术年会,广州,2014 Wang Zehuan, Lai Junjie. An Improved Parallel Connected Component Labeling Algorithm and Its GPU Implementation[C].HPC China, Guangzhou, China,2014

[1]	LONG En, LÜ Shouye, QU Xiaofei, MENG Gang, LAI Guangling, YANG Yuke. Height Inversion Model of Oil Tank Using Satellite Imagery with Same Name Arc Distance[J]. Geomatics and Information Science of Wuhan University, 2024, 49(3): 411-418. DOI: 10.13203/j.whugis20210239
[2]	LÜ Pinji, LI Zhengyuan, SUN Lingli, LIN Jun, TANG Lei, NI Yipeng. Analysis of Impact of the Tonga Volcanic Eruption in 2022 on the Strain Observation of Chinese Mainland[J]. Geomatics and Information Science of Wuhan University, 2022, 47(6): 927-933. DOI: 10.13203/j.whugis20220174
[3]	LEI Xiangxu, SANG Jizhang, LI Zhenwei, CHEN Junyu, DU Jianli, HE Donglei. Association of Very-Short-Arc Angles Data for LEO Space Objects[J]. Geomatics and Information Science of Wuhan University, 2020, 45(10): 1526-1532. DOI: 10.13203/j.whugis20180386
[4]	LOU Yidong, YAO Xiuguang, LIU Yang, ZHENG Fu. Impact of Ambiguity Resolution and Arc Length on Regional Precise Orbit Determination[J]. Geomatics and Information Science of Wuhan University, 2016, 41(2): 249-254. DOI: 10.13203/j.whugis20140201
[5]	LIU Xiaoxia, JIANG Zaisen, WU Yanqiang. The Applicability of Kriging Interpolation Method in GPSVelocity Gridding and Strain Calculating[J]. Geomatics and Information Science of Wuhan University, 2014, 39(4): 457-461. DOI: 10.13203/j.whugis20120086
[6]	WU Yanqiang, JIANG Zaisen, YANG Guohua, FANG Ying. Application and Method of GPS Strain Calculating in Whole Mode Using Multi-Surface Function[J]. Geomatics and Information Science of Wuhan University, 2009, 34(9): 1085-1089.
[7]	DING Kaihua, XU Cajjun. Current Crustal Strain Field in the Sichuan-Yunnan Area by Joint Inversion of GPS and Seismic Moment Tensor[J]. Geomatics and Information Science of Wuhan University, 2009, 34(3): 265-268.
[8]	ZHU Xinhui, SUN Fuping, QIN Yong. Establishment of Plate Motion Model by the Integrated Data of GPS and VLBI[J]. Geomatics and Information Science of Wuhan University, 2005, 30(7): 604-608.
[9]	DU Ruilin, QIAO Xuejun, YANG Shaomin, WANG Qi. Results of the Crustal Deformation by GPS Survey and Horizontal Strain Rate Fields in the Three Gorges Area[J]. Geomatics and Information Science of Wuhan University, 2004, 29(9): 768-771.
[10]	Zhang Zuxun, Bao Xiuzhi, Cao Hui. Arc Spline and Arclet Processing[J]. Geomatics and Information Science of Wuhan University, 1994, 19(3): 189-193.

Cited By

Cited by

Periodical cited type(5)

1.	黄少华，万永革，冯淦，李枭，关兆萱. 2022年9月17日中国台湾地震序列的触发机制及其动力学成因. 地质力学学报. 2023(05): 674-684 .
2.	李之诺，卢佳遇，高锐，陈致同. 斜向聚合及弧后伸展作用对台湾北部-琉球地区的构造影响——砂箱模型实验的启示. 地球学报. 2022(05): 609-615 .
3.	李建涛，刚慧龙. 基于ITRF14框架的URCORS坐标分析. 工程勘察. 2022(10): 62-66 .
4.	高源，瞿伟，张勤，王庆良，郝明. GNSS揭示的汾渭盆地及周缘现今地壳运动与应变差异. 武汉大学学报(信息科学版). 2021(07): 1063-1070+1113 .
5.	徐良叶，邵德盛，吴学群，牛甜. 最小二乘配置的云南区域形变与应变特征研究. 测绘科学. 2021(12): 16-23+74 .

Other cited types(4)

Get Citation

PDF

XML

Article views (1404) PDF downloads (70) Cited by(9)

A GPU-Based Parallel Algorithm for Landscape Metrics

Abstract

References

Related Articles

Cited by

Periodical cited type(5)

Other cited types(4)

Catalog

Related

A GPU-Based Parallel Algorithm for Landscape Metrics

Abstract

References

Related Articles

Cited by

Periodical cited type(5)

Other cited types(4)

Catalog

Related

Export File

Citation

Format

Content