ABSTRACT

As an important step in the construction of digital city, the accuracy and completeness of point cloud classification will directly affect the accuracy of subsequent modeling. Based on the spatial structure of point cloud, this paper adopts a point cloud classification idea with cluster as unit, hoping to achieve a good classification effect while ensuring the integrity of ground objects. Firstly, a progressive morphological method is used to filter the point cloud, and the ground points are removed to make the ground objects more separable. On this basis, the Euclidean distance is used to cluster the point cloud; the eigenvalues of all points in the cluster at different scales are calculated, and the classifier is trained using two samples of trees and buildings; finally, building clusters are extracted by threshold segmentation. From the results, the method can basically achieve the complete classification of buildings.

Keywords:Point Cloud Classification, Euclidean Cluster, Morphological Filtering, Dimension Feature, PCA

一种基于欧氏簇提取的城市点云分类方法

陈尧丰^*，曹智翔

重庆交通大学土木工程学院，重庆

收稿日期：2018年11月20日；录用日期：2018年12月4日；发布日期：2018年12月11日

摘 要

点云分类作为数字城市建设的重要一步，其准确定和完整性将直接影响后续建模的精度。本文从点云空间结构出发，采用一种以簇为单位的点云分类思想，希望能在保证地物完整性的同时，也能达到一种良好的分类效果。首先是采用一种渐进形态学的方式对点云进行滤波处理，除去地面点使地物具有更好的可分性，再此基础上利用欧氏距离进行点云聚类；计算簇中所有点在不同尺度下的特征值，利用树木和建筑两个样本训练分类器；最后通过阈值分割提取建筑物簇。从结果上看，该方法基本能够达到建筑物的完整分类。

关键词 :点云分类，欧氏聚类，形态学滤波，维度特征，主成分分析

Copyright © 2019 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

三维激光扫描作为现阶段高效率的数据采集手段，其日益成熟的技术和不断走低的成本，使得它将会为未来数字城市建设提供完美的数据支持。全面、真实、准确地再现地理空间实体及其环境信息是数字城市建设的关键，也是3D GIS的核心研究问题之一 [1] 。

三维激光提供的反射强度是激光扫描的一大特点，在环境光暗淡的条件下仍能对目标具有一定的识别能力，程小龙 [2] 等人利用激光强度对测量值进行角度和距离的改正，并对建筑物立面点云进行分类和特征提取。除开点云强度和颜色信息，本文希望从点云的形状进行分析，基于三维坐标的数据研究是国内外点云研究的主要焦点。Bo Guo，Xianfeng Huang [3] 等人利用Joint Boost分类器对点云进行识别分类，这是一种监督分类方法，其实质是通过计算各种特征来估计学习模型的参数，并利用空间上下文约束对分类器进行优化。Martin Weinmann [4] 等人分析了邻域选择、特征提取和特征选择之间的关系，在此基础上提出了一种高效的语义注释方法。George Vosslman [5] 提出了一种分段空间上下文分类的方法，段邻接由图形模型中的边表示，手工选取种子点再基于法向量变化程度进行分组。孙森震，卢小平 [6] 等人构建出一种囊括点云的空间网格，利用网格中的点云密度、反射强度对网格进行分类。

本文采用一种以点云簇为单位的分类思想，首先是对点云进行的欧氏聚类，为了达到理想的聚类效果，可以利用渐进形态学聚类方式对地面进行分离过滤；在聚类的基础上，通过计算点云的多尺度下特征信息，并进行分类器的训练，利用分类器对簇内点云进行分类，最后采用阈值条件筛选有关建筑物的簇。

2. 欧几里德聚类

三维激光所提供的数据包括点三维坐标，色彩信息和强度信息，更一般的或是在夜晚采集的数据只包括三维信息和强度信息，在无法通过色彩进行聚类分割的情况下，点云的空间位置和形态将起到分类分割的主要作用。点云聚类的代表是k-means聚类算法，也是较为金典的无监督学习算法 [7] ，该方法需要设置合理的k值进行计算，而在丰富的城市地物中，特别是需要提供数字城市建模的原始数据时，尽可能区分原始地物是关键，因此本文采取最原始的欧氏聚类算法。

欧氏聚类属于划分式聚类，是最基础的聚类方法。欧几里德簇提取的本质是通过欧氏距离判断临近关系的大小来完成的。算法步骤为：1) 为输入的点云P创建一个Kd-tree搜索树；2) 设置一个空集群列表C_i和一个需要检查的点列队Q；3) 对P中每一个点p_i进行如下步骤：搜索在p_i点阈值半径内的近邻点 $P_k^i$ 并添加到集合Q中，再将Q中每个点p_i再次进行相同的操作，直到Q中的点不再增加，则将Q中的点添加到簇C_i中并清空集合Q；4) 通过步骤2和3处理剩余的点，并依次生成簇C₁、C₂、C₃∙∙∙∙∙∙。从过程中可以看出，欧氏聚类属于无监督分类，在缺乏限制条件的情况下很容易造成欠分割和过分割现象，因此需要对原始点云进行预处理工作。

3. 渐进形态学滤波器

