引言

近年来，地面激光扫描(terrestrial laser scanning, TLS)作为测绘领域的高新技术，能够高精度、高效地获取地物的空间坐标，广泛应用于古建筑物测绘和城市建模等领域^[1], 特别是丰富的立面信息，使城市精细化建模成为可能^[2]。由于原始点云呈现无序性和散乱性，需要分割等方法识别场景中的几何基元，点云分割是建筑物提取、几何特征识别和建筑重建的重要步骤。

点云分割算法分为3类：特征聚类^[3]、区域增长^[4]和模型拟合^[5-6]。特征聚类方法分为边缘提取和聚类两个步骤，传统方法利用法向量变化来提取边缘，边缘质量受边界点法向量估算精度的影响^[7]。为避免边界点法向量的直接估算，CHE等人利用最近邻点构建多个三角形的法向量夹角选择边界点^[8]，MINEO等人通过邻域在投影平面上的包含路径确定真实边界点^[9]。聚类算法有k均值聚类算法、k最近邻算法(k-nearest neighbor, KNN)算法和基于密度的聚类算法(density-based spatial clustering of applications with noise, DBSCAN)等^[10]。此类方法易受噪声的影响，同时，点云密度不均匀直接影响邻域的确定。区域增长算法实质上是种子点根据判断准则(距离阈值，法向量阈值)的生长过程，其中，平面拟合残差广泛应用于此类算法中^[11]，如LU等人使用主成分分析法将平面点为种子点，单独将边界点划分至分割结果，保证边界处分割的准确性^[12]。模型拟合算法是依据预设模型与原始点云的拟合进行点云分割，使用的几何基元决定着分割精度^[13]，其中效果较好的是霍夫变换(Hough transform, HT)^[14]和随机采样一致性(random sample consensus, RANSAC)^[15]两种方法，后者效率和准确度较高^[16]。尽管目前对RANSAC的研究已较为深入^[17-18]，但时间复杂度的影响使得模型拟合算法较难应用到大场景点云中。

随着扫描硬件的优化，地面激光扫描的测程不断增加，增加了激光扫描的覆盖范围、应用场景，但也带来了场景内点云密度显著变化等问题，目前已有的分割方法较少考虑和讨论密度变化对分割的影响。邻域选择是密度变化带来的影响之一，适应于低密度区域的邻域参数可能难以在高密度区域形成有效邻域^[19]。已有方法通常通过设置固定搜索范围来解决邻域尺度不统一的问题，并通过香农熵^[20]、曲率一致性水平^[21]等指标选择搜索范围内的最佳邻域，但算法效率易受搜索范围大小的影响，例如，在最大扫描距离为1 km、角分辨率为0.06°的点云中，点间距从毫米级到米级，为固定邻域范围带来问题。WU等人通过拟合半变异函数设计多尺度张量的尺度范围来解决显著密度变化的影响，尽管此范围为动态范围，但拟合半变异函数的计算对算法效率影响较大^[22]。

针对上述问题，本文中提出了一种基于动态邻域搜索范围的平面分割算法，该算法由角分辨率和扫描距离等因素动态生成邻域搜索范围以消除显著密度变化的影响；根据最佳邻域和局部几何特征(法向量、点面距和维度特征)确定种子点和生长规则，提高点云分割的质量。

1.   基本原理

本文中的算法首先通过布料模拟滤波(cloth simu- lation filter, CSF) 过滤地面点, 基于随机非地面点邻域估算角分辨率, 并依据角分辨率和扫描距离估算理论点间距。然后面向单点理论点间距$d_{i}(i=1, 2, \cdots, N$; $N$为点云总数), 设计满足局部密度的动态邻域搜索范围, 为避免此范围过大影响效率, 按一定间隔$d_{i}$取值作为聚类半径, 使用$\mathrm{KNN}$算法聚类, 在此基础上使用内指标评价聚类结果得到最佳聚类半径, 以此半径为中心$d_{i}$为区间左右跨度提取有效子集, 并在有效子集中通过香农熵确定最佳邻域和维度特征。根据维度特征提取建筑物和种子点, 在最佳邻域中依据局部几何特征(点面距, 法向量) 设计生长规则进行平面分割, 最终通过面片合并优化结果。算法流程见图 1。

