一种并行计算的流数据Delaunay构网算法

李坚; 李德仁; 邵振峰

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种并行计算的流数据Delaunay构网算法

李坚, 李德仁, 邵振峰

文章导航 > 武汉大学学报 ● 信息科学版 > 2013 > 38(7): 794-798

李坚, 李德仁, 邵振峰. 一种并行计算的流数据Delaunay构网算法[J]. 武汉大学学报 ● 信息科学版, 2013, 38(7): 794-798.

引用本文:

李坚, 李德仁, 邵振峰. 一种并行计算的流数据Delaunay构网算法[J]. 武汉大学学报 ● 信息科学版, 2013, 38(7): 794-798.

LI Jian, LI Deren, SHAO Zhenfeng. A Streaming Data Delaunay Triangulation Algorithm Based on Parallel Computing[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7): 794-798.

Citation:

LI Jian, LI Deren, SHAO Zhenfeng. A Streaming Data Delaunay Triangulation Algorithm Based on Parallel Computing[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7): 794-798.

一种并行计算的流数据Delaunay构网算法

¹武汉大学测绘遥感信息工程国家重点实验室

基金项目: 国家973计划资助项目(2010CB731800); 国家863计划资助项目(2009AA121404); 国家自然科学基金资助项目(61172174)

详细信息

作者简介:
李坚，博士生，研究方向为ＧＩＳ、遥感图像处理。

中图分类号: P208;P237.3

A Streaming Data Delaunay Triangulation Algorithm Based on Parallel Computing

¹State Key Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,129 Luoyu Road,Wuhan 430079,China

Funds: 国家973计划资助项目(2010CB731800); 国家863计划资助项目(2009AA121404); 国家自然科学基金资助项目(61172174)

摘要: 提出了一种流数据算法进行Delaunay三角网构网,用来处理上十亿的LiDAR点云数据。该算法基于并行多核处理器架构,将三角网构网的分治算法与流数据处理相结合。一种四叉树结构用来自适应地划分点云数据文件,并将分割构网和合并子网工作动态调度分布到不同处理器,以提高负载均衡。算法通过并行计算,充分利用多核处理器平台的计算能力,取得了高运行效率和低内存占用。
- Delaunay构网 /
- 并行计算 /
- 流数据 /
- LiDAR点云 /
- 四叉树
Abstract: This paper presents a streaming data algorithm to execute Delaunay triangulations with large LiDAR point clouds(a billion data points) based on multi-core processor architecture.The algorithm combines divide-and-conquer triangulation with streaming data.A quad-tree structure is used to partition the LiDAR data into subnets adaptively,and schedules triangulation and merging of the subnet data into different processors for load balancing.Parallel computing on multi-core processor architecture makes this algorithm highly efficient with a low memory footprint.
- Delaunay triangulation /
- parallel computing /
- streaming data /
- LiDAR data /
- quad-tree

[1]

郑春燕郭庆胜,胡华科,夏慧琼,. 基于约束Delaunay三角网建立等高线层次结构的方法[J]. 武汉大学学报(信息科学版). 2008(05)[2] 芮一康王结臣,. Delaunay三角形构网的分治扫描线算法[J]. 测绘学报. 2007(03)[3] 谭仁春杜清运,杨品福,张珊珊,. 地形建模中不规则三角网构建的优化算法研究[J]. 武汉大学学报(信息科学版). 2006(05)[4] 胡金星马照亭,吴焕萍,潘懋,. 基于格网划分的海量数据Delaunay三角剖分[J]. 测绘学报. 2004(02)[5] 刘学军龚健雅,. 约束数据域的Delaunay三角剖分与修改算法[J]. 测绘学报. 2001(01)[6] 武晓波王世新,肖春生,. Delaunay三角网的生成算法研究[J]. 测绘学报. 1999(01)

