光学学报, 2021, 41 (5): 0528001, 网络出版: 2021-04-07   

基于改进多规则区域生长的点云多要素分割 下载: 634次

Multi-Factor Segmentation of Point Cloud Based on Improved Multi-Rule Region Growing
作者单位
中国人民解放军战略支援部队信息工程大学地理空间信息学院, 河南 郑州 450001
摘要
针对现有点云多要素分割算法分割面状点集时分割精度低、分割块合并效果差等问题,提出了一种改进的多规则区域生长算法。一方面,计算点云数据的平面拟合残差,基于平面拟合残差设置种子点条件,对面状点集分割进行优化,以此提升面状要素分割的精度;另一方面,在距离条件的基础上,结合相似性和体积变化条件对合并策略进行改进,以实现分割块的有效合并;此外,利用中位数、Baarda数据探测法和k均值聚类分别对算法中涉及的阈值参数进行自适应设置。采用三种不同类型的点云数据进行实验,结果表明:改进算法能够提升面状点集的分割精度,提高了分割块合并的准确性;与其他算法相比,改进算法能够同时兼顾精度和效率,分割结果更具优势。
Abstract
With regard to the low segmentation accuracy of planar point sets and poor merging effect of segments in the existing multi-factor segmentation algorithms of point clouds, an improved multi-rule region growing algorithm was proposed in this paper. On one hand, the plane fitting residuals of point clouds were calculated, based on which, the seed condition was set and the segmentation of planar point sets was optimized, so as to increase the segmentation accuracy of planar factors. On the other hand, on the basis of the distance condition, the merging strategy was improved in combination with similarity and volume changes to achieve effective merging of segments. In addition, the threshold parameters involved in this algorithm were set adaptively using the median clustering, Baarda data snooping, and k-means clustering. Furthermore, three different types of point clouds were tested, and the results show that the improved algorithm can boost the segmentation accuracy of planar point sets, and enhance the veracity of segments merging. Compared with other algorithms, the proposed algorithm can take into account both accuracy and efficiency and has better segmentation results.

1 引言

随着三维激光扫描测量技术的迅猛发展,点云数据处理成为了研究热点[1]。点云分割是点云数据处理的重要环节,在建筑物提取[2]、道路标线识别[3]、森林资源调查[4]、农业生产[5]等方面应用广泛。常见的点云分割方法包括模型拟合法[6-7]、特征聚类法[8-9]和区域生长法[10-11]。模型拟合法常被用于提取点云数据中平面、柱面和球体等规则形状的要素,该方法需要模型先验信息,难以适用于复杂场景的点云分割。特征聚类法是依据特征的相似度进行聚类,其优点是能够自动进行点云分割,特征构建方式灵活多样,但该方法易受噪声影响,聚类过程较为耗时。区域生长法是利用点云数据之间的邻接关系与相关属性的相似性进行分割,该算法的核心在于种子点的选用以及点与点之间生长条件的确定。

目前点云分割的研究多集中于场景中单一类别物体的识别和提取,如车辆[12]、建筑物[13]的提取等。点云场景中通常包含植被、建筑、地面等多种要素,种类复杂多样,随着点云多目标识别提取需求的增长[14]以及基于对象基元的点云分类[15]、融合多点集特征的点云分类[16]等方法的进步,相关分割方法需进一步发展,以实现点云场景的多要素分割。文献[ 17]将机载点云数据分为平面点和非平面点分别进行分割,场景中大部分地物要素能够取得较好的分割结果,但平面和非平面的划分不能完全描述点云数据的特点,一些线状地物分割效果较差。文献[ 18]提出了一种利用点云数据生成多尺度超级体素的方法,然后融合体素的颜色、反射强度、法向量、主方向等多种特征,利用图分割的方法进行点云分割;文献[ 19]以体素为节点构建无向图并利用连通分支对点云数据进行聚类分割,然后结合归一化分割方法对欠分割地物进行细分;文献[ 20]将点云数据表示为深度图,并将深度图和改进的DBSCAN(density-based spatial clustering of applications with noise)算法结合,实现了点云数据的分割。上述三种方法在分割之前往往需要率先利用其他方法对地面点进行剔除,以避免影响地物的分割结果,破坏点云数据的完整性;另外,文献[ 18]算法需要点云属性信息的辅助,限制了算法的应用场景。文献[ 21]扩展了区域生长算法的分割规则,首先利用维数特征将点云数据粗分类为杆状、面状和球状三类,然后根据类别的不同采取不同的生长准则进行分割,使得区域生长算法能够适应不同地物的特点,实现点云数据的多要素分割;文献[ 22]将其应用于建筑物平面的提取;文献[ 23]在文献[ 21]基础上增加了过分割块的合并操作,通过计算各分割块轮廓之间的距离对相邻的分割块进行合并,减小了过分割的程度。

本文在多规则区域生长算法[21-23]的基础上进一步改进,以期提升点云数据多要素分割的准确性,为点云多目标识别和基于分割块的点云分类提供技术支持。本文主要工作包括:1)增加了面状点集数据分割中种子点的选取准则,提高了面状地物分割的精度;2)改进了分割块的合并条件,减少了零散分割块的数量,提升了合并的准确性;3)研究了分割阈值参数的自适应设置方法,提升了分割算法的自适应性。

2 多规则区域生长算法

