Parallel algorithm for hillshading under multi-core computing environment

doi:10.11772/j.issn.1001-9081.2017.07.1911

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (7): 1911-1915.DOI: 10.11772/j.issn.1001-9081.2017.07.1911

Previous Articles Next Articles

Parallel algorithm for hillshading under multi-core computing environment

HAN Litao^1,2, LIU Hailong¹, KONG Qiaoli^1,3, YANG Fanlin^1,2

1. College of Geomatics, Shandong University of Science and Technology, Qingdao Shandong 266590, China;
2. Key Laboratory of Surveying and Mapping Technology on Island and Reed, National Administration of Surveying, Mapping and Geoinformation(Shandong University of Science and Technology), Qingdao Shandong 266590, China;
3. Engineering Laboratory of Spatial Information Technology of Highway Geological Disaster Early Warning in Hunan Province(Changsha University of Science & Technology), Changsha Hunan 410004, China

Received:2017-02-08 Revised:2017-03-06 Online:2017-07-10 Published:2017-07-18
Supported by:
his work is partially supported by the National Natural Science Foundation of China (41201381, 41376108), the Open Fund of Engineering Laboratory of Spatial Information Technology of Highway Geological Disaster Early Warning in Hunan Province (kfj150605).

基于多核计算环境的地貌晕渲并行算法

韩李涛^1,2, 刘海龙¹, 孔巧丽^1,3, 阳凡林^1,2

1. 山东科技大学测绘科学与工程学院, 山东青岛 266590;
2. 海岛(礁)测绘技术国家测绘地理信息局重点实验室(山东科技大学), 山东青岛 266590;
3. 公路地质灾变预警空间信息技术湖南省工程实验室(长沙理工大学), 长沙 410004

通讯作者: 韩李涛
作者简介:韩李涛(1978-),男,山东菏泽人,副教授,博士,主要研究方向:虚拟地理环境、空间信息可视化;刘海龙(1995-),男,山东菏泽人,硕士研究生,主要研究方向:地理信息系统;孔巧丽(1979-),女,山东菏泽人,讲师,博士,主要研究方向:全球定位与导航;阳凡林(1974-),男,湖北荆州人,教授,博士,主要研究方向:海洋测绘、海洋GIS。
基金资助:
国家自然科学基金资助项目（41201381，41376108）；公路地质灾变预警空间信息技术湖南省工程实验室开放基金资助项目（kfj150605）。

Abstract

Abstract: Most of the exiting hillshading algorithms are implemented based on single-core single-thread programming model, which makes them have lower computational efficiency. To solve this problem, an improved algorithm for parallelizing the existing hillshading algorithms based on multi-core programming model was proposed. Firstly, the original Digital Elevation Model (DEM) data were divided into several data blocks by grid segmentation. Secondly, these data blocks were shaded in parallel using the class Parallel under the .Net environment to generate shaded image of each block. Finally, the shaded images were spliced into a complete hillshading image. The experimental results show that the calculation efficiency of the improved parallelized algorithm is obviously higher than that of the existing shading algorithms based on single-core single-thread programming, and there is an approximate linear growth relation between the number of the involved cores and the shading efficiency. Additionally, it is also found that the three dimensional and realistic effect of the hillshading image is extremely relevant to the parameter setting of the light source.

Key words: multi-core environment, Digital Elevation Model (DEM), hillshading, parallel computing, data segmentation, image mosaic

摘要： 针对现有地貌晕渲算法多是基于单核单线程编程模式从而导致计算效率较低的问题，提出利用多核并行计算模式对现有地貌晕渲算法进行并行化改进。首先，通过格网分割方式对原始数字高程模型（DEM）数据进行分割从而实现数据分块；其次，利用.NET环境下的Parallel类对分块数据进行并行晕渲处理，得到各个分块数据的晕渲结果；最后，对各个分块数据的晕渲图像进行拼接，从而得到完整的地貌晕渲图像。实验结果表明：并行化改进算法的计算效率明显高于现有单核单线程地貌晕渲算法，且参与计算核数与晕渲效率基本上呈线性增长关系；同时，分析发现地貌晕渲的立体真实感与光源参数的设置极其相关。

关键词: 多核环境, 数字高程模型, 地貌晕渲, 并行计算, 数据分块, 图像拼接

CLC Number:

P283.3
TP391

