一种建筑物点云轮廓线的自动提取方法

秦家鑫，万幼川，何培培，陈茂霖，卢维欣，王思颖

（武汉大学遥感信息工程学院，武汉430079）

一种建筑物点云轮廓线的自动提取方法

秦家鑫，万幼川，何培培，陈茂霖，卢维欣，王思颖

（武汉大学遥感信息工程学院，武汉430079）

针对地面激光点云包含大量冗余数据、特征信息不明显等缺点，提出了一种自动提取建筑物点云轮廓线的方法。首先基于主成分分析和熵函数计算每个点的最佳邻域，再根据几何位置关系，滤除散乱点和平面中的点，保留轮廓线点云。针对不同地面激光点云数据，无需反复调整阈值。实验证明，该方法提取的建筑物点云轮廓线清晰完整，与现有方法提取的结果相比正确率有一定的提高，且冗余点云几乎全部被滤除，自动化程度高，具有良好的适用性。

地面激光扫描仪；主成分分析；熵函数；最佳邻域；轮廓线提取；LiDAR

0 引 言

地面激光扫描仪可以快速、精确、多方位地获取建筑物的三维信息［1］，但点云数据通常包括大量冗余数据，限制了后续的存储、处理等操作的速度和精度［2］。因此，如何在保留建筑物轮廓线点云的前提下，滤除散乱点和平面中的点，从而大幅度缩减点云数量，同时突出建筑物的特征信息，提高后续处理的计算速度和效率，成为当前研究的一个重点。

目前，国内外大多利用点的邻域信息来描述每个点的特征信息，从而保留特征突出的点云，滤除特征不明显的部分。Gelfand N、Bian Z、Yang Y L等人［3－5］利用积分不变量建立多尺度分析来提取点云特征，其中Gelfand N利用邻域点来拟合曲面，并用体积积分计算该曲面与半球包围的体积，用体积值描述点云特征。Rusu R B［6］在邻域点集中建立局部坐标系，以两个邻域点为一组，每组计算4个特征值，构建16维特征直方图，统计邻域点集的分布信息。Milroy M J、Yang M、Woo H等人［7－9］估计点云的法矢方向和曲率值，利用法矢方向和曲率值的突变来提取边界点。上述方法侧重点云的不同特征，提取的特征信息也有一定的差异，不能很好地适用于所有点云，且精度受邻域大小的影响。针对以上问题，基于文献［10］、文献［11］在维度方面研究的启发，本文提出了一种自动提取建筑物点云轮廓线的方案，该方案不受点云密度、点云分布等属性的影响，适用于不同情况的地面激光点云数据。实验结果表明，该方法提取的轮廓线清晰完整，且自动化程度较高。

1 原理与方法

基于现有的理论方法研究，文中设计了一种地面激光点云数据建筑物轮廓线的自动提取方案，流程图如图1所示。该方案主要包括3个关键步骤。

①主成分分析［12］。设定邻域范围，分别在不同邻域下进行主成分分析，得到3个维度特征值。

②获取最佳邻域并判定每个点的主维度。引入熵函数［13］，利用不同邻域下的3个维度特征值求出熵的最小值，并由此得到每个点的最佳邻域半径，以最佳邻域下的维度特征值，判定每个点的主维度，将原始点云分为线状点云、面状点云和散乱点云。

③轮廓线提取。利用空间几何关系对面状点云提取轮廓线，提取的面状点云轮廓线和线状点云的并集即为最终的轮廓线点云。

图1 流程图

1.1 主成分分析

不同地物的扫描点在三维空间中呈不同的分布形态，为了得到扫描点的分布信息，可以利用每个扫描点X及其邻域点vr的三维坐标｛Xi＝（xi，yi，zi）｜i∈vr｝构造协方差矩阵：

对矩阵C进行主成分分析，可求得3个特征值，对它们按降序排列，得到λ1≥λ2≥λ3＞0。令，根据式（2）计算每个点的3个维度特征，即一维线状特征a1D、二维面状特征a2D和三维散乱点特征a3D。其中a1D、a2D、a3D的和为1，换言之，a1D、a2D、a3D分别代表了扫描点属于3个维度特征的概率。为了得到每个点的主维度，引入主维度判定函数，见式（3）。

