基于多结构快速生成算法的建筑物平面提取

谢 娇，吴云东，陈水利

(集美大学理学院，福建 厦门 361021)

0 引言

在数字城市建设中，空间信息数据是其赖以实现的不可或缺的基础支撑.而快速发展的三维激光扫描仪系统，也称LIDAR(Light Detection And Ranging)系统，对于空间信息数据的采集具有速度快、精度高、密度高和处理成本低的优点，故采用其获取城市空间信息数据是有现实意义的.建筑物作为城市地区中最重要的组成元素，正确地重建其模型是数字城市课题中的关键技术，也是目前亟需解决的问题.然而直接对建筑物数据进行重建，不仅增加数据处理的复杂度，而且可能造成系统资源的巨大消耗.为了后续数据处理的方便，所以对点云数据进行相应的分割处理[1-2].又由于平面是大多数建筑物表面的主要组成元素，故对建筑物进行平面分割或提取高精度的平面区域是建筑物重建的基础.

关于三维点云数据的平面提取或平面拟合问题，已有许多学者对其进行了研究，主要归纳为3种:基于随机一致采样 (Random Sample Consensus，RANSAC)[3-8]方法，基于霍夫变换方法[9-12]和基于区域生长[13-18]或聚类方法.在点云数据的平面分割上，基于区域生长的方法是在每点的法向量特征上实现的，然而每个点法向量的计算对噪声点敏感，且运算量巨大;基于霍夫变换的方法是利用所有数据获得所有可能的平面模型参数后再选择最优的参数，虽然能较准确分割平面，但效率低.而RANSAC的平面检测算法能够很好地解决以上问题，因为它并不需要计算法向量，也不需要选取所有数据获得模型，只是随机的产生一些平面模型，且每个模型只由原始数据中三个点构成，最优模型就在这些模型中选择.但是RANSAC算法的鲁棒性只在单模型的条件下才能得到保障，也就是在多平面结构的情况下它不能做出正确地检测.这是因为在随机采样模型时每个点的获得是独立的，多平面结构的数据集则需要采集很多模型才有可能包含正确的那个模型.

由Chin[19]等人提出的多结构快速假设生成算法，在结构采样上与RANSAC及其改进的算法比较，具有更高的准确率和更快的速度，特别在多结构数据集中.本文拟利用该算法对点云数据进行建筑物的平面检测.

1 多结构快速假设生成算法

输入点云数据后，随机地选择最小点集构成一些模型并计算相应的残差距离.通过对残差距离进行排序，计算任意两点的相似度，最后通过相似度驱动条件内点概率指导采样新模型.其流程为:输入点云数据—残差排列信息—计算两点相似度—基于条件内点概率采样—输出所有模型.

1.1 残差排序信息

设点集P={p1，p2，…，pN}作为输入点集，N为点的个数，在随机选择输入点集的最小子集n拟合出M个模型之后，就能对每个点计算其相对于M个模型的残差距离:ri，j=Hj(pi)，i=1，…，N;j=1，…，M，其中Hj表示第j个模型作用在点上的函数.计算每个点在M个模型下构成的残差向量为:Ri= [ri，1，ri，2，…，ri，M]，i=1，…，N，然后对每个点的残差向量进行升序排序:

其中，fi(1)，fi(2)，…，fi(M)是1，2，…，M 的一个排序.

1.2 计算两点的相似度

利用残差排序定义两点pi，pl的相似度函数:

其中1≤h≤M，并且两点的相似度函数值Φ(pi，pl)∈[0，1].

1.3 基于条件内点概率的采样

通过相似度函数驱动最小子集的条件采样，生成有效的新模型，有利于模型的鲁棒拟合.假设已经随机产生了M个模型，且生成一个模型的最小子集为n，通过条件内点概率函数指导采样下一个模型. 该模型表示为:E={pe1，pe2，…，pen}⊂ P，{e1，e2，…，en}⊂ {1，2，…，N}，其中第一个点 e1是从数据中随机选择的，即:e1～U(1，N)，然后利用第一个点的信息e1，构建第一个条件内点概率分布P1(i)指导采样第二个点e2:

其中α1为归一化参数.以此类推，利用前k个点的信息采样第(k+1)个点，对此需要构建第k个条件内点概率分布Pk(i)，

