采用模糊C均值方法进行激光点云分类

王书民，李文宁，张爱武

(1.中国地震局地震预测研究所，北京 100036； 2. 首都师范大学三维信息获取与应用教育部重点实验室，北京 100048)



采用模糊C均值方法进行激光点云分类

王书民1，李文宁2，张爱武2

(1.中国地震局地震预测研究所，北京 100036； 2. 首都师范大学三维信息获取与应用教育部重点实验室，北京 100048)

LiDAR波形数据的分解可以获得地物的几何坐标属性和物理属性信息。基于几何特征的点云分类方法较多，而对于波形特征分类方法的研究较少。本文首先对全波形数据进行分解得到了振幅、波宽属性，并结合振幅邻域特征提取振幅方差，得到了具有3个属性的激光点云数据；然后采用模糊C均值聚类方法进行了激光点云数据的分割。试验使用Riegl vz-400激光扫描仪采集到的数据验证了算法的可行性，可成功将研究区域中的树木、地面、建筑等进行分类。

波形特征；振幅；波宽；模糊C均值

地面激光雷达能够获取发射激光脉冲与地物接触后发射信号的全波形信息，揭示了地物的物理和几何信息，这些信息是地物分类的重要依据。杨必胜[1]提出了一种基于空间分布特征的点云特征图像生成方法，利用生成的特征图像结合阈值分割、轮廓提取和跟踪等理论实现了建筑和树木的提取，但是此方法需要设置的阈值较多，且计算复杂，各属性的权重难以确定。Li[2]提出了一种基于投影点密度的点云分割方法，但是此方法仅能提取房屋的边界，对于复杂的地物则难以适用。Yan[3]利用法向量结合多尺度空间理论提出了DoN(difference of normals)特征的计算方法,应用于点云的平面分割，然后结合欧氏聚类算法实现了点云的初步分割，此分割方法对于地物间距较大的区域分割效果较好，但是对于重叠地物分割效果则较差。卢秀山[4]提出了一种基于点云密度分布的数据格网化信息提取方法可以快速提取建筑物信息，但是提取精度较低。理论上如果能够提取更多的用于分类的激光属性信息就能够提高分类的精度，而以上方法都只是应用激光的几何信息。但是目前将波形特征应用于地物分类的研究还比较少，都伟冰[5]利用回波强度信息结合其他属性进行了道路的提取，此方法通过采样统计地物回波强度的分布范围，设定阈值提取道路，但仅能应用于强度信息差异明显的地物区分。骆社周[6]利用距离和角度校正后的回波强度提取植被用于叶面积指数反演取得了较好的效果，但不同的传感器和扫描环境对于回波强度的影响不同，给回波强度的校正带来了困难。

本文利用全波形激光点云数据的振幅、波宽属性信息，再统计分析振幅属性获得振幅方差特征，然后采用模糊C均值(fuzzy C-means，FCM)聚类方法分割地物，最后通过试验验证该方法的有效性。

一、波形特征提取

1. 振幅与波宽计算

由于激光遇地物点返回的回波波形近似呈高斯分布，接收到的能量由多个高斯波形叠加而成，为了得到激光的振幅、波宽参数，需要波形分解方法。目前最常用的方法是阻尼高斯-牛顿法最优化算法[7]。它根据高斯函数的标准差、波峰对应的位置及振幅的初值利用非线性最小二乘法得到初始误差平方和，之后不断优化初值，当目标函数的导数小于等于容差值或达到最大迭代次数时，停止迭代，最终得到每个目标物的振幅和半波宽。

2. 振幅方差特征计算

振幅方差的计算主要分为基于k-d树的邻域搜索与方差计算两个步骤。

(1) 基于k-d树的邻域搜索

首先需要明确一下最近邻点的定义，假设给定一含有N个点的样本集合Q，和一查询点p0(p0∈Q)，则p0的最近邻为p′，需满足

(1)

式中，两点之间的距离使用欧氏距离度量

(2)

式中，x0、y0、z0分别表示点p0坐标的3个分量。

在计算点云邻域时，最简单的方法就是计算中心点p0与所有点pi(pi∈Q)的距离，然后获得距离最近的那个点。考虑到点云的数据量较大，如果用此方法则耗时耗力。因此，选择构建k-d树加速点云的搜索。k-d树是一种带有其他约束条件的二分查找树，对于邻域搜索十分有用。如图1所示，k-d树的每一级在指定维度上分开所有的子节点。在树的根部所有子节点是在第一个指定的维度上被分开。树的每一级都在下一个维度上分开，所有其他的维度用完之后就回到第一个维度,从而建立k-d树。