当σ1≫σ2、σ3时，a1D在3个维度特征值中最大，判定为一维线特征；同理当σ1、σ2≫σ3时，a2D最大，判定为二维面特征；当σ1≈σ2≈σ3时，a3D最大，判定为三维无序散乱点特征。

1.2 获取最佳邻域

点的维度特征会随着邻域点集的变化而改变，邻域半径r的取值会影响主维度的判定，有时甚至会有很大的差异性。对于点云中的每个点，理论上都存在一个最佳邻域半径r＊，使得邻域中的信息可以最好地描述出该点处的维度特征。为了计算出r＊，设定r的取值范围［rmin，rmax］，计算不同r值下邻域点集的熵：

当熵取最小值时，表示在此邻域下该点的主维度特征最突出，求出使熵函数取最小值时，最佳邻域半径r＊值：

在得到每个点的最佳邻域之后，按照式（1）、式（2）、式（3）得到每个点的主维度，将散乱点滤除，将线特征点视为点云轮廓线，对面特征点进行下一步轮廓线提取处理。

1.3 轮廓线提取

一般情况下，建筑物立面具有规整的几何形状，可看成由许多个平面构成，每个平面的特征信息为其轮廓线，故大量平面中的点是可以滤除的。本文利用空间几何关系，先为每个点确定其所在的平面，再判断此点是在平面的边缘还是平面内部，根据平面中的点与其邻域点形成的线段夹角和约为360°来滤除平面中的点，从而保留每个平面的轮廓线点云。具体步骤如下：

①根据1.2节得到的最佳邻域确定X点的最佳邻域点集vr＊。

②根据RANSAC算法，从vr＊中随机抽取两个不同点｛Xi，Xj｜i，j∈vr＊∩i≠j｝，并重复多次，计算X、Xi、Xj三点所在平面方程并统计vr＊中其余点到平面的欧氏距离和，选取使距离和最小的平面Sxpq的两邻域点Xp、Xq，将Xp、Xq从vr＊中删除。

③遍历vr＊计算每个∠XpXXi、∠XqXXi，设定角度阈值θ1，若∠XpXXi、∠XqXXi、∠XpXXq的位置关系如图2（a）、图2（b）、图2（c）的一种时，满足∠1＋∠2－∠3小于θ1；或者位置关系如图2（d）时，满足∠1＋∠2＋∠3－360°小于θ1，则认定该点在Sxpq上，否则将Xi从vr＊中删除。

④设 XXp为起始边，遍历vr＊计算每个∠XpXXi，设定角度阈值θ2，选取小于θ2中使∠XpXXi最小的邻域点X′1。

⑤判断X′1与Xp的方向，如果X′1在Xp的顺时针方向，就按照顺时针方向去搜索；否则，按照逆时针搜索下一个邻域点。

⑥将步骤④得到的邻域点与X构成的线段设为起始边，重复步骤④寻求满足条件的下一个邻域点X′2，X′3，…，X′n，直到搜索不到满足条件的邻域点。

图2 位置关系图

2 实验与分析

为了验证本文提出的方法的有效性，使用VC＋＋和OpenGL编程实现了该算法。实验中采用Riegl公司VZ－400激光扫描仪采集的华中师范大学正门及其周围环境点云。原始点云如图3所示。点云数量约为110万，点云平均精度约为6cm。点云数据对象结构复杂、材质多样，除一般建筑物水泥、玻璃窗以外，还包括钢板、LED显示屏、布制广告条幅等，在不同区域内点云密度差异较大，密度最大区域为400个／m2，而最小只有120个／m2。

图3 华中师范大学正门原始点云

设置邻域半径搜索范围为2cm到92cm，利用kd树快速获得邻域点集，半径每增加3cm计算一次维度特征和熵。如果邻域点个数大于50，选择最近的50个邻域点，否则选择所有的邻域点进行计算，得到最佳邻域下的主维度特征结果如图4所示。大部分点云主维度判定正确，但也存在少量的错分现象，例如少量树叶点云因其邻域范围内近似呈现线、面状分布而导致错误分类。

