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

A Fast Global Normal Orientation Method for Tunnel Unordered Point Cloud Based on Priority Queue

作　　者：李纯 黄新文 周清华 薛宇腾 杨璟林 宋浩 LI Chun;HUANG Xinwen;ZHOU Qinghua;XUE Yuteng;YANG Jinglin;SONG Hao(China Railway Engineering Design and Consulting Group Co.,Ltd.,Beijing 100055,China)

机构地区：[1]中铁工程设计咨询集团有限公司,北京100055

出　　处：《铁道标准设计》2023年第10期194-201,共8页Railway Standard Design

基　　金：国家重点研发计划项目(2020YFFO304105)。

摘　　要：针对目前隧道无序点云法线全局定向方法存在的问题,提出一种基于优先级队列的快速法线全局定向方法。首先,针对传统方法采用近邻搜索方法算法复杂度为O(lgn)的问题,提出一种新的Search Data Struct(SDS)空间搜索数据结构用于近邻搜索,将算法复杂度降低到O(n),提升了海量点云的搜索效率;其次,针对传统方法计算复杂且不鲁棒等问题,提出一种新的优先级队列结构,优先级队列容纳多级类别,克服了传统方法的缺点;最后,针对传统方法需要对全局点云进行多次判断和效率低的问题,采用优先级队列策略和区域增长方法,引导点云沿着最平坦的方向进行法线定向,保证点云在奇异情况下定向正常,确保点云整体法线方向的一致性,同时每个点仅需进行一次判断即可完成定向,将算法复杂度降低到O(n),提高了法线全局定向的效率。试验结果表明,本文提出的算法效果与商业软件GeoMagic的效果相当,能够处理隧道无序点云的各种奇异情况,算法在平缓区域、尖锐特征区域和高曲率区域能得到正确的法线方向,且效率相对GeoMagic提高了14倍,大幅提升了无序点云处理的工程化水平。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.

关 键 词：隧道点云 法线定向 空间搜索结构 近邻搜索 优先级队列 

分 类 号：U25[交通运输工程—道路与铁道工程] TP391[自动化与计算机技术—计算机应用技术] U456.3[自动化与计算机技术—计算机科学与技术]