基于三维激光雷达的井下巷道场景漫游系统设计*

蒋盛锋

(华中科技大学自动化学院　武汉　430074)



基于三维激光雷达的井下巷道场景漫游系统设计*

蒋盛锋

(华中科技大学自动化学院武汉430074)

为了实现井下巷道内部漫游功能,设计一种全路径漫游系统,作为快速漫游时视点运动的路径。此系统采用三维激光雷达获取井下三维点云数据,首先经过点云处理,然后经过确定下采样点邻域及计算L1中值、中线分支的建立和延展及连接,逐渐扩大邻域半径提取巷道的中心线,根据用户给定的初始结点和目标结点利用A*算法搜索最短漫游路径,实现场景漫游。结果表明,基于此系统的巷道场景漫游功能满足了大型矿山三维场景中巷道内部快速巡检的功能。

漫游; 点云; 中线; A*算法

Class NumberTP391.41

1　引言

随着计算机技术的发展,可以在计算机上利用虚拟视觉技术实现真实的世界或想象世界的三维立体空间[1]。三维场景漫游系统是一个集视、听、触觉于一体化的特定范围的虚拟环境,用户借助特定的设备如工业相机、三维激光扫描仪在该虚拟环境中漫游,从任意视角对环境中的虚拟对象进行观察和分析,从而产生身临其境的真实感觉,同时也可对观察环境中的物体进行操作来获取反馈[2]。目前通用的场景漫游方式有两种[3]:第一种交互式漫游,其通过鼠标或者触摸屏来进行平移、旋转和缩放场景。第二种是自动路径漫游[4～5],其原理是计算机根据用户提供的有关场景漫游的信息,自动形成漫游路径并按此提供的路径引导用户进行漫游,在漫游过程中,由计算机控制漫游的视觉方向和位置。

由于要提供巷道内部快速巡视的功能,所以对漫游的灵活与快捷性提供了更高的要求,现有的井下漫游方式存在几个问题[5]: 1) 交互式漫游虽然操作灵活,但是需要手动调节漫游的方向和位置,影响了漫游的效果和速度; 2) 自动漫游方式由于有漫游路径,减轻了用户手动调节方向和位置的负担,可以实现快速漫游,但路径提取算法往往比较复杂和耗时,而且漫游路径比较固定。本文提供的这种全路径式的漫游方式,先通过点云中线提取算法,能够快速精确地算出整个巷道的中线数据,然后根据用户指定的起点和终点,利用启发搜索性的A*算法进行路径规划,由于有整个巷道的中线数据,本文提供的漫游方式既保留自动漫游路径的快捷性,又保留了交互式漫游的易操作性。实验证明,此算法能够快速和精确实现巷道的巡检功能。

2　点云中线提取算法

如果把巷道模型比喻为一只多变的手,我们所需要的参考正是贯穿这只手各个部位的中心曲线。下面介绍一种基于点云模型中心线提取算法。

图1　点云模型的中线提取算法流程

2.1点云滤波

激光扫描通常会产生密度不均匀的点云数据集。另外,测量中的误差也会产生稀疏的离群点,使效果更糟。估计局部点云特征(例如采样点处法向量或曲率变化率)的运算很复杂,这会导致错误的数值,反过来有可能导致点云的中心线偏差很大。

基于PCL中的Statistical Outlier Removal滤波器,主要是对每个点的领域进行一个统计分析,并修剪掉那些不符合一定标准的点。我们的稀疏离群点的滤除方法是基于在输入数据中对点到临近点的距离分布的计算。对每个点,计算它到其所有临近点的平均距离。假设得到的结果是一个高斯分布,其形状由均值和标准差决定,平均距离在标准范围以外的点,可以把它定义为离群点就行滤除。

2.2点云稀疏化和下采样

为了更好地显示三维场景的具体细节,在进行场景三维扫描时,设置的扫描频率较高,得到的点云数据密度相对很大,这样不利于快速地计算出点云的中心线。

首先对点云数据进行基于八叉树(Octree)的稀疏处理。八叉树(Octree)[6]是一种用于描述三维空间的树状数据结构。八叉树的每个节点表示一个正方体的体积元素,每个节点有八个子节点,这八个子节点所表示的体积元素加在一起就等于父节点的体积。可以找出点云场景的最大尺寸,并以此尺寸建立第一个立方体,接着依序将单位元元素丢入能被包含且没有子节点的立方体,在将点云点丢入对应的立方体结构后,可以对临近的立方体进行融合,对应立方体中的点云点则取空间平均值,这样在保证位置变化不大的情况下,点的数量会大大下降,这就是基于八叉树点云稀疏方法的原理。

