基于优先级队列的隧道无序点云快速法线全局定向方法.pdf

收稿日期:20230615;修回日期:20230713基金项目:国家重点研发计划项目(2020YFFO304105)作者简介:李 纯(1979),男,正高级工程师,2003 年毕业于武汉大学遥感信息工程学院信息工程专业,工学学士,主要从事测绘与数字化技术研发应用工作,E-mail:253893 。第 67 卷 第 10 期2023 年 10 月铁 道 标 准 设 计RAILWAY STANDARD DESIGNVol.67 No.10Oct.2023文章编号:10042954(2023)10019407基于优先级队列的隧道无序点云快速法线全局定向方法李 纯,黄新文,周清华,薛宇腾,杨璟林,宋 浩(中铁工程设计咨询集团有限公司,北京 100055)摘 要:针对目前隧道无序点云法线全局定向方法存在的问题,提出一种基于优先级队列的快速法线全局定向方法。首先,针对传统方法采用近邻搜索方法算法复杂度为 O(lgn)的问题,提出一种新的 Search Data Struct(SDS)空间搜索数据结构用于近邻搜索,将算法复杂度降低到 O(n),提升了海量点云的搜索效率;其次,针对传统方法计算复杂且不鲁棒等问题,提出一种新的优先级队列结构,优先级队列容纳多级类别,克服了传统方法的缺点;最后,针对传统方法需要对全局点云进行多次判断和效率低的问题,采用优先级队列策略和区域增长方法,引导点云沿着最平坦的方向进行法线定向,保证点云在奇异情况下定向正常,确保点云整体法线方向的一致性,同时每个点仅需进行一次判断即可完成定向,将算法复杂度降低到 O(n),提高了法线全局定向的效率。试验结果表明,本文提出的算法效果与商业软件 GeoMagic 的效果相当,能够处理隧道无序点云的各种奇异情况,算法在平缓区域、尖锐特征区域和高曲率区域能得到正确的法线方向,且效率相对 GeoMagic 提高了 14 倍,大幅提升了无序点云处理的工程化水平。关键词:隧道点云;法线定向;空间搜索结构;近邻搜索;优先级队列中图分类号:U25;TP391;U456.3 文献标识码:A DOI:10.13238/j.issn.1004-2954.202306150004A Fast Global Normal Orientation Method for Tunnel Unordered Point Cloud Based on Priority QueueLI Chun,HUANG Xinwen,ZHOU Qinghua,XUE Yuteng,YANG Jinglin,SONG Hao(China Railway Engineering Design and Consulting Group Co.,Ltd.,Beijing 100055,China)Abstract:The paper proposes a fast global normal orientation method based on a priority queue,aiming to address the problems existing in current unordered point cloud normal estimation methods for tunnels.Firstly,a new Search Data Struct(SDS)spatial search data structure is introduced to replace the traditional nearest neighbor search method,reducing the algorithm complexity from O(lgn)to O(n)and significantly improving the search efficiency for massive point clouds.Secondly,a novel priority queue structure is proposed to overcome the drawbacks of computational complexity and lack of robustness in traditional methods.The priority queue accommodates multiple priority levels,enhancing the performance of the method.Lastly,a combination of priority queue strategy and region growing method is utilized to guide the normal orientation along the flattest direction,ensuring the correct orientation of point clouds even in singular cases and maintaining the consistency of normal directions.With this approach,each point only needs to be evaluated once,reducing the algorithm complexity to O(n)and greatly improving the efficiency of global normal orientation.Experimental results demonstrate that the proposed method achieves comparable results to the commercial software GeoMagic,effectively handling various singular cases in tunnel point clouds.The algorithm produces accurate normal directions in flat areas,sharp feature areas,and high curvature areas,with a 14-fold improvement in efficiency compared to GeoMagic.This significantly enhances the engineering level of unordered point cloud processing.Key words:tunnel point cloud;normal orientation;SDS;nearest neighbor search;priority queue引言随着激光扫描设备的发展,点云数据在铁路隧道的数字化建设和运营维护中得到了广泛应用1-4。定向过程可以确保隧道点云中的点按照正确的方向和顺序进行排列,有助于准确重建隧道的几何形态和结构,包括隧道截面、几何特征和形状。精确的几何重建对于隧道的状态检测、维护非常关键。利用无序点云数据进行点云模型绘制、光顺以及曲面重建等数据处理是以得到无序点云的法线为前提条件。点云法线作为点云数据的基本几何属性,在点云配准5、点云分割6-7和点云重建8中发挥着极其重要的作用。点云法线计算可以分为法线估算和法线全局定向两个步骤。点云法线的估算主要采用协方差分析法9等,该方法对各点的邻域拟合微切平面,将微切平面的法线作为该点的法线,但估算出的法线部分区域指向点云曲面的一侧,部分区域指向另一侧法线,这势必会引起后续相关数据处理的混乱,无法直接应用于后续的点云配准、分割、重建和识别等应用中。为便于后续的数据处理,需要对法线方向进行调整,使得所有点的法线都指向点云曲面的同一侧,该过程称为点云的法线全局定向,而对隧道无序点云的法线全局定向引起了国内外众多学者的广泛关注。法线全局定向方法主要包括直接定向法10-12、最小生成树法(Minimum Spaning Tree,MST)13、光度立体视觉法14-16和曲面重建法17-19。直接定向法需要测量数据点是矩形阵列或者点云与测站的相互位置关系,算法简易鲁棒20,但是对数据依赖,局限性比较大,无法直接用于隧道无序点云的全局定向。最小生成树法是应用最为广泛的法线全局定向算法21。算法随机选取一个种子点,然后沿着一个较平坦的路径来遍历点云的最小生成树(MST),调整路径上点的法线,使得相邻点的法线内积为正,该算法调整一个法线需遍历全部点云,效率低,不适用于处理大规模点云,另外算法在点云中存在奇异情况(薄壁、垂直、相邻曲面等)时,容易出现错误,因此算法几乎不存在实际工程应用的价值22。为此,许多旨在提高MST 生成效率和处理奇异情况的改进方法被提出,实现方法包括 Riemannian 图23、点云分块24、边界区分“平坦点”和“非平坦点”25-27等。通过缩小传播法线搜索范围、增加每次法线传播个数、同时考虑了奇异情况下的法线定向方式等策略改进了 MST 算法,提高了传播效率,但是在高曲率区域和奇异情况,法线方向传播容易出错,效率提升效果也有限。文献28-30采用一定算法区分平缓点和非平缓点,并通过判断采样点的邻域点内是否存在非平缓点而采取不同的法线定向方式,法线定向效率有所提高,但分类类别有限,阈值设定比较困难,因此算法适用范围非常有限。上述MST 的各种改进算法部分解决了奇异情况的定向错误,但仍旧无法解决最本质的问题 运算效率低、耗时长,因此在实际工程应用中也存在一定问题。光度立体视觉法利用曲面反射与光照几何等先验信息来计算曲面法线,曲面上一点的法向通过 3 个或3 个以上的光源照射来确定,但算法易受镜面反射、材料伪影以及相互遮挡的影响,需要利用相当多的先验知识,受外界影响较大,算法稳定性差,对于低质量的点云很难得到完全一致的法线调整结果。曲面重建法31用重采样后原始点云的均匀分布的法线调整点云法线,能够对具有相邻曲面、薄壁特征等奇异情况的点云进行正确的法线调整,但算法中模型重采样和近似结构的法线计算都是曲面重建的必要步骤,处理流程复杂,运算效率比最小生成树更低,耗时较多,工程化应用价值也不大32。总的来说,传统无序点云法线全局定向方法存在以下不足33-35。(1)上述方法皆采用 K-D 树、八叉树等近邻方法,算法复杂度为 O(lgn),在无序点云量较大的情况下,仍存在较大的计算量,因此很多改进算法皆采用缩小搜索空间以提高效率,导致定向效果不鲁棒。(2)点云奇异情况下,法线定向容易出问题,上述改进方法计算复杂、分类类别有限且不鲁棒。(3)上述方法运算往往需要对全局点云进行多次判断和运算,效率低、耗时过长,不利于工程化应用。1 算法描述1.1 空间搜索数据结构1.1.1 搜索数据结构构建SDS 搜索结构的构建与基于空间划分搜索结构的构建类似。对于点云 Pp1,pn,其点云索引为1,np,其中 np为点云数,计算其空间包围盒,然后将其划分为空间立方体网格。其中,立方体网格的边长d 通过点云的密度参数 估计。=np/nbox(1)式中,np为点云数;为点云密度;nbox为立方体网格数。当指定网格密度(默认=0.5)时,可得到立方体网格数 nbox。通过统计点云 P 各方向上的最大、最小值,可求出其空间包围盒的体积 VV=(xmax-xmin)(ymax-ymin)(zmax-zmin)(2)591第 10 期李 纯,黄新文,周清华,等基于优先级队列的隧道无序点云快速法线全局定向方法 式中,xmin,xmax分别为点云 P 在 x 方向上的最小值与最大值;ymin,ymax分别为点云 P 在 y 方向上的最小值与最大值;zmin,zmax分别为点云 P 在 z 方向上的最小值与最大值。通过空间包围盒的体积 V 与立方体网格数 nbox,求得空间划分的立方体网格边长d=3Vnbox(3)因此,点云 P 中每个点 pi(xi,yi,zi)都可以按哈希函数运算后分配到相应的立方体网格中boxid=xi-xmind+yi-ymindnx+zi-zmindnxny(4)式中,xi,yi,zi为点坐标。nx,ny为按边长 d 及沿 x,y 方向划分的网格数,计算方法如下nx=xmax-xmind(5)ny=ymax-ymind(6)boxid实现了点云 P 中的每个点 pi到一个 box 的转化,而且点云 P 在一个 box 中是按1,np的顺序进行存储。SDS 的数据结构极其简单仅为两个不同的数组First 和 Next,其中 First 的长度为 nbox(点云 P 划分的立方体网格数),First 的 ith 行存储着对应的 ithbox 中所有点云的最小索引,-1 用于标记空 box。Next 的长度为 np(点云数),对于 Next 的 jth 行表示该在 ithbox 中,其值为与该点相邻的下一个点的索引,-1 表示其为ithbox 中的最后一个点。如图 1 所示,利用 SDS 的数据结构就可以简单且快速地获取同一个 box 中的所有点idPoint=NextIdPoint(7)图 1 SDS 数据结构示意Fig.1 SDS data structure diagram1.1.2 k 近邻搜索SDS 数据结构的 k 近邻搜索,先构建长度大小为 k的距离数组 distance 和索引数组 idc,因 SDS 的数据结构是将点云 P 中所有点与空间立方体网格相对应,其搜索实质上是网格搜索(BoxSearchK),在网格内搜索满足条件的点。首先,计算输入点pi在x、y、z 各方向轴上的索引idx、idy、idz与偏移量 offsetUp,offsetDown,其计算方法如下idj=(pj-minVj)/d(8)offsetUp=pj-(minVj+idjd)(9)offsetDown=minVj+idjd-pj(10)式中,j=x,y,z代表 x、y、z 三个方向;minVj为 x、y、z 三个方向上的最小值。然后,进行 BoxSearchK 搜索,BoxSearchK 搜索时先根据 idx、idy、idz计算出当前点 pi的立方体网格序号id,在 First id 得 到 对 应 的 点 云,通 过 idPoint=NextIdPoint遍历当前立方体内的所有点,计算其距离 dist 并与 distance 中的值进比较,得到满足条件的点,并取 distance 第一个值作为最小距离 mindist。再次,循环地对立方体的六个方向分别执行 Box-SearchK 搜索,对每个方向是否搜索按偏移量 offsetUp,offsetDown 进行判断,仅对 offsetUp mindist 或 offset-Downmindist且 offsetDownmindist 时搜索结束。1.2 优先级队列对于基于优先级队列的法线定向其核心在于优先级队列 L 的构建。此处选择两点法线夹角大小作为每个点法线定向的优先级别。法线夹角的绝对值范围在0,PI2()内,将该范围按给定的优先级别数 k 进行均匀划分,创建优先级阀值表 level,当夹角值位置于 level 中某一范围时,其索引即为其优先级别,其计算公式如下leveli=cos(PI/2)/k(i+1)(11)优先级队列 L 的结构如图 2 所示,主要包含:一个基础队列 queuesz,用于记录点云索引,其队列中记录的点云按优先级顺序排列,队尾优先级最低,队头优先级最高,优先级内部的点无顺序差异,sz 等于点云数目;一个地址队列 Firstk,用于记录每个优先级在队列 queue 中第一个元素位置,k 即角度阈值数目;一个变量 iq 用于记录队头位置。图 2 优先级队列结构示意Fig.2 Priority queue structure diagram如图 3 所示,最高优先级别点导入优先级队列 L,691铁 道 标 准 设 计第 67 卷对于最高级别点 pmax其索引为 id,首先令 iq=0 指向队头,再将 queueiq=id,First0=0,队列队头第一个即为最高优先级别点(为全局法线调整初始点)。图 3 最高优先级别点导入优先级队列示意Fig.3 Diagram of importing priority queues at the highest priority point对于一般点插入优先级队列的流程如图 4 所示,以导入点优先级为 1 的情况为例,对于一般点 p,其索引为 id。首先 iq+队列中数据增加,将 queueiq=queueFirst0即为将队列中原首元素赋给新增加的空间,First0+指向调整后的原首元素相信点,queueFirst0-1=id,将插入点插入到基础队列。图 4 一般点插入优先级队列示意Fig.4 General point insertion priority queue diagram导入一般点为其他优先级时,插入过程同理,只移动每个优先级内的首元素,先高优先级再低优先级,依次向队头方向移动,直至插入点对应优先级最靠近队头的一端空出,将待插入点索引赋给该空闲元素,即完成一般点的导入操作。从优先级队列 L 中取出一个优先级最高的点的索引值 H,其优先级队列导出流程如图 5 所示,首先 H=queueiq导出优先级最高的点,iq-点数减少,然后调整 优 先 级 地 址 队 列 First,当 First i iq 时,Firsti=iq;否则 Firsti值不变。1.3 快速法线全局定向基于优先级队列的法线定向,对于点云 P 和法线Nn1,nn创建标记数组 Bb1,bn置为 false,其长度为点云数。对每个点 pi进行 k 近邻搜索得到邻域点 Qq1,qk,计算邻域点 Q 中的每一个点 qj在图 5 导出优先级最高点示意Fig.5 Derive a diagram of the highest prioritypi上的投影模长 Mm1,mk,并求其平均值,投影模长的计算公式如下mj=fabs(qj-pi)ni)(12)选择投影模长平均值最小的点作为种子点 s,该点即为全局最平坦的局部区域,引导点云沿着最平坦的方向进行法线定向,保证点云在奇异情况下定向正常,确保点云整体法线方向的一致性。将种子点 s 加入优先级队列中,并将其优先级设置为最高,定向其法线令其法线朝向与(0,0,-1.0)与一致,法线的定向公式如下val=nsnd(13)式中,ns为参考点法线,当前点为种子点 s 时,ns=(0,0,-1.0);nd为待定向点法线,当前点为种子点 s时,nd为种子点 s 的法线。val0 时表示法线方向一致无需定向,当 val0 时表示法线方向相反,需要进行定向,定向计算公式如下nd=nd(-1)(14)然后,导出优先级队列 L 中当前优先级别最高的点 pmax,通过标记数组 B 判断其邻域点 Q 是否已经遍历过。如果未遍历,则与 pmax进行法线定向并计算其优先级别加入优先级队列 L,将 Bi=true;如果已经遍历过,则判断邻域点 Q 中的下一个点,直到遍历完邻域点 Q 中所有点。再导出优先级队列 L 中当前优先级别最高的点再进行判断,直到所有点都已经遍历。算法流程见图 6,其过程包括以下步骤。步骤 1,构建空间搜索数据结构 SDS。步骤 2,无序点云法向定向数据结构的初始化。创建与点云数目相同的索引优先级队列 L 及标记数组B(默认值为 False),同时根据角度阈值数目 N 构建优先级阈值表 T。优先级队列 L 数据结构的设计加速了队列元素的导入和导出。步骤 3,选取法线定向种子点。(1)遍历寻找 z 值最小的点,选取该点作为初始种子点 S,并令种子点 S 的法线朝向与(0,0,-1.0)一致。(2)将种子点 S 的优先级设置为最高级,并将种子点 S 的索引值导入优先级队列 L 中,在标记数组 B791第 10 期李 纯,黄新文,周清华,等基于优先级队列的隧道无序点云快速法线全局定向方法图 6 算法流程Fig.6 Flow diagram of algorithm中将种子点 S 标记为 True。步骤 4,基于优先级队列选择区域增长方向并调整法线方向。引入优先级策略结合优先级队列数据结构,将法线定向算法的计算复杂度降至线性复杂度,大大加速了定向速度。(1)从优先级队列 L 中取出一个优先级最高点的索引值 H。(2)根据 SDS 的 k 近邻算法搜索参考点 H 的 k 近邻点,判断标记数组 B 中 k 近邻点是否调整过方向,若为 True,则返回步骤 4.1,否则继续进行。(3)遍历未调整过法线方向的近邻点,令近邻点的法线方向与参考点 H 的一致,并计算近邻点的优先级向优先级队列中导入索引,在标记数组 B 中将近邻点标记为 True。(4)判断优先级队列 L 是否为空,若不为空,则返回步骤 4.1。(5)遍历标记数组 B,获取未处理的点 S,标记True,并导入到优先级队列 L,返回步骤 4.1 循环处理,直至标记数组 B 中所有值均为 True 结束。从上述算法流程可以看出,较传统无序点云法线定向方法,本文提出的方法拥有 3 点显著优势。第一,引入 SDS 空间搜索数据结构,将 k 近邻搜索算法复杂度从 O(lgn)提升到 O(n)。第二,对点云奇异的处理,传统方法需要特征提取等较为复杂的处理,导致定向不够鲁棒,而本文提出的方法采用了优先级和区域增长策略,算法简洁、易实现且通用性强,在提高效率的情况下确保了奇异情况下定向的鲁棒性。第三,在运算效率方面,本文提出的定向方法显著优于传统方法。传统方法处理点云耗时较长,无法应用于生产实践,但本算法基于新设计的优先级队列结构,将计算复杂度降至线性复杂度 O(n),极大地加速了法线定向过程,可以直接用于生产实践。2 试验结果与分析2.1 数据准备实验采用实际激光扫描得到的 6 段隧道点云进行测试,如图 7 所示,测试数据都先进行了法线估算。从图 7 中可以看出,经过法线估算后,点云具有了法线,但是由于估算并未涉及法线的方向,所以法线存在定向错误的情况,需要进行全局定向。图 7 测试数据示意Fig.7 Test data diagram对比方法采用与 Geomagic 进行比较。GeoMagic作为目前商用程度化最高、使用范围最广、效果与速度最优的商用软件,一直以来是行业的标杆,因此,作为本文算法的效率与效果的对比参考。2.2 效率对比分别采用 GeoMagic 和本文算法对 6 段隧道点云进行点云法线全局定向,并统计耗时,其效率对比分析如表 1 所示。从表 1 可以看出,本文算法相比较于 GeoMagic 算法,效率有了大幅提升,运算速度快了近 20 倍。从6 组数据看,速度对比都比较均衡,GeoMagic 构建速度约为 5 万点/s,本文算法构建速度约为 70 万点/s,本891铁 道 标 准 设 计第 67 卷文算法效率是 GeoMagic 的 14 倍,极大提升了工程化水平。表 1 GeoMagic 与本文算法效率对比Table 1Comparison of Efficiency between GeoMagic and the Proposed Algorithm数据名称点数时间/s处理速度(万点/s)GeoMagic本文算法GeoMagic本文算法Pcd-1_0152846928.772.0565.31374.342Pcd-1_1133413924.861.8255.36773.104Pcd-1_2141534327.251.945.19472.956Pcd-1_3106773620.021.4255.33374.929Pcd-1_4141551732.451.9774.36271.599Pcd-1_5111369420.841.5025.34474.1472.3 效果对比分别对 6 段隧道点云进行点云法线全局定向,并对比定向前、GeoMagic 和本文算法定向效果,如图 8 所示。图 8 法线全局定向效果对比Fig.8 Normal global orientation effect comparison从图 8 可以看出,二者都能够处理隧道无序点云的各种奇异情况,算法在平缓区域、尖锐特征区域和高曲率区域均能得到正确的法线方向。二者对于隧道点云的定向各有优缺点,Pcd-1 _0 和 Pcd-1 _2 中,GeoMagic 对于轨道定向效果优于本文算法,本文算法存在对轨道区域部分反向情况;Pcd-1_4 中,本文算法优于 GeoMagic,GeoMagic 对右边的隧道壁出现整个面反向的情况;Pcd-1_3 中,GeoMagic 对于轨道面出现定向相反的情况;Pcd-1_5 中,本文算法对于轨道面出现定向反了的情况。整体来说,本文算法的定向效果与商业软件 GeoMagic 的效果相当,说明本文算法的效果足够用于工程化与商业化应用。3 结论提出一种基于优先级队列的隧道无序点云快速法线全局定向方法,通过建立优先级队列区分不同特征、构建特殊的空间搜索数据结构来提高法线定向的准确性与效率,为隧道施工、运维提供了可靠的数据基础。提出一种新的空间搜索数据结构和一种新的优先级队列结构用于近邻搜索,可以容纳多级类别,提高了搜索效率和计算方法的鲁棒性,并且构建了一套针对无序点云法线全局定向的区域增长策略,大大提高了法线全局定向的效率。试验结果表明,本文算法能够获取正确的法向定向结果,在和 GeoMagic 效果接近情况下,效率提升 14 倍。由于采用了区域增长策略和串行处理方式,因此如何利用多重判据进一步提高算法鲁棒性和将算法并行化是将来此算法的研究重点。参考文献:1 MAO Q Z,CUI H,HU Q W,et al.A Rigorous Fastener Inspection Approach for High-speed Railway from Structured Light SensorsJ.ISPRS Journal of Photogrammetry and Remote Sensing,2018,143:249-267.2 YANG B S,FANG L N.Automated extraction of 3-D Railway Tracks from Mobile Laser Scanning Point CloudsJ.IEEE journal of select-ed topics in applied earth observations and remote sensing,2014,7(12):4750-4761.3 CUI H,REN X C,MAO Q Z,et al.Shield subway Tunnel Deforma-tion Detection Based on Mobile Laser ScanningJ.Automation in Construction,2019,106:102889.4 熊智敏.城市轨道服役状态检测系统关键技术研究D.武汉:武汉大学,2017.XIONG Zhimin.Research on Key Technology of Urban Track Service State Detection SystemD.Wuhan:Wuhan University,2017.5 陶海跻,达飞鹏.一种基于法向量的点云自动配准方法J.中国激光,2013,40(8):184-189.TAO Haiji,DA Feipeng.Automatic Registration Algorithm for the Point Clouds Based on the Normal VectorJ.Chinese Journal of La-sers,2013,40(8):184-189.6 董震,杨必胜.车载激光扫描数据中多类目标的层次化提取方法J.测绘学报,2015,44(9):980-987.991第 10 期李 纯,黄新文,周清华,等基于优先级队列的隧道无序点云快速法线全局定向方法DONG Zhen,YANG Bisheng.Hierarchical Extraction of Multiple Ob-jects from Mobile Laser Scanning DataJ.Acta Geodaetica et Carto-graphica Sinica,2015,44(9):980-987.7 张强,李朝奎,李俊晓,等.一种改进的基于法矢方向调整的平面点云分割方法J.地理与地理信息科学,2015,31(1):45-48.ZHANG Qiang,LI Chaokui,LI Junxiao,et al.Planar Point Cloud Segmentation Based on the Weighted Average of Adjusted Normal VectorJ.Geography and Geo-Information Science,2015,31(1):45-48.8 方悄云,吕东辉,孙九爱.改进的物体表面重建的三角网格法J.应用科学学报,2016,34(2):145-153.FANG Qiaoyun,L Donghui,SUN Jiuai.Improved Triangle Mesh Method for Surface Reconstruction from Normal FieldJ.Journal of Applied Sciences,2016,34(2):145-153.9 HOPPE H,DEROSE T,DUCHAMP T,et al.Surface Reconstruc-tion from Unorganized PointsJ.ACM SIGGRAPH Computer Graph-ics,1992,26(2):71-78.10 易传云,王涛.数字化曲面的法矢求解J.华中科技大学学报(自然科学版),2002(8):49-51.YI Chuanyun,WANG Tao.Solution of the Normal Vector on Digital-ized SurfaceJ.Journal of Huazhong University of Science and Tech-nology,2002(8):49-51.11 刘雪梅,冯跃志.空间离散点曲面法矢估算的一种新方法J.华北水利水电学院学报,1994(4):64-66.LIU Xuemei,FENG Yaozhi.A Kind of New Method for Calculating Surface Normal Vector of Space Discrete PointsJ.Journal of North China Institute of Water Conservancy and Hydroelectric Power,1994(4):64-66.12 邓勇,张宇,杨振,等.基于人工标志法点云数据配准精度与标志相互位置的关系分析J.测绘通报,2016(S2):231-233,237.DENG Yong,ZHANG Yu,YANG Zhen,et al.Analysis of the Rela-tionship between the Registration Accuracy of Point Cloud Data and the Mutual Position of Marks Based on Artificial Marking MethodJ.Bulletin of Surveying and Mapping,2016(S2):231-233,237.13 贺美芳.基于散乱点云数据的曲面重建关键技术研究D.南京:南京航空航天大学,2006.HE Meifang.Research on Key Technologies of Sufaces Reconstruction Based on Scattered Point Cloud DataD.Nanjing:Nanjing Univer-sity of Aeronautics and Astronautics,2006.14 SUN J A,SMITH M,SMITH L,et al.Examining the Uncertainty of the Recovered Surface Normal in Three Light Photometric StereoJ.Image and Vision Computing,2007,25(7):1073-1079.15 MA W C,HAWKINS T,PEERS P,et al.Rapid Acquisition of Specular and Diffuse Normal Maps from Polarized Spherical Gradient IlluminationCProceedings of the 18th Eurographics conference on Rendering Techniques.Grenoble,France.New York:ACM,2007:183-194.16 HUANG H,LI D,ZHANG H,et al.Consolidation of Unorganized Point Clouds for Surface ReconstructionJ.ACM Transactions on Graphics,2009,28(5):1-7.17 LIU S J,WANG C C L.Orienting Unorganized Points for Surface Re-constructionJ.Computers&Graphics,2010,34(3):209-218.18 曾锋,钟治初,杨通,等.基于 SOM 的散乱点云法矢计算J.计算机工程,2012,38(8):287-290.ZENG Feng,ZHONG Zhichu,YANG Tong,et al.Scattered Point Cloud Normal Vector Calculation Based on SOMJ.Computer Engi-neering,2012,38(8):287-290.19 MULLEN P,DE GOES F,DESBRUN M,et al.Signing the Un-signed:Robust Surface Reconstruction from Raw PointsetsJ.Com-puter Graphics Forum,2010,29(5):1733-1741.20 易倩宇.高质量鲁棒曲面重建D.杭州:浙江大学,2014.YI Qianyu.High Quality Robust Surface ReconstructionD.Hang-zhou:Zhejiang University,2014.21 张剑清,李彩林,郭宝云.基于切平面投影的散乱数据点快速曲面重建算法 J.武汉大学学报(信息科学版),2011,36(7):757-762.ZHANG Jianqing,LI Cailin,GUO Baoyun.A Fast Surface Recon-struction Algorithm for Unorganized Points Based on Tangent Plane ProjectionJ.Geomatics and Information Science of Wuhan Univer-sity,2011,36(7):757-762.22 刘健.可修正的点云一致定向D.大连:大连理工大学,2014.LIU Jian.Mendable Consistent Orientation of Point Clouds D.Dalian:Dalian U