模糊C-均值聚类对点云数据的分割

胡文庆， 施 昆，曹 影

(1.昆明理工大学，云南昆明 650000；2.西南林业大学，云南昆明 650000)



模糊C-均值聚类对点云数据的分割

胡文庆1， 施 昆1，曹 影2

(1.昆明理工大学，云南昆明 650000；2.西南林业大学，云南昆明 650000)

点云数据的分割是点云数据处理流程中的重要内容，同时也是点云数据三维重建的前提和基础。该研究在模糊C-均值聚类(FCM)算法的基础上，根据标靶点云和建筑物点云数据的不同特征进行实验，通过Matlab对地面雷达的标靶、建筑物点云数据进行分割，探讨模糊C-均值聚类算法对点云数据分割的可行性。实验结果显示，通过选择正确点云数据的特征属性，利用模糊C-均值算法对点云数据分割具有一定的可行性。

点云数据分割； 特征；模糊C-均值聚类；可行性

地面LiDAR是近年来兴起的一种获取三维数据和三维建模的空间信息技术，利用这种技术可以同步获取目标范围的点的集合(点云数据)，这其中包含着点的反射强度，三维坐标，色彩信息等三维立体信息，因地面LiDAR技术具有快速获取空间数据的优点而受到广泛关注。在对地面LiDAR点云数据的三维重建中，若直接对地面LiDAR点云数据进行三维重建，则会增加处理的复杂度和系统资源的消耗，因此要对点云数据进行相应分割。

点云数据分割是点云数据的标记过程，把属性相同或者相近、并且空间邻近的点划分为一类，最终得到若干个由属性相近的点云区域。点云数据分割是点云数据几何特征提取、分析和识别的基础，同时也是对点云数据三维重建的重要前提。它可以把复杂的点云数据按照属性特征进行分类，并进行组合，降低了三维建模的难度及复杂度，对其分割的精度也直接影响着后期点云数据三维建模的精度。

国内外学者对点云数据分割算法进行了很多研究，分割算法主要有3类，第一类以点与点之间的几何关系作为其阈值条件，以法向、曲率以及曲率的不连续点作为边界点的边界分割。Besl等通过计算每一个点的平均曲率和高斯曲率，并根据它们的符号将点云初始分割为8种不同的表面类型，然后利用双变量多项式曲面拟合进行区域增长，实现点云分割[1]；第二类基于区域生长的分割，把具有相似局部几何特征点划分为同一区域，这与聚类算法的思想比较相似。柯映林等提出了基于边的点云区域分割，他们利用提取的边特征栅格，通过空间栅格、邻近的曲率差可以识别提取的特征栅格，从而实现空间散乱点的分割[2]；Jiang等提出利用扫描线进行平面区域分割的方法[3]；董明晓等利用点云数据曲率的变化来实现点云数据区域分割[4]；龚友平等利用点云数据中的法矢和曲率等信息，实现了点云数据的区域分割[5]；Ahmad Kamal Aijazi等利用超体素分割方法对城市场景的点云数据进行了分割[6]。第三类则是通过聚类算法来实现点云数据的分割，根据点云数据的特征进行识别，将特征相同的点利用聚类算法分割在一起。Hoffman等根据方差准则聚类算法，利用点坐标及其相应的法向量将点云分割成面片[7]；李海伦等将基于遗传算法的模糊聚类算法来实现点云数据的分割[8]，孙红岩等利用K-means聚类算法来实现三维点云模型的分割[9]。

该研究利用模糊C-均值(Fuzzy C-Mean，FCM)聚类方法，并选择点云数据的不同特征，包括坐标特征，坐标与反射率组合特征为基础来对点云数据进行分割。

1 模糊C-均值算法介绍

模糊C-均值算法是基于划分的聚类算法，其基本思想是利用对象之间的相似性来实现目标对象的聚类[10]。模糊C-均值算法最早是由E.Ruspini的硬聚类算法导出，后来由J.C.Dunn等将硬聚类算法进行优化、拓展，形成了模糊C-均值算法(FCM)。它是根据最小二乘的原理，通过迭代法对目标函数进行优化来获得对数据的有效划分。

假如待分割对象是数据集X={x1,x2,…,xn}，每个分割对象中的点有m个特征属性，这些特征属性包括反射值、坐标、颜色信息等。假设X中样本xk对第i类的隶属度函数为uik(o≤uik≤1)。模糊C-均值聚类中要求所有样本点对于各个类的隶属度满足下式：

(1)

式中，C分类数。

模糊C-均值聚类算法目标函数的一般表述为:

(2)

(3)

式中，V为第i类聚类中心。A是对称正定矩阵，当A是单位矩阵I时，dik则为欧氏距离，当A不是单位矩阵I时，则为马氏距离(Mahalanobis)。Wm的值在一定条件下反映了聚类的紧致度，当聚类的紧致度越大时，则Wm的值越小。

法进行求解，可以得到隶属矩阵(4)及聚类中心(5)：

(4)

(5)

如果分类数C、数据集X及加权指数m是已知，则可以根据公式(4)、(5)来确定最佳模糊划分矩阵以及聚类中心。利用反复迭代进行计算，当算法收敛后，倘若满足下式：