图1　k-d树划分规则

k-d树建立之后，进行最近邻搜索，首先搜索二叉树结点，比较对应分裂维值的大小，小于进入左分支，大于进入右分支，按照搜索路径即可得到最近邻近似点；然后返搜索路径，判断路径上结点的其他子节点空间中是否存在离查询点更近的点，如果有，则进入到此节点空间进行搜素。重复此过程即可得到中心点的最近邻点。据此方法推广即可得到中心点p0的K近邻域点集Pk(k=1,2,…，K)。

(2) 方差计算

根据K近邻搜索得到的K个邻近点及其对应的振幅，利用方差求解公式即可得到点p0的振幅方差

(3)

二、模糊C均值分类

FCM是用隶属度确定每个数据点属于某个聚类的程度，是一种柔性的模糊划分。设FCM把n个点pi(i=1,2,…,N)分为K类，求每类的聚类中心，使得目标函数值最小。通过模糊划分计算每个点与所有类的距离获得隶属度u(0

(4)

(5)

(6)

由式(6)可得目标函数J(U,c1,c2,…,cc)达到最小的必要条件为

(7)

由式(6)—式(7)可得每个类别的聚类中心及所有点到该类的隶属度。FCM算法中聚类中心Ci和隶属矩阵U的确定通过迭代获得，如图2所示。

图2　FCM 分类算法流程

振幅是激光回波强度信息的直接表现，回波强度与地物的反射率呈正相关，即地物反射率越大激光强度的值越大。而反射率则由脉冲的波长、目标的材料及其表面的明亮程度决定。因此，对于同一激光扫描仪获得的点云数据，可利用点云的振幅不同区分目标地物。

(8)

式中，k为常数；PR为激光雷达系统记录的强度；R为激光距离目标的距离；A为目标有效相交面积；α为激光光束的入射角；μ为大气消光系数；ρ为目标反射率。

波宽与地物本身的性质有关。对于机载激光雷达来说不同地物波宽的区分度较小，但是对于地面激光雷达，扫描仪距离地物较近，测量精度高，能在一定程度上反映地物的类别。通过一定的方法可以将波宽用于地物的区分。

振幅方差是地物邻域中振幅变化程度的一种度量。由式(8)可知振幅的大小除了与地物的类型有关外，与激光的入射角、扫描仪与地物之间的距离也有很大的关系。对于建筑来说，某一激光点与其邻近点都位于同一个平面内，入射角相同且深度近似相等，振幅方差较小。而对于树木点云，用于树叶的不规则分布导致的入射角不同、激光点的深度存在一定的差异，其邻域内振幅变化较大，造成振幅方差较大。因此，通过计算振幅方差属性用于地面激光点云中树木与建筑物的分割。

高程是LiDAR数据中较稳定的信息，是机载激光分类的一个重要属性，但是对于地面激光雷达，高程仅能用于地面点的分离。因此，本文选择波宽、振幅、振幅方差3个属性构建FCM特征空间。

三、试验与分析

本文采用Rieglvz-400激光扫描仪获取的激光点云数据，试验场景内包括墙面、门窗、地面、树木、阶梯式看台等，共861 236个激光点，详细分割流程如图3所示。

图3　点云数据分割流程

1. 特征计算

试验使用Riegl扫描仪配套的处理软件，将波形分解为波宽、振幅两个属性。然后再计算振幅方差，本文选择了10个点的邻域进行计算。经过这种方法处理后每条记录包含了X坐标、Y坐标、Z坐标、波宽、振幅、振幅方差6个属性。将X、Y、Z坐标分别与波宽、振幅、振幅方差结合生成3个具有4个属性列的表文件，如图4—图6所示。

图4　按振幅显示

图5　按波宽显示

图6　按振幅方差显示

2. 基于振幅和波宽的FCM分割

FCM是一种非监督分类方法，但是在分类开始前需要指定分类的数目。由于本文研究区域内主要的地物类型有5种，因此，采用非监督分类的一般规则大于类别数的2倍，本文设为14个类别进行试验。试验获得的特征属性有振幅、波宽、振幅方差，分别对不同特征组合进行分类试验。考虑到振幅方差，其主要表现的特征为树木与其他物体之间的区分，需要对振幅方差属性单独分割。因此，本文分为振幅、波宽、振幅和波宽、振幅方差4个组合，得到分类结果如图7所示。图7左上为按振幅进行的FCM分类，图7右上为按波宽进行的FCM分类，图7左下为按振幅与波宽进行的FCM分类，图7右下为按振幅方差进行的FCM分类。

图7　初步分割结果

3. 空间域滤波

从非监督分类得到的结果可以看出，最后得到的结果是以单点的形式作为类别存在，对于一个邻近区域中虽然某一个类别的点数较多，但仍然存在错误点。因此，本文才用概率密度滤波算法对区域内的点进行平滑校正。

如图8所示，设一点o，通过k-d树搜索邻域50个点，蓝色点、绿色点、黄色点，分别标记类别为1、2、3 其中点个数大小为蓝色点>绿色点>黄色点。则将中心点o标记为蓝色点。通过此滤波算法对分类后的点云进行滤波处理，如图9所示，最终分割结果如图10所示。

图8　空间域滤波示意图

图9　空间域滤波结果

图10　模糊C均值分类结果

通过模糊C均值进行点云数据分类总体精度为92.742%，具体混淆矩阵见表1。

表1　模糊C均值分类的混淆矩阵

本文对同样的试验数据进行了k均值法分类，分类结果如图11所示，表2是k均值法分类的误差混淆矩阵，整体分类精度为总分类精度为90.213%，具体混淆矩阵见表2，将表1与表2进行对比可以发现，FCM各类别的误分类程度均小于k均值法分类的误分。

图11　采用k-mean分类结果

树地面建筑门看台树94．4650．4141．9670．0253．128地面0．46892．1255．5160．1861．705建筑3．69810．06380．4392．7353．065门0．3590．0094．06594．2361．331看台2．9993．0054．1080．08789．801

四、结束语

本文提出了一种结合点云数据的波形信息同时利用模糊C均值的分类方法，该方法利用了从激光波形数据中分离的波宽和振幅属性，并通过分析振幅的邻域方差获得振幅方差属性。较传统的激光点云分类方法相比具有更高的分类精度，在基于激光点云数据的地物分类识别上具有较大应用前景。

[1]杨必胜,魏征,李清泉，等.面向车载激光扫描点云快速分类的点云特征图像生成方法[J]. 测绘学报,2010,39(5):540-545.

[2]LI B J, LI Q Q, SHI W Z, et al. Feature Extraction and Modeling of Urban Building from Vehicle-borne Laser Scanning Data[J]. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci, 2004, 35: 934-939.

[3]IOANNOU Y, TAATI B, HARRAP R, et al. Difference of Normals as a Multi-scale Operator in Unorganized Point Clouds[C]∥3D Imaging Modeling Processing Visualization and Transmission (3DIMPVT), 2012 Second International Conference on.[S.l.]：IEEE, 2012：501-508.

[4]卢秀山,黄磊. 基于激光扫描数据的建筑物信息格网化提取方法[J].武汉大学学报(信息科学版),2007,32(10):852-855.

[5]都伟冰,王双亭,王春来.基于机载LiDAR粗糙度指数和回波强度的道路提取[J]. 测绘科学技术学报,2013,30(1):63-67.

[6]骆社周,王成,张贵宾，等. 机载激光雷达森林叶面积指数反演研究[J]. 地球物理学报,2013,56(5):1467-1475.

[7]MADSEN K, NIELSEN H B, TINGLEFF O. Methods for Non-linear Least Squares Problems[M]. Denmark: Informatics and Mathematical Modelling Technical University of Denmark, 2004 : 1-57.

The Classification of Laser Point Clouds Using Fuzzy C-means Method

WANG Shumin,LI Wenning,ZHANG Aiwu

王书民，李文宁，张爱武.采用模糊C均值方法进行激光点云分类[J].测绘通报，2016(10)：21-24.DOI:10.13474/j.cnki.11-2246.2016.0321.

2015-10-01；

2015-11-02

中国地震局地震预测研究所基本科研业务经费专项(2014IES0203)

王书民(1985—)，男，博士，助理研究员，研究方向为计算机视觉与摄影测量等方面。E-mail：wmcnu@163.com

P23

B

0494-0911(2016)10-0021-04