您好、欢迎来到现金彩票网!
当前位置:2019正版免费全年资料 > 凸包逼近 >

建筑物LiDAR点云数据特征检测与配准关键技术分析pdf

发布时间:2019-06-26 20:32 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  Researchon of LiDARPoint KeyTechniquesBuilding CloudDataFeatureDetectionand Registration Abstract Thefeaturedetectionof clouddataand has beenaarea point matchingtechnologycurrently onthe detectionof clouddataand ofresearch feature highlights.Concentrating point registration the for LiDAR feature detection data, problems,thispapermainlyinvestigates points building theextractionof horizontalandverticalfeature issuesof clouddata building edge lines,the point mainworkisasfollows: registration.The clouddata howtobuildatreeand (1)Achieve managementkd—tree,andstudy point using k the the of ordertoestablish improvesearchingefficiencyneighborpoints.In relationship between establisheskd—tree spatialtopologicaladjacentpoints,thispaperfirstly usingdichotomy, and the ofthe clouddataofk thenstudies implementssearchingpoint neighborhoodpoints,and thetimeof treeunderdifferentamountsofdataandthe ofk building searchingefficiency researchshowsthatwiththe timeof tree increaseofdata neighbors.The volume,thebuilding andthetimeof k arebothlinear searchingneighborpoints growth. forwardtoa based0nmulti—structuredatatoextractthehorizontaland (2)Put algorithm vertical of thebasisoftheleast edgesbuildings.On squareplanecuttingalgorithmdetecting feature conditional ofmodelis points,history using sampling perfomed andis tosearch line linear estimation feature algorithmapplied equation.Usingoptimization threshold.The the countthatthe linedistanceislessthanthe algorithm,calculatepoint straight theline locatedinarerecored. maximumcountof isthe feature line,which point optimal points Inordertodetectdifferent ontheidentical rank in targetedsegment straightline,firstlybypoint that thensearchforthe whichinthesameline the line,and points segmentutilizingcomparison between andthethreshold intactextractionofthewindow pointspacing value.Finally,the edge is showsthatthemulti—structurehasa accomplished.Theexperiment algorithmgreater the ofthe and of the linear,the of advantagespeedefficiencysearchingoptimal capacityoptimal linear inlier thanthe traditionalrandom contaimlingpoints sampling. thematchof feature of articleturnsthe (3)Implement edge pointsbuildings.This of discretefeature astheissueof estimation.In registrationedge point probabilitydensity accordancewiththe ofthemodel setis thanthedata requirements point greater point,defined datum cloudasthedata search cloudsetisdefinedasamodelset. point set,waitingpoint cloud of solvetransformation Buildingpoint registrationprocess,thatis,to parametersturning data settomodelset.The mixturemodellikelihoodfunctioniS asthe point gaussian designed lI 万方数据 ectivefunctionof the ofthethree-dimensional obj matching,aid matchingparameters point clouddataareobtained the in the iterativeEM ordertoachieve byapplying algorithm global of feature of that effectofrandomnoiseonthe basis,the matchingedge pointsbulidings.On is thebeneficialconclusionsarereceived. matchingprocessstudied,and OutlineFeature Cloud Data Keyword:DetectionPoint;Kd—tree;Featm’eDetection;Point Registration IlI 万方数据 目 录 第1章绪论….……...……..……………..……..….………..1 1.1研究背景和意义……….…........…..................….……1 1.2研究现状.....….…..…….…..…..….…………..……...2 1.2.1点云数据的研究现状……..………….….………………..2 1.2.2点云数据特征检测研究现状及问题……………………………3 1.2.3点云配准技术研究现状及问题.………………………………4 1.3研究目标及研究内容………..………….….………………..5 第2章KD.TREE管理点云数据….…………….….………………..7 2.1问题的提出……………....………………….……………7 2.3搜索K近邻点……………..………………………………..9 2.4KD—TREE建树和搜索效率实验….…………..….….…..…..….11 2.5本章小结.….…..………...……….....…………….......11 第3章多结构估计的建筑物边缘检测算法……………………….…...12 3.1问题的提出……………....………….….…..…………..12 3.2边缘特征点的检测..……...….….….……..…..……..…..13 3.2.1拟合最小二乘平面...………….….…….….一….……...14 3.2.2切割最小二乘平面算法检测边缘特征点……………………….15 3.3多结构估计算法….….…….…..…......….….…..…......15 33.1数据点相似度…………..……….…………..………...16 33.2条件内点概率………..………………..….…………...16 3t33算法流程表…………....……………………………...16 3.4线段检测算法……………..….………….…..…………..17 3.5实验结果与分析….……....……….……...…….…...…..18 3.6本章小结....…...……...…….…..…….…..…...........2l 第4章建筑物点云高斯混合模型配准算法…………………………….23 4.1问题的提出.……………..………….….….…………….23 IV 万方数据 ....................…...…23 4.2高斯混合模型……….........…... 4.2.1极大似然估计………......…... …................…一.….23 4.2.2 ...…….....……......…24 EM算法估计模型参数…………. ………....……...…....26 4.3配准目标函数的设计…….……….. ...…......…..….........26 4.3.1目标函数的提出…....……...... ……...…….…......….27 4.3.2变换参数表达式……….……... 4.3.3 ……..…..….............28 EM算法优化目标函数…………. 4.4实验结果与分析.…..…………....……...…..…….…..…29 4.5本章小结.………...…..……....…......…..….....….…30 第5章总结与展望.…….……...….....…..……..……...….…31 5.】论文的工作总结.….…….……....……...…..….........…31 ….....…..…….......…32 5.2问题与展望…………………….. 致 谢…………。………………… ...…...…..............…33 参考文献….…………..………….... .............................34 学术成果….…………...…..…….... ...…..….….…......….39 V 万方数据 集美大学硕_上学位论文 建筑物LiDAR点云数据特征检测及配准关键技术研究 第1章绪论 1.1研究背景和意义 传统的摄影测量与遥感技术仍然是空间信息的主要获取手段,但一种新型的LiDAR 激光测量技术备受应用者和研究者关注。三维激光扫描技术以其快速化高精度的三维点云 数据获取能力,在建筑物数字化、城市三维重建、城市规划、植被覆盖分析以及逆向工程 等方面得到了大量应用。相对于激光点云数据获取能力的快速提高,点云数据的处理能力 靠手]二作业。三维点云数据因其数据量大,受网络传送率制约,难以直接服务于客户。因 此,当前点云数据处理技术中自动化程度低的状况,严重制约着激光点云的应用。 点云配准是寻找点云与点云之间的对应点的一项工作,点云配准是建筑物三维模型重 建的一个重要环节。由于作业过程的遮挡以及设备测程的限制,一个测站的点云数据只能 表达建筑物的一个局部,通常,一栋建筑物需要多个测站的点云拼接而成。多个测站的点 云拼接离不开点云配准。另外,在目标识别、目标重建等方面,也离不开点云配准技术。 因此,有必要开展点云配准技术的研究。 激光点云的本质是三维图像,是目标表面在三维空间的离散化表达,通常由光学系统 获得的二维图像,是目标表面在二维焦平面上的离散化表达,激光点云LL--维图像多出一 维。对于二维图像的配准,为了保证其可靠性和精度,高质量的图像配准算法,其计算时 间已经不能满足实际应用的需要,如SIFT算法,对2幅1200万像元的图像,在普通计算 机上做图像匹配,耗费了较大的时间代价…。因此,对于点云数据的配准,可以预见,计 算效率问题将变得更加严重。 原始点云数据是目标表面的离散化表达,数据量巨大。激光扫描仪工作原理决定了原 始点云只能均匀地记录目标信息,这种均匀性,造成了数据冗余与细节表达之间矛盾。因 此,原始点云在满足目标细节表达的同时,存在大量冗余数据。 为了能够在合理的时间内完成点云匹配过程,一方面应尽量控制算法本身的日j叮哪复杂 度,另一方面则应实施点云简化,以减少数据量。注意到原始点云数据的大量冗余现象, 如果能在目标的角点、边缘、凸凹等部位保留原始采样密度,在其它部位减少采样密度, 则可以达到以最小数据量表达目标主要信息的目的。因此,有必要开展点云数据特征检测 算法的研究。 点云数据特征检测技术,可以最大限度地保留目标表面的变化信息,减低信息贫乏点 对数据量的占用,本文拟将特征检测和配准技术相结合,提出基于特征的点云配准技术。 同时注意到被简化后的点云,基准点云和待搜索的点云之间,零匹配点或将增加,为确保 匹配结果的可靠性,本文将重点研究基于特征的整体匹配算法。 万方数据 集美大学硕士学位论文 建筑物LiDAR点云数据特征检测及配准关键技术研究 1.2研究现状 1.2.1点云数据的研究现状 三维扫描仪扫描现实物体表面时,由于受尘土颗粒、天气、扫描设备本身的缺陷等因 素的影响,获取的扫描数据会有噪声,这影响了物体空间信息的表达,因此需要对点云数 据进行去噪处理。保特征的点云去噪算法是在去除噪声点的同时,确保点云模型细节特征 的稳定。在过去的研究中大多数去噪算法都是针对三维网格的去噪,且思想大多来自较成 熟的图像的去噪算法。现有点云数据的去噪光顺算法根据噪声的扩散方式可分为各向同行 和各向异性算法;根据算法的复杂度将点云数据去噪光顺算法分为:Laplace算法、最优化 法和非迭代方法心3。 各向同性算法∞1,算法不难,却对点云数据的噪声和模型的尖锐特征完全准确辨别有 一定难度。算法在去除噪声的同时,不能完全保持尖锐特征的稳定。各向异性算法n3改进 了扩散方程,有益于区分模型的尖锐特征和噪声,算法为保持模型尖锐特征的去噪过程。 由于这些算法需要计算保持细节的模型结构信息,所以计算量较大。 标准的Laplace光顺算法b1经过多次迭代将当前数据点逐步向数据点邻域重心迭代,此 算法对数据的分布情况有要求,如果数据分布不均,迭代后模型会出现变形扭曲;基于最 优化法哺’“,为了使点云模型有效的去噪光顺,算法优化能量函数使其最小来完成。该方 法可以保证较小规模的模型几何度量变形最小,当模型规模较大时优化能量函数使其最小 化需要很高的运算代价;非迭代方法睛1,使用顶点探测器单步完成光顺,该类算法虽然极 大地缩小了运算时问,但顶点探测器的筛选有一定难度。 激光扫描仪在获取点云数据时存在大量的冗余点,给后续处理带来不便,因此可通过 对数据进行特征检测,早期特征检测算法大都针对网格数据阳““1,近几年对点云数据的特 征检测研究逐渐增多。[11]首先对无规则的点云数据进行网格重建,随后处理网格模型的 尖角和尖锐特征。在对网格数据重建时,容易发生网格平滑尖锐特征的问题,针对这一问 题[12]提出在构建网格模型后,细分尖锐特征部分的网格,同时对网格顶点重新配置。 等n朝使用概率统计方法检测模型特征,将数据点的邻域点分配到其对应的局部曲面区域, 然后尖锐特征由分段的移动最小二乘曲面来构造。Demarsin等“41给出了直接检测特征点的 方法,文章首先使用分割方法找到尖锐特征区域,得到特征线附近的数据点,然后建立最 小生成树提取封闭的特征线,此方法的弊端是只对封闭的尖锐特征有效。 激光扫描仪扫描的点云数据中存在大量重复和多余数据,不利于数据的处理和传输。 因此采取数据简化的方法来减少数据量。目前点云数据的简化方法主要有三类:基于曲面 拟合的方法、基于网格拓扑结构的方法以及直接对三维点云模型简化的方法。随面拟合的 简化方法用近似的曲面拟合点云数据模型,然后进行拟合曲面的重采样。Pauly等人“副利 万方数据 集美大学硕士学位论文 建筑物LiDAR点云数据特征检测及配准关键技术研究 用高幂光滑曲面逼近点云模型,可以计算模型的多层次简化结果。使用这种方法获得的简 化模型,计算量较大且不能达到很好的简化目的。基于网格拓扑结构信息的简化方法包括 顶点聚类法n…、迭代法。73等。顶点聚类法是将点云数据转化为多边形网格模型,然后将其 分成数个小单元。用一个新顶点代替同一网格中其它顶点,最后得到点云数据的简化模型。 迭代法也是在点云模型网格化基础上,根据网格上的点对当前网格面的重要程度进行迭代 简化,基于网格模型的简化方法计算量大,简化效率低,内存开销也较大,所以研究者们 更希望直接对点云模型进行简化。 点云简化需要对点云重采样,根据不同的采样规则,可将采样法分为:均匀采样法。8、 赔率缩减采样法“引、弦偏离采样法瞳们及栅格采样法。均匀采样法得到的简化模型相对均匀, 不利于保留模型的细节特征,其它方法,属于非匀采样,有利于保留细节特征。 曲面重构是指根据已知的三维点云数据,利用某种曲面数学模型,准确还原出模型表 面形状,曲面重建是逆向工程的一个重要环节。重构曲面的方法主要可分为两类:一类是 针对表面构造无规则的物体,使用三角Bezier曲面来进行重构,由于三角曲面重构的几何 模型连续性较差,易形成尖锐区域,人机交互性能差,所以三角Bezier曲面重构在实际应 用上有较大局限性;另一类曲面重构方法为矩形边界重构法,将参数的矩形区域与三维空 间中一个矩形边界曲而建立对应关系,用该方法表示模型表面误差很小,工程应用中B样 条曲面和NURBS曲面重构应用普遍。 1.2.2点云数据特征检测研究现状及问题 点云数据特征检测主要方法有基于局部平面性分析的方法、基于点云数据分割的方 法、基于熵信息和最小生成树的边缘榆测法、邻域凸包法、张量投票法。 基于局部平面性分析的方法:Gumhold等人_”提出基于局部平面性分析的方法。算法 首先对点云中每个点的邻域点进行协方差分析,得到协方差矩阵的三个特征值,根据三个 特征值的大小关系来确定当前点为特征点的可能性,并以此构造惩罚函数,建立整个点云 的最小生成图,最小生成图中的点构成了特征线的候选点,之后用样条函数对这些点进行 拟合得到特征线将协方差扩展为基于多尺度实现,采用活动轮廓线取代样 条函数逼近特征线,算法的抗噪能力得到了加强。 基于点云数据分割的方法:该法对点云数据分割完后,各面片的交线就构成了点云特 征线。鉴于此,Demarsin等人瞳3。提出了对封闭特征线的检测算法。算法根据每个点的法向 量计算法向量之问的夹角,然后利用区域增长法将点云分割为多个簇,根据特征线L相邻 点之间的法向量变化较大,形成的簇较小。把具有较小簇的点划分为特征点的候选点,构 建最小生成树生成特征线。Daniels等人陋“2副基于鲁棒的移动最小二乘表面提出点云分割方 法,首先采用鲁棒的最小二乘方法对每个点的局部邻域进行分类,将局部邻域中的点进行 投影,筛选特征点,然后使用主成分分析方法进一步提取特征点,最后连接成特征线。 万方数据 集美大学硕士学位论文 建筑物LiDAR点云数据特征检测及配准关键技术研究 基于熵信息和最小生成树的边缘检测算法:为了避免边缘特征点的误检和漏检,文献 『26—29]示1J用点的局部熵信息初步筛选出可能的边缘特征点,这样避免了特征点的遗漏。然 后利用平均曲率信息和局部投影法进一步确定建筑物的边缘特征点,避免特征点的误检 测。在此基础上建立每个特征点的k邻域,计算当前点与k邻域中的点的距离,以此距离 作为两点间边的权值,用Kruskal算法构建最小生成树,形成建筑物的边缘特征线。最后 对特征边缘线处理得到更加精确的边缘特征线。 利用邻域凸包提取建筑物边缘特征线口“。在构建每个点的k近邻点基础上,计算每个 点基于邻域点范围内的凸包。如果当前点离凸包的最近距离大于给定的距离阂值,则认为 是非边界点,然后利用改进的最小生成树生成建筑物的边缘特征线,最后剔除细小的碎线 段,并利用边界的方向角度约束线段角度使建筑物边缘特征线提取的效果更好。k值和距 离阈值的选取直接影响了边界特征点的确定。 基于张量投票的多尺度法提取建筑物边缘特征线口…。主要研究局部邻域内的点对当 前点特征属性的贡献,通过对法向张量矩阵特征值的分析,判断当前点属于面上的点、边 界点还是没有任何组织机构的点的可能。由于实际中的点云数据可能会有不均匀和噪声的 存在,所以算法增加了对点邻域的多尺度分析,以此确定点的特征权重w,根据W值的情 况对点进行分类,建筑物的细节特征点以及角点由此可以提取出来,然后通过聚类的方法 去除非特征点,最后拟合建筑物立面的边缘特征线。 上述算法均未考虑利用特征点之间的关联性来检测特征线,本文将用条件概率密度估 计的方式来表达数据中任意两点之间的关联程度,并利用关联程度信息来改善特征检测的 效果,提高特征检测的稳健性。 1.2.3点云配准技术研究现状及问题 仿照影像中的像元的定义,将点云中每个采样点称为点元。点云匹配算法大致分为两 类,基于特征的匹配和基于点元的匹配。以下为分别对这两种方法的介绍。 第一类,基于特征的匹配。通过特征基元建立对应关系,特征基元可以分为:点特征、 线特征、面特征。特征基元可以是一种或几种联合使用。 基于同名点对特征的匹配,如盛业华等人口列依扫描站点的顺序,标示相邻站扫描重叠 区内的同名点,建立三维点云数据的坐标转换模型,求取坐标平移和旋转参数。用加权误 差分配的办法修正各站的平移和旋转参数,建立各站的坐标转换模型。最终融合不同站点 坐标系下的点云数据到同一项目坐标系下,实现多视角扫描数据的无缝拼接。用有限个同 名点对估算各站的坐标平移和旋转参数,避免了内存容量不够的问题。 基于同名线状特征的匹配口“,王永波等人口副首先用平面相交法提取的线状特征作为 LiDAR点云配准的基元。然后采用线状特征来约束基于四元数法的配准。最后给出了三维 相似性测度的表示方法,以及同名线 万方数据 集美大学硕士学位论文 建筑物LiDAR点云数据特征检测及配准关键技术研究 基于点、线、面共同约束的LiDAR点云匹配算法,郑德华等人l矧首先根据点云数据 中平面与平面的重合关系,建立点在平面上和平面与平面之间法线种线性不等 约束条件。然后在6参数模型中添加以卜线性不等约束条件,形成带有几何约束条件的配 准模型,经过反复迭代,解算模型的转换参数和残差。 第二类,基于点元匹配。点元匹配分单点点元和整体点元匹配。对于点云匹配,由于 单点点元匹配的可靠性较低,研究文献也较少。基于点元的匹配,绝大多数学者都把关注 点放在了整体点元匹配上。整体点元匹配的基本思想:①找到两个点集之间对应关系;② 估计变换。两步骤交叉迭代使得目标函数最小时的变换参数为最佳匹配。 在刚性配准领域应用广泛。ICP以迭代最近距离为标准,分配对应关系,迭代两个相关的 整体点元直到目标函数收敛。许多改进的ICP算法口…”被相继提出,算法主要在点集的选 择、匹配以及最小控制策略H21方面进行改进。ICP算法要求两个点集的初始位置要相当近。 为了克服ICP算法的局限性,许多概率的方法被相继提出H3’舭1。这些方法使用软匹配 之间的对应关系,根据概率的大小来建立所有点集的对应组合。这类方法典型的代表是 Point Gold提出的鲁棒点集匹配算法(Robust Plate 将RPM算法和由Chui和Rangarajan口1提出的薄板样条法(ThinSpline,TPS)结合形成 TPS.RPM算法,算法运用确定性退火和迭代更新来对软匹配和TPS的参数进行估计。文 章[481中展示了RPM的匹配对应关系和变换的软分配交替过程,其和高斯混合模型中的 EM(ExpectationMaximization)算法相似。 实际上不少刚性点云配准算法H”511将点集配准问题当作极大似然估计问题,并给出了 高斯混合模型质心点集合到数据集配准的公式,本文也是在此基础上进行的研究。 1.3研究目标及研究内容 研究目标: (1)实现用kd.tree管理点云数据,研究建树和搜索k近邻点的效率。为建立各数据点 之间的空间拓扑邻近关系,首先用二分法建立kd.tree,并实现三维点云数据k邻域点的搜 索机制,在此基础上研究不同数据量下的建树时间以及kd—tree搜索k近邻的时间效率问题。 (2)用基于多结构估计的条件采样算法提取建筑物点云数据水平和垂直方向上的边缘 特征线。在用切割最d,-乘平面算法检测边缘特征点基础上,利用多结构估计算法进行历 史模型信息条件采样,迭代搜索边缘特征线特征点直线方程,在此基础上采用直线寻优算 法选出最优的直线,并记录所包含的特征点。为了检测同一直线上不同的目标线段,在对 同一直线上的点排序基础上,利用点间距与阈值的比较来寻找同一线段}二的点,最后实现 窗户边缘特征线的完整提取。 万方数据 集美大学硕士学位论文 建筑物LiDAR点云数据特征检测及配准关键技术研究 f3)实现建筑物边缘特征点的匹配。将建筑物边缘离散特征点集的配准问题转换成概率 密度估计问题,用连续的概率密度函数即高斯混合概率密度函数建立模型,设计高斯混合 模型似然函数作为目标函数,通过EM算法交叉迭代出三维点云数据匹配参数,实现建筑 物边缘特征点整体匹配。在此基础上研究模型集中的随机噪声对特征点集匹配的影响。 本文研究内容: 第一章,主要叙述了点云数据特征检测及配准的研究背景和意义、研究现状及存在的 问题,通过存在问题的分析引出本文的研究目标及研究内容。 第二章,首先用二分法建立kd—tree,并实现了三维点云数据k邻域点的搜索机制,随 后研究了不同数据量下的建树时间以及kd.tree搜索k近邻的搜索时间效率问题。 第三章,利用切割最小二乘平面算法检测建筑物LiDAR点云数据特征点基础上,提 出基于条件采样的多结构估计算法,迭代搜索出所有边缘特征线特征点的直线方程,随后 采用直线寻优算法计算点到直线的距离小于阈值的点个数,点数最多的为最优的直线,并 记录所包含的特征点。为了检测同一直线上不同目标线段,在对同一直线上的点排序基础 上,利用点间距与闽值的比较来寻找同一线段上的点,以实现窗户边缘特征线的完整提取。 第四章,本章将建筑物边缘离散特征点集的配准问题转换成概率密度估计问题,用连 续的概率密度函数即高斯混合概率密度函数来建立模型,设计了高斯混合模型似然函数作 为匹配的目标函数,并通过EM算法交叉迭代出三维点云数据的匹配参数,实现建筑物边 缘特征点的整体匹配。在此基础上研究了模型集中的随机噪声对特征点集匹配的影响。 第五章总结与展望。对论文进行系统的概括及总结,并对下一步将开展的研究课题进 行展望。 6 万方数据 集美大学硕上学位论文 建筑物LiDAR点云数据特征检测及配准关键技术研究 第2章kd—tree管理点云数据 2.1问题的提出 点云数据处理受数据量的限制,因此寻求高效的空间索引方法管理点云数据显得非常 迫切。另一方面,扫描的点云数据处于离散、无序状态,这对点云数据的后续处理如:计 算点的法向信息嵋“、基于邻域点建立点的最小二乘平面等不利。因此创建点云数据的空间 拓扑关系,进而找到每一个数据点的k近邻显得非常重要。目前搜索数据点的k近邻常用 的方法有三种:规则格网、八叉树和kd—tree睛胡法。规则格网算法原理简单,适用于数据量 不大不需要进行复杂索引操作的情况。但是点云数据的数据量比较大,且用规则格网划分 点云空间,将面临单元格的间隔设置大JJ,NtJ问题。八叉树在数据量不大时能达到快速检索 的目的,但是当海量数据,且点云数据的空间分布不均匀时,会造成叶子格网中点云数据 量的不均衡,影响点云数据的检索效率,如果大幅度增加八叉树的深度,数据结构的实现 会有难度。基于上述方法的缺点,我们使用kd.tree来管理点云数据。 2.2建立kd.tree 集,小于某一分割值的那些点构成一个子集,大于某一分割值的点构成另外一个子集,子 节点就对应此划分,深度对应节点所对应的分割线。 二维情况下,建立kd.tree过程定义如下:首先,如图2—1所示,用垂线三,在根节点 处将数据集P分割为近似相等的(左、右)两个子集。分割线保存在根节点中,数据集刀,。 在分割线左侧,保存在左子树中。尸协在分割线右侧,保存在右子树中。用一条水平线在 根节点的左子处,将数据集曰,。分割为(上、下)两个子集,处于分割线以下或者在分割 线上的点保存在该数据集的左子树中;处于分割线以上的数据点,保存在该数据集的右子 树中。同理,P。也被某条水平线分割成两个子集,分别保存在该数据集的左、右子树中, 最后通过一条垂线划分根节点的每个孙子节点。通常,节点深度为偶数的用垂线划分,节 点深度为奇数的用水平线为数据集分割的过程以及对应的二分查找树。 为二叉树的递归深度,即在递归调用时对应子树根节点的深度,首次调用时,该参数设为 零。深度决定了我们究竟是使用垂线还是水平线子程序最后返回(构 造出来的)kd.tree的根节点。 万方数据 集美大学硕士学位论文 建筑物LiDAR点云数据特征检测及配准关键技术研究 ● ● ● ● ●p】幽 艮卿 ● ● ● ● ● ● ● ● ● 图2.1沿垂线L将集合P划分为规模接近的两个子集 L3 L L4 图2-2一棵kd.tree左侧所示的是对整个平面的划分,右侧为其对应的二分查找树 在三维情况下每个点都拥有三个坐标值:x坐标,y坐标和z坐标,离散点云在 即选择Z轴进行分割。计算位于Z轴坐标中问值的点,小于中间值的点位于节点的 左子树,大于中间值的点则位于节点的右子树。 表2—1建立kd—tree算法哺引 建立kd—tree算法 1nput:点集P,当前深度depth以及当前 max((.一。。一Xm。),(匕。、一匕。),(z。。一Zm。。)) Output:与P对应的kd—tree的根节点 l、if(P只包含一个点) 2、lhenreturn存储该点的叶子。 3、else if((Ⅳ。。一Xmm)为当前最大值) 4、then通过P内各点x坐标中值的垂线三,将尸划分为左右两个子集。 万方数据 集美大学硕士学位论文 建筑物LiDAR点云数据特征检测及配准关键技术研究 续表2.I 建立kd—tree算法 (记只为对应于位于£左侧或者落在三上诸点的子集。记只为对应于位 于上右侧诸点的子集。) if((K。一圪i。)为当前最大值) then沿着通过尸内各点Y坐标中值的一条垂线三,将P划分为左右两 个子集。 5、else沿着通过P内各点z坐标中值的一条水平线上,将P划分为上下 两个子集。 (记只为对应位于£下方或落在L上诸点的了集。记只为对应位于三上 方诸点子集。) 6、 ’left一BUILDKDTREE(只,depth+1)。 7、 ’i曲‘一BUILDKDTREE(只,depth+1)。 8、生成一个节点v以存储直线乙,并分别将V.。。和置成v的左右孩子。 9、retlarnv。 2.3搜索k近邻点 查找k近邻点时,保存在根节点处的分割线,将整个平面分割为两个的半平面,左子 树保存左半平面内的点,右子树保存右半平面内的点,即根节点的左、右子树分别对应于 左、右半平面。任一节点v对应的子区域是一个矩形,该矩形在某些边的方向上可能是无 当一个点落在region(v)之内时,表示该点保存在以V为根的某棵子树中。如图2.3所示, 根的子树进行查找。查找算法:对kd+tree作遍历,只访问其对应子区域与查找矩形相交的 节点。如果某个区域完全包含于查找矩形之中,找出区域中的点;若遇到一片叶子,需要 专门检测,以确定其对应的点是否落在待查找区域之内,如果是也将它找出。图2—4显示 了算法过程。如果灰色矩形为待查找区域,那么灰色的那些节点将会被访问到。那个标有 星号的节点,对应于一个完全包含于待查找区域之中的子区域(图中颜色更深区域)。于 是,遍历以此节点为根的子树后,将存储于其中的所有点都报告出来。其他被访问到的叶 子,分别对应于与待查找矩形局部相交的某一子区域,于是需要测试这一子区域所对应的 点,以确定其是否落在待查找区域之内,例如P。和P。,将会以这种方式被报告出来,而P。、 Pl,和P,;则不会报告出来。整个查找算法需要两个参数:kd—tree的根节点V,以及待查找 报告出其中所有的u十子。本文约定:lc(v)和rc(v)分别表示节点V的左、右子。 万方数据 集美大学硕士学位论文 建筑物LiDAR点云数据特征检测及配准关键技术研究 ● ● 0- ● ● ● ● ● ●● ● ● ● ● ● ● ● ● regton Z 图2.3kd.tree中各节点与平面上某一子区域的对应关系 图2.4kd.tree的查找 表2-2搜索kd.tree算法 搜索kd.tree算法 Input:kd.tree的根节点V,待查找区域R(要查询点的子区域),d/s Output:所有以1,为祖先、位于尺之内的叶子所对应的点。 l、if(V是叶子),then(要是V落在月之内,则把它报告出来) 2、else if(region(Lc(v))完全包含于尺之中) 3、then寻找kd—tree的根节点V,以及待查找区域R,并对以v为根的左 子树进行遍历,报告其中所有的叶子。 4、else if(region(Lc(v))与R相交)。 5、then寻找Lc(v)中落在尺区域中的点,并报告出来

  “原创力文档”前称为“文档投稿赚钱网”,本网站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】

http://exlei.net/tubaobijin/280.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有