基于随机森林方法的变电站三维建模点云自动分割

方彦军，唐 勉，罗 嘉，庞志强

（1.武汉大学 自动化系，武汉 430072；2.广东省电力科学研究院，广州 510000）

0 引言

三维视觉技术在数十年的应用和发展中已逐渐成熟起来，将这项新兴技术运用于工业生产也随之成为研究的焦点。现阶段，我国变电站的信息可视化水平亟待提高，借助三维技术对变电站数据、图像、视频信息进行归纳展示将极大地提升其管理智能化程度。对变电站进行三维建模，由于对象场景较大，内容复杂，为保证模型获取的准确性及快速性，需对变电站实行激光扫描，获得的文件称为点云。一份点云文件所包含的大量点中存在着相当数量的冗余和噪声点，因此需要对点云进行聚类分割[1,2]，提取有效点再用于三维模型重构。

目前，许多学者都在大型场景的点云分割方面展开了重要研究。文献[3]针对曼哈顿式建筑大规模三维点云提出一种有效点自动分割提取方法，但适用对象局限于棱角分明的建筑物体。文献[4]提出一种通用型准则对城市非平坦区域的扫描数据进行分割。文献[5]利用隐含形状模型描述物体，借助霍夫森林架构对城市点云图像进行分块检测，并提出循环投票和距离权重投票机制。文献[6]通过总结测量数据中隐含的空间信息，采用基于八叉树的分割与合并方法帮助点云自动划分为若干个共面点集。文献[7]采用几何特征进行分割，这类方法对点云模型的要求极为严格，当其应用于粗糙实物点云时，容易产生过分割的问题。

当前使用的点云分割方法，其效果很大程度上都依赖对象点的分布情况或初始种子点的选取，因此鲁棒性不强。另外，对于变电站这种特殊的复杂场景，要在其三维扫描图中进行各类设备的模型自动识别本身也具有相当大的难度[8]。为了更好地解决上述问题，本文提出运用随机森林方法进行变电站点云聚类分割，通过不同的点特征获得不同的分类结果，再从中进行比较和决策，帮助无序点云进行无监督学习聚类，取得了较好的实验效果。

1 变电站点云特征分析

扫描获得的数据是成千上万个带有三维坐标信息（x, y, z）的点[9]，如图1所示。对深度图像平面分割的数学描述如下[10,11]：将深度图像看作一个数据集合S，分割所采用的特征量集合F-{F1，F2，…，Fn}，最终分割结果集合S-{S1，S2，…，Sn}。每个Si对应一个Fi，表示依据特征量Fi分割得到的点集拟合而成的一个曲面，n为要求的分割曲面数。

图1 变电站三维扫描全景图

点云分割根据一定的特征量或者特征量组合对点云进行聚类计算，也就是将原始点集分割成若干个具有简单形状意义且各自连通、互不相交的子集[12,13]。在不同的分割算法中，特征量的选择不尽相同。分析变电站设备模型的空间几何特性，除变压器箱体之外，形状比较特殊的计算对象主要有塔杆和绝缘子等。这些对象建模所用到最多的基本几何体为圆柱体，且在一定区域内这些物体的间隔固定，这是变电站点云分割工作可利用的一项特点。

就点云图中的每一单个点而言，其本身除了坐标信息之外，还需要计算一些特征作为点分类的依据[14]。空间曲面上任一点的法向量N是其重要的固有特征。计算单个点的法向量时，需借助该点周围相邻点所构成的面片来对其法向量进行估算[15]。由于一个点可与不同的相邻点构成不同的面片得到多个法向量，可采用平均加权的方法来做处理，如图2所示。

图2 点Pk的法向量计算

l为以Pk为顶点的三角形个数，αi为第i个三角形在顶点处的相对角，Vi为第i个三角形的法向量。则顶点Pk的法向量Nk计算公式如式(1)所示。

此外，每个点的曲率亦是其固有特征之一，它不随曲面的位置、方向或参数化方法的变化而变化[16]。最普遍的边缘检测判据则是梯度幅值阈值判据，Canny算子[17]使用高斯函数进行平滑后再由一阶微分的极大值确定边缘点。因此，每一点的梯度G及其与近邻点构成的曲率C也可作为聚类分割的特征判据。

2 点云分割

对变电站进行三维建模，用来描述其中各种大小的圆柱体所需的几何参数为底面半径、柱体高度、中心线矢量。要得到这些参数需要对点云图进行准确的区域分割。依据经典的欧几里得距离进行分类需要设计一个合理的距离阈值[18]，阈值设置不当会导致欠分割或过分割[19]。本文选择先以点密度为基础进行初步分割，如图3所示，然后利用随机森林算法对初步分割得到的聚类的边缘块进行更加精确的分类。