HAN Litao, LIU Hailong, KONG Qiaoli, YANG Fanlin. Parallel algorithm for hillshading under multi-core computing environment[J]. Journal of Computer Applications, 2017, 37(7): 1911-1915.

韩李涛, 刘海龙, 孔巧丽, 阳凡林. 基于多核计算环境的地貌晕渲并行算法[J]. 计算机应用, 2017, 37(7): 1911-1915.

References

[1] 张玲,杨晓平,魏占玉,等.三维数据的二维可视化方法综述[J].地震地质,2014,36(1):275-284.(ZHANG L, YANG X P, WEI Z Y, et al. Overview of visualization methods of three dimensional topographic data[J]. Seismology and Geology, 2014, 36(1):275-284.)
[2] 王少荣,陈星宇,徐秋红.基于曲率的小比例尺地貌晕渲图生成方法[J].计算机应用与软件,2015,32(7):204-206.(WANG S R, CHEN X Y, XU Q H. Generation method of small-scale relief shading based on curvature[J]. Computer Applications and Software, 2015, 32(7):204-206.)
[3] 李少梅,阚映红,陈艳丽,等.数字地貌晕渲光照模型研究[J].测绘科学技术学报,2010,27(1):57-60.(LI S M, KAN Y H, CHEN Y L, et al. Research on illumination model of digital relief shading[J]. Journal of Geomatics Science and Technology, 2010, 27(1):57-60.)
[4] 丁宇萍,蒋球伟.地貌晕渲图的生成原理与实现[J].计算机应用与软件,2011,28(9):214-216.(DING Y P, JIANG Q W. Hill shading map generation principles and realization[J]. Computer Applications and Software, 2011, 28(9):214-216.)
[5] VERONESI F, HURNI L. A GIS tool to increase the visual quality of relief shading by automatically changing the light direction[J]. Computers & Geosciences, 2015, 74:121-127.
[6] 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.
[7] GEPNER P, KOWALIK M F. Multi-core processors:new way to achieve high system performance[C]//PARELEC 2006:Proceedings of the 2006 International Symposium on Parallel Computing in Electrical Engineering. Washington, DC:IEEE Computer Society, 2006:9-13.
[8] ZHANG S H, XIA Z X, YUAN R, et al. Parallel computation of a dam-break flow model using OpenMP on a multi-core computer[J]. Journal of Hydrology, 2014, 512:126-133.
[9] ZHOU G Y, LIU X L, FU S H, et al. Parallel identification and filling of depressions in raster digital elevation models[J/OL]. International Journal of Geographical Information Science, 2016:1-18[2017-01-10]. http://dx.doi.org/10.1080/13658816.2016.1262954.
[10] YILDIRIM A A, WATSON D, TARBOTON D, et al. A virtual tile approach to raster-based calculations of large digital elevation models in a shared-memory system[J]. Computers & Geosciences, 2015, 82:78-88.
[11] SHARMA R, XU Z W, SUGUMARAN R, et al. Parallel landscape driven data reduction & spatial interpolation algorithm for big LiDAR data[J/OL]. ISPRS International Journal of Geo-Information, 2016, 5(6):97:1-14[2016-10-15]. http://dx.doi.org/10.3390/ijgi5060097.
[12] YANG J H, ZHANG J X. Parallel performance of typical algorithms in remote sensing-based mapping on a multi-core computer[J]. Photogrammetric Engineering & Remote Sensing, 2015, 81(5):373-385.
[13] 陈艳丽,陈欣,魏兰.数字地貌晕渲光源的设置和应用研究[J].测绘与空间地理信息,2016,39(1):91-93.(CHEN Y L, CHEN X, WEI L. The research on setting and application of light sources of digital relief shading[J]. Geomatics & Spatial information Technology, 2016, 39(1):91-93.)
[14] 王宗跃,马洪超,徐宏根,等.在集群多核CPU环境下的等高线并行提取方法[J].计算机工程与应用,2010,46(17):5-7.(WANG Z Y, MA H C, XU H G, et al. Method of parallel contours extraction based on multi-core CPU[J]. Computer Engineering and Application, 2010, 46(17):5-7.)
[15] 徐昕.基于单机多核格网DEM填洼并行算法的研究与实现[J].城市地理,2015(24):96-97.(XU X. Research and implementation of parallel algorithm filling grid DEM based on multi-core computer[J]. Cultural Geography, 2015(24):96-97.)
[16] 陈景广,佘江峰,宋晓群,等.基于多核CPU的大规模DEM并行三维晕渲[J].武汉大学学报(信息科学版),2013,38(5):618-621.(CHEN J G, SHE J F, SONG X Q, et al. Parallel rendering of large-scale DEM based on multi-core CPU[J]. Geomatics and Information Science of Wuhan University, 2013, 38(5):618-621.)
[17] 黄先锋,孙岩标,张帆,等.多核计算环境下的LiDAR数据DEM内插方法研究[J].山东科技大学学报(自然科学版),2011,30(1):1-6.(HUANG X F, SUN Y B, ZHANG F, et al. Research on DEM interpolation method with Lidar data under multi-core computing environment[J]. Journal of Shandong University of Science and Technology (Natural Science), 2011, 30(1):1-6.)
[18] 王顺绪.多核计算机上并行计算的实现与分析[J].淮海工学院学报(自然科学版),2009,18(3):30-33.(WANG S X. Implementation and analyses of parallel computation on multi-core computers[J]. Journal of Huaihai Institute of Technology (Natural Science Edition), 2009, 18(3):30-33.)