最后，一个新模型生成后，加入到原始的M个模型中，组成新的模型集.随之需要改变条件内点概率分布，因为每个点残差向量的改变，也就是在最后一列添加其对于新模型的残差距离，即:相应的参数 h随之改变，即:hnew=「0．1(M+1).

为了提高算法的效率，提出在生成b个新模型之后再对残差向量进行一次更新，这是因为单个新模型不会给内点概率带来多少信息.

2 点云数据的平面提取

实验数据为只有x，y，z三维信息的点云数据，总个数为N.由于立体空间中不共线的三点构成面，故最小子集n设为3.通过随机选择得到M个原始模型之后，利用多结构快速假设生成算法获得更多的模型，再从这些模型中选择含内点最多的模型，并将包含在该模型中的点从原始数据中提取和删除，循环上述操作直到原始数据中剩余的点小于0.3N.在判断点是否属于平面模型时，本文采用点到模型的残差距离即点到平面模型的距离.又因为激光扫描仪在扫描点云数据时由于精度问题，造成点云不够绝对准确，故需要给定阈值T，统一设定为0.05，具体的步骤为:1)输入点云数据，记入点云的个数N;2)在T时间内利用多结构快速假设生成算法，生成平面模型集;3)统计模型内点个数，选择内点个数最多的模型，并从原始数据中提取与删除该模型中的点;4)判断原始数据中剩余的点是否小于0.3N，若否，回到2)，若是，结束.

3 实验结果和分析

为了评估该算法的有效性，本文的测试数据采用Trimble公司FX型三维激光扫描仪采集的点云数据.点云数据是方形建筑物的一部分，包含单个平面和多个复杂平面的数据.实验平台:2.8GHz处理器，内存4G的windows 7的操纵系统.

为了能看出数据的结构，已经通过人工标定出共面的点，即同平面的点用同种颜色显示，其中白色的点为未加入考虑的点.图1主要是由单个平面构成的原始数据，其中面上的点即红色点个数为11559个，白色点个数为1128个.图2是由两个面构成的原始数据，其中红色点和黄色点的个数分别为2675和2461个.图3是平面结构复杂的原始数据，其中红紫色、绿色、红色、黄色、蓝色和白色含有点个数分别为3181、2259、4313、2198、814和1729个，由于蓝色点太少，本文将不对它进行提取.

图1 单个平面的原始数据Fig.1 Original data of single plane

图2 两个平面的原始数据Fig.2 Original data of two planes

图3 多个平面的原始数据Fig.3 Original data of multiple planes

把本文提出的算法与传统的RANSAC算法[3]作比较，测试数据为上述的3个原始数据.在以后的图像中，RandomSample代表RANSAC算法测试的结果，MultigsSample代表本文提出的算法测试的结果，且黑色为未考虑结构的点，其他颜色代表平面.实验对比结果见图4，量化结果如表1所示.在提取建筑物平面模型时，存在两种误差:第一种称为α型误差，指的是将非本平面的点错误地检测为本平面点;第二种称为β型误差，指的是本平面的点错误地检测为非本平面点.从图4中发现，应用本文提出的算法和RANSAC算法都能较好地检测出平面结构，很难区分哪个更好.结合表1和原始数据，发现检测的平面是存在误差的，其中每个检测平面存在的误差类型只是两种误差中的一种.对此，针对多平面数据，采用累加不同平面误差来统计数据的整体误差，结果见表2.不难发现，与RANSAC算法相比，本文算法的总误差更小，故本文算法更有效.

表1 RANSAC和Multigs检测平面的误差比较Tab.1 Error comparision of detecting plane by RANSAC and Mutigs

表2 RANSAC和Multigs检测平面的量化结果比较Tab.2 Quantitive comparision of detecting plane by RANSAC and Mutigs，cross means having no point

对效率的比较有两种方法，一是产生同样的效果时比较它们消耗的时间，另一是在相同时间内比较它们产生的效果.本研究选择后者，测试数据为图1—图3，测试时间为1 s，实验结果见图5.与原始图像相比较，图5a红点中夹杂着黑点，而图5b在视觉上看不出区别;图5c中含有红绿黄三色点，与原始图像中的两个平面不符，且其绿点中夹杂的黑色点比图5d中夹杂的点多;图5e中构建的平面结构不准确;图5f在视觉上与图3相比区别不大，故不难发现本文的算法比RANSAC算法效率高.