区域生长(RG)算法[10-11]是由二维图像扩展到三维点云的一种分割算法,已广泛应用于点云数据的分割处理。图1场景中主要包含建筑、地面和植被三种要素(本文所有分割结果图片中地面颜色唯一且确定,其他分割块的颜色随机且与地面颜色不同)。RG算法对于点云数据中的面状点云(如地面、建筑等)可以获得较好的分割结果,但对于非面状点(如植被等)的分割,由于非面状点相互之间法向量夹角过大,容易产生过分割现象,非面状点难以生长。因此单纯利用RG算法难以有效分割多要素场景点云。

图 1. 基于RG算法的点云多要素分割示例

Fig. 1. An example of point cloud multi-factor segmentation based on traditional RG algorithm

下载图片 查看所有图片

文献[ 21]提出了一种基于维数特征的多规则点云区域生长(MRG)算法。相比于RG算法,MRG算法将点云数据分成三种不同的类别——杆状、面状和球状,然后根据点云类别分别采用各自的生长准则进行分割,避免了非面状点难以有效分割的问题。如图2所示,场景中植被点的分割结果整体较好,没有出现图1中点云过于零散的现象。但是,MRG算法还存在以下两个问题:一方面,由于没有种子点条件的限制,容易将不同面状物体分割到同一区域中,如图2 A、B和C区域中的建筑屋顶面被误分割成了地面(建筑分割块与地面同一颜色);另一方面,点云初始分割结果中存在一些尺寸较小的零散分割块,这些分割块应该与相应的其他分割块合并,否则会导致后续地物识别、提取等过程中出现错误结果。为解决这一问题,文献[ 23]利用各分割块轮廓构建邻接关系,通过设置一定的阈值对MRG算法分割结果进行合并,但仅仅依靠距离因素的合并策略容易导致不同类别的物体合并到同一分割块中,因此还需要进一步对合并条件进行优化。

图 2. 基于MRG算法的点云多要素分割示例

Fig. 2. An example of point cloud multi-factor segmentation based on MRG algorithm

下载图片 查看所有图片

3 改进的多规则区域生长算法

为了解决MRG算法中存在的问题,本研究提出一种改进的多规则区域生长(IMRG)算法。针对MRG算法在面状点集分割和分割块合并方面存在的问题,分别提出了相应的改进策略,改进算法有助于提升点云分割的准确性和完整性。

3.1 面状点集分割优化

3.1.1 误分割原因

点云面状点集中包含的要素主要有地面和建筑,面状点集是通过搜索邻域点、判断当前点与邻域点之间法向量夹角与阈值的关系来进行区域生长。从图2中可以看出,利用MRG算法进行点云分割存在部分建筑平面被误分割为地面的情形。下面具体分析出现误分割现象的原因。以某建筑为例,如图3所示,屋顶面、建筑立面和地面各自内部点云,因法向量基本平行,在进行区域生长的过程中可以满足法向量夹角的阈值条件,能够得到有效生长;但是在建筑屋顶面和立面的边界处、建筑立面和地面边界处,由于点云数据变化剧烈,法向量计算不稳定,容易偏离正确方向,从图3 A、B区域中的点云法向量可以看出这一问题,因此,在进行区域生长时,不同要素边界处的法向量仍可以满足阈值条件,故生长点能够越过要素边界,导致不同要素被分割到同一分割块中。

图 3. 法向量示例。(a)点云数据;(b)点云法向量

Fig. 3. An example of normal vector. (a) Point cloud; (b) normal vector of point cloud

下载图片 查看所有图片

3.1.2 优化策略

面状点集误分割产生的原因主要在于不同要素边界处法向量存在偏差,如何控制不同要素边界处点云数据的生长是解决这一问题的关键,即当区域生长点到达要素边界处时停止生长。RG算法在生长过程中设置了种子点选取条件,只有新加入的生长点满足这一条件时才能继续搜索邻近点进行生长,故采用合适的种子点阈值能够取得较好的分割结果。下文借鉴RG算法中种子点选取方法,结合边界位置点云数据性质,对MRG算法面状点集分割进行优化。

RG算法将平面拟合残差用于区域生长种子点的选取[10]。面状点集中以面状地物要素为主,对于面状地物而言,其内部各点平面拟合残差通常较小,而边界点由于靠近其他物体,邻域点中包含有不同类别的点云数据,计算得到的平面拟合残差值会大一些。基于边界点这一特性,可以通过设置一定的平面拟合残差阈值vt来实现对边界点的区分,当面状点平面拟合残差大于阈值vt时,该点被认为是边界点,停止生长。

关于阈值vt的选取,考虑从杆状点集的平面拟合残差入手进行设置。由于不同面状要素边界线具有杆状点云的特征,因此在进行维数特征分类时,部分要素边界线被分类到杆状点集中,从图4中可以看出,杆状点集生长结果中包含大量的建筑平面结构线和边界线。如图5所示,阈值vt的设置是为了区分出面状点集中的边界点B以避免面状点集的错误分割,而面状点集中的边界点B处于各物体要素的边缘位置,与杆状点集L中的结构线、边界线性质接近;换言之,面状点集中的边界点特征与杆状点集具有一定相似性,其平面拟合残差与杆状点集相近。因此,可以考虑利用杆状点集的平面拟合残差代表边界点残差,将其作为面状点集的阈值vt。由于前期利用维数特征进行点集分类时存在误差,杆状点集中存在少部分其他类型的误分点,导致残差数据中包含异常值。平均数容易受到异常值的影响,而中位数可以描述数据的集中趋势,具有稳健性,能够避免异常值的影响,是数据分析中重要的统计量[24]。因此,本文将面状点集平面拟合残差阈值vt设置为杆状点集平面拟合残差的中位数。

