论文 # 一种改进的自动估计Eps参数的激光雷达数据分割DBSCAN方法 王春晓 $^{1,2}$，纪敏 $^{1,*}$，王健 $^{1}$，文伟 $^{2}$，李婷 $^{1}$，孙勇 $^{1}$ 1 山东科技大学测绘学院，青岛 266590，中国； (C.W.)； (J.W.)； (T.L.)； (Y.S.) 2 国家测绘地理信息局海南测绘中心，海口 570203，中国； 通讯作者：；电话：+86-150-532-07989 收稿日期：2018年11月8日；录用日期：2019年1月2日；发表日期：2019年1月5日 ![Image](images/b6bdf69a134c2dfae7e9a6e1450e3d0c201f9b0c9a25a9b9647a51b5da4e231d.jpg) 摘要：点云数据分割、滤波、分类和特征提取是点云数据处理的主要研究内容。DBSCAN（具有噪声的基于密度的应用空间聚类算法）能够在任意维度的空间中检测任意形状的簇，该方法非常适合LiDAR（光探测与测距）数据分割。DBSCAN方法至少需要两个参数：最小点数minPts和搜索半径ε。然而参数ε通常更难确定，这阻碍了DBSCAN方法在点云分割中的应用。因此，本文提出一种基于DBSCAN的分割算法，带有一种全新的自动参数ε估计方法——基于k近邻最大距离平均值的估计方法，该方法可以根据点云数据的固有特性计算参数ε。该方法基于k和平均最大距离的拟合曲线。我们在不同类型的点云数据上对该方法进行了评估：机载点云，以及带颜色信息和不带颜色信息的移动点云数据。结果表明，使用本文提出方法估计得到的ε，精度分别为75%、74%和71%，均高于使用小于或大于该估计值参数得到的精度。结果表明，本文提出的算法能够以稳健的方式对不同类型的LiDAR点云实现更高精度的分割。该算法可应用于机载和移动LiDAR点云数据处理系统，能够减少人工工作量，提高数据处理的自动化程度。 ## 1. 引言 关键词：LiDAR；分割；DBSCAN；参数估计 激光雷达（LiDAR，即光探测与测距）技术具备数据密度高、精度高、作业效率高、穿透力强的优势。除传统野外测量与遥感[^1]外，LiDAR技术还广泛应用于诸多其他领域，例如森林生态[^2] [^3] [^4] [^5]、城市变化检测[^6]、城市道路检测与规划[^7] [^8]、机器人环境感知[^9]以及自动驾驶技术[^10]，并在这些领域发挥着日益重要的作用。然而，LiDAR点云数据的解译仍是基础研究领域的一项挑战。激光扫描技术是一种新型的对地观测技术，但相较于激光扫描系统硬件的快速发展，点云数据处理与应用的研究相对滞后。目前，尽管学界已在点云分割、滤波、分类和特征提取研究中取得了一系列成果，但这些方法主要适用于特定数据集，或是要求用户对 --- 数据拥有充分的先验认知。利用现有点云数据处理方法仍难以实现快速、全自动的高精度分割。 本研究聚焦于点云自动分割问题，提出了一种DBSCAN（具有噪声的基于密度的空间聚类）参数估计方法。该方法在不同类型的点云数据上进行了评估，结果显示其在机载和移动LiDAR数据实验中表现良好。 ### 2. LiDAR数据分割的相关研究 点云数据分割是场景重建和目标识别的基础，也是点云数据处理的关键步骤。当前主流的点云分割算法主要包括基于聚类的算法、模型拟合算法、区域生长算法以及其他分割方法。 #### 2.1. 基于聚类的方法 基于密度的聚类方法，例如DBSCAN [^11]、OPTICS（排序点以识别聚类结构）[^12]和DENCLUE（基于密度的聚类）[^13]等，能够检测任意形状的聚类[^14]。LiDAR数据的聚类本身具有任意形状和不同密度，因此聚类方法适用于LiDAR数据分割[^15]。 然而，目前鲜有研究论证DBSCAN方法用于LiDAR数据分割的效率和自动分割效果。半径参数$\varepsilon$通常难以设定。现有使用DBSCAN进行LiDAR分割的研究主要针对特定数据，例如必须充分了解每个LiDAR数据集，再仔细挑选参数值$\varepsilon$。从DBSCAN的设计原理来看，$\varepsilon$应尽可能小，且$\varepsilon$的取值还取决于距离函数。在理想情况下，可凭借领域知识结合应用场景选择合适参数[^16]，也就是说，用户必须非常了解数据，才能谨慎地选择$\varepsilon$。这种情况阻碍了DBSCAN在自动聚类中的应用。 Ester等人[^11]曾尝试开发一种简单有效的启发式方法，利用k-距离图确定该算法的参数$\varepsilon$和minPts。k-距离图将每个点映射到其第k近邻的距离。作者指出，对于二维数据，所有k > 4的情况，所得的图与4-距离图没有显著差异。但这个过程交互性较强，作者推荐使用k-距离图的图形表示来帮助用户估计正确的阈值。在广义DBSCAN中，Sander等人[^17]利用k-距离图确定参数，建议使用$(2\cdot dim - 1)$近邻，且minPts = 2\cdot dim（dim为数据集的维度），而k-距离图中k的值需要由用户提供。Daszykowski、Walczak和Massart尝试为化学应用建立经验法则，但这些法则需要在LiDAR数据上进行测试[^18]。 尽管参数估计方法已有研究，但对于同一种估计方法也存在不同观点。例如，针对来自UCI（加州大学欧文分校）机器学习库$[0;10^5]$、归一化为整数的家庭数据集[^19]的聚类问题，Schubert和Sander提出，$\varepsilon$的最小值显然应当选择在$\varepsilon < 2000$以下[^18]，而Gan和Tao则建议改用$\varepsilon \geq 5000$[^20]。 Ghosh和Lohani研究了DBSCAN和OPTICS在LiDAR数据上的效果。他们的结果表明，根据ARI（调整兰德指数，由Hubert和Arabie提出的一种衡量两种不同聚类方法之间相似度的指标[^21]），DBSCAN的表现相对更好。该研究中所用的阈值是通过实验确定的，实验测试的阈值范围从低值0.7 m到高值4.0 m[^15] [^22]。因此，强烈推荐开展利用LiDAR数据参数自动确定阈值的分析研究[^22]。Lari和Habib在自适应LiDAR数据处理中，将点之间的三维关系以及点所属表面的物理性质纳入了考虑[^23]。 --- 目前许多分割研究论文都基于另一种聚类方法展开。Biosca和Lerma提出了一种基于模糊C均值算法（FCM）的平面提取算法[^24]。Filin提出了一种表面聚类算法，实现了房屋与植被点云的分割[^25]。Jiang提出了自组织映射（SOM）算法，并将其应用于点云特征提取[^26]，该算法可在无需先验知识的情况下完成无监督分类，但该方法的学习过程仍依赖于输入参数。Morsdorf等人利用K均值聚类算法，在机载点云数据中实现了林区单木的提取[^27]。Roggero利用三维张量生成n维特征向量，并采用层次聚类算法对机载点云数据进行分割[^28]。Biosca和Lerma提出了一种基于模糊C均值（FCM）模糊聚类的平面提取算法[^24]。Crosilla等人利用二阶泰勒展开从邻域点集中检测高斯曲率和平均曲率，并通过聚类将点云划分为规则几何形状[^29]。常用的空间分割方法有K最近邻（KNN）和最大似然法。Jain和Duin等人总结了统计模式识别的其他多种方法[^30]。 总体而言，在激光点云数据分割领域，学者们已经开展了大量研究并取得了诸多成果。然而，这些基于聚类的分割方法大多仅适用于某些特定数据；多数方法依赖人工经验，能够实现自动分割的方法较少。部分聚类方法对输入参数非常敏感，微小差异就会导致完全不同的聚类结果。尽管上述研究人员取得了良好的实验效果，但他们的分割精度依赖于人工定义的分割参数，而这些参数大多与设备和具体数据相关。 基于上述研究，本文提出了一种基于DBSCAN密度聚类的参数估计方法，该方法将在第3.2节中详细介绍。 #### 2.2 基于模型拟合的方法 基于模型拟合的方法主要分为两类：霍夫变换（HT）[^31] [^32]，以及由Fischler和Bolles于1981年提出的随机抽样一致（RANSAC）方法[^33]。HT方法用于检测点云中的平面、圆柱和球体。Hoffman和Jain [^34]总结了激光点云数据中边界的三种基本形式：跳变边、折痕边和平滑边。基于这些基本形式，基于模型拟合的方法逐步发展起来。Yang等人提出了一种从LiDAR点云中两步自适应提取地面点和断裂线的方法[^35]。Maas和Vosselman利用不变矩方法重建了规则建筑模型[^36]。 在RANSAC方法中，研究人员利用候选形状基元对所有点进行检验，以确定最佳模型拟合[^33]。该方法已被应用于点云分割领域。例如，Riveiro等人采用基于路面分割的自动检测方法，从移动激光雷达数据中识别出斑马线[^37]。Neidhart利用原始激光雷达点云数据提取与高程和几何相关的建筑物信息，再通过图形化方法重建建筑物[^38]。Woo等人、Su等人和Vo等人提出了基于八叉树三维格网的点云数据分割方法，用于处理大量无序点数据集[39–41]。Boulaassal等人利用RANSAC算法从地面激光扫描仪数据中提取建筑物立面平面[^42]。Schnabel等人利用RANSAC，通过对平面、球体、圆柱体等形状进行随机采样，检测散乱点云的形状[^43]。Awwad等人基于点的法向量将数据集划分为小簇，对RANSAC算法进行了改进[^44]。Schwalbe等人将两个或多个相邻平面分组，结合二维GIS（地理信息系统）数据生成三维建筑物模型[^45]。Moosmann等人采用基于图的方法，利用统一的 --- 基于局部凸性度量的通用准则，从三维激光雷达扫描数据中分割地面和目标[^46]。密集三维数据（例如Riegl扫描）的分割通过简单高效的空间体素化得到了优化[^47]。 HT方法和RANSAC方法都是鲁棒性良好的点云分割方法，其中RANSAC方法的优势在于能够处理大量噪声。但这些方法也存在缺陷：它们在具有复杂几何结构的数据集上表现不佳，且HT方法对表面参数的选择较为敏感。 #### 2.3 基于区域生长的方法 目前已有大量基于区域生长法的分割研究。Besl等人将变阶高次多项式用作曲面拟合函数，通过种子点扩展法完成点云分割[^48]。但不规则复杂曲面的分割效果仍有待提升。Rabbani等人提出了基于平滑约束的生长算法，可将点云数据分割为平滑曲面[^49]。Vo等人提出了一种基于八叉树的区域生长点云分割方法，遵循由粗到细的思路分为两个阶段实现[^41]。总体而言，基于区域生长的分割方法可以实现点云数据分割，但种子点和参数的选择仍需要人工干预确定，参数设置对分割结果影响很大，因此分割结果稳定性不足。 #### 2.4 其他分割方法 点云分割还有许多其他方法，例如Delaunay三角剖分[^50]、小波变换[^51]、三维网格法[^39]、线跟踪算法[^45]等。Höfle等人提出了一种新的GIS工作流，结合决策树和人工神经网络（ANN）分类器，利用激光雷达数据完成城市植被制图[^52]。Niemeyer等人将随机森林分类器集成到条件随机场（CRF）框架中，利用该框架可以非常可靠地检测出主体建筑物（面积大于50 m²）[^53]。 激光扫描技术的应用研究并不局限于地球科学与测绘领域，从事计算机与机器人研究的学者也利用激光扫描开展机器人环境感知与导航研究。这类方法主要基于统计学习监督分类，需要预先学习样本数据确定模型参数，再利用得到的模型对未知数据进行分类。Anguelov等人[^54]和Triebel等人[^55]为基于机器学习的地面点云数据自动分类与滤波提供了宝贵参考。 总体而言，在激光点云数据分割领域，学者们已开展了大量研究，主流方法包括基于聚类、基于模型拟合、基于区域生长等类型，且这些方法已取得了一定研究成果。但这类分割方法大多仅适用于特定问题或特定数据，分割方法的多数参数依赖人工经验设置，所选参数通常会对分割结果产生显著影响。Meng等人在对LiDAR地面滤波算法进行综述后发现，在实际应用中大多数滤波算法都会通过迭代修改邻域大小来提升滤波精度[^56]。 可用于自动分割的方法较少。本文提出了一种基于DBSCAN的自动参数估计方法。 ### 3. 研究方法 基于k近邻最大距离均值的参数估计方法包含六个步骤：数据归一化、空间索引构建、聚类参数估计、聚类、映射回原始数据、输出结果，如图1所示。该分割方法的输入数据是经过配准、降噪和坐标变换处理后的数据。 --- ![Image](images/b434f4cc0c581803e855adc485fb5598e75562411b38eceb1ce1bfa02e555de4.jpg)
Figure 1. Segmentation workflow.
#### 3.1.1. 数据归一化 #### 3.1. 预处理 点云数据通常包含位置$(X, Y, Z)$和强度$(i)$数据，部分点云还可能包含颜色$(R, G, B)$数据。这些数据具有不同的单位和量纲，为了使不同单位的维度适合进行比较，需要在聚类前进行数据归一化处理。如果分割仅考虑位置数据，则无需进行数据归一化。 --- 对于包含n个点、每个点具有m个维度的点云，可表示为公式(1)： $$ \left[\begin{array}{c c c}X_{11}&\cdots&X_{1m}\\ \vdots&\ddots&\vdots\\ X_{n1}&\cdots&X_{n m}\end{array}\right] $$ 式中n为点云内的点数量，m为维度数量。原始值$Z_{ij}$对应的归一化值$X_{ij}$如公式(2)所示。 $$ Z_{ij}=\frac{x_{ij}-x_{j}}{\delta_{j}}\quad i=1,2,\cdots,n;j=1,2,\cdots,m $$ 式中$\delta_j = \sqrt{\frac{1}{n-1} \sum_{i=1}^n (x_{ij} - x_j)^2}$为样本的标准差，$x_j = \frac{1}{n} \sum_{i=1}^n x_{ij}$为样本的均值。 归一化后的数据用于参数估计和聚类分割，在生成最终结果时会考虑其与原始数据的对应关系。 ##### 3.1.2. 聚类中的距离定义 本研究选择欧氏距离作为点之间的距离度量。基于欧氏距离，可根据不同变量的重要性为其赋予给定权重w，如式(3)所示。针对激光雷达点云数据，可分别为空间位置、颜色信息和强度设置不同的权重。本研究未采用不同的权重设置，所有变量的权重均设为1。 $$ d\left(p_{i},q_{j}\right)=\sqrt{w_{1}\left(x_{i1}-x_{j1}\right)^{2}+w_{2}\left(x_{i2}-x_{j2}\right)^{2}+\cdots+w_{m}\left(x_{i m}-x_{j m}\right)^{2}} $$ 式中$p_{i} = (x_{i1}, x_{i2}, \cdots, x_{im})$和$q_{j} = (x_{j1}, x_{j2}, \cdots, x_{jm})$是点云P中的两个m维点，$w_{m} = (w_{1}, w_{2}, \cdots, w_{m})$为各维度的给定权重。 为了提高计算效率，在实际的距离计算与比较过程中，我们计算点与点之间的平方距离。 ##### 3.1.3. Kd-Tree 空间索引 空间搜索在聚类过程中被频繁使用。为了提升海量点的搜索速度，必须建立高效的索引机制。本文采用Kd-tree [^49]构建空间索引，它是一种对多维数据进行索引的有效方法。点云数据通常包含多个维度（例如x、y、z、r、g、b、强度）。Kd-tree中k的取值取决于聚类所用的字段数量：例如，仅包含x、y、z三个字段的数据集，k值取3；包含x、y、z、r、g、b六个字段的数据集，k值取6。 Kd-tree索引在聚类中主要用于两种操作：一种是范围搜索，另一种是K近邻搜索。范围搜索用于搜索给定点一定距离范围内的所有点，K近邻搜索则用于搜索距离给定点最近的k个点。 #### 3.2. 参数估计 在基于密度的聚类方法中，对象之间的相似程度决定了这些对象是否属于同一类别，因此，判定标准的选择对聚类结果至关重要。 DBSCAN方法对输入的聚类阈值$\varepsilon$非常敏感，微小的差异就可能导致完全不同的聚类结果。 --- 目前，传统的聚类半径设置方式通常依赖人工经验。部分研究者提出的参数估计方法一般基于某一类数据，对于其他类型的数据，经验值可能并不适用。开源软件PCL（Point Cloud Library）针对不同数据分割需要设置不同参数，其推荐做法是：不断尝试点云分辨率的5倍、10倍、15倍、20倍等取值，直到得到最优聚类结果[^57]。同时，不同数据的最优参数通常各不相同，得到的参数难以复用，因此有必要针对不同类型的点云数据建立对应的聚类参数估计方法。 针对上述问题，本文提出了基于K近邻最大距离平均值的参数估计方法。 ##### 3.2.1. 定义 在介绍该方法之前，需要先定义两个概念。 点p的KNN最大距离（ $d_{maxi}$）：对于包含m个点的点云数据P $p_i(i=1,2,3,\ldots,m)$，Q是$p_i$的k个最近邻点的集合 $q_j(j=1,2,3,\ldots,k)$。$d(p_i, q_j)$是$p_i$与$q_j$之间的距离，则$p_i$的KNN最大距离 $d_{maxi}$定义如下： $$ d_{m a x i}=_{1m a x}\_{d}_{i j} $$ 在图2中，对于点$p_i$，当$k = 8$时，通过KNN搜索选出距离$p_i$最近的8个点（包含$p_i$自身），其中最远点与$p_i$之间的距离就是$p_i$的KNN最大距离$d_{max}$。 ![Image](images/d8fda5aba9e2f620dd60514ae2e4d65ed06946248edc340e387b30862b351dd5.jpg)
Figure 2. The point $p_i$'s KNN max distance $d_{maxi}$ ( $k = 8$).
点云P的KNN平均最大距离 $(D_{k})$：对于包含m个点的点云P，在给定k的条件下，点云P的KNN平均最大距离可定义如下： $$ D_{k}=\sum_{i=1}^{m}d_{max i}/m=\sum_{i=1}^{m}MAX\left(d_{ij}\right)/m $$ ##### 3.2.2 分析 在均匀分布点云的理想场景中，$d_{max}$与k之间的关系可类比圆面积计算公式： $$ A=\pi R^{2} $$ 式中A为半径R的圆的面积。对于均匀分布点云和$d_{maxi}$的定义，k对应A，$d_{maxi}$对应R，k与$d_{maxi}$的关系可表示为： $$ k=\pi d_{max i}^{2}+f(k) $$ 式中$f(k)$为理论值到实际值的修正项。 --- 因此： $$ d_{max i}=\left(\frac{k-f(k)}{\pi}\right)^{\frac{1}{2}} $$ $$ D_{k}=\sum_{i=1}^{m}\left(\frac{k-f(k)}{\pi}\right)^{\frac{1}{2}}/m\;i=1,2,3,\cdots\cdots,m $$ 因此，基于上述分析，$D_{k}$与k之间的关系可以用多项式拟合函数来描述。 当k从$2 \to +\infty$开始增大时，$D_k$与k的拟合曲线呈现出如下规律，如图3a所示： ![Image](images/59fc870edd58fcfcf8ecadb7f5cc9268526d2c0796e3a11219e07b8ab37a517f.jpg)
(a)
![Image](images/7edf8797c17006368deeba4a935f811c74ebf4bd633f0c251cb8f621a2a8865c.jpg)
(b)
Figure 3. Analysis of the three stages of point $P_{i}$'s neighbor points. (a) Three stages and the turning point; (b) Tangent slopes for three stages and the turning point.
阶段1（S1）：点$p_{i}$的邻域点主要来自同一个物体。 $D_{k}$随k增大以速率$R_{1}$逐渐增长。 阶段2（S2）：点$p_i$的邻域点主要来自多个相邻物体。 $D_{k}$以速率$R_{2}$增长，该速率低于$R_{1}$。 阶段3（S3）：点$p_{i}$的邻域点覆盖整个数据集中的所有点。 当$D_{k}$时，$k \to +\infty$的极限为常数，此时增长速率为$R_{3}$。 $$ \lim_{k\to+\infty}D_{k}=D_{max} $$ 式中$D_{max}$为数据集中相距最远的两个点之间的距离。 由于DBSCAN方法是将邻域内的点划分到不同簇中，因此可将阶段1到阶段2转变时对应的$D_k$值设为最优半径。曲线的切线斜率可用于寻找从阶段1到阶段2的转折点（图3a中的T点）。可以对拟合曲线添加修正，使$D_k$和k具有相同的取值范围。添加修正后，各阶段的切线斜率分别为$R_1 > 1$、$R_2 < 1$、$R_3 < 1$，如图3b所示。因此，当切线斜率满足$R = 1$时，即可找到阶段1到阶段2的转折点。 在拟合曲线中，不同的一阶导数值对应不同的距离值。当一阶导数等于1时，对应的$D_{k}$就是半径$\varepsilon$的最优值。 ##### 3.2.3 方法 该方法的详细流程如图4所示： --- ![Image](images/c2e2868d9ad7387878c703253325c88410f4f5b2d85591d9458e46248ebed242.jpg)
Figure 4. Parameter estimation process.
## (1) 计算点云P的KNN平均最大距离 $(D_{k})$ 当 $k=1$ 时，点P最近的点就是其自身，距离为0，因此k的取值为 $k\in[2,K]$。根据式(5)计算 $d_k$，得到 $d_k$ 的离散函数，即 $(2,d_{m2})$、$(3,d_{m3})$、$(4,d_{m4})$、$\ldots$、$(K,d_{mK})$ 序列。 $$ d_{k}=g(k) $$ ## (2) 对离散函数 $d_{k}$ 进行多项式拟合 对式(12)进行多项式拟合，得到连续函数 $D_{k}$： $$ D_{k}=f(k)\;k\in[2,K] $$ 如果 $R^{2} < 0.99$ 成立，则令 $K = K + 1$，重复步骤1。 ## (3) 添加修正项 设K为k的最大值，$D_{kmax}$ 为 $D_k$ 的最大值，则添加修正量 $\frac{K}{D_{kmax}}$ $$ D_{m k}=\frac{K}{D_{k m a x}}\cdot f(k)k\in[2,K] $$ --- (4) 对 $D_{mk}$ 求一阶导数： $$ D_{m k^{\prime}}=\frac{K}{D_{k m a x}}\cdot f^{\prime}(K) $$ 令 $D_{mk'} = 1$，求解得到 $k = k_0$。如果 $k_0 > K$ 成立，则令 $K = K + 1$，重复步骤1至4。 ## (5) 计算估计半径 $\varepsilon$ 将 $k = k_0$ 代入式(13)，得到 $D_k = f(a)$，此时 $\varepsilon = D_k$ 即为估计半径。 本文分析了点云中点与点之间的距离，推导得到了k与 $f(k)$ 之间的关系。当函数切线斜率设为1时，对应的k值 $f(k)$ 被认为是最优聚类半径。该方法的有效性和准确性将在第4节通过实验验证。 ### 3.3 聚类分割 DBSCAN是一种基于密度的聚类算法，与k-means不同，它不需要预先指定数据中的聚类数量。DBSCAN可以发现任意形状的簇，这一特性使其非常适合处理激光雷达点云数据。本研究采用DBSCAN算法进行点云分割。 #### 3.3.1 参数 尤其是对于高维数据，所谓的“维数灾难”使得很难为阈值 $\varepsilon$ 找到合适的取值。然而，这种影响也存在于其他基于欧氏距离的算法中 [^14]。本研究中改进后的DBSCAN算法可以很好地处理高维数据，包括归一化后的高维数据，并且采用了Kd树索引。 DBSCAN仅需要两个参数：$\min Pts$ 和 $\varepsilon$。本研究额外添加了一个参数 $\max Pts$ 来控制簇的大小。$\min Pts$ 和 $\max Pts$ 根据最小和最大目标可能包含的点数进行选择。$\min Pts$ 的取值会影响小目标被判定为簇还是噪声；$\max Pts$ 会影响目标在被合并为一个簇而不是被拆分前的最大允许尺寸。本研究中这两个参数需要手动设置，参数 $\varepsilon$ 可通过上述方法计算得到。 ##### 3.3.2 聚类 在HDBSCAN（分层DBSCAN）[^58]中，边界点的概念被舍弃，任意时刻仅核心点被视为簇的一部分，这与密度水平集的概念更加一致。Rusu也提出了一种基于DBSCAN的改进聚类方法，该方法仅使用核心点[^57]。本研究对DBSCAN算法的改进如下（算法1）： --- ```pseudo // Algorithm 1: Improved DBSCAN Algorithm Input: Dataset: P, $\min Pts$, $\varepsilon$, $\max Pts$ Output: Clusters C ``` 1 创建空簇列表C，以及用于存储待检查点的空队列Q 2 遍历所有$p_i \in P$，执行 3 若$p_i$已被处理，则 4 继续 5 结束 6 将$p_i$添加到当前队列Q 7 遍历所有$p_j \in Q$，执行 8 在半径为$p_j^k$的球域中搜索$p_j$的邻点集合$r < \varepsilon$； 9 遍历所有$p_t \in p_j^k$ 10 若$p_t$未被处理，则 11 将$p_t$添加到Q 12 结束 13 结束 14 结束 15 n = Q中的点数量 16 若$n > \min Pts$且$n < \max Pts$，则 17 将Q添加到簇列表C 18 遍历所有$p_j \in Q$，执行 19 将$p_j$标记为已处理 20 结束 21 将Q重置为空列表 22 结束 23 结束 24 返回C #### 3.4. 输出分割结果 由于所有处理过程都是在归一化后的数据上开展的，因此输出结果时需要将归一化数据的结果映射回原始数据。归一化数据与原始数据的点数量和点顺序均保持不变，因此可以对应得到原始数据的分割结果，并将其导出为指定格式的数据文件。 ### 4. 实验结果与分析 为了测试本文方法的鲁棒性和准确性，分别使用仅空间信息、空间信息结合颜色信息两种输入，对机载和移动LiDAR数据开展了实验。 #### 4.1.1. 研究区域与数据来源 #### 4.1. 机载LiDAR数据实验 本次实验使用的机载LiDAR数据研究区域位于美国马里兰州巴尔的摩市，数据下载自NOAA海岸服务中心()。该数据由搭载在Sanborn Aero Commander 500B飞机上的徕卡ALS 50型机载激光扫描仪采集获得，飞行高度为1400 m，扫描频率为36 KHz，脉冲频率为63 KHz，点密度为1.0 点/m。原始点云数据不包含颜色信息，因此本研究通过与遥感影像进行数据融合，为点云添加了颜色信息。 研究区域包含运动场、道路、高层建筑、低层建筑、树木等地物，点云数据包含空间位置、回波强度和颜色信息。 --- 原始点云数据如图5所示，对应的遥感影像数据和参考数据如图6所示。参考数据由作者基于遥感影像采集得到。 ![Image](images/987915889b024b24f7e6053b0977b0fc3dc41653891f0b7abef03a3b2f292485.jpg)
(a)
![Image](images/e3d2484da683e9668766afd932ef89d40da874ec9d5b9e8574d6d27757c871d3.jpg) ![Image](images/bb4d39dfb1a0a625172ba78b3c12373576dab2ae4fdb45327cb0f86dcdb313b3.jpg)
(b)
(c)
![Image](images/7b3009a516c008009a5900d74783e1c9b2af59430b8201bbe5f876a2575360e6.jpg)
(d)
Figure 5. Original data. (a) Colored by RGB; (b) colored by height; (c) colored by intensity; (d) grayed by intensity.
![Image](images/f3d5a3df8d743f69ac51248be8efdd4ea99a8403e9155d7efa8f1528c33834b0.jpg)
Figure 6. Remote sensing image and reference data.
尽管DBSCAN算法可以处理噪声数据，但为了获得更准确的统计结果，我们仍然对数据进行了滤波处理。去噪后，点云的总点数为3,388,214。 为提高分割精度，需要将反射强度信息与空间位置信息、颜色信息等相结合。本研究经过数据分析发现，树木和建筑物的反射强度相较于空间和颜色 --- 信息更为接近。因此，如果将反射强度信息加入聚类分割，会缩小树木和建筑物这类不同类别之间的距离，进而影响分割精度。为此，本研究选择空间位置信息和颜色信息参与点云数据分割。 为了评价分割精度，本研究从遥感影像中采集了参考数据。参考数据包含高层建筑、低层建筑、体育场和树木，如图6所示。共采集得到333个参考对象。 ##### 4.1.2. 使用空间信息 ## 参数估计 首先对测试数据进行归一化处理，并构建Kd-tree空间索引。当 $K = 60$, $R^2 > 0.99$ and $k_0 < K$, 计算得到 $D_k$ 条件下数据的KNN平均最大距离（ $k = (2,3,4, \ldots, 60)$）。结果和拟合多项式如图7所示。详细过程如下。 ![Image](images/a0bf673b968e94f0c3bd633758f38582eedd6bc0c54556466449c250b1374925.jpg)
Figure 7. Chart and fitting curve of the mean max distance of k nearest neighbor of airborne laser scanning data using X, Y, Z fields.
加入修正项后，当K = 60, $D_{k} = 1.64151$，多项式拟合曲线如下所示： $$ D_{mk}=\frac{60}{1.64151}\times f(k) $$ 令一阶导数： $$ D\_{m}k^{\prime}=60/1.64151\times f^{\prime}\left(k\right)=1 $$ 求解 $k_{0}=14.389$, 即可得到估计参数 $r_{0}=f(k_{0})=0.8114$。 （阈值的估计值 $\varepsilon$ 和对应的k值已用红线标出。拟合曲线和方差位于图的底部。） ## 聚类与结果 为聚类分割 $\varepsilon \in (0.6, 0.7, 0.8, 0.8114, 0.9, 1.0, 1.1)$ 选取了不同的半径，所有实验设置minPts = 100, maxPts = 3,000,000。输入参数和结果（运行时间、聚类数量、噪声比例）如表1所示。 最终得到的聚类是点数多于minPts的簇。噪声比例是噪声点数占数据集总点数的比例。 --- 从表1可以看出，聚类时间随聚类半径的增大逐渐增加，聚类结果的总数量不断减少，噪声比例也呈下降趋势。大多数聚类结果包含200–4000个点。当估计参数为 $\varepsilon = 0.8114$ 时，聚类结果分布在200–50,000范围内，噪声比例为3.9%。 实验结果如图8所示。 ![Image](images/a2a0e19286ae62cd7200ed2491809e0ead37612f1d2c51abc22640c3289feec7.jpg)
T1
![Image](images/c2ba331f73b5d725324eb91cf6e0e29fb2555168c0e197d107790c8ca5c9cb3d.jpg)
T2
![Image](images/6fa06eff6633fcb35f6c7cfa691798ece7bbfef04f783d024d7196f8b05ddc86.jpg)
T3
![Image](images/d4f7aee155a25f42ab2681c4ed58d91beca83d644e91c91ae735a1324704b0ce.jpg)
T4
![Image](images/382b8bc8e69518177123f33213ceaf0872a929e1815c19f0d997cfe3295d58b0.jpg)
T5
![Image](images/5434e72c588dfb00cf43173246e1186aa7b7e3dbfd086ea6ca115e2d47b93428.jpg)
T6
![Image](images/2eab1a2f54d9323340a48f6d20439bdb447fbf92af7793b4a5857175ac64d3cc.jpg)
T7
Figure 8. Airborne laser scanning data segmentation result maps using X, Y, Z fields.
---
Table 1. The segmentation results using different $\varepsilon$ for airborne laser scanning data using X, Y, Z fields.
ClassNameT1T2T3T4T5T6T7
Inputs$\varepsilon$0.60.70.80.81140.91.01.1
ResultsRun Time (s)20.022.222.222.022.826.532.8
No. of Clusters901828729728660577486
Noise Ratio (%)8.85.84.13.93.02.31.7
可以看出，随着聚类半径的增大，分割结果从碎片化状态逐渐转变为合并状态。若半径小于估计值，如测试T1、T2、T3的情况，分割结果会呈碎片化，原因是许多目标被过分割。例如棒球场西侧的建筑被分割成了多个区块。当半径大于估计值时，多个不同目标会被合并分割为一类。例如在测试T6（ $\varepsilon = 1.0$）和T7（ $\varepsilon = 1.1$）中，道路左下角的低矮建筑和植被被分割为同一个聚类。在测试T4（ $\varepsilon = 0.8114$）中，高层建筑、低矮建筑和部分植被都得到了清晰的分割。和其他分割结果相比，尽管仍有部分目标存在过分割或欠分割，但这已经是令人满意的结果。 ## 精度评估 Hoover等人根据分割效果将点云分割结果分为五类：正确检测、过分割、欠分割、漏检和噪声 $^{[59]}$。本研究采用该准则进行精度评价。 过分割指一个目标被分割为多个部分，欠分割则指分割不充分——邻近的多个目标被分割为同一类。漏检指目标在分割结果中被遗漏。点云数据分割的目标就是尽可能减少后四种错误分割的发生。 图9展示了一个参考建筑以及不同测试中除噪声外的四种分割结果。在测试中，如果一个聚类内的点数量小于minPts，该聚类内的所有点都会被判定为噪声。 ![Image](images/59b698b0e418912a10aeee6d99b36fdf8063b1ddc8ffa479086b0a8306cb85f0.jpg)
(a)
![Image](images/080533978cd88932992e1d8956897151e1eff7c31e2c38c27d74e7639b6f8440.jpg)
(b)
![Image](images/294a6c30a940cf00f352a99b3aabd1916c6c4807b5661389bbc7f8b4758da8d4.jpg)
(c)
![Image](images/604f4fa724798dccb2f6a8221dc4407b178f60d136a652502fde933494e3960a.jpg)
(d)
![Image](images/a7a37f3bb7f4805254291c0bc841c29db9c8ac57a5795757d01aeea4ee918e30.jpg)
(e)
Figure 9. Evaluation criteria. (a) Reference building image; (b) correct detection; (c) over-segmentation; (d) under-segmentation; (e) missed.
本研究聚焦于不同类别的分割。因此，在分割结果的精度评价中，同一类别的目标被分割到同一个簇中被视为正确检测，不属于欠分割。欠分割指的是一个簇中包含不同类别的目标。例如，仅包含多棵树的簇属于正确检测，而同时包含树木和建筑物的簇则属于欠分割。 各测试结果均根据参考数据进行评估，精度如表2所示。测试T4采用了高于估计值的75%估计参数，其精度 --- 高于估计值。在测试T1中，大量目标被判定为噪声或被过分割，导致精度偏低。在测试T7中，目标漏检是精度偏低的主要原因。
Table 2. Accuracy evaluation using different $\varepsilon$ for airborne laser scanning data using X, Y, Z fields.
Test$\varepsilon$Correct DetectionUnder-SegmentationOver-SegmentationMissedAccuracy
T10.614940816345%
T20.717636655653%
T30.823317364770%
T40.811425121154675%
T50.920133366360%
T61.021029266863%
T71.11825179355%
### 4.1.3. 结合空间与颜色信息 ## 参数估计 包含空间与颜色信息的六维LiDAR数据经过归一化处理后，构建了Kd-tree空间索引。当 $K = 60$，$R^2 > 0.99$ 和 $k_0 < K$。当 $D_k$ 时，计算得到数据的KNN平均最大距离（ $k = (2,3,4,\cdots,60)$）。结果和拟合多项式如图10所示，详细过程如下： ![Image](images/dd1d1f27c153ec707b974fdc5c9df4ca83b450c36c2bf38c7536bb77fdafc82f.jpg)
Figure 10. Chart and fitting curve of the mean max distance of k nearest neighbor of airborne laser scanning data using X, Y, Z, R, G, B fields.
加入修正后，若K = 60，$D_{k} = 0.148$，多项式拟合曲线如下所示： $$ D_{mk}=\frac{60}{0.148}\times f(k) $$ 令一阶导数： $$ D\_{m}k^{\prime}=60/0.148\times f^{\prime}\left(k\right)=1 $$ 求解 $k_{0}=10.860$，即可得到估计参数 $r_{0}=f(k_{0})=0.097$。 (阈值$\varepsilon$的估计值和对应的k值已用红线标出，拟合曲线和方差位于图的底部)。 ## 聚类与结果 针对聚类分割$\varepsilon\in(0.07,0.08,0.09,0.097,0.10,0.11,0.12)$选择不同半径进行实验，所有实验的minPts均为100，maxPts均为3,000,000。输入参数和实验结果（运行时间、聚类数量和噪声比）如表3所示。 --- 从表3可以看出，聚类时间随聚类半径的增大逐渐增加，聚类结果的总数量不断减少，噪声比也呈下降趋势。 大多数聚类结果包含200–2000个点。若采用估计参数$\varepsilon = 0.097$，聚类结果的点数量分布在200–50000区间内，噪声比为14.4%，结果如图11所示。 ![Image](images/7c2e9843989ea214a6b2bc11bb11937308f2efacf1b1f5f78f09adbc21f834de.jpg)
T1
![Image](images/e84b22fb1b1429d0099d5bed852992ab2d658c325ad9c6ec2ffcd2261f5a9ead.jpg) ![Image](images/6888c2b8deb09aa925d00e7f07716d593eae6d4e805b802ca9abbc0289df2bfd.jpg)
T2
T3
![Image](images/168e44f3013497fde29ebac1bc1440ef543c8fec7e2f7a6ea56d7e3af605674b.jpg) ![Image](images/bc34a01197b699ac9728846465e68a7460ab9a827b8354b4ccc87e41830a1da3.jpg)
T4
T5
![Image](images/742a110b89b8fbeba49854de9c1249f5d641f143151edfaa4aaa46dc5448b154.jpg)
T6
![Image](images/47687e2bd033d2c5486f6a9fb650d01a24223aca1565e90fb98fb05b1a15a935.jpg)
T7
Figure 11. Airborne laser scanning data segmentation result maps using X, Y, Z, R, G, B fields.
---
Table 3. The segmentation results using different thresholds for airborne laser scanning data using X, Y, Z, R, G, B fields.
ClassNameT1T2T3T4T5T6T7
Inputs$\varepsilon$0.070.080.090.0970.10.110.12
ResultsRun Time (s)52.165.282.091.6105.4133.3166.3
No. of Clusters635632570504498412340
Noise Ratio (%)31.023.618.014.413.29.36.1
当参数为$\varepsilon < 0.097$时，例如测试T1（$\varepsilon = 0.07$），主要高层建筑已被分离出来；运动场草地完成划分，道路被分为六类，体育场顶部被分为三类，部分低层建筑和植被草地被划分为同一类。因此，若取值为$\varepsilon < 0.097$，部分物体会出现过分割，另一部分则会出现欠分割。 在测试T4（$\varepsilon = 0.097$）中，高层建筑屋顶与部分混有树木的低层建筑已经分离，道路和道路中间的绿化带也分离开来，草地、跑道以及不同区域的座位也完成了分离。可以看出，当参数为$\varepsilon = 0.09$、$\varepsilon = 0.097$或$\varepsilon = 0.10$时，过分割和欠分割的情况较少，分割结果优于T1、T2和T3。 当参数为$\varepsilon > 0.097$时，例如测试T7（$\varepsilon = 0.12$），主路和小径没有被分离，低层建筑、运动场的草地和跑道也没有被分离。总体来看，T5、T6和T7测试中，大多数物体都存在欠分割问题。 ## 精度评估 每个测试结果都根据参考数据进行评估，精度如表4所示。参考数据中共有333个目标。采用$\varepsilon$估计值的测试T4准确率最高，达到74%。
Table 4. Accuracy evaluation using different $\varepsilon$ values for airborne laser scanning data using X, Y, Z, R, G, B fields.
Test$\varepsilon$Correct DetectionUnder-SegmentationOver-SegmentationMissedAccuracy
T10.0715753735047%
T20.0817858583953%
T30.0923627482271%
T40.09724724431974%
T50.1023625403271%
T60.1119265255158%
T70.121739086252%
### 4.2. 移动激光雷达数据实验 #### 4.2.1. 研究区与数据源 研究区为一条长500米的街道，包含树木、路灯、建筑物等各类地物，如图12所示。数据由Optech Lynx V100移动测量系统采集，采样频率为75 Hz，激光测量速率为100 kHz，车辆沿该道路行驶速度为40 km/h，在10米距离处点间距为2至3厘米。 --- ![Image](images/67e3cc4912d8a2e15f73a2dd478f06c33acaa029f78d50f0a1183093033974eb.jpg)
Figure 12. Original mobile point cloud data.
这些数据同时包含空间信息和强度信息。点云总量为700万个，其中路面的点密度普遍高于树木、建筑、路灯等地物的点密度。高密度点对于路面质量检测十分重要，但对于地物分割任务而言，为了降低聚类中不同密度带来的影响，必须先移除地面点，仅保留包含树木、路灯和建筑的剩余数据用于分割。该方法基于最低点建立水平面，再在该平面上方设置缓冲区，将缓冲区内的点归类为地面点。我们开发了一款C#工具来读取PCD（Point Cloud Data）文件并移除地面点。移除地面点后，剩余点数量为854994个，如图13所示。 ![Image](images/5b0931e2bcb15a8bb3307076e82d53164bb95f856a837309b4a68f69a535a836.jpg)
Figure 13. Point cloud without ground points.
对于部分地物类别，具体来说是树木和路灯，它们的反射强度信息和颜色信息取值几乎一致。如果将这些信息纳入聚类分割，会缩小不同对象之间的距离，进而影响分割效果。因此，针对本次移动LiDAR数据，我们选择仅使用空间位置信息参与点云数据分割。 作者使用ESRI ArcScene 10.3，基于LiDAR数据采集得到了用于精度评估的参考数据。参考数据包含树木、路灯和建筑三类，数量分别为807、94和18。部分参考数据如图14所示。 --- ![Image](images/9c7b872724b68fc76864a3755334c8f1bc0b6fc6c9f6a5f92ff45abc9f4768c9.jpg)
Figure 14. Part of the reference data.
##### 4.2.2. 使用空间信息 ## 参数估计 我们对包含空间信息的数据进行了归一化处理，并构建了三维Kd-tree空间索引。当 $K = 40$，得到 $R^2 > 0.99$ 和 $k_0 < K$。在 $D_k$ 条件下计算得到数据的KNN平均最大距离（ $k = (2,3,4,\cdots,40)$）。结果和拟合多项式如图15所示，详细过程如下： ![Image](images/7be55c020d52c8773b8bdac5107fa1177082a771a82a0e5b629a049fcaabc302.jpg)
Figure 15. Chart and fitting curve of the mean max distance of the k nearest neighbor of mobile laser scanning data using X, Y, Z fields.
加入修正项后，当K = 40，得到$D_{k} = 2.04$，多项式拟合曲线如下所示： $$ D_{mk}=\frac{40}{2.04}\times f(k) $$ 令一阶导数： $$ D\_{m}k^{\prime}=40/2.04\times f^{\prime}\left(k\right)=1 $$ 求解 $k_{0}=12.063$，即可得到估计参数 $r_{0}=f(k_{0})=1.14686$。 （阈值的估计值 $\varepsilon$ 和对应的k值已用红线标出，拟合曲线和方差位于图的底部）。 --- ## 聚类与结果 我们为聚类分割 $\varepsilon \in (0.5, 0.8, 1.1, 1.14686, 1.2, 1.5, 1.7)$ 选取了不同的半径参数。所有实验的minPtss均设置为200，maxPtss设置为854994。输入参数和结果（运行时间、聚类数量、噪点比）如表5所示。 从表中可以看出，聚类时间随聚类半径的增大逐渐增加，聚类结果的总数量逐渐减少，噪点比相应呈下降趋势。大部分聚类结果包含100–3000个点。在实验T4（ $\varepsilon = 1.14686$）中，聚类结果的点数量分布在100–60000区间内，噪点比为14.4%。 实验结果如图16所示。 ![Image](images/c50b9af6bcc2b285f086e5949f78eac45e1a6a2fb546ef1db53a369f7b907e6d.jpg)
T1
![Image](images/455d06726444739dee3841152796b88eac554ce889626a16e2268b5bd6193219.jpg) ![Image](images/586f4c2c1bfab6d7fd4ae67cf5b9713131af1a49b69b2ee46db0e923c99a4df1.jpg)
T2
T3
![Image](images/286f21f5827a271121581d3c05f7b9c1b53d29e2fda9c32aba219b0b55489f0d.jpg) ![Image](images/306d5ddf1248d8ce762ba99e9268a8d86754a17c5c7b493dfdf018301a575397.jpg)
T4
T5
![Image](images/abe8820d1f58a11fe9103f82e59b8eca8ff7c0c0daee1c96d42ee1c453f57841.jpg) ![Image](images/3ce59e174d95aee30ad3b49a856f76a3c59d80d65a19e1938c9a1eba7cf48216.jpg)
T6
T7
Figure 16. Part segmentation results of the mobile laser scanning data using X, Y, Z fields.
---
Table 5. The segmentation results using different thresholds for mobile laser scanning data from X, Y, Z fields.
ClassNameT1T2T3T4T5T6T7
Inputs$\varepsilon$0.50.81.11.146861.21.51.7
ResultsRun Time (s)3.56.39.412.813.714.818.5
Number of clusters186663619611592459385
Noise Ratio (%)84.127.915.914.412.78.56.5
从结果图中可以看出，在测试T4（ $\varepsilon = 1.14686$）中，大多数建筑物、单株树木、路灯等已被分割出来，但成行树木中的部分单株树木未被分离。原因是这些树木间距过近，无法完成分割。随着聚类半径增大，欠分割问题会导致更多路灯和树木被分割到同一个聚类中。例如测试T7（ $\varepsilon = 1.7$）中，仅有少数单株树木被成功分割，大多数单株树木被合并为一整行树木，同时更多路灯被与树木分割在一起，如图16中T6和T7所示。当半径小于估计值时，例如测试T2（ $\varepsilon = 0.8$），结果中仅存在少量单株树木或成行树木，只有极少甚至没有路灯被分割出来，这种情况可视为过分割。 ## 精度评估 测试结果依据精度评估章节的评估标准，对照参考数据开展评估。如果多棵树木被分割到同一个聚类中，则该聚类被判定为检测正确。 所有测试结果均已对照参考数据完成评估，精度如表6所示。使用$\varepsilon$估计值的测试T4准确率为71%，高于使用大于或小于该估计值参数的测试准确率。
Table 6. Accuracy evaluation using different $\varepsilon$ values of mobile laser scanning data using X, Y, Z fields.
Test$\varepsilon$Correct DetectionUnder-SegmentationOver-SegmentationMissedAccuracy
T10.5481448465%
T20.839493342243%
T31.1598512324066%
T41.14686645441520871%
T51.2579131319963%
T61.5382338418842%
T71.7271455318330%
### 4.3. 结果 具有空间和颜色信息的机载激光雷达（ALS）和移动激光雷达（MLS）数据，使用估计的$\varepsilon$以及大于和小于$\varepsilon$的参数进行分割。根据参考数据评估每次分割测试的准确性。结果如图17所示。 实验结果表明，本文提出的基于空间位置和颜色特征的方法可实现点云自动分割。使用该方法估计得到的$\varepsilon$进行分割，准确率分别为75%、74%和71%，均高于本研究中使用大于或小于该估计值参数得到的准确率。 在ALS数据集中，跑道、草坪、高低层建筑、道路、树木和操场等地物均被正确分割；在MLS数据集中，单株树木、路灯和建筑物也被清晰分割。该参数估计方法可用于实现更高精度的自动分割。 --- ![Image](images/be48446ab524d8884ba4b3ea94b946c9a9ebfe795bdc9499081c7426942659f1.jpg)
Figure 17. Accuracy graph for estimated $\varepsilon$ (T4), radii gradually lower than $\varepsilon$ (T3, T2, T1) and gradually greater than $\varepsilon$ (T5, T6, T7).
### 5. 结论 本文提出了一种基于DBSCAN密度聚类技术的分割算法，并针对聚类过程的关键参数$\varepsilon$设计了一种全新的自动参数估计方法。该方法可根据数据特征自动计算得到最优聚类参数$\varepsilon$，用户无需对数据有深入了解即可使用。该方法利用点云数据的固有属性，分析点云内点与点之间的距离，推导得到了k与平均最大距离$f(k)$的关系。当函数的切线斜率等于1时，对应k的$f(k)$值即为最优聚类半径。 本文在不同类型的点云数据（包括带颜色信息和不带颜色信息的机载、移动点云数据）上对该方法进行了评估。实验结果表明，使用本文方法估计得到的参数$\varepsilon$进行分割，准确率分别为75%、74%和71%，均高于使用大于或小于该估计值参数得到的准确率。 实验结果表明，该参数估计方法具有鲁棒性，同样可应用于高维数据。该方法可用于机载和移动点云数据处理系统，能够减少人工工作量，提升数据处理的自动化程度。该方法改变了当前聚类参数设置主要依赖经验值、且需要预先充分了解数据的现状。 未来研究可聚焦于迭代分割起止条件涉及的另外两个参数minPts和max pts的估计。可基于本文提出的分割方法，进一步研究离散点的表达对比以及目标自动识别。 作者贡献：M.J.、C.W.和J.W.提出研究构想并设计实验；C.W.完成实验；J.W.和W.W.分析数据；T.L.和Y.S.提供试剂/材料/分析工具；C.W.撰写论文。 资助：本研究得到中国国家自然科学基金（项目编号：41471330）、山东省重点研发计划（项目编号：2016GSF117017）、中国山东省自然科学基金项目（项目编号：ZR2014DM014）、国家测绘地理信息局（NASG）地理信息重点实验室的资助。本文APC由中国国家自然科学基金资助。作者对上述支持表示衷心感谢。 利益冲突：作者声明不存在利益冲突。 --- ## 参考文献 [^1]: Akel, N.A.; Kremeike, K.; Filin, S.; Sester, M.; Doytsher, Y. Dense DTM generalization aided by roads extracted from LiDAR data. In Proceedings of the ISPRS WG III/3, III/4, V/3 Workshop "Laser scanning 2005", Enschede, The Netherlands, 12–14 September 2005; pp. 54–59. [^2]: Popescu, S.C.; Wynne, R.H. Seeing the trees in the forest: Using lidar and multispectral data fusion with local filtering and variable window size for estimating tree height. Photogramm. Eng. Remote Sens. 2004, 70, 589–604. [CrossRef] [^3]: Bortolot, Z.J.; Wynne, R.H. Estimating forest biomass using small footprint LiDAR data: An individual tree-based approach that incorporates training data. ISPRS J. Photogramm. Remote Sens. 2005, 59, 342–360. [CrossRef] [^4]: Hollaus, M.; Wagner, W.; Eberhöfer, C.; Karel, W. Accuracy of large-scale canopy heights derived from LiDAR data under operational constraints in a complex alpine environment. ISPRS J. Photogramm. Remote Sens. 2006, 60, 323–338. [CrossRef] [^5]: Garcia-Alonso, M.; Ferraz, A.; Saatchi, S.S.; Casas, A.; Koltunov, A.; Ustin, S.; Ramirez, C.; Balzter, H. Estimating forest biomass from LiDAR data: A comparison of the raster-based and point-cloud data approach. In Proceedings of the AGU Fall Meeting, San Francisco, CA, USA, 14–18 December 2015. [^6]: Murakami, H.; Nakagawa, K.; Hasegawa, H.; Shibata, T.; Iwanami, E. Change detection of buildings using an airborne laser scanner. ISPRS J. Photogramm. Remote Sens. 1999, 54, 148–152. [CrossRef] [^7]: Gomes Pereira, L.; Janssen, L. Suitability of laser data for DTM generation: A case study in the context of road planning and design. ISPRS J. Photogramm. Remote Sens. 1999, 54, 244–253. [CrossRef] [^8]: Clode, S.; Rottensteiner, F.; Kootsookos, P.; Zelniker, E. Detection and vectorisation of roads from lidar data. Photogramm. Eng. Remote Sens. 2006, 73, 517–535. [CrossRef] [^9]: Quattoni, A.; Torralba, A. Recognizing indoor scenes. In Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition, Miami, FL, USA, 20–25 June 2009. [^10]: Inokuchi, H. Multi-Lidar System. U.S. Patent Application No. 20120092645A1, 19 April 2012. [^11]: Ester, M.; Kriegel, H.P.; Sander, J.; Xu, X. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, OR, USA, 2–4 August 1996. [^12]: Ankerst, M.; Breunig, M.M.; Kriegel, H.P.; Sander, J. OPTICS: Ordering points to identify the clustering structure. In Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, Philadelphia, PA, USA, 31 May-3 June 1999; pp. 49–60. [^13]: Hinneburg, A.; Gabriel, H.-H. DENCLUE 2.0: Fast Clustering Based on Kernel Density Estimation. In Intelligent Data Analysis VII, Proceedings of the 7th International Symposium on Intelligent Data Analysis, IDA 2007, Ljubljana, Slovenia, 6–8 September 2007; Berthold, M.R., Shawe-Taylor, J., Lavrač, N., Eds.; Springer: Berlin, Germany, 2007; pp. 70–80. [^14]: Han, J.; Kamber, M. Density-Based Methods. In Data Mining: Concepts and Technique; Morgan Kaufmann Publishers: Burlington, MA, USA, 2006; Chapter 7; pp. 418–422. [^15]: Ghosh, S.; Lohani, B. Heuristical Feature Extraction from LIDAR Data and Their Visualization. ISPRS—Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2012, 38, 13–18. [CrossRef] [^16]: Schubert, E.; Sander, J.; Ester, M.; Kriegel, H.P.; Xu, X. DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN. ACM Trans. Database Syst. 2017, 42, 1–21. [CrossRef] [^17]: Sander, J.; Ester, M.; Kriegel, H.P.; Xu, X. Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications. Data Min. Knowl. Discov. 1998, 2, 169–194. [CrossRef] [^18]: Daszykowski, M.; Walczak, B.; Massart, D.L. Looking for natural patterns in data: Part 1. Density-based approach. Chemom. Intell. Lab. Syst. 2001, 56, 83–92. [CrossRef] 19. Dua, D.; Karra Taniskidou, E. UCI机器学习库。美国加利福尼亚州欧文市，加利福尼亚大学信息与计算机科学学院，2017。在线地址：（访问日期：2019年1月3日）。 [^20]: Gan, J.; Tao, Y. DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Australia, 31 May–4 June 2015; pp. 519–530. ## [^21]: Hubert, L.; Arabie, P. Comparing partitions. J. Classif. 1985, 2, 193–218. [CrossRef] --- [^22]: Ghosh, S.; Lohani, B. Mining lidar data with spatial clustering algorithms. Int. J. Remote Sens. 2013, 34, 5119–5135. [CrossRef] [^23]: Lari, Z.; Habib, A. Alternative methodologies for the estimation of local point density index: Moving towards adaptive LiDAR data processing. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2012, 39, 127–132. [CrossRef] [^24]: Biosca, J.M.; Lerma, J.L. Unsupervised robust planar segmentation of terrestrial laser scanner point clouds based on fuzzy clustering methods. ISPRS J. Photogramm. Remote. Sens. 2008, 63, 84–98. [CrossRef] [^25]: Filin, S. Surface clustering from airborne laser scanning data. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2002, 34, 119–124. [^26]: Jiang, B. Extraction of Spatial Objects from Laser-Scanning data using a clustering technique. In Proceedings of the XXth ISPRS Congress, Istanbul, Turkey, 12–13 July 2004. [^27]: Morsdorf, F.; Meier, E.; Allgöwer, B.; Nüesch, D. Clustering in airborne laser scanning raw data for segmentation of single trees. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2003, 34, W13. [^28]: Roggero, M. Object segmentation with region growing and principal component analysis. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2002, 34, 289–294. [^29]: Crosilla, F.; Visintini, D.; Sepic, F. A statistically proven automatic curvature based classification procedure of laser points. In Proceedings of the XXI ISPRS Congress, Beijing, China, 3–11 July 2008. [^30]: Jain, A.K.; Duin, R.P.W.; Mao, J. Statistical pattern recognition: A review. IEEE Trans. Pattern Anal. Mach. Intell. 2000, 22, 4–37. [CrossRef] [^31]: Ballard, D.H. Generalizing the Hough transform to detect arbitrary shapes. Pattern Recognit. 1981, 13, 111–122. [CrossRef] [^32]: Tarsha-Kurdi, F.; Tania, L.; Pierre, G. Hough-transform and extended ransac algorithms for automatic detection of 3d building roof planes from lidar data. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Syst. 2007, 36, 407–412. [^33]: Fischler, M.; Bolles, R. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 1981, 24, 381–395. [CrossRef] [^34]: Hoffman, R.; Jain, A.K. Segmentation and classification of range images. IEEE Trans. Pattern Anal. Mach. Intell. 1987, 5, 608–620. [CrossRef] [^35]: Yang, B.; Huang, R.; Dong, Z.; Zang, Y.; Li, J. Two-step adaptive extraction method for ground points and breaklines from lidar point clouds. ISPRS J. Photogramm. Remote Sens. 2016, 119, 373–389. [CrossRef] [^36]: Maas, H.G.; Vosselman, G. Two algorithms for extracting building models from raw laser altimetry data. ISPRS J. Photogramm. Remote. Sens. 1999, 54, 153–163. [CrossRef] [^37]: Riveiro, B.; González-Jorge, H.; Martínez-Sánchez, J.; Díaz-Vilariño, L.; Arias, P. Automatic detection of zebra crossings from mobile LiDAR data. Opt. Laser Technol. 2015, 70, 63–70. [CrossRef] [^38]: Neidhart, H.; Sester, M. Extraction of building ground plans from Lidar data. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2008, 37, 405–410. [^39]: Woo, H.; Kang, E.; Wang, S.; Lee, K.H. A new segmentation method for point cloud data. Int. J. Mach. Tools Manuf. 2002, 42, 167–178. [CrossRef] [^40]: Su, Y.-T.; Bethel, J.; Hu, S. Octree-based segmentation for terrestrial LiDAR point cloud data in industrial applications. ISPRS J. Photogramm. Remote Sens. 2016, 113, 59–74. [CrossRef] [^41]: Vo, A.V.; Truong-Hong, L.; Laefer, D.F.; Bertolotto, M. Octree-based region growing for point cloud segmentation. ISPRS J. Photogramm. Remote. Sens. 2015, 104, 88–100. [CrossRef] [^42]: Boulaassal, H.; Landes, T.; Grussenmeyer, P.; Tarsha-Kurdi, F. Automatic segmentation of building facades using terrestrial laser data. In Proceedings of the ISPRS Workshop on Laser Scanning 2007 and Silvi Laser, Espoo, Finland, 12–14 September 2007; Volume XXXVI, pp. 65–70. [^43]: Schnabel, R.; Wahl, R.; Klein, R. Efficient RANSAC for Point-Cloud Shape Detection. In Computer Graphics Forum; Wiley Online Library: Hoboken, NJ, USA, 2007. [^44]: Awwad, T.M.; Zhu, Q.; Du, Z.; Zhang, Y. An improved segmentation approach for planar surfaces from unstructured 3D point clouds. Photogramm. Rec. 2010, 25, 5–23. [CrossRef] ## [^45]: Schwalbe, E.; Maas, H.-G.; Seidel, F. 3D building model generation from airborne laser scanner data using 2D GIS data and orthogonal point cloud projections. In Proceedings of the ISPRS WG III/3, III/4, Enschede, The Netherlands, 12–14 September 2005; Volume 3, pp. 12–14. --- [^46]: Moosmann, F.; Pink, O.; Stiller, C. Segmentation of 3D lidar data in non-flat urban environments using a local convexity criterion. In Proceedings of the 2009 IEEE Intelligent Vehicles Symposium, Xi'an, China, 3–5 June 2009. [^47]: Douillard, B.; Douillard, B.; Underwood, J.; Kuntz, N.; Vlaskine, V.; Quadros, A.; Morton, P.; Frenkel, A. On the segmentation of 3D LIDAR point clouds. In Proceedings of the 2011 IEEE International Conference on Robotics and Automation, Shanghai, China, 9–13 May 2011. [^48]: Besl, P.J.; Jain, R.C. Segmentation through variable-order surface fitting. IEEE Trans. Pattern Anal. Mach. Intell. 1988, 10, 167–192. [CrossRef] [^49]: Rabbani, T. Automatic Reconstruction of Industrial Installations Using Point Clouds and Images; NCG: Delft, The Netherlands, 2006. [^50]: Hofmann, A. Analysis of TIN-structure parameter spaces in airborne laser scanner data for 3-D building model generation. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2004, 35, 302–307. [^51]: Wang, C.-K.; Hsu, P.-H. Building Extraction from LiDAR Data Using Wavelet Analysis. In Proceedings of the 27th Asian Conference on Remote Sensing, Ulaanbaatar, Mongolia, 9–13 October 2006. [^52]: Höfle, B.; Hollaus, M.; Hagenauer, J. Urban vegetation detection using radiometrically calibrated small-footprint full-waveform airborne LiDAR data. ISPRS J. Photogramm. Remote Sens. 2012, 67, 134–147. [CrossRef] [^53]: Niemeyer, J.; Rottensteiner, F.; Soergel, U. Contextual classification of lidar data and building object detection in urban areas. ISPRS J. Photogramm. Remote Sens. 2014, 87, 152–165. [CrossRef] [^54]: Anguelov, D.; Taskarf, B.; Chatalbashev, V.; Koller, D.; Gupta, D.; Heitz, G.; Ng, A. Discriminative learning of markov random fields for segmentation of 3d scan data. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Diego, CA, USA, 20–25 June 2005. [^55]: Triebel, R.; Kersting, K.; Burgard, W. Robust 3D scan point classification using associative Markov networks. In Proceedings of the IEEE International Conference on Robotics and Automation, Orlando, FL, USA, 15–19 May 2006. [^56]: Meng, X.; Currit, N.; Zhao, K. Ground Filtering Algorithms for Airborne LiDAR Data: A Review of Critical Issues. Remote Sens. 2010, 2, 833–860. [CrossRef] [^57]: Rusu, R.B. Semantic 3D Object Maps for Everyday Manipulation in Human Living Environments. KI-Künstliche Intell. 2010, 24, 345–348. [CrossRef] [^58]: Campello, R.J.G.B.; Moulavi, D.; Sander, J. Density-Based Clustering Based on Hierarchical Density Estimates. In Lecture Notes in Computer Science; Pei, J., Tseng, V.S., Cao, L., Motoda, H., Xu, G., Eds.; Advances in Knowledge Discovery and Data Mining; Springer: Berlin, Germany, 2013; Volume 7819. [^59]: Hoover, A.; Jean-Baptiste, G.; Jiang, X.; Flynn, P.J.; Bunke, H.; Goldgof, D.B.; Fisher, R.B. An experimental comparison of range image segmentation algorithms. IEEE Trans. Pattern Anal. Mach. Intell. 1996, 18, 673–689. [CrossRef] ![Image](images/685603092fbb31b983d9836cd277057db1859b1f64c4c2f4bd923871c3b3468c.jpg) © 2019 作者所有。版权许可方：瑞士巴塞尔MDPI。本文为开放获取文章，遵循知识共享署名（CC BY）许可的条款与条件发布（）。