基于维度特征的RANSAC建筑物点云分割算法

刘 闯,花向红,田 茂,袁 达

(1.武汉大学 测绘学院，湖北 武汉 430079；2.武汉大学 灾害监测与防治中心，湖北 武汉 430079)



基于维度特征的RANSAC建筑物点云分割算法

刘 闯1,2,花向红1,2,田 茂1,2,袁 达1,2

(1.武汉大学 测绘学院，湖北 武汉 430079；2.武汉大学 灾害监测与防治中心，湖北 武汉 430079)

提出一种以建筑物表面形状特征为分割依据的改进RANSAC点云分割算法。该算法以主成分分析算法为基础计算维度特征和熵函数，并以熵函数最小准则确定最优邻域，继而进行表面形状分类，运用法向量夹角作为约束条件对分类结果进行优化。将分类结果作为随机抽样一致性(RANSAC)点云分割算法的模型选择依据，进行建筑物表面分割，采用法向量和距离等约束条件对分割结果进行优化，从而分割出具有不同形状的特征表面。实验表明：文中提出的改进的RANSAC点云分割算法是可行的，能有效保留表面特征。

维度特征；熵函数；点云数据；建筑物表面形状；改进的RANSAC算法

随着研究的不断深入，点云分割的算法理论已得到不断丰富和完善。在众多的算法中，随机抽样一致性算法(RANSAC)作为一种有效的稳健估计算法[1]，在建筑物表面分割方面有天然优势。李娜等[1]将点云的r半径密度引入RANSAC点云分割的判定准则中，并结合角度和距离等约束条件进行算法改进。胡伟等[2]将种子点的选取和点到距离的标准差等引入到屋顶面片点云的RANSAC分割中。Awwad等[3]提出以点云法向量与RANSAC分割平面的夹角剔除分割假平面的方法，提高分割质量。Martinez J等[4]提出通过对扫描数据定向改进RANSAC点云分割算法。但当涉及形状较为复杂的表面时，RANSAC一次仅能使用一个模型，而使用常规的一种模型分割，会造成分割的错误或不足，导致表面特征的丢失，为后续的曲面重建及建模工作带来不便；若使用两种或多种模型分别对点云分割，会导致部分点云分割错误或位于不同模型中。

Demantke等[5]提出通过计算维度特征，确定最优邻域和邻域的形状的方法。Yang等[6]成功地将维度特征与点云的其他特征相结合，使用支持向量机(SVM)方法实现不同物体的分类与提取。Pauly M等[7]提出通过自适应步长的PCA算法与轮廓模型相结合，从点云表面模型中提取线形特征的方法。Belton D等[8]提出用局部邻域构建协方差矩阵进行点云数据分类和特征提取的改进算法，并应用于分割之中。借鉴上述思想，为克服在表面形状较为复杂的建筑物分割中存在的分割不足或错误现象，本文提出一种以维度特征为基础，进行多类模型分割的RANSAC分割改进算法。

1 基于维度特征的RANSAC点云分割算法

为保证形状较为复杂的建筑物表面分割的正确性和特征的完整性，本文将以维度特征为基础的形状判断准则引入到RANSAC点云分割算法中，并针对形状判定准则存在的缺陷，提出以法向量夹角对其判定结果进行修正的方法。对分类后的形状选择不同分割模型分别进行RANSAC分割，并以法向量和距离为约束条件进行分割优化，有效保证分割的正确性和特征的完整性。

1.1 建筑物表面形状的分类

依据主成分分析(PCA)算法构建点pi的局部协方差矩阵C。由于C为对称正定矩阵，必存在特征值分解，即

(1)

分类时，首先，确定邻域搜索半径的下限rmin和上限rmax及变化步长rΔ，并设定初始搜索半径r为rmin，并以此令r=r+rΔ，根据搜索半径，对局部邻域内的点云运用PCA算法分别计算相应的维度特征和熵函数值，熵函数计算见式(2)，直至r>rmax。然后，比较并选出最小熵函数值，并将其对应的半径的覆盖区域作为最优邻域[3]，利用最优邻域对应的维度值区分不同形状。

Ef=-α1Dln(α1D)-α2Dln(α2D)-α3Dln(α3D).