地表物体通常情况下是单独不相连的个体，直接采用欧氏聚类会出现楼房与地面聚到一类的情况，为了避免这种情况，可以先提取路面点云。一种常用的去除地物的算法是数学形态学滤波器，数学形态学以集合理论为基础进行运算，有两个基本的操作：腐蚀和膨胀，结合在一起可以形成开闭操作，打开操作是通过对数据集进行腐蚀然后进行膨胀来实现的，而关闭操作是通过先进行膨胀然后进行腐蚀来完成的。对于机载激光扫描数据，在x和y处的高程z的膨胀定义为：

$d_p=\underset{\left(x_p,y_p\right)\in w}{\max }(zp)$

其中点(X_p，Y_p，Z_p)表示在p点窗口w内附近的点坐标。窗口可以是一维线或二维矩形或其他形状。膨胀输出为p附近的最大高程值。相对的腐蚀定义为：

$e_p=\underset{\left(x_p,y_p\right)\in w}{\max }(zp)$

Kilian [8] 等人提出了一种利用形态学滤波器去除非地面点的方法，但是实验表明：一个侵蚀操作删除了比窗户小的树对象，而扩张恢复了大型建筑对象，无法过滤大型建筑物，因此该方法只能运用到岩石表面的提取中。为了能够将形态学理论运用到城市地形提取中，本文采用一种渐进形态学滤波器 [9] 。

传统的滤波器中使用固定的窗口很难检测到大小不同的费地面物体，这个问题可以通过逐渐增加形态滤波窗口的大小来解决。对激光扫描的数据执行多次打开操作，通过一个逐渐增大的行窗口，渐进式形态过滤器可以从点云数据集中移除不同大小的建筑物和树木 [9] 。然而，滤波过程往往会产生一个低于地形测量值的表面，导致高起伏地形顶部的测量值不正确的去除，因为屋顶与地面的高程是突变的，地形高程变化是平缓的，所以可以通高差阈值检测非地面点，地面点的高差阈值表示为dh_d,k，初次计算采用初始高差阈值dh₀，并计算下一次迭代的高差阈值。应用数学形态学滤波时，窗口大小和高程阈值是取得良好效果的关键。对于窗口大小的选择通过线性公式：w_k = 2kb + 1，其b是初始窗口w₀的大小。高程差阈值和窗口的大小有关：

