基于KD树与八叉树索引相结合的LiDAR点云数据索引建立方法..docx

编号:( )字号
本科生毕业设计(论文)
基于KD树与八叉树索引相结合的
LiDAR点云数据索引建立方法
张哲霄 07113032
测绘11-3班
题目:

姓名: 学号:
班级:
二〇一五年六月
中国矿业大学
本科生毕业设计
姓名: 张哲霄学号: 07113032
学院: 环境与测绘学院
专业: 测绘工程
设计题目: 基于KD树与八叉树索引相结合的
LiDAR点云数据索引建立方法
指导教师: 王永波职称: 副教授



2015年6月徐州
中国矿业大学毕业设计任务书
学院环境与测绘学院专业年级测绘11-3班学生姓名张哲霄

任务下达日期:2015 年 3月 23日
毕业设计日期: 2015 年 3月 23日至 2015年 6月 15日
毕业设计题目:基于KD树与八叉树索引相结合的LiDAR点云数据索引建立方法
毕业设计专题题目:
毕业设计主要内容和要求:
1回顾LiDAR技术的发展,归纳LiDAR技术获取的点云数据的特点;
2回顾点云数据组织与管理方法的发展,研究KD树与八叉树这两种常用的空间索引方式在对LiDAR点云数据管理时的特点;
3编程实现KD树与八叉树索引,进行算法测试比较两种算法之间的优劣;
4将两种索引方式进行结合,探索有着更高效率的LiDAR点云数据组织与管理方式,并编码实现算法。比较结合后的算法与单独使用一种索引方式时的效率;
5得出最后的结论,指出研究中的不足及下步的研究方向。
院长签字: 指导教师签字:
中国矿业大学毕业设计指导教师评阅书
指导教师评语(①基础理论及基本技能的掌握;②独立解决实际问题的能力;③研究内容的理论依据和技术方法;④取得的主要成果及创新点;⑤工作态度及工作量;⑥总体评价及建议成绩;⑦存在问题;⑧是否同意答辩等):
成绩: 指导教师签字:
年月日
中国矿业大学毕业设计评阅教师评阅书
评阅教师评语(①选题的意义;②基础理论及基本技能的掌握;③综合运用所学知识解决实际问题的能力;③工作量的大小;④取得的主要成果及创新点;⑤写作的规范程度;⑥总体评价及建议成绩;⑦存在问题;⑧是否同意答辩等):
成绩: 评阅教师签字:
年月日
中国矿业大学毕业设计答辩及综合成绩
答辩情况
提出问题
回答问题
正确
基本
正确
有一般性错误
有原则性错误
没有
回答
答辩委员会评语及建议成绩:
答辩委员会主任签字:
年月日
学院领导小组综合评定成绩:
学院领导小组负责人:
年月日
摘要
由于迅速发展着的计算机技术和不断增加的社会需求,地面LiDAR作为一种三维空间信息的实时获取手段,集高效与高精度于一体,它也取得了长足的发展。地面LiDAR的发展改变了传统的数据获取模式,拓宽了数据源范围,实现了快速获取高分辨率数字表面模型;但是点云数据的海量性成为了制约点云数据处理方法的发展的重要因素,急需寻找一种高效空间索引的方法来解决这个问题,高效地管理海量点云数据。基于上述分析,对于研究点云数据的索引机制也就非常重要了,针对与点云索引建立过程中有涉及到的关键技术,论文的主要的研究内容和成果有:
1)回顾了三维空间信息获取技术、LiDAR技术和点云数据组织管理方法的发展和研究现状;
2)总结了点云数据的特点,例如有点云数据海量性、离散性、分布不均匀等特点,除此之外还介绍了八叉树索引和规则格网索引,同时分析了它们在组织和管理点云数据时存在的缺点和不足;
3)设计并编程实现了基于KD树与八叉树的点云索引,并进行了算法测试与比较,由获得的测试结果得出,在点云数据量相同的情况下,KD树的查询效率比八叉树索引更更高,对于点云数据的管理效率更加优秀;
4)探索了KD树索引与八叉树索引相结合的点云索引建立方法,分别形成了KDO与OKD等两种索引,利用C++语言对其编程实现,进行了算法测试,结果显示出OKD索引更适合于海量的点云数据管理。
关键词:LiDAR;点云;空间索引;八叉树;KD树
ABSTRACT
With advances puter technology and the growing social demand, as a real-time three-dimensional information acquisition method has the advantages of high efficiency and precision ground LiDAR has also made great strides. Developments on the ground LiDAR has changed the traditional d