基于RANSAC的地下矿山巷道边线检测算法

doi:10.11872/j.issn.1005-2518.2020.01.043

基于RANSAC的地下矿山巷道边线检测算法

毕林^,¹^,², 段长铭^,¹^,², 任助理¹^,²

1.中南大学资源与安全工程学院，湖南长沙 410083

2.中南大学数字矿山研究中心，湖南长沙 410083

Roadway Edge Detection Algorithm Based on RANSAC in Underground Mine

BI Lin^,¹^,², DUAN Changming^,¹^,², REN Zhuli¹^,²

1.School of Resources and Safety Engineering，Central South University，Changsha 410083，Hunan，China

2.Center of Digital Mine Research，Central South University，Changsha 410083，Hunan，China

通讯作者: 段长铭（1995-），男，河南洛阳人，硕士研究生，从事数字矿山和铲运机定位等方面的研究工作。Changming_duan@163.com

收稿日期: 2019-05-05 修回日期: 2019-09-17 网络出版日期: 2020-03-06

基金资助:

国家自然科学基金项目“基于深度学习和距离场的复杂金属矿体三维建模技术研究”. 41572317

Received: 2019-05-05 Revised: 2019-09-17 Online: 2020-03-06

作者简介 About authors

毕林（1975-），男，四川通江人，副教授，从事GIS、数字矿山和铲运机无人化等方面的研究与软件开发工作Mr.BiLin@163.com , E-mail：Mr.BiLin@163.com

摘要

巷道边线是井下铲运机反应式导航系统中重要的感知信息。为了准确可靠地在井下环境中感知巷道边线，提出一种基于二维激光扫描信息和随机抽样一致性（RANSAC）的巷道边线检测算法。首先计算每个激光点的曲率，根据曲率阈值将激光点云划分为多个区域；然后基于RANSAC从每个区域提取直线，并根据铲运机航向角及巷道的设计标准进行筛选；最后合并筛选后的激光点云数据，使用RANSAC算法生成最终的巷道边线。基于地下矿山6种典型的巷道场景对算法效果进行验证，结果显示提取的巷道边线可靠度均达到96%以上，且算法具有很高的实时性和稳健性。

关键词： 井下铲运机 ; 激光雷达 ; 随机抽样一致性 ; 巷道边线检测 ; 反应式导航 ; 地下矿山

Abstract

Because the working environment of underground LHD（load-haul-and-dump-machine）is very bad，and with the increase of mining depth in underground mines，the realization of underground unmanned LHD is of great significance for ensuring the safety and health of workers and improving the production efficiency of mining enterprises.Navigation and positioning of LHD is one of the difficulties in the research of unmanned LHD.At present，the navigation technology of underground LHD mainly includes plan-based metric navigation and reactive navigation.The reactive navigation technology has the advantages of low cost and low computation.The former reactive navigation technology mainly relies on adding beacons manually，it has the shortcomings of high cost and poor adaptability.The roadway edge is an important natural beacon perception information，which has natural advantages compared with the artificial beacon.Foreign scholars had applied it to the reactive navigation system of underground LHD and achieved good navigation effect.However，they only did the research on the detection of the roadway edge in the straight roadway，no further discussion on the detection of roadway edge in more complex underground environments.Therefore，a more applicable roadway edge detection algorithm is proposed in this paper.This method is based on two-dimensional laser scanning information and random sampling consistency (RANSAC).The flow chart of the algorithm is as follows：Firstly，the curvature of each laser point in the laser point cloud is calculated，according to the curvature threshold，the laser point cloud data are divided into several regions.RANSAC algorithm is used to extract the roadway edges from each region.Then，the roadway edges are filtered according to the heading angle of the LHD and the design criteria of the roadway.Lastly，the laser point cloud data contained in the remaining roadway edges is merged，and the final roadway edges is generated by RANSAC algorithm again.This article simulated the laser data of six underground mine roadway scenarios，and these six sets of data included typical scenes from simple to complex in underground mine.The experiment was based on MATLAB，and the experimental results were analyzed from the aspects of parallelism，proportion of interior points，fit degree with heading angle，visual display and so on.The calculated results show that the reliability of the extracted roadway edges is more than 96%，and the visual results are in line with the actual situation.This method can detect roadway edge in various scenarios of underground mines，and has high robustness，the roadway edge detection algorithm can play an important technical support role in the reactive navigation of underground LHD，and is of great significance to the realization of the unmanned underground LHD.