图4 最佳半径下点云主维度的判定结果

按照主维度将点云分类之后，对面状点云进行轮廓线提取。经试验，设θ1＝10°、θ2＝100°时效果最佳，该阈值同样适用于其他点云数据，不需要根据点云的密度、精度等属性重新设置。最佳邻域下提取的轮廓线整体效果如图5（a）所示，整体轮廓保留比较完整，大量散乱点和平面中的点被滤除，点云数量从110万降到17万，滤除率约为85%。细节部分如图6所示，图6（a）校门立柱和图6（b）屋顶的轮廓线清晰完整，平面中的点云几乎全部被滤除，结构相对比较复杂的图6（c）图中的“广埠屯”3个汉字轮廓也能明显看出。

图5 轮廓线整体效果图

为了说明邻域大小对实验结果的影响，同时证明本文提出方法的优越性，对全部数据点云在统一半径下进行了相同的处理，并对结果做了对比分析。通常，较大的邻域内各个维度呈现更大的区分性，但也有特殊的情况。为得到邻域大小对不同维度特征的影响，分别选取3个维度特征明显区域，统计其在不同邻域半径下的取值，如图7所示。

图6 轮廓线细节效果图

图7 中所取样本在点云中的位置在图3中用相应颜色的矩形标出。三幅图中，当熵取最小值时，对应的r＊为最佳邻域半径，此时主维度特征值为最大。图7（a）中，当r大于r′时，主维度特征值明显减小，原因主要是遇到拐点、直线方向改变，故点集趋于面状分布，二维特征值明显增加；图7（b）、图7（c）图中，当r小于r′时，邻域点数量不足，维度特征随r变化剧烈且无规律，不能反映出主维度特征。实验证明：①不同区域点云的最佳邻域差异较大，若使用统一的邻域对全部点云进行处理，必定会造成部分区域的分类错误，如图8所示；②邻域过大或过小都会影响主维度的判定；③主成分分析所需的最少邻域点个数约为10个，当点数不足时，计算结果无意义，应继续扩大邻域范围，直到邻域点个数满足要求。

图7 维度特征与邻域半径关系图

图8 最佳邻域和统一邻域下主成分分析结果

本次实验数据的建筑物对象包含了多种材质并且结构复杂，这就造成了点云密度在不同区域的明显差异。若使用统一邻域半径对点云进行处理，不但不能达到很好的效果，而且针对其他数据还需要重新修改邻域大小。对比实验中将邻域半径设为50cm，在此邻域下轮廓线提取效果如图5（b）所示，轮廓线保留得较为完整，但与图5（a）相比较，保留了过多平面中的点和散乱点，如红色矩形标示区域。细节对比如图8所示，图8（a下）由于r较小，导致部分散乱点错分为线特征；图8（b下）由于r较大，造成部分线、面点云错分为散乱点。表1定量分析了两者的分类结果，统计了当邻域取0.3m、0.5m、0.7m、0.9m时与最佳邻域下的对比结果。在统一邻域下，线特征的正确率下降得最多，仅为最佳邻域下的60%左右，线、面特征的正确率随邻域的增大引入散乱点而降低，而散乱点的正确率随邻域的增大变化不大，但正确率也只有最佳邻域下的80%左右。

为了验证本文提出的方法的优越性，引入对比实验，使用现有的点云特征提取方法对实验数据进行处理，计算点云的法矢方向和曲率值，根据法矢方向和曲率值的突变来提取边界点。表2为两种方法结果对比，其中A表示手动提取的点云个数，即特征点云个数；B表示运用本文方法和现有方法计算得到的点云个数。由表2可知，本文方法提取点云的正确率为92.98%，高于现有方法的83.85%；同时冗余数据被大量剔除，冗余率从25.85%下降为3.54%。

表1 最佳邻域与统一邻域的主成分分析结果统计／个

表2 本文方法与现有方法的实验结果统计／个

3 结束语