图 4. 杆状、面状点集分割示例。(a)杆状点集;(b)面状点集

Fig. 4. An example of linear and planar point set segmentation. (a) Linear point set; (b) planar point set

下载图片 查看所有图片

图 5. 阈值vt设置原理图

Fig. 5. Schematic diagram of threshold vt setting

下载图片 查看所有图片

3.2 分割块合并优化

3.2.1 合并策略

点云数据利用维数特征分类时存在误差,且各点集生长结果由于阈值条件的限制会产生过分割现象,在这两种因素的作用下,点云数据的分割结果缺乏完整性,在此基础上进行的目标识别、提取等也将受到影响,所以有必要对MRG算法点云分割结果进行合并。文献[ 23]提出了一种合并方法,首先提取点云各分割块的轮廓,然后构建分割块轮廓之间的邻接关系,最后通过设置一定的距离阈值对分割块进行合并,但仅仅依靠距离因素的合并策略容易导致不同类型的物体合并到同一分割块中。针对该方法存在的问题,本文提出了一种结合距离、分割块相似性和体积变化的合并策略,具体合并条件如下:

1) 距离条件。首先,利用凸包算法[25]得到各分割块的轮廓点;然后,计算分割块轮廓点之间的最小距离,并将其作为分割块之间的距离;最后,将分割块距离与阈值条件dt进行比较,当分割块距离大于阈值dt时,不需要进行合并操作。

2) 相似性条件。同一类型的分割块平面拟合残差一般接近,不同类型的分割块平面拟合残差往往相差较大,因此可以将分割块平面拟合残差作为分割块的相似性条件;计算分割块中各点平面拟合残差的平均值作为分割块的平面拟合残差, 表达式为

Ri=1mj=1mrj, i=1,2,,M,(1)

式中:Ri为分割块的平面拟合残差;rj为分割块中点的平面拟合残差;m为分割块中点的个数;M为分割块的个数。若两分割块平面拟合残差的差值大于阈值st,则不满足合并要求。

3) 体积变化条件。本文所涉及的分割块合并是将尺寸较小的分割块合并到同属于一个物体的较大分割块中。在将一小尺寸分割块Si(i∈{1,2,…,M})合并到大尺寸分割块Sj(j∈{1,2,…,M},ji)的过程中,合并前后Sj对应的凸包体积Vj会有所变化,当SiSj属于同一物体时,Sj合并后增加的体积δVj一般与Si的体积Vi相差不大,如图6所示;但实际过程中还会存在一些误合并现象,当于两个分割块属于不同的物体时,δVjVi常有明显的出入,如图7所示。因此需要设置一定的标准对Sj合并前后的体积变化进行衡量,以提升分割块合并的准确性。本文设置体积变化统计参数ΔVij,表达式为

ΔVij=Vj-V'jVi, i,j=1,2,,M,andij,(2)

式中:ΔVij是将分割块Si合并到Sj体积变化参数;Vi为小分割块Si的凸包体积;V'jV″j分别是大分割块Sj合并前后的凸包体积。同时设置体积变化阈值Vt,当ΔVij>Vt时,说明Sj合并之后体积变化太大,不满足合并要求。

图 6. 正确合并体积变化示例(ΔV=2.13)。(a)待合并分割块;(b)待合并分割块的凸包;(c)合并后的分割块;(d)合并后分割块的凸包

Fig. 6. An example of volume change based on correct merging (ΔV=2.13). (a) Unmerged segments; (b) convex hulls of unmerged segments; (c) merged segment; (d) convex hull of merged segments

下载图片 查看所有图片

图 7. 错误合并体积变化示例(ΔV=17214.04)。(a)待合并分割块;(b)待合并分割块的凸包;(c)合并后的分割块;(d)合并后分割块的凸包

Fig. 7. An example of volume change based on incorrect merging (ΔV=17214.04). (a) Unmerged segments; (b) convex hulls of unmerged segments; (c) merged segment; (d) convex hull of merged segments

下载图片 查看所有图片

分割块合并操作需要同时满足以上三个条件,其中三个相关阈值——距离阈值dt、相似性阈值st和体积变化阈值Vt的自适应设置方法见后文,具体合并步骤的伪代码如图8所示。

图 8. 合并策略的伪代码

Fig. 8. Pseudo-code of merge strategy

下载图片 查看所有图片

3.2.2 阈值自适应设置

合并策略中涉及三个参数——距离阈值dt、相似性阈值st和体积变化阈值Vt,本文考虑对参数进行自适应设置来提升算法的自适应性,具体设置方法如下。

1) 距离阈值dt

对于每个分割块Si(i∈{1,2,…,M}),通过计算可以得到与其距离最近的分割块Sj(j∈{1,2,…,M},ji)以及二者之间的邻近距离di,而阈值dt是决定分割块与其距离最近分割块是否合并的条件,因此可以从分割块之间的邻近距离集D={d1,d2,…,dM}出发进行dt的设置。

