基于四叉树的LiDAR点云数据组织研究

1、文章编号：0494-0911 (2008 )11x)021-03中图分类号:p237文献标识码基于四叉树的lidar点云数据组织研究陈冈9,张芯，张明，石宏斌(中国地质大学(武汉)信息工程学院，湖北武汉430074)study of the organization of lidar points cloud data based on quadtreechen gang, zhang xin, zhang ming, shi hong-bin摘要：针对传统的数据读取方法不能満足lidar点云数据尿大的待点，塔于windowh的内存映射机制研究lidar点心数据组 织，利用四义树对lidar点

2、云数据进行索引管理，并在lidar点云的三维场駅绘制中对点公数据进行的裁碱轻cpu的负帆捉 薛氏运第的效率。关键词:udar；pm x树；内“映射四叉树是一种常见的空间索引，它是基于空间 划分组织索引结构的索引机制。如果将(2知范碉 的空间划成四个相等的齐空间，若帶耍叮以将每个 或英中儿个子空间继续划分下去，这样就形成了一 个基于四叉树的空间划分。目前国内比较成熟 的软件supermap, mapgis均是采用四义树作为索 引方法对数据进行组织的。机载激光雷达(lidar)是一种主动式的对地观 测系统。通过hdar传感器发射的激光脉冲，能直 接连续自动获取高箱度三维地表地形数据。尽管 lida

3、r硕件系统发展迅速，但数据后处理过程中的 许多算法和模型冇待完善。本文的冃标就是要 研究ijdar点云数据组织，针对传统的数据读取方 法不能满足udar点云数据疑大的特点，研究基于 windows的内存映射机制，利用四叉树对ijdak点 云数据进行索引管理，并在lidar点云的三维场景 绘制中对点云数据进行剪裁。!1!四叉树有线性四叉树和链式四叉树，本文只讨 论链式四叉树。在数据结构中，树用来表达一对多 的非线性数据关系。在n(n>0)个结点的有限集合 中，它或为空树(n=0),或是由一个根结点加上四 棵称为子树的、互不相交的四叉树组成。四叉树是 一种递归的方法，其中每个结点的度不大于4

4、。其 数据结构如下：struct quardtreei 结点所表示的数据范围double x_min,x_max；double y_min,y_max；int mintcount ；/点云链表struct pointld * pointhead;/指向头结点的 id struct pointld * pointcurrent ；/指向当前结 点的id指向四个孩子结点struct quardtree * tree 4 j ；i；二、四叉树的建立当读取数据文件的时候,需要获取数据文件的 的放大瑕小值，用于建立四叉树的根结点，获 取最人最小值后，将最大最小值赋给对应的变量, 并对四个子结点赋空，用于

5、将其标识为叶子结点, 根结点的实现过程如下：struct quardtree * m _ quardtree = new quardtree ();m_quardiree -> x_max = xmax； m_quardtree -> x_min = xmin；m_quardtree -> y_max = ymax ； m_quanltree -> y_min = ymin；for (int i = 0 ； i <4； i + )收稿日期：200809-22作者简介：陈 刚(197】)男湖北咸宁人，博士，副教授，研究方向为“3s"技术在资源与环境遥感中的

6、应用。ni_quardtree -> tree ： i = edgepoint ； m_quardtree -> proot = null ； m_quardtree -> m_pointcount = 0 ； m_quardtree -> pointhead = null； m_quardtree -> pointcurrent = null； 根结点创建之后，需要读数据文件，每读入一个点，创建一个点类(cdot)对象,为其赋予一个id 号，这个id信息存储在点类对象中，并把这个对象 保存在对象数组中，然后根据该点所属的区域，将 该ii)插入到四叉树中,其插入的

7、过程是个递归调用 的过程。其实现原理为:将一个id插入根结点,首先判 断该树是否为空，然后判断该id所标识的点是否属 于该四叉树所表达的区域，如果是判断根结点是否 为叶结点,如杲为叶子结点,将该点插入根结点，继 续读文件。当在根结点插入点数大于某限定值(一 般不大于1啤2厲)，四叉树进行四均分，将父结点的 点按照所屈于的沪区域撒播，并将父布点中的点云 链表赋空。在插入的过程中主要涉及叶子结点的判断及 点与矩形关系的判断，是否为叶子结点主要看该结 点的四个子结点是否为空，如果为空,则为叶结点。 点与矩形关系的判断主要看大是否在该区域兀 的最小最大值中，如果同时满足，则在矩形区域中。 其实现代码如