目前，地面激光已成为建筑物三维重建的一种重要数据源，但建筑物点云的轮廓线提取还处于研究阶段。本文提出的建筑物点云轮廓线自动提取方法，针对复杂建筑物点云能够正确计算出最能反映点云特征的邻域大小，并将点云按照主维度分类之后滤除散乱点云，再根据几何位置关系，滤除平面中的点。最终提取出的轮廓线点云清晰完整，冗余点云滤除率高，验证了算法的准确度和稳定性。在算法设计中特地将距离阈值转换为角度阈值，用每个点与邻域点的相对位置关系替代绝对位置关系，这样针对不同点云数据无需修改实验中的阈值，达到自动提取的目的，提高了算法的适用性。

［1］ 赵煦.基于地面激光扫描点云数据的三维重建方法研究［D］.武汉：武汉大学，2010.

［2］ 张瑞菊，王晏民，李德仁.快速处理大数据量三维激光扫描数据的技术研究［J］.测绘科学，2006，31（5）：93－94.

［3］ GELFAND N，MITRA N J，GUIBAS L J，et al.Robust global registration［C］.Symposium on geometry processing，2005，2（3）：5.

［4］ BIAN Z，TONG R.Feature－preserving mesh denoising based on vertices classification［J］.Computer Aided Geometric Design，2011，28（1）：50－64.

［5］ YANG Y L，LAI Y K，HU S M，et al.Robust principal curvatures on multiple scales［C］.Symposium on Geometry Processing，2006：223－226.

［6］ RUSU R B，BLODOW N，MARTON Z C，et al.Aligning point cloud views using persistent feature histograms［C］.Intelligent Robots and Systems，2008.IROS 2008.IEEE／RSJ International Conference on.IEEE，2008：3384－3391.

［7］ MILROY M J，BRADLEY C，VICKERS G W.Segmentation of a wrap－around model using an active contour［J］.Computer－Aided Design，1997，29（4）：299－320.

［8］ YANG M，LEE E.Segmentation of measured point data using aparametric quadric surface approximation［J］.Computer－Aided Design，1999，31（7）：449－457.

［9］ WOO H，KANG E，WANG S，et al.A new segmentation method for point cloud data［J］.International Journal of Machine Tools and Manufacture，2002，42（2）：167－178.

［10］ GRESSIN A，MALLET C，DEMANTKÉJ，et al.Towards 3Dlidar point cloud registration improvement using optimal neighborhood knowledge［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2013，79：240－251.

［11］ DEMANTKÉJ，MALLET C，DAVID N，et al.Dimensionality based scale selection in 3Dlidar point clouds［J］.International Archives of Photogrammetry，Remote Sensing and Spatial Information Sciences，Laser Scanning，2011.

［12］ GROSS H，JUTZI B，THOENNESSEN U.Segmentation of tree regions using data of a full－waveform laser［J］.International Archives of Photogrammetry，Remote Sensing and Spatial Information Sciences，2007，36（part 3）：W49A.

［13］ SHANNON C E.A mathematical theory of communication［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2001，5（1）：3－55.

An Automatic Building Boundary Extraction Method of TLS Data

QIN Jia－xin，WAN You－chuan，HE Pei－pei，CHEN Mao－lin，LU Wei－xin，WANG Si－ying
（School of Remote Sensing and Information Engineering，Wuhan University，Wuhan 430079）

In view of the redundancy of point cloud data and the shortcoming of unconspicuous features，this paper presents an automatic method of building boundary extraction.Firstly，the optimal neighborhood is acquired according to the principal component analysis and entropy function.Then，scattered points are deleted and boundaries of planes are extracted by geometry information.Experimental results show that this method can not only extract boundary completely and filter almost all improper point cloud data，but also has a high applicability and automaticity without adjusting threshold to different TLS data.

terrestrial laser scanner；principal component analysis；entropy function；optimal neighborhood；boundary extraction；LiDAR

10.3969／j.issn.1000－3177.2015.04.001

TP751

A

1000－3177（2015）140－0003－05

2014－06－17

2014－08－31

863计划（2013AA122104－3）；博士点基金（20130141130003）；国家科技支撑（2012BAJ15B04）。

秦家鑫（1989—），男，硕士研究生，主要研究方向为地面激光点云数据处理。

E－mail：qinjiaxin12345＠163.com