邻近距离集合D可以分成两部分:一部分是满足合并要求的邻近距离D1;另一部分是不满足合并要求的邻近距离D2。由于初始分割结果中存在较多的零散分割块,D中包含的D1类型数据多,D2类型数据少,最后要得到的数据是D1类型数据,而D1类型数据数值通常较小,与D2类型数据有较为明显的区别。因此,考虑将D2类型数据作为粗差,基于Baarda数据探测法[26]采用向后选择的方式将D中粗差逐个剔除,最后选择D中剩余数据的最大值作为距离阈值dt

2) 相似性阈值st

点云数据在进行初始分割之前被分类为杆状、面状和球状点集,由这些点集分割得到的点云分割块也可以分为杆状、面状和球状三类。不同类别分割块的平面拟合残差大小各不相同,相似性阈值st是用来判断不同分割块之间平面拟合残差的相似性程度,当点云分割块SiSj的平面拟合残差之差ΔRij= Ri-Rj超过不同类别分割块之间平面拟合残差的差值时,可以认为二者所属点云分割块的类别不同,不能进行合并。因此可以利用不同类别分割块之间平面拟合残差的差值设置相似性阈值st。本文考虑利用k均值聚类方法对所有点云分割块残差进行聚类,聚类中心个数为3,将聚类中心之间的最小差值作为相似性阈值st

3) 体积变化阈值Vt

选取两个同时满足距离阈值dt和相似性阈值st的点云分割块SiSj(Vi<Vj),计算Sj的体积变化参数ΔVij,把所有计算得到的分割块体积变化参数ΔVij记为ΔV。ΔVD类似,其中同样存在两部分数据,因此可以参照距离阈值dt的设置方法,采用Baarda数据探测法剔除其中的粗差,将最后剩余数据中的最大值作为体积变化阈值Vt

4 实验

4.1 实验数据及评价指标

为验证本文算法的有效性,采用机载、站载和车载三种不同场景(Scene I 、Scene II 、 Scene III)的点云数据集进行实验,将三种点云数据集分别按高程赋色,如图9所示。其中,机载点云数据集来自Terrasolid软件官网(http://www.terrasolid.com/training/training_data.php)的训练数据,本文选取了其中部分数据进行分类实验;站载点云数据集选择了开源数据集Robotic 3D Scan Repsitory中场景12的数据(http://kos.informatik.uni-osnabrueck.de/3Dscans/),该数据是在德国不莱梅市中心由Riegl VZ400站载扫描仪扫描得到。车载点云数据集采用了Paris-Lille-3D开源数据集[27],该数据是由车载移动测量系统在法国巴黎和里尔两座城市扫描获得,本文只截取了其中部分数据。由于原始点云数据量太大,三种点云数据集均进行了降采样处理。另外,实验在Intel(R) Core(TM)i7-9750H CPU @2.60 GHz RAM 16 GB的计算机上实现。

图 9. 点云数据集。(a)机载点云(场景I);(b)站载点云(场景II);(c)车载点云(场景III)

Fig. 9. Point cloud data set. (a) Airborne point cloud (scene I); (b) terrestrial point cloud (scene II); (c) vehicle-borne point cloud (scene III)

下载图片 查看所有图片

为了更好地评价点云分割质量,采用了精度P、召回率RF1得分三种评价指标[11],具体计算表达式为

P=TPTP+FPR=TPTP+FNF1=2×P×R(P+R),(3)

式中:TP表示正确点被归类为正确点的个数;FP表示错误点被归类为正确点的个数;FN表示正确点被归类为错误点的个数。另外,分别对三种场景点云数据进行了手工分割并将结果作为参考数据,见图10。其中:Scene I场景中包括建筑、植被和地面三类地物;Scene II场景中包括建筑、植被、地面和电力线4类地物;Scene III场景中包括建筑、植被、地面和车辆4类地物。

图10中可以看出,参考分割数据都是完整的物体,在进行点云分割时,一个参考分割物体往往对应多个分割块,因此,在进行评价时规定:1)当分割块Si(i∈{1,2,…,M})与参考物体Sr(r∈{1,2,…,Mr},Mr为参考物体的个数)中交叉点[pc∈(SiSr)]数目超过Si中总点数的一半时,认为Si为有效分割块;2)当Sr中所有与其他分割块的交叉点总数超过Sr点数的一半时,认为Sr被有效识别。满足以上两个条件时,将交叉点pc数目计入TP中,同时把Si中剩余点[pr∈(Sir)]数目计入FP中;将Sr中交叉点扣除之后,剩余点的数目计入FN中,同时其他未被识别的参考物体也计入FN中。

图 10. 各场景点云参考数据。(a)场景I;(b)场景II;(c)场景III

Fig. 10. Reference data of each scene. (a) Scene I; (b) scene II; (c) scene III

下载图片 查看所有图片

4.2 面状点集分割对比

为验证本文算法面状点集分割优化的效果,分别采用Scene I、Scene II和SceneIII三种场景的点云数据进行分割,未进行合并操作。分割过程中最优邻域计算选择了文献[ 28-29]方法;主向量夹角阈值Mt设置为15°,法向量夹角阈值Nt分别取5°、10°和15°;IMRG算法在三种场景下的种子点阈值vt按照自适应设置方法分别设置为0.70 m、0.09 m和0.06 m。具体分割结果见表1表2

表 1. 1 Scene I场景地面分割结果

Table 1. 1 Segmentation results of ground in Scene I

MethodTPFP
RG+mean shift35170829669
CSF+DBSCAN36459434771
IMRG34050238946