(2)

(3)

1.2 建筑物表面形状分割

考虑到RANSAC算法是不加区分的对待所有数据，噪声点云会对分割造成一定的影响。为获得正确的建筑物表面模型，在建筑物表面形状分类的基础上，按照下列步骤进行分割：

1)按照RANSAC算法要求，需要在一定的置信概率下，获得求解模型参数的最小迭代次数M，满足关系式[1,9]

P=1-(1-(1-ε)m)M.

(4)

式中:P为能取得较好模型的概率，一般为0.9～0.99;ε为数据错误率;m为计算模型参数需要的最小点数。

2)从确定的建筑物表面形状中,随机选取m个点云数据，计算建筑物表面模型参数。按照欧氏距离判定准则进行局内点和局外点的判定，即通过计算点云至模型表面的几何距离d,若d在阈值δ范围内则是局内点，反之是局外点。按照RANSAC算法,直到构建M个模型为止。从M个模型中选取点云数最多的模型，当模型上点大于一定阈值时，利用这些点云数据，采用整体最小二乘方法求得模型参数，将此模型作为最优模型，并将此模型上的点从点云数据中剔除；否则跳出分割过程，将点云归为离散点。

3)对剩余的点，按照步骤2)进行建筑物表面形状提取，获取所有符合条件的模型。

(5)

2 实验与分析

为了考察本文提出的改进的RANSAC点云分割算法的可行性和效果，采用C++和OPENGL实现该算法，其算法流程如图1所示。

图1 改进的RANSAC点云分割算法流程

采用RIGEL_VZ_400地面三维激光扫描仪，对两种不同风格的建筑物进行扫描，设置采样间隔为0.03 m，其扫描的建筑物点云数据如图2所示。

2.1 表面形状分类分析

确定最优邻域是形状正确分类的前提。受PCA算法所需点云数的影响,根据相关统计，邻域范围内点云应在10个以上[3]，为此，本文设定rmin为0.08 m；考虑到建筑物A上部的圆体的体积大小，为尽量避免将曲面分为平面，设置rmax为3 m；在综合考虑分类的正确率和计算时间后，并将其平分为16份。按照1.1节方法分别计算相应半径的维度特征和熵函数，并比较熵函数大小选出最优邻域，并按式(1)进行形状分类，分类结果见图2。

由图2中分类后的点云可以看出，在选定最优邻域进行形状分类时，结果基本正确。此外，在界面的交界处点云被错误的分为三维曲面，且当结构凹凸较明显时，会将凹凸相交处的边界线分为三维曲面，如建筑物A中平面部分中的窗体边缘及凸出部分的边缘被判断成三维曲面。为此，本文通过计算表面上一点p及相邻点的法向量夹角Δθ，对比夹角与阈值的大小，对形状分类结果进一步处理。针对本文数据，设置夹角阈值为0.2°。处理前后的对比见表1。

由表1可以看出，建筑物A平面分类的准确率为74.9%，曲面分类准确率为80.2%；建筑物B分类的正确率可达到90.8%。采用以法向量夹角为约束条件对分类结果进行处理后，建筑物A平面分类准确率提高14.9%，曲面分类准确率提高8.1%；建筑物B分类准确率提高3.1%。

图2 扫描的建筑物点云

建筑物类别点云总数/个原始数据类别数量/个分类形状原始分类优化后分类数量/个正确率/%数量/个正确率/%建筑物A88128平面曲面803477781平面曲面线形平面曲面线形60229182971821147062426974.9---80.2-721526374182174568676989.8---88.3-建筑物B90182平面90182平面曲面线形818595680264390.8--846952844264393.9--

2.2 表面形状分割分析

在进行RANSAC点云分割时，为有效区分不同的形状模型，保证表面特征的完整性，本文根据采集数据结构凹凸的具体情况，设置距离阈值δ为0.2 m；此外，为减少离群点对分割的影响，在迭代计算模型时，将终止条件设定为最优模型的局内点数不少于总数的1/5。分割结果如图3所示。

由图3(a)可知，当采用一种模型(以平面模型为例)进行分割时，会导致上部的球体(仅取球面上位于斜平面上的点)和侧面屋檐(数据丢失)等特征信息的错误或丢失。采用本文方法可有效避免上述问题，如图3(b)所示。

