顾及建筑物屋顶结构的改进RANSAC点云分割算法

李云帆， 谭德宝， 刘 瑞, 邬建伟

(1.长江水利委员会长江科学院，武汉 430010； 2.哈尔滨工业大学深圳研究生院，深圳 518055；3.深圳市房地产评估发展中心，深圳 518040； 4.城市空间信息工程北京市重点实验室，北京 100830； 5.武汉大学遥感信息工程学院，武汉 430029)

顾及建筑物屋顶结构的改进RANSAC点云分割算法

李云帆1， 谭德宝1， 刘 瑞2,3, 邬建伟4，5

(1.长江水利委员会长江科学院，武汉 430010； 2.哈尔滨工业大学深圳研究生院，深圳 518055；3.深圳市房地产评估发展中心，深圳 518040； 4.城市空间信息工程北京市重点实验室，北京 100830； 5.武汉大学遥感信息工程学院，武汉 430029)

针对传统RANSAC点云分割算法在处理多层次、多面片的复杂建筑物中的困难，提出一种改进算法对建筑物点云进行分割和几何基元的提取。首先,结合基于坡度和高差的三角形区域生长方法，对复杂建筑物的不同结构层次进行分解，提高了随机采样时的有效模型命中率，并降低了错分现象； 然后，提出一种浮动一致集阈值的RANSAC算法，通过自动调整RANSAC算法中的关键参数，使算法能够适应不同尺度的几何基元。实验证明了该算法在复杂建筑物点云数据分割效果和运算效率上的有效性。

LiDAR； 区域生长； RANSAC； 建筑物； 点云分割

0 引言

在机载LiDAR点云处理领域，分割始终是主要的研究方向之一[1-5]，其目的在于将大量数据进行一定层次的组织，以便于从中提取出有用信息，是点云目标识别的重要前提[6]。但是，目前点云分割算法研究还远未达到满足现实需求的水平，即使只是针对相对简单的平面特征，仍需要大量人工处理[6-7]。同时，现代城市的发展建造了大量具有多层次、多面片的复杂结构建筑物，点云分割问题更为复杂，寻找一种鲁棒、高效的建筑物点云分割方法是目前的研究热点。

近年来提出了大量点云分割算法，大致被分为3类： ①基于区域增长的分割算法[8-14]，该算法依据点坐标、法向量和表面粗糙度等属性制定生长规则，但是仍没有通用的规则适用于所有场景[10]； ②基于特征聚类的分割算法[2, 10, 15-16]，该算法提供了一种更灵活的一致性模式识别方法，但是从大量的散乱三维点云中进行特征估计和聚类分析非常耗时，同时也具有较大的噪声敏感性； ③基于模型拟合的分割算法，该算法用不同的几何形状基元通过互异的数学模型进行描述，将分割过程转变为各种数学模型的拟合过程，如三维Hough变换[17]和RANSAC[18]算法。这2种算法均可以用于自动处理点云数据，在建筑物的三维建模领域应用广泛，文献[19]对二者在效率和噪声敏感性等方面进行了详细的比较分析，指出RANSAC算法较Hough变换更适宜于点云分割。

虽然，RANSAC算法已是一种具有成熟性和优越性的点云分割方法，但是对于结构复杂的多层次、多面片建筑物，仍然存在一些不足。本文将在RANSAC基本原理的基础上，针对复杂机载LiDAR点云数据分割的难点进行分析，并提出一种改进的RANSAC算法。

1 RANSAC算法分析

1.1 RANSAC算法原理

根据RANSAC算法的基本原理[18]，在一次运算周期中只能提取出一个模型，并需要多次迭代，当一次运算周期结束，将属于最佳模型的一致集从原始的样本集中移除，依次迭代，直到从剩余的样本集中找出其余的模型，并设定一个剩余点数比例阈值作为迭代结束的条件。RANSAC算法包括3个关键阈值参数[18]，分别为拟合精度阈值、随机采样次数和有效一致集的大小阈值(简称为一致集阈值)。其中一致集阈值决定了通过随机采样得到的模型是否有效，为了确保得到正确的模型，一般要求一致集足够大，对于多尺度目标的检测成功率具有决定性的影响。通常情况下，上述参数均依据经验值设置，其自适应性问题也是目前的研究方向之一[6]。

