优化超体素凹凸性的矿区地物提取算法研究

汪 骁 周大伟 占喜林 周 健 刁鑫鹏 耿智江

(中国矿业大学环境与测绘学院,江苏 徐州 221116)

机载LiDAR是一种空间数据传感器,可快速获取物体的三维空间结构信息,近年来成为了矿区地表监测的重要手段之一。矿区地物作为煤矿开采规划的重要参考依据,对其进行准确分割是矿区后续部署的重要环节。但由于矿区地表起伏较大、地物混杂种类繁多、机载LiDAR点云数据呈现空间无序性等诸多影响因素的存在,利用常规点云分割算法进行矿区地物的准确分割存在一定的困难。

常规的点云分割算法主要分为基于属性分割[1-3]、基于图分割[4-7]、基于模型分割[8]、边缘检测分割[9]、区域增长分割[10-14]及深度学习分割[15-17]。其中基于属性分割利用点云自身的特征作为阈值完成分割,但依赖于点云密度且分割精度较低;基于图分割算法利用权值描述点与点的相似性,该方法分割精度较高但效率较低;基于模型分割可以有效分割规则几何物体,但在复杂场景的点云分割效果欠佳;边缘检测分割主要靠检测物体边缘进行分割,该方法分割效率高但易受到噪点影响;基于区域增长分割算法通过选取最小曲率的种子,按法线与曲率为阈值进行区域增长,但选取的种子点优劣直接决定了最终分割结果的优良;深度学习分割效果最佳,但只适用于小范围的数据集分割,对大场景分割效率极低。针对以上算法的缺点,众多学者对其进行了一定的改进。例如,柯映林等[1]依据曲率变化剧烈程度实现了区域点云的边界提取与分割,但在平滑区域该算法的适用性较差。Saglam等[2]提出了基于点云局部曲率相似度合并的非连续区域增长算法,该方法有效解决了噪声点对精确分割的影响,但分割结果和点云密度等其他因素相关。Felzenswalb等[5]利用点云的数据结构图,提出一种快速的基于图优化的分割算法,用权值描述点之间的相似性来进行点云分割,但该方法需要计算所有临近点间的相似性,算法耗时较长。Cheng等[6]提出了一种结合点云法线信息结构图与收缩-扩展技术的屋顶点云分割方法,该方法需要对点云平面条段精细分割,效率较低。邹鹏等[8]提出一种改进的RANSAC点云分割算法,该算法可以有效分割工件型面特征,但分割效果依赖于合并阈值的选择。丁承君等[9]提出一种基于PCL库与边缘提取的分割算法,通过比较K邻域法线夹角搜寻边界特征进行分割,但该方法需要经过大量实验进行结果筛选寻找最优解。Song等[10]基于分割网络特征图提出BSA模块充分利用种子点进行分割且取得了不错的分割效果。钱建国等[16]利用最小分割与深度学习联合的方法对室内粘连点云进行分割,分割结果具有较高的精度与数据完整性。

目前常用的分割算法均实验于简单的场景分割或点云数据集的分割,且算法流程均具有各自的局限性,对于类似矿区的复杂大场景点云地物分割的适用性也有待研究。针对以上问题,本文提出一种优化超体素凹凸性的聚类分割算法。主要步骤:首先体素化原始点云,各体素中心作为初始种子点,根据半径搜索法与基于颜色、欧式距离和法向量的特征距离完成超体素的初次分割;其次采用FCM算法计算超体素边界点与其相邻超体素中心的隶属度,更新各超体素边界及中心点,完成超体素边界细化;最后相邻超体素的中心点高程作差,对符合高程差阈值要求的凸相邻超体素进行合并,同时更新超体素中心,进行超体素迭代聚类,最终获取矿区地物点云。

1 研究方法

点云过分割指将属于同一物体的点按某一标准分割为多个集合。依据矿区点云的空间属性将其过分割成多个集合,计算相邻集合之间的相似度并按相似度的判定阈值对各集合进行聚类操作,通过该思路可以实现矿区点云分割。具体算法流程如下:首先利用超体素分割算法对原始点云进行初次过分割聚类。其次针对初始分割得到的超体素边界存在越界现象,对超体素边界点用FCM算法计算边界点对临近超体素中心的隶属度,从而更新超体素的边界与中心点。最后根据超体素中心点高差与临近超体素的凹凸性对超体素迭代聚类,防止出现类似地物与地面点归为一类的欠分割现象,确保最终分割地物的准确性。具体流程如图1所示。

1.1 超体素的生成

1.1.1 矿区点云超体素过分割

超体素是一种由体素数据组成的集合,是由体素构成的三维空间内的不规则的几何体。超体素分割算法的目的不在于准确地分割点云,而是对获取的点云数据进行过分割,根据分割点云之间的相似性,将相似点云进行合并。

超体素分割算法具体步骤如下:

(1)将预处理后的点云P1按照半径r1体素化,利用八叉树获取每个体素内最接近中心的点作为该体素的代表点,这些中心点的集合为点云P2,以体素为单元计算P2点云的法向量。计算公式如下