图  1  算法流程图

Figure  1.  Algorithm flow chart

下载: 全尺寸图片 幻灯片

1.1   最佳邻域搜索

1.1.1   使用随机点邻域分析的角分辨率估算

角分辨率是地面激光扫描仪水平或垂直相邻激光束之间的夹角，针对扫描仪采集参数未知的情况，使用随机点邻域分析估算理论角分辨率。

对于非地面点云, 随机选取$n$个点$P_{c}(c=1, 2, \cdots$, $n)$, 使用$\mathrm{KNN}$算法搜索其$k$个最近邻点$P_{c_{j}}(j=1, 2$, $\cdots, k)$, 并计算出$P_{c_{j}}$与$P_{c}$的水平夹角(或垂直夹角)。同时, 以$\Delta$为区间宽度建立直方图, 统计每个区间内的点数, 如图 2所示。根据采集原理, 与$P_{c}$所在扫描线相邻的扫描线上的邻近点最多^[23], 故将点数最多区间内水平夹角(或垂直夹角) 的平均值作为角分辨率。为了降低参数$\Delta$对角分辨率估算的影响, 区间宽度$\Delta \in$ $\left[0.005^{\circ}, 0.015^{\circ}\right]$, 取值间隔为$0.001^{\circ}$, 分别构建不同$\Delta$下的直方图。取所有角分辨率的中间值, 即为最终的角分辨率。

图  2  水平夹角直方图构建

Figure  2.  Construction of horizontal angular interval histograms

下载: 全尺寸图片 幻灯片

1.1.2   动态邻域搜索范围构建

地面激光点云密度与扫描距离直接相关，基于不同扫描距离下的理论点间距设计邻域是解决密度变化问题的有效思路。根据角分辨率和扫描距离，理论点间距d_i表示为：

式中, $\beta$为角分辨率对应的弧度, $D_{i}$为$i$点的扫描距离。

任一点的最佳邻域，其邻域半径在理论点间距的1~10倍之间^[24]，即任一点的动态邻域搜索范围为$\left[d_{i}, 10 d_{i}\right]$, 该范围充分考虑局部点云密度，但仍有较多无效子集，使用香农熵查找最佳邻域的效率受无效子集影响较大，依据聚类结果的有效性评价指标去除无效子集。

1.1.3   基于内部指标和香农熵的邻域评估

在动态邻域搜索范围内取$I$倍的$d_{i}(I=1, 2, \cdots, 10)$为聚类半，以此为中心获取有效子集，并通过香农熵计算最佳邻域和维度特征。聚类结果的有效性评价指标可以分为两类：内部指标和外部指标^[25]。内部指标仅依靠分类后数据集自身的特征对结果进行评判，外部指标需要借助数据真实情况进行对比分析，可以验证内部指标的有效性。考虑到算法效率，本文中使用戴维森-堡丁内(Davies-Bouldin，DB)指标来确定最佳倍数。

若聚类结果为$C=\left\{c_{1}, c_{2}, \cdots, c_{m}\right\}, \mathrm{DB}$指标^[25]的计算如下:

式中, $S$表示DB指标大小; $\operatorname{avg}\left(c_{a}\right)$和$\operatorname{avg}\left(c_{b}\right)$分别表示$a$类、$b$类点间距的平均值; $d\left(c_{a}, c_{b}\right)$表示$a$类和$b$类几何中心的距离, $a, b=1, 2, \cdots, m$, 且$a<b$。

根据DB指标最小的原则篮选最佳聚类结果, 其聚类半径对应$d_{i}$的倍数为$I_{1}$。取$\left[\left(I_{1}-1\right) d_{i}, \left(I_{1}+1\right) d_{i}\right]$为动态邻域搜索范围内的有效子集, 并在此范围内取香农熵最小值为最佳邻域。香农熵E^[20]的计算如下：