4 结论

本文提出了一种通过指导采样，从三维激光点云数据中检测与提取平面的新方法.与RANSAC算法相比，本文的方法不是完全的随机选择模型，而是采用条件内点概率的信息来指导采样模型，加快有效模型的生成.实验表明，本文的方法在点云数据的平面检测上具有有效性，且比RANSAC更具效率，尤其在多结构复杂模型的数据中.

虽然属于同个平面上的点可以准确提取，但是建筑物的重建需要通过线条来表示，故未来的研究方向是如何获取点云的轮廓线.

图4 RANSAC和Multigs检测平面的结果比较Fig.4 Camparision of detecting plane by RANSAC and Multigs

图5 RANSAC和Multigs在时间为1 s时检测平面的结果比较Fig.5 Comparision of detecting plane in one second by RANSAC and Multigs

[1]魏征.车载LiDAR点云中建筑物的自动识别与立面几何重建[D].武汉:武汉大学，2012.

[2]赵煦.基于地面激光扫描点云数据的三维重建方法研究[D].武汉:武汉大学，2010.

[3]FISCHLER M A，BOLLES R C.RANSAC:A paradigm for model fitting with applications to image analysis and automated cartography[J].Comm Of the ACM，1981，24(6):381-395.

[4]AMERI B，FRITSCH D.Automatic 3D building reconstruction using plane-roof structures[M].Washington DC:ASPRS，2000.

[5]BRENNER C.Towards fully automatic generation of city models[J].International Archives of Photogrammetry and Remote Sensing，2000，33(B3/1;PART 3):84-92.

[6]周春霖，朱合华，李晓军.随机抽样一致性平面拟合及其应用研究[J].计算机工程与应用，2011，47(7):177-179.

[7]BAUER J，KARNER K，SCHINDLER K，et al.Segmentation of building models from dense 3D point-clouds[C/OL]//Proc.27th Workshop of the Austrian Association for Pattern Recognition. [2013-12-12]http://scholar.googleusercontent.com/scholar?q=cache:h_7VdvfVjvUJ:scholar.google.com/++Segmentation+of+building+models+from+dense+3D+point-clouds＆hl=zh_CN＆as_sdt=0，5html.

[8]BOULAASSAL H，LANDES T，GRUSSENMEYER P，et al.Automatic segmentation of building facades using terrestrial laser data [J].International Archives of Photogrammetry，Remote Sensing and Spatial Information Systems，2007:65-70.

[9]HOUGH P V C.Method and means for recognizing complex patterns:U.S.Patent 3，069，654 [P].1962-12-18.

[10]戴楠，李传荣，苏国中，等.激光点云提取建筑物平面目标算法研究[J].微计算机信息，2010(7):205-207.

[11]DÉCORET X，DURAND F，SILLION F X，et al.Billboard clouds for extreme model simplification[J].ACM Transactions on Graphics(TOG)，2003，22(3):689-696.

[12]HULIK R，SPANEL M，SMRZ P，et al.Continuous plane detection in point-cloud data based on 3D hough transform[J].Journal of Visual Communication and Image Representation，2014，25(1):86-97.

[13]章毓晋.图像工程 (中):图像分析 [M].北京:清华大学出版社，2005:102-103.

[14]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.

[15]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.

[16]PETERNELL M，STEINER T.Reconstruction of piecewise planar objects from point clouds[J].Computer-Aided Design，2004，36(4):333-342.

[17]VERMA V，KUMAR R，HSU S.3D building detection and modeling from aerial lidar data[C]//IEEE Computer Society，Computer Vision and Pattern Recognition.New York:Andrew Fitzgibbon，2006:2213-2220.

[18]李云帆，马洪超.从LiDAR数据中提取建筑物平面目标的新方法[J].计算机工程与应用，2011，47(10):5-7.

[19]CHIN T J，YU J，SUTER D.Accelerated hypothesis generation for multistructure data via preference analysis [J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2012，34(4):625-638.