图3 根据点云密度进行初步分割

变电站点云分割的具体步骤如下：1）将三维点云图平均划分为n个方格；2）依据排列的空间位置对方格编号，依次计算每个方格的点密度Di(i=1,2…,n)；3）将D值相近且位置相邻的方格合并成一类，并更新该类的位置信息及点密度信息；4）重复步骤1）～3），直至聚类结果稳定；5）聚类结果中存在一部分特殊类，包含的是因点密度较小而独立出来的方格，称为边缘方格。使用随机森林算法对边缘格中的点进行计算和决策，使其能归于相邻的具有相似特征的聚类中，以完善分割结果；6）综合基于密度的初步分割以及基于随机森林方法的深入分割，得到最终的点云图分割结果。

3 基于随机森林方法的深入分割

随机森林方法适合于多分类问题；训练和预测速度快；对训练数据有较强的容错能力，即当数据集中有大量数据缺失时可通过数据预估保持结果精度不变；能够有效地处理大的数据集；可以处理没有删减的成千上万的变量；能够在分类的过程中生成一个泛化误差的内部无偏估计；并能检测到特征之间的相互影响以及重要性程度；不易出现过度拟合；实现简单且并行效率高。

3.1 随机森林算法

在机器学习中，随机森林由若干决策树组成，决策树将空间用超平面进行划分，每次分割都将当前的空间一分为二。这些决策树的形成采用了随机的方法，决策树之间没有关联。当测试数据进入随机森林时，就是让每一颗决策树进行分类，取所有决策树中分类结果最多的作为最终结果。随机森林就是一个包含多个决策树的分类器，其输出的类别是由个别树输出的类别的众数而定。其具体步骤如下：

步骤1：在n个随机样本中用放回取样的方式采样n次，用这n个样本来训练一个决策树，训练结束后用这棵树对剩余样本进行测试，并进行误差评估；

步骤2：设每个样本有M个属性，在决策树的某节点分裂时，从这M个属性中随机选取m个属性（m <

步骤3：决策树形成过程中每个节点都按照步骤2来分裂，如果下一次该节点选出来的分裂属性是刚刚其父节点分裂时用过的属性，则表示该节点已经达到了叶子节点，无须继续分裂了；

步骤4：重复步骤1～3，建立大量的决策树，如图4所示，用它们对新的计算数据进行分类，最终分类结果根据每个决策树的投票多少来决定。

由于随机森林每颗决策树的训练样本是随机的，树中每个节点的分类属性也是随机选择的，因此就能保证不会产生过拟合现象。

图4 依据不同分类属性生成决策树

3.2 针对变电站点云分割的算法设计

输入带有位置坐标及特征信息的点数据，点的三维坐标（可用于计算两点之间的方向距离或欧式距离）、法向量N、梯度G、曲率C作为样本属性。随机选取样本训练生成多棵决策树，运用决策树对边缘点进行聚类，进行多次决策与投票后，取投票数最多的结果为边缘点的归类结果。流程图如图5所示。

图5 随机森林进行边缘分割决策

三维图像的每个区域对应曲面物体上的一个有限曲面，分割完成后，可由相应的深度数据计算该有限曲面的几何矢量，并对分割后的曲面片以及它们的拓扑关系用特征关系图描述，最后根据这些特征矢量基于特征关系图匹配进行识别。

4 实验结果与分析

用以上提出的分割方法对变电站点云图进行聚类分割。关于初步分割划分方格的尺寸，根据变电站扫描图中点间距离，设置方格尺寸为2.5×2.5×2.5（坐标单位），如图6(b)所示。初步分割基于点云密度进行，粗略将点云图中的点密集部分分别成立为一个聚类Si（i=1,2, …, n），每个聚类包含的点记为P（x,y,z,N,C,G），其中（x,y,z）为每一点自带的三维坐标，而法向量N，梯度G，曲率C，则由公式计算得到。第二步，调用随机森林程序，将点密度较小的方格及其邻近方格中的点作为样本输入到程序中，训练生成的决策树对边缘点进行分类。

实验得到的结果如图6(c)、(d)所示。图6(c)用不同颜色显示出分割结果中的几个点分类作为示例；图6(d)进行简单的曲面拟合验证分割的效果。可以看出，在变电站错综复杂的几何结构下，点云分割效果很好。多次进行该算法的实验，其收敛结果稳定且一致，说明该方法鲁棒性较强。