式中, $\lambda_{1}, \lambda_{2}, \lambda_{3}$为邻域拟合平面的特征值, 分别代表三轴方向的残差, 且$\lambda_{1} \geqslant \lambda_{2} \geqslant \lambda_{3}$, 在有效子集中根据$E$最小的原则篮选最佳邻域, 并结合$\lambda_{1}, \lambda_{2}$和$\lambda_{3}$得到点所属维度$F$ :

式中，F∈[0, 2]，分别对应1维特征(线状点)、2维特征(平面点)、3维特征(离散点)，如图 3所示。

图  3  维度特征

Figure  3.  Dimensionality feature

下载: 全尺寸图片 幻灯片

1.2   点云分割

区域增长算法的两个关键问题是种子点的选取和生长准则。传统的方法依赖于法向量和点间距，由于边界点法向量的估算精度较低，边界处分割结果有较大误差，如图 4a所示，同时点间距直接受点云密度的影响。基于上述问题，联合最佳邻域和维度特征，改进的方法如下：

图  4  边界分割结果

a—传统区域增长 b—改进区域增长

Figure  4.  Edge segmentation result

a—traditional region growing  b—improved region growing

下载: 全尺寸图片 幻灯片

(1) 按每一类平面点的比例，筛选建筑物，在各建筑物中执行下述操作。

(2) 设置空集合，随机选取一平面点进入集合作为种子点。

(3) 在种子点的最佳邻域中搜索待生长点，将满足以下两个条件的平面点加入集合中。

式中, $\boldsymbol{n}$表示以种子点为起点、以待生长点为终点的向量; $\boldsymbol{n}_{1} 、\boldsymbol{n}_{2}$分别为种子点、待生长点的法向量; $\delta$为点面距阈值; $\varphi$为法向量夹角阈值。

(4) 选取集合中未进行生长的点作为新的种子点，重复第(3)步过程，直至满足条件的平面点全部进入集合，即为一个平面。

(5) 当前建筑物中是否存在未进入任何集合的平面点?若是，则新设空集合，并从当前建筑物剩余平面点中随机选择一点进入集合作为种子点，重复第(3)、第(4)步过程。直至全部平面点已进入某一集合。

平面不仅包含平面点，也包含诸如边界等的线状点，由于区域增长仅针对平面点进行设计，此时的分割结果并不包含线状点，需要将每个建筑物簇中的线状点按距离分配至最近平面以得到初步平面分割结果。同时由于地物遮挡，平面部分信息丢失，存在过分割的情况，面片合并是解决此问题的常用方法，原理是基于法向量夹角阈值和最近邻距离阈值对两个邻近平面进行判断，将满足要求的面片合并，得到完整平面，如图 4b所示。

2.   实验结果与分析

2.1   实验数据

本文中使用最大扫描距离为1 km的TLS数据进行算法有效性的测试，数据采集于重庆市来福士广场，如图 5所示。场景中一共有5330542个点，建筑物平均点间距为[0.012 m, 0.623 m]。区域Ⅰ、区域Ⅱ、区域Ⅲ的平均扫描距离分别为850 m、20 m、500 m。

图  5  原始数据

Figure  5.  Original data

下载: 全尺寸图片 幻灯片

2.2   有效性分析

重庆市地形复杂，为准确过滤地面点，根据实验经验，CSF的参数如表 1所示。地面点主要集中在测站点，测站处的地面滤波结果见图 6。

表  1  CSF参数

Table  1.  Parameters of CSF

method	cloth resolution/m	classification threshold/m	iterations	rigidness/(N·m-1)
CSF	1.2	0.02	500	2

下载: 导出CSV 

| 显示表格

图  6  地面滤波结果

Figure  6.  Result of the ground filtering

下载: 全尺寸图片 幻灯片

利用随机邻域点分析方法得到的水平角分辨率和垂直角分辨率均为0.0357°。在动态邻域搜索范围中选取I倍的d_i作为KNN聚类半径得到10个聚类结果，通过DB内指标选取最佳聚类结果，同时使用人工分割结果计算Rand外部指标^[25]，对选取结果进行验证，如图 7所示。内外指标确定出最佳聚类结果对应的I相同，验证了DB指标的合理性。此时区域Ⅰ、区域Ⅱ和区域Ⅲ的聚类结果如图 8所示, 不同颜色代表不同的类或平面。在此基础上，使用香农熵进一步在有效子集内选取最佳邻域半径的系数，见图 7b。