查看所有表

表 2. 各场景地面分割评价

Table 2. Segmentation evaluation of ground in each scene

MethodNt /(°)P /%R /%F1 /%
Scene IScene IIScene IIIScene IScene IIScene IIIScene IScene IIScene III
588.4197.6498.6187.8798.0999.0388.1497.8798.82
MRG1085.7893.7784.4290.6598.5599.3188.1596.1091.26
1583.0993.6567.0590.553.6699.5486.667.0580.13
590.1197.5198.7586.2398.3499.0788.1397.9298.91
IMRG1089.8597.3991.5089.8198.5699.3189.8397.9795.25
1589.2792.6678.9990.5898.6399.4589.9295.5588.05

查看所有表

结合表1表2点云面状点数据分割结果进行分析,可以发现:

1) 总体来看,增加了种子点条件的多规则区域生长IMRG算法在面状点集方面分割效果良好,在不同法向量夹角阈值Nt、不同场景条件下分割精度均优于MRG算法,而且随着Nt的增大,优势更加明显,这证实了IMRG算法的有效性。

2) Scene I场景中,IMRG算法建筑平面召回率R高于MRG算法,这表明增加了种子点条件之后,建筑平面被误分割成地面的现象减少;与此同时,地面分割的精度P也有所提高,这说明地面分割块中非地面点减少,从侧面印证建筑物平面有效提取的点数得到了增加。由此可以看出IMRG算法的面状点集分割优化策略能够取得较好的效果。

3) Scene II和Scene III场景中,在阈值Nt取值较小时,IMRG算法分割精度和MRG算法相差不大;随着Nt取值的增加,MRG算法的平面分割精度大幅下降,这是因为大量建筑平面和地面被误分割到同一分割块中;相比而言,IMRG算法总体分割精度显著优于MRG算法,这说明IMRG算法能够在一定程度上抵御Nt设置不良的影响,体现了算法的稳定性和可靠性。同时,从图11中也可以看出,MRG算法的分割结果中出现明显的误分割现象,大量建筑与地面位于同一分割块中(颜色相同);而IMRG算法分割效果则明显优于MRG算法,可有效地将建筑平面与地面分割开来。

4.3 分割块合并对比

为了对比两种合并方法的效果,本文设置了两种合并策略,合并操作针对4.2节中IMRG算法的初始分割结果进行。策略①:仅根据分割块距离进行合并;策略②:结合距离、分割块相似性和体积变化进行合并。两种策略生长过程中主向量夹角阈值Mt设置为15°,法向量夹角阈值Nt分别设置为10°(Scene I和Scene II)和5°(Scene III);策略②中涉及的合并参数按照自适应阈值设置方法得到,结果见表3;策略①涉及的距离阈值dt取值参考策略②。两种策略合并结果分别见表4表5表6

表 3. 合并阈值参数

Table 3. Merge threshold parameters

Scenedt /mst /mVt
Scene I1.540.4018.71
Scene II0.250.0516.33
Scene III0.130.0314.61

查看所有表

表 4. Scene I场景合并结果

Table 4. Merge results in Scene I

Type of ground objectBuilding planGroundVegetation
P /%89.7087.5391.77
Strategy① (M=1150)R /%80.5087.9292.14
F1 /%84.8587.7291.96
P /%96.4489.7492.99
Strategy② (M=1515)R /%90.4389.1994.14
F1 /%93.3489.4693.56

查看所有表

表 5. Scene II场景合并结果

Table 5. Merge results in Scene II

Type of ground objectBuilding planGroundVegetationPower line
P /%97.6791.1599.7895.72
Strategy①(M=1550)R /%96.2297.2596.4760.97
F1 /%96.9494.1098.1074.49
P /%99.3897.4299.7899.40
Strategy②(M=2730)R /%98.9798.4599.7998.36
F1 /%99.1797.9499.7998.88

查看所有表

表 6. Scene III场景合并结果

Table 6. Merge results in Scene III

Type of ground objectBuilding planGroundVegetationCar
P /%97.0998.3098.7594.67
Strategy①(M=1673)R /%98.6598.1896.4094.14
F1 /%97.8698.2497.5694.41
P /%98.9698.7299.0195.35
Strategy②(M=2386)R /%99.0798.7198.7995.44
F1 /%99.0198.7198.9095.39

查看所有表

图 11. Scene II和Scene III场景面状点集分割结果(Nt=15°)。(a) Scene II中MRG结果;(b) Scene II中IMRG结果;(c) Scene III中MRG结果;(d) Scene III中IMRG结果

Fig. 11. Segmentation results of planar point set in Scene II and Scene III (Nt=15°). (a) MRG in Scene II; (b) IMRG in Scene II; (c) MRG in Scene III; (d) IMRG in Scene III

下载图片 查看所有图片

对比两种策略的合并结果,可以发现:

1) 结合距离、分割块相似性和体积变化的合并策略②的整体合并效果优于仅依靠距离条件的合并策略①。利用策略①进行合并时,由于Scene I场景中植被密集,建筑平面容易与相邻的植被分割块合并到一起,致使建筑平面分割精度下降最为明显;Scene II场景中大部分电力线紧挨着建筑平面,致使合并之后电力线召回率R显著降低;Scene III场景中各类别分割块合并后的精度均低于策略②。相比而言,本文提出的合并策略②考虑了分割块之间的相似性和分割前后体积的变化,避免了策略①中存在的问题,使分割块在合并过程中能够基本保持原有的分割精度。

