基于隨機森林方法的變電站三維建模點云自動分割

方彥軍，唐 勉，羅 嘉，龐志強

（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.