图  7  最佳邻域半径选择

a—动态邻域搜索范围下的有效范围筛选 b—有效范围内的最佳邻域半径

Figure  7.  Optimal neighborhood radius selection

a—valid range filtering of dynamic neighborhood search range  b—optimal neighborhood radius in the valid range

下载: 全尺寸图片 幻灯片

图  8  聚类结果

Figure  8.  Clustering results

下载: 全尺寸图片 幻灯片

为验证基于有效子集计算的邻域半径为最佳值，随机选取30个点，基于整个动态邻域搜索范围计算香农熵E最小值，以得到理论上的最佳邻域半径，并与本文中的算法得到的邻域半径进行对比，如图 9所示。其中相对误差都小于1%，如图 10所示。

图  9  理论最佳邻域半径与实验最佳邻域半径对比图

Figure  9.  Comparison of theoretical optimal neighborhood radius and true optimal neighborhood radius

下载: 全尺寸图片 幻灯片

图  10  最佳邻域半径的相对误差

Figure  10.  Relative error of true optimal neighborhood radius

下载: 全尺寸图片 幻灯片

表 2中设置了点云分割的相关参数。根据实验经验，平面点比例阈值ζ设置为60%~80%，点面距阈值δ设置为0.05 m~0.15 m，法向量夹角阈值φ为0.05°~ 0.15°时，点云分割效果较好。

表  2  算法参数

Table  2.  Algorithm parameters

object	ζ/%	δ/m	φ/(°)
long-range TLS point cloud	70	0.05	0.05

下载: 导出CSV 

| 显示表格

初始分割结果存在过分割现象，如图 11a所示。进行面片合并，将法向量夹角阈值设为0.15°，将最近邻距离阈值设置为0.5 m，效果如图 11b所示。若将最近邻距离阈值设置为1 m，此区域将存在欠分割，如图 11c所示。因此，在长测距点云中，选取合适的最近邻距离阈值可有效消除过分割并避免欠分割。

图  11  面片合并

a—距离阈值0.1 m  b—距离阈值0.5 m  c—距离阈值1 m

Figure  11.  Patch combination

a—distance threshold of 0.1 m  b—distance threshold of 0.5 m  c—distance threshold of 1 m

下载: 全尺寸图片 幻灯片

最终分割结果如图 12所示。根据准确率和召回率进行精度评价，见表 3。本文中的算法与使用固定距离阈值(平均点间距)的区域增长算法相比，准确度和召回率提高了60%左右，与使用固定搜索范围的香农熵算法相比，查询时间由5400 s降为600 s。

图  12  平面分割结果

Figure  12.  Plane segmentation results

下载: 全尺寸图片 幻灯片

表  3  分割结果评价

Table  3.  Analysis of segmentation result

method	precision/%	recall/%	time/s
traditional method (the fixed radius 0.461 m)	33	20	—
Shannon entropy based on the fixed neighborhoods search range	92	93	5400
the proposed method (optimal neighborhood radius)	95	92	600

下载: 导出CSV 

| 显示表格

3.   结论

面向点云密度变化在地基点云分割中带来的邻域选择问题，提出一种基于动态邻域搜索范围的长测距地基点云平面分割方法。实验结果表明：本文中的平面分割方法的准确率达到95%，召回率达到92%，能有效满足显著密度变化点云分割的需要。同时，与基于固定搜索范围的方法相比，本文中使用动态邻域的方法可以将最佳邻域查询时间由5400 s缩短至600 s，在保证分割精度的基础上显著提高分割效率。结合最佳邻域和维度特征改进区域生长算法，消除了密度变化对平面分割的影响，保证了边界处分割的准确性。下一步研究将联合多站TLS点云进行平面分割，并根据分割结果实现建筑物重建。