顾及激光反射率的点云数据分割算法研究

叶珉吕,花向红

(1.佛山市城市规划勘测设计研究院,广东佛山 528000; 2.武汉大学测绘学院,湖北武汉 430079)

顾及激光反射率的点云数据分割算法研究

叶珉吕1∗,花向红2

(1.佛山市城市规划勘测设计研究院,广东佛山 528000; 2.武汉大学测绘学院,湖北武汉 430079)

点云数据分割是三维模型重建的关键环节,传统的基于模糊C均值聚类(FCM)的点云数据分割算法在规则物体细节的分割上具有一定的局限性。针对此问题,在传统算法的基础上,增加了激光反射率信息,提出了顾及激光反射率的分割算法。通过实例验证,该算法具有较高的可行性和普遍适用性,分类结果较为可靠。

点云数据;分割算法;激光反射率;FCM;三维模型

1 引 言

三维激光扫描技术以其数据获取速度快、实时性强、精度高及全天候工作等优点被广泛应用于逆向工程、数字城市及变形监测等领域,利用它可以对实物进行数字化,快速获取物体表面大量点的三维坐标、激光反射强度及颜色信息等,称为点云数据。对点云数据的分割是三维模型重建的基础,也是关键环节,分割的结果和效率直接决定了后续应用的难度,具有重要的研究意义[1]。点云分割是指将三维空间中的点划分成若干个互不相交的子集的过程,经过分割后,具有相似属性的点归为一类,得到一系列我们感兴趣的对象,如建筑、植被、街道等[2]。

目前,点云分割算法主要有以下三种:基于边检测的分割算法、基于区域增长的分割算法及基于聚类的分割算法[3]。基于边检测的分割算法根据点云的局部几何特征在点集中检测边界点,通过边界点的连接形成边界线将整个点云分割成多个独立的子点云,由于对边界的确定只用到边界的局部数据,使得该算法易受到测量噪声的影响。基于区域增长的分割算法根据给定的相似性准则,以一个选定的种子点向外延伸,同时判断周围的点是否满足同一准则,合乎准则的点被加入到同一区域中,直至其周围邻域不包含连续的点集为止。与基于边检测的算法相比,该算法容易实现而且计算速度快,受噪声的干扰也较小,但种子点选择的好坏对分割效果有很大的影响,如何得到一致的分割结果依然是一个有待解决的问题[4]。基于聚类的分割算法根据“物以类聚”的原则对数据进行分割,属于同一表面的点云数据具有某种相似的特征属性(如法向量、曲率等)。该算法无需选择种子点,且具有较强的抗噪能力,在机载或地面激光扫描点云的分割实例中,已显示出了它的健壮性[1],其中基于模糊C均值聚类(Fuzzy C-Means algorithm,FCM)的分割算法[4,5]已经较为成熟,被广泛应用于点云数据中建筑物、街道与植被之间的分割。目前基于FCM的分割算法主要是借助点云的位置信息、几何信息如法向量或曲率等特征属性进行数据分割,对于属性信息差别较大的数据能够获得较为理想的结果,但对于比较规则的物体,如在三维城市建模中,建筑物外观细节的分割却具有较大的局限性。

针对上述问题,在现有算法的基础上,提出一种顾及激光反射率的点云数据分割算法,并通过实例分析,验证该算法的可行性。

2 点云数据分割算法

2.1 传统算法

传统的基于FCM的点云数据分割算法根据点云的位置信息、几何信息等特征属性,通过引入隶属度矩阵表示属于不同类别的程度对数据进行分割,其基本思想是:首先初始化分类,之后通过反复迭代运算,考察每个样本的分类是否正确。若不正确,就要不断地计算类心和调整各样本的类别,直到使得以非相似性(或距离)为指标的目标函数达到最小。最后如果相邻两次的聚类中心没有任何变化,说明样本调整结束,目标函数已经收敛,算法结束。模糊C均值聚类算法能够使得各类本身尽可能的紧凑,而各类之间尽可能的分开。

设样本集X={X1,X2,…,Xn},n为样本集中元素个数,观测样本Xi具有m维特征属性{xi1,xi2,…, xim},其中包括点云位置信息即x、y、z坐标、几何信息如法向量或曲率等。

式中,k为聚类数,满足2≤k≤n;d(Xj,Ci)=‖Xj-Ci‖2为样本Xj和聚类中心Ci的欧几里得距离的平方;M为模糊度,一般M=2时算法最优[6];uij表示第j个样本和第i个聚类中心的隶属度,uij∈[0,1],且满足以下条件:

给定聚类数k及阈值ε,算法的具体计算步骤如下:

(1)初始化聚类中心Ci,i=1,2,…,k;

(2)计算隶属度矩阵;

(3)根据式(1)计算目标函数,如果其小于给定的阈值ε,则算法停止;

(4)循环(2)到(3)步直到每个聚类不再发生变化为止。

2.2 本文算法

扫描获得的点云数据中包含了三维坐标、激光反射率及颜色等属性信息,现有的算法更多的是借助点云的几何信息,从空间相似性上对数据进行分割,没有很好地利用激光反射率等特征属性。由于仅根据空间相似性,对于属性信息差别较大的数据,传统算法能够获得较为理想的分割结果,但对于比较规则或变化起伏不大的物体,却具有较大的局限性。

激光反射率是扫描目标对仪器激光束的反射回波的光功率[7],包含了目标表面的特征信息。一般情况下,同类型的地物具有近似的反射率特征,因此可以利用激光反射率作为点云分割的一个判别依据。在传统的基于FCM的点云数据分割算法的基础上,在观测数据的特征属性{xi1,xi2,…,xim}中增加反射率信息,形成本文提出的顾及激光反射率的分割算法,其目标函数和计算步骤同2.1中一致。