$d{h}_{T,k}=\{\begin{array}{l}d{h}_0\\ s\left(w_k-w_{k-1}\right)+d{h}_0\\ d{h}_{\max }\end{array}\begin{array}{c}\left(k=0\right)\\ \left(k\ne 0\right)\\ \left(d{h}_{T,k}\ge d{h}_{\max }\right)\end{array}$

其中k为迭代次数，s为地形的局部最大坡度。在城市地区的数据中，诸如汽车、树木以及人工建筑物将会在其几迭代中移除，而大型建筑物会在最后被移除。最高高差阈值设置为最低建筑物高度，以保证建筑物综合体的识别。

4. 多尺度下维度特征

描述场景在每个点和不同尺度上的局部维数特性，局部维数指的是云在给定位置和给定尺度下的几何形状：它更像一条直线(1维)、一个平面(2维)，还是分布在周围空间中(3维) [10] 。当结合不同尺度的信息时，我们可以建立标签来识别场景中某些类别的物体。在这种标识方法是结合空间上下文的，对于场景中的每一个点，计算其临近范围内的球体，将球内的点在笛卡尔坐标系下进行主成分分析(PCA)。对于第一主方向u₁可以通过所有点在其方向上的投影最大进行求解，则有：

$\{\begin{array}{c}\max \left\{u_1^{\text{T}}X{X}^{\text{T}}{u}_1\right\}\\ u_1^{\text{T}}{u}_1=1\end{array}$

通过构造拉格朗日函数：

$f\left(u_1\right)=u_1^{\text{T}}X{X}^{\text{T}}{u}_1+\lambda \left(1-u_1^{\text{T}}{u}_1\right)$

求得特征值λ₁以及单位向量u₁。而三维点云数据而言，主方向就有三个，分别用u₁、u₂、u₃表示，并同样通过构造拉格朗日函数计算。最后利用特征值方差比例：

$p_i=\frac{{\lambda }_1}{{\lambda }_1+{\lambda }_2+{\lambda }_3},\left(i=\text{1,}\text{2,}\text{3}\right),\left({\lambda }_1>{\lambda }_2>{\lambda }_3\right)$

这样就可以用(P₁，P₂，P₃)表示一点在尺度D下的维度特征。计算所有点在尺度D下的特征值，并以(P₁，P₂，P₃)为坐标分布在空间，接下来就需要一个超平面分割这些数据，常用的线性分类器为支持向量基(SVM)，该分类器作为二分类分类器，已经成熟地使用在图像处理中。该分类器同样适用于三维数据甚至多维数据分析中，其学习策略是建立超平面使分类间隔最大化。这里定义一组超平面函数方程：

${\omega }^{T}x+b=0$

对于三维数据而言，这里的x为(x_i，y_i，z_i)^T，该超平面作为分类器将数据划开，这个超平面可以用线性分类函数 $f\left(x\right)={\omega }^{T}x+b$ 表示，带入特征坐标，值的正负表示类别，值的大小表示点到超平面的距离，满足两类所有点距离超平面距离最大的计算方法可以通过构造拉格朗日函数。以上是在尺度D下的分类结果，接下来需要做的是在所有给定的度下计算所有点的维度特征，通过不同的尺度特征值去训练分类器，已达到最佳分类效果。

5. 实验与分析

数据来源于土木学院主楼前的广场，广场上有停放的车辆、树、灌木。采集工具为机载三维激光扫描仪，飞行轨迹为广场中轴线来回两次扫描。无人机搭载惯性导航和GPS差分定位，所采集数据均在WGS84坐标系下，为了方便计算，需要对数据进行坐标变换和裁剪，将点云坐标在E和N方向上整体减小，转换到自定义坐标系下，裁剪数据保留中轴线两边一定范围的数据，这部分数据遮挡少，扫描信息相对完整。

实验第一步是对数据进行欧氏簇提取，工具采用C++语言，结合PCL开源代码，完成对点云的滤波、聚类、以及分割提取等工作。利用数学形态学滤波，重点在于初始值的设置，根据测区点云的尺寸，设置最大检测窗口边长为20米，最大坡度为1，初始高差阈值为0.5米，最大高差阈值为3米，过程中将提取的路面点导入ground目录中，移除路面点云保留地物点云如图1。

设置数据的搜索结构，对点云建立一个kd-tree结构树，这是一个二进制结构树，它的分支只有两个，通过判别是与非的方式快速的搜索目标点附近的点。建立一个点云索引向量cluster_indices，将点的索引路径存放在0和1组成的多维向量中，以便每次检测到点云聚类都可以直接保存下来。

利用pcl::Euclidean Cluster Extraction模块构建分割器，设置分割阈值为0.5米，簇最小点数为100，由于存在大型建筑物，所以簇最大点数为1,000,000，设置搜索方法为之前的Kd-tree，最后输入点云数据，导出聚类结果并显示每一个簇对象如图2。

图1. 形态学滤波后的结果(结果仅保留地物信息)

图2. 欧氏聚类分割出的单位簇(簇总数为189个)

接下来就是分类器的训练，实验采用Brodu提供的CANUPO工具，该工具被整合到Cloud Compare的插件工具栏。由于SVM是二分类器，因此选取两个主要的地物作为训练样本，在选取建筑样本时需要注意零星点对特征值计算的影响。将样本添加到训练机中并设置尺度，初始尺度从0.5米开始，通过测试搜集了不同最大尺度与不同尺度个数下的训练结果，如表1。

表1. 不同尺度组合下的错分类比率

表1中分别列出了5种尺度组合，括号中是尺度个数，尺度越多说明尺度增长越密集，可以看出尺度并不是越多越好，这会分摊分割效果好的尺度的权重；另一方面最大尺度越大，分类效果越好，但是尺度增大会增加计算量，而且影响会越来越小。在实验中发现尺度如果取得太大的话，建筑和树木的错分割数会突然趋近一致，这种情况下的分类器泛用性就很低了，因此最大尺度也不能取得太大。这里取Max8 (16)尺度组合的分类器进行点云分类，结果如图3。

图3. 点云分类结果(深色点表示识别为建筑物，浅色点表示识别为植被)

结果显示该尺度组合基本分出了植被和建筑，再对之前提取的单位簇进行分析。从分类结果和表1数据中可以看出，部分建筑点云被识别为植被，植被的分类效果较好，为确保建筑物的完整性，规定深色点云数占总数的50%以上为建筑，反之为植被。阈值分割结果如图4。

图4. 通过阈值分割移除植被簇后的结果

6. 结论与展望

本文从原理上解释了一种地物分类的流程，首先基于渐进形态学的地表提取能够为欧氏聚类提供良好的条件，然后基于多尺度特征分析对所得的簇进行分类，最后进行阈值分割。从结果上看，欧氏聚类和阈值分割基本能够完成地物的分类提取，并且采用聚类分割，确保了建筑物数据的完整性，对数字城市的城市建模提供良好的数据支持。但是在实验中可以发现欧氏聚类和阈值分割仍有许多的缺点。首先是聚类结果不够理想，植物和建筑物靠得近，很容易将植被和建筑物聚到一起，这也使得后面的阈值分割遇到了很大的困难，有条件的进行欧氏聚类或许能够解决这个问题；其次，由于测区范围的建筑物比较明显，这里只是通过简单的阈值分割提取建筑物，在之后的研究中，可以增加阈值分段，簇的大小以及点数量作为条件提取不同的地物，或者以簇为单位进行空间上下文分析，随机样本一致性分析达到簇识别的目的。

文章引用

陈尧丰,曹智翔. 一种基于欧氏簇提取的城市点云分类方法
A City Point Cloud Classification Method Based on Euclidean Extract[J]. 测绘科学技术, 2019, 07(01): 5-11. https://doi.org/10.12677/GST.2019.71002

参考文献