图2　八叉树结构图

其次对点云进行随机下采样。在稀疏化后的点云中随机选取采样点,这些点将作为中心线提取迭代计算的起始点。下采样点数量不同,算法计算量和稳定性也会不同。采样点数量越少,计算量就越少,越节约后面计算的时间,但是最终中心线提取算法的稳定性可能就会有所下降。

2.3点云迭代收缩进行中心点提取

点云迭代运算以及骨架点选取是算法的核心部分。其主要分为三个步骤下采样点的邻域确定及其L1中值、中线分支的建立和延展及连接、逐渐扩大邻域半径。

下采样点的邻域确定及其L1[7]中值。L1中值是p型范数的特例,给定杂乱点云集Q={qi}i∈I∈R3,下采样点集为X,求得空间一点x使得其满足argminx∑i∈I‖x-qi‖p[8～9],当p=1,该公式就是求点集中L1。具体分为六个步骤:

1) 对原始的点云数据集合J进行随机下采样,得到下采样集合I;

2) 基于邻域半径h,求点集I中的每个点xi在I中的邻点域S和J中的邻点域O;

3) 由di=1+∑t′∈I{i}e-‖pi-pi′‖2/(hd/2)2(hd为邻域半径)求点集J中每个点的密度权值di,若此为第一次迭代,还需求出点集J中的每个点的密度;若密度低于此用户定义的阈值,把该点删除;

6) 再次遍历点集I并求出每个点xi的新坐标:xi=Ri+σi*μ*Ai,其中μ为常数,人工设定。若迭代次数少于设定值,或者两次迭代间的误差大于设定值,返回第二步。

3　A*算法

A*算法是在Dijkstra算法基础上发展起来的[10],A*算法是一种启发式搜索方法。其原理是从起始节点开始,依次对当前节点的子节点的权值重新计算,并用子节点中权值最小的来更新当前节点。直至遍历所有节点为止。A*算法中核心的估价函数f(n)=g(n)+h(n);f(x)表示从起始节点到节点Dx的一条最佳路径的实际代价加上从节点Dx到目标节点的一条最佳路径的代价之和。而g(x)就是从起始节点到节点Dx之间最小代价路径的实际代价,h(x)则是从vx节点到目标节点路径的估计代价。在A*算法中h(n)的实现方法很多,不同的方法导致的算法的效率也是差别很大的。

本文所采用的启发式函数h为起始点和目标点的直线距离:

其中vb为起始节点,ve为目标节点,vbx,vby,vbz分别为起始节点的x,y,z坐标;vex,vey,vez分别为目标节点的x,y,z坐标。这种启发函数给数据搜索指引一个方向,是原来向四周圆辐射式的搜索方法变为直线式搜索,即搜索中访问的节点主要集重在vb和ve的最短路径周围,由于访问节点大大减少,搜索效率提高了。其具体步骤为

1) 首先把起点节点加入到“开启列表”中。

2) 寻找开启列表中F值最低的节点,我们把它称为当前节点,把它切换到关闭列表中。

3) 对当前节点的所有相邻节点,如果它不存在,或者已经在关闭列表中,忽略它;如果它不在开启列表中,就把它添加进开启列表,并把当前节点作为这个相邻节点的父节点,记录这一接地的F,G,H值;如果它已经在开启列表中,把G值作为参考检查新的路径是否更优,更低的G值意味着更好的路径,如果真是这样,就把这一相邻节点的父节点,改成当前节点,重新计算G和F的值。

4) 重复2)和3),直至把目标节点添加进了关闭列表,这时候路径就算被找到了,从目标节点开始,沿着每一个节点的父节点移动直到回到起始节点,输入路径。如果没有找到目标节点,开启列表已经空了,这时候表示路径不存在。

4　实验结果演示与分析

为了验证本文提出的方法的可行性和有效性,本文以从井下通过三维激光雷达采集的巷道数据,图3是原始的点云数据,经过点云处理后的点云数据,即经过点云滤波和稀疏化后,点云的数据大大减少了,为后面提取点云的中心线减少了很多时间,图4是点云提取的中心线,可以看出中心线数据能够非常准确地反应输入的模型骨架,而且提取不同模型的中心线进行分析。如表1。图5是从起始节点到目标节点的漫游路径规划。

图3　原始点云数据

图4　点云中心线数据

图5　漫游路径规划