2) 三种场景点云初始分割块数目分别为2028、3787和3376,对比两种策略合并后剩余的分割块数量,利用策略①合并之后的分割块数量更少,这说明分割块的合并程度更深,但是一味地追求合并程度、忽略分割块的精度是没有意义的;与之相对,策略②能够在保持分割精度的情况下有选择的进行合并,同时兼顾了合并程度和分割块精度,合并思路更为合理。

4.4 不同分割方法对比

目前针对点云多要素分割方面的算法较少,为了更好地评估验证本文提出IMRG算法的分割效果,选择了四种典型的方法与本文方法进行对比。Method 1:MRG算法;Method 2:RG+mean shift算法,该算法参考文献[ 17]思路,先采用RG算法进行面状点分割,然后利用mean shift算法对非面状点进行聚类,最后利用本文合并策略对分割结果进行合并;Method 3:采用布料模拟滤波(CSF)[30]与DBSCAN聚类组合的方法——CSF+DBSCAN算法,该算法参考文献[ 16,20]思路,先利用CSF算法去除地面点,然后利用DBSCAN算法对非地面点进行聚类,最后利用本文合并策略对分割结果进行合并; Method 4:本文提出的IMRG算法;Method 5:高斯映射迭代聚类方法(GMIC),该算法借鉴了文献[ 31]的分割思路,先将点云数据进行高斯映射得到高斯球,然后对高斯球上的点迭代进行DBSCAN聚类(由于机载点云中建筑物和地面在高斯球上的映射点相近,聚类过程中难以区分,因此不进行机载点云的分割),最后将迭代剩余点映射回原始空间进行聚类处理,并将分割结果进行合并。其中IMRG算法参数设置参照4.3节,MRG算法生长阈值MtNt以及合并阈值dt均参考IMRG算法;在RG+mean shift算法中,RG算法生长阈值Mtvt均参考IMRG算法,mean shift算法的带宽参数分别设置为8 m、4 m和2 m;CSF+DBSCAN算法中涉及的参数有网格尺寸lc、分类阈值hc、搜索半径rd和最小点数md,具体设置见表7。各种算法在不同场景下点云分割的F1得分分别见表8~10。

表 7. Method 4方法参数

Table 7. Parameters for Method 4

SceneCSFDBSCAN
lc /mhc /mrd /mmd
Scene I0.80.525
Scene II20.40.510
Scene III20.50.530

查看所有表

表 8. Scene I场景分割F1得分

Table 8. F1 score of segmentation in Scene I

MethodF1 /%Time /s
BuildingplanGroundVegetation
Method 176.8485.0390.62294.03
Method 292.9992.1794.714697.64
Method 383.7093.3594.423230.18
Method 493.3489.4693.56372.53

查看所有表

表 9. Scene II场景分割F1得分

Table 9. F1 score of segmentation in Scene II

MethodF1 /%Time /s
Building planGroundVegetationPower line
Method 197.0094.5697.5354.95499.06
Method 298.9497.5798.7493.61943.72
Method 398.6497.5199.1979.061523.06
Method 499.1797.9499.7998.88830.65
Method 597.9095.7196.3678.594627.44

查看所有表

0 Scene III场景分割F1得分

0 F1 score of segmentation in Scene III

Table 1
MethodF1 /%Time /s
Building planGroundVegetationCar
Method 198.5698.1998.4193.89954.01
Method 297.5298.6997.0192.721750.89
Method 393.0896.1889.5882.651218.09
Method 499.0198.7198.9095.39987.68
Method 591.9296.1089.4779.115922.04

分析表8~10中不同算法得到的点云分割结果,可以发现:

1) 本文提出的IMRG算法整体分割效果良好,在分割精度和效率方面都具有一定的优势。IMRG算法在MRG算法基础上进行了优化,分割精度显著提升;同时IMRG算法继承了多点集多规则生长的特色,能够根据不同要素的特点分别进行分割。相比而言,RG+mean shift算法和CSF+DBSCAN算法无法概括点云整体场景的特点,特别是缺乏对杆状、线状地物的描述,影响分割精度;GMIC算法可以较好地提取面性点,但对于法向量杂乱的非面性点难以有效分割;如图12所示,部分电力线被错误地分割到了建筑物中,GMIC算法建筑分割结果中还包括了部分植被点。

图 12. 错误分割。(a) RG+mean shift;(b) CSF+DBSCAN;(c) GMIC

Fig. 12. Incorrect segmentation. (a) RG+mean shift; (b) CSF+DBSCAN; (c) GMIC

下载图片 查看所有图片

2) 在分割精度方面,IMRG算法整体优于其他算法,但在Scene I场景的地面和植被分割中精度低于RG+mean shift算法和CSF+DBSCAN算法。分析其原因,Scene I场景覆盖范围大、地形起伏变化明显,利用维数特征进行点集分类的误分率增大,部分地面点没能正确归入面状点集,如表11所示,与其他算法相比,IMRG算法中得到的地面分割块有效点数偏少;同时,点集分类误差也使得地面点中包含植被点云的可能性增大,最终影响了地面分割块的精度,从表11中也可以看出IMRG算法得到的地面分割块中错误点数偏多。

1 Scene I场景地面分割结果

1 Segmentation results of ground in Scene I