通过对RANSAC算法的复杂度进行分析，表明RANSAC算法的效率由以下2个关键因素决定[20]： ①定义一个有效模型所需的最小样本集大小； ②评估每一个随机采样得到的几何基元的有效性所耗费的时间。RANSAC算法运行时，若要提升其效率，则必须降低候选几何基元的数量s，同时提高能够成功检测出最佳形状候选人的概率P(n)。这正是本文对RANSAC进行改进的依据。

1.2 RANSAC算法缺陷

传统的RANSAC算法用于复杂建筑物点云分割存在3个缺陷：

1)算法效率。由RANSAC算法原理可知对于数据量较大的复杂建筑物数据，如果笼统地对整体点云数据进行提取，那么具体到某一次搜索过程中，s的大小增加，相应的P(n)降低，算法耗时较长。文献[20]采用了基于八叉树的局部采样策略，在建筑物不同结构层次的边界处仍然存在八叉树的一个结点中同时包含了2个几何基元点云的现象，这同样会造成算法效率的降低。

2)点云错分割。针对建筑物中最常见的平面几何基元，RANSAC算法提取出的只是特征空间中数学意义上的平面参数，并非目标空间中带有边界约束的真实面片。为此文献[6]加入了法向量的约束，但是在多面片的复杂建筑物中仍会出现某2个不同的面片法向量相同，造成错分现象。

3)点云分割尺度。传统RANSAC算法中一致集阈值PN_S固定不变，但复杂建筑物往往由大小不一的多面片构成，采用固定不变的点数阈值会导致一个两难问题： 若采用较大的PN_S，那么小于此尺度的面片脚点则因为达不到有效的一致集阈值条件而无法提取； 若采用较小的PN_S，那么大于此尺度的平面在迭代过程中由于过早满足了有效一致集阈值条件，会造成较大平面的破碎。

2 RANSAC算法改进

2.1 结合区域增长的分割策略

复杂建筑物屋顶通常可以视为多个典型结构基元(平面、人字形和四坡型等)的组合。在点云数据中，这些结构基元相邻处存在高差，内部则存在连通性。利用这一特性能够将这些结构基元进行分解，然后以每个结构基元为约束分别在其内部进行平面提取，则可提高随机采样时得到正确平面最小点云集合的概率。同时，由于结构基元之间独立处理，也能降低错分效应的影响。

本文采用不规则三角网(triangulated irregular net,TIN)中的三角形作为增长单元。令建筑物点云生成的TIN为Dt，高程突变造成Dt中处于结构基元连接处的三角形斜率较大。三角形斜率可以通过三角形法向量与水平面的夹角进行定义。对Dt中所有三角形进行遍历，判断其斜率是否超限，并对其进行相应的标记。这个过程可以表述为

(1)

式中：Trij∈Dt；slope()为计算三角形斜率的函数；Slopemax为斜率阈值。

当结构基元之间的高差较大或飞机航高较低的情况下，结构基元之间也会存在遮挡现象，造成被遮挡区域所生成的三角形坡度较小，还需要增加高差条件对其进行约束。假设某个三角形Tri的3个顶点分别为p1，p2和p3，当满足式(2)时，可以认为其位于独立结构基元之间，即

max(zp1,zp2,zp3)-min(zp1,zp2,zp3)>ε,

(2)

式中：ε是事先设定的某个高差阈值；zp1，zp2和zp3分别为3个顶点的高程值。

在对Dt中的所有三角形都进行正确的标记之后，即可以通过文献[11]中提出的三角形区域生长算法将具有相同标记的三角形进行分组。

2.2 浮动一致集阈值的RANSAC算法

针对1.2节中缺陷3，本文提出一种浮动阈值的改进RANSAC算法，通过自动调整一致集阈值PN_S在某一个区间内由大到小浮动变化，实现多尺度面片的自动提取。假设每一次阈值调整之后，算法都能够正确提取该尺度下的所有几何基元，运行K次后达到最小一致集阈值的收敛条件，则有

PNmin=PNmax(Tfactor)K,

(3)