3 实例分析

3.1 实例一

使用三维激光扫描仪获取一点云数据,分别使用传统方法和本文方法进行数据分割,不同类别的点云使用不同颜色标出,结果如图1与图2所示:

图1 传统算法分割结果

图2 本文算法分割结果

图1 、图2中,红色数据为建筑物屋顶,蓝色数据为周边的树木,由两图可以看出,两种地物被很好地分割成了两类。相比于树木,建筑物比较规则,曲率等空间特性变化较小,两者属性信息相差较大,因此两种算法都能获得很好的分割结果。

对于建筑、植被、街道等地物,彼此之间的空间位置、几何特性等属性信息相差较大,而传统算法和本文算法都顾及了数据的位置、曲率等信息,因此,两种算法都能够有效地将它们分割开来,获得较好的聚类结果。

3.2 实例二

使用三维激光扫描仪获取一建筑物立面数据,分别使用传统方法和本文方法进行数据分割,不同类别的点云使用不同颜色标出,结果如图3与图4所示:

由于建筑物外观比较规则,曲率等特性变化不大,而传统算法仅依据空间属性进行分割,因此图3中数据被简单地平均分割成两部分。而由图4可以看出,由于增加了激光反射率信息,本文算法能够正确地将窗户(黄色)与墙壁(蓝色)分割开来,虽然两者都为规则平面,空间相似性较大,但两者材质决定了两者具有不同的反射特性,因此获得了理想的分割结果。

图3 传统算法分割结果

图4 本文算法分割结果

对于空间属性信息差别较小的地物分割,如建筑物外观细节的分割、不同材质路面的分割等,仅根据空间信息进行聚类的传统算法不能获得较为理想的结果;而本文算法在空间信息的基础上,增加了激光反射率信息,能够较好地将不同类型的地物区分开来,获得较为正确的分割结果,具有较高的可行性。

由上述两个实例可以看出,本文算法同时顾及了空间属性信息与反射率信息,对于任何类型的数据都能获取较好的分割结果,具有较高的可行性和普遍适用性。

4 结 语

在传统的基于FCM的点云数据分割算法的基础上,增加了反射率信息,作为点云数据分割的一个判别依据,提出了顾及激光反射率的分割算法。实例结果表明,对于空间位置、几何特性等属性信息相差较大的物体,传统算法和本文算法都能够获得较好的聚类结果;而对于空间属性信息差别较小的地物分割,仅根据空间信息进行聚类的传统算法不能获得较为理想的结果,由于不同类型的地物具有不同的反射率特征,本文算法在空间信息的基础上,增加了激光反射率信息,能够较好地将不同类型的地物区分开来,获得较为正确的分割结果,该算法具有较高的可行性和普遍适用性,分类结果较为可靠。

[1] 刘进,武仲科,周明全.点云模型分割及应用技术综述[J].计算机科学,2010,38(4):21～24.

[2] Pu Shi,Vosselman G.Automatic extraction of building features from terrestrial laser scanning[C]//International Archives of Photogrammetry,Remote Sensing and Spatial Information Science,2006,36.

[3] 喻亮.基于车载激光扫描数据的地物分类和快速建模技术研究[D].武汉:武汉大学,2011.

[4] Biosca J M,Lerma J L.Unsupervised robust planar segmentation of terrestrial laser scanner point clouds based on fuzzy clustering methods[J].ISPRS Journal of Photogrammetry and Remote Sensing,2008,63(1):84～98.

[5] Jiangtong Zhao,Deren Li,Yanmin Wang.Ancient Architecture Point Cloud Data Segmentation Based on Modified Fuzzy C-Means Clustering Algorithm[J].Proceedings of SPIEICEODPA 2008,Wuhan,China,2008,12.

[6] J.C.Bezdek,R.Hathaway et al.Convergence theory for fuzzy c-means:counter examples and repairs[C]//IEEE, Trans,PAMI,1987,17(5):873～877.

[7] Pfeifer N,Dorninger P,Haring A,et al.Investigating terrestrial laser scanning intensity data:quality and functional relations[C]//Proceedings of the VIII Conference on Optical 3D Measurement Technology,Zurich,2007:328～337.

[8] 杨荣华.地面三维激光扫描点云角度分辨率与数据处理模型研究[D].武汉:武汉大学,2011.

Research on Segmentation Algorithm considering Laser Reflectance for Point Cloud Data

Ye Minlv1,Hua Xianghong2
(1.Foshan Urban Planning Design and Surveying Research Institute,Foshan 528000,China; 2.School of Geodesy and Geomatics,Wuhan University,Wuhan 430079,China)

Segmentation algorithm for point cloud data is the key to the reconstruction of 3D model,the traditional segmentation algorithm based on fuzzy c-means algorithm has limitation on the segmentation of the regular object’s details.For this problem,on the basis of the traditional algorithm,the thesis adds the laser reflectance information to the algorithm and proposes a new segmentation algorithm considering laser reflectance.Verified by the examples,it is indicating that the new segmentation algorithm is more feasible and effective,its results are more reliable.

point cloud data;segmentation algorithm;laser reflectance;fuzzy c-means algorithm;3D model

1672-8262(2014)06-21-03

P234.4

B

2014—09—10

叶珉吕(1989—),男,助理工程师,主要研究方向为三维激光扫描技术。

国家自然科学基金(41174010)