Parallel algorithm for hillshading under multi-core computing environment

基于多核计算环境的地貌晕渲并行算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	XIE Wenbo, WEI Yongzhuang, LIU Zhenghong. Parallel implementation and analysis of SKINNY encryption algorithm using CUDA [J]. Journal of Computer Applications, 2021, 41(4): 1136-1141.
[2]	YANG Xianfeng, GUI Hongjun, FU Chunchang. F-X domain predictive filtering parallel algorithm based on compute unified device architecture [J]. Journal of Computer Applications, 2021, 41(2): 486-491.
[3]	ZENG Zhiyang, CHEN Yan, WANG Ke. Design and implementation of parallel genetic algorithm for cutting stock of circular parts [J]. Journal of Computer Applications, 2020, 40(2): 392-397.
[4]	CUI Yixin, CHEN Xiaodong. Spark framework based optimized large-scale spectral clustering parallel algorithm [J]. Journal of Computer Applications, 2020, 40(1): 168-172.
[5]	HE Xi, WU Yantao, DI Zhenwei, CHEN Jia. GPU-based morphological reconstruction system [J]. Journal of Computer Applications, 2019, 39(7): 2008-2013.
[6]	CHENG Lu, ZHOU Bo. Slope unit extraction algorithm based on texture watershed [J]. Journal of Computer Applications, 2019, 39(6): 1810-1815.
[7]	SHA Zongxuan, XUE Fei, ZHU Jie. Scheduling strategy of cloud robots based on parallel reinforcement learning [J]. Journal of Computer Applications, 2019, 39(2): 501-508.
[8]	WANG Peng, ZHOU Yan. MPI big data processing for high performance applications [J]. Journal of Computer Applications, 2018, 38(12): 3496-3499.
[9]	ZHANG Runlian, ZHANG Xin, ZHANG Chuyun, XI Yuang. Path planning algorithm based on distance and slope in regular Grid digital elevation model [J]. Journal of Computer Applications, 2018, 38(11): 3188-3192.
[10]	JIAO Jiafeng, LI Yun. Review of typical machine learning platforms for big data [J]. Journal of Computer Applications, 2017, 37(11): 3039-3047.
[11]	JI Lina, CHEN Qingkui, CHEN Yuanjing, ZHAO Deyu, FANG Yuling, ZHAO Yongtao. Real-time crowd counting method from video stream based on GPU [J]. Journal of Computer Applications, 2017, 37(1): 145-152.
[12]	XUE Jun, DUAN Fajie, JIANG Jiajia, LI Yanchao, YUAN Jianfu, WANG Xianquan. Parallel cyclic redundancy check Verilog program generating method based on Matlab [J]. Journal of Computer Applications, 2016, 36(9): 2503-2507.
[13]	XING Shuning, LIU Fang'ai, ZHAO Xiaohui. Parallel high utility pattern mining algorithm based on cluster partition [J]. Journal of Computer Applications, 2016, 36(8): 2202-2206.
[14]	GUAN Yaqin, ZHAO Xuesheng, WANG Pengfei, LI Dapeng. Parallel algorithm for massive point cloud simplification based on slicing principle [J]. Journal of Computer Applications, 2016, 36(7): 1793-1796.
[15]	WANG Yuanlong. Rendering algorithm of dynamic participating media based on optical flow [J]. Journal of Computer Applications, 2016, 36(5): 1352-1355.