Table 1
MethodTPFP
RG+mean shift35170829669
CSF+DBSCAN36459434771
IMRG34050238946

3) 在分割耗时方面,IMRG算法时间略多于MRG算法,这是由于IMRG算法增加了种子点判断条件和合并条件,延长了面状点集生长迭代和分割块合并的时间。RG+mean shift算法、CSF+DBSCAN算法和GMIC算法耗时长,这与聚类算法复杂度高、计算效率低有关。

5 结论

本文立足于点云场景多要素分割需求,在多规则区域生长算法的基础上,提出了一种改进的多规则区域生长算法。该方法保持了原有算法的优势,对面状点集分割和分割块合并两方面内容进行了优化,同时探索了相关阈值参数自适应设置的方法。在面状点集分割方面,分析了MRG算法误分割现象产生的原因,然后采取相应的措施——利用平面拟合残差设置种子点条件,提升了面状点集分割的精度;在分割块合并方面,针对单一距离因素合并效果差的问题,增加了分割块相似性条件和体积变化条件,保证了分割块合并的准确性;在阈值自适应设置方面,结合各参数的特点,分别采用中位数、Baarda数据探测法、k均值聚类等方法实现阈值参数的自适应设置,提升了算法的自适应性。利用三组数据进行实验,结果表明本文算法所具有的优势——面状地物分割的准确性得到了提升,同时能够兼顾合并程度和分割块精度。

本文算法可以有效实现点云场景的多要素分割,为点云地物识别和提取、点云分类等应用提供了有效支持。但同时本文算法还存在一定的优化空间,包括点云最优邻域的快速计算以及点云杆状、面状和体状数据维数特征分类方法的改善等,这些问题的解决将有助于算法进一步获取更优的点云多要素分割结果。

参考文献

[1] 李明磊, 宗文鹏, 李广云, 等. 基于体素生长的点云结构直线段提取[J]. 光学学报, 2018, 38(1): 0112001.

    Li M L, Zong W P, Li G Y, et al. Extraction of structure line segments from point clouds using voxel-based region growing[J]. Acta Optica Sinica, 2018, 38(1): 0112001.

[2] Wang Y, Cheng L, Chen Y M, et al. Building point detection from vehicle-borne LiDAR data based on voxel group and horizontal hollow analysis[J]. Remote Sensing, 2016, 8(5): 419.