μik=max{μ1k,μ2k,…,μCk}

(6)

则xk属于第i类。

2 基于FCM的点云数据分割

2.1 实验数据简介 此次实验所获取的点云数据是由徕卡HDS3000采集，所获取的点云数据见图1。

2.2 实验结果与分析 通过利用Matlab对模糊C-均值聚类算法进行编程实现点云数据的分割。利用选择点云数据的不同特征属性，研究模糊C-均值聚类对点云数据的分割效果。图2为FCM对点云数据进行分割的流程图，取dik为欧氏距离，加权指数m=2。

图1 原始点云数据

图2 FCM算法流程

2.2.1 以点的坐标作为特征所得的聚类效果。通过不同的颜色信息来反映模糊C-均值聚类对点云数据分割的效果，实验结果见图3。

从图3可以看出，如果只是选择点的坐标作为特征，不论C选取为何值，都无法通过模糊C-均值聚类对点云数据进行正确的分割。

2.2.2 以点的坐标和反射率作为特征的聚类结果。以点的坐标和反射率作为特征进行聚类，实验结果见图4。

从图4可以看出，当以点的坐标和反射率作为特征时，模糊C-均值聚类的分割结果则很明显。相比于只选择点的坐标为特征的分割结果，其分割效果要好很多。对于标靶点云数据，在选取适当的分类树C和反射率，利用FCM聚类对其进行分割；而对于建筑物点云，建筑物的墙面、门和窗户能较好的分割出来，但在树木和建筑物相参杂的部分，其分割的效果较差。

通过模糊C-均值聚类对地面LiDAR点云数据的分割实验可知，在选择合适的特征和参数时，对点云数据的分割还是有较好的可行性。但如何提高分割的精度、如何选择合适的特征参数还需要进一步的研究。

图4 以点的坐标和反射率为特征的分割结果

3 结语

随着激光扫技术的发展，其应用也渗透到城市规划、监测、军事等各个领域，而如何提取、分析和识别其获取大量的实时、动态、高精度的点云数据，也将是研究的重要部分。该研究基于模糊C-均值聚类算法，选择合适特征参数，有效地对点云数据进行了分割，证明其可行性。为提高点云分割的效果和精度，则需要选择合适的特征，确定算法中的关键参数。如何选择更合适的特征、确定算法中的关键参数和改进算法来使得点云分割更加自动、精度更高，是今后通过模糊C-聚类对点云数据进行分割的重要研究内容。

[1] BESL P J，JAIN R C.Segmentation through variable-order surface fitting[J].PAMI,1988,10(2):167-192.

[2] 柯映林,单东日.基于边特征的点云数据区域分割[J].浙江大学学报：工学版，2005,39(3):377-380，396.

[3] JIANG X Y，BUNKE H，MEIER U.Fast range image segmentation using high-level segmentation primitives[C]//Proc.of the 3rdIEEE workshop on applications of computer vision.Washington,DC,USA:IEEE Computer Society,1996.

[4] 董明晓，郑康平，许伯彦.一种点云数据的区域分割方法[J].机械设计，2004，21(10)：38-40.

[5] 龚友平，金涛，童水光.点云数据区域分割方法[J].工程图学学报，2006(4)：8-13.

[6] AIJAZI A K,CHECCHIN P,TRASSOUDAINE L T.Segmentation based classifi cation of 3D urban point clouds:A Super-Voxel based approach with evaluation[J].Remote Sens,2013,5(4):1624-1650.

[7] HOFFMAN R，JAIN A K．Segmentation and classification of range images[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1987，9(5):608-620.

[8] 李海伦,黎荣,丁国富，等.应用遗传模糊聚类实现点云数据区域分割[J].计算机应用研究，2012，29(5)：1974-1976.

[9] 孙红岩，孙晓鹏，李华.基于K-means聚类方法的三维点云模型分割[J].计算机工程与应用，2006(10)：42-45.

[10] 高新波.模糊聚类分析及其应用[J].西安：西安电子科技大学出版社，2004.

Segmentation of Point Cloud Data with Fuzzy C-means Clustering

HU Wen-qing1, SHI Kun1, CAO Ying2

(1. Kunming University of Science and Technology, Kunming, Yunnan 650000; 2. Southwest Forestry University, Kunming, Yunnan 650000)

Point cloud data segmentation is an important part of the point cloud data processing flow, but also the premise and basis of three-dimensional reconstruction of point cloud data. Based on the fuzzy C- means clustering (FCM) algorithm, according to different characteristics of the target point cloud and building point cloud data, the target of the ground radar and buildings point cloud data was segmented with Matlab, the feasibility of fuzzy C- means clustering algorithm to segment the point cloud data was explored. The experimental results show that, by choosing the correct feature point cloud data, using the fuzzy C- mean algorithm has certain feasibility of point cloud data segmentation.

Point cloud data segmentation; Feature; Fuzzy C- means clustering; Feasibility

胡文庆(1991- )，男，江西抚州人，硕士研究生，研究方向：3S技术。

2015-04-24

S 127

A

0517-6611(2015)17-353-04