图3 RANSAC分割结果

为了解决过度分割现象，如存在窗体和墙体不在同一平面等现象，本文采用平面法向量夹角阈值0.1°和平面间距0.25 m进行分割面的优化，其结果如图3(c)所示。由图3(c)可知，本文方法有效保留表面的特征，避免运行RANSAC仅能使用一种模型的缺陷。

3 结 论

本文通过引入维度特征进行形状的判断和分类，并通过法向量夹角进行优化，保证分类的正确性，后续进行RANSAC分割，既能有效避免采用不同模型分别对所有点云数据进行处理造成的点云分割错误或重复，又能保证分割的正确性与完整性。实验证明，通过本文的方法，能够有效克服仅使用一种模型的RANSAC分割造成的分割错误或不足，有效保留表面特征，为下一步的曲面重建和建模做好准备。

[1] 李娜,马一薇,杨洋,等.利用RANSAC算法对建筑物立面进行点云分割[J].测绘科学,2011，36(5):144-145.

[2] 胡伟,卢小平,李珵,等.基于改进RANSAC算法的屋顶激光点云面片分割方法[J].测绘通报，2012(11):31-34.

[3] AWWAD T M,ZHU Qing,DU Zhiqiang,et al.An improved segmentation approach for planar surfaces from unstructured 3D point clouds[J].The photogrammetric record,2010,25(129): 5-23.

[4] MARTINEZ J,SORIA-MEDINA A,ARIAS P,et al.Automatic processing of Terrestrial Laser Scanning data of building facades[J].Automation in construction,2012,22: 298-305.

[5] DEMANTKE J,MALLET C,DAVID N,et al.Dimensionality based scale selection in 3D lidar point clouds[J].ISPRS Workshop on Laser Scanning 2011: 29-31.

[6] YANG Bisheng,DONG Zhen.A shape-based segmentation method for mobile laser scanning point clouds[J].ISPRS Journal of Photogrammetry and Remote Sensing,2013,81:19-30.

[7] PAULY M,KEISER R,GROSS M.Multi-scale feature extraction on point-sampled surfaces[J].Computer graphics forum,2003,22(3):281-289.

[8] BELTON D,LICHTI D.Classification and segmentation of terrestrial laser scanner point clouds using local variance information[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Science,2006,36(5):44-49.

[9] 张蕊,李广云,李明磊,等.利用PCA-BP算法进行激光点云分类方法研究[J].测绘通报，2014(7):23-26．

[10] 李孟迪,蒋胜平,王红平,等.基于随机抽样一致性算法的稳健点云平面拟合方法[J].测绘科学,2015,40(1):102-106.

[责任编辑：张德福]

An improved RANSAC algorithm based on dimension feature in 3D point cloud of buildings

LIU Chuang1,2,HUA Xianghong1,2,TIAN Mao1,2,YUAN Da1,2

(1.School of Geodesy and Geomatics,Wuhan University,Wuhan 430079,China;2.Hazard Monitoring and Prevention Research Center,Wuhan University,Wuhan 430079,China)

An improved RANSAC algorithm for complex surface shape feature in buildings is proposed in this paper.The dimension characteristics and the entropy functions are calculated,and the optimal neighborhood is determined by the criterion of the minimum value of entropy function,and the surface shape is classified.The precision of the classification result is improved by the angle of the normal vectors.Models are selected in random sampling (RANSAC) algorithm based on the classification results,then the surfaces of building are segmented.The more precise surfaces are segmented by the normal vector and distance constraints.Experiment shows that the improved RANSAC algorithm is feasible,and the surface characteristics can be effectively kept.

dimension characteristic; entropy function; point cloud data; surface shape of buildings; improved RANSAC algorithm

引用著录：刘闯,花向红,田茂，等.基于维度特征的RANSAC建筑物点云分割算法[J].测绘工程，2017，26(1)：64-68.

10.19349/j.cnki.issn1006-7949.2017.01.014

2015-07-10

长江科学院开放研究基金资助项目(CKWV2014217/KY)

刘闯(1991-)，男，硕士研究生.

P207

A

1006-7949(2017)01-0064-05