图6 变电站点云分割

5 结论

将三维可视化技术应用于变电站管理系统有助于实现其在计算机上的仿真展示、导航定位、远程监测和作业推演等。而这些功能开发的前提是变电站三维模型的重构。点云分割是三维重构的关键基础。本文提出的点云分割方法借助随机森林算法为变电站三维扫描图中的点云数据实现了精准的聚类分割，而且对于变电站大规模点云数据的计算，该方法保持了很好的鲁棒性和稳定性，克服了其它算法在分割效果上对初始种子点选取的依赖性。为变电站的三维模型重构打下了可靠的基础。

[1] Tahir Rabbani Shah.Automatic Reconstruction of Industrial Installations Using Point Clouds and Images[M].Netherlands. 2006.

[2] Mac Queen J.Some Methods for Classification and Analysis of Multivariate Observations//Proc of the 5th Berkeley Symposium on Mathematical Statistics and Probability.Berkeley,USA,1967: 28l-297.

[3] Carlos A Vanegas,Daniel G Aliaga,Bedrich B. Automatic Extraction of Manhattan-World Building Masses from 3D Laser Range Scans.IEEE Transactions on Visualization and Computer Graphic.2012,18(10):1627-1637.

[4] Moosmann F, Pink O, Stiller C.Segmentation of 3D Lidar Data in Non-flat Urban Environments Using a Local Convexity Criterion[C].Proceedings of IEEE Intelligent Vehicles Symposium.Piscataway, NJ,USA,2009:215-220．

[5] Hanyun WANG, Cheng WANG, Huan LUO,Peng LI,et al.Object Detection in Terrestrial Laser Scanning Point Clouds Based on Hough Forest[J].IEEE Geoscience and Remote Sensing Letters,2014,11:1807-1811.

[6] Miao WANG,Yi-Hsing TSENG.Automatic Segmentation of Lidar Data into Coplanar Point Clusters Using an Octree-based Split-and-Merge Algorithm[J].Photogrammetric Engineering and Remote Sensing,2010,76(4):407-420.

[7] Douilard B,Underwood J, Kuntz N,et al.On the Segmentation of 3D Lidar Point Clouds[C].Proceedings of IEEE International Conference on Robotics and Automation Piscataway,NJ,USA:IEEE,2011:2798-2805.

[8] Clarice S,Alexandre P.Challenges in 3D Reconstruction from Images for Diff i cult Large Scale Objects A Study on the Modeling of Electrical Substations[D].2012 14th Symposium on Virtual and Augmented Reality

[9] 王小超,刘秀平,李宝军,张绍光.基于局部重建的点云特征点提取[J].计算机辅助设计与图形学学报.2013,25(5):659-665.

[10] Bianca Schon, Abu Saleh Mohammad Mosa, Debra F,Laefer.Octree-based indexing for 3D point clouds within an Oracle Spatial DBMS[J].Computers & Geosciences. 2013,51:430-438.

[11] 傅欢,梁力,王飞,赵季中.采用局部凸性和八叉树的点云分割算法[J].西安交通大学学报.2012,46(10):60-64.

[12] 柯映林,单东日.基于边特征的点云数据区域分割[J].浙江大学学报(工学版).2005,39(3):377-379.

[13] 孙永伟,孙殿柱,朱昌志,朱宗伟.散乱点云切片数据快速获取与优化[J].哈尔滨工程大学学报.2010,31(11):1514-1518.

[14] Mahmoud Fouad Ahmed, Carl T. Haas, Ralph Haas.Automatic Detection of Cylindrical Objects in Built Facilities[J].Journal of Computing in Civil Engineering,2014,28(3).

[15] 范剑英,于舒春,王洋,等.基于法向分量边缘融合的深度图像分割[J].计算机工程.2010,36(17):221-225.

[16] 王申怀,刘继志.微分几何[M].北京:北京师范大学出版社,1990.

[17] Canny J.A Computational Approach to Edge Detection[J].1EEE Transactions on Pattern Analysis and Machine Intelligence,1986,8(6):679-698．

[18] R. B. Rusu.Semantic 3D Object Maps for Everyday Manipulation in Human Living Environment. KI-Künstliche Intelligenz,2010,24(4):345-348.

[19] Ying ZHOU,Dan WANG, Xiang XIE, et al. A Fast and Accurate Segmentation Method for Ordered Lidar Point Cloud of Large-Scale Scenes[J].IEEE Geoscience and Remote Sensing Letters,2014,11:1981-1985.