模型原始点云处理后点云迭代次数耗时(s)机器人1025004350524630恐龙894502501030028巷道4499509195045059

从表1中可以看出,输入点云的数据级基本在十万以上,但是经过点云处理后(滤波和稀疏化)点云的数量级变为万,足见点云处理还是能非常有效减少点云的数量而且保留点云原始的特征,点云中线提取所需消耗的时间不仅跟点云的数量有关系,而且跟点云的中线提取算法中的迭代次数有直接关系。

5　结语

本文针对井下巷道需要实现内部巡检的要求,设计的一种基于中线数据的全路径漫游方式,从三维激光雷达采集过来的点云数据,经过本文采用的滤波和稀疏化处理,然后利用本文的中线提取算法能够非常快速而且光滑的自动提取点云模型的中心线数据,然后利用A*算法规划出具体的漫游路径,实现巷道内部的快速巡检。

[1] ZHOU Ke-ping, GUO Ming-ming. Virtual reality simulation system for underground mining project[C]//Proceedings of 2009 4thInternational Conference Computer Science & Education Nanning: IEEE Press,2009:615-632.

[2] 王柯.基于虚拟现实技术的三维漫游系统研究与实现[D].成都:西南交通大学,2006:9-21.

WANG Ke. Research and Implementation of Three-Dnavigating System based on Virtual Reality Technology[D]. Chengdu: Southwest Jiaotong University,2006:9-21.

[3] 尚建噶,刘修国,郑坤.三维场景交互漫游的研究与实现[J].计算机工程,2003,29(2):61-62.

SHANG jianga, LIU Xiuguo, ZHENG Kun. Research and implementation of interactive walkthrough in 3D scene[J]. Computer Engineering,2003,29(2):61-62.

[4] 吴玲达,赵健,杨冰,等.一种虚拟场景的自动漫游方法[J].小型微型计算机系统,2010,31(8):1563-1566.

WU Lingda, ZHAO Jian, YANG Bing, et al. Method for virtual scene automatic exploration[J]. Journal of Chinese Computer Systems,2010,31(8):1563-1566.

[5] 续爱民,金烨,鲍劲松.虚拟场景中自动漫游路径的多分辨率规划[J].系统仿真学报,2005,17(8):1912-1915.

XU Aimin, JIN Ye, BAO Jinsong. Navigation path muti-resolution planning in virtual environment[J]. Journal of System Simulation,2005,17(8):1912-1915.

[6] 权毓舒,何明一.基于三维点云数据的线性八叉树编码压缩算法[J].计算机应用研究,2005,22(8):70-71.

QUAN Yushu, HE Mingyi. Encoding Compression Algorithm of Linear Octree Based on Three-Dimensional Point Cloud Data[J]. Application Research of Computers,2005,22(8):70-71.

[7] Weber A. über den Standort der Industrie. Tubingen, J.C.B. Mohr (Paul Siebeck). English translation by C. J. Frei-drich (1929): Alfred Webers Theory of the Location of Industries.

[8] Avron H., Sharf A., Greif C., et al. Sparse reconstruction of sharp point set surfaces. ACM Trans. on Graph 29, 5, 135:1-135:12.

[9] Mullen P., Degoes F., Desbrun M., et al. Signing the unsigned: Robust surface reconstruction from raw pointsets[C]//Computer Graphics Forum 29,2010:1733-1741.

[10] Trovato K I, Dorst L. Differential A＊[J]. IEEE Transactions on Knowledge and Data Engineering,2002,14(6):1218.

Underground Tunnel Scene Roaming System Design Based on 3D Laser Radar

JIANG Shengfeng

(School of Automation, Huazhong University of Science & Technology, Wuhan430074)

In order to achieve the underground tunnel internal roaming function, the whole path roaming system used for the trajectory of the camera during roaming was designed. This system used the 3D laser radar to obtain three-dimensional point cloud data, first through point cloud processing, then by determining the next sampling point in the neighborhood and calculated value, and established centerline branch and extension and connection, the neighborhood radius extraction roadway centerline was expanded gradually, according to the user given initial nodes and target nodes, A* algorithm was used to search the shortest roaming path, scene roaming was realized. The results showed that, based on underground tunnel scene roaming of this system meet the large mining roadway internal three-dimensional scene fast inspection function.

roaming, point cloud, centerline, A* algorithm

2016年3月7日,

2016年4月26日

蒋盛锋,男,硕士研究生,研究方向:三维点云处理。

TP391.41DOI:10.3969/j.issn.1672-9722.2016.09.020