[1]	李水泉, 乐阳, 李清泉, 庄严. 一种Haar小波概要的流数据压缩方法 . 武汉大学学报 ● 信息科学版, 2021, 46(8): 1216-1223. doi: 10.13203/j.whugis20190309
[2]	张强, 赵齐乐. OpenMP并行计算在全球电离层反演中的应用 . 武汉大学学报 ● 信息科学版, 2018, 43(2): 227-233, 240. doi: 10.13203/j.whugis20160065
[3]	王鸿琰, 关雪峰, 吴华意. 一种面向CPU/GPU异构环境的协同并行空间插值算法 . 武汉大学学报 ● 信息科学版, 2017, 42(12): 1688-1695. doi: 10.13203/j.whugis20150361
[4]	谢金运, 涂伟, 李清泉, 常晓猛, 马承林, 李追日, 黄练. 大规模浮动车流数据并行地图匹配方法 . 武汉大学学报 ● 信息科学版, 2017, 42(5): 697-703. doi: 10.13203/j.whugis20140847
[5]	李林阳, 吕志平, 崔阳, 王宇谱, 吕浩, 宫晓春. 大规模GNSS基线向量网抗差并行贝叶斯估计 . 武汉大学学报 ● 信息科学版, 2016, 41(10): 1385-1390. doi: 10.13203/j.whugis20140763
[6]	王玉着, 刘修国, 张唯. 并行化多流向策略的栅格河网提取算法 . 武汉大学学报 ● 信息科学版, 2015, 40(12): 1646-1652,1682. doi: 10.13203/j.whugis20140645
[7]	陈正生, 吕志平, 崔阳, 王宇谱. 大规模GNSS数据的分布式处理与实现 . 武汉大学学报 ● 信息科学版, 2015, 40(3): 384-389.
[8]	彭代锋, 张永军, 熊小东. 结合LiDAR点云和航空影像的建筑物三维变化检测 . 武汉大学学报 ● 信息科学版, 2015, 40(4): 462-468. doi: 10.13203/j.whugis20130325
[9]	陈驰, 王珂, 徐文学, 彭向阳, 麦晓明, 杨必胜. 海量车载激光扫描点云数据的快速可视化方法 . 武汉大学学报 ● 信息科学版, 2015, 40(9): 1163-1168. doi: 10.13203/j .whu g is20130693
[10]	罗广祥, 刘苗, 樊鸿宇, 杨芳. 全球等面积四叉树离散格网建模与编码体系研究 . 武汉大学学报 ● 信息科学版, 2012, 37(10): 1252-1255.
[11]	翟晓芳, 龚健雅, 肖志峰, 张丙龙. 利用流水线技术的遥感影像并行处理 . 武汉大学学报 ● 信息科学版, 2011, 36(12): 1430-1433.
[12]	徐正全, 高路, 李忠民, 王浩. 基于非结构化P2P网络的地形数据存储系统 . 武汉大学学报 ● 信息科学版, 2010, 35(1): 122-125.
[13]	王宗跃, 马洪超, 徐宏根, 彭检贵. 基于LiDAR点云数据的水体轮廓线提取方法研究 . 武汉大学学报 ● 信息科学版, 2010, 35(4): 432-435.
[14]	谢顺平, 冯学智, 王结臣, 周立国. 一种基于优势属性存储的四叉树结构及其构建算法 . 武汉大学学报 ● 信息科学版, 2009, 34(6): 663-666.
[15]	周芹, 钟耳顺, 黄耀欢, 郭会. 大型空间数据库的并发索引策略CQR树 . 武汉大学学报 ● 信息科学版, 2009, 34(7): 856-858.
[16]	王宗跃, 马洪超, 徐宏根, 邬建伟. LiDAR点云数据的分布式组织及其并行获取方法 . 武汉大学学报 ● 信息科学版, 2009, 34(8): 936-939.
[17]	吴芳, 芮国胜. 基于四叉树和纠错编码的数字图像水印算法 . 武汉大学学报 ● 信息科学版, 2007, 32(3): 208-211.
[18]	蒋晶珏, 张祖勋, 明英. 复杂城市环境的机载Lidar点云滤波 . 武汉大学学报 ● 信息科学版, 2007, 32(5): 402-405.
[19]	易尧华, 龚健雅, 秦前清. 大型影像数据库中的色调调整方法 . 武汉大学学报 ● 信息科学版, 2003, 28(3): 311-314.
[20]	邓朝晖, 贾华. 直接表达区域的四叉树链式编码 . 武汉大学学报 ● 信息科学版, 1995, 20(3): 224-227.

点击查看大图

计量

文章访问数: 1077
HTML全文浏览量: 21
PDF下载量: 637
被引次数: 0

一种并行计算的流数据Delaunay构网算法

¹武汉大学测绘遥感信息工程国家重点实验室

基金项目: 国家973计划资助项目(2010CB731800); 国家863计划资助项目(2009AA121404); 国家自然科学基金资助项目(61172174)

作者简介:
李坚，博士生，研究方向为ＧＩＳ、遥感图像处理。

收稿日期: 2013-04-15
修回日期: 2013-04-15
刊出日期: 2013-07-05

中图分类号: P208;P237.3

关键词:

Delaunay构网 /

并行计算 /

流数据 /

LiDAR点云 /

四叉树

摘要: 提出了一种流数据算法进行Delaunay三角网构网,用来处理上十亿的LiDAR点云数据。该算法基于并行多核处理器架构,将三角网构网的分治算法与流数据处理相结合。一种四叉树结构用来自适应地划分点云数据文件,并将分割构网和合并子网工作动态调度分布到不同处理器,以提高负载均衡。算法通过并行计算,充分利用多核处理器平台的计算能力,取得了高运行效率和低内存占用。

English Abstract

李坚, 李德仁, 邵振峰. 一种并行计算的流数据Delaunay构网算法[J]. 武汉大学学报 ● 信息科学版, 2013, 38(7): 794-798.

引用本文:

李坚, 李德仁, 邵振峰. 一种并行计算的流数据Delaunay构网算法[J]. 武汉大学学报 ● 信息科学版, 2013, 38(7): 794-798.

LI Jian, LI Deren, SHAO Zhenfeng. A Streaming Data Delaunay Triangulation Algorithm Based on Parallel Computing[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7): 794-798.

Citation:

LI Jian, LI Deren, SHAO Zhenfeng. A Streaming Data Delaunay Triangulation Algorithm Based on Parallel Computing[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7): 794-798.