陈 凯,张 达,张元生

(1.北京矿冶科技集团有限公司，北京 100160；2.北京科技大学 机械工程学院，北京 100083；3.金属矿山智能开采技术北京市重点实验室，北京 102628)

在地下开采矿山，通过三维激光扫描测量获取高精度的井下三维空间信息，对于采矿作业的超爆欠爆评价、井巷工程及采场验收、矿石资源的损失贫化分析、保有资源计算、矿山采空区调查与安全分析、采矿溜井及井巷工程治理及矿山工程数字化建设等具有十分重要的意义。北京矿冶科技集团有限公司研制了国内首套矿用三维激光扫描测量系统，并实现了产业化推广应用，打破了国外技术垄断，填补了国内空白，可为后续矿山安全生产提供数据基础[1-4]。

但是，矿用三维激光扫描测量系统测量的采场、溜井等区域形态复杂，内部存在矿石点柱、垮塌、超爆、欠爆等情况，使矿用三维激光扫描测量系统工作时由于遮挡导致点云数据存在很多盲区，同时由于人员难于进入这些区域，肉眼通常无法直接获知哪些区域存在遮挡，这将使准确识别盲区边界存在很大困难，为后续数据分析带来一系列麻烦。为解决盲区定位困难的问题，需提供一种高效的点云数据预处理方法，须在杂乱无章的点云数据基础上，对点云数据特征进行分析研究，准确判断盲区边界，为后续盲区数据处理提供判断依据。

1 构建点云空间拓扑关系

KD-Tree广泛应用于数据库索引中，从概念的角度讲，它是一种高纬数据的快速查询结构。KD-Tree是一种二叉树，它继承二叉查找树的优点，平均查找长度只为1+4logn，表示对k维空间的一个划分，构造KD-Tree相当于不断地用垂直于坐标轴的超平面对k维空间进行切分，构成一系列的k维超矩形区域，KD-Tree的每个结点对应于一个k维超矩形区域。由于点云数据分布不规则，所以不能采用规则划分的方式来划分点云空间，但是KD-Tree是一种非常适合管理点云的索引方法，建立空间点云的拓扑关系，快速查找点云的邻域[5-8]。KD-Tree构建过程如图1所示。

图1 构建KD-Tree数据结构流程图Fig.1 The flow chart of building KD-Tree data structure

2 点云数据领域法向矢量计算

点云数据法向矢量的计算是判断点云数据的K-近邻点是否分布均匀的前提。通过KD-Tree构建的点云拓扑关系，构造点云中各点的最小二乘平面，计算该平面的法向矢量，并将该法向矢量作为数据点的法向矢量计算结果。其中K值的选取很重要，在曲率变化大的地方需要慎重考虑K值的选取，以保证单凸或单凹，这样得到的最小二乘平面才能更好地逼近原始点云，也使得投影点在局部型面的参数化更好地反映点云的参数化。

ax+by+cz=d

输入：点云数据集S

如果点云数据集S为空，则算法将结束；否则从点云数据集S中顺序提取数据点P作为当前处理数据；

计算矩阵A的特征值；

计算最小特征值对应的特征向量。

3 点云数据盲区边界提取

K-近邻的创建可为特征边界的提取提供好的基础[9]。假设点云数据中点P是特征边界点，K-近邻点的分布将偏向某一侧；如果是内部点，则其K邻域点将均匀地分布在该点的周围(如图2所示)。基于该思路，本文利用了数据点及其K-近邻点的均匀分布特性来判断特征边界点。

图2 边界特征点识别原理Fig.2 The recognition principle of character boundary point

假设输入的点云数据集为S，输出的边界特征集合为F(S)，基于上述思想，边界检测的算法流程如下：

1)如果点云数据集S为空，则算法将直接结束；否则从点云数据集S中按照先后秩序提取数据点P作为当前需处理数据；

2)将数据点P的K-近邻点投影到对应的法向矢量平面内，连接数据点P和邻域的投影点形成一个向量集；

3)计算向量集对应的所有向量与基准向量间的夹角，计算结果按照升序进行排序，得到了夹角集S’。计算S’的夹角差然后得到向量集中相邻向量的夹角集A；

4)若夹角集A的最大角度差Amax>u(一般情况，阈值u取值大小为π/2)，则将数据点P放入集合F(S)中；如果完成点云数据集S中的所有数据处理，则算法结束，否则转向1)。

4 现场扫描点云数据验证

为验证本文提出的盲区边界识别算法效果，选择两组矿山的采空区扫描点云数据进行验证，第一组采空区点云数据数量为208 786个，使用该算法耗时5 s准确识别出盲区边界(如图3所示)，盲区边界点云数量为305个；第二组采空区点云数据数量为158 756个，使用该算法耗时3.5 s准确识别出盲区边界(如图4所示)，盲区边界点云数量为158个。通过现场两组采空区点云数据验证结果表明该算法可有效获取点云数据盲区边界。

图3 第一组点云数据盲区边界识别结果Fig.3 The blind area recognition result of the first-group point cloud data

图4 第二组点云数据盲区边界识别结果Fig.4 The blind area recognition result of the second-group point cloud data

5 结论

本文应用的盲区识别算法利用KD-Tree构建点云的空间拓扑关系，快速、准确地获取局部型面参考点集，然后利用KD-Tree计算出点云中各数据点的K-近邻点，通过判断K-近邻域点分布的均匀性来提取出边界特征点，最后利用估计边界的走向来提取特征边界点并形成边界线，最后达到识别出内外边界的目的，为后续点云数据修复和补洞提供了数据基础。