式中,λ1、λ2、λ3为特征值,且λ1>λ2>λ3;v1、v2、v3分别为λ1、λ2、λ3对应的特征向量值,分别代表目标点的3个方向,其中最小特征值对应的特征向量为所求点的法向量。

(2)点云P2按照半径r2体素化,利用八叉树获取每个体素的中心点,加入到初始种子点集合S1中,对S1进行半径搜索筛选,确定最终种子点集合S。根据KdTree获取种子点的邻接关系,计算体素与相邻种子点的特征距离,计算公式如下:

式中,Dc为归一化RGB空间下的欧式距离;Ds为两相邻点之间的空间欧氏距离;Dn为两点法向量之间的弧度;ωc、ωs、ωn分别为颜色、欧式距离和法向量的权重;Rs为S1的搜索半径。

(3)以种子点为中心向外迭代,比较体素与种子点间的特征距离大小,特征距离越小,表明二者越相似,标记该体素内的所有点属于此种子点,直到每个种子点达到搜索范围边界或没有符合合并条件的体素为止。

1.1.2 基于FCM算法优化超体素边界

超体素分割效果取决于初始种子点的选取和初始固定的体素分辨率。若体素分辨率过低会导致不同点被分割至同一体素中,导致初次分割生成的超体素出现边缘形状不规则、相邻超体素间的边界存在越界问题;若分辨率过高则会大大降低算法的效率,导致后续的超体素聚类存在欠分割问题。为解决这一问题本文引入模糊C均值聚类算法对超体素边界进行细化从而解决超体素越界问题。模糊C均值聚类算法(FuzzyC-means,FCM)是一种基于目标函数的模糊聚类算法,不同于硬性划分算法,FCM算法是模糊划分,其并不会明确规定某一点归属于哪一类。在{x1、x2、x3、…、xn},获取当前超体素的邻接超体素并归为集合A={a1、a2、a3、…、ac},对应的各超体素聚类中心为V={v1、v2、v3、…、vc}。实际划分中超体素边界点的属性并不清晰,因此需要利用FCM算法引入隶属度对点云进行模糊划分。隶属度描述边界点属于相邻超体素的不确定性,可以客观反映边界点的隶属程度,从而在超体素与邻接超体素间寻找最优解。

基于FCM的边界细化算法具体流程如下:

(1)将标记与临近点不同的点定义边界点,根据标记大小顺序选定某一超体素聚类,按边界点定义寻找出当前超体素的边界点归为数据样本集X=

(2)根据公式(5)计算样本集中第i个边缘点对第k个临近超体素聚类中心的隶属度μik且需满足式(6)。

式中,dik为欧氏距离;m为样本的特征数;b为模糊指数(取值范围为1≤b≤∞,其通常设为2或2.5)。

(3)由步骤(2)求得的样本点对聚类中心的隶属度μik更新聚类中心集合V及目标函数J,方法如下:

设Ik={i|2≤c

(4)执行步骤(2)、(3)反复更新聚类中心、数据隶属度和目标函数,当Jn+1/Jn收敛或达到最大迭代次数时,便得到了当前超体素边界点对于邻接超体素聚类的隶属度,从而完成了当前超体素的边界细化。

(5)按照标记大小顺序遍历所有超体素,重复上述步骤完成所有超体素的边界细化。

1.2 改进凹凸性聚类算法融合超体素

在细化边界超体素的基础上,采用基于相邻聚类凹凸性的局部凸连接算法,使过分割的场景超体素聚类成与实际物体相对应的区域。为使矿区地表典型地物例如房屋、围墙、高压线塔、信号接收站经过聚类算法后尽量合并,防止出现欠分割现象,本文对局部凸连接算法进行优化:计算当前超体素类中心与其相邻超体素类中心的高程差,与给定的阈值相比较,若在阈值范围内,则从当前超体素类的邻接列表里剔除该相邻超体素,随后以凹凸判定准则CC(Extended Convexity Criterion)及其补充准则SC(Sanity criterion)为依据判断当前超体素与其余邻接超体素的凹凸关系,如图2所示。

图2 相邻超体素凹凸关系Fig.2 Bump relationship of adjacent super-voxel

扩展凸性准则利用相邻点云的中心连线与法向量的夹角判断凹凸性。图2中x1、x2为相邻超体素的质心,、为其对应的法向量,α1为与的夹角,α2为与的夹角。由图可知,当α1<α2时相邻超体素为凹关系,当α1>α2时相邻超体素为凸关系。同时为防止测量引起的平面较小凹凸误差,需要引入某一阈值β去除错误,至此CC的判定规则如下:

某些特殊情况下,两邻接超体素具有公共点而不具有公共边,此时需要加入凹凸判定的补充准则SC对其进行补充判定。SC利用相邻点云法向量叉乘向量与中心连线的夹角判断两面形成凸面的概率。如图3所示,,用θ的大小判断相邻超体素的连接方式,θ越接近90°,表明二者连接方式越接近边连接;越接近0°,表明二者连接方式越接近点连接。设置阈值θ′,保留θ大于阈值的凸关系,其余舍弃,至此SC的判定规则如下:

改进后的融合超体素的凹凸性聚类算法具体步骤如下:

(1)按标记大小顺序遍历超体素的中心点,获取其邻接关系,计算相邻超体素的中心点高程差,判定两超体素是否符合合并条件。

(2)采用CC与SC的判定规则判断相邻超体素的凹凸性,对满足凸面关系的邻接超体素进行合并操作,直到所有邻接超体素不满足合并条件。

(3)更新融合超体素的中心点,重复步骤(1)、(2)直到所有超体素都完成遍历且相邻超体素不满足融合条件。

(4)根据点云标记完成分割,输出结果。

2 实验与分析

2.1 实验数据

点云数据由大疆M600无人机搭载ARS-450i激光雷达扫描内蒙古鄂尔多斯某首采工作面地表获取。但采集的数据受到仪器精度、电磁波衍射、及环境自身的影响,原始数据中含有大量噪声,因此利用CloudComapre软件对点云数据进行预处理。随后采用1.1节算法处理,对比算法结果可知改进后算法得到的超体素边界较为规则,超体素间基本不存在类似部分地表点与建筑点边界越界现象。最终得到的实验点数总计49 118 377,具体如图4所示。

图4 点云对应地物超体素生成对比Fig.4 Comparison of super-voxel generation effect of house point cloud

2.2 实验结果

考虑到矿区内房屋、电塔等地物的高度,因此在进行超体素凹凸性合并时设置高差阈值为2.5～4 m,相邻超体素在该范围内不考虑凹凸性合并,范围外则根据1.2节的凹凸准则判定是否合并。从分割数与点云损失率对3种方法的矿区整体点云分割效果进行对比,具体效果如图5和表1所示。

表1 整体点云分割结果Table 1 Result of all point cloud segmentation

图5 整体点云分割效果Fig.5 Effect of all point cloud segmentation

2.3 讨论及分析

结合图5与表1可知,在整体上3种方法均将矿区地面与地物分割开,但在地物的分割细节、点云损失率等方面存在较大差异。改进前的超体素分割算法没有点云损失且分割数与本文算法接近,但整体分割效果较差,存在大面积过分割现象,对地物的整体提取效果不利;区域增长算法点云分割数是其余2种算法的2倍左右,在部分区域的点云分割效果与本文算法较为接近,但存在44%的点云损失率,且存在原始数据特征信息丢失的现象,不利于地物的准确提取。因此从整体分割点云的角度看,本文分割算法可以在保证数据完整的情况下,仍可以满足矿区在地物分割上的效果需求。

对区域内的部分房屋、信号塔及植被3种地物的分割细节效果进行对比。由图6可知,在房屋分割上,本文算法成功将图中的三间房屋的相邻超体素完全聚类并分割出来,与之对比,其他2种算法并没有将房屋完全分割成一类,存在将部分地面点归于房屋一类或部分房屋边角超体素未被归于一类;在信号塔分割上,本文算法可以明显看出整个电塔被归为一类,不存在上下部分欠分割现象,而改进前的超体素分割算法明显将塔尖与塔身等区域分为多类,区域增长算法则是在聚类后电塔大量点云缺失只剩下一半;在地表植被分割上,本文算法在植被密集区分割效果较好,可以分割出大区域植被,在植被稀疏区分割同样有较好的效果,改进前超体素的分割算法在大植被区存在欠分割现象,而区域增长算法存在大量植被点云缺失。

为定量分析算法效果,从精确度与召回率两方面对放大区域的点云分割效果进行定量比较,计算公式如下:

式中,TP为算法分割的正确点数;FP为算法未分割的正确点数;FN为算法分割的错误点数。

定量分析结果如表2所示,3种算法欠分割现象均较少,因此点云召回率大部分在90%以上,但存在点云缺失或过分割现象,导致精确度存在较大的差异。由于本文算法解决了超体素分割边界越界现象以及凹凸性分割时部分超体素凸连接错误聚类的问题,因此在精确度与召回率相对其余2种算法均有了一定程度的提高,相较于改进前超体素分割算法加权平均精确度提升了13.1%,加权平均召回率提升了2.3%;与区域增长算法相比加权平均精确度提升了30%,加权平均召回率提升了6.3%。

3 结 论

针对常规点云分割算法在矿区地物分割效果不理想的现状,本文提出一种优化超体素凹凸性的矿区地物提取算法,该方法克服了区域生长算法分割点云缺失现象及传统超体素分割算法的过分割问题,可以在保证点云完整性的前提下,完成地物较为准确的分割。比改进前超体素分割算法的加权平均精确度提升了13.1%,加权平均召回率提升了2.3%,比区域增长算法的加权平均精确度提升了30%,加权平均召回率提升了6.3%。