[3] 方莉娜, 黄志文, 罗海峰, 等. 车载激光扫描数据中实线型交通标线提取[J]. 测绘学报, 2019, 48(8): 960-974.

    Fang L N, Huang Z W, Luo H F, et al. Solid lanes extraction from mobile laser scanning point clouds[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(8): 960-974.

[4] 马振宇, 庞勇, 李增元, 等. 地基激光雷达森林近地面点云精细分类与倒木提取[J]. 遥感学报, 2019, 23(4): 743-755.

    Ma Z Y, Pang Y, Li Z Y, et al. Fine classification of near-ground point cloud based on terrestrial laser scanning and detection of forest fallen wood[J]. Journal of Remote Sensing, 2019, 23(4): 743-755.

[5] 冯佳睿, 马晓丹, 关海鸥, 等. 基于深度信息的大豆株高计算方法[J]. 光学学报, 2019, 39(5): 0515003.

    Feng J R, Ma X D, Guan H O, et al. Calculation method of soybean plant height based on depth information[J]. Acta Optica Sinica, 2019, 39(5): 0515003.

[6] Ballard D H. Generalizing the Hough transform to detect arbitrary shapes[J]. Pattern Recognition, 1981, 13(2): 111-122.

[7] Fischler M A, Bolles R C. Random sample consensus[J]. Communications of the ACM, 1981, 24(6): 381-395.

[8] Lari Z, Habib A. An adaptive approach for the segmentation and extraction of planar and linear/cylindrical features from laser scanning data[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 93: 192-212.

[9] 王晓辉, 吴禄慎, 陈华伟, 等. 基于区域聚类分割的点云特征线提取[J]. 光学学报, 2018, 38(11): 1110001.

    Wang X H, Wu L S, Chen H W, et al. Feature line extraction from a point cloud based on region clustering segmentation[J]. Acta Optica Sinica, 2018, 38(11): 1110001.

[10] Rabbani T, Heuvel F A, Vosselman G. Segmentation of point clouds using smoothness constraint[J]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2006, 36(5): 248-253.

[11] Vo A V, Truong-Hong L, Laefer D F, et al. Octree-based region growing for point cloud segmentation[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2015, 104: 88-100.

[12] Zhang J X, Duan M Y, Yan Q, et al. Automatic vehicle extraction from airborne LiDAR data using an object-based point cloud analysis method[J]. Remote Sensing, 2014, 6(9): 8405-8423.

[13] 赵宗泽, 张永军. 基于植被指数限制分水岭算法的机载激光点云建筑物提取[J]. 光学学报, 2016, 36(10): 1028002.

    Zhao Z Z, Zhang Y J. Building extraction from airborne laser point cloud using NDVI constrained watershed algorithm[J]. Acta Optica Sinica, 2016, 36(10): 1028002.

[14] 陈明猷, 唐昀超, 邹湘军, 等. 复杂环境下异形多目标识别与点云获取算法[J]. 激光与光电子学进展, 2018, 55(11): 111505.

    Chen M Y, Tang Y C, Zou X J, et al. Multi-shaped targets recognition and point clouds acquisition algorithm in complex environment[J]. Laser & Optoelectronics Progress, 2018, 55(11): 111505.

[15] Vosselman G, Coenen M, Rottensteiner F. Contextual segment-based classification of airborne laser scanner data[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2017, 128: 354-371.

[16] Tong G F, Li Y, Zhang W L, et al. Point set multi-level aggregation feature extraction based on multi-scale max pooling and LDA for point cloud classification[J]. Remote Sensing, 2019, 11(23): 2846.

[17] 吴腾. 机载LiDAR点云面向对象的分类与建筑物提取[D]. 武汉: 武汉大学, 2016: 11- 43.

    WuT. Object oriented classification and building extraction using airborne LiDAR point clouds[D]. Wuhan: Wuhan University, 2016: 11- 43.

[18] 董震, 杨必胜. 车载激光扫描数据中多类目标的层次化提取方法[J]. 测绘学报, 2015, 44(9): 980-987.

    Dong Z, Yang B S. Hierarchical extraction of multiple objects from mobile laser scanning data[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(9): 980-987.

[19] 罗海峰, 方莉娜, 陈崇成, 等. 基于DBN的车载激光点云路侧多目标提取[J]. 测绘学报, 2018, 47(2): 234-246.

    Luo H F, Fang L N, Chen C C, et al. Road side multiple objects extraction from mobile laser scanning point cloud based on DBN[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(2): 234-246.

[20] 范小辉, 许国良, 李万林, 等. 基于深度图的三维激光雷达点云目标分割方法[J]. 中国激光, 2019, 46(7): 0710002.

    Fan X H, Xu G L, Li W L, et al. Target segmentation method for three-dimensional LiDAR point cloud based on depth image[J]. Chinese Journal of Lasers, 2019, 46(7): 0710002.

[21] 杨必胜, 董震, 魏征, 等. 从车载激光扫描数据中提取复杂建筑物立面的方法[J]. 测绘学报, 2013, 42(3): 411-417.

    Yang B S, Dong Z, Wei Z, et al. Extracting complex building facades from mobile laser scanning data[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(3): 411-417.

[22] 卢维欣, 万幼川, 何培培, 等. 大场景内建筑物点云提取及平面分割算法[J]. 中国激光, 2015, 42(9): 0914004.

    Lu W X, Wan Y C, He P P, et al. Extracting and plane segmenting buildings from large scene point cloud[J]. Chinese Journal of Lasers, 2015, 42(9): 0914004.

[23] Yang B S, Dong Z, Liu Y, et al. Computing multiple aggregation levels and contextual features for road facilities recognition using mobile laser scanning data[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2017, 126: 180-194.

[24] 范金城, 梅长林. 数据分析[M]. 2版. 北京: 科学出版社, 2010: 1- 11.

    Fan JC, Mei CL. Data analysis[M]. 2nd ed. Beijing: Science Press, 2010: 1- 11.

[25] Barber C B, Dobkin D P, Huhdanpaa H. The quickhull algorithm for convex hulls[J]. ACM Transactions on Mathematical Software, 1996, 22(4): 469-483.

[26] 隋立芬, 宋力杰, 柴洪洲. 误差理论与测量平差基础[M]. 北京: 测绘出版社, 2010: 194- 199.

    Sui LF, Song LJ, Chai HZ. Error theory and foundation of surveying adjustment[M]. Beijing: Surveying and Mapping Press, 2010: 194- 199.

[27] Roynard X, Deschaud J E, Goulette F. Paris-Lille-3D: a large and high-quality ground-truth urban point cloud dataset for automatic segmentation and classification[J]. The International Journal of Robotics Research, 2018, 37(6): 545-557.

[28] Weinmann M, Jutzi B, Mallet C. Semantic 3D scene interpretation: a framework combining optimal neighborhood size selection with relevant features[J]. ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2014, 2(3): 181-188.

[29] Weinmann M, Jutzi B, Hinz S, et al. Semantic point cloud interpretation based on optimal neighborhoods, relevant features and efficient classifiers[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2015, 105: 286-304.

[30] Zhang W M, Qi J B, Wan P, et al. An easy-to-use airborne LiDAR data filtering method based on cloth simulation[J]. Remote Sensing, 2016, 8(6): 501.

[31] Zhao B F, Hua X H, Yu K G, et al. Indoor point cloud segmentation using iterative Gaussian mapping and improved model fitting[J]. IEEE Transactions on Geoscience and Remote Sensing, 2020, 58(11): 7890-7907.

汪文琪, 李宗春, 付永健, 何华, 熊峰. 基于改进多规则区域生长的点云多要素分割[J]. 光学学报, 2021, 41(5): 0528001. Wenqi Wang, Zongchun Li, Yongjian Fu, Hua He, Feng Xiong. Multi-Factor Segmentation of Point Cloud Based on Improved Multi-Rule Region Growing[J]. Acta Optica Sinica, 2021, 41(5): 0528001.

本文已被 11 篇论文引用
被引统计数据来源于中国光学期刊网
引用该论文: TXT   |   EndNote

相关论文

加载中...

关于本站 Cookie 的使用提示

中国光学期刊网使用基于 cookie 的技术来更好地为您提供各项服务,点击此处了解我们的隐私策略。 如您需继续使用本网站,请您授权我们使用本地 cookie 来保存部分信息。
全站搜索
您最值得信赖的光电行业旗舰网络服务平台!