式中：PNmax和PNmin分别为平面包含点数的最大值和最小值，则PN_S∈[PNmin，PNmax]；Tfactor为阈值PN_S的收缩因子，Tfactor∈(0,1)。在迭代开始时PN_S0=PNmax，以较严格的一致集阈值准则检测较大的平面； 经过数次迭代后，算法无法得到有效一致集，说明以PN_S0为一致集条件的平面已检测完毕，则以PN_S1=PN_S0Tfactor为新的阈值，对剩下的样本集继续进行搜索，以检测较小尺度的平面； 以此类推，在第i次迭代中，PN_Si=PN_Si-1Tfactor； 达到收敛条件时迭代结束。

故可以得到最大迭代次数(MaxIteration)计算方法为

(4)

其中加入一个正整数n，用来保证迭代效果的完整性，实验证明通常情况下n取1即可。改进后的算法流程如图1。

图1 浮动一致集阈值的RANSAC点云分割算法流程Fig.1 Flowchat of point cloud segmentation base on floating consensus threshold RANSAC algorithm

3 实验与分析

为了验证本文所提出的改进RANSAC算法的效果，本文采用C++语言分别实现传统RANSAC算法以及本文所提出的改进算法，并以真实建筑物点云数据作为实验对象，对二者进行对比。

3.1 复杂多平面建筑物点云分割

选取同一测区内2栋复杂建筑物作为实验数据。平均点云密度约为2.5个/m2，航向点间距约为0.46 m，旁向点间距约为0.51 m。其中建筑物A包含10 837个激光脚点，建筑物B包含7 128个激光脚点。最小的面片约4.7 m×6.9 m，而最大的面片大小约为27.1 m×39.3 m，结构尺度跨度较大。实验数据如图2所示。

(a) 建筑物A点云数据 (b) 建筑物A航空影像

(c) 建筑物B点云数据 (d) 建筑物B航空影像

图2实验点云数据及其航空影像

Fig.2Experimentpointclouddatasetsandcorrespondingaerialimages

基于传统RANSAC分割算法[6]，2个建筑物的分割结果如图3所示。为了便于比较，分别使用接近最大面片的点云数目和略小于最小面片的点云数目2组不同的一致集阈值(PN_S)。

(a) 建筑物APN_S=550 (b) 建筑物APN_S=81

(c) 建筑物BPN_S=460 (d) 建筑物BPN_S=70

图3传统RANSAC算法分割结果Fig.3ResultsofclassicRANSACalgorithm

从图3中可以看出，由于采用较大的一致集阈值可以完整提取较大平面，如图3 (a) 1—3、图3 (c) 1—3，但较小的平面未能有效提取，黑色为未成功提取的脚点，如图3 (a) 4—7、图3 (c) 4—6； 采用较小的一致集阈值能够成功提取较小的平面，如图3 (b) 1—2、图3 (d) 1—2，但较大的平面出现了破碎，如图3 (b) 5—6、图3 (d) 3—4。实验表明了传统RANSAC算法的点云分割错误随分割尺度的变化规律： 阈值变大则欠分割情况增多； 阈值变小则过分割情况增多。另外，图3 (b)中3，4和7同时说明了对复杂建筑物数据整体进行平面提取会产生较严重的共面判断错误。

本文提出的改进RANSAC算法所采用的参数如表1所示。

表1 算法参数Tab.1 Parameters of the proposed algorithm

改进RANSAC算法分割结果见图4。通过对比图3与图4可以看出，本文改进算法得到的分割结果很好地解决了复杂建筑物中多尺度面片提取的问题，保证了平面的完整性，同时大大减少了共面判断错误的发生。

(a) 建筑物A (b) 建筑物B

图4改进RANSAC算法分割结果

Fig.4SegmentationresultsofimprovedRANSACalgorithm

3.2 改进RANSAC算法效率验证

为了验证本文算法在效率上的改善效果，利用多组数据，在采用相同关键参数的前提下与传统RANSAC算法进行比较。由于2种算法均需要计算脚点法向量，实验中将事先计算的法向量作为输入数据，其运算时间不计入统计。同时，由于RANSAC算法在采样上的随机性，本文将2种算法各运行10次并取其平均值作为最终结果。本文实验环境为Intel Core2 Duo T9300(2.5 GHz)/2 048 M内存/Windows XP(32 bit)，实验结果如表2所示。

表2 改进RANSAC算法效率实验结果Tab.2 Efficiency experimental results of improved RANSAC algorithm

图5传统RANSAC算法与本文算法运行效率对比

