《基于KD树与八叉树索引相结合的LiDAR点云数据索引建立方法讲解》由会员分享，可在线阅读，更多相关《基于KD树与八叉树索引相结合的LiDAR点云数据索引建立方法讲解（74页珍藏版）》请在金锄头文库上搜索。
1、 编号：（ ）字 号本科生毕业设计（论文） 基于KD树与八叉树索引相结合的 LiDAR点云数据索引建立方法张 哲 霄 07113032测绘11-3班题目： 姓名： 学号： 班级： 二一五年六月中 国 矿 业 大 学本科生毕业设计姓 名： 张哲霄 学 号： 07113032 学 院： 环境与测绘学院 专 业： 测绘工程 设计题目： 基于KD树与八叉树索引相结合的 LiDAR点云数据索引建立方法 指导教师： 王永波 职 称： 副教授 2015年6月 徐州中国矿业大学毕业设计任务书学院 环境与测绘学院 专业年级 测绘11-3班 学生姓名 张 哲 霄 任务下达日期：2015 年 3月 23日毕业设计日
2、期： 2015 年 3月 23日至 2015年 6月 15日毕业设计题目：基于KD树与八叉树索引相结合的LiDAR点云数据索引建立方法毕业设计专题题目：毕业设计主要内容和要求：1回顾LiDAR技术的发展，归纳LiDAR技术获取的点云数据的特点；2回顾点云数据组织与管理方法的发展，研究KD树与八叉树这两种常用的空间索引方式在对LiDAR点云数据管理时的特点；3编程实现KD树与八叉树索引，进行算法测试比较两种算法之间的优劣；4将两种索引方式进行结合，探索有着更高效率的LiDAR点云数据组织与管理方式，并编码实现算法。比较结合后的算法与单独使用一种索引方式时的效率；5得出最后的结论，指出研究中的不足
3、及下步的研究方向。院长签字： 指导教师签字：中国矿业大学毕业设计指导教师评阅书指导教师评语（基础理论及基本技能的掌握；独立解决实际问题的能力；研究内容的理论依据和技术方法；取得的主要成果及创新点；工作态度及工作量；总体评价及建议成绩；存在问题；是否同意答辩等）：成 绩： 指导教师签字： 年 月 日中国矿业大学毕业设计评阅教师评阅书评阅教师评语（选题的意义；基础理论及基本技能的掌握；综合运用所学知识解决实际问题的能力；工作量的大小；取得的主要成果及创新点；写作的规范程度；总体评价及建议成绩；存在问题；是否同意答辩等）：成 绩： 评阅教师签字： 年 月 日中国矿业大学毕业设计答辩及综合成绩答 辩
4、情 况提 出 问 题回 答 问 题正 确基本正确有一般性错误有原则性错误没有回答答辩委员会评语及建议成绩：答辩委员会主任签字： 年 月 日学院领导小组综合评定成绩：学院领导小组负责人： 年 月 日摘 要由于迅速发展着的计算机技术和不断增加的社会需求，地面LiDAR作为一种三维空间信息的实时获取手段，集高效与高精度于一体，它也取得了长足的发展。地面LiDAR的发展改变了传统的数据获取模式，拓宽了数据源范围，实现了快速获取高分辨率数字表面模型；但是点云数据的海量性成为了制约点云数据处理方法的发展的重要因素，急需寻找一种高效空间索引的方法来解决这个问题，高效地管理海量点云数据。基于上述分析，对于研究
5、点云数据的索引机制也就非常重要了，针对与点云索引建立过程中有涉及到的关键技术，论文的主要的研究内容和成果有：1）回顾了三维空间信息获取技术、LiDAR技术和点云数据组织管理方法的发展和研究现状；2）总结了点云数据的特点，例如有点云数据海量性、离散性、分布不均匀等特点，除此之外还介绍了八叉树索引和规则格网索引，同时分析了它们在组织和管理点云数据时存在的缺点和不足；3）设计并编程实现了基于KD树与八叉树的点云索引，并进行了算法测试与比较，由获得的测试结果得出，在点云数据量相同的情况下，KD树的查询效率比八叉树索引更更高，对于点云数据的管理效率更加优秀；4）探索了KD树索引与八叉树索引相结合的点云索
6、引建立方法，分别形成了KDO与OKD等两种索引，利用C+语言对其编程实现，进行了算法测试，结果显示出OKD索引更适合于海量的点云数据管理。关键词：LiDAR；点云；空间索引；八叉树；KD树ABSTRACTWith advances incomputer technology and the growingsocialdemand,as a real-time three-dimensional information acquisition method has the advantages of high efficiency and precision ground LiDAR has a
7、lso made great strides. Developments on the ground LiDAR has changed the traditional data acquisition modes, broaden the scope of the data source and can rapidly capture high-resolution digital surface model. But the mass of the point cloud data become an important factor restricting the development
8、 of processing method , so we need to find an efficient spatial indexes solve this problem. Based on the above analysis, the indexing mechanism for the study of point cloud data is very important . Established in point cloud for the indexing process involving key technologies, the main research cont
9、ent and results of the paper are:1) It describes the development and research status of the three-dimensional information acquisition technology, LiDAR technology and point cloud data organization and management methods;2) It summarizes the characteristics of the point cloud data, such as the mass o
10、f a little cloud data, discrete, uneven distribution. In addition, It describes the octree index and regular grid index, and analyzes the shortcomings and deficiencies of their existence in the organization and management of point cloud data;3) Design and programming index of point cloud which based
11、 on the KD Tree and octree, and tested and compared the two of algorithms. According to the test results, at the same point cloud data, KD tree efficiency is higher than the efficiency of the octree;4)Explore the composite index of the KD-tree indexes and octree index, and found two method of indexe
12、s for point cloud which named KDO index and OKD index. After testing of two new indexes, the results show, OKD index is more suitable for massive point cloud data management.Keywords: LiDAR; point cloud; spatial index; octree; KD tree目 录摘 要ABSTRACT目 录1 绪 论11.1 研究背景与意义11.2 国内外研究现状11.2.1三维空间数据的获取技术的研究现状11.2.2空间数据索引国内外研究现状41.3 研究内容51.4 论文结构安排52 点云数据获取的理论和数据特点62.1机载LiDAR系统62.1.1系统的组成62.1.2工作原理72.1.3系统的特点102.2地面LiDAR系统112.2.1系统的组成112.2.2工作原理112.2.3系统的特点122.3点云数据结构142.4点云数据特点142.5本章总结153 基于KD树的LiDAR点云数据组织与管理153.1引言153.2算法描述163.2.1分割规则163.2.2索引建立163.2.2 K邻近查找173.