8、下：叶子结点的判断bool copengl ： isla£|unction( quardtree * t)iint flag = 0 ；for( int i = 0 ； i <4 ； i + ) if(t-> treei = = edgepoint) flag+；if (flag = = 4) return true；elsereturn false；i点与矩形关系的判断bool copengl : dotinrectang( double x, double y,double xmin,double xmax,double ymin,double ymax)iif( (

9、 x > 二 xmin ) && ( x v xmax ) && ( y二 ymin)&&(y <ymax)ireturn true；ireturn false；三、四叉树在lidar数据处理中的应用1点云数据内插在实际应用中常需要将不规则的点云数据内 插成规则格网数据，而在大数据窜的环境下如何高 效内插是业内的一个热门研究问题，基于四叉树的 点云数据组织模式是在数据的内插过程中，缩小临 近点搜索范闌，从而提岛规则格网内插的效率。徃内插之前，臬待插点的平面位论为已知数 据，在箔规的内描方法中，一般濡要捜索其一定范 围内的点，按照某方法

10、讣算出该待插点的高程 值。搜索过程般是以待插点为圆心，按一定的 半径进行搜索,待插点是属于某一叶子结点的，而 按照某半径进行搜索的范围可能在该叶子结点中, 也可能在其所属叶子结点的相邻结点中，因此该搜 索过程可能涉及四叉树结点的邻域搜索问题。搜索是在以待插点为im1丿11、的某一半径范国内 进行的，而四叉树的叶子结点均表示数据区域的某 一分割的矩形区域，判断某一叶子结点是否在搜索 范围也就是判断叶子结点所表示的矩形范围和搜 索的圆形范围的关系：相交、包含、相离。为了简化 计算，在本文中，该判别关系转换为结点所表示的 矩形范围和搜索圆的外接四边形的关系，也就是矩 形和矩形之间的关系，而矩形的相互

11、位置关系判别 只需比较左右边界和上卜边界就町以了。其实现 代码如下：bool copengl : rectangtorectang( double xl , double yl , double x2, double y2,double x3 , double y3 , double x4, double y4 )/xl,yl,x2,y2矩形的两个对角顶点，分别表 示最大最小值/x3,y3,x4,y4矩形的两个对角顶点，分别表 示最大最小值如果有一个最小的顶点/比另一个最大的都大，那么它济股有交点 if(x3 >x2l 1x4 <xl)return false；如果有一个最大的顶点

12、/比另一个最小的都小,那么它们没有交点 if( y3 > y2 i i y4 < yl) return false ；实现了结点的邻域搜索之后，利用各种方法进return true;glgetdoublev ( gl _ projection _ ma-trix, projection)；glgetlntegcrv (gl_viewport, viewport)；/近裁剪面上某点对应的世界坐标行内插的时候，比不使用四叉树时候效率明显提高。2.二维场景没游场晟的漫游采用透视投影，而透视投影的视场 为一平截头体(如图1所示)，e为摄像机位置。视 景体的视场是有范围的，在移动图中摄像机e

13、点的 位怪过程中，视景体的可视范围在不断地变化。 对于lidar点云数据来说，其范閘比较大，在三维 场娥中视景体不叮能显示全部的数据区域，如果不 加选择地绘制全部数据点,将会对cpu带來巨大的 压力，为捉高效率，必须实时地计算视娥体的町视 范宙i,根据其可视范w,有选择地绘制数据点。图1视娥体可视范围图面abed为近裁剪面，即计算机屏幕；面abcd 为远裁剪面,ifil p为平均高程面，面p截平截头体, 得到四边形区域a,btctdty四边形区域a,btctdt即 为平截头体(视景体)的可视范围。视呆体可视范围的计算可以通过以下方法解 决:根据点a,a,b,b,c,c,d,d的坐标分别计算空间

14、 直线aa,bb,cc,dd的直线方程，然后根据平均高程 面计算点a,b,c,0的空间坐标，而点a,a,b,b, c,c,d®的坐标可以通过opengl中所提供的函数 去获取，其实现方法如下：void copengl : getneargipoint ( cpoint point,cdot &pdot)gldouble modelview 16;gldouble projection 16 j ；glintviewportl4；glgetdoublev ( gl _ modelview _ matrix ,modelview )；系坐标glxlouble world_x, w

15、orldly, worl(l_z ；/获取近裁剪面上的交点glu un project ( ( gldouble) point, x, (；l double) ( height-point, y) , 0. 0, niodelview, projection, viewport, &world_xt &worldly, &world/)； pdot. sclx( world_x) ； pl)ot. sety ( world _ y) ;pdot. setz( ( float) world./)；i三维町视化足lidar点云的组织与处理的农 现方法，采用四义树能够冇效地实现点云数据的组 织及快速搜索,满足动态的数据操作、独立的数据 存取、索引的简单有效的要求。四、结束语而对lidar点云的大数据量读取和组织，提岀 了基于四叉树的空间索引方法，该方法是建立在对 数据区域分层次四分的基础上，缩小了搜索范围, 大大提高了点云数据的搜索效率。木文分析了常用数据索引方法的特点,最后确 定利用四叉树对点云数据进行分块组织