Fig.5EfficiencycomparationofclassicRANSACalgorithmwiththeproposedalgorithm

实验中1—5号建筑物均为多层次、多面片的复杂建筑物，6号建筑物在层次结构上相对简单， 7号建筑物不具有多层次结构。1—5号建筑物的对比实验证明，改进算法在复杂建筑物上具有明显的效率改进，其得益于结合区域增长的分割策略，提高了每次随机采样时有效模型命中效率。

同时，比较6和7这2组数据，发现建筑物7在运算时间上改进算法长于传统RANSAC算法，说明改进算法在建筑物7上并无优势。分析其原因，建筑物7为层次结构单一的建筑物，层次分组操作后只会得到一个结构分组，对后续的分割并无帮助，反而造成冗余计算，会耗费更多的运算时间。

4 结论

针对多层次、多面片的复杂建筑物，提出了一种顾及建筑物屋顶结构的改进RANSAC分割算法。得到如下结论：

1)对复杂建筑物的不同结构层次进行分解，提高了随机采样时有效模型命中率，同时能够大大降低算法的错分割现象；

2)自动调整RANSAC算法中的关键参数一致集阈值，能够尽可能适应各种大小的面片，从而改进了传统RANSAC算法的分割尺度问题。实验证明了改进算法在复杂建筑物点云数据分割正确率和运算效率上的有效性。

本文提出的改进算法同样也存在不足： ①仅考虑了一致集阈值的向下调整，而且收缩因子依靠经验值确定，主要原因在于事先缺乏对于建筑物面片大小的尺度分析； ②对于简单结构的建筑物，改进算法在运算效率上并无改善，需要研究如何对建筑物结构复杂程度进行快速判断，从而平衡建筑物结构分组与分割之间的计算资源； ③受制于RANSAC算法本身的原理，对于自由曲面建筑物的处理仍然需要进一步研究。

[1] Sapkota P P.Segmentation of Coloured Point Cloud Data[D].Endchede,The Netherlands:International Institute for Geo-Information Science and Earth Observation,2008:67.

[2] Filin S,Pfeifer N.Segmentation of airborne laser scanning data using a slope adaptive neighborhood[J].ISPRS Journal of Photogrammetry and Remote Sensing,2006,60(2):71-80.

[3] 程 亮,龚健雅.LiDAR辅助下利用超高分辨率影像提取建筑物轮廓方法[J].测绘学报,2008,37(3):391-393.

Cheng L,Gong J Y.Building boundary extraction using very high resolution images and LiDAR[J].Acta Geodaetica et Cartographica Sinica,2008,37(3):391-393.

[4] 黄先锋.利用机载LIDAR数据重建3D建筑物模型的关键技术研究[D].武汉:武汉大学,2006.

Huang X F.Research on 3D Building Model Extraction from Airborne LIDAR Data[D].Wuhan:Wuhan University,2006.

[5] 张小红,耿江辉.用不变矩从机载激光扫描测高点云数据中重建规则房屋[J].武汉大学学报(信息科学版),2006,31(2):168-171.

Zhang X H,Geng J H.Building reconstruction from airborne laser altimetry points cloud data set based on invariant moments[J].Geomatics and Information Science of Wuhan University,2006,31(2):168-171.

[6] Awwad T M,Zhu Q,Du Z Q,et al.An improved segmentation approach for planar surfaces from unstructured 3D point clouds[J].The Photogrammetric Record,2010,25(129):5-23.

[7] Boulaassal H,Landes T,Grussenmeyer P,et al.Automatic segmentation of building facades using terrestrial laser data[C]//ISPRS workshop on laser scanning and silvilaser.Espoo,Finland:ISPRS,2007:65-70.