Keywords： underground LHD ; lidar ; random sampling consistency ; roadway edge detection ; reactive navigation ; underground mine

PDF (1125KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

毕林, 段长铭, 任助理. 基于RANSAC的地下矿山巷道边线检测算法[J]. 黄金科学技术, 2020, 28(1): 105-111 doi:10.11872/j.issn.1005-2518.2020.01.043

BI Lin, DUAN Changming, REN Zhuli. Roadway Edge Detection Algorithm Based on RANSAC in Underground Mine[J]. Gold Science and Technology, 2020, 28(1): 105-111 doi:10.11872/j.issn.1005-2518.2020.01.043

井下铲运机的工作环境存在粉尘大、噪音多和通风差等问题^[1]，而且随着地下矿山开采深度逐渐增加，井下高温、高地压和高岩溶水压的“三高”问题也将更加严重。这些因素对铲运机操作人员的身体健康、生命安全及工作效率都有很大影响，所以研究井下铲运机的自主导航具有重要意义。

目前，井下铲运机的自主导航主要有绝对导航和反应式导航2种方案。相对于绝对导航，反应式导航的优点是不需要精确的度量地图，也不需要事先记录和定义路线，数据计算量小，管理和规划导航路径更加方便^[2]。井下铲运机反应式导航的研究由来已久。国外学者曾提出基于顶板反光带、感应电缆和顶板绘线等感知信息的反应式导航技术^[2]，但是这些方法完全依靠人工添加信标，具有设备设施投资大、对矿山变动性环境适应差等缺点。目前主流的井下铲运机反应式导航技术主要基于“沿壁法”^[3,4,5,6,7]，同时依靠自然信标和人工信标，而巷道边线是井下可靠度很高的自然信标。

井下最理想的信息感知传感器是激光雷达，检测巷道边线的本质是基于传感器信息对巷道环境进行特征提取^[8]，特征提取常用的方法有Least Squares Technique算法^[9]、Hough Transform算法^[10]和RANSAC算法^[11]等。Larsson等^[12]曾提出基于Hough Transform原理的井下巷道边线检测方法，但只对简单的直行巷道进行了研究，没有对其他井下复杂场景展开讨论。国内学者对井下铲运机自主导航的研究起步较晚，没有关于井下巷道边线检测的研究，但是一些地面无人驾驶领域的车道线检测算法可以作为参考^{[13,14,15,16]}。

本文提出了一种基于二维单线激光雷达扫描信息和随机抽样一致性的井下巷道边线检测方法，通过考虑矿山井下巷道环境的特点及复杂性，提高算法在多种类型巷道环境下的稳健性和准确度。文中阐述了该方法的数学原理及算法实现流程，并通过6组激光模拟数据对算法的效果进行了验证及分析。

1 基于RANSAC的巷道边线提取

1.1 随机抽样一致算法原理

随机抽样一致算法（RANSAC，Random Sample Consensus）最早由Fischler等^[11]于1981年提出，主要用来处理包含异常数据、噪声和离群数据的观测数据，通过迭代的思想求解最优数学模型。随机性和假设性是RANSAC算法的核心。其中，随机性是对所有数据进行随机抽样，结合抽中正确数据的概率，基于大数定律得到近似的正确结果；假设性是假设每一次随机抽取的抽样数据是正确的，并由抽取的数据确定模型参数，然后将该模型应用于其他数据，根据符合该模型的数据量判断结果的好坏。RANSAC算法广泛应用于数学和计算机视觉等领域，除了基础的RANSAC算法，还有很多优化版本，可以解决直线拟合、平面拟合、点云或图像匹配及帧间变换矩阵计算等问题^[17]。

RANSAC算法的数学推导过程如下：

首先，假设数据集中内点占所有数据的比例为t，有

t = \frac{n_{i n l i e r s}}{n_{i n l i e r s} + n_{o u t l i e r s}}

(1)

式中： $n_{i n l i e r s}$ 为内点数量； $n_{o u t l i e r s}$ 为外点数量。

然后，假设用RANSAC算法求解的数学模型需要的点数为n。n的值由求解的问题确定，如求解直线模型时n为2，求解平面模型时n为3。则用RANSAC算法解得正确模型的概率P为

P = 1 - (1 - t^{n})^{k}

(2)

式中：k为迭代次数，表示每次随机选取n个点进行解算，重复k次； $t^{n}$ 为从数据集中随机选取n个点，且这n个点全是内点的概率。

由于内点所占比例t是一个先验值，且是未知数，所以通常先赋给t一个经验值。根据式（2），可得t和迭代次数k共同影响RANSAC算法求得正确模型的概率，如果赋给t的经验值与真实值偏差过大，可以通过调整迭代次数来保证算法的准确度P，迭代次数k由以下公式得出：

k = \frac{l o g (1 - P)}{l o g (1 - t^{n})}

(3)

式中：P为算法的目标准确度；k为迭代次数；t为内点占比。

1.2 基于RANSAC的巷道边线提取流程

基于RANSAC的巷道边线提取流程如图1所示。首先使用二维单线激光雷达收集激光点云数据，并计算每个激光点的曲率，在曲率超过阈值的点处，将激光点云划分为前、后2个区域；然后运用RANSAC算法从各个区域中提取巷道边线，并且根据铲运机航向角和巷道设计标准对生成的直线进行筛选；最后合并筛选过后的激光数据，再次应用RANSAC算法，生成最终的巷道边线，并从平行度等方面计算巷道边线可靠度。

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 基于RANSAC的巷道边线检测流程

Fig.1 Roadway edge detection process based on RANSAC

步骤1：计算激光点曲率

公式如下：

c = \frac{1}{|S| \cdot ‖X_{(k, i)}^{}‖} ‖\sum_{j \in S, j \neq i} (X_{(k, i)}^{} - X_{(k, j)}^{})‖

(4)

式中：k为激光雷达的第k扫描帧；X为激光点坐标的集合；S为由i点及其前后等量若干j点组成的点集；c值为i点的曲率大小^[18]。本文中点集S共包含11个点，即在i点左右各取5个j点。

步骤2：根据激光点曲率划分不同的区域

在曲率出现突然变化的点处，将该点前后的激光点划分为2个部分。

步骤3：运用RANSAC提取不同区域的直线

应用RANSAC算法，从每一部分激光点提取巷道边线，并存储每个巷道边线的斜率和截距。

步骤4：根据铲运机运动方向和巷道设计标准筛选巷道边线

巷道边线筛选原则如下：

（1）巷道边线应该以铲运机为中点，分成左右2个部分。

（2）为保证铲运机的安全，铲运机运动方向与巷道走向夹角始终不超过50°。

（3）巷道边线原则上是两两平行的，但是由于实际建设或数据收集过程存在误差，相交角度应该在一定范围内（本文设置相交角度范围为小于20°），则有

α ＝ a r c t a n [\frac{(k_{2} - k_{1})}{(1 + k_{2} \cdot k_{1})}]

(5)

式中： $k_{1}$ 和 $k_{2}$ 为巷道左右两边分别提取的直线斜率；α为巷道左右两边分别提取的直线相交后的夹角。

（4）巷道宽度范围应满足矿山巷道设计要求，本文设置为约2.2 m。

步骤5：合并筛选剩余的巷道边线激光点，并再次运用RANSAC算法进行最终巷道边线提取，同时计算巷道边线可靠度。

根据上述规则对巷道边线进行筛选后，可能还存在多条巷道边线。将这些巷道边线包含的激光点合并为巷道左右2个部分，运用RANSAC算法提取出最终的巷道边线，然后计算提取边线的可靠度。计算方法如下^[15]：

η = \frac{η_{T} + η_{Δ} + η_{θ}}{3}

(6)

式中： $η_{T}$ 为巷道边线的内点占比， $η_{T}$ = $\frac{T_{1} + T_{2}}{T}$ ，其中 $T_{1}$ 和 $T_{2}$ 为巷道左右边线各自的内点数量， $T$ 为最终提取巷道边线用到的激光点总数； $η_{Δ}$ 为巷道边线平行度， $η_{Δ}$ = $1 - \frac{|θ_{1} - θ_{2}|}{90^{。}}$ ，其中 $θ_{1}$ 和 $θ_{2}$ 为左右巷道边线的倾斜角； $η_{θ}$ 为巷道边线方向和铲运机运动方向契合程度， $η_{θ}$ = $1 - \frac{|θ - ϕ|}{90^{。}}$ ，其中 $θ = \frac{θ_{1} + θ_{2}}{2}$ ， $ϕ$ 为铲运机运动方向。

2 实例验证

2.1 数据准备

算法数据基于二维单线激光雷达。单线激光雷达与多线束激光雷达相比，具有体积小、测量速度快、数据量少和成本较低的优点，因此更加适用于巷道边线的检测。为了测试本文所提算法的准确度和稳健性，共准备了6组激光点云模拟数据，分别代表地下矿山井下巷道中6种典型的场景，其中既有对应相对简单情景的数据，也有对应相对复杂情景的数据，所以试验结果具有很好的代表性。

6组激光点云数据是在铲运机航向角与巷道真实走向完全一致的假设条件下模拟得出（航向角与x轴夹角为90°，模拟的巷道真实走向与x轴夹角也为90°）。本文的研究重点是如何在井下根据二维激光扫描信息提取巷道边线，所以文中数据是指经过去除运动畸变等处理的激光点数据，不需要考虑铲运机运动速度等因素的影响。

6组数据如图2所示。根据巷道类型可分为3类：数据集（a）和（b）分别是没有交叉口的直行运输巷道和部分弯曲的运输巷道，这是井下环境最简单的场景；数据集（c）、（d）和（e）分别对应有各类交叉口的巷道，情景相对复杂，其中数据集（c）是巷道岔口处，（d）、（e）是多交叉口及不规则交叉口处的巷道，岔口密集，巷道两帮被岔口分为多段短壁，由于短壁之间空隙较多，激光扫描信息反馈缺失严重；数据集（f）是采掘工作面附近的巷道场景，有很多不规则的几何结构，必须结合巷道设计准则和铲运机的航向角等信息才能提取出巷道边线。

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 激光点云数据集

Fig.2 Laser point cloud data set

2.2 试验结果及分析

（1）巷道边线检测试验结果及分析。基于MATLAB2016设计试验，硬件环境为Intel Core i5-7300HQ，Samsung 8G。通过本文算法，6种激光数据最终全部完成巷道边线的提取，结果如图3所示。其中，图3（a）、3（b）、3（c）、3（g）、3（h）、3（i）显示的是计算激光点曲率并划分成不同区域后，用RANSAC算法提取巷道边线的结果，图3（d）、3（e）、3（f）、3（j）、3（k）、3（l）显示的是本文算法提取巷道边线的最终结果。

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 巷道边线提取效果图

（a）直行巷道分段；（b）转弯处分段；（c）交叉口处分段；（d）直行巷道最终结果；（e）转弯处最终结果；（f）交叉口处最终结果；（g）多交叉口巷道分段；（h）不规则交叉口处分段；（i）采场处分段；（j）多交叉口巷道最终结果；（k）不规则交叉口处最终结果；（l）采场处最终结果

Fig.3 Effect map of roadway edge extraction

以图2中数据集（d）为例进行分析。该数据集显示的是井下常见的巷道交叉口场景，巷道两帮是多段短壁，通过计算激光点的曲率，巷道两帮的激光点云各被划分为6个区域，然后分别运用RANSAC算法进行直线提取共产生12条直线。根据铲运机的航向角和巷道的设计标准对直线进行筛选，当前铲运机的航向角 $ϕ$ =90°，分别求12条直线的倾角θ₁，θ₂，…，θ₁₂，判断是否符合以下条件： $|ϕ - θ_{i}| \leq 50^{\circ} (i = 1 ， 2 ， \cdot \cdot \cdot ， 12)$ 。

筛选过后，共剩余6条直线，巷道两帮各有3条。计算巷道两帮直线两两之间的距离和夹角，若某一直线与巷道另一边的所有直线夹角或距离都超出一定范围则剔除该直线，经筛选依然是6条直线。合并筛选后的6条直线，再次应用RANSAC算法提取出最终的巷道边线，如图3（h）所示。该巷道的2条边线倾角分别为89.5°和91.9°，平行度为97.33%，内点占比为94.90%，与航向角契合度为99.22%，经计算得到总体可靠度为97.15%，说明该巷道边线具有很高的可靠度（表1）。同时可视化结果显示，生成的巷道边线准确完整。如表1所示，根据式（6），从3个方面对算法提取巷道边线的效果进行分析：巷道左右两帮边线的平行度、巷道边线与铲运机航向角契合度、巷道边线内点占比，然后计算平均值，得到巷道边线的总体可靠度。表2记录了算法的解算时间。

表1 巷道边线可靠度分析

Table 1 Reliability analysis of roadway edge（%）

数据集序号	平行度	与航向角契合度	内点占比	总体可靠度
平均值	97.45	98.34	96.16	97.32
（a）	99.43	99.23	94.50	97.72
（b）	93.01	97.78	100.00	96.93
（c）	97.72	96.74	95.31	96.59
（d）	97.33	99.22	94.90	97.15
（e）	98.71	97.79	92.25	96.25
（f）	98.51	99.31	100.00	99.27

新窗口打开| 下载CSV

表2 算法解算时间

Table 2 Operating time of algorithm

数据集序号	解算时间/ms
平均值	72.51
（a）	68.46
（b）	53.74
（c）	76.74
（d）	89.47
（e）	64.51
（f）	82.12

新窗口打开| 下载CSV

通过分析试验结果得出：在6种场景下，提取的巷道边线平行度都在93%以上，巷道边线与航向角契合度都在96%以上，巷道边线内点占比都在92%以上，最终计算得到提取的巷道边线总体可靠度都在96%以上；同时生成的巷道边线经可视化显示后均符合井下巷道工程实际情况，没有异常；算法的平均解算时长为72.51 ms，最大值为89.47 ms，完全满足井下反应式导航的需求。以上结果说明本文所提方法能够有效准确地提取巷道边线，并且具有很高的实时性。

（2）算法稳健性评估。试验场景设计由简单到复杂，已经对算法的稳健性进行了一定程度的测试。为了更加深入地评估算法的稳健性，通过删除当前数据的1/2和2/3来模拟不同角度分辨率的激光数据，如果激光雷达原本角度分辨率是1°，经上述处理之后分别为2°和3°，这样就可以评估当使用更低数据速率（角度分辨率更大）的雷达或小功率处理器时算法的效果。

通过对数据进行处理，得到了原始角度分辨率2倍及3倍的激光点数据，然后分别进行试验，统计所有试验结果中的巷道边线可靠度如表3所示。根据表3数据进行无重复试验的方差分析，量化不同角度分辨率和不同井下场景对算法效果是否有显著影响，从而评估算法的稳健性。

表3 由不同角度分辨率数据提取的巷道边线可靠度

Table 3 Reliability of roadway edge extracted from different angle resolution data

数据集序号	巷道边线可靠度/%
数据集序号	1×角度	2×角度	3×角度
（a）	97.72	97.77	96.39
（b）	96.93	92.50	93.05
（c）	96.59	97.37	95.74
（d）	97.15	99.14	97.11
（e）	96.25	95.17	96.06
（f）	99.27	91.23	93.85

新窗口打开| 下载CSV

在显著水平α=0.05的条件下，通过查阅F分布表得知F_0.05（2，10）=4.10，F_0.05（5，10）=3.33。由表4可知，数据角度分辨率的F值为1.579，不同井下场景的F值为1.088，很明显1.579<F_0.05（2，10）=4.10，1.088<F_0.05（5，10）=3.33，所以不同角度分辨率的激光雷达数据和不同井下场景对算法的效果并不会产生显著影响，说明算法本身具有很高的稳健性。

表4 试验数据方差分析

Table 4 Variance analysis of experimental date

方差来源	平方和	自由度	均方	F值
总和	69.055	17
数据角度分辨率	11.723	2	5.862	1.579
不同井下场景	20.198	5	4.040	1.088
随机误差	37.134	10	3.713

新窗口打开| 下载CSV

3 结语

（1）针对多粉尘及巷道壁凹凸不平的井下封闭环境，提出了基于RANSAC的巷道边线检测算法，用于辅助井下铲运机的反应式导航，为实现井下铲运机的自主导航提供技术支撑。

（2）模拟了从简单到复杂的6种井下场景的激光数据，对算法进行验证，结果显示生成的巷道边线可靠度均在96％以上，解算时间均在0.1 s以下，证明算法具有较高的准确度和实时性，能为井下反应式导航提供准确的感知信息。

（3）稳健性分析试验结果表明：该算法在矿山复杂多变的环境和较大角度分辨率的激光数据下均能稳定有效地提取巷道边线，具有很高的稳健性。

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Dragt

B J

Modeling and Control of an Autonomous Underground Vehicle

[D].Pretoria：University of Pretoria，2006.