[8] Besl P J,Jain R C.Segmentation through variable-order surface fitting[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1988,10(2):167-192.

[9] Vosselman G,Gorte B G H,Sithole G,et al.Recognising structure in laser scanner point clouds[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Sciences,2004,46(8):33-38.

[10] Biosca J,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.

[11] Gorte B.Segmentation of TIN-structured surface models[C]//Proceedings Joint International Symposium on Geospatial Theory Processing and Application.Ottawa,Canada:ISPRS,2002:465-469.

[12] Tóvári D,Pfeifer N.Segmentation based robust interpolation-a new approach to laser data filtering[C]//ISPRS WG III/3,III/4,V/3 Workshop “Laser scanning 2005”.Enschede,the Netherlands:ISPRS,2005:79-84.

[13] Rabbani T,Van den Heuvel F,Vosselman G.Segmentation of point clouds using smoothness constraint[C]//ISPRS Commission V Symposium “Image Engineering and Vision Metrology”.Dresden,German:ISPRS,2006:248-253.

[14] Pu S,Vosselman G.Automatic extraction of building features from terrestrial laser scanning[C]//ISPRS Commission V Symposium “Image Engineering and Vision Metrology”,Dresden,German:ISPRS,2006:25-27.

[15] Filin S.Surface clustering from airborne laser scanning data[C]//ISPRS Commission III Symposium “Photogrammetric Computer Vision”.Graz,Austria:ISPRS,2002:119-124.

[16] Hofmann A D,Maas H G,Streilein A.Derivation of roof types by cluster analysis in parameter spaces of airborne laserscanner point clouds[C]//IAPRS International Archives of Photogrammetry and Remote Sensing and Spatial Information Sciences.Dresden,Germany:IAPRS,2003,34:112-117.

[17] Hough P V C.Method and Means for Recognizing Complex Patterns:U.S.,Patent 3.069.654[P].1962-12-18.

[18] Fischler M A,Bolles R C.Random sample consensus:A paradigm for model fitting with applications to image analysis and automated cartography[J].Communications of the ACM,1981,24(6):381-395.

[19] Tarsha-Kurdi F,Landes T,Grussenmeyer P.Hough-transform and extended ransac algorithms for automatic detection of 3D building roof planes from lidar data[C]//ISPRS Workshop on Laser Scanning and SilviLaser.Espoo,Finland:ISPRS,2007:407-412.

[20] Schnabel R,Wahl R,Klein R.Efficient RANSAC for point-cloud shape detection[J].Computer Graphics Forum,2007,26(2):214-226.

AnimprovedRANSACalgorithmforbuildingpointcloudssegmentationinconsiderationofroofstructure

LI Yunfan1， TAN Debao1， LIU Rui2,3， WU Jianwei4,5

(1.YangtzeRiverScientificResearchInstitute,Wuhan430010,China; 2.ShenzhenGraduateSchool，HarbinInstituteofTechnology，Shenzhen518055,China； 3.CenterforAssessmentandDevelopmentofRealEstate,Shenzhen518040,China; 4.BeijingKeyLaboratoryofUrbanSpatialInformationEngineering,Beijing100830,China; 5.SchoolofRemoteSensingandInformationEngineering,WuhanUniversity,Wuhan430029,China)

An improved RANSAC algorithm was proposed for point cloud segmentation and geometric primitives extraction of buildings with multiple facets and complex roof structures, including two innovations. Firstly, the “split-segment” strategy combined with regional growth concept is proposed to improve the segment result and efficiency of classic RANSAC algorithm; Secondly, an improved RANSAC algorithm with variant consensus set threshold is presented. By automatically adjusting the consensus set threshold value, geometric primitives with scale difference are likely to meet the validity test, thus avoiding the over-segmentation and under- segmentation problems of classic RANSAC algorithm with fixed consensus set threshold.

LiDAR; regional growing; RANSAC; building; point clouds segmentation

10.6046/gtzyyg.2017.04.04

李云帆,谭德宝,刘瑞，等.顾及建筑物屋顶结构的改进RANSAC点云分割算法[J].国土资源遥感,2017,29(4)：20-25.(Li Y F,Tan D B,Liu R,et al.An improved RANSAC algorithm for building point clouds segmentation in consideration of roof structure[J].Remote Sensing for Land and Resources,2017,29(4)：20-25.)

TP 79

A

1001-070X(2017)04-0020-06

2016-05-18；

2016-08-22

中央级公益性科研院所基本科研业务费项目“车载激光雷达点云数据堤防地形三维重建研究”(编号： CKSF2014031/KJ)、城市空间信息工程北京市重点实验室经费资助项目(编号： 2015201)和国家自然科学基金项目(编号： 41771485)共同资助。

李云帆(1984-),男,博士,主要从事机载、车载激光雷达数据处理方向的研究。Email： liyunfan0828@gmail.com。

(责任编辑：陈理)